nucleus/library/nodes/doubly_linked_list.cpp

   1 /*
   2 *
   3 *  Name   : doubly_linked_list
   4 *  Author : Chris Koeritz
   5 **
   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
  12 */
  13
  14 /*
  15  * POLICIES:
  16  *
  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.
  19  */
  20
  21 #include "doubly_linked_list.h"
  22
  23 #include "node.h"
  24
  25 #include <basis/functions.h>
  26
  27 namespace nodes {
  28
  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;
  32 const int NEXT = 1;
  33
  34 //////////////
  35
  36 // iterator functions:
  37
  38 void doubly_linked_list::iterator::operator ++()
  39 {
  40   if (is_tail()) return;  // already at the end.
  41   _cursor = _cursor->get_link(NEXT);
  42 }
  43
  44 void doubly_linked_list::iterator::operator --()
  45 {
  46   if (is_head()) return;  // already at the front.
  47   _cursor = _cursor->get_link(PREVIOUS);
  48 }
  49
  50 bool doubly_linked_list::iterator::operator ==(const iterator &to_compare) const
  51 { return _cursor == to_compare._cursor; }
  52
  53 const node *doubly_linked_list::iterator::observe()
  54 {
  55   if (!_manager || _manager->empty()) return NULL_POINTER;
  56   if (*this == _manager->head()) next();
  57   if (*this == _manager->tail()) previous();
  58   return _cursor;
  59 }
  60
  61 node *doubly_linked_list::iterator::access()
  62 {
  63   if (!_manager || _manager->empty()) return NULL_POINTER;
  64   if (*this == _manager->head()) next();
  65   if (*this == _manager->tail()) previous();
  66   return _cursor;
  67 }
  68
  69 bool doubly_linked_list::iterator::is_head() const
  70 {
  71   if (!_manager) return false;
  72   return _cursor == _manager->_head;
  73 }
  74
  75 bool doubly_linked_list::iterator::is_tail() const
  76 {
  77   if (!_manager) return false;
  78   return _cursor == _manager->_tail;
  79 }
  80
  81 void doubly_linked_list::iterator::jump_head()
  82 {
  83   if (!_manager) return;
  84   _cursor = _manager->_head;
  85 }
  86
  87 void doubly_linked_list::iterator::jump_tail()
  88 {
  89   if (!_manager) return;
  90   _cursor = _manager->_tail;
  91 }
  92
  93 //////////////
  94
  95 doubly_linked_list::doubly_linked_list()
  96 : _head(NULL_POINTER), _tail(NULL_POINTER)
  97 {
  98   _head = new node(2);
  99   _tail = new node(2);
 100   _head->set_link(NEXT, _tail);
 101   _tail->set_link(PREVIOUS, _head);
 102 }
 103
 104 doubly_linked_list::~doubly_linked_list()
 105 {
 106   iterator zapper = head();
 107   while (!empty())
 108     zap(zapper);
 109   WHACK(_head);
 110   WHACK(_tail);
 111 }
 112
 113 bool doubly_linked_list::empty() const
 114 {
 115   if (_head->get_link(NEXT) == _tail) return true;
 116   return false;
 117 }
 118
 119 bool doubly_linked_list::set_index(iterator &where, int new_index)
 120 {
 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.
 127   }
 128   where._cursor = skipper;
 129   return true;
 130 }
 131
 132 bool doubly_linked_list::forward(iterator &where, int count)
 133 {
 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();
 139   return true;
 140 }
 141
 142 bool doubly_linked_list::backward(iterator &where, int count)
 143 {
 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();
 149   return true;
 150 }
 151
 152 int doubly_linked_list::elements() const
 153 {
 154   if (empty()) return 0;
 155   int to_return = 0;
 156   node *skipper = _head->get_link(NEXT);
 157   while (skipper != _tail) {
 158     to_return++;
 159     skipper = skipper->get_link(NEXT);
 160   }
 161   return to_return;
 162 }
 163
 164 int doubly_linked_list::items_from_head(const iterator &where) const
 165 {
 166   if (where._manager != this) return 0;
 167   if (where.is_head()) return 0;  // make sure it's not there already.
 168   int index = 0;
 169   node *skipper = _head->get_link(NEXT);
 170   while ( (where._cursor != skipper) && (skipper != _tail) ) {
 171     index++;
 172     skipper = skipper->get_link(NEXT);
 173   }
 174   return index;
 175 }
 176
 177 int doubly_linked_list::items_from_tail(const iterator &where) const
 178 {
 179   if (where._manager != this) return 0;
 180   if (where.is_tail()) return 0;  // make sure it's not there already.
 181   int index = 0;
 182   node *skipper = _tail->get_link(PREVIOUS);
 183   while ( (where._cursor != skipper) && (skipper != _head) ) {
 184     index++;
 185     skipper = skipper->get_link(PREVIOUS);
 186   }
 187   return index;
 188 }
 189
 190 /*
 191 node *list::get()
 192 {
 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.
 198   return _cursor;
 199 }
 200 */
 201
 202 node *doubly_linked_list::remove(iterator &where)
 203 {
 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;
 218   return old_cursor;
 219 }
 220
 221 void doubly_linked_list::zap(iterator &where) { delete remove(where); }
 222
 223 void doubly_linked_list::append(iterator &where, node *new_node)
 224 {
 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;
 237 }
 238
 239 void doubly_linked_list::insert(iterator &where, node *new_node)
 240 {
 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;
 253 }
 254
 255 void doubly_linked_list::zap_all()
 256 {
 257   iterator zapper = head();
 258   while (!empty()) zap(zapper);
 259 }
 260
 261 } // namespace.
 262
 263
 264
 265