doxygen: intern/container tagged
[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     int size() { 
60         int count=0;
61         for (int i=0;i<m_num_buckets;i++)
62         {
63             Entry* bucket = m_buckets[i];
64             while(bucket)
65             {
66                 bucket = bucket->m_next;
67                 count++;
68             }
69         }
70         return count;
71     }
72     
73     Value* at(int index) {
74         int count=0;
75         for (int i=0;i<m_num_buckets;i++)
76         {
77             Entry* bucket = m_buckets[i];
78             while(bucket)
79             {
80                 if (count==index)
81                 {
82                     return &bucket->m_value;
83                 }
84                 bucket = bucket->m_next;
85                 count++;
86             }
87         }
88         return 0;
89     }
90     
91     void clear() {
92         for (int i = 0; i < m_num_buckets; ++i) {
93             Entry *entry_ptr = m_buckets[i];
94             
95             while (entry_ptr != 0) {
96                 Entry *tmp_ptr = entry_ptr->m_next;
97                 delete entry_ptr;
98                 entry_ptr = tmp_ptr;
99             }
100             m_buckets[i] = 0;
101         }
102     }
103     
104     ~CTR_Map() {
105         clear();
106         delete [] m_buckets;
107     }
108     
109     void insert(const Key& key, const Value& value) {
110         Entry *entry_ptr = m_buckets[key.hash() % m_num_buckets];
111         while ((entry_ptr != 0) && !(key == entry_ptr->m_key)) {
112             entry_ptr = entry_ptr->m_next;
113         }
114         
115         if (entry_ptr != 0) {
116             entry_ptr->m_value = value;
117         }
118         else {
119             Entry **bucket = &m_buckets[key.hash() % m_num_buckets];
120             *bucket = new Entry(*bucket, key, value);
121         }
122     }
123
124     void remove(const Key& key) {
125         Entry **entry_ptr = &m_buckets[key.hash() % m_num_buckets];
126         while ((*entry_ptr != 0) && !(key == (*entry_ptr)->m_key)) {
127             entry_ptr = &(*entry_ptr)->m_next;
128         }
129         
130         if (*entry_ptr != 0) {
131             Entry *tmp_ptr = (*entry_ptr)->m_next;
132             delete *entry_ptr;
133             *entry_ptr = tmp_ptr;
134         }
135     }
136
137     Value *operator[](Key key) {
138         Entry *bucket = m_buckets[key.hash() % m_num_buckets];
139         while ((bucket != 0) && !(key == bucket->m_key)) {
140             bucket = bucket->m_next;
141         }
142         return bucket != 0 ? &bucket->m_value : 0;
143     }
144     
145 private:
146     int     m_num_buckets;
147     Entry **m_buckets;
148 };
149
150 #endif
151