intern/container/CTR_Map.h

   1 /*
   2  * $Id$
   3  * ***** BEGIN GPL LICENSE BLOCK *****
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * as published by the Free Software Foundation; either version 2
   8  * of the License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  18  *
  19  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
  20  * All rights reserved.
  21  *
  22  * The Original Code is: all of this file.
  23  *
  24  * Contributor(s): none yet.
  25  *
  26  * ***** END GPL LICENSE BLOCK *****
  27  */
  28
  29 /** \file container/CTR_Map.h
  30  *  \ingroup ctr
  31  */
  32
  33
  34 #ifndef CTR_MAP_H
  35 #define CTR_MAP_H
  36
  37 template <class Key, class Value>
  38 class CTR_Map {
  39 private:
  40     struct Entry {
  41         Entry (Entry *next, Key key, Value value) :
  42             m_next(next),
  43             m_key(key),
  44             m_value(value) {}
  45
  46         Entry *m_next;
  47         Key    m_key;
  48         Value  m_value;
  49     };
  50
  51 public:
  52     CTR_Map(int num_buckets = 100) : m_num_buckets(num_buckets) {
  53         m_buckets = new Entry *[num_buckets];
  54         for (int i = 0; i < num_buckets; ++i) {
  55             m_buckets[i] = 0;
  56         }
  57     }
  58
  59         CTR_Map(const CTR_Map& map)
  60         {
  61                 m_num_buckets = map.m_num_buckets;
  62                 m_buckets = new Entry *[m_num_buckets];
  63
  64                 for (int i = 0; i < m_num_buckets; ++i) {
  65                         m_buckets[i] = 0;
  66
  67                         for(Entry *entry = map.m_buckets[i]; entry; entry=entry->m_next)
  68                                 insert(entry->m_key, entry->m_value);
  69                 }
  70         }
  71
  72     int size() {
  73         int count=0;
  74         for (int i=0;i<m_num_buckets;i++)
  75         {
  76             Entry* bucket = m_buckets[i];
  77             while(bucket)
  78             {
  79                 bucket = bucket->m_next;
  80                 count++;
  81             }
  82         }
  83         return count;
  84     }
  85
  86     Value* at(int index) {
  87         int count=0;
  88         for (int i=0;i<m_num_buckets;i++)
  89         {
  90             Entry* bucket = m_buckets[i];
  91             while(bucket)
  92             {
  93                 if (count==index)
  94                 {
  95                     return &bucket->m_value;
  96                 }
  97                 bucket = bucket->m_next;
  98                 count++;
  99             }
 100         }
 101         return 0;
 102     }
 103
 104     Key* getKey(int index) {
 105         int count=0;
 106         for (int i=0;i<m_num_buckets;i++)
 107         {
 108             Entry* bucket = m_buckets[i];
 109             while(bucket)
 110             {
 111                 if (count==index)
 112                 {
 113                     return &bucket->m_key;
 114                 }
 115                 bucket = bucket->m_next;
 116                 count++;
 117             }
 118         }
 119         return 0;
 120     }
 121
 122     void clear() {
 123         for (int i = 0; i < m_num_buckets; ++i) {
 124             Entry *entry_ptr = m_buckets[i];
 125
 126             while (entry_ptr != 0) {
 127                 Entry *tmp_ptr = entry_ptr->m_next;
 128                 delete entry_ptr;
 129                 entry_ptr = tmp_ptr;
 130             }
 131             m_buckets[i] = 0;
 132         }
 133     }
 134
 135     ~CTR_Map() {
 136         clear();
 137         delete [] m_buckets;
 138     }
 139
 140     void insert(const Key& key, const Value& value) {
 141         Entry *entry_ptr = m_buckets[key.hash() % m_num_buckets];
 142         while ((entry_ptr != 0) && !(key == entry_ptr->m_key)) {
 143             entry_ptr = entry_ptr->m_next;
 144         }
 145
 146         if (entry_ptr != 0) {
 147             entry_ptr->m_value = value;
 148         }
 149         else {
 150             Entry **bucket = &m_buckets[key.hash() % m_num_buckets];
 151             *bucket = new Entry(*bucket, key, value);
 152         }
 153     }
 154
 155     void remove(const Key& key) {
 156         Entry **entry_ptr = &m_buckets[key.hash() % m_num_buckets];
 157         while ((*entry_ptr != 0) && !(key == (*entry_ptr)->m_key)) {
 158             entry_ptr = &(*entry_ptr)->m_next;
 159         }
 160
 161         if (*entry_ptr != 0) {
 162             Entry *tmp_ptr = (*entry_ptr)->m_next;
 163             delete *entry_ptr;
 164             *entry_ptr = tmp_ptr;
 165         }
 166     }
 167
 168     Value *operator[](Key key) {
 169         Entry *bucket = m_buckets[key.hash() % m_num_buckets];
 170         while ((bucket != 0) && !(key == bucket->m_key)) {
 171             bucket = bucket->m_next;
 172         }
 173         return bucket != 0 ? &bucket->m_value : 0;
 174     }
 175
 176 private:
 177     int     m_num_buckets;
 178     Entry **m_buckets;
 179 };
 180
 181 #endif
 182