home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1999 March / PCWK3A99.iso / Linux / DDD331 / DDD-3_1_.000 / DDD-3_1_ / ddd-3.1.1 / ddd / Assoc.h < prev    next >
Encoding:
C/C++ Source or Header  |  1998-11-24  |  6.6 KB  |  338 lines
  1. // $Id: Assoc.h,v 1.16 1998/11/24 16:42:53 zeller Exp $
  2. // Associative array
  3.  
  4. // Copyright (C) 1995-1998 Technische Universitaet Braunschweig, Germany.
  5. // Written by Andreas Zeller <zeller@ips.cs.tu-bs.de>.
  6. // 
  7. // This file is part of the ICE Library.
  8. // 
  9. // The ICE Library is free software; you can redistribute it and/or
  10. // modify it under the terms of the GNU Library General Public
  11. // License as published by the Free Software Foundation; either
  12. // version 2 of the License, or (at your option) any later version.
  13. // 
  14. // The ICE Library is distributed in the hope that it will be useful,
  15. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  16. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  17. // See the GNU Library General Public License for more details.
  18. // 
  19. // You should have received a copy of the GNU Library General Public
  20. // License along with the ICE Library -- see the file COPYING.LIB.
  21. // If not, write to the Free Software Foundation, Inc.,
  22. // 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  23. // 
  24. // ICE is the incremental configuration environment.
  25. // For details, see the ICE World-Wide-Web page, 
  26. // `http://www.cs.tu-bs.de/softech/ice/',
  27. // or send a mail to the ICE developers <ice@ips.cs.tu-bs.de>.
  28.  
  29. #ifndef _ICE_Assoc_h
  30. #define _ICE_Assoc_h
  31.  
  32. #if defined(__GNUC_MINOR__) && (__GNUC_MINOR__ >= 5)
  33. #pragma interface
  34. #endif
  35.  
  36. #include "bool.h"
  37. #include "assert.h"
  38.  
  39. #include <stdlib.h>        // abort()
  40.  
  41. template<class K, class V> class AssocMark;
  42. template<class K, class V> class _Assoc;
  43. template<class K, class V> class Assoc;
  44. template<class K, class V> class AssocIter;
  45.  
  46. template<class K, class V>
  47. class AssocRec {
  48.     friend class _Assoc<K,V>;
  49.     friend class Assoc<K,V>;
  50.     friend class AssocIter<K,V>;
  51.  
  52. private:
  53.     AssocRec<K,V> *next;        // For Assoc usage only
  54.  
  55. public:
  56.     K key;
  57.     V value;
  58.     
  59.     // Constructor
  60.     AssocRec(const K& k, const V& v)
  61.     : next(0), key(k), value(v)
  62.     {}
  63.     AssocRec(const K& k)
  64.     : next(0), key(k)
  65.     {}
  66.  
  67. private:
  68.     AssocRec(const AssocRec<K, V>& x)
  69.     : next(0), key(x.key), value(x.value)
  70.     {
  71.     assert(0);
  72.     }
  73.     AssocRec<K,V>& operator = (const AssocRec<K, V>&)
  74.     {
  75.     assert(0); return *this;
  76.     }
  77. };
  78.  
  79. template<class K, class V>
  80. class _Assoc {
  81.     friend class AssocMark<K,V>;
  82.  
  83. protected:
  84.     AssocRec<K,V> *entries;    // Entries
  85.  
  86.     virtual AssocRec<K,V> *lookup(const K& key) const
  87.     {
  88.     for (AssocRec<K,V> *e = entries; e != 0; e = e->next)
  89.         if (key == e->key)
  90.         return e;
  91.  
  92.     return 0;
  93.     }
  94.  
  95.     virtual AssocRec<K,V> *insert(const K& key)
  96.     {
  97.     AssocRec<K,V> *e = new AssocRec<K,V>(key);
  98.     e->next = entries;
  99.     return entries = e;
  100.     }
  101.  
  102. public:
  103.     // Constructors
  104.     _Assoc():
  105.     entries(0)
  106.     {}
  107.  
  108.     // Destructor
  109.     virtual ~_Assoc()
  110.     {
  111.     AssocRec<K,V> *next = 0;
  112.     for (AssocRec<K,V> *e = entries; e != 0; e = next)
  113.     {
  114.         next = e->next;
  115.         delete e;
  116.     }
  117.     }
  118.  
  119.     // Resources
  120.  
  121.     // Access (or create) element KEY
  122.     V& operator[] (const K& key)
  123.     {
  124.     AssocRec<K,V> *e = lookup(key);
  125.     if (e == 0)
  126.         e = insert(key);
  127.     return e->value;
  128.     }
  129.  
  130.     // Access element KEY; abort if non-existent
  131.     const V& operator[] (const K& key) const
  132.     {
  133.     AssocRec<K,V> *e = lookup(key);
  134.     if (e == 0)
  135.         abort();
  136.     return e->value;
  137.     }
  138.  
  139.     // Add element KEY
  140.     void add(const K& key)
  141.     {
  142.     insert(key);
  143.     }
  144.  
  145.     // Check if element KEY is present
  146.     bool has(const K& key) const
  147.     {
  148.     return lookup(key) != 0;
  149.     }
  150.  
  151.     // Remove up to N elements KEY
  152.     void remove(const K& key, int n = -1)
  153.     {
  154.     if (n == 0)
  155.         return;
  156.  
  157.     AssocRec<K,V> *prev = 0;
  158.     AssocRec<K,V> *e = entries;
  159.     while (e != 0)
  160.     {
  161.         AssocRec<K,V> *next = e->next;
  162.  
  163.         if (key == e->key)
  164.         {
  165.         if (prev == 0)
  166.             entries = next;
  167.         else
  168.             prev->next = next;
  169.         delete e;
  170.  
  171.         if (--n == 0)
  172.             return;
  173.         }
  174.         else
  175.         {
  176.         prev = e;
  177.         }
  178.  
  179.         e = next;
  180.     }
  181.     }
  182.  
  183.     // Copy constructor
  184.     _Assoc(const _Assoc<K,V>& m):
  185.     entries(0)
  186.     {
  187.     for (AssocRec<K,V> *e = m.entries; e != 0; e = e->next)
  188.         (*this)[e->key] = e->value;
  189.     }
  190.  
  191.     // Assignment
  192.     _Assoc<K, V>& operator = (const _Assoc<K,V>& m)
  193.     {
  194.     if (this != &m)
  195.     {
  196.         if (entries)
  197.         delete entries;
  198.         entries = 0;
  199.  
  200.         for (AssocRec<K,V> *e = m.entries; e != 0; e = e->next)
  201.         (*this)[e->key] = e->value;
  202.     }
  203.  
  204.     return *this;
  205.     }
  206. };
  207.  
  208.  
  209. template<class K, class V>
  210. class AssocMark {
  211.     friend class Assoc<K,V>;
  212.  
  213. protected:
  214.     AssocRec<K,V> *rec;
  215.  
  216.     AssocMark(AssocRec<K,V> *ptr):
  217.     rec(ptr)
  218.     {}
  219.  
  220. public:
  221.     AssocMark(const Assoc<K,V>& assoc):
  222.     rec(assoc.entries)
  223.     {}
  224.     AssocMark(const AssocMark<K,V>& mark):
  225.     rec(mark.rec)
  226.     {}
  227.     AssocMark<K,V>& operator = (const Assoc<K,V>& assoc)
  228.     {
  229.     rec = assoc.entries;
  230.     return *this;
  231.     }
  232.     AssocMark<K,V>& operator = (const AssocMark<K,V>& mark)
  233.     {
  234.     rec = mark.rec;
  235.     return *this;
  236.     }
  237. };
  238.  
  239.  
  240. template<class K, class V>
  241. class AssocIter: public AssocMark<K,V> {
  242. protected:
  243.     AssocIter(AssocRec<K,V> *ptr):
  244.     AssocMark<K,V>(ptr)
  245.     {}
  246.  
  247. public:
  248.     AssocIter(const Assoc<K,V>& assoc):
  249.     AssocMark<K,V>(assoc)
  250.     {}
  251.     AssocIter(const AssocIter<K,V>& iter):
  252.     AssocMark<K,V>(iter)
  253.     {}
  254.     AssocIter<K,V>& operator = (const Assoc<K,V>& assoc)
  255.     {
  256.     AssocMark<K,V>::operator = (assoc);
  257.     return *this;
  258.     }
  259.     AssocIter<K,V>& operator = (const AssocIter<K,V>& iter)
  260.     {
  261.     AssocMark<K,V>::operator = (iter);
  262.     return *this;
  263.     }
  264.  
  265.     const K& key() const   { return rec->key;   }
  266.     const V& value() const { return rec->value; }
  267.     V& value()             { return rec->value; }
  268.  
  269.     bool ok() { return rec != 0; }
  270.     AssocIter<K,V> next() { return AssocIter<K,V>(rec->next); }
  271.     const AssocIter<K,V>& operator ++ ()
  272.     {
  273.     rec = rec->next; return *this;
  274.     }
  275.     const AssocIter<K,V> operator ++ (int)
  276.     {
  277.     AssocIter<K,V> old(*this);
  278.     rec = rec->next;
  279.     return old;
  280.     }
  281. };
  282.  
  283.  
  284. template<class K, class V>
  285. class Assoc: public _Assoc<K, V>
  286. {
  287. protected:
  288.     AssocRec<K,V> *lookup(const K& key) const
  289.     {
  290.     return _Assoc<K, V>::lookup(key);
  291.     }
  292.  
  293.     AssocRec<K,V> *insert(const K& key)
  294.     {
  295.     return _Assoc<K, V>::insert(key);
  296.     }
  297.  
  298. public:
  299.     // Truncate array up to assoc iterator
  300.     void release (const AssocMark<K, V>& mark)
  301.     {
  302.     AssocRec<K, V> *e = entries;
  303.  
  304.     while (e != 0 && e != mark.rec)
  305.     {
  306.         AssocRec<K, V> *tmp = e;
  307.         e = e->next;
  308.         tmp->next = 0;
  309.         delete tmp;
  310.     }
  311.  
  312.     entries = e;
  313.     }
  314.  
  315.     // Constructor
  316.     Assoc()
  317.     : _Assoc<K, V>() 
  318.     {}
  319.  
  320.     // Destructor
  321.     ~Assoc() {}
  322.  
  323.     // Copy
  324.     Assoc(const Assoc<K, V>& m)
  325.     : _Assoc<K, V>(m)
  326.     {}
  327.  
  328.     // Assignment
  329.     Assoc<K, V>& operator = (const Assoc<K, V>& m)
  330.     {
  331.     _Assoc<K, V>::operator =(m);
  332.     return *this;
  333.     }
  334. };
  335.  
  336. #endif // _ICE_Assoc_h
  337. // DON'T ADD ANYTHING BEHIND THIS #endif
  338.