home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / yacl-012.zip / base / map.h < prev    next >
C/C++ Source or Header  |  1995-04-08  |  14KB  |  401 lines
  1.  
  2.  
  3. #ifndef _map_h_ /* Tue Jan 26 22:08:12 1993 */
  4. #define _map_h_
  5.  
  6.  
  7.  
  8.  
  9.  
  10. /*
  11.  *
  12.  *          Copyright (C) 1994, M. A. Sridhar
  13.  *  
  14.  *
  15.  *     This software is Copyright M. A. Sridhar, 1994. You are free
  16.  *     to copy, modify or distribute this software  as you see fit,
  17.  *     and to use  it  for  any  purpose, provided   this copyright
  18.  *     notice and the following   disclaimer are included  with all
  19.  *     copies.
  20.  *
  21.  *                        DISCLAIMER
  22.  *
  23.  *     The author makes no warranties, either expressed or implied,
  24.  *     with respect  to  this  software, its  quality, performance,
  25.  *     merchantability, or fitness for any particular purpose. This
  26.  *     software is distributed  AS IS.  The  user of this  software
  27.  *     assumes all risks  as to its quality  and performance. In no
  28.  *     event shall the author be liable for any direct, indirect or
  29.  *     consequential damages, even if the  author has been  advised
  30.  *     as to the possibility of such damages.
  31.  *
  32.  */
  33.  
  34.  
  35.  
  36.  
  37. #ifdef __GNUC__
  38. #pragma interface
  39. #endif
  40.  
  41.  
  42. #include "base/objseq.h"
  43. #include "base/iterator.h"
  44. #include "base/string.h"
  45.  
  46.  
  47. template <class KeyClass, class ValueClass>
  48. class CL_EXPORT  CL_MapIterator;
  49.  
  50.  
  51. // A MapAssoc is simply a key-value pair that functions as a single entry
  52. // in a map.
  53.  
  54. template <class KeyClass, class ValueClass>
  55. class CL_EXPORT  CL_MapAssoc: public CL_Object {
  56.  
  57. public:
  58.     KeyClass key;
  59.     ValueClass value;
  60.  
  61.     CL_MapAssoc ();
  62.     // Default constructor.
  63.  
  64.     CL_MapAssoc (const KeyClass& k, const ValueClass& v);
  65.     // Build a MapAssoc with given key and value.
  66.     
  67.     CL_MapAssoc (const CL_MapAssoc<KeyClass,ValueClass>& a);
  68.     // Copy constructor.
  69.  
  70.     ~CL_MapAssoc () {};
  71.     
  72.     void operator= (const CL_Object& o)
  73.     { if (CheckClassType (o, "CL_MapAssoc::op="))
  74.             *this = ((const CL_MapAssoc<KeyClass, ValueClass>&) o); };
  75.     // Override method inherited from {\small\tt CL_Object}. The
  76.     // implementation checks that o's class id is the same as ours, casts
  77.     // down o and invokes the MapAssoc assignment.
  78.  
  79.     void operator= (const CL_MapAssoc<KeyClass,ValueClass>& o);
  80.  
  81.     short Compare (const CL_Object& o) const;
  82.  
  83.     CL_String AsString () const;
  84.  
  85.     // --------------------- Basic operations ---------------------
  86.     
  87.     CL_Object* Clone () const
  88.         { return new CL_MapAssoc<KeyClass, ValueClass> (*this); };
  89.     // Override the method inherited from {\small\tt CL_Object}.
  90.  
  91.     const char* ClassName () const {return "CL_MapAssoc";};
  92.     // Override the method inherited from {\small\tt CL_Object}.
  93.     
  94.  
  95.  
  96. };
  97.  
  98.  
  99.  
  100.  
  101. // This is a  Map class, that  maintains a key-value mapping.  Duplicate keys
  102. // are {\it not\/}   allowed.  Keys must  be   objects that  define the  {\tt
  103. // Compare()} method (or pointers to such objects), and values must belong to
  104. // a class which provides a default constructor.  (A value object constructed
  105. // with its  default constructor is thought  of as a  {\it null\/} value, and
  106. // returned  when the map  lookup for a key fails.)   All methods that return
  107. // boolean values return TRUE on success and FALSE on error.
  108. // 
  109. // A Map stores MapAssoc objects, which are key-value pairs.
  110. // 
  111. // A MapIterator object is also provided; this object allows inspecting
  112. // the  key-value pairs (associations) contained in  a  map, in ascending
  113. // order of  keys.  It  provides methods Reset(),  More() and  Next(), so
  114. // that iteration in the following form is possible:
  115. // \par\begin{verbatim}
  116. //           CL_StringIntMapIterator iter (myMap);
  117. //           CL_StringIntAssoc assoc;
  118. //           for (iter.Reset(); iter.More(); ) {
  119. //               assoc = iter.Next();
  120. //               // Process the pair "assoc" here....
  121. //           }
  122. // \end{verbatim}
  123. // Associations returned by the Next() method of  the iterator may NOT be
  124. // modified. It is not  advisable to remove  elements from a map while an
  125. // iterator on the map is active.
  126. //
  127. // When the Map is instantiated as a container for pointers (as are
  128. // several maps -- see {\tt mapdef.h}), the map
  129. // does {\it not\/} own the objects that the pointers point to, and
  130. // therefore does not delete them when it is destroyed. The MapIterator
  131. // can be used to iterate over the map's contents and destroy pointed-to
  132. // objects.
  133. //
  134. // The implementation uses a sorted {\small\tt CL_Sequence}, so that it is
  135. // possible to create maps with size up to $2^{26}$, or approximately 64
  136. // million, even under MS-Windows, thus alleviating the 64K  limitation
  137. // under MS-Windows (provided, of course, there is enough main memory
  138. // available).
  139.  
  140.  
  141.  
  142. template <class KeyClass, class ValueClass>
  143. class CL_EXPORT  CL_Map: public CL_Object {
  144.  
  145. public:
  146.  
  147.     // ---------------------- Construction and destruction ---------------
  148.  
  149.     CL_Map (CL_MapAssoc<KeyClass, ValueClass> *assoc_array, long count, 
  150.             CL_ObjectIOFilter* key_builder = 0,
  151.             CL_ObjectIOFilter* value_builder = 0);
  152.     // Convenience constructor: build a map from a C-style array of
  153.     // associations.
  154.     
  155.     CL_Map (CL_ObjectIOFilter* key_builder = 0,
  156.             CL_ObjectIOFilter* value_builder = 0);
  157.     // Default constructor: build an empty map. The builder objects are used
  158.     // only if this map uses a pointer to a CL_Object (or derivative) for
  159.     // either key or value; and they are used only when the map needs to be
  160.     // restored from a stream. The builder objects are {\it not\/} owned by
  161.     // this map, but must exist as long as the map does. 
  162.  
  163.     CL_Map (const CL_Map<KeyClass,ValueClass>& s);
  164.     // Copy constructor.
  165.  
  166.     ~CL_Map ();
  167.     // Destructor.
  168.     
  169.     //
  170.     // ---------------------- Element access -----------------------------
  171.     //
  172.  
  173.     inline long Size () const;
  174.     // Return the number of entries in the map.
  175.     
  176.     virtual bool IncludesKey (const KeyClass& key) const;
  177.     // Tell whether the map includes the given key.
  178.  
  179.     virtual ValueClass& operator[]  (const KeyClass& key);
  180.     // Return the value associated with the given key. The
  181.     // return value is a reference, and may be modified, resulting in
  182.     // modification of the map. If the key is not found, this operator
  183.     // returns a reference to an object of type ValueClass whose value
  184.     // is the null value of the ValueClass.
  185.     //
  186.     // The implementation uses binary search when the number of keys exceeds
  187.     // seven.
  188.  
  189.     virtual const ValueClass& operator[] (const KeyClass& key) const;
  190.     // Same as the other operator[], except that this is a const method.
  191.     
  192.     virtual const CL_MapAssoc<KeyClass,ValueClass>& ItemWithRank (long i)
  193.         const;
  194.     // Given an index $i$ between 0 and Size()-1, return the Assoc of rank
  195.     // $i$, i.e., the Assoc that has $i$ keys less than it in the map.
  196.     // If $i \le 0$, this returns the Assoc with smallest key, and if $i
  197.     // \ge {\tt Size()}$, this returns the one with the largest key.
  198.     //
  199.     // This is a const method; even if this
  200.     // is a map of pointers, it is not safe to modify the object pointed
  201.     // to by the return value because the map's internal representation
  202.     // may be affected and its algorithms may perform incorrectly.
  203.     //   Note that it is possible to iterate through the elements of the map
  204.     // via calls to this method, varying the index from 0 to Size()-1;
  205.     // however, depending on the implementation, this may lead to very
  206.     // inefficient iteration. Use of the MapIterator is the recommended way
  207.     // to inspect all elements of the set.
  208.     
  209.     virtual long RankOf (const KeyClass& k) const;
  210.     // Return the number of MapAssoc's in this map whose keys less than k.
  211.     // The key k need not be in the map. The ordering
  212.     // relationship used is that defined by {\tt KeyClass};
  213.     // if the latter does not define a Compare method or an {\tt
  214.     // operator<} method, this method does not return anything useful.
  215.     
  216.     
  217.     // ------------------------- Modification ---------------------------
  218.  
  219.     virtual bool Add  (const KeyClass& key, const ValueClass& value);
  220.     // Add a key-value pair to the map. 
  221.  
  222.     virtual CL_MapAssoc<KeyClass, ValueClass> Remove  (const KeyClass& key);
  223.     // Remove the given key and its associated value from the map. Return
  224.     // the Assoc that was removed; return the null value of the MapAssoc if
  225.     // the removal failed.
  226.  
  227.     virtual void MakeEmpty ();
  228.     // Remove all the key-value pairs in the map. If this map uses
  229.     // pointers in either key or value, the pointed-to objects are {\it
  230.     // not\/} deleted.
  231.  
  232.     virtual void DestroyContents ();
  233.     // Remove all key-value pairs  in the map. If this map uses
  234.     // pointers in either key or value, the pointed-to objects {\it are\/}
  235.     // deleted.
  236.     
  237.     void operator= (const CL_Map<KeyClass,ValueClass>&);
  238.     // Assign the given map to ourselves.
  239.     
  240.     void operator= (const CL_Object& o);
  241.     // Check that the given object has the same class id as this one,
  242.     // and then perform a map assignment after casting down.
  243.     
  244.  
  245.     // -------------------- Storage and retrieval ---------------------
  246.  
  247.     long StorableFormWidth () const;
  248.     // Override the method inherited from {\small\tt CL_Object}.
  249.  
  250.     bool ReadFrom (const CL_Stream&);
  251.     // Override the method inherited from {\small\tt CL_Object}.
  252.  
  253.     bool WriteTo  (CL_Stream&) const;
  254.     // Override the method inherited from {\small\tt CL_Object}.
  255.  
  256.     void IntoStream (ostream& strm) const;
  257.     // Override the method inherited from {\small\tt CL_Object}.
  258.  
  259.     
  260.     //
  261.     // -------------------- Basic inherited methods ---------------------
  262.     //
  263.     CL_Object* Clone () const
  264.         {return new CL_Map<KeyClass,ValueClass> (*this);};
  265.     // Override the method inherited from {\small\tt CL_Object}.
  266.     
  267.     virtual const char* ClassName() const
  268.         { return "CL_Map";};
  269.     // Override the method inherited from {\small\tt CL_Object}.
  270.     
  271.     virtual CL_ClassId ClassId () const
  272.         {return _CL_Map_CLASSID;};
  273.     // Override the method inherited from {\small\tt CL_Object}.
  274.  
  275.  
  276.  
  277.  
  278.     // -------------------- End public protocol -------------------------
  279.  
  280. protected:
  281.  
  282.     // -------------------- Friend declarations ----------------------
  283.     
  284.     friend CL_MapIterator<KeyClass,ValueClass>;
  285.  
  286.  
  287.     // -------------------- Protected methods -------------------------
  288.  
  289.     virtual CL_MapAssoc<KeyClass,ValueClass>*  _ReadAssoc (const CL_Stream&)
  290.         const;
  291.     // Read the data for a single MapAssoc, reconstruct it in a new object,
  292.     // and return it. If the read fails, return a NULL pointer. This method
  293.     // is called by {\tt ReadFrom}. The default implementation uses the
  294.     // _keyBuilder and _valueBuilder variables if necessary.
  295.  
  296.     virtual bool _WriteAssoc (CL_Stream& s, const
  297.                               CL_MapAssoc<KeyClass,ValueClass>& assoc)
  298.         const;
  299.     // Write a single MapAssoc value into the stream. This method is called
  300.     // for each contained Assoc by the {\tt WriteTo} method. 
  301.  
  302.     // -------------------- Instance variables -----------------------
  303.     
  304.     CL_MapAssoc<KeyClass, ValueClass> _null;
  305.     CL_ObjectSequence                 _data;
  306.     CL_ObjectIOFilter*                _keyBuilder;
  307.     CL_ObjectIOFilter*                _valueBuilder;
  308.  
  309. };
  310.  
  311.  
  312.  
  313.  
  314. // This is MapIterator, that allows iteration over all entries in a map.
  315.  
  316. template <class KeyClass, class ValueClass>
  317. class CL_EXPORT CL_MapIterator: public CL_Iterator<CL_MapAssoc<KeyClass, ValueClass> > {
  318.  
  319. public:
  320.     CL_MapIterator (const CL_Map<KeyClass,ValueClass>& map);
  321.  
  322.     CL_MapIterator (const CL_MapIterator<KeyClass, ValueClass>& itr);
  323.     // Copy constructor. The copy inspects the same map as {\tt itr}, and
  324.     // (unless reset) begins  its iteration at the  Assoc at which {\tt itr}
  325.     // is currently positioned.
  326.     
  327.     void Reset ();
  328.     // Reset the iterator to the beginning (lowest-valued key). The next
  329.     // call to Next() will return the Assoc with the lowest-valued key.
  330.  
  331.     virtual void BeginFromRank (long i);
  332.     // Start the iteration so that the first call to {\tt Next} returns the
  333.     // Assoc of rank i. Thus {\tt BeginFromRank(0)} is equivalent to {\tt
  334.     // Reset()}.
  335.     
  336.     bool More  ();
  337.     // Return TRUE if there are more Assoc's in the map we're
  338.     // inspecting.
  339.     
  340.     const CL_MapAssoc<KeyClass, ValueClass>& Next ();
  341.     // Return a reference to the next Assoc in the iteration. It is
  342.     // NOT safe to modify the key in the returned Assoc, although the
  343.     // value may be modified.
  344.  
  345.  
  346.  
  347. protected:
  348.     const CL_Map<KeyClass,ValueClass>&  _map;
  349.     long                                _index;
  350.  
  351. };
  352.  
  353.  
  354.  
  355.  
  356.  
  357. // ---------------------- Inline functions ------------------------
  358.  
  359.  
  360.  
  361. template <class KeyClass, class ValueClass>
  362. inline long CL_Map<KeyClass, ValueClass>::Size () const
  363. {
  364.     return _data.Size ();
  365. }
  366.  
  367.  
  368.  
  369.  
  370. template <class KeyClass, class ValueClass>
  371. inline long CL_Map<KeyClass, ValueClass>::StorableFormWidth () const
  372. {
  373.     return sizeof (CL_ClassId) + _data.StorableFormWidth ();
  374. }
  375.  
  376.  
  377.  
  378.  
  379.  
  380. template <class KeyClass, class ValueClass>
  381. inline void CL_Map<KeyClass, ValueClass>::operator= (const CL_Object& o)
  382. {
  383.     if (CheckClassType (o, "CL_Map::op="))
  384.         *this = ((const CL_Map<KeyClass, ValueClass>&) o);
  385. }
  386.  
  387.  
  388.  
  389.  
  390.  
  391.  
  392.  
  393. #ifndef _no_cl_map_typedefs_ /* Fri Nov 19 14:31:53 1993 */
  394. #include "base/mapdef.h"
  395. #endif /* _no_cl_map_typedefs_ */
  396.  
  397.  
  398. #endif  /* _map_h_ */
  399.  
  400.  
  401.