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