Merged 15170:15635 from trunk (no conflicts or even merges)
[blender.git] / intern / moto / include / GEN_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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, 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 #ifndef GEN_MAP_H
30 #define GEN_MAP_H
31
32 template <class Key, class Value>
33 class GEN_Map {
34 private:
35     struct Entry {
36         Entry (Entry *next, Key key, Value value) :
37             m_next(next),
38             m_key(key),
39             m_value(value) {}
40
41         Entry *m_next;
42         Key    m_key;
43         Value  m_value;
44     };
45  
46 public:
47     GEN_Map(int num_buckets = 100) : m_num_buckets(num_buckets) {
48         m_buckets = new Entry *[num_buckets];
49         for (int i = 0; i < num_buckets; ++i) {
50             m_buckets[i] = 0;
51         }
52     }
53     
54     int size() { 
55         int count=0;
56         for (int i=0;i<m_num_buckets;i++)
57         {
58             Entry* bucket = m_buckets[i];
59             while(bucket)
60             {
61                 bucket = bucket->m_next;
62                 count++;
63             }
64         }
65         return count;
66     }
67     
68     Value* at(int index) {
69         int count=0;
70         for (int i=0;i<m_num_buckets;i++)
71         {
72             Entry* bucket = m_buckets[i];
73             while(bucket)
74             {
75                 if (count==index)
76                 {
77                     return &bucket->m_value;
78                 }
79                 bucket = bucket->m_next;
80                 count++;
81             }
82         }
83         return 0;
84     }
85
86     Key* getKey(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_key;
96                 }
97                 bucket = bucket->m_next;
98                 count++;
99             }
100         }
101         return 0;
102     }
103     
104     void clear() {
105         for (int i = 0; i < m_num_buckets; ++i) {
106             Entry *entry_ptr = m_buckets[i];
107             
108             while (entry_ptr != 0) {
109                 Entry *tmp_ptr = entry_ptr->m_next;
110                 delete entry_ptr;
111                 entry_ptr = tmp_ptr;
112             }
113             m_buckets[i] = 0;
114         }
115     }
116     
117     ~GEN_Map() {
118         clear();
119         delete [] m_buckets;
120     }
121     
122     void insert(const Key& key, const Value& value) {
123         Entry *entry_ptr = m_buckets[key.hash() % m_num_buckets];
124         while ((entry_ptr != 0) && !(key == entry_ptr->m_key)) {
125             entry_ptr = entry_ptr->m_next;
126         }
127         
128         if (entry_ptr != 0) {
129             entry_ptr->m_value = value;
130         }
131         else {
132             Entry **bucket = &m_buckets[key.hash() % m_num_buckets];
133             *bucket = new Entry(*bucket, key, value);
134         }
135     }
136
137     void remove(const Key& key) {
138         Entry **entry_ptr = &m_buckets[key.hash() % m_num_buckets];
139         while ((*entry_ptr != 0) && !(key == (*entry_ptr)->m_key)) {
140             entry_ptr = &(*entry_ptr)->m_next;
141         }
142         
143         if (*entry_ptr != 0) {
144             Entry *tmp_ptr = (*entry_ptr)->m_next;
145             delete *entry_ptr;
146             *entry_ptr = tmp_ptr;
147         }
148     }
149
150     Value *operator[](Key key) {
151         Entry *bucket = m_buckets[key.hash() % m_num_buckets];
152         while ((bucket != 0) && !(key == bucket->m_key)) {
153             bucket = bucket->m_next;
154         }
155         return bucket != 0 ? &bucket->m_value : 0;
156     }
157     
158 private:
159     int     m_num_buckets;
160     Entry **m_buckets;
161 };
162
163 #endif
164