This repository has been archived on 2024-12-16. You can view files and clone it, but cannot push or open issues or pull requests.
CodeBlocksPortable/Borland/BCC55/Include/Rw/tree.cc

637 lines
19 KiB
C++
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

#ifndef __TREE_CC
#define __TREE_CC
#pragma option push -b -a8 -pc -Vx- -Ve- -w-inl -w-aus -w-sig
/***************************************************************************
*
* tree.cc - Non-nline tree definitions for the Standard Library
*
***************************************************************************
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
***************************************************************************
*
* Copyright (c) 1994-1999 Rogue Wave Software, Inc. All Rights Reserved.
*
* This computer software is owned by Rogue Wave Software, Inc. and is
* protected by U.S. copyright laws and other laws and by international
* treaties. This computer software is furnished by Rogue Wave Software,
* Inc. pursuant to a written license agreement and may be used, copied,
* transmitted, and stored only in accordance with the terms of such
* license and with the inclusion of the above copyright notice. This
* computer software or any other copies thereof may not be provided or
* otherwise made available to any other person.
*
* U.S. Government Restricted Rights. This computer software is provided
* with Restricted Rights. Use, duplication, or disclosure by the
* Government is subject to restrictions as set forth in subparagraph (c)
* (1) (ii) of The Rights in Technical Data and Computer Software clause
* at DFARS 252.227-7013 or subparagraphs (c) (1) and (2) of the
* Commercial Computer Software Restricted Rights at 48 CFR 52.227-19,
* as applicable. Manufacturer is Rogue Wave Software, Inc., 5500
* Flatiron Parkway, Boulder, Colorado 80301 USA.
*
**************************************************************************/
#include <stdcomp.h>
#ifndef _RWSTD_NO_NAMESPACE
namespace __rwstd {
#endif
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__deallocate_buffers ()
{
while (__buffer_list.data())
{
__buffer_pointer tmp = __buffer_list;
__buffer_list = (__buffer_pointer)(__buffer_list.data()->next_buffer);
__node_alloc_type(__buffer_list).deallocate(tmp->buffer,tmp->size);
__buffer_alloc_type(__buffer_list).deallocate(tmp,1);
}
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>&
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
operator= (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& x)
{
if (!(this == &x))
{
//
// Can't be done as in list because _Key may be a constant type.
//
erase(begin(), end());
__root() = __copy(x.__root(), __header);
if (__isNil(__root()))
{
__leftmost() = __header; __rightmost() = __header;
}
else
{
__leftmost() = __minimum(__root()); __rightmost() = __maximum(__root());
}
__node_count = x.__node_count;
}
return *this;
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
__insert (__link_type x, __link_type y, const _Val& v)
{
__link_type z = __get_node(v);
++__node_count;
if (y == __header || !__isNil(x) || __key_compare(_KeyOf()(v), __key(y)))
{
__left(y) = z; // Also makes __leftmost() = z when y == __header.
if (y == __header)
{
__root() = z; __rightmost() = z;
}
else if (y == __leftmost())
__leftmost() = z; // Maintain __leftmost() pointing to minimum node.
}
else
{
__right(y) = z;
if (y == __rightmost())
__rightmost() = z; // Maintain __rightmost() pointing to maximum node.
}
__parent(z) = y;
x = z; // Recolor and rebalance the tree.
while (x != __root() && __color(__parent(x)) == __rb_red)
{
if (__parent(x) == __left(__parent(__parent(x))))
{
y = __right(__parent(__parent(x)));
if (!__isNil(y) && __color(y) == __rb_red)
{
__color(__parent(x)) = __rb_black;
__color(y) = __rb_black;
__color(__parent(__parent(x))) = __rb_red;
x = __parent(__parent(x));
}
else
{
if (x == __right(__parent(x)))
{
x = __parent(x);
__rotate_left(x);
}
__color(__parent(x)) = __rb_black;
__color(__parent(__parent(x))) = __rb_red;
__rotate_right(__parent(__parent(x)));
}
}
else
{
y = __left(__parent(__parent(x)));
if (!__isNil(y) && __color(y) == __rb_red)
{
__color(__parent(x)) = __rb_black;
__color(y) = __rb_black;
__color(__parent(__parent(x))) = __rb_red;
x = __parent(__parent(x));
}
else
{
if (x == __left(__parent(x)))
{
x = __parent(x);
__rotate_right(x);
}
__color(__parent(x)) = __rb_black;
__color(__parent(__parent(x))) = __rb_red;
__rotate_left(__parent(__parent(x)));
}
}
}
__color(__root()) = __rb_black;
return iterator(z);
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::pair_iterator_bool
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::insert (const _Val& v)
{
__link_type y = __header;
__link_type x = __root();
bool _RWSTD_COMP = true;
while (!__isNil(x))
{
y = x;
_RWSTD_COMP = __key_compare(_KeyOf()(v), __key(x));
x = _RWSTD_COMP ? __left(x) : __right(x);
}
if (__insert_always)
{
pair_iterator_bool tmp(__insert(x, y, v), true); return tmp;
}
iterator j = iterator(y);
if (_RWSTD_COMP)
{
if (j == begin())
{
pair_iterator_bool tmp(__insert(x, y, v), true); return tmp;
}
else
--j;
}
if (__key_compare(__key(j.node), _KeyOf()(v)))
{
pair_iterator_bool tmp(__insert(x, y, v), true); return tmp;
}
pair_iterator_bool tmp(j, false);
return tmp;
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::insert (iterator position,
const _Val& v)
{
if (position == iterator(begin()))
{
if (size() > 0 && __key_compare(_KeyOf()(v), __key(position.node)))
return __insert(position.node, position.node, v);
//
// First argument just needs to be non-NIL.
//
else
return insert(v).first;
}
else if (position == iterator(end()))
{
if (__key_compare(__key(__rightmost()), _KeyOf()(v)))
return __insert(__nil(), __rightmost(), v);
else
return insert(v).first;
}
else
{
iterator before = --position;
if (__key_compare(__key(before.node), _KeyOf()(v))
&& __key_compare(_KeyOf()(v), __key(position.node)))
{
if (__isNil(__right(before.node)))
return __insert(__nil(), before.node, v);
else
return __insert(position.node, position.node, v);
//
// First argument just needs to be non-NIL.
//
}
else
return insert(v).first;
}
}
#ifndef _RWSTD_NO_MEMBER_TEMPLATES
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
template<class Iterator>
void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::insert (Iterator first,
Iterator last)
{
while (first != last) insert(*first++);
}
#else
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::insert (const_iterator first,
const_iterator last)
{
while (first != last) insert(*first++);
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::insert (const _Val* first,
const _Val* last)
{
while (first != last) insert(*first++);
}
#endif
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::erase (iterator position)
{
iterator tmp = position; // Retain 'next' position for return
if (tmp != end())
tmp++;
__link_type z;
_RW_STD::__initialize(z, __link_type(position.node));
__link_type y = z;
__link_type x;
bool __deleted = false;
if (__isNil(__left(y)))
{
if (__isNil(__right(y)))
{
x = __parent(y);
__erase_leaf(y);
__deleted = true;
}
else
x = __right(y);
}
else
{
if (__isNil(__right(y)))
x = __left(y);
else
{
y = __right(y);
while (!__isNil(__left(y))) y = __left(y);
x = __right(y);
}
}
if (!__deleted && y != z)
{
//
// Relink y in place of z.
//
__parent(__left(z)) = y;
__left(y) = __left(z);
if (y != __right(z))
{
if (!__isNil(x))
__parent(x) = __parent(y);
__left(__parent(y)) = x; // Y must be a left child.
__right(y) = __right(z);
__parent(__right(z)) = y;
}
else if (!__isNil(x))
__parent(x) = y;
if (__root() == z)
__root() = y;
else if (__left(__parent(z)) == z)
__left(__parent(z)) = y;
else
__right(__parent(z)) = y;
__parent(y) = __parent(z);
if (__isNil(x))
x = y; // Don't want to start balancing with nil
#ifndef _RWSTD_NO_NAMESPACE
std::swap(__color(y), __color(z));
#else
::swap(__color(y), __color(z));
#endif
y = z; // y points to node to be actually deleted.
}
else if (!__deleted)
{
//
// y == z
//
__parent(x) = __parent(y);
if (__root() == z)
__root() = x;
else
{
if (__left(__parent(z)) == z)
__left(__parent(z)) = x;
else
__right(__parent(z)) = x;
}
if (__leftmost() == z)
{
if (__isNil(__right(z))) // __left(z) must be NIL also.
__leftmost() = __parent(z);
else
__leftmost() = __minimum(x);
}
if (__rightmost() == z)
{
if (__isNil(__left(z))) // __right(z) must be NIL also.
__rightmost() = __parent(z);
else
__rightmost() = __maximum(x);
}
}
if (x != __header && __color(y) != __rb_red)
{
while (x != __root() && __color(x) == __rb_black)
{
if (x == __left(__parent(x)))
{
__link_type w = __right(__parent(x));
if (__isNil(w))
{
__color(x) = __rb_red;
x = __parent(x);
}
else
{
if (__color(w) == __rb_red)
{
__color(w) = __rb_black;
__color(__parent(x)) = __rb_red;
__rotate_left(__parent(x));
w = __right(__parent(x));
}
if (__isNil(w))
{
__color(x) = __rb_red;
x = __parent(x);
}
else if ((__isNil(__left(w)) || __color(__left(w)) == __rb_black) &&
(__isNil(__right(w)) || __color(__right(w)) == __rb_black))
{
__color(w) = __rb_red;
x = __parent(x);
}
else
{
if (__isNil(__right(w)) || __color(__right(w)) == __rb_black)
{
if (!__isNil(__left(w)))
__color(__left(w)) = __rb_black;
__color(w) = __rb_red;
__rotate_right(w);
w = __right(__parent(x));
}
if (!__isNil(w))
{
__color(w) = __color(__parent(x));
__color(__parent(x)) = __rb_black;
if (!__isNil(__right(w)))
__color(__right(w)) = __rb_black;
__rotate_left(__parent(x));
}
break;
}
}
}
else
{
//
// Same as then clause with "right" and "left" exchanged.
//
__link_type w = __left(__parent(x));
if (__isNil(w))
{
__color(x) = __rb_red;
x = __parent(x);
}
else
{
if (__color(w) == __rb_red)
{
__color(w) = __rb_black;
__color(__parent(x)) = __rb_red;
__rotate_right(__parent(x));
w = __left(__parent(x));
}
if (__isNil(w))
{
__color(x) = __rb_red;
x = __parent(x);
}
else if ((__isNil(__right(w)) || __color(__right(w)) == __rb_black) &&
(__isNil(__left(w)) || __color(__left(w)) == __rb_black))
{
__color(w) = __rb_red; x = __parent(x);
}
else
{
if (__isNil(__left(w)) || __color(__left(w)) == __rb_black)
{
if (!__isNil(__right(w)))
__color(__right(w)) = __rb_black;
__color(w) = __rb_red;
__rotate_left(w);
w = __left(__parent(x));
}
if (!__isNil(w))
{
__color(w) = __color(__parent(x));
__color(__parent(x)) = __rb_black;
if (!__isNil(__left(w)))
__color(__left(w)) = __rb_black;
__rotate_right(__parent(x));
}
break;
}
}
}
}
__color(x) = __rb_black;
}
__put_node(y);
--__node_count;
return tmp;
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::size_type
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::erase (const _Key& x)
{
pair_iterator_iterator p = equal_range(x);
size_type n;
_RW_STD::__initialize(n, size_type(0));
_RW_STD::distance(p.first, p.second, n);
erase(p.first, p.second);
return n;
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__link_type
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__copy (__link_type x, __link_type p)
{
//
// Structural copy.
//
__link_type r = x;
while (!__isNil(x))
{
__link_type y = __get_node(__value(x));
if (r == x) r = y; // Save for return value.
__left(p) = y;
__parent(y) = p;
__color(y) = __color(x);
__right(y) = __copy(__right(x), y);
p = y;
x = __left(x);
}
__left(p) = __nil();
return r;
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::__erase (__link_type x)
{
//
// Erase without rebalancing.
//
while (!__isNil(x))
{
__erase(__right(x));
__link_type y = __left(x);
__put_node(x);
x = y;
}
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::erase (iterator first,
iterator locallast)
{
iterator tmp = end();
if (first == begin() && locallast == end() && __node_count != 0)
{
__erase(__root());
__leftmost() = __header;
__root() = __nil();
__rightmost() = __header;
__node_count = 0;
tmp = end();
} else
{
while (first != locallast)
tmp = erase(first++);
}
return tmp;
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::erase (const _Key* first,
const _Key* last)
{
while (first != last) erase(*first++);
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::find (const _Key& k) const
{
__link_type y = __header; // Last node that is not less than k.
__link_type x = __root(); // Current node.
while (!__isNil(x))
{
if (!__key_compare(__key(x), k))
y = x, x = __left(x);
else
x = __right(x);
}
iterator j = iterator(y);
return (j == end() || __key_compare(k, __key(j.node))) ? end() : j;
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::size_type
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::count (const _Key& k) const
{
_RW_STD::pair<iterator, iterator> p = equal_range(k);
size_type n;
_RW_STD::__initialize(n, size_type(0));
_RW_STD::distance(p.first, p.second, n);
return n;
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::lower_bound (const _Key& k) const
{
__link_type y = __header; // Last node that is not less than k.
__link_type x = __root(); // Current node.
while (!__isNil(x))
{
if (!__key_compare(__key(x), k))
y = x, x = __left(x);
else
x = __right(x);
}
return iterator(y);
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::upper_bound (const _Key& k) const
{
__link_type y = __header; // Last node that is greater than k.
__link_type x = __root(); // Current node.
while (!__isNil(x))
{
if (__key_compare(k, __key(x)))
y = x, x = __left(x);
else
x = __right(x);
}
return iterator(y);
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::pair_iterator_iterator
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::equal_range (const _Key& k) const
{
pair_iterator_iterator tmp(lower_bound(k), upper_bound(k));
return tmp;
}
#ifndef _RWSTD_NO_NAMESPACE
}
#endif
#pragma option pop
#endif /* __TREE_CC */