spaces -> tabs (only whitespace changes)
[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