vcl_tree.h

来自「DTMK软件开发包,此为开源软件,是一款很好的医学图像开发资源.」· C头文件 代码 · 共 1,136 行 · 第 1/3 页

    else {                      // z has two non-null children.  Set y to
      y = y->right;             //   z's successor.  x might be null.
      while (y->left != 0)
        y = y->left;
      x = y->right;
    }
  if (y != z) {                 // relink y in place of z.  y is z's successor
    z->left->parent = y;
    y->left = z->left;
    if (y != z->right) {
      x_parent = y->parent;
      if (x) x->parent = y->parent;
      y->parent->left = x;      // y must be a left child
      y->right = z->right;
      z->right->parent = y;
    }
    else
      x_parent = y;
    if (root == z)
      root = y;
    else if (z->parent->left == z)
      z->parent->left = y;
    else
      z->parent->right = y;
    y->parent = z->parent;
    vcl_swap(y->color, z->color);
    y = z;
    // y now points to node to be actually deleted
  }
  else {                        // y == z
    x_parent = y->parent;
    if (x) x->parent = y->parent;
    if (root == z)
      root = x;
    else
      if (z->parent->left == z)
        z->parent->left = x;
      else
        z->parent->right = x;
    if (leftmost == z)
      if (z->right == 0)        // z->left must be null also
        leftmost = z->parent;
    // makes leftmost == header if z == root
      else
        leftmost = __rb_tree_node_base::minimum(x);
    if (rightmost == z)
      if (z->left == 0)         // z->right must be null also
        rightmost = z->parent;
    // makes rightmost == header if z == root
      else                      // x == z->left
        rightmost = __rb_tree_node_base::maximum(x);
  }
  if (y->color != __rb_tree_red) {
    while (x != root && (x == 0 || x->color == __rb_tree_black))
      if (x == x_parent->left) {
        __rb_tree_node_base* w = x_parent->right;
        if (w->color == __rb_tree_red) {
          w->color = __rb_tree_black;
          x_parent->color = __rb_tree_red;
          __rb_tree_rotate_left(x_parent, root);
          w = x_parent->right;
        }
        if ((w->left == 0 || w->left->color == __rb_tree_black) &&
            (w->right == 0 || w->right->color == __rb_tree_black)) {
          w->color = __rb_tree_red;
          x = x_parent;
          x_parent = x_parent->parent;
        } else {
          if (w->right == 0 || w->right->color == __rb_tree_black) {
            if (w->left) w->left->color = __rb_tree_black;
            w->color = __rb_tree_red;
            __rb_tree_rotate_right(w, root);
            w = x_parent->right;
          }
          w->color = x_parent->color;
          x_parent->color = __rb_tree_black;
          if (w->right) w->right->color = __rb_tree_black;
          __rb_tree_rotate_left(x_parent, root);
          break;
        }
      } else {                  // same as above, with right <-> left.
        __rb_tree_node_base* w = x_parent->left;
        if (w->color == __rb_tree_red) {
          w->color = __rb_tree_black;
          x_parent->color = __rb_tree_red;
          __rb_tree_rotate_right(x_parent, root);
          w = x_parent->left;
        }
        if ((w->right == 0 || w->right->color == __rb_tree_black) &&
            (w->left == 0 || w->left->color == __rb_tree_black)) {
          w->color = __rb_tree_red;
          x = x_parent;
          x_parent = x_parent->parent;
        } else {
          if (w->left == 0 || w->left->color == __rb_tree_black) {
            if (w->right) w->right->color = __rb_tree_black;
            w->color = __rb_tree_red;
            __rb_tree_rotate_left(w, root);
            w = x_parent->left;
          }
          w->color = x_parent->color;
          x_parent->color = __rb_tree_black;
          if (w->left) w->left->color = __rb_tree_black;
          __rb_tree_rotate_right(x_parent, root);
          break;
        }
      }
    if (x) x->color = __rb_tree_black;
  }
  return y;
}

template <class Value, class Alloc>
class __rb_tree_base
{
    typedef __rb_tree_base<Value,Alloc> self;
 public:
    typedef Value value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef vcl_size_t size_type;
    typedef vcl_ptrdiff_t difference_type;
 protected:
    typedef __rb_tree_node_base* base_ptr;
    typedef __rb_tree_node<Value> rb_tree_node;
    typedef __rb_tree_color_type color_type;
    typedef rb_tree_node* link_type;
    typedef vcl_simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;
    static link_type get_node() { return rb_tree_node_allocator::allocate(); }
    static void put_node(link_type p) { rb_tree_node_allocator::deallocate(p); }
 protected:
    link_type header;

