vcl_tree.h

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

  inline size_type erase(const key_type& x);
  inline void erase(const key_type* first, const key_type* last);

 public:
                                // vcl_set operations:
  inline iterator find(const key_type& x);
  inline const_iterator find(const key_type& x) const;
  inline size_type count(const key_type& x) const;
  inline iterator lower_bound(const key_type& x);
  inline const_iterator lower_bound(const key_type& x) const;
  inline iterator upper_bound(const key_type& x);
  inline const_iterator upper_bound(const key_type& x) const;
  inline vcl_pair<iterator,iterator> equal_range(const key_type& x);
  inline vcl_pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
 public:
                                // Debugging.
  inline bool __rb_verify() const;
};

// fbp: these defines are for outline methods definitions.
// needed for definitions to be portable. Should not be used in method bodies.
# if defined  ( __STL_NESTED_TYPE_PARAM_BUG )
#  define __iterator__        __rb_tree_iterator<Value>
#  define __const_iterator__  __rb_tree_const_iterator<Value>
#  define __size_type__       vcl_size_t
#  define __link_type__       __rb_tree_node<Value>*
#  define __base_ptr__        __rb_tree_node_base*
#  define __value_type__      Value
#  define __key_type__        Key
# else
#  define __iterator__        rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
#  define __const_iterator__  rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::const_iterator
#  define __link_type__       rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::link_type
#  define __size_type__       rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::size_type
#  define __base_ptr__        rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::base_ptr
#  define __value_type__      rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::value_type
#  define __key_type__        rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::key_type
# endif

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
inline bool operator==(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x,
                       const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& y) {
    return x.size() == y.size() && vcl_equal(x.begin(), x.end(), y.begin());
}

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
inline bool operator<(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x,
                      const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& y) {
    return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>&
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::operator=
(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x) {
    if (this != &x) {
        // can't be done as in vcl_list because Key may be a constant type
        clear();
        root() = __copy(x.root(), header);
        if (root() == 0) {
            leftmost() = header;
            rightmost() = header;
        } else {
            leftmost() = minimum(root());
            rightmost() = maximum(root());
        }
        node_count = x.node_count;
        key_compare = x.key_compare;
    }
    return *this;
}


template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
typename __iterator__
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__insert(__base_ptr__ x_,
                                                          __base_ptr__ y_,
                                                          const __value_type__& v) {
    link_type x = (link_type) x_;
    link_type y = (link_type) y_;
    // determine link before allocating new node
    bool link_to_left = y == header || x != 0 || key_compare(KeyOfValue()(v), key(y));
    link_type z = __new_node(v);
    if (link_to_left) {
        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;
    left(z) = 0;
    right(z) = 0;
    __rb_tree_rebalance(z, header->parent);
    ++node_count;
    return make_iterator(z);
}


template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
inline void
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(__iterator__
                                                       position) {
    __stl_debug_check(__check_if_owner(header,position));
    __stl_verbose_assert(position.node!=header, __STL_MSG_ERASE_PAST_THE_END);
    __stl_debug_do(invalidate_iterator(position));
  link_type y = (link_type) __rb_tree_rebalance_for_erase(position.node,
                                                          header->parent,
                                                          header->left,
                                                          header->right);
  vcl_destroy(&(value(y)));
  put_node(y);
  --node_count;
}

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
typename __size_type__
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(const __key_type__& x) {
    vcl_pair<iterator,iterator> p = equal_range(x);
    size_type n = 0;
    vcl_distance(p.first, p.second, n);
    erase(p.first, p.second);
    return n;
}

template <class Value, class Alloc>
inline __rb_tree_node<Value>*
__rb_tree_base<Value, Alloc>::__copy(__rb_tree_node<Value>* x, __rb_tree_node<Value>* p) {
    link_type l;
#  if defined (__STL_USE_EXCEPTIONS)
    l = left(p);
#  endif
    IUEg__TRY {
    l = __copy_aux(x, p);
    }
#  if defined (__STL_USE_EXCEPTIONS)
    catch(...) {
        if (left(p) != l) {
            __erase(left(p));
            left(p) = l;
        }
        throw;
    }
#  endif
    return l;
}

template <class Value, class Alloc>
inline
__rb_tree_node<Value>*
__rb_tree_base<Value, Alloc>::__copy_aux(__rb_tree_node<Value>* x,
                                         __rb_tree_node<Value>* p) {
   // structural copy
   link_type r = x;
   while (x != 0) {
      link_type y = __new_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_aux(right(x), y);
      left(y) = 0;
      p = y;
      x = left(x);
   }
   left(p) = 0;
   return r;
}


template <class Value, class Alloc>
inline
void __rb_tree_base<Value, Alloc>::__erase(__rb_tree_node<Value>* x) {
    // erase without rebalancing
    while (x != 0) {
       __erase(right(x));
       link_type y = left(x);
       vcl_destroy(&(value(x)));
       put_node(x);
       x = y;
    }
}

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
void
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(__iterator__ first,
                                                       __iterator__ last) {
    if (first == begin() && last == end())
        clear();
    else
         while (first != last) erase(first++);
}

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(const Key* first,
                                                            const Key* last) {
    while (first != last) erase(*first++);
}

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
typename __iterator__
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::find(const __key_type__& k) {
   link_type y = header; /* Last node which is not vcl_less than k. */
   link_type x = root(); /* Current node. */

   while (x != 0)
     if (!key_compare(key(x), k))
       y = x, x = left(x);
   else
       x = right(x);

   return make_iterator((y == header || key_compare(k, key(y))) ? header : y);
}

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
typename __const_iterator__
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::find(const __key_type__& k) const {
   link_type y = header; /* Last node which is not vcl_less than k. */
   link_type x = root(); /* Current node. */

   while (x != 0) {
     if (!key_compare(key(x), k))
       y = x, x = left(x);
   else
       x = right(x);
   }
   return make_const_iterator((y == header || key_compare(k, key(y))) ? header : y);
}

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
typename __size_type__
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::count(const __key_type__& k) const {
    vcl_pair<const_iterator, const_iterator> p = equal_range(k);
    size_type n = 0;
    vcl_distance(p.first, p.second, n);
    return n;
}

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
typename __iterator__
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::lower_bound(const __key_type__& k) {
   link_type y = header; /* Last node which is not vcl_less than k. */
   link_type x = root(); /* Current node. */

   while (x != 0)
     if (!key_compare(key(x), k))
       y = x, x = left(x);
     else
       x = right(x);

   return make_iterator(y);
}

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
typename __const_iterator__
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::lower_bound(const __key_type__& k) const {
   link_type y = header; /* Last node which is not vcl_less than k. */
   link_type x = root(); /* Current node. */

   while (x != 0)
     if (!key_compare(key(x), k))
       y = x, x = left(x);
     else
       x = right(x);

   return make_const_iterator(y);
}

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
typename __iterator__
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::upper_bound(const __key_type__& k) {
  link_type y = header; /* Last node which is vcl_greater than k. */
  link_type x = root(); /* Current node. */

   while (x != 0)
     if (key_compare(k, key(x)))
       y = x, x = left(x);
     else
       x = right(x);

   return make_iterator(y);
}

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
typename __const_iterator__
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::upper_bound(const __key_type__& k) const {
  link_type y = header; /* Last node which is vcl_greater than k. */
  link_type x = root(); /* Current node. */

   while (x != 0)
     if (key_compare(k, key(x)))
       y = x, x = left(x);
     else
       x = right(x);

   return make_const_iterator(y);
}

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
inline vcl_pair<typename __iterator__,typename __iterator__>
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::equal_range(const __key_type__& k) {
    return vcl_pair<iterator, iterator>(lower_bound(k), upper_bound(k));
}

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
inline vcl_pair<typename __const_iterator__,typename __const_iterator__>
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::equal_range(const __key_type__& k) const {
    return vcl_pair<const_iterator,const_iterator>(lower_bound(k), upper_bound(k));
}

// awf patched
#ifdef __PUT_STATIC_DATA_MEMBERS_HERE
int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root)
{
  if (node == 0)
    return 0;
  else {
    int bc = node->color == __rb_tree_black ? 1 : 0;
    if (node == root)
      return bc;
    else
      return bc + __black_count(node->parent, root);
  }
}
#else
extern int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root);
#endif

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
bool
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__rb_verify() const
{
  int len = __black_count(leftmost(), root());
  for (const_iterator it = begin(); it != end(); ++it) {
    link_type x = (link_type) it.node;
    link_type L = left(x);
    link_type R = right(x);

    if (x->color == __rb_tree_red)
      if ((L && L->color == __rb_tree_red) ||
          (R && R->color == __rb_tree_red))
        return false;

    if (L && key_compare(key(x), key(L)))
      return false;
    if (R && key_compare(key(R), key(x)))
      return false;

    if (!L && !R && __black_count(x, root()) != len)
      return false;
  }

  if ( !empty() )
  {
          if (leftmost() != __rb_tree_node_base::minimum(root()))
                return false;
          if (rightmost() != __rb_tree_node_base::maximum(root()))
                return false;
  }

  return true;
}

# undef __iterator__
# undef __const_iterator__
# undef __size_type__
# undef __link_type__
# undef __base_ptr__
# undef __value_type__
# undef __key_type__

#endif // vcl_emulation_tree_h