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