    link_type& root() const { return (link_type&) header->parent; }
    link_type& leftmost() const { return (link_type&) header->left; }
    link_type& rightmost() const { return (link_type&) header->right; }
    size_type node_count; // keeps track of size of vcl_tree

    static link_type& left(link_type x) { return (link_type&)(x->left); }
    static link_type& right(link_type x) { return (link_type&)(x->right); }
    static link_type& parent(link_type x) { return (link_type&)(x->parent); }
    static reference value(link_type x) { return x->value_field; }
    static color_type& color(link_type x) { return (color_type&)(x->color); }

    static link_type& left(base_ptr x) { return (link_type&)(x->left); }
    static link_type& right(base_ptr x) { return (link_type&)(x->right); }
    static link_type& parent(base_ptr x) { return (link_type&)(x->parent); }
    static reference value(base_ptr x) { return ((link_type)x)->value_field; }
    static color_type& color(base_ptr x) { return (color_type&)(link_type(x)->color); }

    static link_type minimum(link_type x) {
        return (link_type)  __rb_tree_node_base::minimum(x);
    }
    static link_type maximum(link_type x) {
        return (link_type) __rb_tree_node_base::maximum(x);
    }

 public:
    __rb_tree_base() : header( get_node() ), node_count(0) {
        color(header) = __rb_tree_red; // used to distinguish header from
        // root, in iterator.operator++
        __stl_debug_do(iter_list.safe_init(header));
    }
    ~__rb_tree_base() {
        put_node(header);
        __stl_debug_do(iter_list.invalidate());
    }

 public:
    bool empty() const { return node_count == 0; }
    size_type size() const { return node_count; }
    size_type max_size() const { return size_type(-1); }

 protected:
    static link_type __new_node(const value_type& v) {
        link_type z = get_node();
        IUEg__TRY {
        vcl_construct(&(value(z)), v);
        left(z) = 0;
        right(z) = 0;
        }
#  if defined (__STL_USE_EXCEPTIONS)
        catch(...) {
            put_node(z);
            throw;
        }
#  endif
        return z;
    }
    static inline link_type __copy_aux(link_type x, link_type p);
    static inline void __erase(link_type x);
    static inline link_type __copy(link_type x, link_type p);

 public:
    void clear() {
      if (node_count != 0) {
        __erase(root());
        leftmost() = header;
        root() = 0;
        rightmost() = header;
        node_count = 0;
        __stl_debug_do(invalidate_all());
      }
    }
};

template <class Key, class Value, class KeyOfValue, class Compare, VCL_DFL_TYPE_PARAM_STLDECL(Alloc,vcl_alloc) >
class rb_tree : public __rb_tree_base<Value,Alloc>
{
  typedef __rb_tree_base<Value,Alloc> super;
  typedef rb_tree<Key,Value,KeyOfValue,Compare,Alloc> self;
 public:
  __IMPORT_CONTAINER_TYPEDEFS(super)
  typedef __rb_tree_node_base* base_ptr;
  typedef __rb_tree_node<Value> rb_tree_node;
  typedef __rb_tree_color_type color_type;
  typedef rb_tree_node* link_type;
  typedef __rb_tree_iterator<value_type> iterator;
  typedef __rb_tree_const_iterator<value_type> const_iterator;
  typedef vcl_reverse_bidirectional_iterator<iterator, value_type, reference,
                                             difference_type> reverse_iterator;
  typedef vcl_reverse_bidirectional_iterator<const_iterator, value_type,
                                             const_reference, difference_type>
      const_reverse_iterator;
  typedef Key key_type;
 protected:
  Compare key_compare;
  static const Key& key(link_type x) { return KeyOfValue()(value(x)); }
  static const Key& key(base_ptr x) { return KeyOfValue()(value(link_type(x)));}
 private:
  inline iterator __insert(base_ptr x, base_ptr y, const value_type& v);
  void init() {
      root() = 0;
      leftmost() = header;
      rightmost() = header;
  }
 public:
  // allocation/deallocation
  rb_tree(): key_compare(Compare())  { init(); }
  rb_tree(const Compare& comp): key_compare(comp)  { init(); }
  rb_tree(const self& x)
    : key_compare(x.key_compare)  {
      root() = __copy(x.root(), header);
      if (root() == 0) {
          leftmost() = header;
          rightmost() = header;
      } else {
          leftmost() = minimum(root());
          rightmost() = maximum(root());
      }
      node_count = x.node_count;
  }

