Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r79498 - in trunk/boost/intrusive: . detail
From: igaztanaga_at_[hidden]
Date: 2012-07-14 09:29:30

Next message: igaztanaga_at_[hidden]: "[Boost-commit] svn:boost r79499 - in trunk/libs/intrusive: doc proj/vc7ide test"
Previous message: jurko.gospodnetic_at_[hidden]: "[Boost-commit] svn:boost r79497 - trunk/tools/build/v2/engine"

Author: igaztanaga
Date: 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
New Revision: 79498
URL: http://svn.boost.org/trac/boost/changeset/79498

Log:
Added `bounded_range` function to trees
Text files modified:
   trunk/boost/intrusive/avl_set.hpp | 170 +++++++++++++++++++++++++++++++++++++++
   trunk/boost/intrusive/avltree.hpp | 98 ++++++++++++++++++++++
   trunk/boost/intrusive/avltree_algorithms.hpp | 25 +++++
   trunk/boost/intrusive/detail/tree_algorithms.hpp | 164 ++++++++++++++++++++++++-------------
   trunk/boost/intrusive/detail/utilities.hpp | 2
   trunk/boost/intrusive/rbtree.hpp | 98 ++++++++++++++++++++++
   trunk/boost/intrusive/rbtree_algorithms.hpp | 25 +++++
   trunk/boost/intrusive/set.hpp | 170 +++++++++++++++++++++++++++++++++++++++
   trunk/boost/intrusive/sg_set.hpp | 170 +++++++++++++++++++++++++++++++++++++++
   trunk/boost/intrusive/sgtree.hpp | 106 +++++++++++++++++++++++
   trunk/boost/intrusive/sgtree_algorithms.hpp | 25 +++++
   trunk/boost/intrusive/splay_set.hpp | 172 ++++++++++++++++++++++++++++++++++++++++
   trunk/boost/intrusive/splaytree.hpp | 98 ++++++++++++++++++++++
   trunk/boost/intrusive/splaytree_algorithms.hpp | 45 +++++++++-
   trunk/boost/intrusive/treap.hpp | 98 ++++++++++++++++++++++
   trunk/boost/intrusive/treap_algorithms.hpp | 25 +++++
   trunk/boost/intrusive/treap_set.hpp | 170 +++++++++++++++++++++++++++++++++++++++
   17 files changed, 1594 insertions(+), 67 deletions(-)

Modified: trunk/boost/intrusive/avl_set.hpp
==============================================================================
--- trunk/boost/intrusive/avl_set.hpp (original)
+++ trunk/boost/intrusive/avl_set.hpp 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
@@ -969,6 +969,91 @@
 equal_range(const KeyType& key, KeyValueCompare comp) const
 { return tree_.equal_range(key, comp); }

