Polaris: Set.h Source File

Collection/Set.h Go to the documentation of this file. /// /// #ifndef _SET_H #define _SET_H /// /// file Set.cc /// /// \class Set /// \brief A very simple set class /// \defgroup Polaris /// \ingroup Polaris /// C++ VDL /// \see Set.h /// /// \endcode /// \section Overview Overview /// A template for a set for type T /// where 'T' must be derived from Listable. The /// Set is built from Collection so the Iterator /// class operates on it. The Set takes ownership /// of objects which are inserted into it. /// /// \endcode /// \section Bugs Bugs /// The set is implemented...poorly. It is a /// a List. Due to the simple implementation a /// number of problems exists including efficiency /// and confusing error messages. It is, however, /// operational (we think). /// The interface is based on the RefSet. Thus, /// it is not particularly good. It should be /// reconsidered. /// /// \endcode /// \section Hierarchy Hierarchy Structure /// Set 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 /// /// #include <stream.h> /// #include "BaseList.h" #include "TypedCollection.h" /// template <class T> class Set : public TypedCollection<T> { friend class Iterator <T>; friend class Mutator <T>; protected: BaseList _list; virtual INLINE const Collection & _base_collection() const; virtual INLINE Collection & _base_collection(); public: INLINE Set(); INLINE Set(const Set<T> &l); virtual INLINE ~Set(); INLINE const T &_element(int loc) const; INLINE T &_element(int loc); ///< Used to obtain a specific element of the set. Use the _member() ///< function to get the index that is used. INLINE void _del(int loc); ///< Random Access Delete. ///< Delete the Node in position loc where 1 <= loc <= entries(). INLINE void _modify(int loc, T *el); ///< Random Access Modify. ///< Change the node at position loc to be el. If el is already ///< in the set, the locth position is deleted. INLINE int entries() const; ///< Return the number of entries in the Set. INLINE Boolean empty() const; ///< Return a flag indicating if the Set is empty. INLINE void print(ostream & out, char *sep) const; ///< print set to out with 'sep' sepperating each element INLINE T &ins(const T *new_element); ///< Insert new_element into the set, and return a reference ///< to '*new_element' (for purposes of programming convenience). ///< If an element with the same key already exists, this old ///< object is deleted and replaced with 'new_element'. INLINE void modify(T &el, T *new_element); ///< Modify 'el' to be the new_element. INLINE void del(T &el); ///< Delete node 'el'. INLINE T *grab(); ///< Delete and return an arbitrary element of the set. INLINE Boolean member(const T &el) const; ///< Check to see if node 'el' is a member of the Set. INLINE int _member(const T &el) const; ///< Check to see if node 'el' is a member of the Set. Return ///< -1 if the element was not found otherwise return its index. INLINE void clear(); ///< Delete the entire set. INLINE Set<T> & operator = (const Set<T> &l); ///< Copy operator completely copies a Set. 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. INLINE Listable *listable_clone() const; ///< Needed for Listable class. INLINE void print(ostream &o) const; ///< Needed for Listable class. }; ///< implementation template <class T> INLINE Set<T>::Set() { ///< nothing to do } template <class T> INLINE Set<T>::Set(const Set<T> &l) { _list = l._list; } template <class T> INLINE Set<T>::~Set() { ///< nothing to do } template <class T> INLINE int Set<T>::entries() const { return _list.entries(); } template <class T> INLINE Boolean Set<T>::empty() const { return (_list.entries() == 0); } template <class T> INLINE void Set<T>::print(ostream & out, char *sep) const { out << "{"; _list.print(out, sep); out << "}"; } template <class T> INLINE T & Set<T>::ins(const T *new_element) { int loc = _list.index(*new_element); if (loc >= 0) { ///< Replace the old with the new _list.modify(loc, CASTAWAY(T *)new_element); } else { ///< Simply insert at end (is not already in set) _list.ins(new_element, _list.entries()); } return CASTAWAY(T &)*new_element; } template <class T> INLINE void Set<T>::_del(int loc) { _list.del(loc); } template <class T> INLINE void Set<T>::_modify(int loc, T *el) { if (_list.member(*el)) _list.del(loc); else _list.modify(loc, el); } template <class T> INLINE void Set<T>::modify(T &el, T *new_element) { del( el ); _list.ins(new_element, _list.entries()); } template <class T> INLINE void Set<T>::del(T &el) { int i = _list.index(el); if (i >= 0) _list.del(i); } template <class T> INLINE T * Set<T>::grab() { return (T *) _list.grab(_list.entries() - 1); } template <class T> INLINE int Set<T>::_member(const T &el) const { return _list.index(el); } template <class T> INLINE Boolean Set<T>::member(const T &el) const { return (_list.member(el)); } template <class T> INLINE void Set<T>::clear() { _list.clear(); } template <class T> INLINE Set<T> & Set<T>::operator = (const Set<T> &l) { _list = l._list; return *this; } template <class T> INLINE int Set<T>::structures_OK() const { return _list.structures_OK(); } template <class T> INLINE const T & Set<T>::_element(int sub) const { return (const T &) _list[sub]; } template <class T> INLINE T & Set<T>::_element(int sub) { return (T &) _list[sub]; } template <class T> INLINE const Collection & Set<T>::_base_collection() const { return _list; } template <class T> INLINE Collection & Set<T>::_base_collection() { return _list; } template <class T> INLINE Listable * Set<T>::listable_clone() const { return (Listable *) new Set<T>(*this); } template <class T> INLINE void Set<T>::print(ostream &o) const { print(o, ", "); } ///< This interface is for testing purposes only. It invokes a non-virtual ///< member function to print a representation of the data structure at this ///< level of the Collection hierarchy, and, since it is not a class member ///< function, it must be explicitly instantiated before use. template <class T> ostream & operator << (ostream & o, const Set<T> &s) { s.print(o, ", "); return o; } #endif

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