1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/detail/list_base.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,220 @@
1.4 +//=======================================================================
1.5 +// Copyright 2002 Indiana University.
1.6 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
1.7 +//
1.8 +// Distributed under the Boost Software License, Version 1.0. (See
1.9 +// accompanying file LICENSE_1_0.txt or copy at
1.10 +// http://www.boost.org/LICENSE_1_0.txt)
1.11 +//=======================================================================
1.12 +
1.13 +#ifndef BOOST_LIST_BASE_HPP
1.14 +#define BOOST_LIST_BASE_HPP
1.15 +
1.16 +#include <boost/iterator_adaptors.hpp>
1.17 +
1.18 +// Perhaps this should go through formal review, and move to <boost/>.
1.19 +
1.20 +/*
1.21 + An alternate interface idea:
1.22 + Extend the std::list functionality by creating remove/insert
1.23 + functions that do not require the container object!
1.24 + */
1.25 +
1.26 +namespace boost {
1.27 + namespace detail {
1.28 +
1.29 + //=========================================================================
1.30 + // Linked-List Generic Implementation Functions
1.31 +
1.32 + template <class Node, class Next>
1.33 + inline Node
1.34 + slist_insert_after(Node pos, Node x,
1.35 + Next next)
1.36 + {
1.37 + next(x) = next(pos);
1.38 + next(pos) = x;
1.39 + return x;
1.40 + }
1.41 +
1.42 + // return next(pos) or next(next(pos)) ?
1.43 + template <class Node, class Next>
1.44 + inline Node
1.45 + slist_remove_after(Node pos,
1.46 + Next next)
1.47 + {
1.48 + Node n = next(pos);
1.49 + next(pos) = next(n);
1.50 + return n;
1.51 + }
1.52 +
1.53 + template <class Node, class Next>
1.54 + inline Node
1.55 + slist_remove_range(Node before_first, Node last,
1.56 + Next next)
1.57 + {
1.58 + next(before_first) = last;
1.59 + return last;
1.60 + }
1.61 +
1.62 + template <class Node, class Next>
1.63 + inline Node
1.64 + slist_previous(Node head, Node x, Node nil,
1.65 + Next next)
1.66 + {
1.67 + while (head != nil && next(head) != x)
1.68 + head = next(head);
1.69 + return head;
1.70 + }
1.71 +
1.72 + template<class Node, class Next>
1.73 + inline void
1.74 + slist_splice_after(Node pos, Node before_first, Node before_last,
1.75 + Next next)
1.76 + {
1.77 + if (pos != before_first && pos != before_last) {
1.78 + Node first = next(before_first);
1.79 + Node after = next(pos);
1.80 + next(before_first) = next(before_last);
1.81 + next(pos) = first;
1.82 + next(before_last) = after;
1.83 + }
1.84 + }
1.85 +
1.86 + template <class Node, class Next>
1.87 + inline Node
1.88 + slist_reverse(Node node, Node nil,
1.89 + Next next)
1.90 + {
1.91 + Node result = node;
1.92 + node = next(node);
1.93 + next(result) = nil;
1.94 + while(node) {
1.95 + Node next = next(node);
1.96 + next(node) = result;
1.97 + result = node;
1.98 + node = next;
1.99 + }
1.100 + return result;
1.101 + }
1.102 +
1.103 + template <class Node, class Next>
1.104 + inline std::size_t
1.105 + slist_size(Node head, Node nil,
1.106 + Next next)
1.107 + {
1.108 + std::size_t s = 0;
1.109 + for ( ; head != nil; head = next(head))
1.110 + ++s;
1.111 + return s;
1.112 + }
1.113 +
1.114 + template <class Next, class Data>
1.115 + class slist_iterator_policies
1.116 + {
1.117 + public:
1.118 + explicit slist_iterator_policies(const Next& n, const Data& d)
1.119 + : m_next(n), m_data(d) { }
1.120 +
1.121 + template <class Reference, class Node>
1.122 + Reference dereference(type<Reference>, const Node& x) const
1.123 + { return m_data(x); }
1.124 +
1.125 + template <class Node>
1.126 + void increment(Node& x) const
1.127 + { x = m_next(x); }
1.128 +
1.129 + template <class Node>
1.130 + bool equal(Node& x, Node& y) const
1.131 + { return x == y; }
1.132 +
1.133 + protected:
1.134 + Next m_next;
1.135 + Data m_data;
1.136 + };
1.137 +
1.138 + //===========================================================================
1.139 + // Doubly-Linked List Generic Implementation Functions
1.140 +
1.141 + template <class Node, class Next, class Prev>
1.142 + inline void
1.143 + dlist_insert_before(Node pos, Node x,
1.144 + Next next, Prev prev)
1.145 + {
1.146 + next(x) = pos;
1.147 + prev(x) = prev(pos);
1.148 + next(prev(pos)) = x;
1.149 + prev(pos) = x;
1.150 + }
1.151 +
1.152 + template <class Node, class Next, class Prev>
1.153 + void
1.154 + dlist_remove(Node pos,
1.155 + Next next, Prev prev)
1.156 + {
1.157 + Node next_node = next(pos);
1.158 + Node prev_node = prev(pos);
1.159 + next(prev_node) = next_node;
1.160 + prev(next_node) = prev_node;
1.161 + }
1.162 +
1.163 + // This deletes every node in the list except the
1.164 + // sentinel node.
1.165 + template <class Node, class Delete>
1.166 + inline void
1.167 + dlist_clear(Node sentinel, Delete del)
1.168 + {
1.169 + Node i, tmp;
1.170 + i = next(sentinel);
1.171 + while (i != sentinel) {
1.172 + tmp = i;
1.173 + i = next(i);
1.174 + del(tmp);
1.175 + }
1.176 + }
1.177 +
1.178 + template <class Node>
1.179 + inline bool
1.180 + dlist_empty(Node dummy)
1.181 + {
1.182 + return next(dummy) == dummy;
1.183 + }
1.184 +
1.185 + template <class Node, class Next, class Prev>
1.186 + void
1.187 + dlist_transfer(Node pos, Node first, Node last,
1.188 + Next next, Prev prev)
1.189 + {
1.190 + if (pos != last) {
1.191 + // Remove [first,last) from its old position
1.192 + next(prev(last)) = pos;
1.193 + next(prev(first)) = last;
1.194 + next(prev(pos)) = first;
1.195 +
1.196 + // Splice [first,last) into its new position
1.197 + Node tmp = prev(pos);
1.198 + prev(pos) = prev(last);
1.199 + prev(last) = prev(first);
1.200 + prev(first) = tmp;
1.201 + }
1.202 + }
1.203 +
1.204 + template <class Next, class Prev, class Data>
1.205 + class dlist_iterator_policies
1.206 + : public slist_iterator_policies<Next, Data>
1.207 + {
1.208 + typedef slist_iterator_policies<Next, Data> Base;
1.209 + public:
1.210 + template <class Node>
1.211 + void decrement(Node& x) const
1.212 + { x = m_prev(x); }
1.213 +
1.214 + dlist_iterator_policies(Next n, Prev p, Data d)
1.215 + : Base(n,d), m_prev(p) { }
1.216 + protected:
1.217 + Prev m_prev;
1.218 + };
1.219 +
1.220 + } // namespace detail
1.221 +} // namespace boost
1.222 +
1.223 +#endif // BOOST_LIST_BASE_HPP