+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<iterator,iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<iterator,iterator> bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<const_iterator, const_iterator>
+ bounded_range(const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<const_iterator, const_iterator>
+ bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
 //! Requires: value must be an lvalue and shall be in a avl_set of
 //! appropriate type. Otherwise the behavior is undefined.
 //!
@@ -2086,6 +2171,91 @@
 equal_range(const KeyType& key, KeyValueCompare comp) const
 { return tree_.equal_range(key, comp); }

+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<iterator,iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<iterator,iterator> bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<const_iterator, const_iterator>
+ bounded_range(const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<const_iterator, const_iterator>
+ bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
 //! Requires: value must be an lvalue and shall be in a avl_multiset of
 //! appropriate type. Otherwise the behavior is undefined.
 //!

Modified: trunk/boost/intrusive/avltree.hpp
==============================================================================
--- trunk/boost/intrusive/avltree.hpp (original)
+++ trunk/boost/intrusive/avltree.hpp 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
@@ -1228,6 +1228,104 @@
 return std::pair<const_iterator, const_iterator>(const_iterator(ret.first, this), const_iterator(ret.second, this));
 }

+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<iterator,iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
+ { return this->bounded_range(lower_value, upper_value, priv_comp(), left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<iterator,iterator> bounded_range
+ (const KeyType &lower_key, const KeyType &upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
+ {
+ detail::key_nodeptr_comp<KeyValueCompare, avltree_impl>
+ key_node_comp(comp, this);
+ std::pair<node_ptr, node_ptr> ret
+ (node_algorithms::bounded_range
+ (this->priv_header_ptr(), lower_key, upper_key, key_node_comp, left_closed, right_closed));
+ return std::pair<iterator, iterator>(iterator(ret.first, this), iterator(ret.second, this));
+ }
+
+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<const_iterator,const_iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
+ { return this->bounded_range(lower_value, upper_value, priv_comp(), left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<const_iterator,const_iterator> bounded_range
+ (const KeyType &lower_key, const KeyType &upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
+ {
+ detail::key_nodeptr_comp<KeyValueCompare, avltree_impl>
+ key_node_comp(comp, this);
+ std::pair<node_ptr, node_ptr> ret
+ (node_algorithms::bounded_range
+ (this->priv_header_ptr(), lower_key, upper_key, key_node_comp, left_closed, right_closed));
+ return std::pair<const_iterator, const_iterator>(const_iterator(ret.first, this), const_iterator(ret.second, this));
+ }
+
 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //! Cloner should yield to nodes equivalent to the original nodes.
 //!

Modified: trunk/boost/intrusive/avltree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/avltree_algorithms.hpp (original)
+++ trunk/boost/intrusive/avltree_algorithms.hpp 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
@@ -464,6 +464,31 @@
 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
 { return tree_algorithms::equal_range(header, key, comp); }

+ //! Requires: "header" must be the header node of a tree.
+ //! KeyNodePtrCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyNodePtrCompare>
+ static std::pair<node_ptr, node_ptr> bounded_range
+ (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp
+ , bool left_closed, bool right_closed)
+ { return tree_algorithms::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed); }
+
 //! Requires: "h" must be the header node of a tree.
 //! NodePtrCompare is a function object that induces a strict weak
 //! ordering compatible with the strict weak ordering used to create the

Modified: trunk/boost/intrusive/detail/tree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/detail/tree_algorithms.hpp (original)
+++ trunk/boost/intrusive/detail/tree_algorithms.hpp 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
@@ -765,55 +765,73 @@
 //! KeyNodePtrCompare is a function object that induces a strict weak
 //! ordering compatible with the strict weak ordering used to create the
 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
 //!
- //! Effects: Returns an a pair of node_ptr delimiting a range containing
- //! all elements that are equivalent to "key" according to "comp" or an
- //! empty range that indicates the position where those elements would be
- //! if they there are no equivalent elements.
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
 //!
 //! Complexity: Logarithmic.
 //!
 //! Throws: If "comp" throws.
- template<class KeyType, class KeyNodePtrCompare>
- static std::pair<node_ptr, node_ptr> equal_range
- (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template< class KeyType, class KeyNodePtrCompare>
+ static std::pair<node_ptr, node_ptr> bounded_range
+ ( const const_node_ptr & header
+ , const KeyType &lower_key
+ , const KeyType &upper_key
+ , KeyNodePtrCompare comp
+ , bool left_closed
+ , bool right_closed)
 {
 node_ptr y = uncast(header);
 node_ptr x = NodeTraits::get_parent(header);

 while(x){
- if(comp(x, key)){
+ //If x is less than lower_key the target
+ //range is on the right part
+ if(comp(x, lower_key)){
+ //Check for invalid input range
+ BOOST_INTRUSIVE_INVARIANT_ASSERT(comp(x, upper_key));
 x = NodeTraits::get_right(x);
 }
- else if(comp(key, x)){
+ //If the upper_key is less than x, the target
+ //range is on the left part
+ else if(comp(upper_key, x)){
+ //y > upper_key
 y = x;
 x = NodeTraits::get_left(x);
 }
 else{
- node_ptr xu(x), yu(y);
- y = x, x = NodeTraits::get_left(x);
- xu = NodeTraits::get_right(xu);
-
- while(x){
- if(comp(x, key)){
- x = NodeTraits::get_right(x);
- }
- else {
- y = x;
- x = NodeTraits::get_left(x);
- }
- }
-
- while(xu){
- if(comp(key, xu)){
- yu = xu;
- xu = NodeTraits::get_left(xu);
- }
- else {
- xu = NodeTraits::get_right(xu);
- }
- }
- return std::pair<node_ptr,node_ptr> (y, yu);
+ //x is inside the bounded range( x >= lower_key && x <= upper_key),
+ //so we must split lower and upper searches
+ //
+ //Sanity check: if lower_key and upper_key are equal, then both left_closed and right_closed can't be false
+ BOOST_INTRUSIVE_INVARIANT_ASSERT(left_closed || right_closed || comp(lower_key, x) || comp(x, upper_key));
+ return std::pair<node_ptr,node_ptr>(
+ left_closed
+ //If left_closed, then comp(x, lower_key) is already the lower_bound
+ //condition so we save one comparison and go to the next level
+ //following traditional lower_bound algo
+ ? lower_bound_loop(NodeTraits::get_left(x), x, lower_key, comp)
+ //If left-open, comp(x, lower_key) is not the upper_bound algo
+ //condition so we must recheck current 'x' node with upper_bound algo
+ : upper_bound_loop(x, y, lower_key, comp)
+ ,
+ right_closed
+ //If right_closed, then comp(upper_key, x) is already the upper_bound
+ //condition so we can save one comparison and go to the next level
+ //following lower_bound algo
+ ? upper_bound_loop(NodeTraits::get_right(x), y, upper_key, comp)
+ //If right-open, comp(upper_key, x) is not the lower_bound algo
+ //condition so we must recheck current 'x' node with lower_bound algo
+ : lower_bound_loop(x, y, upper_key, comp)
+ );
 }
 }
 return std::pair<node_ptr,node_ptr> (y, y);
@@ -824,6 +842,26 @@
 //! ordering compatible with the strict weak ordering used to create the
 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
 //!
+ //! Effects: Returns an a pair of node_ptr delimiting a range containing
+ //! all elements that are equivalent to "key" according to "comp" or an
+ //! empty range that indicates the position where those elements would be
+ //! if there are no equivalent elements.
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ template<class KeyType, class KeyNodePtrCompare>
+ static std::pair<node_ptr, node_ptr> equal_range
+ (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
+ {
+ return bounded_range(header, key, key, comp, true, true);
+ }
+
+ //! Requires: "header" must be the header node of a tree.
+ //! KeyNodePtrCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
+ //!
 //! Effects: Returns an node_ptr to the first element that is
 //! not less than "key" according to "comp" or "header" if that element does
 //! not exist.
@@ -835,18 +873,7 @@
 static node_ptr lower_bound
 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
 {
- node_ptr y = uncast(header);
- node_ptr x = NodeTraits::get_parent(header);
- while(x){
- if(comp(x, key)){
- x = NodeTraits::get_right(x);
- }
- else {
- y = x;
- x = NodeTraits::get_left(x);
- }
- }
- return y;
+ return lower_bound_loop(NodeTraits::get_parent(header), uncast(header), key, comp);
 }

 //! Requires: "header" must be the header node of a tree.
@@ -864,18 +891,7 @@
 static node_ptr upper_bound
 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
 {
- node_ptr y = uncast(header);
- node_ptr x = NodeTraits::get_parent(header);
- while(x){
- if(comp(key, x)){
- y = x;
- x = NodeTraits::get_left(x);
- }
- else {
- x = NodeTraits::get_right(x);
- }
- }
- return y;
+ return upper_bound_loop(NodeTraits::get_parent(header), uncast(header), key, comp);
 }

 //! Requires: "header" must be the header node of a tree.
@@ -1596,6 +1612,40 @@
 }

 private:
+
+ template<class KeyType, class KeyNodePtrCompare>
+ static node_ptr lower_bound_loop
+ (node_ptr x, node_ptr y, const KeyType &key, KeyNodePtrCompare comp)
+ {
+ while(x){
+ if(comp(x, key)){
+ x = NodeTraits::get_right(x);
+ }
+ else{
+ y = x;
+ x = NodeTraits::get_left(x);
+ }
+ }
+ return y;
+ }
+
+ template<class KeyType, class KeyNodePtrCompare>
+ static node_ptr upper_bound_loop
+ (node_ptr x, node_ptr y, const KeyType &key, KeyNodePtrCompare comp)
+ {
+ while(x){
+ if(comp(key, x)){
+ y = x;
+ x = NodeTraits::get_left(x);
+ }
+ else{
+ x = NodeTraits::get_right(x);
+ }
+ }
+ return y;
+ }
+
+
 template<class NodePtrCompare>
 static void insert_equal_check_impl
 (bool upper, const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, insert_commit_data & commit_data, std::size_t *pdepth = 0)

Modified: trunk/boost/intrusive/detail/utilities.hpp
==============================================================================
--- trunk/boost/intrusive/detail/utilities.hpp (original)
+++ trunk/boost/intrusive/detail/utilities.hpp 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
@@ -529,7 +529,7 @@
 x += 127 << 23;
 caster.x = x;
 val = caster.val;
- val = ((-1.0f/3) * val + 2) * val - 2.0f/3;
+ val = ((-1.0f/3.f) * val + 2.f) * val - (2.0f/3.f);

 return (val + log_2);
}

Modified: trunk/boost/intrusive/rbtree.hpp
==============================================================================
--- trunk/boost/intrusive/rbtree.hpp (original)
+++ trunk/boost/intrusive/rbtree.hpp 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
@@ -1232,6 +1232,104 @@
 return std::pair<const_iterator, const_iterator>(const_iterator(ret.first, this), const_iterator(ret.second, this));
 }

+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<iterator,iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
+ { return this->bounded_range(lower_value, upper_value, priv_comp(), left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<iterator,iterator> bounded_range
+ (const KeyType &lower_key, const KeyType &upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
+ {
+ detail::key_nodeptr_comp<KeyValueCompare, rbtree_impl>
+ key_node_comp(comp, this);
+ std::pair<node_ptr, node_ptr> ret
+ (node_algorithms::bounded_range
+ (this->priv_header_ptr(), lower_key, upper_key, key_node_comp, left_closed, right_closed));
+ return std::pair<iterator, iterator>(iterator(ret.first, this), iterator(ret.second, this));
+ }
+
+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<const_iterator,const_iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
+ { return this->bounded_range(lower_value, upper_value, priv_comp(), left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<const_iterator,const_iterator> bounded_range
+ (const KeyType &lower_key, const KeyType &upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
+ {
+ detail::key_nodeptr_comp<KeyValueCompare, rbtree_impl>
+ key_node_comp(comp, this);
+ std::pair<node_ptr, node_ptr> ret
+ (node_algorithms::bounded_range
+ (this->priv_header_ptr(), lower_key, upper_key, key_node_comp, left_closed, right_closed));
+ return std::pair<const_iterator, const_iterator>(const_iterator(ret.first, this), const_iterator(ret.second, this));
+ }
+
 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //! Cloner should yield to nodes equivalent to the original nodes.
 //!

Modified: trunk/boost/intrusive/rbtree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/rbtree_algorithms.hpp (original)
+++ trunk/boost/intrusive/rbtree_algorithms.hpp 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
@@ -518,6 +518,31 @@
 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
 { return tree_algorithms::equal_range(header, key, comp); }

+ //! Requires: "header" must be the header node of a tree.
+ //! KeyNodePtrCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyNodePtrCompare>
+ static std::pair<node_ptr, node_ptr> bounded_range
+ (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp
+ , bool left_closed, bool right_closed)
+ { return tree_algorithms::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed); }
+
 //! Requires: "h" must be the header node of a tree.
 //! NodePtrCompare is a function object that induces a strict weak
 //! ordering compatible with the strict weak ordering used to create the

Modified: trunk/boost/intrusive/set.hpp
==============================================================================
--- trunk/boost/intrusive/set.hpp (original)
+++ trunk/boost/intrusive/set.hpp 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
@@ -976,6 +976,91 @@
 equal_range(const KeyType& key, KeyValueCompare comp) const
 { return tree_.equal_range(key, comp); }

+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<iterator,iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<iterator,iterator> bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<const_iterator, const_iterator>
+ bounded_range(const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<const_iterator, const_iterator>
+ bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
 //! Requires: value must be an lvalue and shall be in a set of
 //! appropriate type. Otherwise the behavior is undefined.
 //!
@@ -2096,6 +2181,91 @@
 equal_range(const KeyType& key, KeyValueCompare comp) const
 { return tree_.equal_range(key, comp); }

+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<iterator,iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<iterator,iterator> bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<const_iterator, const_iterator>
+ bounded_range(const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<const_iterator, const_iterator>
+ bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
 //! Requires: value must be an lvalue and shall be in a set of
 //! appropriate type. Otherwise the behavior is undefined.
 //!

Modified: trunk/boost/intrusive/sg_set.hpp
==============================================================================
--- trunk/boost/intrusive/sg_set.hpp (original)
+++ trunk/boost/intrusive/sg_set.hpp 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
@@ -967,6 +967,91 @@
 equal_range(const KeyType& key, KeyValueCompare comp) const
 { return tree_.equal_range(key, comp); }

+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<iterator,iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<iterator,iterator> bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<const_iterator, const_iterator>
+ bounded_range(const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<const_iterator, const_iterator>
+ bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
 //! Requires: value must be an lvalue and shall be in a sg_set of
 //! appropriate type. Otherwise the behavior is undefined.
 //!
@@ -2119,6 +2204,91 @@
 equal_range(const KeyType& key, KeyValueCompare comp) const
 { return tree_.equal_range(key, comp); }

+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<iterator,iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<iterator,iterator> bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<const_iterator, const_iterator>
+ bounded_range(const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<const_iterator, const_iterator>
+ bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
 //! Requires: value must be an lvalue and shall be in a sg_multiset of
 //! appropriate type. Otherwise the behavior is undefined.
 //!

Modified: trunk/boost/intrusive/sgtree.hpp
==============================================================================
--- trunk/boost/intrusive/sgtree.hpp (original)
+++ trunk/boost/intrusive/sgtree.hpp 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
@@ -48,7 +48,7 @@

namespace detail{

-//! Returns floor(log(n)/log(sqrt(2))) -> floor(2*log2(n))
+//! Returns floor(log2(n)/log2(sqrt(2))) -> floor(2*log2(n))
//! Undefined if N is 0.
//!
//! This function does not use float point operations.
@@ -83,9 +83,9 @@

 std::size_t operator()(std::size_t n) const
 {
- //Returns floor(log1/alpha(n)) ->
- // floor(log(n)/log(1/alpha)) ->
- // floor(log(n)/(-log(alpha)))
+ //Returns floor(log2(1/alpha(n))) ->
+ // floor(log2(n)/log(1/alpha)) ->
+ // floor(log2(n)/(-log2(alpha)))
 //return static_cast<std::size_t>(std::log(float(n))*inv_minus_logalpha_);
 return static_cast<std::size_t>(detail::fast_log2(float(n))*inv_minus_logalpha_);
 }
@@ -1404,6 +1404,104 @@
 return std::pair<const_iterator, const_iterator>(const_iterator(ret.first, this), const_iterator(ret.second, this));
 }

+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<iterator,iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
+ { return this->bounded_range(lower_value, upper_value, priv_comp(), left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<iterator,iterator> bounded_range
+ (const KeyType &lower_key, const KeyType &upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
+ {
+ detail::key_nodeptr_comp<KeyValueCompare, sgtree_impl>
+ key_node_comp(comp, this);
+ std::pair<node_ptr, node_ptr> ret
+ (node_algorithms::bounded_range
+ (this->priv_header_ptr(), lower_key, upper_key, key_node_comp, left_closed, right_closed));
+ return std::pair<iterator, iterator>(iterator(ret.first, this), iterator(ret.second, this));
+ }
+
+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<const_iterator,const_iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
+ { return this->bounded_range(lower_value, upper_value, priv_comp(), left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<const_iterator,const_iterator> bounded_range
+ (const KeyType &lower_key, const KeyType &upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
+ {
+ detail::key_nodeptr_comp<KeyValueCompare, sgtree_impl>
+ key_node_comp(comp, this);
+ std::pair<node_ptr, node_ptr> ret
+ (node_algorithms::bounded_range
+ (this->priv_header_ptr(), lower_key, upper_key, key_node_comp, left_closed, right_closed));
+ return std::pair<const_iterator, const_iterator>(const_iterator(ret.first, this), const_iterator(ret.second, this));
+ }
+
 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //! Cloner should yield to nodes equivalent to the original nodes.
 //!

Modified: trunk/boost/intrusive/sgtree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/sgtree_algorithms.hpp (original)
+++ trunk/boost/intrusive/sgtree_algorithms.hpp 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
@@ -421,6 +421,31 @@
 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
 { return tree_algorithms::equal_range(header, key, comp); }

+ //! Requires: "header" must be the header node of a tree.
+ //! KeyNodePtrCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyNodePtrCompare>
+ static std::pair<node_ptr, node_ptr> bounded_range
+ (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp
+ , bool left_closed, bool right_closed)
+ { return tree_algorithms::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed); }
+
 //! Requires: "h" must be the header node of a tree.
 //! NodePtrCompare is a function object that induces a strict weak
 //! ordering compatible with the strict weak ordering used to create the

Modified: trunk/boost/intrusive/splay_set.hpp
==============================================================================
--- trunk/boost/intrusive/splay_set.hpp (original)
+++ trunk/boost/intrusive/splay_set.hpp 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
@@ -934,6 +934,92 @@
 equal_range_dont_splay(const KeyType& key, KeyValueCompare comp) const
 { return tree_.equal_range_dont_splay(key, comp); }

+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<iterator,iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<iterator,iterator> bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<const_iterator, const_iterator>
+ bounded_range_dont_splay_dont_splay
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range_dont_splay(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<const_iterator, const_iterator>
+ bounded_range_dont_splay
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range_dont_splay(lower_key, upper_key, comp, left_closed, right_closed); }
+
 //! Requires: value must be an lvalue and shall be in a splay_set of
 //! appropriate type. Otherwise the behavior is undefined.
 //!
@@ -2073,6 +2159,92 @@
 equal_range_dont_splay(const KeyType& key, KeyValueCompare comp) const
 { return tree_.equal_range_dont_splay(key, comp); }

+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<iterator,iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<iterator,iterator> bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<const_iterator, const_iterator>
+ bounded_range_dont_splay
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range_dont_splay(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<const_iterator, const_iterator>
+ bounded_range_dont_splay
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range_dont_splay(lower_key, upper_key, comp, left_closed, right_closed); }
+
 //! Requires: value must be an lvalue and shall be in a set of
 //! appropriate type. Otherwise the behavior is undefined.
 //!

Modified: trunk/boost/intrusive/splaytree.hpp
==============================================================================
--- trunk/boost/intrusive/splaytree.hpp (original)
+++ trunk/boost/intrusive/splaytree.hpp 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
@@ -1169,6 +1169,104 @@
 return std::pair<const_iterator, const_iterator>(const_iterator(ret.first, this), const_iterator(ret.second, this));
 }

+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<iterator,iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
+ { return this->bounded_range(lower_value, upper_value, priv_comp(), left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<iterator,iterator> bounded_range
+ (const KeyType &lower_key, const KeyType &upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
+ {
+ detail::key_nodeptr_comp<KeyValueCompare, splaytree_impl>
+ key_node_comp(comp, this);
+ std::pair<node_ptr, node_ptr> ret
+ (node_algorithms::bounded_range
+ (this->priv_header_ptr(), lower_key, upper_key, key_node_comp, left_closed, right_closed));
+ return std::pair<iterator, iterator>(iterator(ret.first, this), iterator(ret.second, this));
+ }
+
+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<const_iterator,const_iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
+ { return this->bounded_range_dont_splay(lower_value, upper_value, priv_comp(), left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<const_iterator,const_iterator> bounded_range
+ (const KeyType &lower_key, const KeyType &upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
+ {
+ detail::key_nodeptr_comp<KeyValueCompare, splaytree_impl>
+ key_node_comp(comp, this);
+ std::pair<node_ptr, node_ptr> ret
+ (node_algorithms::bounded_range
+ (this->priv_header_ptr(), lower_key, upper_key, key_node_comp, left_closed, right_closed, false));
+ return std::pair<const_iterator, const_iterator>(const_iterator(ret.first, this), const_iterator(ret.second, this));
+ }
+
 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //! Cloner should yield to nodes equivalent to the original nodes.
 //!

Modified: trunk/boost/intrusive/splaytree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/splaytree_algorithms.hpp (original)
+++ trunk/boost/intrusive/splaytree_algorithms.hpp 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
@@ -15,7 +15,7 @@
// The code has been modified and (supposely) improved by Ion Gaztanaga.
// Here is the header of the file used as base code:
//
-// splay_tree.h -- implementation of a STL complatible splay tree.
+// splay_tree.h -- implementation of a STL compatible splay tree.
//
// Copyright (c) 2004 Ralf Mattethat
//
@@ -477,6 +477,38 @@
 //! KeyNodePtrCompare is a function object that induces a strict weak
 //! ordering compatible with the strict weak ordering used to create the
 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyNodePtrCompare>
+ static std::pair<node_ptr, node_ptr> bounded_range
+ (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp
+ , bool left_closed, bool right_closed, bool splay = true)
+ {
+ std::pair<node_ptr, node_ptr> ret =
+ tree_algorithms::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed);
+
+ if(splay)
+ splay_up(ret.first, uncast(header));
+ return ret;
+ }
+
+ //! Requires: "header" must be the header node of a tree.
+ //! KeyNodePtrCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
 //!
 //! Effects: Returns an node_ptr to the first element that is
 //! not less than "key" according to "comp" or "header" if that element does
@@ -772,10 +804,11 @@
 node_ptr leftmost (NodeTraits::get_left(header));
 node_ptr rightmost(NodeTraits::get_right(header));
 {
+ //Anti-exception rollback, recovers the original header node if an exception is thrown.
 detail::splaydown_rollback<NodeTraits> rollback(&t, header, leftmost, rightmost);
- node_ptr null = header;
- node_ptr l = null;
- node_ptr r = null;
+ node_ptr null_node = header;
+ node_ptr l = null_node;
+ node_ptr r = null_node;

 for( ;; ){
 if(comp(key, t)){
@@ -827,10 +860,12 @@
 }
 }

- assemble(t, l, r, null);
+ assemble(t, l, r, null_node);
 rollback.release();
 }

+ //Now recover the original header except for the
+ //splayed root node.
 //t is the current root
 NodeTraits::set_parent(header, t);
 NodeTraits::set_parent(t, header);

Modified: trunk/boost/intrusive/treap.hpp
==============================================================================
--- trunk/boost/intrusive/treap.hpp (original)
+++ trunk/boost/intrusive/treap.hpp 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
@@ -1339,6 +1339,104 @@
 return std::pair<const_iterator, const_iterator>(const_iterator(ret.first, this), const_iterator(ret.second, this));
 }

+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<iterator,iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
+ { return this->bounded_range(lower_value, upper_value, priv_comp(), left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<iterator,iterator> bounded_range
+ (const KeyType &lower_key, const KeyType &upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
+ {
+ detail::key_nodeptr_comp<KeyValueCompare, treap_impl>
+ key_node_comp(comp, this);
+ std::pair<node_ptr, node_ptr> ret
+ (node_algorithms::bounded_range
+ (this->priv_header_ptr(), lower_key, upper_key, key_node_comp, left_closed, right_closed));
+ return std::pair<iterator, iterator>(iterator(ret.first, this), iterator(ret.second, this));
+ }
+
+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<const_iterator,const_iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
+ { return this->bounded_range(lower_value, upper_value, priv_comp(), left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<const_iterator,const_iterator> bounded_range
+ (const KeyType &lower_key, const KeyType &upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
+ {
+ detail::key_nodeptr_comp<KeyValueCompare, treap_impl>
+ key_node_comp(comp, this);
+ std::pair<node_ptr, node_ptr> ret
+ (node_algorithms::bounded_range
+ (this->priv_header_ptr(), lower_key, upper_key, key_node_comp, left_closed, right_closed));
+ return std::pair<const_iterator, const_iterator>(const_iterator(ret.first, this), const_iterator(ret.second, this));
+ }
+
 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //! Cloner should yield to nodes equivalent to the original nodes.
 //!

Modified: trunk/boost/intrusive/treap_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/treap_algorithms.hpp (original)
+++ trunk/boost/intrusive/treap_algorithms.hpp 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
@@ -499,6 +499,31 @@
 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
 { return tree_algorithms::equal_range(header, key, comp); }

+ //! Requires: "header" must be the header node of a tree.
+ //! KeyNodePtrCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyNodePtrCompare>
+ static std::pair<node_ptr, node_ptr> bounded_range
+ (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp
+ , bool left_closed, bool right_closed)
+ { return tree_algorithms::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed); }
+
 //! Requires: "h" must be the header node of a tree.
 //! NodePtrCompare is a function object that induces a strict weak
 //! ordering compatible with the strict weak ordering used to create the

Modified: trunk/boost/intrusive/treap_set.hpp
==============================================================================
--- trunk/boost/intrusive/treap_set.hpp (original)
+++ trunk/boost/intrusive/treap_set.hpp 2012-07-14 09:29:28 EDT (Sat, 14 Jul 2012)
@@ -1043,6 +1043,91 @@
 equal_range(const KeyType& key, KeyValueCompare comp) const
 { return tree_.equal_range(key, comp); }

+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<iterator,iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<iterator,iterator> bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<const_iterator, const_iterator>
+ bounded_range(const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<const_iterator, const_iterator>
+ bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
 //! Requires: value must be an lvalue and shall be in a treap_set of
 //! appropriate type. Otherwise the behavior is undefined.
 //!
@@ -2265,6 +2350,91 @@
 equal_range(const KeyType& key, KeyValueCompare comp) const
 { return tree_.equal_range(key, comp); }

+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<iterator,iterator> bounded_range
+ (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<iterator,iterator> bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
+ //! Requires: 'lower_value' must not be greater than 'upper_value'. If
+ //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
+ //!
+ //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If the predicate throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_value and upper_value.
+ std::pair<const_iterator, const_iterator>
+ bounded_range(const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
+
+ //! Requires: KeyValueCompare is a function object that induces a strict weak
+ //! ordering compatible with the strict weak ordering used to create the
+ //! the tree.
+ //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //!
+ //! Effects: Returns an a pair with the following criteria:
+ //!
+ //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
+ //!
+ //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
+ //!
+ //! Complexity: Logarithmic.
+ //!
+ //! Throws: If "comp" throws.
+ //!
+ //! Note: This function can be more efficient than calling upper_bound
+ //! and lower_bound for lower_key and upper_key.
+ template<class KeyType, class KeyValueCompare>
+ std::pair<const_iterator, const_iterator>
+ bounded_range
+ (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
+ { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
+
 //! Requires: value must be an lvalue and shall be in a treap_multiset of
 //! appropriate type. Otherwise the behavior is undefined.
 //!

Next message: igaztanaga_at_[hidden]: "[Boost-commit] svn:boost r79499 - in trunk/libs/intrusive: doc proj/vc7ide test"
Previous message: jurko.gospodnetic_at_[hidden]: "[Boost-commit] svn:boost r79497 - trunk/tools/build/v2/engine"

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk