4 /*****************************************************************************\
7 * Author : Chris Koeritz *
9 *******************************************************************************
10 * Copyright (c) 1998-$now By Author. This program is free software; you can *
11 * redistribute it and/or modify it under the terms of the GNU General Public *
12 * License as published by the Free Software Foundation; either version 2 of *
13 * the License or (at your option) any later version. This is online at: *
14 * http://www.fsf.org/copyleft/gpl.html *
15 * Please send any updates to: fred@gruntose.com *
16 \*****************************************************************************/
20 // the cursor should never be stored to or deleted; it is merely a scanner that
21 // runs through the list.
23 // the cursor can point at the head or tail. any storage action is taken to
24 // mean that it applies to the closest real object, if one exists. any query
25 // action is taken similarly.
30 #include <basis/functions.h>
34 // nice names for the positions of the next link and the previous link in
35 // our node's indices.
36 const int PREVIOUS = 0;
41 // iterator functions:
43 void list::iterator::operator ++()
45 if (is_tail()) return; // already at the end.
46 _cursor = _cursor->get_link(NEXT);
49 void list::iterator::operator --()
51 if (is_head()) return; // already at the front.
52 _cursor = _cursor->get_link(PREVIOUS);
55 bool list::iterator::operator ==(const iterator &to_compare) const
56 { return _cursor == to_compare._cursor; }
58 const node *list::iterator::observe()
60 if (!_manager || _manager->empty()) return NIL;
61 if (*this == _manager->head()) next();
62 if (*this == _manager->tail()) previous();
66 node *list::iterator::access()
68 if (!_manager || _manager->empty()) return NIL;
69 if (*this == _manager->head()) next();
70 if (*this == _manager->tail()) previous();
74 bool list::iterator::is_head() const
76 if (!_manager) return false;
77 return _cursor == _manager->_head;
80 bool list::iterator::is_tail() const
82 if (!_manager) return false;
83 return _cursor == _manager->_tail;
86 void list::iterator::jump_head()
88 if (!_manager) return;
89 _cursor = _manager->_head;
92 void list::iterator::jump_tail()
94 if (!_manager) return;
95 _cursor = _manager->_tail;
101 : _head(NIL), _tail(NIL)
105 _head->set_link(NEXT, _tail);
106 _tail->set_link(PREVIOUS, _head);
111 iterator zapper = head();
118 bool list::empty() const
120 if (_head->get_link(NEXT) == _tail) return true;
124 bool list::set_index(iterator &where, int new_index)
126 if (where._manager != this) return false;
127 if (empty()) return false;
128 node *skipper = _head->get_link(NEXT);
129 for (int i = 0; i < new_index; i++) {
130 skipper = skipper->get_link(NEXT);
131 if (skipper == _tail) return false; // out of bounds now.
133 where._cursor = skipper;
137 bool list::forward(iterator &where, int count)
139 if (where._manager != this) return false;
140 if (count <= 0) return true;
141 if (items_from_tail(where) < count) return false;
142 if (where.is_head()) where.next(); // skip the head guard.
143 for (int i = 0; i < count; i++) where.next();
147 bool list::backward(iterator &where, int count)
149 if (where._manager != this) return false;
150 if (count <= 0) return true;
151 if (items_from_head(where) < count) return false;
152 if (where.is_tail()) where.previous(); // skip the tail guard.
153 for (int i = 0; i < count; i++) where.previous();
157 int list::elements() const
159 if (empty()) return 0;
161 node *skipper = _head->get_link(NEXT);
162 while (skipper != _tail) {
164 skipper = skipper->get_link(NEXT);
169 int list::items_from_head(const iterator &where) const
171 if (where._manager != this) return 0;
172 if (where.is_head()) return 0; // make sure it's not there already.
174 node *skipper = _head->get_link(NEXT);
175 while ( (where._cursor != skipper) && (skipper != _tail) ) {
177 skipper = skipper->get_link(NEXT);
182 int list::items_from_tail(const iterator &where) const
184 if (where._manager != this) return 0;
185 if (where.is_tail()) return 0; // make sure it's not there already.
187 node *skipper = _tail->get_link(PREVIOUS);
188 while ( (where._cursor != skipper) && (skipper != _head) ) {
190 skipper = skipper->get_link(PREVIOUS);
198 if (empty()) return NIL; // make sure the list isn't empty.
199 if (_cursor == _head) return _head->get_link(NEXT);
200 // check special case for pointing at the head.
201 if (_cursor == _tail) return _tail->get_link(PREVIOUS);
202 // check special case for pointing at the tail.
207 node *list::remove(iterator &where)
209 if (where._manager != this) return NIL;
210 if (empty()) return NIL;
211 if (where._cursor == _head)
212 where._cursor = _head->get_link(NEXT);
213 if (where._cursor == _tail)
214 where._cursor = _tail->get_link(PREVIOUS);
215 node *old_cursor = where._cursor;
216 node *old_previous = old_cursor->get_link(PREVIOUS);
217 node *old_next = old_cursor->get_link(NEXT);
218 old_cursor->set_link(PREVIOUS, NIL);
219 old_cursor->set_link(NEXT, NIL);
220 old_previous->set_link(NEXT, old_next);
221 old_next->set_link(PREVIOUS, old_previous);
222 where._cursor = old_next;
226 void list::zap(iterator &where) { delete remove(where); }
228 void list::append(iterator &where, node *new_node)
230 if (where._manager != this) return;
231 while (new_node->links() < 2) new_node->insert_link(0, NIL);
232 if (empty()) where._cursor = _head;
233 if (where._cursor == _tail)
234 where._cursor = _tail->get_link(PREVIOUS);
235 // shift from the tail sentinel to the tail element.
236 node *save_next = where._cursor->get_link(NEXT);
237 where._cursor->set_link(NEXT, new_node);
238 new_node->set_link(PREVIOUS, where._cursor);
239 new_node->set_link(NEXT, save_next);
240 save_next->set_link(PREVIOUS, new_node);
241 where._cursor = new_node;
244 void list::insert(iterator &where, node *new_node)
246 if (where._manager != this) return;
247 while (new_node->links() < 2) new_node->insert_link(0, NIL);
248 if (empty()) where._cursor = _tail;
249 if (where._cursor == _head)
250 where._cursor = _head->get_link(NEXT);
251 // shift from head sentinel to the head element.
252 node *save_prior = where._cursor->get_link(PREVIOUS);
253 where._cursor->set_link(PREVIOUS, new_node);
254 new_node->set_link(NEXT, where._cursor);
255 new_node->set_link(PREVIOUS, save_prior);
256 save_prior->set_link(NEXT, new_node);
257 where._cursor = new_node;
262 iterator zapper = head();
263 while (!empty()) zap(zapper);