Mercurial > projects > hoofbaby

comparison deps/Platinum/ThirdParty/Neptune/Source/Core/NptMap.h @ 0:3425707ddbf6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial import (hopefully this mercurial stuff works...)
author fraserofthenight
date Mon, 06 Jul 2009 08:06:28 -0700
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:3425707ddbf6
1 /*****************************************************************
2 |
3 | Neptune - Maps
4 |
5 | Copyright (c) 2002-2008, Axiomatic Systems, LLC.
6 | All rights reserved.
7 |
8 | Redistribution and use in source and binary forms, with or without
9 | modification, are permitted provided that the following conditions are met:
10 | * Redistributions of source code must retain the above copyright
11 | notice, this list of conditions and the following disclaimer.
12 | * Redistributions in binary form must reproduce the above copyright
13 | notice, this list of conditions and the following disclaimer in the
14 | documentation and/or other materials provided with the distribution.
15 | * Neither the name of Axiomatic Systems nor the
16 | names of its contributors may be used to endorse or promote products
17 | derived from this software without specific prior written permission.
18 |
19 | THIS SOFTWARE IS PROVIDED BY AXIOMATIC SYSTEMS ''AS IS'' AND ANY
20 | EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
21 | WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 | DISCLAIMED. IN NO EVENT SHALL AXIOMATIC SYSTEMS BE LIABLE FOR ANY
23 | DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24 | (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25 | LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
26 | ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28 | SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 |
30 ****************************************************************/
31
32 #ifndef _NPT_MAP_H_
33 #define _NPT_MAP_H_
34
35 /*----------------------------------------------------------------------
36 | includes
37 +---------------------------------------------------------------------*/
38 #include "NptTypes.h"
39 #include "NptResults.h"
40 #include "NptList.h"
41
42 /*----------------------------------------------------------------------
43 | NPT_Map
44 +---------------------------------------------------------------------*/
45 template <typename K, typename V>
46 class NPT_Map
47 {
48 public:
49 // types
50 class Entry {
51 public:
52 // constructor
53 Entry(const K& key, const V& value) : m_Key(key), m_Value(value) {}
54 Entry(const K& key) : m_Key(key) {}
55
56 // accessors
57 const K& GetKey() const { return m_Key; }
58 const V& GetValue() const { return m_Value; }
59
60 // operators
61 bool operator==(const Entry& other) const {
62 return m_Key == other.m_Key && m_Value == other.m_Value;
63 }
64
65 protected:
66 // methods
67 void SetValue(const V& value) { m_Value = value; }
68
69 // members
70 K m_Key;
71 V m_Value;
72
73 // friends
74 friend class NPT_Map<K,V>;
75 };
76
77 class EntryValueDeleter {
78 public:
79 void operator()(Entry* entry) const {
80 delete entry->GetValue();
81 }
82 };
83
84 // constructors
85 NPT_Map<K,V>() {}
86 NPT_Map<K,V>(const NPT_Map<K,V>& copy);
87
88 // destructor
89 ~NPT_Map<K,V>();
90
91 // methods
92 NPT_Result Put(const K& key, const V& value);
93 NPT_Result Get(const K& key, V*& value) const;
94 bool HasKey(const K& key) const { return GetEntry(key) != NULL; }
95 bool HasValue(const V& value) const;
96 NPT_Result Erase(const K& key);
97 NPT_Cardinal GetEntryCount() const { return m_Entries.GetItemCount(); }
98 const NPT_List<Entry*>& GetEntries() const { return m_Entries; }
99 NPT_Result Clear();
100
101 // operators
102 V& operator[](const K& key);
103 const NPT_Map<K,V>& operator=(const NPT_Map<K,V>& copy);
104 bool operator==(const NPT_Map<K,V>& other) const;
105 bool operator!=(const NPT_Map<K,V>& other) const;
106
107 private:
108 // types
109 typedef typename NPT_List<Entry*>::Iterator ListIterator;
110
111 // methods
112 Entry* GetEntry(const K& key) const;
113
114 // members
115 NPT_List<Entry*> m_Entries;
116 };
117
118 /*----------------------------------------------------------------------
119 | NPT_Map<K,V>::NPT_Map<K,V>
120 +---------------------------------------------------------------------*/
121 template <typename K, typename V>
122 NPT_Map<K,V>::NPT_Map(const NPT_Map<K,V>& copy)
123 {
124 *this = copy;
125 }
126
127 /*----------------------------------------------------------------------
128 | NPT_Map<K,V>::~NPT_Map<K,V>
129 +---------------------------------------------------------------------*/
130 template <typename K, typename V>
131 inline
132 NPT_Map<K,V>::~NPT_Map()
133 {
134 // call Clear to ensure we delete all entry objects
135 Clear();
136 }
137
138 /*----------------------------------------------------------------------
139 | NPT_Map<K,V>::Clear
140 +---------------------------------------------------------------------*/
141 template <typename K, typename V>
142 inline
143 NPT_Result
144 NPT_Map<K,V>::Clear()
145 {
146 m_Entries.Apply(NPT_ObjectDeleter<Entry>());
147 m_Entries.Clear();
148
149 return NPT_SUCCESS;
150 }
151
152 /*----------------------------------------------------------------------
153 | NPT_Map<K,V>::GetEntry
154 +---------------------------------------------------------------------*/
155 template <typename K, typename V>
156 typename NPT_Map<K,V>::Entry*
157 NPT_Map<K,V>::GetEntry(const K& key) const
158 {
159 typename NPT_List<Entry*>::Iterator entry = m_Entries.GetFirstItem();
160 while (entry) {
161 if ((*entry)->GetKey() == key) {
162 return *entry;
163 }
164 ++entry;
165 }
166
167 return NULL;
168 }
169
170 /*----------------------------------------------------------------------
171 | NPT_Map<K,V>::Put
172 +---------------------------------------------------------------------*/
173 template <typename K, typename V>
174 inline
175 NPT_Result
176 NPT_Map<K,V>::Put(const K& key, const V& value)
177 {
178 Entry* entry = GetEntry(key);
179 if (entry == NULL) {
180 // no existing entry for that key, create one
181 m_Entries.Add(new Entry(key, value));
182 } else {
183 // replace the existing entry for that key
184 entry->SetValue(value);
185 }
186
187 return NPT_SUCCESS;
188 }
189
190 /*----------------------------------------------------------------------
191 | NPT_Map<K,V>::Get
192 +---------------------------------------------------------------------*/
193 template <typename K, typename V>
194 inline
195 NPT_Result
196 NPT_Map<K,V>::Get(const K& key, V*& value) const
197 {
198 Entry* entry = GetEntry(key);
199 if (entry == NULL) {
200 // no existing entry for that key
201 value = NULL;
202 return NPT_ERROR_NO_SUCH_ITEM;
203 } else {
204 // found an entry with that key
205 value = &entry->m_Value;
206 return NPT_SUCCESS;
207 }
208 }
209
210 /*----------------------------------------------------------------------
211 | NPT_Map<K,V>::HasValue
212 +---------------------------------------------------------------------*/
213 template <typename K, typename V>
214 bool
215 NPT_Map<K,V>::HasValue(const V& value) const
216 {
217 ListIterator entry = m_Entries.GetFirstItem();
218 while (entry) {
219 if (value == (*entry)->m_Value) {
220 return true;
221 }
222 ++entry;
223 }
224
225 return false;
226 }
227
228 /*----------------------------------------------------------------------
229 | NPT_Map<K,V>::operator=
230 +---------------------------------------------------------------------*/
231 template <typename K, typename V>
232 const NPT_Map<K,V>&
233 NPT_Map<K,V>::operator=(const NPT_Map<K,V>& copy)
234 {
235 // do nothing if we're assigning to ourselves
236 if (this == &copy) return copy;
237
238 // destroy all entries
239 Clear();
240
241 // copy all entries one by one
242 ListIterator entry = copy.m_Entries.GetFirstItem();
243 while (entry) {
244 m_Entries.Add(new Entry((*entry)->GetKey(), (*entry)->GetValue()));
245 ++entry;
246 }
247
248 return *this;
249 }
250
251 /*----------------------------------------------------------------------
252 | NPT_Map<K,V>::Erase
253 +---------------------------------------------------------------------*/
254 template <typename K, typename V>
255 inline
256 NPT_Result
257 NPT_Map<K,V>::Erase(const K& key)
258 {
259 ListIterator entry = m_Entries.GetFirstItem();
260 while (entry) {
261 if ((*entry)->GetKey() == key) {
262 delete *entry; // do this before removing the entry from the
263 // list, because Erase() will invalidate the
264 // iterator item
265 m_Entries.Erase(entry);
266 return NPT_SUCCESS;
267 }
268 ++entry;
269 }
270
271 return NPT_ERROR_NO_SUCH_ITEM;
272 }
273
274 /*----------------------------------------------------------------------
275 | NPT_Map<K,V>::operator==
276 +---------------------------------------------------------------------*/
277 template <typename K, typename V>
278 bool
279 NPT_Map<K,V>::operator==(const NPT_Map<K,V>& other) const
280 {
281 // quick test
282 if (m_Entries.GetItemCount() != other.m_Entries.GetItemCount()) return false;
283
284 // compare all entries to all other entries
285 ListIterator entry = m_Entries.GetFirstItem();
286 while (entry) {
287 V* value;
288 if (NPT_SUCCEEDED(other.Get((*entry)->m_Key, value))) {
289 // the other map has an entry for this key, check the value
290 if (!(*value == (*entry)->m_Value)) return false;
291 } else {
292 // the other map does not have an entry for this key
293 return false;
294 }
295 ++entry;
296 }
297
298 return true;
299 }
300
301 /*----------------------------------------------------------------------
302 | NPT_Map<K,V>::operator!=
303 +---------------------------------------------------------------------*/
304 template <typename K, typename V>
305 inline
306 bool
307 NPT_Map<K,V>::operator!=(const NPT_Map<K,V>& other) const
308 {
309 return !(*this == other);
310 }
311
312 /*----------------------------------------------------------------------
313 | NPT_Map<K,V>::operator[]
314 +---------------------------------------------------------------------*/
315 template <typename K, typename V>
316 inline
317 V&
318 NPT_Map<K,V>::operator[](const K& key)
319 {
320 Entry* entry = GetEntry(key);
321 if (entry == NULL) {
322 // create a new "default" entry for this key
323 entry = new Entry(key);
324 m_Entries.Add(entry);
325 }
326
327 return entry->m_Value;
328 }
329
330 #endif // _NPT_MAP_H_