Chris@16: //======================================================================= Chris@16: // Copyright 2002 Indiana University. Chris@16: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek Chris@16: // Chris@16: // Distributed under the Boost Software License, Version 1.0. (See Chris@16: // accompanying file LICENSE_1_0.txt or copy at Chris@16: // http://www.boost.org/LICENSE_1_0.txt) Chris@16: //======================================================================= Chris@16: Chris@16: #ifndef BOOST_LIST_BASE_HPP Chris@16: #define BOOST_LIST_BASE_HPP Chris@16: Chris@16: #include Chris@16: Chris@16: // Perhaps this should go through formal review, and move to . Chris@16: Chris@16: /* Chris@16: An alternate interface idea: Chris@16: Extend the std::list functionality by creating remove/insert Chris@16: functions that do not require the container object! Chris@16: */ Chris@16: Chris@16: namespace boost { Chris@16: namespace detail { Chris@16: Chris@16: //========================================================================= Chris@16: // Linked-List Generic Implementation Functions Chris@16: Chris@16: template Chris@16: inline Node Chris@16: slist_insert_after(Node pos, Node x, Chris@16: Next next) Chris@16: { Chris@16: next(x) = next(pos); Chris@16: next(pos) = x; Chris@16: return x; Chris@16: } Chris@16: Chris@16: // return next(pos) or next(next(pos)) ? Chris@16: template Chris@16: inline Node Chris@16: slist_remove_after(Node pos, Chris@16: Next next) Chris@16: { Chris@16: Node n = next(pos); Chris@16: next(pos) = next(n); Chris@16: return n; Chris@16: } Chris@16: Chris@16: template Chris@16: inline Node Chris@16: slist_remove_range(Node before_first, Node last, Chris@16: Next next) Chris@16: { Chris@16: next(before_first) = last; Chris@16: return last; Chris@16: } Chris@16: Chris@16: template Chris@16: inline Node Chris@16: slist_previous(Node head, Node x, Node nil, Chris@16: Next next) Chris@16: { Chris@16: while (head != nil && next(head) != x) Chris@16: head = next(head); Chris@16: return head; Chris@16: } Chris@16: Chris@16: template Chris@16: inline void Chris@16: slist_splice_after(Node pos, Node before_first, Node before_last, Chris@16: Next next) Chris@16: { Chris@16: if (pos != before_first && pos != before_last) { Chris@16: Node first = next(before_first); Chris@16: Node after = next(pos); Chris@16: next(before_first) = next(before_last); Chris@16: next(pos) = first; Chris@16: next(before_last) = after; Chris@16: } Chris@16: } Chris@16: Chris@16: template Chris@16: inline Node Chris@16: slist_reverse(Node node, Node nil, Chris@16: Next next) Chris@16: { Chris@16: Node result = node; Chris@16: node = next(node); Chris@16: next(result) = nil; Chris@16: while(node) { Chris@16: Node next = next(node); Chris@16: next(node) = result; Chris@16: result = node; Chris@16: node = next; Chris@16: } Chris@16: return result; Chris@16: } Chris@16: Chris@16: template Chris@16: inline std::size_t Chris@16: slist_size(Node head, Node nil, Chris@16: Next next) Chris@16: { Chris@16: std::size_t s = 0; Chris@16: for ( ; head != nil; head = next(head)) Chris@16: ++s; Chris@16: return s; Chris@16: } Chris@16: Chris@16: template Chris@16: class slist_iterator_policies Chris@16: { Chris@16: public: Chris@16: explicit slist_iterator_policies(const Next& n, const Data& d) Chris@16: : m_next(n), m_data(d) { } Chris@16: Chris@16: template Chris@16: Reference dereference(type, const Node& x) const Chris@16: { return m_data(x); } Chris@16: Chris@16: template Chris@16: void increment(Node& x) const Chris@16: { x = m_next(x); } Chris@16: Chris@16: template Chris@16: bool equal(Node& x, Node& y) const Chris@16: { return x == y; } Chris@16: Chris@16: protected: Chris@16: Next m_next; Chris@16: Data m_data; Chris@16: }; Chris@16: Chris@16: //=========================================================================== Chris@16: // Doubly-Linked List Generic Implementation Functions Chris@16: Chris@16: template Chris@16: inline void Chris@16: dlist_insert_before(Node pos, Node x, Chris@16: Next next, Prev prev) Chris@16: { Chris@16: next(x) = pos; Chris@16: prev(x) = prev(pos); Chris@16: next(prev(pos)) = x; Chris@16: prev(pos) = x; Chris@16: } Chris@16: Chris@16: template Chris@16: void Chris@16: dlist_remove(Node pos, Chris@16: Next next, Prev prev) Chris@16: { Chris@16: Node next_node = next(pos); Chris@16: Node prev_node = prev(pos); Chris@16: next(prev_node) = next_node; Chris@16: prev(next_node) = prev_node; Chris@16: } Chris@16: Chris@16: // This deletes every node in the list except the Chris@16: // sentinel node. Chris@16: template Chris@16: inline void Chris@16: dlist_clear(Node sentinel, Delete del) Chris@16: { Chris@16: Node i, tmp; Chris@16: i = next(sentinel); Chris@16: while (i != sentinel) { Chris@16: tmp = i; Chris@16: i = next(i); Chris@16: del(tmp); Chris@16: } Chris@16: } Chris@16: Chris@16: template Chris@16: inline bool Chris@16: dlist_empty(Node dummy) Chris@16: { Chris@16: return next(dummy) == dummy; Chris@16: } Chris@16: Chris@16: template Chris@16: void Chris@16: dlist_transfer(Node pos, Node first, Node last, Chris@16: Next next, Prev prev) Chris@16: { Chris@16: if (pos != last) { Chris@16: // Remove [first,last) from its old position Chris@16: next(prev(last)) = pos; Chris@16: next(prev(first)) = last; Chris@16: next(prev(pos)) = first; Chris@16: Chris@16: // Splice [first,last) into its new position Chris@16: Node tmp = prev(pos); Chris@16: prev(pos) = prev(last); Chris@16: prev(last) = prev(first); Chris@16: prev(first) = tmp; Chris@16: } Chris@16: } Chris@16: Chris@16: template Chris@16: class dlist_iterator_policies Chris@16: : public slist_iterator_policies Chris@16: { Chris@16: typedef slist_iterator_policies Base; Chris@16: public: Chris@16: template Chris@16: void decrement(Node& x) const Chris@16: { x = m_prev(x); } Chris@16: Chris@16: dlist_iterator_policies(Next n, Prev p, Data d) Chris@16: : Base(n,d), m_prev(p) { } Chris@16: protected: Chris@16: Prev m_prev; Chris@16: }; Chris@16: Chris@16: } // namespace detail Chris@16: } // namespace boost Chris@16: Chris@16: #endif // BOOST_LIST_BASE_HPP