27 D_list_item() : _dli_next(0) {}
29 friend class D_list_item_policy;
31 D_list_item(D_list_item
const &);
32 void operator = (D_list_item
const &);
34 D_list_item *_dli_next, *_dli_prev;
37class D_list_item_policy
40 typedef D_list_item Item;
41 static D_list_item *&prev(D_list_item *e) {
return e->_dli_prev; }
42 static D_list_item *&next(D_list_item *e) {
return e->_dli_next; }
43 static D_list_item *prev(D_list_item
const *e) {
return e->_dli_prev; }
44 static D_list_item *next(D_list_item
const *e) {
return e->_dli_next; }
48struct Sd_list_head_policy
51 static T *head(Head_type h) {
return h; }
52 static void set_head(Head_type &h, T *v) { h = v; }
57 typename C = D_list_item_policy
62 template<
typename VALUE,
typename ITEM >
66 typedef VALUE *Value_type;
67 typedef VALUE *value_type;
71 bool operator == (__Iterator
const &o)
const
72 {
return _c == o._c; }
74 bool operator != (__Iterator
const &o)
const
75 {
return _c != o._c; }
77 __Iterator &operator ++ ()
83 __Iterator &operator -- ()
89 Value_type operator * ()
const {
return static_cast<Value_type
>(_c); }
90 Value_type operator -> ()
const {
return static_cast<Value_type
>(_c); }
93 friend class D_list_cyclic;
95 explicit __Iterator(ITEM *s) : _c(s) {}
101 typedef T *Value_type;
102 typedef T *value_type;
103 typedef __Iterator<T, typename C::Item> Iterator;
104 typedef Iterator Const_iterator;
106 static void remove(T *e)
108 C::next(C::prev(e)) = C::next(e);
109 C::prev(C::next(e)) = C::prev(e);
113 static Iterator erase(Iterator
const &e)
115 typename C::Item *n = C::next(*e);
120 static Iterator iter(T
const *e) {
return Iterator(
const_cast<T*
>(e)); }
122 static bool in_list(T
const *e) {
return C::next(
const_cast<T*
>(e)); }
123 static bool has_sibling(T
const *e) {
return C::next(
const_cast<T*
>(e)) != e; }
125 static Iterator insert_after(T *e, Iterator
const &pos)
128 C::next(e) = C::next(*pos);
129 C::prev(C::next(*pos)) = e;
134 static Iterator insert_before(T *e, Iterator
const &pos)
137 C::prev(e) = C::prev(*pos);
138 C::next(C::prev(*pos)) = e;
143 static T *self_insert(T *e)
144 { C::next(e) = C::prev(e) = e;
return e; }
146 static void remove_last(T *e)
150 static Iterator __iter(
typename C::Item *e) {
return Iterator(e); }
155 typename C = D_list_item_policy,
156 typename H = Sd_list_head_policy<T>,
159class Sd_list :
public D_list_cyclic<T, C>
162 typedef D_list_cyclic<T, C> Base;
165 typedef typename Base::Iterator Iterator;
169 Sd_list() {
if (!BSS) H::set_head(_f, 0); }
171 bool empty()
const {
return !H::head(_f); }
172 T *front()
const {
return H::head(_f); }
179 Base::remove_last(e);
184 if (e == H::head(_f))
185 H::set_head(_f,
static_cast<T*
>(C::next(h)));
190 Iterator erase(Iterator
const &e)
192 typename C::Item *n = C::next(*e);
197 void push(T *e, Pos pos)
201 H::set_head(_f, Base::self_insert(e));
204 Base::insert_before(e, this->iter(h));
210 void push_back(T *e) { push(e, Back); }
211 void push_front(T *e) { push(e, Front); }
212 void rotate_to(T *h) { H::set_head(_f, h); }
214 typename H::Head_type
const &head()
const {
return _f; }
215 typename H::Head_type &head() {
return _f; }
218 Sd_list(Sd_list
const &);
219 void operator = (Sd_list
const &);
221 typename H::Head_type _f;
226 typename C = D_list_item_policy,
229class D_list :
public D_list_cyclic<T, C>
232 typedef D_list_cyclic<T, C> Base;
233 typedef typename C::Item Internal_type;
239 typedef typename Base::Iterator Iterator;
240 typedef typename Base::Const_iterator Const_iterator;
241 typedef T* value_type;
242 typedef T* Value_type;
244 D_list() { this->self_insert(
static_cast<T*
>(&_h)); }
246 bool empty()
const {
return C::next(
static_cast<T
const *
>(&_h)) == &_h; }
248 static void remove(T *e) { Base::remove(e); }
249 Iterator erase(Iterator
const &e) {
return Base::erase(e); }
251 void push(T *e, Pos pos)
254 Base::insert_after(e, end());
256 Base::insert_before(e, end());
259 void push_back(T *e) { push(e, Back); }
260 void push_front(T *e) { push(e, Front); }
262 Iterator begin()
const {
return this->__iter(C::next(
const_cast<Internal_type *
>(&_h))); }
263 Iterator end()
const {
return this->__iter(
const_cast<Internal_type *
>(&_h)); }
266 D_list(D_list
const &);
267 void operator = (D_list
const &);