--- /dev/null
+/////////////////////////////////////////////////////////////////////////////\r
+//\r
+// (C) Copyright Ion Gaztañaga 2006-2007\r
+//\r
+// Distributed under the Boost Software License, Version 1.0.\r
+// (See accompanying file LICENSE_1_0.txt or copy at\r
+// http://www.boost.org/LICENSE_1_0.txt)\r
+//\r
+// See http://www.boost.org/libs/intrusive for documentation.\r
+//\r
+/////////////////////////////////////////////////////////////////////////////\r
+#ifndef BOOST_INTRUSIVE_IRBTREE_HPP\r
+#define BOOST_INTRUSIVE_IRBTREE_HPP\r
+\r
+#include "config_begin.hpp"\r
+#include <functional>\r
+#include <iterator>\r
+#include <boost/utility.hpp>\r
+#include <boost/compressed_pair.hpp>\r
+#include <utility>\r
+#include <boost/assert.hpp>\r
+#include <boost/static_assert.hpp>\r
+#include "pointer_type.hpp"\r
+#include "pointer_to_other.hpp"\r
+#include "../iset_hook.hpp"\r
+#include "rbtree_node.hpp"\r
+#include "ebo_holder.hpp"\r
+#include "../rbtree_algorithms.hpp"\r
+#include "../linking_policy.hpp"\r
+#include <cstddef>\r
+#include <iterator>\r
+\r
+namespace boost {\r
+namespace intrusive {\r
+namespace detail {\r
+\r
+//! The class template irbtree is an intrusive red-black tree container, that\r
+//! is used to construct intrusive set and tree containers. The no-throw \r
+//! guarantee holds only, if the Compare object \r
+//! doesn't throw.\r
+template < class ValueTraits\r
+ , class Compare = std::less<typename ValueTraits::value_type>\r
+ , bool ConstantTimeSize = true\r
+ , class SizeType = std::size_t\r
+ >\r
+class irbtree\r
+ : private detail::size_holder<ConstantTimeSize, SizeType>\r
+{\r
+ private:\r
+ typedef irbtree<ValueTraits, Compare\r
+ ,ConstantTimeSize, SizeType> this_type; \r
+ typedef typename ValueTraits::node_traits node_traits;\r
+ typedef detail::size_holder<ConstantTimeSize, SizeType> size_traits;\r
+\r
+ //noncopyable\r
+ irbtree (const irbtree&);\r
+ irbtree operator =(const irbtree&);\r
+\r
+ public:\r
+ typedef typename ValueTraits::value_type value_type;\r
+ typedef typename ValueTraits::pointer pointer;\r
+ typedef typename ValueTraits::const_pointer const_pointer;\r
+ typedef value_type& reference;\r
+ typedef const value_type& const_reference;\r
+ typedef SizeType size_type;\r
+ typedef typename std::iterator_traits\r
+ <pointer>::difference_type difference_type;\r
+ typedef value_type key_type;\r
+ typedef Compare value_compare;\r
+ class iterator;\r
+ class const_iterator;\r
+ friend class iterator;\r
+ friend class const_iterator;\r
+\r
+ private:\r
+ typedef typename node_traits::node node;\r
+ typedef typename boost::pointer_to_other\r
+ <pointer, node>::type node_ptr;\r
+ typedef typename boost::pointer_to_other\r
+ <node_ptr, const node>::type const_node_ptr;\r
+ typedef rbtree_algorithms<node_traits> node_algorithms;\r
+ enum { safemode_or_autounlink = \r
+ (int)ValueTraits::linking_policy == (int)auto_unlink ||\r
+ (int)ValueTraits::linking_policy == (int)safe_mode_link };\r
+\r
+ //Constant-time size is incompatible with auto-unlink hooks!\r
+ BOOST_STATIC_ASSERT(!(ConstantTimeSize && ((int)ValueTraits::linking_policy == (int)auto_unlink)));\r
+\r
+ template<class KeyValueCompare>\r
+ struct key_node_ptr_compare\r
+ : private ebo_holder<KeyValueCompare>\r
+ {\r
+ typedef ebo_holder<KeyValueCompare> base_t;\r
+ key_node_ptr_compare(KeyValueCompare kcomp)\r
+ : base_t(kcomp)\r
+ {}\r
+\r
+ template<class KeyType>\r
+ bool operator()(node_ptr node, const KeyType &key) const\r
+ { return base_t::get()(*ValueTraits::to_value_ptr(node), key); }\r
+\r
+ template<class KeyType>\r
+ bool operator()(const KeyType &key, node_ptr node) const\r
+ { return base_t::get()(key, *ValueTraits::to_value_ptr(node)); }\r
+\r
+ bool operator()(node_ptr node1, node_ptr node2) const\r
+ {\r
+ return base_t::get()\r
+ (*ValueTraits::to_value_ptr(node1), *ValueTraits::to_value_ptr(node2)); \r
+ }\r
+ };\r
+\r
+ //Use boost::compressed_pair to get EBO if possible\r
+ boost::compressed_pair<node, Compare> members_;\r
+ \r
+ const Compare &priv_comp() const\r
+ { return members_.second(); }\r
+\r
+ Compare &priv_comp()\r
+ { return members_.second(); }\r
+\r
+ const node &priv_header() const\r
+ { return members_.first(); }\r
+\r
+ node &priv_header()\r
+ { return members_.first(); }\r
+\r
+ template<class F>\r
+ struct value_to_node_cloner\r
+ : private ebo_holder<F>\r
+ {\r
+ typedef ebo_holder<F> base_t;\r
+ value_to_node_cloner(F f)\r
+ : base_t(f)\r
+ {}\r
+ \r
+ node_ptr operator()(node_ptr p)\r
+ { return ValueTraits::to_node_ptr(*base_t::get()(*ValueTraits::to_value_ptr(p))); }\r
+ };\r
+\r
+ template<class F>\r
+ struct value_to_node_destroyer\r
+ : private ebo_holder<F>\r
+ {\r
+ typedef ebo_holder<F> base_t;\r
+ value_to_node_destroyer(F f)\r
+ : base_t(f)\r
+ {}\r
+\r
+ void operator()(node_ptr p)\r
+ { base_t::get()(ValueTraits::to_value_ptr(p)); }\r
+ };\r
+\r
+ static node_ptr uncast(const_node_ptr ptr)\r
+ {\r
+ using boost::get_pointer;\r
+ return node_ptr(const_cast<node*>(get_pointer(ptr)));\r
+ }\r
+\r
+ public:\r
+ typedef typename node_algorithms::insert_commit_data insert_commit_data;\r
+\r
+ class iterator\r
+ : public detail::rbtree_iterator <value_type, iterator, node_traits>\r
+ {\r
+ private:\r
+ typedef typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::value_type private_vt;\r
+ typedef typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::pointer private_pointer;\r
+ typedef typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::reference private_reference;\r
+ typedef detail::rbtree_iterator<private_vt, iterator, node_traits> inherited;\r
+\r
+ public:\r
+ iterator ()\r
+ {}\r
+\r
+ private_pointer operator->() const\r
+ { return ValueTraits::to_value_ptr(this->tree_node()); }\r
+\r
+ private_reference operator*() const\r
+ { return *ValueTraits::to_value_ptr(this->tree_node()); }\r
+\r
+ private:\r
+ explicit iterator(node_ptr node)\r
+ : inherited(node)\r
+ {}\r
+ \r
+ friend class irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>; \r
+ friend class detail::rbtree_iterator<private_vt, iterator, node_traits>;\r
+ friend class const_iterator;\r
+ };\r
+\r
+ class const_iterator\r
+ : public detail::rbtree_iterator<const value_type, const_iterator, node_traits>\r
+ {\r
+ private:\r
+ typedef const typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::value_type private_vt;\r
+ typedef typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::const_pointer private_pointer;\r
+ typedef typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::const_reference private_reference;\r
+ typedef detail::rbtree_iterator<private_vt, const_iterator, node_traits> inherited;\r
+\r
+ public:\r
+ const_iterator ()\r
+ {}\r
+\r
+ const_iterator(const typename irbtree::iterator& it)\r
+ : inherited (it.tree_node())\r
+ {}\r
+\r
+ const_iterator & operator=(const typename irbtree::iterator& it)\r
+ { return inherited::operator=(it.tree_node()); }\r
+\r
+ private_pointer operator->()\r
+ { return ValueTraits::to_value_ptr(this->tree_node()); }\r
+\r
+ private_reference operator*()\r
+ { return *ValueTraits::to_value_ptr(this->tree_node()); }\r
+\r
+ private:\r
+ explicit const_iterator (const_node_ptr p)\r
+ : inherited (uncast(p))\r
+ {}\r
+\r
+ friend class irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>; \r
+ friend class detail::rbtree_iterator<private_vt, const_iterator, node_traits>;\r
+ };\r
+\r
+ typedef std::reverse_iterator<iterator> reverse_iterator;\r
+ typedef std::reverse_iterator<const_iterator> const_reverse_iterator;\r
+\r
+ public:\r
+\r
+ //! <b>Effects</b>: Constructs an empty tree. \r
+ //! \r
+ //! <b>Complexity</b>: Constant. \r
+ //! \r
+ //! <b>Throws</b>: Nothing unless the copy constructor of the Compare object throws. \r
+ irbtree(Compare cmp = Compare()) \r
+ : members_(cmp)\r
+ { \r
+ node_algorithms::init_header(&priv_header()); \r
+ size_traits::set_size(size_type(0));\r
+ }\r
+\r
+ //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type. \r
+ //! cmp must be a comparison function that induces a strict weak ordering.\r
+ //! \r
+ //! <b>Effects</b>: Constructs an empty tree and inserts elements from \r
+ //! [b, e).\r
+ //! \r
+ //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using \r
+ //! comp and otherwise N * log N, where N is last first.\r
+ //! \r
+ //! <b>Throws</b>: Nothing unless the copy constructor of the Compare object throws. \r
+ template<class Iterator>\r
+ irbtree(bool unique, Iterator b, Iterator e, Compare cmp = Compare())\r
+ : members_(cmp)\r
+ {\r
+ node_algorithms::init_header(&priv_header());\r
+ size_traits::set_size(size_type(0));\r
+ if(unique)\r
+ this->insert_unique(b, e);\r
+ else\r
+ this->insert_equal(b, e);\r
+ }\r
+\r
+ //! <b>Effects</b>: Detaches all elements from this. The objects in the set \r
+ //! are not deleted (i.e. no destructors are called), but the nodes according to \r
+ //! the ValueTraits template parameter are reinitialized and thus can be reused. \r
+ //! \r
+ //! <b>Complexity</b>: Linear to elements contained in *this. \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ ~irbtree() \r
+ { this->clear(); }\r
+\r
+ //! <b>Effects</b>: Returns an iterator pointing to the beginning of the tree.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ iterator begin()\r
+ { return iterator (node_traits::get_left(node_ptr(&priv_header()))); }\r
+\r
+ //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the tree.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ const_iterator begin() const\r
+ { return const_iterator (node_traits::get_left(const_node_ptr(&priv_header()))); }\r
+\r
+ //! <b>Effects</b>: Returns an iterator pointing to the end of the tree.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ iterator end()\r
+ { return iterator (node_ptr(&priv_header())); }\r
+\r
+ //! <b>Effects</b>: Returns a const_iterator pointing to the end of the tree.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ const_iterator end() const\r
+ { return const_iterator (const_node_ptr(&priv_header())); }\r
+\r
+ //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning of the\r
+ //! reversed tree.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ reverse_iterator rbegin()\r
+ { return reverse_iterator(end()); }\r
+\r
+ //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning\r
+ //! of the reversed tree.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ const_reverse_iterator rbegin() const\r
+ { return const_reverse_iterator(end()); }\r
+\r
+ //! <b>Effects</b>: Returns a reverse_iterator pointing to the end\r
+ //! of the reversed tree.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ reverse_iterator rend()\r
+ { return reverse_iterator(begin()); }\r
+\r
+ //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end\r
+ //! of the reversed tree.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ const_reverse_iterator rend() const\r
+ { return const_reverse_iterator(begin()); }\r
+\r
+ //! <b>Effects</b>: Returns the value_compare object used by the tree.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: If value_compare copy-constructor throws.\r
+ value_compare value_comp() const\r
+ { return priv_comp(); }\r
+\r
+ //! <b>Effects</b>: Returns true is the container is empty.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ bool empty() const\r
+ { return node_algorithms::unique(const_node_ptr(&priv_header())); }\r
+\r
+ //! <b>Effects</b>: Returns the number of elements stored in the tree.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to elements contained in *this.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ size_type size() const\r
+ {\r
+ if(ConstantTimeSize)\r
+ return size_traits::get_size();\r
+ else\r
+ return empty() ? 0 : node_algorithms::count(node_traits::get_parent(const_node_ptr(&priv_header())));\r
+ }\r
+\r
+ //! <b>Effects</b>: Swaps the contents of two multisets.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: If the comparison functor's unspecified swap call throws.\r
+ void swap(irbtree& other)\r
+ {\r
+ //This can throw\r
+ using std::swap;\r
+ swap(priv_comp(), priv_comp());\r
+ //These can't throw\r
+ node_algorithms::swap_tree(node_ptr(&priv_header()), node_ptr(&other.priv_header()));\r
+ if(ConstantTimeSize){\r
+ size_type backup = size_traits::get_size();\r
+ size_traits::set_size(other.get_size());\r
+ other.set_size(backup);\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: value must be an lvalue\r
+ //! \r
+ //! <b>Effects</b>: Inserts value into the tree before the upper bound.\r
+ //! \r
+ //! <b>Complexity</b>: Average complexity for insert element is at\r
+ //! most logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Note</b>: Does not affect the validity of iterators and references.\r
+ //! No copy-constructors are called.\r
+ iterator insert_equal_upper_bound(value_type &value)\r
+ {\r
+ key_node_ptr_compare<value_compare> key_node_comp(priv_comp());\r
+ node_ptr to_insert(ValueTraits::to_node_ptr(value));\r
+ if(safemode_or_autounlink)\r
+ BOOST_ASSERT(node_algorithms::unique(to_insert));\r
+ size_traits::increment();\r
+ return iterator(node_algorithms::insert_equal_upper_bound\r
+ (node_ptr(&priv_header()), to_insert, key_node_comp));\r
+ }\r
+\r
+ //! <b>Requires</b>: value must be an lvalue\r
+ //! \r
+ //! <b>Effects</b>: Inserts value into the tree before the lower bound.\r
+ //! \r
+ //! <b>Complexity</b>: Average complexity for insert element is at\r
+ //! most logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Note</b>: Does not affect the validity of iterators and references.\r
+ //! No copy-constructors are called.\r
+ iterator insert_equal_lower_bound(value_type &value)\r
+ {\r
+ key_node_ptr_compare<value_compare> key_node_comp(priv_comp());\r
+ node_ptr to_insert(ValueTraits::to_node_ptr(value));\r
+ if(safemode_or_autounlink)\r
+ BOOST_ASSERT(node_algorithms::unique(to_insert));\r
+ size_traits::increment();\r
+ return iterator(node_algorithms::insert_equal_lower_bound\r
+ (node_ptr(&priv_header()), to_insert, key_node_comp));\r
+ }\r
+\r
+ //! <b>Requires</b>: value must be an lvalue, and "hint" must be\r
+ //! a valid iterator.\r
+ //! \r
+ //! <b>Effects</b>: Inserts x into the tree, using "hint" as a hint to\r
+ //! where it will be inserted. If "hint" is the upper_bound\r
+ //! the insertion takes constant time (two comparisons in the worst case)\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic in general, but it is amortized\r
+ //! constant time if t is inserted immediately before hint.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Note</b>: Does not affect the validity of iterators and references.\r
+ //! No copy-constructors are called.\r
+ iterator insert_equal(const_iterator hint, value_type &value)\r
+ {\r
+ key_node_ptr_compare<value_compare> key_node_comp(priv_comp());\r
+ node_ptr to_insert(ValueTraits::to_node_ptr(value));\r
+ if(safemode_or_autounlink)\r
+ BOOST_ASSERT(node_algorithms::unique(to_insert));\r
+ size_traits::increment();\r
+ return iterator(node_algorithms::insert_equal\r
+ (node_ptr(&priv_header()), hint.tree_node(), to_insert, key_node_comp));\r
+ }\r
+\r
+ //! <b>Requires</b>: Dereferencing iterator must yield an lvalue \r
+ //! of type value_type.\r
+ //! \r
+ //! <b>Effects</b>: Inserts a each element of a range into the tree\r
+ //! before the upper bound of the key of each element.\r
+ //! \r
+ //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the \r
+ //! size of the range. However, it is linear in N if the range is already sorted \r
+ //! by value_comp().\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Note</b>: Does not affect the validity of iterators and references.\r
+ //! No copy-constructors are called.\r
+ template<class Iterator>\r
+ void insert_equal(Iterator b, Iterator e)\r
+ {\r
+ if(this->empty()){\r
+ iterator end(this->end());\r
+ for (; b != e; ++b)\r
+ this->insert_equal(end, *b);\r
+ }\r
+ else{\r
+ for (; b != e; ++b)\r
+ this->insert_equal_upper_bound(*b);\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: value must be an lvalue\r
+ //! \r
+ //! <b>Effects</b>: Inserts value into the tree if the value\r
+ //! is not already present.\r
+ //! \r
+ //! <b>Complexity</b>: Average complexity for insert element is at\r
+ //! most logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Note</b>: Does not affect the validity of iterators and references.\r
+ //! No copy-constructors are called.\r
+ std::pair<iterator, bool> insert_unique(value_type &value)\r
+ {\r
+ insert_commit_data commit_data;\r
+ std::pair<iterator, bool> ret = insert_unique_check(value, commit_data);\r
+ if(!ret.second)\r
+ return ret;\r
+ return std::pair<iterator, bool> (insert_unique_commit(value, commit_data), true);\r
+ }\r
+\r
+ //! <b>Requires</b>: value must be an lvalue, and "hint" must be\r
+ //! a valid iterator\r
+ //! \r
+ //! <b>Effects</b>: Tries to insert x into the tree, using "hint" as a hint\r
+ //! to where it will be inserted.\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic in general, but it is amortized\r
+ //! constant time (two comparisons in the worst case)\r
+ //! if t is inserted immediately before hint.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Note</b>: Does not affect the validity of iterators and references.\r
+ //! No copy-constructors are called.\r
+ iterator insert_unique(const_iterator hint, value_type &value)\r
+ {\r
+ insert_commit_data commit_data;\r
+ std::pair<iterator, bool> ret = insert_unique_check(hint, value, commit_data);\r
+ if(!ret.second)\r
+ return ret.first;\r
+ return insert_unique_commit(value, commit_data);\r
+ }\r
+\r
+ //! <b>Requires</b>: Dereferencing iterator must yield an lvalue \r
+ //! of type value_type.\r
+ //! \r
+ //! <b>Effects</b>: Tries to insert each element of a range into the tree.\r
+ //! \r
+ //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the \r
+ //! size of the range. However, it is linear in N if the range is already sorted \r
+ //! by value_comp().\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Note</b>: Does not affect the validity of iterators and references.\r
+ //! No copy-constructors are called.\r
+ template<class Iterator>\r
+ void insert_unique(Iterator b, Iterator e)\r
+ {\r
+ if(this->empty()){\r
+ iterator end(this->end());\r
+ for (; b != e; ++b)\r
+ this->insert_unique(end, *b);\r
+ }\r
+ else{\r
+ for (; b != e; ++b)\r
+ this->insert_unique(*b);\r
+ }\r
+ }\r
+\r
+ std::pair<iterator, bool> insert_unique_check\r
+ (const value_type &value, insert_commit_data &commit_data)\r
+ { return insert_unique_check(value, priv_comp(), commit_data); }\r
+\r
+ template<class KeyType, class KeyValueCompare>\r
+ std::pair<iterator, bool> insert_unique_check\r
+ (const KeyType &key, KeyValueCompare key_value_comp, insert_commit_data &commit_data)\r
+ {\r
+ key_node_ptr_compare<KeyValueCompare> comp(key_value_comp);\r
+ std::pair<node_ptr, bool> ret = \r
+ (node_algorithms::insert_unique_check\r
+ (node_ptr(&priv_header()), key, comp, commit_data));\r
+ return std::pair<iterator, bool>(iterator(ret.first), ret.second);\r
+ }\r
+\r
+ std::pair<iterator, bool> insert_unique_check\r
+ (const_iterator hint, const value_type &value, insert_commit_data &commit_data)\r
+ { return insert_unique_check(hint, value, priv_comp(), commit_data); }\r
+\r
+ template<class KeyType, class KeyValueCompare>\r
+ std::pair<iterator, bool> insert_unique_check\r
+ (const_iterator hint, const KeyType &key\r
+ ,KeyValueCompare key_value_comp, insert_commit_data &commit_data)\r
+ {\r
+ key_node_ptr_compare<KeyValueCompare> comp(key_value_comp);\r
+ std::pair<node_ptr, bool> ret = \r
+ (node_algorithms::insert_unique_check\r
+ (node_ptr(&priv_header()), hint.tree_node(), key, comp, commit_data));\r
+ return std::pair<iterator, bool>(iterator(ret.first), ret.second);\r
+ }\r
+\r
+ iterator insert_unique_commit(value_type &value, const insert_commit_data &commit_data)\r
+ {\r
+ node_ptr to_insert(ValueTraits::to_node_ptr(value));\r
+ if(safemode_or_autounlink)\r
+ BOOST_ASSERT(node_algorithms::unique(to_insert));\r
+ size_traits::increment();\r
+ node_algorithms::insert_unique_commit\r
+ (node_ptr(&priv_header()), to_insert, commit_data);\r
+ return iterator(to_insert);\r
+ }\r
+\r
+ //! <b>Effects</b>: Erases the element pointed to by pos. \r
+ //! \r
+ //! <b>Complexity</b>: Average complexity for erase element is constant time. \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references)\r
+ //! to the erased elements. No destructors are called.\r
+ iterator erase(iterator i)\r
+ {\r
+ iterator ret(i);\r
+ ++ret;\r
+ node_ptr to_erase(i.tree_node());\r
+ if(safemode_or_autounlink)\r
+ BOOST_ASSERT(!node_algorithms::unique(to_erase));\r
+ node_algorithms::erase(&priv_header(), to_erase);\r
+ size_traits::decrement();\r
+ if(safemode_or_autounlink)\r
+ node_algorithms::init(to_erase);\r
+ return ret;\r
+ }\r
+\r
+ //! <b>Effects</b>: Erases the range pointed to by b end e. \r
+ //! \r
+ //! <b>Complexity</b>: Average complexity for erase range is at most \r
+ //! O(log(size() + N)), where N is the number of elements in the range.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references)\r
+ //! to the erased elements. No destructors are called.\r
+ iterator erase(iterator b, iterator e)\r
+ { size_type n; return private_erase(b, e, n); }\r
+\r
+ //! <b>Effects</b>: Erases all the elements with the given value.\r
+ //! \r
+ //! <b>Returns</b>: The number of erased elements.\r
+ //! \r
+ //! <b>Complexity</b>: O(log(size() + N).\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references)\r
+ //! to the erased elements. No destructors are called.\r
+ size_type erase(const value_type &value)\r
+ { return this->erase(value, priv_comp()); }\r
+\r
+ //! <b>Effects</b>: Erases all the elements with the given key.\r
+ //! according to the comparison functor "comp".\r
+ //!\r
+ //! <b>Returns</b>: The number of erased elements.\r
+ //! \r
+ //! <b>Complexity</b>: O(log(size() + N).\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references)\r
+ //! to the erased elements. No destructors are called.\r
+ template<class KeyType, class KeyValueCompare>\r
+ size_type erase(const KeyType& key, KeyValueCompare comp)\r
+ {\r
+ std::pair<iterator,iterator> p = this->equal_range(key, comp);\r
+ size_type n;\r
+ private_erase(p.first, p.second, n);\r
+ return n;\r
+ }\r
+\r
+ //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
+ //!\r
+ //! <b>Effects</b>: Erases the element pointed to by pos. \r
+ //! Destroyer::operator()(pointer) is called for the removed element.\r
+ //! \r
+ //! <b>Complexity</b>: Average complexity for erase element is constant time. \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators \r
+ //! to the erased elements.\r
+ template<class Destroyer>\r
+ iterator erase_and_destroy(iterator i, Destroyer destroyer)\r
+ {\r
+ node_ptr to_erase(i.tree_node());\r
+ iterator ret(this->erase(i));\r
+ destroyer(ValueTraits::to_value_ptr(to_erase));\r
+ return ret;\r
+ }\r
+\r
+ //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
+ //!\r
+ //! <b>Effects</b>: Erases the range pointed to by b end e.\r
+ //! Destroyer::operator()(pointer) is called for the removed elements.\r
+ //! \r
+ //! <b>Complexity</b>: Average complexity for erase range is at most \r
+ //! O(log(size() + N)), where N is the number of elements in the range.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators\r
+ //! to the erased elements.\r
+ template<class Destroyer>\r
+ iterator erase_and_destroy(iterator b, iterator e, Destroyer destroyer)\r
+ { size_type n; return private_erase(b, e, n, destroyer); }\r
+\r
+ //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
+ //!\r
+ //! <b>Effects</b>: Erases all the elements with the given value.\r
+ //! Destroyer::operator()(pointer) is called for the removed elements.\r
+ //! \r
+ //! <b>Returns</b>: The number of erased elements.\r
+ //! \r
+ //! <b>Complexity</b>: O(log(size() + N).\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references)\r
+ //! to the erased elements. No destructors are called.\r
+ template<class Destroyer>\r
+ size_type erase_and_destroy(const value_type &value, Destroyer destroyer)\r
+ {\r
+ std::pair<iterator,iterator> p = this->equal_range(value);\r
+ size_type n;\r
+ private_erase(p.first, p.second, n, destroyer);\r
+ return n;\r
+ }\r
+\r
+ //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
+ //!\r
+ //! <b>Effects</b>: Erases all the elements with the given key.\r
+ //! according to the comparison functor "comp".\r
+ //! Destroyer::operator()(pointer) is called for the removed elements.\r
+ //!\r
+ //! <b>Returns</b>: The number of erased elements.\r
+ //! \r
+ //! <b>Complexity</b>: O(log(size() + N).\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators\r
+ //! to the erased elements.\r
+ template<class KeyType, class KeyValueCompare, class Destroyer>\r
+ size_type erase_and_destroy(const KeyType& key, KeyValueCompare comp, Destroyer destroyer)\r
+ {\r
+ std::pair<iterator,iterator> p = this->equal_range(key, comp);\r
+ size_type n;\r
+ private_erase(p.first, p.second, n, destroyer);\r
+ return n;\r
+ }\r
+\r
+ //! <b>Effects</b>: Erases all of the elements. \r
+ //! \r
+ //! <b>Complexity</b>: Linear to the number of elements on the container.\r
+ //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references)\r
+ //! to the erased elements. No destructors are called.\r
+ void clear()\r
+ {\r
+ if(safemode_or_autounlink){\r
+ while(1){\r
+ node_ptr leftmost\r
+ (node_algorithms::unlink_leftmost_without_rebalance\r
+ (node_ptr(&priv_header())));\r
+ if(!leftmost)\r
+ break;\r
+ size_traits::decrement();\r
+ if(safemode_or_autounlink)\r
+ node_algorithms::init(leftmost);\r
+ }\r
+ }\r
+ else{\r
+ node_algorithms::init_header(&priv_header());\r
+ size_traits::set_size(0);\r
+ }\r
+ }\r
+\r
+ //! <b>Effects</b>: Erases all of the elements calling destroyer(p) for\r
+ //! each node to be erased.\r
+ //! <b>Complexity</b>: Average complexity for is at most O(log(size() + N)),\r
+ //! where N is the number of elements in the container.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references)\r
+ //! to the erased elements. Calls N times to destroyer functor.\r
+ template<class Destroyer>\r
+ void clear_and_destroy(Destroyer destroyer)\r
+ {\r
+ while(1){\r
+ node_ptr leftmost\r
+ (node_algorithms::unlink_leftmost_without_rebalance\r
+ (node_ptr(&priv_header())));\r
+ if(!leftmost)\r
+ break;\r
+ size_traits::decrement();\r
+ if(safemode_or_autounlink)\r
+ node_algorithms::init(leftmost);\r
+ destroyer(ValueTraits::to_value_ptr(leftmost));\r
+ }\r
+ }\r
+\r
+ //! <b>Effects</b>: Returns the number of contained elements with the given value\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal\r
+ //! to number of objects with the given value.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ size_type count(const value_type &value) const\r
+ { return this->count(value, priv_comp()); }\r
+\r
+ //! <b>Effects</b>: Returns the number of contained elements with the given key\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal\r
+ //! to number of objects with the given key.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ template<class KeyType, class KeyValueCompare>\r
+ size_type count(const KeyType &key, KeyValueCompare comp) const\r
+ {\r
+ std::pair<const_iterator, const_iterator> ret = this->equal_range(key, comp);\r
+ return std::distance(ret.first, ret.second);\r
+ }\r
+\r
+ //! <b>Effects</b>: Returns an iterator to the first element whose\r
+ //! key is not less than k or end() if that element does not exist.\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ iterator lower_bound(const value_type &value)\r
+ { return this->lower_bound(value, priv_comp()); }\r
+\r
+ //! <b>Effects</b>: Returns an iterator to the first element whose\r
+ //! key is not less than k or end() if that element does not exist.\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ const_iterator lower_bound(const value_type &value) const\r
+ { return this->lower_bound(value, priv_comp()); }\r
+\r
+ //! <b>Effects</b>: Returns an iterator to the first element whose\r
+ //! key is not less than k or end() if that element does not exist.\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ template<class KeyType, class KeyValueCompare>\r
+ iterator lower_bound(const KeyType &key, KeyValueCompare comp)\r
+ {\r
+ key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);\r
+ return iterator(node_algorithms::lower_bound\r
+ (const_node_ptr(&priv_header()), key, key_node_comp));\r
+ }\r
+\r
+ //! <b>Effects</b>: Returns a const iterator to the first element whose\r
+ //! key is not less than k or end() if that element does not exist.\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ template<class KeyType, class KeyValueCompare>\r
+ const_iterator lower_bound(const KeyType &key, KeyValueCompare comp) const\r
+ {\r
+ key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);\r
+ return const_iterator(node_algorithms::lower_bound\r
+ (const_node_ptr(&priv_header()), key, key_node_comp));\r
+ }\r
+\r
+ //! <b>Effects</b>: Returns an iterator to the first element whose\r
+ //! key is greater than k or end() if that element does not exist.\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ iterator upper_bound(const value_type &value)\r
+ { return this->upper_bound(value, priv_comp()); }\r
+\r
+ //! <b>Effects</b>: Returns an iterator to the first element whose\r
+ //! key is greater than k according to comp or end() if that element\r
+ //! does not exist.\r
+ //!\r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ template<class KeyType, class KeyValueCompare>\r
+ iterator upper_bound(const KeyType &key, KeyValueCompare comp)\r
+ {\r
+ key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);\r
+ return iterator(node_algorithms::upper_bound\r
+ (const_node_ptr(&priv_header()), key, key_node_comp));\r
+ }\r
+\r
+ //! <b>Effects</b>: Returns an iterator to the first element whose\r
+ //! key is greater than k or end() if that element does not exist.\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ const_iterator upper_bound(const value_type &value) const\r
+ { return this->upper_bound(value, priv_comp()); }\r
+\r
+ //! <b>Effects</b>: Returns an iterator to the first element whose\r
+ //! key is greater than k according to comp or end() if that element\r
+ //! does not exist.\r
+ //!\r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ template<class KeyType, class KeyValueCompare>\r
+ const_iterator upper_bound(const KeyType &key, KeyValueCompare comp) const\r
+ {\r
+ key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);\r
+ return const_iterator(node_algorithms::upper_bound\r
+ (const_node_ptr(&priv_header()), key, key_node_comp));\r
+ }\r
+\r
+ //! <b>Effects</b>: Finds an iterator to the first element whose key is \r
+ //! k or end() if that element does not exist.\r
+ //!\r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ iterator find(const value_type &value)\r
+ { return this->find(value, priv_comp()); }\r
+\r
+ //! <b>Effects</b>: Finds an iterator to the first element whose key is \r
+ //! k or end() if that element does not exist.\r
+ //!\r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ template<class KeyType, class KeyValueCompare>\r
+ iterator find(const KeyType &key, KeyValueCompare comp)\r
+ {\r
+ key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);\r
+ return iterator\r
+ (node_algorithms::find(const_node_ptr(&priv_header()), key, key_node_comp));\r
+ }\r
+\r
+ //! <b>Effects</b>: Finds a const_iterator to the first element whose key is \r
+ //! k or end() if that element does not exist.\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ const_iterator find(const value_type &value) const\r
+ { return this->find(value, priv_comp()); }\r
+\r
+ //! <b>Effects</b>: Finds a const_iterator to the first element whose key is \r
+ //! k or end() if that element does not exist.\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ template<class KeyType, class KeyValueCompare>\r
+ const_iterator find(const KeyType &key, KeyValueCompare comp) const\r
+ {\r
+ key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);\r
+ return const_iterator\r
+ (node_algorithms::find(const_node_ptr(&priv_header()), key, key_node_comp));\r
+ }\r
+\r
+ //! <b>Effects</b>: Finds a range containing all elements whose key is k or\r
+ //! an empty range that indicates the position where those elements would be\r
+ //! if they there is no elements with key k.\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ std::pair<iterator,iterator> equal_range(const value_type &value)\r
+ { return this->equal_range(value, priv_comp()); }\r
+\r
+ //! <b>Effects</b>: Finds a range containing all elements whose key is k or\r
+ //! an empty range that indicates the position where those elements would be\r
+ //! if they there is no elements with key k.\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ template<class KeyType, class KeyValueCompare>\r
+ std::pair<iterator,iterator> equal_range(const KeyType &key, KeyValueCompare comp)\r
+ {\r
+ key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);\r
+ std::pair<node_ptr, node_ptr> ret\r
+ (node_algorithms::equal_range(const_node_ptr(&priv_header()), key, key_node_comp));\r
+ return std::pair<iterator, iterator>(iterator(ret.first), iterator(ret.second));\r
+ }\r
+\r
+ //! <b>Effects</b>: Finds a range containing all elements whose key is k or\r
+ //! an empty range that indicates the position where those elements would be\r
+ //! if they there is no elements with key k.\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ std::pair<const_iterator, const_iterator>\r
+ equal_range(const value_type &value) const\r
+ { return this->equal_range(value, priv_comp()); }\r
+\r
+ //! <b>Effects</b>: Finds a range containing all elements whose key is k or\r
+ //! an empty range that indicates the position where those elements would be\r
+ //! if they there is no elements with key k.\r
+ //! \r
+ //! <b>Complexity</b>: Logarithmic.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ template<class KeyType, class KeyValueCompare>\r
+ std::pair<const_iterator, const_iterator>\r
+ equal_range(const KeyType &key, KeyValueCompare comp) const\r
+ {\r
+ key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);\r
+ std::pair<node_ptr, node_ptr> ret\r
+ (node_algorithms::equal_range(const_node_ptr(&priv_header()), key, key_node_comp));\r
+ return std::pair<const_iterator, const_iterator>(const_iterator(ret.first), const_iterator(ret.second));\r
+ }\r
+\r
+ template <class Cloner, class Destroyer>\r
+ void clone_from(const irbtree &src, Cloner cloner, Destroyer destroyer)\r
+ {\r
+ this->clear_and_destroy(destroyer);\r
+ if(!src.empty()){\r
+ node_algorithms::clone_tree\r
+ (const_node_ptr(&src.priv_header())\r
+ ,node_ptr(&this->priv_header())\r
+ ,value_to_node_cloner<Cloner>(cloner)\r
+ ,value_to_node_destroyer<Destroyer>(destroyer));\r
+ size_traits::set_size(src.get_size());\r
+ }\r
+ }\r
+\r
+ pointer unlink_leftmost_without_rebalance()\r
+ {\r
+ node_ptr to_destroy(node_algorithms::unlink_leftmost_without_rebalance\r
+ (node_ptr(&priv_header())));\r
+ if(!to_destroy)\r
+ return 0;\r
+ size_traits::decrement();\r
+ if(safemode_or_autounlink)\r
+ node_algorithms::init(to_destroy);\r
+ return ValueTraits::to_value_ptr(to_destroy);\r
+ }\r
+\r
+ //! <b>Requires</b>: value must be an lvalue and shall be in a set of\r
+ //! appropriate type. Otherwise the behavior is undefined.\r
+ //! \r
+ //! <b>Effects</b>: Returns: a valid iterator i belonging to the set\r
+ //! that points to the value\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static iterator current(value_type &value)\r
+ { return iterator (ValueTraits::to_node_ptr(value)); }\r
+\r
+ //! <b>Requires</b>: value must be an lvalue and shall be in a set of\r
+ //! appropriate type. Otherwise the behavior is undefined.\r
+ //! \r
+ //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the\r
+ //! set that points to the value\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ static const_iterator current(const value_type &value) \r
+ { return const_iterator (ValueTraits::to_node_ptr(const_cast<value_type&> (value))); }\r
+/*\r
+ //! <b>Requires</b>: value shall not be in a tree of the appropriate type.\r
+ //! \r
+ //! <b>Effects</b>: init_node post-constructs the node data in x used by multisets of \r
+ //! the appropriate type. For the accessors multiset_derived_node and multiset_member_node \r
+ //! init_node has no effect, since the constructors of multiset_node_d and multiset_node_m \r
+ //! have already initialized the node data. \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant time.\r
+ //! \r
+ //! <b>Note</b>: This function is meant to be used mainly with the member value_traits, \r
+ //! where no implicit node initialization during construction occurs.\r
+ static void init_node(reference value)\r
+ { node_algorithms::init(node_ptr(&*ValueTraits::to_node_ptr(value))); }\r
+\r
+ //! <b>Effects</b>: removes x from a tree of the appropriate type. It has no effect,\r
+ //! if x is not in such a tree. \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant time.\r
+ //! \r
+ //! <b>Note</b>: This static function is only usable with the "safe mode"\r
+ //! hook and non-constant time size lists. Otherwise, the user must use\r
+ //! the non-static "erase(value_type &)" member. If the user calls\r
+ //! this function with a non "safe mode" or constant time size list\r
+ //! a compilation error will be issued.\r
+ template<class T>\r
+ static void remove_node(T& value)\r
+ {\r
+ //This function is only usable for safe mode hooks and non-constant\r
+ //time lists. \r
+ //BOOST_STATIC_ASSERT((!(safemode_or_autounlink && ConstantTimeSize)));\r
+ BOOST_STATIC_ASSERT((!ConstantTimeSize));\r
+ BOOST_STATIC_ASSERT((boost::is_convertible<T, value_type>::value));\r
+ node_ptr to_remove(ValueTraits::to_node_ptr(value));\r
+ node_algorithms::unlink_and_rebalance(to_remove);\r
+ if(safemode_or_autounlink)\r
+ node_algorithms::init(to_remove);\r
+ }\r
+*/\r
+ private:\r
+ template<class Destroyer>\r
+ iterator private_erase(iterator b, iterator e, size_type &n, Destroyer destroyer)\r
+ {\r
+ for(n = 0; b != e; ++n)\r
+ this->erase_and_destroy(b++, destroyer);\r
+ return b;\r
+ }\r
+\r
+ iterator private_erase(iterator b, iterator e, size_type &n)\r
+ {\r
+ for(n = 0; b != e; ++n)\r
+ this->erase(b++);\r
+ return b;\r
+ }\r
+};\r
+\r
+template <class V, class P, bool C, class S>\r
+inline bool operator==(const irbtree<V, P, C, S>& x, const irbtree<V, P, C, S>& y)\r
+{\r
+ if(C && x.size() != y.size()){\r
+ return false;\r
+ }\r
+ typedef typename irbtree<V, P, C, S>::const_iterator const_iterator;\r
+ const_iterator end1 = x.end();\r
+\r
+ const_iterator i1 = x.begin();\r
+ const_iterator i2 = y.begin();\r
+ if(C){\r
+ while (i1 != end1 && *i1 == *i2) {\r
+ ++i1;\r
+ ++i2;\r
+ }\r
+ return i1 == end1;\r
+ }\r
+ else{\r
+ const_iterator end2 = y.end();\r
+ while (i1 != end1 && i2 != end2 && *i1 == *i2) {\r
+ ++i1;\r
+ ++i2;\r
+ }\r
+ return i1 == end1 && i2 == end2;\r
+ }\r
+}\r
+\r
+template <class V, class P, bool C, class S>\r
+inline bool operator<(const irbtree<V, P, C, S>& x,\r
+ const irbtree<V, P, C, S>& y)\r
+{ return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }\r
+\r
+template <class V, class P, bool C, class S>\r
+inline bool operator!=(const irbtree<V, P, C, S>& x, const irbtree<V, P, C, S>& y) \r
+{ return !(x == y); }\r
+\r
+template <class V, class P, bool C, class S>\r
+inline bool operator>(const irbtree<V, P, C, S>& x, const irbtree<V, P, C, S>& y) \r
+{ return y < x; }\r
+\r
+template <class V, class P, bool C, class S>\r
+inline bool operator<=(const irbtree<V, P, C, S>& x, const irbtree<V, P, C, S>& y) \r
+{ return !(y < x); }\r
+\r
+template <class V, class P, bool C, class S>\r
+inline bool operator>=(const irbtree<V, P, C, S>& x, const irbtree<V, P, C, S>& y) \r
+{ return !(x < y); }\r
+\r
+template <class V, class P, bool C, class S>\r
+inline void swap(irbtree<V, P, C, S>& x, irbtree<V, P, C, S>& y)\r
+{ x.swap(y); }\r
+\r
+} //namespace detail\r
+} //namespace intrusive \r
+} //namespace boost \r
+\r
+#include "config_end.hpp"\r
+\r
+#endif //BOOST_INTRUSIVE_IRBTREE_HPP\r
projects / senf.git / blobdiff