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