--- /dev/null
+#ifndef DOUBLY_LINKED_LIST_CLASS
+#define DOUBLY_LINKED_LIST_CLASS
+
+/*
+* Name : doubly_linked_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
+*/
+
+namespace nodes {
+
+class node; // forward.
+
+//! Implements a guarded, doubly linked list structure.
+/*!
+ The list is viewed one element at a time, through the monocular of an
+ iterator, which keeps track of the current position in the list. the
+ iterator's cursor can be shifted around at will. nodes can be added to
+ the list before or after the cursor, and the node pointed at by the cursor
+ can be queried or modified. Using multiple iterators is fine as long as
+ you guarantee that they either are all just reading the list or that you
+ have a valid access pattern of reads and writes such that no iterator's
+ cursor is affected. Note that this list is not thread safe.
+*/
+
+
+//hmmm: is this class really for real? it's doing all sorts of stuff with nodes, rather than with the list object itself.
+// consider dropping the current implementation and providing more standard list operations, on an object that is actually using itself in its definition, rather than a different class (node).
+// this would be easy to do if we just break down and define the dl list as a node itself. then we have something to work with.
+
+//current iterator implementation here is bunk.
+
+
+class doubly_linked_list
+{
+public:
+ doubly_linked_list();
+ //!< constructs a blank list.
+
+ ~doubly_linked_list();
+ //!< invalidates all contents of the list and destroys all child nodes.
+
+ int elements() const;
+ //!< returns the number of items currently in the list.
+ /*!< this is a costly operation. */
+
+ bool empty() const;
+ //!< returns true if the list is empty.
+ /*!< this is really quick compared to checking the number of elements. */
+
+ //! iterators allow the list to be traversed.
+ /*! NOTE: it is an error to use an iterator on one list with a different
+ list; the methods will do nothing or return empty results in this
+ situation. */
+
+ class iterator {
+ public:
+ iterator(const doubly_linked_list *mgr, node *start) : _cursor(start), _manager(mgr) {}
+ //!< opens up an iterator on a list.
+ /*!< the preferred method to construct an iterator is to use the
+ head/tail functions in list. */
+
+ void operator ++(); //!< go to next item.
+ void operator --(); //!< go to previous item.
+ void operator ++(int) { ++(*this); } //!< post-fix synonym for ++.
+ void operator --(int) { --(*this); } //!< post-fix synonym for --.
+
+
+ void next() { (*this)++; } //!< synonym for ++.
+ void previous() { (*this)--; } //!< synonyms for --.
+
+ bool operator ==(const iterator &to_compare) const;
+ //!< returns true if the two iterators are at the same position.
+
+ bool is_head() const;
+ //!< returns true if the cursor is at the head of the list.
+ /*!< Note: head() and tail() only return true if the iterator is
+ actually positioned _at_ the head or tail guard. for example, if the
+ cursor is pointing at the last actual element in the list (but not at
+ the guard itself), then is_tail() returns false. so, in iteration,
+ your iterator will actually go past the last valid element before
+ is_tail() returns true. thus it is very important to check is_tail()
+ *before* looking at the node with observe() or access(), since those
+ two will shift the list position to the nearest valid node and away
+ from the guard. */
+ bool is_tail() const;
+ //!< returns true if the cursor is at the tail of the list.
+
+ void jump_head(); //!< set the iterator to the head.
+ void jump_tail(); //!< set the iterator to the tail.
+
+ const node *observe(); //!< peek at the current element.
+ /*!< Note: observe() and access() will return the first element if the
+ list is positioned at the head (or the last if at the tail), and will
+ not return NULL_POINTER for these two positions as long as the list has some
+ elements in it. the cursor will also have been moved to point at the
+ element that is returned.
+ Another Note: it is extremely important that you do not mess with the
+ links owned by the node (or at least the first two links).
+ A Third Note: these two functions can return NULL_POINTER if the list is empty. */
+ node *access(); //!< obtain access to the current element.
+
+ private:
+ node *_cursor; //!< the current position.
+ friend class doubly_linked_list; //!< lists have full access to this object.
+ const doubly_linked_list *_manager; //!< our friendly manager.
+ };
+
+ iterator head() const { return iterator(this, _head); }
+ //!< returns an iterator located at the head of the list.
+ iterator tail() const { return iterator(this, _tail); }
+ //!< returns an iterator located at the tail of the list.
+
+ int index(const iterator &it) const { return items_from_head(it); }
+ //!< returns the zero-based index of the cursor's position from the head.
+ /*!< this is a synonym for items_from_head(). */
+
+ bool set_index(iterator &to_set, int new_index);
+ //!< positions the iterator "to_set" at the index specified.
+
+ // storage and retrieval actions.
+ // Note: all of these methods shift the iterator onto the next valid node
+ // if it is positioned at the beginning or end of the list.
+
+ void append(iterator &where, node *new_node);
+ //!< adds a "new_node" into the list immediately after "where".
+ /*!< the nodes previously following the current node (if any) will follow
+ after the "new_node". this does not change the current position.
+ ownership of "new_node" is taken over by the list. */
+
+ void insert(iterator &where, node *new_node);
+ //!< places a "new_node" immediately before the current node in the list.
+ /*!< the "new_node" will follow the prior precursor to the current node.
+ this does not change the current position. ownership of "new_node"
+ is taken over by the list. after the call, the iterator points at
+ the new node. */
+
+ node *remove(iterator &where);
+ //!< extracts the current item from "where" and repairs the hole.
+ /*!< NULL_POINTER is returned if the list was empty. the current position is set
+ to the node that used to be after the node that has been removed. after
+ the call, the iterator points at the new node. */
+
+ void zap(iterator &where);
+ //!< wipes out the item at "where", including its contents.
+ /*!< the current position is reset to the item after the now defunct
+ item (or the tail). */
+
+ void zap_all();
+ //!< destroys all the list elements and makes the list empty.
+ /*!< any existing iterators will be invalidated by this. */
+
+ // the following positioning functions could fail if the request is out of
+ // bounds. for example, forward cannot go beyond the end of the list. in
+ // such cases, false is returned and the list pointer is not moved.
+
+ bool forward(iterator &where, int count);
+ //!< moves the list pointer "count" items towards the tail.
+ /*!< Note: forward and backward operate on elements; the head and tail
+ guard are not included in the count. Also, negative values of "count"
+ are ignored. */
+ bool backward(iterator &where, int count);
+ //!< moves the list pointer "count" items towards the head.
+
+ int items_from_head(const iterator &where) const;
+ //!< Returns the number of elements between the current item and the head.
+ /*!< zero is returned if this is at the first element or the head. */
+ int items_from_tail(const iterator &where) const;
+ //!< Returns the number of elements between the current item and the tail.
+ /*!< zero is returned if this is at the last element or the tail. */
+
+private:
+ friend class iterator;
+ node *_head; //!< pointer to the first item.
+ node *_tail; //!< pointer to the last item.
+
+ bool skip_or_ignore(iterator &where, int count);
+ //!< zips the list to the position indicated by "count", if it can.
+
+ // not permitted.
+ doubly_linked_list(const doubly_linked_list &);
+ doubly_linked_list &operator =(const doubly_linked_list &);
+};
+
+} // namespace.
+
+#endif
+
projects / feisty_meow.git / blobdiff