Polaris: RefSet.h Source File

RefSet.h Go to the documentation of this file. /// /// #ifndef _REF_SET_H #define _REF_SET_H /// /// \class RefSet /// \brief A very simple set class for references /// \defgroup Polaris /// \ingroup Polaris /// C++ VDL /// \see RefSet.h /// /// \endcode /// \section Overview Overview /// A template for a reference set for type T /// where 'T' must be derived from Listable. /// Like other Ref collections, this structure stores only /// references to the actual live objects, so objects which /// are put in the RefSet are aliased. Further, also like /// other Ref Collections, objects must already be living /// inside other collections before they can be inserted /// into a RefSet. /// /// If an object is inserted into a RefSet and is then /// removed or deleted from the live structure in which it /// truely lives, the reference to it in the RefSet becomes /// invalid. An invalid element can still be removed and /// indexed as before. /// /// RefSets work with the standard Iterator package. /// /// .BUGS /// The set is implemented...poorly. It is simply /// a RefList. It is not well desguised....a lot of the /// error messages will not seem appropriate, when it /// prints the set it still has brackets, etc.. /// Further, the interface seems sort of goofy, (for instance, /// having _member and member and no index etc..) /// This should perhaps be reconsidered. /// /// \endcode /// \section Hierarchy Hierarchy Structure /// RefSet does not directly inherit from Collection. Instead /// it inherits from TypedCollection (which forms the interface /// to all Iterator routines) and contains a BaseRefList /// 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, RefWrapper, Iterator, TypedCollection, Zombie, /// BaseRefList /// #include <stream.h> #include "../macros.h" #include "TypedCollection.h" #include "BaseRefList.h" /// template <class T> class RefSet : public TypedCollection<T> { friend class Iterator <T>; friend class Mutator <T>; protected: BaseRefList _list; virtual INLINE const Collection & _base_collection() const; virtual INLINE Collection & _base_collection(); public: INLINE RefSet(); INLINE RefSet(const RefSet<T >&l); virtual INLINE ~RefSet(); INLINE int _member(const T &el) const; ///< Check to see if node 'el' is a member of the RefSet. Return ///< -1 if the element was not found otherwise return its index. INLINE const T &_element(int loc) const; INLINE T &_element(int loc); ///< Used to obtain a specific elelemt of the set. Use the _member() ///< function to get the index that is used. An error is raised if ///< the locth element is invalid. INLINE void _del(int loc); ///< Random Access Delete. ///< Delete the Node in position loc where 0 <= loc <= entries()-1 INLINE void _modify(int loc, T &el); ///< Random Access Modify. ///< Change the node at position loc to be el. INLINE int entries() const; ///< Return the number of entries in the Set. INLINE Boolean empty() const; ///< Return a flag indicating if the RefSet is empty. INLINE Boolean any_valid() const; ///< Check to see if any valid elements exist in the RefSet. INLINE void print(ostream & out, char *sep) const; ///< print list 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, the old ///< object is deleted and replace with 'new_element'. INLINE void del(T &el); ///< Delete node 'el'. INLINE T &grab(); ///< Remove and return an arbitrary valid element of the set. This ///< raises an error if there are no valid elements. INLINE Boolean member(const T &el) const; ///< Check to see if node 'el' is a member of the RefSet. INLINE Boolean valid(const T &el) const; ///< Check to see if node 'el' is still valid in the RefSet. INLINE Boolean valid(const int loc) const; ///< Check to see if the locth element is valid. INLINE void clear(); ///< Delete the entire list. INLINE RefSet<T> & operator -= (const RefSet<T>& l); ///< Remove one set from another. This operator ///< finds the members of the arg RefSet which are also ///< in the *this RefSet, and removes them from the *this ///< RefSet. The elements of the arg RefSet need not ///< all be contained in the *this RefSet. ///< THIS OPERATOR DECIDES THAT ELEMENTS ARE THE SAME BY ///< COMPARING THEIR ADDRESSES, NOT THEIR CONTENT. THEREFORE, ///< THIS WILL NOT FIND CLONES TO BE THE SAME ELEMENT. ///< THIS IS MOST USEFUL FOR THINGS THAT LIVE IN ONLY ONE ///< PLACE IN THE SYSTEM, FOR INSTANCE, SYMBOLS. INLINE RefSet<T> & operator += (const RefSet<T>& l); ///< Append the members of one set onto another. ///< THIS OPERATOR DECIDES THAT ELEMENTS ARE THE SAME BY ///< COMPARING THEIR ADDRESSES, NOT THEIR CONTENT. THEREFORE, ///< THIS WILL NOT FIND CLONES TO BE THE SAME ELEMENT. ///< THIS IS MOST USEFUL FOR THINGS THAT LIVE IN ONLY ONE ///< PLACE IN THE SYSTEM, FOR INSTANCE, SYMBOLS. INLINE int operator == (const RefSet<T > &l) const; ///< Check for equality between two RefSets: ///< 1. check that # entries is the same ///< 2. check that all members of one are members of the other INLINE RefSet<T >&operator = (const RefSet<T >&l); ///< Copy operator copies all valid elements of a RefSet. 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 #include "Iterator.h" #include "Mutator.h" template <class T> INLINE RefSet<T>::RefSet() { ///< nothing to do } template <class T> INLINE RefSet<T>::RefSet(const RefSet<T >&l) { _list = l._list; } template <class T> INLINE RefSet<T>::~RefSet() { ///< nothing to do } template <class T> INLINE int RefSet<T>::entries() const { return _list.entries(); } template <class T> INLINE Boolean RefSet<T>::empty() const { return (_list.entries() == 0); } template <class T> INLINE void RefSet<T>::print(ostream & out, char *sep) const { out << "{"; _list.print(out, sep); out << "}"; } template <class T> INLINE T & RefSet<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 RefSet<T>::_del(int loc) { _list.del(loc); } template <class T> INLINE void RefSet<T>::_modify(int loc, T &el) { int old_loc = this->_member(el); if (old_loc != loc) { _list.modify(loc, el); if (old_loc != -1) { _list.del(old_loc); } } } template <class T> INLINE void RefSet<T>::del(T &el) { int i = _list.index(el); if (i >= 0) _list.del(i); } template <class T> INLINE T & RefSet<T>::grab() { int num = _list.entries()-1; ///< Find a valid element while (!_list.valid(num)) { _list.del(num); num = _list.entries()-1; } ///< p_assert( num < 0, "Attempting to grab() from an empty RefSet" ); T &el = (T &) _list[num]; _list.del(num); return el; } template <class T> INLINE int RefSet<T>::_member(const T &el) const { return _list.index(el); } template <class T> INLINE Boolean RefSet<T>::member(const T &el) const { return (_list.member(el)); } template <class T> INLINE Boolean RefSet<T>::valid(const int loc) const { return (_list.valid(loc)); } template <class T> INLINE Boolean RefSet<T>::valid(const T &el) const { return (_list.valid(el)); } template <class T> INLINE Boolean RefSet<T>::any_valid() const { for (int i = 0; i < _list.entries(); ++i) if (_list.valid(i)) return 1; return 0; } template <class T> INLINE void RefSet<T>::clear() { _list.clear(); } template <class T> INLINE int RefSet<T>::operator == (const RefSet<T> &l) const { if (entries() != l.entries()) return 0; for (Iterator<T> iter = l; iter.valid(); ++iter) if (!(this->member( iter.current() ))) return 0; return 1; } template <class T> INLINE RefSet<T> & RefSet<T>::operator -= (const RefSet<T> &l) { ///< THIS OPERATOR DECIDES THAT ELEMENTS ARE THE SAME BY ///< COMPARING THEIR ADDRESSES, NOT THEIR CONTENT. THEREFORE, ///< THIS WILL NOT FIND CLONES TO BE THE SAME ELEMENT. ///< THIS IS MOST USEFUL FOR THINGS THAT LIVE IN ONLY ONE ///< PLACE IN THE SYSTEM, FOR INSTANCE, SYMBOLS. for (Iterator<T> iter = l; iter.valid(); ++iter) if (this->member( iter.current() )) { this->del(iter.current()); } return *this; } template <class T> INLINE RefSet<T> & RefSet<T>::operator += (const RefSet<T> &l) { ///< THIS OPERATOR DECIDES THAT ELEMENTS ARE THE SAME BY ///< COMPARING THEIR ADDRESSES, NOT THEIR CONTENT. THEREFORE, ///< THIS WILL NOT FIND CLONES TO BE THE SAME ELEMENT. ///< THIS IS MOST USEFUL FOR THINGS THAT LIVE IN ONLY ONE ///< PLACE IN THE SYSTEM, FOR INSTANCE, SYMBOLS. for (Iterator<T> iter = l; iter.valid(); ++iter) this->ins( iter.current() ); return *this; } template <class T> INLINE RefSet<T> & RefSet<T>::operator = (const RefSet<T> &l) { _list = l._list; return *this; } template <class T> INLINE int RefSet<T>::structures_OK() const { return _list.structures_OK(); } template <class T> INLINE const T & RefSet<T>::_element(int sub) const { return (const T &) _list[sub]; } template <class T> INLINE T & RefSet<T>::_element(int sub) { return (T &) _list[sub]; } template <class T> INLINE const Collection & RefSet<T>::_base_collection() const { return _list; } template <class T> INLINE Collection & RefSet<T>::_base_collection() { return _list; } template <class T> INLINE Listable * RefSet<T>::listable_clone() const { return (Listable *) new RefSet<T>(*this); } template <class T> INLINE void RefSet<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 S> ostream & operator << (ostream & o, const RefSet<S> &s) { s.print(o, ", "); return o; } #endif

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