1991ec19e3a6e37b824d0cdb1235c510bc828031
[blender.git] / 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