Initial revision
[blender.git] / intern / container / CTR_Map.h
1 /**
2  * $Id$
3  * ***** BEGIN GPL/BL DUAL 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. The Blender
9  * Foundation also sells licenses for use in proprietary software under
10  * the Blender License.  See http://www.blender.org/BL/ for information
11  * about this.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, write to the Free Software Foundation,
20  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
21  *
22  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
23  * All rights reserved.
24  *
25  * The Original Code is: all of this file.
26  *
27  * Contributor(s): none yet.
28  *
29  * ***** END GPL/BL DUAL LICENSE BLOCK *****
30  */
31
32 #ifndef CTR_MAP_H
33
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     int size() { 
59         int count=0;
60         for (int i=0;i<m_num_buckets;i++)
61         {
62             Entry* bucket = m_buckets[i];
63             while(bucket)
64             {
65                 bucket = bucket->m_next;
66                 count++;
67             }
68         }
69         return count;
70     }
71     
72     Value* at(int index) {
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                 if (count==index)
80                 {
81                     return &bucket->m_value;
82                 }
83                 bucket = bucket->m_next;
84                 count++;
85             }
86         }
87         return 0;
88     }
89     
90     void clear() {
91         for (int i = 0; i < m_num_buckets; ++i) {
92             Entry *entry_ptr = m_buckets[i];
93             
94             while (entry_ptr != 0) {
95                 Entry *tmp_ptr = entry_ptr->m_next;
96                 delete entry_ptr;
97                 entry_ptr = tmp_ptr;
98             }
99             m_buckets[i] = 0;
100         }
101     }
102     
103     ~CTR_Map() {
104         clear();
105         delete [] m_buckets;
106     }
107     
108     void insert(const Key& key, const Value& value) {
109         Entry *entry_ptr = m_buckets[key.hash() % m_num_buckets];
110         while ((entry_ptr != 0) && !(key == entry_ptr->m_key)) {
111             entry_ptr = entry_ptr->m_next;
112         }
113         
114         if (entry_ptr != 0) {
115             entry_ptr->m_value = value;
116         }
117         else {
118             Entry **bucket = &m_buckets[key.hash() % m_num_buckets];
119             *bucket = new Entry(*bucket, key, value);
120         }
121     }
122
123     void remove(const Key& key) {
124         Entry **entry_ptr = &m_buckets[key.hash() % m_num_buckets];
125         while ((*entry_ptr != 0) && !(key == (*entry_ptr)->m_key)) {
126             entry_ptr = &(*entry_ptr)->m_next;
127         }
128         
129         if (*entry_ptr != 0) {
130             Entry *tmp_ptr = (*entry_ptr)->m_next;
131             delete *entry_ptr;
132             *entry_ptr = tmp_ptr;
133         }
134     }
135
136     Value *operator[](Key key) {
137         Entry *bucket = m_buckets[key.hash() % m_num_buckets];
138         while ((bucket != 0) && !(key == bucket->m_key)) {
139             bucket = bucket->m_next;
140         }
141         return bucket != 0 ? &bucket->m_value : 0;
142     }
143     
144 private:
145     int     m_num_buckets;
146     Entry **m_buckets;
147 };
148
149 #endif
150
151
152