X-Git-Url: https://feistymeow.org/gitweb/?a=blobdiff_plain;f=nucleus%2Flibrary%2Fnodes%2Flist.h;fp=nucleus%2Flibrary%2Fnodes%2Flist.h;h=455ebaa4711f02335a2fd87fef64be5d32c8b7b2;hb=457b128b77b5b4a0b7dd3094de543de2ce1477ad;hp=0000000000000000000000000000000000000000;hpb=32d7caf45d886d0d24e69eea00511c7815ac15d0;p=feisty_meow.git diff --git a/nucleus/library/nodes/list.h b/nucleus/library/nodes/list.h new file mode 100644 index 00000000..455ebaa4 --- /dev/null +++ b/nucleus/library/nodes/list.h @@ -0,0 +1,190 @@ +#ifndef LIST_CLASS +#define LIST_CLASS + +/*****************************************************************************\ +* * +* 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 * +\*****************************************************************************/ + + + +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. +*/ + +class list +{ +public: + list(); + //!< constructs a blank list. + + ~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 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 NIL 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 NIL if the list is empty. */ + node *access(); //!< obtain access to the current element. + + private: + node *_cursor; //!< the current position. + friend class list; //!< lists have full access to this object. + const 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. + /*!< NIL 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. + list(const list &); + list &operator =(const list &); +}; + +} // namespace. + +#endif +