|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r48827 - sandbox/SOC/2006/tree/trunk/boost/tree
From: ockham_at_[hidden]
Date: 2008-09-17 17:09:08
Author: bernhard.reiter
Date: 2008-09-17 17:09:08 EDT (Wed, 17 Sep 2008)
New Revision: 48827
URL: http://svn.boost.org/trac/boost/changeset/48827
Log:
Replace tabs by spaces.
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp | 192 ++++++++--------
sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp | 478 ++++++++++++++++++++--------------------
sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp | 96 ++++----
sandbox/SOC/2006/tree/trunk/boost/tree/searcher.hpp | 440 ++++++++++++++++++------------------
4 files changed, 603 insertions(+), 603 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp 2008-09-17 17:09:08 EDT (Wed, 17 Sep 2008)
@@ -37,107 +37,107 @@
*
*/
template <class T, class Hierarchy = nary_tree<std::vector<T> >/*, class Balance,
- class Augment*/>
+ class Augment*/>
class multiway_tree {
- typedef multiway_tree<T, Hierarchy> self_type;
+ typedef multiway_tree<T, Hierarchy> self_type;
public:
- typedef T value_type;
- typedef Hierarchy hierarchy_type;
+ typedef T value_type;
+ typedef Hierarchy hierarchy_type;
-// typedef node<2, T, typename augmentor::metadata_type, typename balancer::metadata_type> node_type;
-
- typedef typename hierarchy_type::cursor base_cursor;
- typedef typename hierarchy_type::const_cursor base_const_cursor;
-
- typedef multiway_tree_cursor<base_cursor> cursor;
- typedef const_multiway_tree_cursor<base_const_cursor> const_cursor;
-
-// typedef inorder::iterator<cursor> iterator;
-// typedef inorder::iterator<const_cursor> const_iterator;
-//
-// typedef std::reverse_iterator<iterator> reverse_iterator;
-// typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
-
- typedef typename cursor_pointer<cursor>::type pointer;
- typedef typename cursor_reference<cursor>::type reference;
- typedef typename cursor_size<cursor>::type size_type;
- typedef typename cursor_difference<cursor>::type difference_type;
-
-// typedef typename node_traits<node_type>::node_base_type node_base_type;
-// typedef typename node_traits<node_type>::node_pointer node_pointer;
-
-// typedef typename ValAlloc::template rebind<value_type>::other
-// value_allocator_type;
-// typedef typename NodeAlloc::template rebind<node_type>::other
-// node_allocator_type;
-
-// multiway_tree()
-// {
-// h.insert(h.root(), );
-// }
-
- explicit multiway_tree(Hierarchy const& hier = Hierarchy()) : h(hier)
- { }
-
- bool empty()
- {
- return h.empty();
- }
-
- size_type size() const
- {
- return h.size();
- }
-
-
-
- /**
- * Returns a read/write ("mutable") cursor to the %nary_tree's root.
- */
- cursor root()
- {
- return cursor(h.root());
- }
-
- /**
- * Returns a read-only const_cursor to the %nary_tree's root.
- */
- const_cursor root() const
- {
- return croot();
- }
-
- /**
- * Returns a read-only const_cursor to the %nary_tree's root.
- */
- const_cursor croot() const
- {
- return const_cursor(h.croot());
- }
-
- cursor insert(cursor pos, value_type const& val)
- {
- base_cursor bc = base_cursor(pos);
-// if (bc != h.root())
-// bc = bc.parent();
+// typedef node<2, T, typename augmentor::metadata_type, typename balancer::metadata_type> node_type;
+
+ typedef typename hierarchy_type::cursor base_cursor;
+ typedef typename hierarchy_type::const_cursor base_const_cursor;
+
+ typedef multiway_tree_cursor<base_cursor> cursor;
+ typedef const_multiway_tree_cursor<base_const_cursor> const_cursor;
+
+// typedef inorder::iterator<cursor> iterator;
+// typedef inorder::iterator<const_cursor> const_iterator;
+//
+// typedef std::reverse_iterator<iterator> reverse_iterator;
+// typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+
+ typedef typename cursor_pointer<cursor>::type pointer;
+ typedef typename cursor_reference<cursor>::type reference;
+ typedef typename cursor_size<cursor>::type size_type;
+ typedef typename cursor_difference<cursor>::type difference_type;
+
+// typedef typename node_traits<node_type>::node_base_type node_base_type;
+// typedef typename node_traits<node_type>::node_pointer node_pointer;
+
+// typedef typename ValAlloc::template rebind<value_type>::other
+// value_allocator_type;
+// typedef typename NodeAlloc::template rebind<node_type>::other
+// node_allocator_type;
+
+// multiway_tree()
+// {
+// h.insert(h.root(), );
+// }
+
+ explicit multiway_tree(Hierarchy const& hier = Hierarchy()) : h(hier)
+ { }
+
+ bool empty()
+ {
+ return h.empty();
+ }
+
+ size_type size() const
+ {
+ return h.size();
+ }
+
+
+
+ /**
+ * Returns a read/write ("mutable") cursor to the %nary_tree's root.
+ */
+ cursor root()
+ {
+ return cursor(h.root());
+ }
+
+ /**
+ * Returns a read-only const_cursor to the %nary_tree's root.
+ */
+ const_cursor root() const
+ {
+ return croot();
+ }
+
+ /**
+ * Returns a read-only const_cursor to the %nary_tree's root.
+ */
+ const_cursor croot() const
+ {
+ return const_cursor(h.croot());
+ }
+
+ cursor insert(cursor pos, value_type const& val)
+ {
+ base_cursor bc = base_cursor(pos);
+// if (bc != h.root())
+// bc = bc.parent();
//if (bc.parity())
- //h.insert(bc, val);
- //if (bc == h.root())
- // bc =
- if (bc->empty()) {
- bc->push_back(val);
- bc.m_pos = 0;
- }
- else {
- bc->insert((bc->begin()+bc.parity()), val);
- }
- return cursor(bc);
-
- }
-
+ //h.insert(bc, val);
+ //if (bc == h.root())
+ // bc =
+ if (bc->empty()) {
+ bc->push_back(val);
+ bc.m_pos = 0;
+ }
+ else {
+ bc->insert((bc->begin()+bc.parity()), val);
+ }
+ return cursor(bc);
+
+ }
+
protected:
- hierarchy_type h;
-
+ hierarchy_type h;
+
};
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp 2008-09-17 17:09:08 EDT (Wed, 17 Sep 2008)
@@ -41,278 +41,278 @@
//to forest... Though: we might need metadata...
template <class Tp, class Alloc = std::allocator<Tp>,
- std::size_t N = /*numeric_limits<int>::max()*/ INT_MAX>
+ std::size_t N = /*(numeric_limits<int>::max)()*/ INT_MAX>
class nary_tree {
- typedef nary_tree<Tp, Alloc, N> self_type;
+ typedef nary_tree<Tp, Alloc, N> self_type;
public:
- typedef Tp value_type;
- typedef typename Alloc::template rebind<value_type>::other
- allocator_type;
-
- // We actually want a container whose capacity we can set and that doesn't
- // need an allocator...
- template <typename T>
- struct mycontainer //{
- : public std::vector<T, allocator_type> {
- explicit mycontainer(allocator_type const& = allocator_type())
- {}
- explicit mycontainer(typename std::vector<T, allocator_type>::size_type n,
- T const& = T(),
- allocator_type const& = allocator_type())
- {}
- };
-
- typedef node<value_type, mycontainer> node_type;
- typedef typename Alloc::template rebind<node_type>::other
- node_allocator_type;
- typedef typename node_traits<node_type>::node_base_type node_base_type;
- typedef node_base_type* node_base_pointer;
- typedef typename node_traits<node_type>::node_pointer node_pointer;
-
- typedef nary_tree_cursor<node_type> cursor;
- typedef nary_tree_cursor<node_type const> const_cursor;
-
-// typedef inorder::iterator<cursor> iterator;
-// typedef inorder::iterator<const_cursor> const_iterator;
-
-// typedef std::reverse_iterator<iterator> reverse_iterator;
-// typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
-
- typedef typename allocator_type::pointer pointer;
- typedef typename allocator_type::reference reference;
- typedef typename allocator_type::size_type size_type;
- typedef typename allocator_type::difference_type difference_type;
+ typedef Tp value_type;
+ typedef typename Alloc::template rebind<value_type>::other
+ allocator_type;
+
+ // We actually want a container whose capacity we can set and that doesn't
+ // need an allocator...
+ template <typename T>
+ struct mycontainer //{
+ : public std::vector<T, allocator_type> {
+ explicit mycontainer(allocator_type const& = allocator_type())
+ {}
+ explicit mycontainer(typename std::vector<T, allocator_type>::size_type n,
+ T const& = T(),
+ allocator_type const& = allocator_type())
+ {}
+ };
+
+ typedef node<value_type, mycontainer> node_type;
+ typedef typename Alloc::template rebind<node_type>::other
+ node_allocator_type;
+ typedef typename node_traits<node_type>::node_base_type node_base_type;
+ typedef node_base_type* node_base_pointer;
+ typedef typename node_traits<node_type>::node_pointer node_pointer;
+
+ typedef nary_tree_cursor<node_type> cursor;
+ typedef nary_tree_cursor<node_type const> const_cursor;
+
+// typedef inorder::iterator<cursor> iterator;
+// typedef inorder::iterator<const_cursor> const_iterator;
+
+// typedef std::reverse_iterator<iterator> reverse_iterator;
+// typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+
+ typedef typename allocator_type::pointer pointer;
+ typedef typename allocator_type::reference reference;
+ typedef typename allocator_type::size_type size_type;
+ typedef typename allocator_type::difference_type difference_type;
public:
- explicit nary_tree (allocator_type const& alloc = allocator_type())
- : m_header(), m_value_alloc(alloc)
- {
- m_header.push_back(node_base_type::nil());
- m_header.push_back(&m_header);
-
-// m_header[0] = node_base_type::nil();
-// m_header[1] = &m_header;
- }
-
- explicit nary_tree (size_type n, value_type const& value = value_type(),
- allocator_type const& alloc = allocator_type())
- : m_header(), m_value_alloc(alloc)
- {}
-
- template <class InputIterator>
- nary_tree (InputIterator first, InputIterator last,
- allocator_type const& alloc = allocator_type())
- : m_value_alloc(alloc)
- {
- while (first++ != last)
- this->insert(this->end(), *first);
- }
- nary_tree (self_type const& other)
- : m_header(other.m_header), m_value_alloc(other.m_value_alloc)
- {}
-
- ~nary_tree()
- {
- //clear();
- }
-
- nary_tree<Tp, Alloc>& operator=(
- nary_tree<Tp, Alloc> const& x);
- template <class InputIterator>
- void assign(InputIterator first, InputIterator last);
- template <class Size, class T>
- void assign(Size n, const T& t = T());
- allocator_type get_allocator() const;
-
- /// Functions returning cursors (as required by the Hierarchy concept)
-
- /**
- * Returns a read/write ("mutable") cursor to the %nary_tree's root.
- */
- cursor root()
- {
- return cursor(&m_header, 0);
- }
-
- /**
- * Returns a read-only const_cursor to the %nary_tree's root.
- */
- const_cursor root() const
- {
- return croot();
- }
-
- /**
- * Returns a read-only const_cursor to the %nary_tree's root.
- */
- const_cursor croot() const
- {
- return const_cursor(&m_header, 0);
- }
-
- /**
- * Returns a read/write ("mutable") cursor to the first (inorder) value.
- */
- cursor inorder_first()
- {
- return cursor(m_header[1], 0);
- }
-
- /**
- * Returns a read-only const_cursor to the first (inorder) value.
- */
- const_cursor inorder_first() const
- {
- return const_cursor(m_header[1], 0);
- }
-
- // Hierarchy-specific
- /**
- * @brief Inserts val in front of @a pos, or, if @a pos' parent is
- * already full, creates a new child node containing @a val
- * instead.
- * @param pos The %nary_tree cursor in front of which to insert.
- * @param val The value to insert.
- * @return A cursor that points to the inserted data.
- */
- cursor insert(cursor pos, value_type const& val)
- {
- //increment size!
-
- void* val_hint = 0;//TODO: need some method to obtain hints from cursor
- void* node_hint = 0;
-
- pointer p_val = m_value_alloc.allocate(1, val_hint);
- m_value_alloc.construct(p_val, val);
-
- node_pointer p_node = m_node_alloc.allocate(1, node_hint);
- m_node_alloc.construct(p_node, p_val);
-
- p_node->m_parent = pos.m_node;
-
- if (pos.m_node->operator[](pos.m_pos) == node_type::nil())
- static_cast<node_pointer>(pos.m_node)->operator[](pos.m_pos) = p_node;
- else
- if (static_cast<node_pointer>(pos.m_node)->empty()) {
- static_cast<node_pointer>(pos.m_node)->push_back(p_node);
- pos.m_pos = 0;
- } else
- static_cast<node_pointer>(pos.m_node)->insert(
- static_cast<node_pointer>(pos.m_node)->begin()+(pos.m_pos),
- p_node);
- return pos;
-// balancer_type::add(pos, this->root());
- }
-
- /**
- * Removes a node and its descendants recursively in postorder
- * without rebalancing
- * @param c Cursor pointing to the node to be removed.
- */
- void clear(cursor c)
- {
- if (!c.empty()) {
-
- // delete the value this c points to
- m_value_alloc.destroy(c.node()->data());
- m_value_alloc.deallocate(c.node()->data(), 1);
-
- // recurse
- clear(c.begin());
- clear(c.end());
-
- // delete the node c points to
- m_node_alloc.destroy(c.node());
- m_node_alloc.deallocate(c.node(), 1);
-
- }
- }
-
- /**
- * @brief Clears all data from the tree (without any rebalancing).
- */
- void clear()
- {
- clear(this->root());
- m_header.m_parent = &m_header;
- m_header[0] = node_base_type::nil();
- m_header[1] = &m_header;
- }
-
- bool empty() const
- {
- return m_header.m_parent == &m_header;
- }
+ explicit nary_tree (allocator_type const& alloc = allocator_type())
+ : m_header(), m_value_alloc(alloc)
+ {
+ m_header.push_back(node_base_type::nil());
+ m_header.push_back(&m_header);
+
+// m_header[0] = node_base_type::nil();
+// m_header[1] = &m_header;
+ }
+
+ explicit nary_tree (size_type n, value_type const& value = value_type(),
+ allocator_type const& alloc = allocator_type())
+ : m_header(), m_value_alloc(alloc)
+ {}
+
+ template <class InputIterator>
+ nary_tree (InputIterator first, InputIterator last,
+ allocator_type const& alloc = allocator_type())
+ : m_value_alloc(alloc)
+ {
+ while (first++ != last)
+ this->insert(this->end(), *first);
+ }
+ nary_tree (self_type const& other)
+ : m_header(other.m_header), m_value_alloc(other.m_value_alloc)
+ {}
+
+ ~nary_tree()
+ {
+ //clear();
+ }
+
+ nary_tree<Tp, Alloc>& operator=(
+ nary_tree<Tp, Alloc> const& x);
+ template <class InputIterator>
+ void assign(InputIterator first, InputIterator last);
+ template <class Size, class T>
+ void assign(Size n, const T& t = T());
+ allocator_type get_allocator() const;
+
+ /// Functions returning cursors (as required by the Hierarchy concept)
+
+ /**
+ * Returns a read/write ("mutable") cursor to the %nary_tree's root.
+ */
+ cursor root()
+ {
+ return cursor(&m_header, 0);
+ }
+
+ /**
+ * Returns a read-only const_cursor to the %nary_tree's root.
+ */
+ const_cursor root() const
+ {
+ return croot();
+ }
+
+ /**
+ * Returns a read-only const_cursor to the %nary_tree's root.
+ */
+ const_cursor croot() const
+ {
+ return const_cursor(&m_header, 0);
+ }
+
+ /**
+ * Returns a read/write ("mutable") cursor to the first (inorder) value.
+ */
+ cursor inorder_first()
+ {
+ return cursor(m_header[1], 0);
+ }
+
+ /**
+ * Returns a read-only const_cursor to the first (inorder) value.
+ */
+ const_cursor inorder_first() const
+ {
+ return const_cursor(m_header[1], 0);
+ }
+
+ // Hierarchy-specific
+ /**
+ * @brief Inserts val in front of @a pos, or, if @a pos' parent is
+ * already full, creates a new child node containing @a val
+ * instead.
+ * @param pos The %nary_tree cursor in front of which to insert.
+ * @param val The value to insert.
+ * @return A cursor that points to the inserted data.
+ */
+ cursor insert(cursor pos, value_type const& val)
+ {
+ //increment size!
+
+ void* val_hint = 0;//TODO: need some method to obtain hints from cursor
+ void* node_hint = 0;
+
+ pointer p_val = m_value_alloc.allocate(1, val_hint);
+ m_value_alloc.construct(p_val, val);
+
+ node_pointer p_node = m_node_alloc.allocate(1, node_hint);
+ m_node_alloc.construct(p_node, p_val);
+
+ p_node->m_parent = pos.m_node;
+
+ if (pos.m_node->operator[](pos.m_pos) == node_type::nil())
+ static_cast<node_pointer>(pos.m_node)->operator[](pos.m_pos) = p_node;
+ else
+ if (static_cast<node_pointer>(pos.m_node)->empty()) {
+ static_cast<node_pointer>(pos.m_node)->push_back(p_node);
+ pos.m_pos = 0;
+ } else
+ static_cast<node_pointer>(pos.m_node)->insert(
+ static_cast<node_pointer>(pos.m_node)->begin()+(pos.m_pos),
+ p_node);
+ return pos;
+// balancer_type::add(pos, this->root());
+ }
+
+ /**
+ * Removes a node and its descendants recursively in postorder
+ * without rebalancing
+ * @param c Cursor pointing to the node to be removed.
+ */
+ void clear(cursor c)
+ {
+ if (!c.empty()) {
+
+ // delete the value this c points to
+ m_value_alloc.destroy(c.node()->data());
+ m_value_alloc.deallocate(c.node()->data(), 1);
+
+ // recurse
+ clear(c.begin());
+ clear(c.end());
+
+ // delete the node c points to
+ m_node_alloc.destroy(c.node());
+ m_node_alloc.deallocate(c.node(), 1);
+
+ }
+ }
+
+ /**
+ * @brief Clears all data from the tree (without any rebalancing).
+ */
+ void clear()
+ {
+ clear(this->root());
+ m_header.m_parent = &m_header;
+ m_header[0] = node_base_type::nil();
+ m_header[1] = &m_header;
+ }
+
+ bool empty() const
+ {
+ return m_header.m_parent == &m_header;
+ }
private:
- node_base_type m_header;
+ node_base_type m_header;
- allocator_type m_value_alloc;
- node_allocator_type m_node_alloc;
-
- //erase operations must rebalance; clear doesn't need to.
- //TODO: Can/Should remove (and erase) return the next cursor's position ?
- //(There may be some DR concerning this for associative containers)
- void erase (cursor pos)
- {
- cursor root = this->root();
- pos = pos.parent();
-
- node_pointer p_node;
- if (pos == root) {
- p_node = pos.detach();
- } else {
- p_node = pos.detach(root);
- }
-
- m_value_alloc.destroy(p_node->data());
- m_value_alloc.deallocate(p_node->data(), 1);
-
- m_node_alloc.destroy(p_node);
- m_node_alloc.deallocate(p_node, 1);
- }
+ allocator_type m_value_alloc;
+ node_allocator_type m_node_alloc;
+
+ //erase operations must rebalance; clear doesn't need to.
+ //TODO: Can/Should remove (and erase) return the next cursor's position ?
+ //(There may be some DR concerning this for associative containers)
+ void erase (cursor pos)
+ {
+ cursor root = this->root();
+ pos = pos.parent();
+
+ node_pointer p_node;
+ if (pos == root) {
+ p_node = pos.detach();
+ } else {
+ p_node = pos.detach(root);
+ }
+
+ m_value_alloc.destroy(p_node->data());
+ m_value_alloc.deallocate(p_node->data(), 1);
+
+ m_node_alloc.destroy(p_node);
+ m_node_alloc.deallocate(p_node, 1);
+ }
};
//namespace inorder {
//
///**
-// * @brief First element of a MultiwayTree in inorder traversal
-// * (equivalent to postorder::first()) - O(1) overload for nary_tree
-// * @param t A nary_tree
-// * @return Mutable cursor to the first element of @a t in inorder traversal
+// * @brief First element of a MultiwayTree in inorder traversal
+// * (equivalent to postorder::first()) - O(1) overload for nary_tree
+// * @param t A nary_tree
+// * @return Mutable cursor to the first element of @a t in inorder traversal
// */
//template <class T, class Balance, class Augment, class Alloc>
//typename nary_tree<T, Balance, Augment, Alloc>::cursor
//first(nary_tree<T, Balance, Augment, Alloc>& t)
//{
-// return t.inorder_first();
+// return t.inorder_first();
//}
//
///**
-// * @brief First element of a MultiwayTree in inorder traversal
-// * (Alias of cfirst(); equivalent to postorder::first()) -
-// * O(1) overload for nary_tree
-// * @param t A nary_tree
-// * @return Read-only cursor to the first element of @a t in inorder traversal
+// * @brief First element of a MultiwayTree in inorder traversal
+// * (Alias of cfirst(); equivalent to postorder::first()) -
+// * O(1) overload for nary_tree
+// * @param t A nary_tree
+// * @return Read-only cursor to the first element of @a t in inorder traversal
// */
//template <class T, class Balance, class Augment, class Alloc>
//typename nary_tree<T, Balance, Augment, Alloc>::const_cursor
//first(nary_tree<T, Balance, Augment, Alloc>& t)
//{
-// return t.inorder_first();
+// return t.inorder_first();
//}
//
///**
-// * @brief First element of a MultiwayTree in inorder traversal
-// * (equivalent to postorder::first()) - O(1) overload for nary_tree
-// * @param t A nary_tree
-// * @return Read-only cursor to the first element of @a t in inorder traversal
+// * @brief First element of a MultiwayTree in inorder traversal
+// * (equivalent to postorder::first()) - O(1) overload for nary_tree
+// * @param t A nary_tree
+// * @return Read-only cursor to the first element of @a t in inorder traversal
// */
//template <class T, class Balance, class Augment, class Alloc>
//typename nary_tree<T, Balance, Augment, Alloc>::const_cursor
//cfirst(nary_tree<T, Balance, Augment, Alloc>& t)
//{
-// return t.inorder_first();
+// return t.inorder_first();
//}
//
//} // namespace inorder
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp 2008-09-17 17:09:08 EDT (Wed, 17 Sep 2008)
@@ -27,38 +27,38 @@
template <class Cursor>
class root_tracking_cursor
: public cursor_adaptor<root_tracking_cursor<Cursor>
- , Cursor
- , boost::use_default
- , typename cursor_horizontal_traversal<Cursor>::type
- , typename cursor_vertical_traversal<Cursor>::type
+ , Cursor
+ , boost::use_default
+ , typename cursor_horizontal_traversal<Cursor>::type
+ , typename cursor_vertical_traversal<Cursor>::type
> {
private:
struct enabler {};
- typedef root_tracking_cursor<Cursor> self_type;
+ typedef root_tracking_cursor<Cursor> self_type;
public:
- typedef typename Cursor::value_type value_type;
+ typedef typename Cursor::value_type value_type;
- // Container-specific:
- typedef typename Cursor::size_type size_type;
+ // Container-specific:
+ typedef typename Cursor::size_type size_type;
- // Cursor-specific
- typedef root_tracking_cursor<Cursor> cursor;
- typedef root_tracking_cursor<typename Cursor::const_cursor> const_cursor;
-
- // Container-specific:
- typedef cursor iterator;
- typedef const_cursor const_iterator;
-
- template <class OtherCursor>
- struct rebind {
- typedef root_tracking_cursor<OtherCursor> other;
- };
-
+ // Cursor-specific
+ typedef root_tracking_cursor<Cursor> cursor;
+ typedef root_tracking_cursor<typename Cursor::const_cursor> const_cursor;
+
+ // Container-specific:
+ typedef cursor iterator;
+ typedef const_cursor const_iterator;
+
+ template <class OtherCursor>
+ struct rebind {
+ typedef root_tracking_cursor<OtherCursor> other;
+ };
+
root_tracking_cursor()
: root_tracking_cursor::cursor_adaptor_(), m_depth(0) {}
explicit root_tracking_cursor(Cursor c)
- : root_tracking_cursor::cursor_adaptor_(c), m_depth(0) {}
+ : root_tracking_cursor::cursor_adaptor_(c), m_depth(0) {}
template <class OtherCursor>
root_tracking_cursor(
@@ -72,44 +72,44 @@
, m_depth(other.m_depth) {}
private:
- friend class boost::iterator_core_access;
+ friend class boost::iterator_core_access;
friend class boost::tree::cursor_core_access;
-
- std::size_t m_depth;
-
+
+ std::size_t m_depth;
+
// bool equal(cursor const& other) const
// {
// }
- void left()
- {
- ++m_depth;
- this->base_reference().to_begin();
- }
-
- void right()
- {
- ++m_depth;
- this->base_reference().to_end();
- }
-
- void up()
- {
- --m_depth;
- this->base_reference().to_parent();
- }
+ void left()
+ {
+ ++m_depth;
+ this->base_reference().to_begin();
+ }
+
+ void right()
+ {
+ ++m_depth;
+ this->base_reference().to_end();
+ }
+
+ void up()
+ {
+ --m_depth;
+ this->base_reference().to_parent();
+ }
public:
- bool is_root() const
- {
- return !m_depth;
- }
+ bool is_root() const
+ {
+ return !m_depth;
+ }
};
template <class Cursor>
inline root_tracking_cursor<Cursor> make_root_tracking_cursor(Cursor c)
{
- return root_tracking_cursor<Cursor>(c);
+ return root_tracking_cursor<Cursor>(c);
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/searcher.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/searcher.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/searcher.hpp 2008-09-17 17:09:08 EDT (Wed, 17 Sep 2008)
@@ -45,11 +45,11 @@
* Note that this declaration is empty;
* there are two specializations, one for each of the two possible values of the
* %Multi template argument:
- * - true for a
+ * - true for a
* \link http://www.sgi.com/tech/stl/MultipleSortedAssociativeContainer.html
* Multiple Sorted Associative Container \endlink , i.e. one that allows
* multiple values to share the same key
- * - false for a
+ * - false for a
* \link http://www.sgi.com/tech/stl/UniqueSortedAssociativeContainer.html
* Unique Sorted Associative Container \endlink , allowing only one value for
* each key.
@@ -57,10 +57,10 @@
* These specializations are necessary as their interfaces differ.
*/
template <bool Multi, class Container,
- class Extract =
- boost::multi_index::identity<typename Container::value_type>,
- class Compare = std::less<typename Extract::result_type>
- >
+ class Extract =
+ boost::multi_index::identity<typename Container::value_type>,
+ class Compare = std::less<typename Extract::result_type>
+ >
class searcher;
//derive both specializations from common base modelling only
@@ -78,226 +78,226 @@
template <class Container, class Extract, class Compare>
class searcher<false, Container, Extract, Compare> {
- typedef searcher<false, Container, Extract, Compare> self_type;
+ typedef searcher<false, Container, Extract, Compare> self_type;
public:
- typedef Container container_type; // type name as in STL sequence adaptors
-
- typedef typename container_type::iterator iterator;
- typedef typename container_type::const_iterator const_iterator;
-
- typedef typename container_type::value_type value_type;
- typedef typename container_type::size_type size_type;
+ typedef Container container_type; // type name as in STL sequence adaptors
+
+ typedef typename container_type::iterator iterator;
+ typedef typename container_type::const_iterator const_iterator;
+
+ typedef typename container_type::value_type value_type;
+ typedef typename container_type::size_type size_type;
- typedef Extract key_extract;
- typedef typename key_extract::result_type key_type;
- typedef Compare key_compare;
-
- searcher(key_extract const& extract = key_extract(),
- key_compare const& compare = key_compare(),
- container_type const& sortable = container_type())
- : c(sortable), comp(compare), ext(extract) { }
-
- /**
- * Returns a read/write ("mutable") iterator to first value in the
- * %searcher. Iteration is done in ascending order as dictated by comparing
- * the keys (extracted from the values via %extract) using %cmp.
- */
- iterator begin()
- {
- return c.begin();
- }
-
- /**
- * Returns a read-only const_iterator to the first value in the %searcher.
- * Iteration is done in ascending order as dictated by comparing the keys
- * (extracted from the values via %extract) using %cmp.
- */
- const_iterator begin() const
- {
- return cbegin();
- }
-
- /**
- * Returns a read-only const_iterator to the first value in the %searcher.
- * Iteration is done in ascending order as dictated by comparing the keys
- * (extracted from the values via %extract) using %cmp.
- */
- const_iterator cbegin() const
- {
- return c.cbegin();
- }
-
- /**
- * Returns a read/write ("mutable") iterator to the position one past the
- * last value in the %searcher. Iteration is done in ascending order as
- * dictated by comparing the keys (extracted from the values via
- * %extract) using %cmp.
- */
- iterator end()
- {
- return c.end();
- }
-
- /**
- * Returns a read-only const_iterator to the position one past the last
- * value in the %searcher. Iteration is done in ascending order as dictated
- * by comparing the keys (extracted from the values via
- * %extract) using %cmp.
- */
- const_iterator end() const
- {
- return cend();
- }
-
- /**
- * Returns a read-only const_iterator to the position one past the last
- * value in the %searcher. Iteration is done in ascending order as dictated
- * by comparing the keys (extracted from the values via
- * %extract) using %cmp.
- */
- const_iterator cend() const
- {
- return c.cend();
- }
-
- /**
- * @brief Finds the first position in the searcher in which @a val
- * could be inserted without changing the ordering, using comp
- * for comparisons.
- * @param k The search term
- * @return An iterator pointing to the first element not less than
- * @a k, or end() if every element in the searcher is less than
- * @a k.
- */
- iterator lower_bound(key_type const& k)
- {
- return c.lower_bound(k, bind<bool>(comp, bind(ext(), _1), _2));
- }
-
- /**
- * @brief Finds the first position in the searcher in which @a val
- * could be inserted without changing the ordering, using comp
- * for comparisons.
- * @param k The search term
- * @return A const_iterator pointing to the first element not less than
- * @a k, or end() if every element in the searcher is less than
- * @a k.
- */
- const_iterator lower_bound(key_type const& k) const
- {
- return c.lower_bound(k, bind<bool>(comp, bind(ext(), _1), _2));
- }
-
- /**
- * @brief Finds the last position in the searcher in which @a val
- * could be inserted without changing the ordering, using comp
- * for comparisons.
- * @param k The search term
- * @return An iterator pointing to the first element greater than
- * @a k, or end() if no element in the searcher is greater than
- * @a k.
- */
- iterator upper_bound(key_type const& k)
- {
- return c.upper_bound(k, bind<bool>(comp, bind(ext(), _1), _2));
- }
-
- /**
- * @brief Finds the last position in the searcher in which @a val
- * could be inserted without changing the ordering, using comp
- * for comparisons.
- * @param k The search term
- * @return A const_iterator pointing to the first element greater than
- * @a k, or end() if no element in the searcher is greater than
- * @a k.
- */
- const_iterator upper_bound(key_type const& k) const
- {
- return c.upper_bound(k, bind<bool>(comp, bind(ext(), _1), _2));
- }
-
- /**
- * @brief Attempts to insert @a val into the %searcher
- * @param val Value to be inserted
- * @return A pair, whose
- * - second member is a bool that is true iff the
- * insertion was successful (which is only the case if there
- * was no element with the same key as @a val before the
- * attempted insertion)
- * - and whose first member is an iterator indicating the
- * position where @val was inserted (if the second pair member
- * is true) or the element's position whose key part is equal
- * to @a val's (if the second pair member is false)
- */
- std::pair<iterator, bool> insert(value_type const& val)
- {
- //TODO
- iterator it = c.lower_bound(ext(val), bind<bool>(comp,
- bind<typename key_extract::result_type>(ext, _1), _2));
- if (it == c.end())
- return std::make_pair(it, false);
- return std::make_pair(c.insert(it, val), true);
- }
-
-
- /**
- * @brief Attempts to insert @a val into the %searcher
- * @param pos An iterator that serves as a hint to indicate the position
- * in front of which @a val must be inserted so the %searcher's
- * order (determined by the key part of @a val) is kept.
- * @param val Value to be inserted
- * @return An iterator pointing to the element whose key is equal to
- * @a val's (may be different from @a val if such an element
- * already existed before the attempted insertion).
- */
- iterator insert (iterator pos, value_type const& val)
- {
- key_type key = ext(val);
-
- if ((pos != c.end()) && comp(key, *pos))
- if (comp(*--pos, key))
- return iterator(c.insert(++pos, val));
-
- //the pos hint was not useful
- return this->insert(val).first;
- }
-
-
- template <class InputIterator>
- void insert (InputIterator a, InputIterator b)
- {
-
- }
-
- /**
- * @brief Erases the value at pos
- * @param pos The iterator pointing to the value to be erased.
- */
- iterator erase (iterator pos)
- {
- return c.erase(pos);
- }
-
- size_type erase (key_type const& k)
- {
- }
-
- void erase (iterator a, iterator b)
- {
- }
-
- void clear()
- {
- c.clear();
- }
-
+ typedef Extract key_extract;
+ typedef typename key_extract::result_type key_type;
+ typedef Compare key_compare;
+
+ searcher(key_extract const& extract = key_extract(),
+ key_compare const& compare = key_compare(),
+ container_type const& sortable = container_type())
+ : c(sortable), comp(compare), ext(extract) { }
+
+ /**
+ * Returns a read/write ("mutable") iterator to first value in the
+ * %searcher. Iteration is done in ascending order as dictated by comparing
+ * the keys (extracted from the values via %extract) using %cmp.
+ */
+ iterator begin()
+ {
+ return c.begin();
+ }
+
+ /**
+ * Returns a read-only const_iterator to the first value in the %searcher.
+ * Iteration is done in ascending order as dictated by comparing the keys
+ * (extracted from the values via %extract) using %cmp.
+ */
+ const_iterator begin() const
+ {
+ return cbegin();
+ }
+
+ /**
+ * Returns a read-only const_iterator to the first value in the %searcher.
+ * Iteration is done in ascending order as dictated by comparing the keys
+ * (extracted from the values via %extract) using %cmp.
+ */
+ const_iterator cbegin() const
+ {
+ return c.cbegin();
+ }
+
+ /**
+ * Returns a read/write ("mutable") iterator to the position one past the
+ * last value in the %searcher. Iteration is done in ascending order as
+ * dictated by comparing the keys (extracted from the values via
+ * %extract) using %cmp.
+ */
+ iterator end()
+ {
+ return c.end();
+ }
+
+ /**
+ * Returns a read-only const_iterator to the position one past the last
+ * value in the %searcher. Iteration is done in ascending order as dictated
+ * by comparing the keys (extracted from the values via
+ * %extract) using %cmp.
+ */
+ const_iterator end() const
+ {
+ return cend();
+ }
+
+ /**
+ * Returns a read-only const_iterator to the position one past the last
+ * value in the %searcher. Iteration is done in ascending order as dictated
+ * by comparing the keys (extracted from the values via
+ * %extract) using %cmp.
+ */
+ const_iterator cend() const
+ {
+ return c.cend();
+ }
+
+ /**
+ * @brief Finds the first position in the searcher in which @a val
+ * could be inserted without changing the ordering, using comp
+ * for comparisons.
+ * @param k The search term
+ * @return An iterator pointing to the first element not less than
+ * @a k, or end() if every element in the searcher is less than
+ * @a k.
+ */
+ iterator lower_bound(key_type const& k)
+ {
+ return c.lower_bound(k, bind<bool>(comp, bind(ext(), _1), _2));
+ }
+
+ /**
+ * @brief Finds the first position in the searcher in which @a val
+ * could be inserted without changing the ordering, using comp
+ * for comparisons.
+ * @param k The search term
+ * @return A const_iterator pointing to the first element not less than
+ * @a k, or end() if every element in the searcher is less than
+ * @a k.
+ */
+ const_iterator lower_bound(key_type const& k) const
+ {
+ return c.lower_bound(k, bind<bool>(comp, bind(ext(), _1), _2));
+ }
+
+ /**
+ * @brief Finds the last position in the searcher in which @a val
+ * could be inserted without changing the ordering, using comp
+ * for comparisons.
+ * @param k The search term
+ * @return An iterator pointing to the first element greater than
+ * @a k, or end() if no element in the searcher is greater than
+ * @a k.
+ */
+ iterator upper_bound(key_type const& k)
+ {
+ return c.upper_bound(k, bind<bool>(comp, bind(ext(), _1), _2));
+ }
+
+ /**
+ * @brief Finds the last position in the searcher in which @a val
+ * could be inserted without changing the ordering, using comp
+ * for comparisons.
+ * @param k The search term
+ * @return A const_iterator pointing to the first element greater than
+ * @a k, or end() if no element in the searcher is greater than
+ * @a k.
+ */
+ const_iterator upper_bound(key_type const& k) const
+ {
+ return c.upper_bound(k, bind<bool>(comp, bind(ext(), _1), _2));
+ }
+
+ /**
+ * @brief Attempts to insert @a val into the %searcher
+ * @param val Value to be inserted
+ * @return A pair, whose
+ * - second member is a bool that is true iff the
+ * insertion was successful (which is only the case if there
+ * was no element with the same key as @a val before the
+ * attempted insertion)
+ * - and whose first member is an iterator indicating the
+ * position where @val was inserted (if the second pair member
+ * is true) or the element's position whose key part is equal
+ * to @a val's (if the second pair member is false)
+ */
+ std::pair<iterator, bool> insert(value_type const& val)
+ {
+ //TODO
+ iterator it = c.lower_bound(ext(val), bind<bool>(comp,
+ bind<typename key_extract::result_type>(ext, _1), _2));
+ if (it == c.end())
+ return std::make_pair(it, false);
+ return std::make_pair(c.insert(it, val), true);
+ }
+
+
+ /**
+ * @brief Attempts to insert @a val into the %searcher
+ * @param pos An iterator that serves as a hint to indicate the position
+ * in front of which @a val must be inserted so the %searcher's
+ * order (determined by the key part of @a val) is kept.
+ * @param val Value to be inserted
+ * @return An iterator pointing to the element whose key is equal to
+ * @a val's (may be different from @a val if such an element
+ * already existed before the attempted insertion).
+ */
+ iterator insert (iterator pos, value_type const& val)
+ {
+ key_type key = ext(val);
+
+ if ((pos != c.end()) && comp(key, *pos))
+ if (comp(*--pos, key))
+ return iterator(c.insert(++pos, val));
+
+ //the pos hint was not useful
+ return this->insert(val).first;
+ }
+
+
+ template <class InputIterator>
+ void insert (InputIterator a, InputIterator b)
+ {
+
+ }
+
+ /**
+ * @brief Erases the value at pos
+ * @param pos The iterator pointing to the value to be erased.
+ */
+ iterator erase (iterator pos)
+ {
+ return c.erase(pos);
+ }
+
+ size_type erase (key_type const& k)
+ {
+ }
+
+ void erase (iterator a, iterator b)
+ {
+ }
+
+ void clear()
+ {
+ c.clear();
+ }
+
// protected. It's a sequence (and hierarchy) adaptor, and the STL ones do the
// same.
protected:
- container_type c;
- key_compare comp;
- key_extract ext;
+ container_type c;
+ key_compare comp;
+ key_extract ext;
};
/* @brief Multiple key %searcher specialization
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