3 * Name : doubly_linked_list
4 * Author : Chris Koeritz
6 * Copyright (c) 1998-$now By Author. This program is free software; you can
7 * redistribute it and/or modify it under the terms of the GNU General Public
8 * License as published by the Free Software Foundation; either version 2 of
9 * the License or (at your option) any later version. This is online at:
10 * http://www.fsf.org/copyleft/gpl.html
11 * Please send any updates to: fred@gruntose.com
17 * + the cursor should never be stored to or deleted; it is merely a scanner that runs through the list.
18 * + the cursor can point at the head or tail. any storage action is taken to mean that it applies to the closest real object, if one exists. any query action is taken similarly.
21 #include "doubly_linked_list.h"
25 #include <basis/functions.h>
29 // nice names for the positions of the next link and the previous link in
30 // our node's indices.
31 const int PREVIOUS = 0;
36 // iterator functions:
38 void doubly_linked_list::iterator::operator ++()
40 if (is_tail()) return; // already at the end.
41 _cursor = _cursor->get_link(NEXT);
44 void doubly_linked_list::iterator::operator --()
46 if (is_head()) return; // already at the front.
47 _cursor = _cursor->get_link(PREVIOUS);
50 bool doubly_linked_list::iterator::operator ==(const iterator &to_compare) const
51 { return _cursor == to_compare._cursor; }
53 const node *doubly_linked_list::iterator::observe()
55 if (!_manager || _manager->empty()) return NULL_POINTER;
56 if (*this == _manager->head()) next();
57 if (*this == _manager->tail()) previous();
61 node *doubly_linked_list::iterator::access()
63 if (!_manager || _manager->empty()) return NULL_POINTER;
64 if (*this == _manager->head()) next();
65 if (*this == _manager->tail()) previous();
69 bool doubly_linked_list::iterator::is_head() const
71 if (!_manager) return false;
72 return _cursor == _manager->_head;
75 bool doubly_linked_list::iterator::is_tail() const
77 if (!_manager) return false;
78 return _cursor == _manager->_tail;
81 void doubly_linked_list::iterator::jump_head()
83 if (!_manager) return;
84 _cursor = _manager->_head;
87 void doubly_linked_list::iterator::jump_tail()
89 if (!_manager) return;
90 _cursor = _manager->_tail;
95 doubly_linked_list::doubly_linked_list()
96 : _head(NULL_POINTER), _tail(NULL_POINTER)
100 _head->set_link(NEXT, _tail);
101 _tail->set_link(PREVIOUS, _head);
104 doubly_linked_list::~doubly_linked_list()
106 iterator zapper = head();
113 bool doubly_linked_list::empty() const
115 if (_head->get_link(NEXT) == _tail) return true;
119 bool doubly_linked_list::set_index(iterator &where, int new_index)
121 if (where._manager != this) return false;
122 if (empty()) return false;
123 node *skipper = _head->get_link(NEXT);
124 for (int i = 0; i < new_index; i++) {
125 skipper = skipper->get_link(NEXT);
126 if (skipper == _tail) return false; // out of bounds now.
128 where._cursor = skipper;
132 bool doubly_linked_list::forward(iterator &where, int count)
134 if (where._manager != this) return false;
135 if (count <= 0) return true;
136 if (items_from_tail(where) < count) return false;
137 if (where.is_head()) where.next(); // skip the head guard.
138 for (int i = 0; i < count; i++) where.next();
142 bool doubly_linked_list::backward(iterator &where, int count)
144 if (where._manager != this) return false;
145 if (count <= 0) return true;
146 if (items_from_head(where) < count) return false;
147 if (where.is_tail()) where.previous(); // skip the tail guard.
148 for (int i = 0; i < count; i++) where.previous();
152 int doubly_linked_list::elements() const
154 if (empty()) return 0;
156 node *skipper = _head->get_link(NEXT);
157 while (skipper != _tail) {
159 skipper = skipper->get_link(NEXT);
164 int doubly_linked_list::items_from_head(const iterator &where) const
166 if (where._manager != this) return 0;
167 if (where.is_head()) return 0; // make sure it's not there already.
169 node *skipper = _head->get_link(NEXT);
170 while ( (where._cursor != skipper) && (skipper != _tail) ) {
172 skipper = skipper->get_link(NEXT);
177 int doubly_linked_list::items_from_tail(const iterator &where) const
179 if (where._manager != this) return 0;
180 if (where.is_tail()) return 0; // make sure it's not there already.
182 node *skipper = _tail->get_link(PREVIOUS);
183 while ( (where._cursor != skipper) && (skipper != _head) ) {
185 skipper = skipper->get_link(PREVIOUS);
193 if (empty()) return NULL_POINTER; // make sure the list isn't empty.
194 if (_cursor == _head) return _head->get_link(NEXT);
195 // check special case for pointing at the head.
196 if (_cursor == _tail) return _tail->get_link(PREVIOUS);
197 // check special case for pointing at the tail.
202 node *doubly_linked_list::remove(iterator &where)
204 if (where._manager != this) return NULL_POINTER;
205 if (empty()) return NULL_POINTER;
206 if (where._cursor == _head)
207 where._cursor = _head->get_link(NEXT);
208 if (where._cursor == _tail)
209 where._cursor = _tail->get_link(PREVIOUS);
210 node *old_cursor = where._cursor;
211 node *old_previous = old_cursor->get_link(PREVIOUS);
212 node *old_next = old_cursor->get_link(NEXT);
213 old_cursor->set_link(PREVIOUS, NULL_POINTER);
214 old_cursor->set_link(NEXT, NULL_POINTER);
215 old_previous->set_link(NEXT, old_next);
216 old_next->set_link(PREVIOUS, old_previous);
217 where._cursor = old_next;
221 void doubly_linked_list::zap(iterator &where) { delete remove(where); }
223 void doubly_linked_list::append(iterator &where, node *new_node)
225 if (where._manager != this) return;
226 while (new_node->links() < 2) new_node->insert_link(0, NULL_POINTER);
227 if (empty()) where._cursor = _head;
228 if (where._cursor == _tail)
229 where._cursor = _tail->get_link(PREVIOUS);
230 // shift from the tail sentinel to the tail element.
231 node *save_next = where._cursor->get_link(NEXT);
232 where._cursor->set_link(NEXT, new_node);
233 new_node->set_link(PREVIOUS, where._cursor);
234 new_node->set_link(NEXT, save_next);
235 save_next->set_link(PREVIOUS, new_node);
236 where._cursor = new_node;
239 void doubly_linked_list::insert(iterator &where, node *new_node)
241 if (where._manager != this) return;
242 while (new_node->links() < 2) new_node->insert_link(0, NULL_POINTER);
243 if (empty()) where._cursor = _tail;
244 if (where._cursor == _head)
245 where._cursor = _head->get_link(NEXT);
246 // shift from head sentinel to the head element.
247 node *save_prior = where._cursor->get_link(PREVIOUS);
248 where._cursor->set_link(PREVIOUS, new_node);
249 new_node->set_link(NEXT, where._cursor);
250 new_node->set_link(PREVIOUS, save_prior);
251 save_prior->set_link(NEXT, new_node);
252 where._cursor = new_node;
255 void doubly_linked_list::zap_all()
257 iterator zapper = head();
258 while (!empty()) zap(zapper);