Polaris: BaseMapRoot.h Source File

BaseMapRoot.h Go to the documentation of this file. /// /// #ifndef _BASE_MAP_ROOT_H #define _BASE_MAP_ROOT_H /// /// \class BaseMapRoot /// \brief The underlying tree structure for Maps /// \defgroup Polaris /// \ingroup Polaris /// C++ VDL /// \see BaseMapNode.h /// \see BaseMapRoot.h /// \see BaseMapRoot.cc /// /// \endcode /// \section Overview Overview /// BaseMapRoot is an abstract base class for a map of keys /// to objects of type Listable. The internal nodes and /// descriptions of the key objects are described in BaseMapNode.h. /// BaseMapRoot is the base of a wide variety of Maps and /// Databases with full functionality, however, this class can /// not be used on its own. Derived classes can be used as /// follows: /// /// \code /// 1. BaseMapRoot should be used to define other BaseMap classes /// (BaseMap & BaseRefMap) which will define _list_remove and /// _list_insert. /// /// 2. The pure virtual functions _kill_key, _less, _equal and _print have /// been defined in the class derived from BaseMapRoot. /// \endcode /// /// \endcode /// \section Not Not Really a Collection /// BaseMapRoot is not really a part of the Collection hierarchy in the /// strictest sense. Instead it is a tree implementation which is fairly /// independent of the world of Collections. It only inherits from Listable /// to allow all Maps to be placed in Collections. The Map classes only /// really join the Collection structure when BaseMap and BaseRefMap inherit /// from BaseMapRoot and also contain an internal Collection strucutre which /// is used to keep track of elements. /// /// \endcode /// \section Hierarchy Hierarchy Structure /// BaseMapRoot is the base of a long inheritance chain which eventually /// results in usable classes. The hierarchy can be modeled as follows: /// /// \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 References References /// The routines used in this class are derived from algorithms given in /// pseudocode form in Chapters 13 and 14 of "Introduction to Algorithms" /// by Cormen, Leiserson and Rivest. /// /// \endcode /// \section See See Also /// BaseMapNode, Listable, BaseMap, BaseRefMap /// #ifdef POLARIS_GNU_PRAGMAS #pragma interface #endif /// #include "../Listable.h" #include "../Boolean.h" #include "Wrapper.h" #include "BaseMapNode.h" /// enum BM_NODE_TYPE { /// type of base map node NONROOT = 0, /// node contains a parent pointer ROOT = 1 /// node contains a map pointer }; /// enum BASE_MAP_POS { /// insertion position of node from ptr TOP, /// node should be inserted as root LEFT, /// node should be inserted as lc of ptr RIGHT, /// node should be inserted as rc of ptr MATCH /// matching node pointed to by ptr }; /// struct BMPosition { /// position of node BASE_MAP_POS _type; /// type of position BMNode *_ptr; /// pointer to match or parent }; /// class BaseMapIter; class BaseMapRoot : public Listable { private: int _entries; ///< number of entries in map BMNode *_root; ///< ptr to root (sentinel if empty tree) BMNode *_sentinel; ///< pointer to sentinel Boolean _own_key; ///< Are the keys owned by the map? friend class BaseMapIter; friend ostream & operator << (ostream &o, const BMNode &node); ///< Boolean _check_node(const BMNode *node, const BMNode *parent_node, /*&*/ int black_height) const; ///< check node and children for testing purposes void _kill_node(BMNode *node); ///< kill node and children (this also kills data) inline Boolean _leaf(const BMNode *z) const; ///< find if leaf node void _left_rotate(BMNode *x); ///< perform left rotation BMNode *_minimum(const BMNode *z) const; ///< find a minimum node BMNode *_maximum(const BMNode *z) const; ///< find a minimum node void _print_node(ostream &o, const BMNode &node) const; ///< print node void _right_rotate(BMNode *x); ///< perform right rotation protected: BMNode *_successor(const BMNode *z) const; ///< find successor node void _position(const BMKey &pos_key, BMPosition &pos) const; ///< set position to node with key pos_key void _first(BMPosition &first) const; ///< set position to first node void _last(BMPosition &last) const; ///< set position to last node virtual void _list_insert(BMNode *z, Listable *new_data) = 0; ///< Insert new_data into the internal list. Set z's _data field ///< to point to new_data's wrapper. virtual void *_list_remove(Wrapper *rem_wrap); ///< Remove node y's data from the internal list. virtual void _list_delete(Wrapper *del_wrap); ///< Delete node y's data from the internal list. virtual void _kill_key(BMKey &key); ///< kill key virtual void _kill_data(void *data); ///< kill data virtual Boolean _less(const BMKey &key1, const BMKey &key2) const = 0; ///< less than compare virtual Boolean _equal(const BMKey &key1, const BMKey &key2) const = 0; ///< equal compare virtual void _print(ostream &o, const BMKey &key) const = 0; ///< print map node inline Boolean _owned_keys() const; ///< Are the keys owned by the map? inline void _set_owned_keys(Boolean truth); ///< Set the above condition. inline const BMKey *_arb_bmkey_ref() const; ///< return an arbitrary node in the tree, or 0 if the tree is empty public: friend ostream & operator << (ostream &o, const BaseMapRoot &map); ///< For testing purposes only BaseMapRoot(); virtual ~BaseMapRoot(); inline int entries() const; ///< Return the number of elements in the BaseMap. void *key_ref( Listable *data ) const; ///< Return a pointer to data's key or 0 if none. int ins(BMKey &new_key, Listable *new_data); ///< Insert a node with key new_key and data new_data. ///< If a node already exists with an equivalent key, do nothing ///< and return 0, otherwise insert and return 1. void *remove(BMKey &del_key); ///< delete a node with key del_key, if such a node is present, ///< otherwise do nothing and return 0 Listable *find_ref(const BMKey &find_key) const; ///< find data of node with key of find_key, or 0 if no such node Boolean member(const BMKey &mem_key) const; ///< Return a flag indicating if there is a node with key mem_key inline void clear(); ///< clear the entire map 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. }; ///< implementation ///< Find if leaf node inline Boolean BaseMapRoot::_leaf(const BMNode *z) const { return (z == _sentinel); } ///< Clear out map inline void BaseMapRoot::clear() { if (_entries>0) { _kill_node(_root); _root = _sentinel; } } ///< Return number of entries inline int BaseMapRoot::entries() const { return _entries; } inline Boolean BaseMapRoot::_owned_keys() const { return _own_key; } inline void BaseMapRoot::_set_owned_keys(Boolean truth) { _own_key = truth; } inline const BMKey * BaseMapRoot::_arb_bmkey_ref() const { if (entries() == 0) return 0; return (_leaf(_root) ? 0 : &_root->_key); } #endif

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