--- /dev/null
+
+
+
+/*****************************************************************************\
+* *
+* Name : list *
+* Author : Chris Koeritz *
+* *
+*******************************************************************************
+* Copyright (c) 1998-$now By Author. This program is free software; you can *
+* redistribute it and/or modify it under the terms of the GNU General Public *
+* License as published by the Free Software Foundation; either version 2 of *
+* the License or (at your option) any later version. This is online at: *
+* http://www.fsf.org/copyleft/gpl.html *
+* Please send any updates to: fred@gruntose.com *
+\*****************************************************************************/
+
+// POLICIES:
+//
+// the cursor should never be stored to or deleted; it is merely a scanner that
+// runs through the list.
+//
+// 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.
+
+#include "list.h"
+#include "node.h"
+
+#include <basis/functions.h>
+
+namespace nodes {
+
+// nice names for the positions of the next link and the previous link in
+// our node's indices.
+const int PREVIOUS = 0;
+const int NEXT = 1;
+
+//////////////
+
+// iterator functions:
+
+void list::iterator::operator ++()
+{
+ if (is_tail()) return; // already at the end.
+ _cursor = _cursor->get_link(NEXT);
+}
+
+void list::iterator::operator --()
+{
+ if (is_head()) return; // already at the front.
+ _cursor = _cursor->get_link(PREVIOUS);
+}
+
+bool list::iterator::operator ==(const iterator &to_compare) const
+{ return _cursor == to_compare._cursor; }
+
+const node *list::iterator::observe()
+{
+ if (!_manager || _manager->empty()) return NIL;
+ if (*this == _manager->head()) next();
+ if (*this == _manager->tail()) previous();
+ return _cursor;
+}
+
+node *list::iterator::access()
+{
+ if (!_manager || _manager->empty()) return NIL;
+ if (*this == _manager->head()) next();
+ if (*this == _manager->tail()) previous();
+ return _cursor;
+}
+
+bool list::iterator::is_head() const
+{
+ if (!_manager) return false;
+ return _cursor == _manager->_head;
+}
+
+bool list::iterator::is_tail() const
+{
+ if (!_manager) return false;
+ return _cursor == _manager->_tail;
+}
+
+void list::iterator::jump_head()
+{
+ if (!_manager) return;
+ _cursor = _manager->_head;
+}
+
+void list::iterator::jump_tail()
+{
+ if (!_manager) return;
+ _cursor = _manager->_tail;
+}
+
+//////////////
+
+list::list()
+: _head(NIL), _tail(NIL)
+{
+ _head = new node(2);
+ _tail = new node(2);
+ _head->set_link(NEXT, _tail);
+ _tail->set_link(PREVIOUS, _head);
+}
+
+list::~list()
+{
+ iterator zapper = head();
+ while (!empty())
+ zap(zapper);
+ WHACK(_head);
+ WHACK(_tail);
+}
+
+bool list::empty() const
+{
+ if (_head->get_link(NEXT) == _tail) return true;
+ return false;
+}
+
+bool list::set_index(iterator &where, int new_index)
+{
+ if (where._manager != this) return false;
+ if (empty()) return false;
+ node *skipper = _head->get_link(NEXT);
+ for (int i = 0; i < new_index; i++) {
+ skipper = skipper->get_link(NEXT);
+ if (skipper == _tail) return false; // out of bounds now.
+ }
+ where._cursor = skipper;
+ return true;
+}
+
+bool list::forward(iterator &where, int count)
+{
+ if (where._manager != this) return false;
+ if (count <= 0) return true;
+ if (items_from_tail(where) < count) return false;
+ if (where.is_head()) where.next(); // skip the head guard.
+ for (int i = 0; i < count; i++) where.next();
+ return true;
+}
+
+bool list::backward(iterator &where, int count)
+{
+ if (where._manager != this) return false;
+ if (count <= 0) return true;
+ if (items_from_head(where) < count) return false;
+ if (where.is_tail()) where.previous(); // skip the tail guard.
+ for (int i = 0; i < count; i++) where.previous();
+ return true;
+}
+
+int list::elements() const
+{
+ if (empty()) return 0;
+ int to_return = 0;
+ node *skipper = _head->get_link(NEXT);
+ while (skipper != _tail) {
+ to_return++;
+ skipper = skipper->get_link(NEXT);
+ }
+ return to_return;
+}
+
+int list::items_from_head(const iterator &where) const
+{
+ if (where._manager != this) return 0;
+ if (where.is_head()) return 0; // make sure it's not there already.
+ int index = 0;
+ node *skipper = _head->get_link(NEXT);
+ while ( (where._cursor != skipper) && (skipper != _tail) ) {
+ index++;
+ skipper = skipper->get_link(NEXT);
+ }
+ return index;
+}
+
+int list::items_from_tail(const iterator &where) const
+{
+ if (where._manager != this) return 0;
+ if (where.is_tail()) return 0; // make sure it's not there already.
+ int index = 0;
+ node *skipper = _tail->get_link(PREVIOUS);
+ while ( (where._cursor != skipper) && (skipper != _head) ) {
+ index++;
+ skipper = skipper->get_link(PREVIOUS);
+ }
+ return index;
+}
+
+/*
+node *list::get()
+{
+ if (empty()) return NIL; // make sure the list isn't empty.
+ if (_cursor == _head) return _head->get_link(NEXT);
+ // check special case for pointing at the head.
+ if (_cursor == _tail) return _tail->get_link(PREVIOUS);
+ // check special case for pointing at the tail.
+ return _cursor;
+}
+*/
+
+node *list::remove(iterator &where)
+{
+ if (where._manager != this) return NIL;
+ if (empty()) return NIL;
+ if (where._cursor == _head)
+ where._cursor = _head->get_link(NEXT);
+ if (where._cursor == _tail)
+ where._cursor = _tail->get_link(PREVIOUS);
+ node *old_cursor = where._cursor;
+ node *old_previous = old_cursor->get_link(PREVIOUS);
+ node *old_next = old_cursor->get_link(NEXT);
+ old_cursor->set_link(PREVIOUS, NIL);
+ old_cursor->set_link(NEXT, NIL);
+ old_previous->set_link(NEXT, old_next);
+ old_next->set_link(PREVIOUS, old_previous);
+ where._cursor = old_next;
+ return old_cursor;
+}
+
+void list::zap(iterator &where) { delete remove(where); }
+
+void list::append(iterator &where, node *new_node)
+{
+ if (where._manager != this) return;
+ while (new_node->links() < 2) new_node->insert_link(0, NIL);
+ if (empty()) where._cursor = _head;
+ if (where._cursor == _tail)
+ where._cursor = _tail->get_link(PREVIOUS);
+ // shift from the tail sentinel to the tail element.
+ node *save_next = where._cursor->get_link(NEXT);
+ where._cursor->set_link(NEXT, new_node);
+ new_node->set_link(PREVIOUS, where._cursor);
+ new_node->set_link(NEXT, save_next);
+ save_next->set_link(PREVIOUS, new_node);
+ where._cursor = new_node;
+}
+
+void list::insert(iterator &where, node *new_node)
+{
+ if (where._manager != this) return;
+ while (new_node->links() < 2) new_node->insert_link(0, NIL);
+ if (empty()) where._cursor = _tail;
+ if (where._cursor == _head)
+ where._cursor = _head->get_link(NEXT);
+ // shift from head sentinel to the head element.
+ node *save_prior = where._cursor->get_link(PREVIOUS);
+ where._cursor->set_link(PREVIOUS, new_node);
+ new_node->set_link(NEXT, where._cursor);
+ new_node->set_link(PREVIOUS, save_prior);
+ save_prior->set_link(NEXT, new_node);
+ where._cursor = new_node;
+}
+
+void list::zap_all()
+{
+ iterator zapper = head();
+ while (!empty()) zap(zapper);
+}
+
+} // namespace.
+
+
+
+
projects / feisty_meow.git / blobdiff