Polaris: List.h Source File

List.h Go to the documentation of this file. /// /// #ifndef _LIST_H #define _LIST_H /// /// \class List /// \brief template for types derived from Listable /// \defgroup Polaris /// \ingroup Polaris /// C++ VDL /// \see List.h /// /// \endcode /// \section Overview Overview /// The List class creates a templatized linked-list object for /// objects which must be derived from Listable. Since the List /// is built from Collection it works with Iterators. When an /// object is placed into a List, the List assumes ownership of /// the object and that object can not be placed in any other /// live structure. An object must be in a live structure, like /// List, before it can be used in a reference structure, like /// RefList. /// /// \endcode /// \section Description Description /// If a list is static, its size must remain constant. Thus, calls /// to either ins or del methods result in errors. If an element is /// grabbed from a static list, the element's position becomes invalid /// (a state which can be checked). That position can then be /// modified to another object which will revalidate it. All modify /// routines operate on static lists. A static list can be initialized /// to a fixed size by passing a positive integer value to the constructor. /// This creates a staic list of invlaid elements which can changed /// using 'modify' commands. /// /// Note that Lists are indexed from 0. /// /// These Lists provide reference counting so /// List elements, if deleted or grabbed from the owner list while /// still being referenced by some reference structures, will /// become \'invalid\'--a state which can be checked by the ref. structure /// before any dereferencing takes place. /// /// \endcode /// \section Assign Assign Operation /// assign/pull is designed to allow the functionality of /// modifying an element of a list to be some function of the old value of /// that position. The assign() is meant to be executed first, to /// capture the original position in the under-lying list for the element. /// The Assign<T> object returned by assign() stores the position information /// of the element. Then, pull() is used to remove the element from the /// list, without losing its position in the list. /// /// The 'pull' method removes the specified object from its list (like /// grab) but maintains it's 'place' in the list. Once an object has been /// pulled, it is no longer possible to access the List using the pulled /// object as a reference. Once an object has been pulled it can be /// modified in any way. Once the modification is complete, the object /// can be returned to its position in the list by assigning to the Assign<T> /// object (the one created by the original assign() call). /// /// The user, of course, is responsible for garbage collecting any /// intermediate forms of the pulled object which may be created. A /// complete use would be as follows: /// /// \code /// { /// loc = list.index(el); /// Assign<Expression> a = list.assign(loc); /// a = function(list.pull(loc) ); /// } // "a" is removed by leaving the scope /// /// --or-- /// { /// Assign<Expression> a = list.assign(el); /// a = function(list.pull(el) ); /// } // "a" is removed by leaving the scope /// \endcode /// /// 'function' is simply a funtion which returns the modified value. If /// the modified value is a different object than the original, function /// is responsible for garbage collecting the original. In this case, the /// specified object is pulled from the list, modified somehow by function /// and the returned value takes it's place in the list. /// /// IMPORTANT \note /// /// Due to the order in which different C++ compilers evaluate assignment /// statements, the statement: /// /// \code /// list.assign(el) = f(list.pull(el)); /// \endcode /// /// may not function correctly. Also, the following code is INCORRECT: /// /// \code /// x = list.pull(el); /// list.assign(el) = f(x); /// \endcode /// /// will result in a run-time error. The assign() member function must /// ALWAYS execute prior to the corresponding pull() member function! /// /// /// \endcode /// \section Hierarchy Hierarchy Structure /// List does not directly inherit from Collection. Instead /// it inherits from TypedCollection (which forms the interface /// to all Iterator routines) and contains a BaseList /// which inherits from Collection. /// The hierarchy can be represented by: /// /// \code /// --- : inherited from relationship /// -c- : contained in relationship /// /// /// Collection /// / \ // /// / \ // /// BaseList Listable BaseRefList /// | \ | / | /// | \ | / | /// | c TypedCollection c | /// | \ / \ / | /// | \ / \ / | /// | LIST RefList | /// | Set RefSet | /// c c /// | Listable | /// | | | /// | | | /// | BaseMapRoot | /// | / \ | /// | / \ | /// BaseMap BaseRefMap /// | | /// | | /// TypedBaseMap TypedBaseRefMap /// / \ / \ // /// / \ / \ // /// ProtoDatabase ProtoMap ProtoRefMap ProtoRefDatabase /// / \ | | | | | \ // /// / \ | | | | | \ // /// Database KeyDatabase Map KeyMap RefMap KeyMap RefDatabase RefKeyDatabase /// \endcode /// /// \endcode /// \section See See Also /// Collection, Listable, Wrapper, Iterator, TypedCollection, Zombie, /// BaseList /// /// #include <stream.h> #include "BaseList.h" #include "TypedCollection.h" #include "Assign.h" #include "../macros.h" /// template <class T> class List : public TypedCollection<T> { friend class Iterator <T>; friend class Mutator <T>; friend class TopSorter; ///< gcc-2.96 need the stupid "<>" pair ///< friend ostream & operator << (ostream & o, const List<T> &l); friend ostream & operator << <> (ostream & o, const List<T> &l); protected: BaseList _list; virtual INLINE const Collection & _base_collection() const; virtual INLINE Collection & _base_collection(); public: INLINE List(); ///< create an empty list INLINE List(const List<T> &l); ///< create a list identical to l virtual INLINE ~List(); INLINE List(unsigned static_size); ///< Create a static list of size static_size initialized ///< with all elements invalid. INLINE List(const T *el1, const T *el2 GIV(0)); ///< create a static list of 1 or 2 elements. INLINE void make_static_list(int static_size); ///< Clear the list and set it to a static list of size ///< static_size with all elements invalid. INLINE Boolean static_size() const; ///< Is the size of the collection static? INLINE void fix_size(); ///< Make the size constant. INLINE void unfix_size(); ///< Make the size variable. INLINE int entries() const; ///< Return the number of entries within the List. INLINE Boolean member(const T &el) const; ///< Check to see if node 'el' is a member of the List. Return ///< 0 if the element was not found, else return 1. INLINE int index(const T &el) const; ///< Check to see if node 'el' is a member of the List. Return ///< -1 if the element was not found, else return the index of ///< the element. INLINE const T &operator[] (int sub) const; INLINE T &operator[] (int sub); ///< Implements the subscript operator (indexed from 0). ///< Should be used for random access only. ///< Consecutive searching should use the Iterator<T> class. ///< It is much more efficient. INLINE void print(ostream & out, char *sep) const; ///< print list to out with 'sep' sepperating each element. virtual INLINE void ins(const T *new_element, int loc); ///< Insert new_element at location loc, where 0 <= loc <= entries(). ///< This results in an error if the List is static sized. virtual INLINE void del(int loc); ///< Random Access Delete. ///< Delete the Node in position loc where 0 <= loc < entries()-1. ///< If references to the deleted element exist in RefStructures, ///< the references will now be invalid, making access illegal. ///< This results in an error for static lists. virtual INLINE void del(T &el); ///< Delete node 'el'. el MUST be in the BaseList (this is not ///< necessarily checked). If the list is static a error is raised. ///< If references to the deleted element exist in RefStructures, ///< the references will now be invalid, making access illegal. virtual INLINE T *grab(int loc); ///< Random Access Grab. ///< Grab (i.e. unlink and return the pointer to, but DO NOT ///< delete) the element at location loc. ///< If the list is static, the locth Node becomes invalid. virtual INLINE T *grab(T &el); ///< Grab (i.e. unlink and return the reference to, but DO NOT ///< delete) the element 'el', which MUST be in the list ///< (this is not necessarily checked). If the list is static ///< the node which was grabbed becomes invalid. ///< If references to the deleted element exist in RefStructures, ///< the references will now be invalid, making access illegal. virtual INLINE T *modify_and_grab(T &el, T *replacement); ///< Modify the list by grabbing 'el' out of the list and ///< replacing it with 'replacement' in the spot which ///< 'el' had taken in the list. A pointer to 'el' is returned, ///< and the user becomes responsible for deleting 'el'. ///< If 'el' is the same element as 'replacement', a run-time ///< error message occurs. virtual INLINE void modify(T &el, T *replacement); ///< Modify the list by grabbing 'el' out of the list and ///< replacing it with 'replacement' in the spot which ///< 'el' had taken in the list. 'el' is deleted. ///< 'el' MAY be the same element as 'replacement'. In this ///< case, the call is simply ignored. virtual INLINE void modify(int loc, T *replacement); ///< Modify the list by grabbing the locth element out of the ///< list and replacing it with 'replacement'. If the locth ///< element is valid, it is deleted, if it is not valid, ///< 'replacement' takes the locth position. 'el' MAY be the ///< same element as teh locth element. In this case, the call ///< is simply ignored. This is the only method of revalidating ///< invalid nodes. virtual INLINE void ins_first(const T *new_element); ///< Prepend new_element to the beginning of the list. ///< This results in an error for static lists. virtual INLINE void ins_last(const T *new_element); ///< Append new_element to the end of the list. ///< This results in an error for staic lists. virtual INLINE void ins_before(const T *new_element, const T *ref); ///< Insert new_element before the reference element 'ref' ///< (if ref == 0, insert at END of list). ///< ref MUST be in the list (this is not necessarily ///< checked). ///< This results in an error for staic lists. virtual INLINE void ins_after(const T *new_element, const T *ref); ///< Insert new_element after the reference element 'ref' ///< (if ref == 0, insert at BEGINNING of list). ///< ref MUST be in the list (this is not necessarily ///< checked). ///< This results in an error for staic lists. virtual INLINE T *pull(int loc); ///< Temporarily remove the locth element from the list so that ///< it can be operated on by assign and replaced. The pulled ///< element must be replaced using an assign call which must be ///< on the same line. See detailed description in the above ///< section "Assign Operation". virtual INLINE T *pull(T &el); ///< Temporarily remove the element el from the list so that ///< it can be operated on by assign and replaced. The pulled ///< element must be replaced using an assign call which must be ///< on the same line. See detailed description in the ///< section "Assign Operation". virtual INLINE Assign<T> assign(int loc); ///< Return control of a pulled element to its list in its original ///< position. The assign call must be on the same line as the pull ///< operation. See detailed description in the ///< section "Assign Operation". virtual INLINE Assign<T> assign(T &el); ///< Return control of a pulled element to its list in its original ///< position. The assign call must be on the same line as the pull ///< operation. See detailed description in the above ///< section "Assign Operation". INLINE const T *next_ref(const T &el) const; INLINE T *next_ref(const T &el); ///< Return the element after 'el' (return 0 if none). INLINE const T *prev_ref(const T &el) const; INLINE T *prev_ref(const T &el); ///< Return the element before 'el' (return 0 if none). INLINE const T *first_ref() const; INLINE T *first_ref(); ///< Return the first element. ///< Run-time error if none (i.e. the list is empty). INLINE const T *last_ref() const; INLINE T *last_ref(); ///< Return the last element. ///< Run-time error if none (i.e. the list is empty). INLINE Boolean valid(int loc) const; ///< is the locth element valid? virtual INLINE void clear(); ///< Delete the entire list and, for static lists, set all ///< entries to invalid. virtual INLINE List<T> &operator = (const List<T> &l); ///< Copy operator copies all elements of a list ///< If the LHS list is static, the RHS list must be of ///< equal or smaller size and the LHS list will be padded ///< with invalid nodes. virtual INLINE int structures_OK() const; ///< Check the structure of the data for errors or inconsistency ///< Return 0 and print error message if problems found, otherwise ///< return 1 without message. virtual INLINE Listable *listable_clone() const; ///< Needed for Listable class. virtual INLINE void print(ostream &o) const; ///< Needed for Listable class. }; ///< implementation template <class T> INLINE List<T>::List() { ///< nothing to do } template <class T> INLINE List<T>::List(const List<T> &l) { _list = l._list; } template <class T> INLINE List<T>::List(unsigned static_sz) { _list.make_static_list(static_sz); } template <class T> INLINE void List<T>::make_static_list ( int static_size ) { _list.make_static_list ( static_size ); } template <class T> INLINE List<T>::~List() { ///< nothing to do } template <class T> INLINE List<T>::List(const T *el1, const T *el2 GIV(0)) { _list.ins(el1, 0); if (el2) _list.ins(el2, 1); _list.fix_size(); } template <class T> INLINE int List<T>::entries() const { return _list.entries(); } template <class T> INLINE Boolean List<T>::static_size() const { return _list.static_size(); } template <class T> INLINE void List<T>::fix_size() { _list.fix_size(); } template <class T> INLINE void List<T>::unfix_size() { _list.unfix_size(); } template <class T> INLINE const T & List<T>::operator[] (int sub) const { return (const T &) _list[sub]; } template <class T> INLINE T & List<T>::operator[] (int sub) { return (T &) _list[sub]; } template <class T> INLINE void List<T>::print(ostream & out, char *sep) const { _list.print(out, sep); } template <class T> INLINE void List<T>::ins(const T *new_element, int loc) { _list.ins(new_element, loc); } template <class T> INLINE void List<T>::del(int loc) { _list.del(loc); } template <class T> INLINE void List<T>::del(T &el) { _list.del(el); } template <class T> INLINE T * List<T>::grab(int loc) { return (T *) _list.grab(loc); } template <class T> INLINE T * List<T>::grab(T &el) { return (T *) _list.grab( el ); } template <class T> INLINE void List<T>::ins_first(const T *new_element) { _list.ins(new_element, 0); } template <class T> INLINE void List<T>::ins_last(const T *new_element) { _list.ins(new_element, _list.entries()); } template <class T> INLINE void List<T>::ins_before(const T *new_element, const T *ref) { _list.ins_before(new_element, ref); } template <class T> INLINE void List<T>::ins_after(const T *new_element, const T *ref) { _list.ins_after(new_element, ref); } template <class T> INLINE Assign<T> List<T>::assign(int loc) { Assign<T> a(_list.assign(loc)); return a; } template <class T> INLINE Assign<T> List<T>::assign(T &el) { Assign<T> a(_list.assign(el)); return a; } template <class T> INLINE T * List<T>::pull(int loc) { return (T *) _list.pull(loc); } template <class T> INLINE T * List<T>::pull(T &el) { return (T *) _list.pull(el); } template <class T> INLINE const T * List<T>::next_ref(const T &el) const { return (const T *) _list.next_ref(el); } template <class T> INLINE T * List<T>::next_ref(const T &el) { return (T *) _list.next_ref(el); } template <class T> INLINE const T * List<T>::prev_ref(const T &el) const { return (const T *) _list.prev_ref(el); } template <class T> INLINE T * List<T>::prev_ref(const T &el) { return (T *) _list.prev_ref(el); } template <class T> INLINE const T * List<T>::first_ref() const { return (const T *) _list.first_ref(); } template <class T> INLINE T * List<T>::first_ref() { return (T *) _list.first_ref(); } template <class T> INLINE const T * List<T>::last_ref() const { return (const T *) _list.last_ref(); } template <class T> INLINE T * List<T>::last_ref() { return (T *) _list.last_ref(); } template <class T> INLINE Boolean List<T>::valid(int loc) const { return _list.valid(loc); } template <class T> INLINE void List<T>::clear() { _list.clear(); } template <class T> INLINE List<T> & List<T>::operator = (const List<T> &l) { _list = l._list; return *this; } template <class T> INLINE int List<T>::structures_OK() const { return _list.structures_OK(); } template <class T> INLINE T * List<T>::modify_and_grab(T &el, T *replacement) { return (T *) _list.modify_and_grab(el, replacement); } template <class T> INLINE void List<T>::modify(T &el, T *replacement) { _list.modify(el, replacement); } template <class T> INLINE void List<T>::modify(int loc, T *replacement) { _list.modify(loc, replacement); } template <class T> INLINE const Collection & List<T>::_base_collection() const { return _list; } template <class T> INLINE Collection & List<T>::_base_collection() { return _list; } template <class T> INLINE Listable * List<T>::listable_clone() const { return (Listable *) new List<T>(*this); } template <class T> INLINE void List<T>::print(ostream &o) const { print(o, ", "); } template <class T> INLINE int List<T>::index(const T &el) const { return _list.index( el ); } template <class T> INLINE Boolean List<T>::member(const T &el) const { return _list.member( el ); } ///< This interface is for testing purposes only. It prints the BaseList ///< (with wrapper information), and, since it is not a class member ///< function, it must be explicitly instantiated before use. template <class T> ostream & operator << (ostream & o, const List<T> &l) { ///< return o << l._list; ///< -> l.print( o ); return o; } #endif

© 1995-2005 University of Illinois, Urbana-Champaign. All rights reserved.  Fri Mar 25 23:05:58 2005