home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / a_arrays.zip / ASSOC.HPP < prev    next >
Text File  |  1994-10-31  |  13KB  |  287 lines
  1. /***************************************************************
  2.  * file: ASSOC.HPP
  3.  * purpose: template class for associative arrays
  4.  * contains:
  5.  *      ASSOCIATION_BASE - core routines for the ASSOCIATION template
  6.  *      ASSOCIATION - association between strings and data objects
  7.  * copyright: 1994 by David Weber.  Unlimited use granted in EXE, OBJ,
  8.  *  or LIB formats.  Do not sell as source without asking first.
  9.  * environment:
  10.  *  tested Borland C++ 4.01 and Zortech C++ 3.1r2
  11.  * history:
  12.  *  10-02-94 - initial code, based on an earlier C module
  13.  **************************************************************/
  14.  
  15. #ifndef _ASSOC
  16. #define _ASSOC
  17.  
  18. // needed goodies
  19. #include <string.h>
  20.  
  21. // Feature controls
  22. #define ASSOC_CASE_SENSITIVE 1          // string case sensitivity (1 or 0)
  23. #define ASSOC_EXCEPTIONS 0              // environment supports C++ exceptions
  24. #define ASSOC_NEW_CASTS 0               // environment supports new C++ casts
  25.  
  26.  
  27. // case sensitivity - This could be done dynamically with a function ptr in the
  28. //      class, but would disallow the compiler to do optimization via intrinsic
  29. //      function expansion.
  30. #if ASSOC_CASE_SENSITIVE
  31. #define ASSOC_STRCMP strcmp
  32. #define ASSOC_MAP(c) (c)
  33. #else
  34. #include <ctype.h>
  35. #define ASSOC_STRCMP stricmp
  36. #define ASSOC_MAP(c) toupper(c)
  37. #endif
  38.  
  39.  
  40. // The only place exceptions occur are resource failure with the "new" calls.
  41. // If the environment supports C++ exceptions and a failure occurs, a handler
  42. // somewhere, even if it's terminate(), will take care of it.  Without
  43. // exception handling we just shut down the farm via assert() and abort()
  44. #if ASSOC_EXCEPTIONS
  45. #define ASSOC_MEM_CHECK(p)
  46. #else
  47. #include <stdlib.h>
  48. #include <assert.h>
  49. #define ASSOC_MEM_CHECK(p) { if ((p) == 0) { assert((p) != 0); abort(); } }
  50. #endif
  51.  
  52.  
  53. // old versus new casting, not much gained here except you can search for casts
  54. #if ASSOC_NEW_CASTS
  55. #define ASSOC_CAST(cast,item) reinterpret_cast<cast>(item)
  56. #else
  57. #define ASSOC_CAST(cast,item) (cast)(item)
  58. #endif
  59.  
  60.  
  61. // defines
  62. const int DEFAULT_ASSOC_SIZE = 64;      // default estimated size of array
  63. const unsigned int ASSOC_NULL = ~0;     // end of chain
  64.  
  65.  
  66. // The base class for associative arrays.  You should NOT make an instance
  67. // of this class.  Instead use the ASSOCIATON template below
  68. class ASSOCIATION_BASE
  69.     {
  70.     protected:                          // protect everything
  71.         ASSOCIATION_BASE(unsigned int data_size,unsigned int estimated_size);
  72.         ~ASSOCIATION_BASE();            // destructor - make virtual if extending
  73.                                         // inheritance and/or pointing along the chain
  74.         ASSOCIATION_BASE(const ASSOCIATION_BASE &); // copy constructor
  75.         ASSOCIATION_BASE &operator=(const ASSOCIATION_BASE &);  // assignment
  76.         ASSOCIATION_BASE(const char **keys,const char *data,    // static initializer
  77.                         unsigned int data_size,unsigned int count);
  78.         unsigned int size(void)         // how many data elements in array
  79.             { return fill_level; }
  80.         int insert(const char *key,const char *data);// add an element
  81.         int remove(const char *key);    // remove an element
  82.         char *find(const char *key);    // find an element
  83.         const char *first(void);        // traversal functions
  84.         const char *next(void);
  85.         int operator!()                 // test array for problems
  86.             { return hash_list==0 || key_list==0 || link_list==0 || data_list==0; }
  87.         int operator()(const char *key) // existence operator
  88.             { return find(key) != 0; }
  89.         char &operator[](const char *key)// access operator
  90.             { return *reference(key); }
  91.         char *reference(const char *key);// get a reference to data or insert if needed
  92.         unsigned int hash(const char *key);// hash function
  93.         void allocate_array(void);      // get enough space for the array
  94.         int expand_array(void);         // resize array
  95.         void clear_pointers(void)       // clear all pointers
  96.             { hash_list = 0; key_list = 0; link_list = 0; data_list = 0; }
  97.         void delete_pointers(void)      // delete all pointers
  98.             { delete [] hash_list; delete [] key_list; delete [] link_list; delete [] data_list; }
  99.         unsigned int array_size;        // full size of array
  100.         unsigned int fill_level;        // data entries currently in array
  101.         unsigned int *hash_list;        // hash indexed array of chains
  102.         const char **key_list;          // storage for key pointers
  103.         unsigned int *link_list;        // storage for key linkages
  104.         char *data_list;                // storage for data expressed as char
  105.         unsigned int sizeofdata;        // size of data objects in bytes
  106.         unsigned int iteration;         // current iteration position in data
  107.     };
  108.  
  109.  
  110. // ASSOCIATION - associative array template
  111. //  Use this class template for creating instances when you will be
  112. //  storing associations between character strings and data objects.
  113. //  There are three ways to use this template:
  114. //      direct storage - data are stored directly in the associative array.
  115. //          good for small classes or native types
  116. //          ASSOCIATION<myclass> direct_array(estimated_size);
  117. //          value = *direct_array.find("key");
  118. //      indirect storage - pointers to data are stored in the array.
  119. //          good for large classes or pointers to things that vary in size
  120. //          ASSOCIATION<myclass *> indirect_array(estimated_size);
  121. //          ptr_to_value = *indirect_array.find("key");
  122. //          value = **indirect_array.find("key");
  123. //      function pointer storage - pointers to functions are stored.
  124. //          ASSOCIATION<int (*)(int)> func_ptr_array(estimated_size);
  125. //          int (**fptr)(int);
  126. //          if ((fptr = func_ptr_array.find("key")) != 0)   // always test
  127. //              function_return = (**fptr)(parameter);
  128. //  You are responsible for the string storage.  In the case of indirect
  129. //  storage you are also responsible for storing the data.
  130. //  example:
  131. //      ASSOCIATION<myclass> assoc_array(estimated_size);   // declaration
  132. //      if (!assoc_array) { class is unusable; }            // validity
  133. //      assoc_array.insert("xray",myclass_instance1);       // insert, returns 0 on failure
  134. //      assoc_array.insert("yodel",myclass_instance2);
  135. //      assoc_array.insert("zorro",myclass_instance3);
  136. //      assoc_array.remove("yodel");                        // delete, returns 0 if not there
  137. //      cout << "Size is " << assoc_array.size() << "\n";   // size is 2
  138. //      cout << "zorro is " << *assoc_array.find("zorro") << "\n";// find
  139. //      assert(assoc_array.find("garbage") == 0);           // failed find returns 0
  140. //      if ((const char *p = assoc_array.first()) != 0)     // iterate over set
  141. //          {                       // do not insert or remove while iterating
  142. //          do
  143. //              {
  144. //              cout << p << "\t\t" << *assoc_array.find(p) << "\n";
  145. //              } while ((p = assoc_array.next()) != 0);
  146. //          }
  147. //  other uses:
  148. //      copy constructor
  149. //          ASSOCIATION<int> x;     // fill x with stuff
  150. //          ASSOCIATION<int> y(x);
  151. //      assignment
  152. //          ASSOCIATION<int> x;     // fill x with stuff
  153. //          ASSOCIATION<int> y;
  154. //          y = x;
  155. //      static initialization
  156. //          static const char *keys[] = { "key1","key2", "key3" };// note: const
  157. //          static int data[] = { 1,2,3 };
  158. //          ASSOCIATION<int> x(keys,data,sizeof(keys)/sizeof(keys[0]));
  159. template <class T> class ASSOCIATION : public ASSOCIATION_BASE
  160.     {
  161.     public:
  162.         ASSOCIATION(unsigned int estimated_size = DEFAULT_ASSOC_SIZE) :
  163.             ASSOCIATION_BASE(sizeof(T),estimated_size) { }  // default constructor
  164.         // destructor and copy constructor found in ASSOCIATION_BASE
  165.         ASSOCIATION<T> &operator=(const ASSOCIATION<T> &original)// assignment
  166.             { ASSOCIATION_BASE::operator=(original); return *this; }
  167.                                             // static initializer
  168.         ASSOCIATION(const char **keys,T *data,unsigned int count) :
  169.             ASSOCIATION_BASE(keys,ASSOC_CAST(const char *,data),sizeof(T),count) { }
  170.         unsigned int size(void)             // how many data elements in array
  171.             { return fill_level; }
  172.         int insert(const char *key,T data)  // add an element
  173.             { return ASSOCIATION_BASE::insert(key,ASSOC_CAST(const char *,&data)); }
  174.         int remove(const char *key)         // remove an element
  175.             { return ASSOCIATION_BASE::remove(key); }
  176.         T *find(const char *key)            // find an element
  177.             { return ASSOC_CAST(T *,ASSOCIATION_BASE::find(key)); }
  178.         const char *first(void)             // traversal functions
  179.             { return ASSOCIATION_BASE::first(); }
  180.         const char *next(void)
  181.             { return ASSOCIATION_BASE::next(); }
  182.         int operator!()                     // test array for problems
  183.             { return ASSOCIATION_BASE::operator!(); }
  184.         int operator()(const char *key)     // existence operator
  185.             { return ASSOCIATION_BASE::find(key) != 0; }
  186.         T &operator[](const char *key)      // access operator
  187.             { return *(ASSOC_CAST(T *,ASSOCIATION_BASE::reference(key))); }
  188.     };
  189.  
  190.  
  191. // ASSOC_STORED - ASSOCIATION class with storage for keys
  192. // This class is almost identical to ASSOCIATION except that it maintains the
  193. // storage for the keys.  The interface is the same but the static initializer
  194. // is left out.  If it is static, the keys are already stored. So why bother?
  195. template <class T> class ASSOC_STORED : public ASSOCIATION_BASE
  196.     {
  197.     public:
  198.         ASSOC_STORED(unsigned int estimated_size = DEFAULT_ASSOC_SIZE) :
  199.             ASSOCIATION_BASE(sizeof(T),estimated_size) { }  // default constructor
  200.         ~ASSOC_STORED();                    // destructor
  201.         ASSOC_STORED(const ASSOC_STORED<T> &original) : ASSOCIATION_BASE(original)
  202.             { dup_keys(); }                 // copy constructor
  203.         ASSOC_STORED<T> &operator=(const ASSOC_STORED<T> &original)
  204.             {                               // assignment
  205.             ASSOCIATION_BASE::operator=(original);
  206.             dup_keys();
  207.             return *this;
  208.             }
  209.         unsigned int size(void)             // how many data elements in array
  210.             { return fill_level; }
  211.         int insert(const char *key,T data)  // add an element
  212.             {
  213.             if (key == 0)
  214.                 return 0;
  215.             char *p = new char[strlen(key)+1];
  216.             ASSOC_MEM_CHECK(p);
  217.             strcpy(p,key);
  218.             return ASSOCIATION_BASE::insert(p,ASSOC_CAST(const char *,&data));
  219.             }
  220.         int remove(const char *key);        // remove an element
  221.         T *find(const char *key)            // find an element
  222.             { return ASSOC_CAST(T *,ASSOCIATION_BASE::find(key)); }
  223.         const char *first(void)             // traversal functions
  224.             { return ASSOCIATION_BASE::first(); }
  225.         const char *next(void)
  226.             { return ASSOCIATION_BASE::next(); }
  227.         int operator!()                     // test array for problems
  228.             { return ASSOCIATION_BASE::operator!(); }
  229.         int operator()(const char *key)     // existence operator
  230.             { return ASSOCIATION_BASE::find(key) != 0; }
  231.         T &operator[](const char *key)      // access operator
  232.             {
  233.             char *p = ASSOCIATION_BASE::find(key);
  234.             if (p == 0)
  235.                 {
  236.                 if (key == 0)
  237.                     return *(ASSOC_CAST(T *,0));// garbage in, garbage out
  238.                 char *p = new char[strlen(key)+1];
  239.                 ASSOC_MEM_CHECK(p);
  240.                 strcpy(p,key);
  241.                 return *(ASSOC_CAST(T *,ASSOCIATION_BASE::reference(p)));
  242.                 }
  243.             return *(ASSOC_CAST(T *,p));
  244.             }
  245.     private:
  246.         void dup_keys(void);
  247.     };
  248. // functions out of line cuz looped, large and/or called infrequently
  249. // destructor
  250. template <class T> ASSOC_STORED<T>::~ASSOC_STORED()
  251.     {
  252.     for (unsigned int i = 0 ; i < fill_level ; i++)
  253.         delete [] ASSOC_CAST(char *,key_list[i]);
  254.     }
  255. // remove
  256. template <class T> int ASSOC_STORED<T>::remove(const char *key)
  257.     {
  258.     char *data = ASSOCIATION_BASE::find(key);
  259.     if (data != 0)
  260.         {
  261.         data = ASSOC_CAST(char *,key_list[(data-data_list)/sizeofdata]);
  262.         if (ASSOCIATION_BASE::remove(key))
  263.             {
  264.             delete [] data;
  265.             return 1;
  266.             }
  267.         }
  268.     return 0;
  269.     }
  270. // duplicate the full set of keys
  271. template <class T> void ASSOC_STORED<T>::dup_keys(void)
  272.     {
  273.     char *newkey;
  274.     const char *oldkey;
  275.  
  276.     for (unsigned int i = 0 ; i < fill_level ; i++)
  277.         {       // duplicate keys
  278.         oldkey = key_list[i];
  279.         newkey = new char[strlen(oldkey)+1];
  280.         ASSOC_MEM_CHECK(newkey);
  281.         strcpy(newkey,oldkey);
  282.         key_list[i] = newkey;
  283.         }
  284.     }
  285.  
  286. #endif  // _ASSOC
  287.