cde/programs/dtinfo/dtinfo/src/UAS/DtSR/Util_Classes/Dict.C

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 // $XConsortium: Dict.cc /main/3 1996/06/11 16:42:15 cde-hal $
  24
  25 #include "Dict.hh"
  26 #include "DictIter.hh"
  27 #include "DictLink.hh"
  28
  29 #ifndef NULL
  30 #define NULL    0
  31 #endif
  32
  33 template<class K, class V>
  34 K
  35 Dict<K,V>::kdef()
  36 {
  37     static K k;
  38     return k;
  39 }
  40
  41 template<class K, class V>
  42 V
  43 Dict<K,V>::vdef()
  44 {
  45     static V v;
  46     return v;
  47 }
  48
  49 template<class K, class V>
  50 void
  51 Dict<K,V>::init()
  52 {
  53     if (head)
  54         delete head;
  55     head = NULL;
  56     current = NULL;
  57     sz = 0;
  58 }
  59
  60 template<class K, class V>
  61 Dict<K,V>::Dict() : def_key(kdef()), def_val(vdef()), head(NULL)
  62 {
  63     init();
  64 }
  65
  66
  67 template<class K, class V>
  68 Dict<K,V>::Dict(const K& k, const V& v) : def_key(k), def_val(v), head(NULL)
  69 {
  70     init();
  71 }
  72
  73 template<class K, class V>
  74 Dict<K,V>::~Dict()
  75 {
  76     if (head)
  77         delete head;
  78 }
  79
  80
  81 template<class K, class V>
  82 DictIter<K,V>
  83 Dict<K,V>::element(const K& k)
  84 {
  85     (void) operator[](k); // move current to k
  86     return DictIter<K,V>(this, current);
  87 }
  88
  89 template<class K, class V>
  90 DictIter<K,V>
  91 Dict<K,V>::first()
  92 {
  93     return DictIter<K,V>(this, head);
  94 }
  95
  96 template<class K, class V>
  97 V&
  98 Dict<K,V>::operator[](const K& k)
  99 {
 100     if (head == NULL) {
 101         current = head = new DictLink<K,V>(k, def_val);
 102         current->pre = current->suc = NULL;
 103         sz++;
 104         return current->value;
 105     }
 106
 107     DictLink<K,V>* p = head;
 108     for (;;) {
 109         if (p->key == k) { // found
 110             current = p;
 111             return current->value;
 112         }
 113
 114         if (k < p->key) { // insert before p
 115             current = new DictLink<K,V>(k, def_val);
 116             current->pre = p->pre;
 117             current->suc = p;
 118             if (p == head)
 119                 head = current;
 120             else
 121                 p->pre->suc = current;
 122             p->pre = current;
 123             sz++;
 124             return current->value;
 125         }
 126
 127         DictLink<K,V>* s = p->suc;
 128         if (s == NULL) {
 129             current = new DictLink<K,V>(k, def_val);
 130             current->pre = p;
 131             current->suc = NULL;
 132             p->suc = current;
 133             sz++;
 134             return current->value;
 135         }
 136         p = s;
 137     }
 138 }
 139
 140