core/library/nodes/list.cpp

   1
   2
   3
   4 /*****************************************************************************\
   5 *                                                                             *
   6 *  Name   : list                                                              *
   7 *  Author : Chris Koeritz                                                     *
   8 *                                                                             *
   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 \*****************************************************************************/
  17
  18 // POLICIES:
  19 //
  20 // the cursor should never be stored to or deleted; it is merely a scanner that
  21 // runs through the list.
  22 //
  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.
  26
  27 #include "list.h"
  28 #include "node.h"
  29
  30 #include <basis/functions.h>
  31
  32 namespace nodes {
  33
  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;
  37 const int NEXT = 1;
  38
  39 //////////////
  40
  41 // iterator functions:
  42
  43 void list::iterator::operator ++()
  44 {
  45   if (is_tail()) return;  // already at the end.
  46   _cursor = _cursor->get_link(NEXT);
  47 }
  48
  49 void list::iterator::operator --()
  50 {
  51   if (is_head()) return;  // already at the front.
  52   _cursor = _cursor->get_link(PREVIOUS);
  53 }
  54
  55 bool list::iterator::operator ==(const iterator &to_compare) const
  56 { return _cursor == to_compare._cursor; }
  57
  58 const node *list::iterator::observe()
  59 {
  60   if (!_manager || _manager->empty()) return NIL;
  61   if (*this == _manager->head()) next();
  62   if (*this == _manager->tail()) previous();
  63   return _cursor;
  64 }
  65
  66 node *list::iterator::access()
  67 {
  68   if (!_manager || _manager->empty()) return NIL;
  69   if (*this == _manager->head()) next();
  70   if (*this == _manager->tail()) previous();
  71   return _cursor;
  72 }
  73
  74 bool list::iterator::is_head() const
  75 {
  76   if (!_manager) return false;
  77   return _cursor == _manager->_head;
  78 }
  79
  80 bool list::iterator::is_tail() const
  81 {
  82   if (!_manager) return false;
  83   return _cursor == _manager->_tail;
  84 }
  85
  86 void list::iterator::jump_head()
  87 {
  88   if (!_manager) return;
  89   _cursor = _manager->_head;
  90 }
  91
  92 void list::iterator::jump_tail()
  93 {
  94   if (!_manager) return;
  95   _cursor = _manager->_tail;
  96 }
  97
  98 //////////////
  99
 100 list::list()
 101 : _head(NIL), _tail(NIL)
 102 {
 103   _head = new node(2);
 104   _tail = new node(2);
 105   _head->set_link(NEXT, _tail);
 106   _tail->set_link(PREVIOUS, _head);
 107 }
 108
 109 list::~list()
 110 {
 111   iterator zapper = head();
 112   while (!empty())
 113     zap(zapper);
 114   WHACK(_head);
 115   WHACK(_tail);
 116 }
 117
 118 bool list::empty() const
 119 {
 120   if (_head->get_link(NEXT) == _tail) return true;
 121   return false;
 122 }
 123
 124 bool list::set_index(iterator &where, int new_index)
 125 {
 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.
 132   }
 133   where._cursor = skipper;
 134   return true;
 135 }
 136
 137 bool list::forward(iterator &where, int count)
 138 {
 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();
 144   return true;
 145 }
 146
 147 bool list::backward(iterator &where, int count)
 148 {
 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();
 154   return true;
 155 }
 156
 157 int list::elements() const
 158 {
 159   if (empty()) return 0;
 160   int to_return = 0;
 161   node *skipper = _head->get_link(NEXT);
 162   while (skipper != _tail) {
 163     to_return++;
 164     skipper = skipper->get_link(NEXT);
 165   }
 166   return to_return;
 167 }
 168
 169 int list::items_from_head(const iterator &where) const
 170 {
 171   if (where._manager != this) return 0;
 172   if (where.is_head()) return 0;  // make sure it's not there already.
 173   int index = 0;
 174   node *skipper = _head->get_link(NEXT);
 175   while ( (where._cursor != skipper) && (skipper != _tail) ) {
 176     index++;
 177     skipper = skipper->get_link(NEXT);
 178   }
 179   return index;
 180 }
 181
 182 int list::items_from_tail(const iterator &where) const
 183 {
 184   if (where._manager != this) return 0;
 185   if (where.is_tail()) return 0;  // make sure it's not there already.
 186   int index = 0;
 187   node *skipper = _tail->get_link(PREVIOUS);
 188   while ( (where._cursor != skipper) && (skipper != _head) ) {
 189     index++;
 190     skipper = skipper->get_link(PREVIOUS);
 191   }
 192   return index;
 193 }
 194
 195 /*
 196 node *list::get()
 197 {
 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.
 203   return _cursor;
 204 }
 205 */
 206
 207 node *list::remove(iterator &where)
 208 {
 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;
 223   return old_cursor;
 224 }
 225
 226 void list::zap(iterator &where) { delete remove(where); }
 227
 228 void list::append(iterator &where, node *new_node)
 229 {
 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;
 242 }
 243
 244 void list::insert(iterator &where, node *new_node)
 245 {
 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;
 258 }
 259
 260 void list::zap_all()
 261 {
 262   iterator zapper = head();
 263   while (!empty()) zap(zapper);
 264 }
 265
 266 } // namespace.
 267
 268
 269
 270