  ~rb_tree() { clear();}
  inline self& operator=(const self& x);

 public:
  // accessors:
  iterator make_iterator(link_type l) { return iterator(l); }
  const_iterator make_const_iterator(link_type l) const { return const_iterator(l); }
  iterator begin() { return leftmost(); }
  const_iterator begin() const { return leftmost(); }
  iterator end() { return header; }
  const_iterator end() const { return header; }
  reverse_iterator rbegin() { return reverse_iterator(end()); }
  const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
  reverse_iterator rend() { return reverse_iterator(begin()); }
  const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
  Compare key_comp() const { return key_compare; }

  void swap(self& t) {
      __stl_debug_do(iter_list.swap_owners(t.iter_list));
      vcl_swap(header, t.header);
      vcl_swap(node_count, t.node_count);
      vcl_swap(key_compare, t.key_compare);
  }

 public:
  // insert/erase
  vcl_pair<iterator,bool> insert_unique(const value_type& v){
    link_type y = header;
    link_type x = root();
    bool comp = true;
    while (x != 0) {
        y = x;
        comp = key_compare(KeyOfValue()(v), key(x));
        x = comp ? left(x) : right(x);
    }
    iterator j = make_iterator(y);
    if (comp)
        if (j == begin())
            return vcl_pair<iterator,bool>(__insert(x, y, v), true);
        else
            --j;
    if (key_compare(key(j.node), KeyOfValue()(v)))
        return vcl_pair<iterator,bool>(__insert(x, y, v), true);
    return vcl_pair<iterator,bool>(j, false);
  }

  iterator insert_equal(const value_type& v){
    link_type y = header;
    link_type x = root();
    while (x != 0) {
        y = x;
        x = key_compare(KeyOfValue()(v), key(x)) ? left(x) : right(x);
    }
    return __insert(x, y, v);
  }

  iterator insert_unique(iterator position, const value_type& v){
    __stl_debug_check(__check_if_owner(header,position));
    if (position.node == header->left) // begin()
        if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node)))
            return __insert(position.node, position.node, v);
            // first argument just needs to be non-null
        else
            return insert_unique(v).first;
    else if (position.node == header) // end()
        if (key_compare(key(rightmost()), KeyOfValue()(v)))
            return __insert(0, rightmost(), v);
        else
            return insert_unique(v).first;
    else {
        iterator before = position;
        --before;
        if (key_compare(key(before.node), KeyOfValue()(v))
            && key_compare(KeyOfValue()(v), key(position.node)))
            if (right(before.node) == 0)
                return __insert(0, before.node, v);
            else
                return __insert(position.node, position.node, v);
                // first argument just needs to be non-null
        else
            return insert_unique(v).first;
    }
  }

  iterator insert_equal(iterator position, const value_type& v){
    __stl_debug_check(__check_if_owner(header,position));
    if (position.node == header->left) // begin()
        if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node)))
            return __insert(position.node, position.node, v);
            // first argument just needs to be non-null
        else
            return insert_equal(v);
    else if (position.node == header) // end()
        if (!key_compare(KeyOfValue()(v), key(rightmost())))
            return __insert(0, rightmost(), v);
        else
            return insert_equal(v);
    else {
        iterator before = position;
        --before;
        if (!key_compare(KeyOfValue()(v), key(before.node))
            && !key_compare(key(position.node), KeyOfValue()(v)))
            if (right(before.node) == 0)
                return __insert(0, before.node, v);
            else
                return __insert(position.node, position.node, v);
                // first argument just needs to be non-null
        else
            return insert_equal(v);
    }
  }

  void insert_unique(const_iterator    first, const_iterator    last){while (first != last) insert_unique(*first++);}
  void insert_unique(const value_type* first, const value_type* last){while (first != last) insert_unique(*first++);}
  void insert_equal(const_iterator first, const_iterator last) {
    while (first != last) insert_equal(*first++);
  }

  void insert_equal(const value_type* first, const value_type* last) {
    while (first != last) insert_equal(*first++);
  }

  inline void erase(iterator position);
  inline void erase(iterator first, iterator last);