Nebula
Loading...
Searching...
No Matches
dictionary.h
Go to the documentation of this file.
1#pragma once
2//------------------------------------------------------------------------------
27#include "util/array.h"
28#include "util/keyvaluepair.h"
29
30//------------------------------------------------------------------------------
31namespace Util
32{
33template<class KEYTYPE, class VALUETYPE> class Dictionary
34{
35public:
47 VALUETYPE& operator[](const KEYTYPE& key);
49 const VALUETYPE& operator[](const KEYTYPE& key) const;
51 SizeT Size() const;
53 void Clear();
55 bool IsEmpty() const;
57 void Reserve(SizeT numElements);
63 IndexT Add(const KEYTYPE& key, const VALUETYPE& value);
65 VALUETYPE& Emplace(const KEYTYPE& key);
67 void EndBulkAdd();
71 void Erase(const KEYTYPE& key);
73 void EraseAtIndex(IndexT index);
75 IndexT FindIndex(const KEYTYPE& key) const;
77 bool Contains(const KEYTYPE& key) const;
79 bool Contains(const KEYTYPE& key, IndexT& index) const;
81 const KEYTYPE& KeyAtIndex(IndexT index) const;
83 VALUETYPE& ValueAtIndex(IndexT index);
85 const VALUETYPE& ValueAtIndex(IndexT index) const;
93 template<class RETURNTYPE> RETURNTYPE KeysAs() const;
95 template<class RETURNTYPE> RETURNTYPE ValuesAs() const;
96
100 void clear();
101 void emplace(KEYTYPE&&key, VALUETYPE&&value);
102
103protected:
105 void SortIfDirty() const;
106
109};
110
111//------------------------------------------------------------------------------
114template<class KEYTYPE, class VALUETYPE>
116 inBulkInsert(false)
117{
118 // empty
119}
120
121//------------------------------------------------------------------------------
124template<class KEYTYPE, class VALUETYPE>
126 keyValuePairs(rhs.keyValuePairs),
127 inBulkInsert(false)
128{
129 #if NEBULA_BOUNDSCHECKS
131 #endif
132}
133
134//------------------------------------------------------------------------------
137template<class KEYTYPE, class VALUETYPE>
139 keyValuePairs(std::move(rhs.keyValuePairs)),
140 inBulkInsert(false)
141{
142#if NEBULA_BOUNDSCHECKS
143 n_assert(!rhs.inBulkInsert);
144#endif
145}
146
147//------------------------------------------------------------------------------
150template<class KEYTYPE, class VALUETYPE>
151inline void
153{
154 #if NEBULA_BOUNDSCHECKS
155 n_assert(!this->inBulkInsert);
157 #endif
158 this->keyValuePairs = rhs.keyValuePairs;
159}
160
161//------------------------------------------------------------------------------
164template<class KEYTYPE, class VALUETYPE>
165inline void
167{
168#if NEBULA_BOUNDSCHECKS
169 n_assert(!this->inBulkInsert);
170 n_assert(!rhs.inBulkInsert);
171#endif
172 this->keyValuePairs = std::move(rhs.keyValuePairs);
173}
174
175//------------------------------------------------------------------------------
178template<class KEYTYPE, class VALUETYPE>
179inline void
181{
182 #if NEBULA_BOUNDSCHECKS
183 n_assert(!this->inBulkInsert);
184 #endif
185 this->keyValuePairs.Clear();
186}
187
188//------------------------------------------------------------------------------
191template<class KEYTYPE, class VALUETYPE>
192inline SizeT
194{
195 return this->keyValuePairs.Size();
196}
197
198//------------------------------------------------------------------------------
201template<class KEYTYPE, class VALUETYPE>
202inline bool
204{
205 return (0 == this->keyValuePairs.Size());
206}
207
208//------------------------------------------------------------------------------
211template<class KEYTYPE, class VALUETYPE>
212inline void
214{
215 this->keyValuePairs.Reserve(numElements);
216}
217
218//------------------------------------------------------------------------------
221template<class KEYTYPE, class VALUETYPE>
222inline void
224{
225 #if NEBULA_BOUNDSCHECKS
226 n_assert(!this->inBulkInsert);
227 #endif
228 this->inBulkInsert = true;
229}
230
231//------------------------------------------------------------------------------
234template<class KEYTYPE, class VALUETYPE>
235inline void
237{
238 #if NEBULA_BOUNDSCHECKS
239 n_assert(this->inBulkInsert);
240 #endif
241 this->keyValuePairs.Sort();
242 this->inBulkInsert = false;
243}
244
245//------------------------------------------------------------------------------
248template<class KEYTYPE, class VALUETYPE>
249inline void
251{
252 this->BeginBulkAdd();
253 IndexT i;
254 for (i = 0; i < rhs.keyValuePairs.Size(); i++)
255 {
256 this->keyValuePairs.Append(rhs.keyValuePairs[i]);
257 }
258 this->EndBulkAdd();
259}
260
261
262//------------------------------------------------------------------------------
265template<class KEYTYPE, class VALUETYPE>
266inline IndexT
268{
269 if (this->inBulkInsert)
270 {
271 this->keyValuePairs.Append(kvp);
272 return this->keyValuePairs.Size() - 1;
273 }
274 else
275 {
276 return this->keyValuePairs.InsertSorted(kvp);
277 }
278}
279
280//------------------------------------------------------------------------------
283template<class KEYTYPE, class VALUETYPE>
284inline IndexT
285Dictionary<KEYTYPE, VALUETYPE>::Add(const KEYTYPE& key, const VALUETYPE& value)
286{
287#if NEBULA_BOUNDSCHECKS
288 //n_assert(!this->Contains(key));
289#endif
290 KeyValuePair<KEYTYPE, VALUETYPE> kvp(key, value);
291 if (this->inBulkInsert)
292 {
293 this->keyValuePairs.Append(kvp);
294 return this->keyValuePairs.Size() - 1;
295 }
296 else
297 {
298 return this->keyValuePairs.InsertSorted(kvp);
299 }
300}
301
302//------------------------------------------------------------------------------
305template<class KEYTYPE, class VALUETYPE>
306inline VALUETYPE&
308{
309 IndexT i = this->FindIndex(key);
310 if (i == InvalidIndex)
311 {
312 return this->ValueAtIndex(this->Add(key, VALUETYPE()));
313 }
314 else
315 {
316 return this->ValueAtIndex(i);
317 }
318}
319
320//------------------------------------------------------------------------------
323template<class KEYTYPE, class VALUETYPE>
324inline void
326{
327 #if NEBULA_BOUNDSCHECKS
328 n_assert(!this->inBulkInsert);
329 #endif
330 IndexT eraseIndex = this->keyValuePairs.template BinarySearchIndex<KEYTYPE>(key);
331 #if NEBULA_BOUNDSCHECKS
332 n_assert(InvalidIndex != eraseIndex);
333 #endif
334 this->keyValuePairs.EraseIndex(eraseIndex);
335}
336
337//------------------------------------------------------------------------------
340template<class KEYTYPE, class VALUETYPE>
341inline void
343{
344 #if NEBULA_BOUNDSCHECKS
345 n_assert(!this->inBulkInsert);
346 #endif
347 this->keyValuePairs.EraseIndex(index);
348}
349
350//------------------------------------------------------------------------------
353template<class KEYTYPE, class VALUETYPE>
354inline IndexT
356{
357 #if NEBULA_BOUNDSCHECKS
358 n_assert(!this->inBulkInsert);
359 #endif
360 return this->keyValuePairs.template BinarySearchIndex<KEYTYPE>(key);
361}
362
363//------------------------------------------------------------------------------
366template<class KEYTYPE, class VALUETYPE>
367inline bool
369{
370 #if NEBULA_BOUNDSCHECKS
371 n_assert(!this->inBulkInsert);
372 #endif
373 return (InvalidIndex != this->keyValuePairs.template BinarySearchIndex<KEYTYPE>(key));
374}
375
376//------------------------------------------------------------------------------
379template<class KEYTYPE, class VALUETYPE>
380inline bool
381Dictionary<KEYTYPE, VALUETYPE>::Contains(const KEYTYPE& key, IndexT& index) const
382{
383#if NEBULA_BOUNDSCHECKS
384 n_assert(!this->inBulkInsert);
385#endif
386 index = this->keyValuePairs.template BinarySearchIndex<KEYTYPE>(key);
387 return (InvalidIndex != index);
388}
389
390//------------------------------------------------------------------------------
393template<class KEYTYPE, class VALUETYPE>
394inline const KEYTYPE&
396{
397 #if NEBULA_BOUNDSCHECKS
398 n_assert(!this->inBulkInsert);
399 #endif
400 return this->keyValuePairs[index].Key();
401}
402
403//------------------------------------------------------------------------------
406template<class KEYTYPE, class VALUETYPE>
407inline VALUETYPE&
409{
410 #if NEBULA_BOUNDSCHECKS
411 n_assert(!this->inBulkInsert);
412 #endif
413 return this->keyValuePairs[index].Value();
414}
415
416//------------------------------------------------------------------------------
419template<class KEYTYPE, class VALUETYPE>
420inline const VALUETYPE&
422{
423 #if NEBULA_BOUNDSCHECKS
424 n_assert(!this->inBulkInsert);
425 #endif
426 return this->keyValuePairs[index].Value();
427}
428
429//------------------------------------------------------------------------------
432template<class KEYTYPE, class VALUETYPE>
435{
436 #if NEBULA_BOUNDSCHECKS
437 n_assert(!this->inBulkInsert);
438 #endif
439 return this->keyValuePairs[index];
440}
441
442//------------------------------------------------------------------------------
445template<class KEYTYPE, class VALUETYPE>
446inline VALUETYPE&
448{
449 int keyValuePairIndex = this->FindIndex(key);
450 #if NEBULA_BOUNDSCHECKS
451 n_assert(InvalidIndex != keyValuePairIndex);
452 #endif
453 return this->keyValuePairs[keyValuePairIndex].Value();
454}
455
456//------------------------------------------------------------------------------
459template<class KEYTYPE, class VALUETYPE>
460inline const VALUETYPE&
462{
463 int keyValuePairIndex = this->FindIndex(key);
464 #if NEBULA_BOUNDSCHECKS
465 n_assert(InvalidIndex != keyValuePairIndex);
466 #endif
467 return this->keyValuePairs[keyValuePairIndex].Value();
468}
469
470//------------------------------------------------------------------------------
473template<class KEYTYPE, class VALUETYPE>
474template<class RETURNTYPE>
475RETURNTYPE
477{
478 #if NEBULA_BOUNDSCHECKS
479 n_assert(!this->inBulkInsert);
480 #endif
481 RETURNTYPE result(this->Size(),this->Size());
482 IndexT i;
483 for (i = 0; i < this->keyValuePairs.Size(); i++)
484 {
485 result.Append(this->keyValuePairs[i].Value());
486 }
487 return result;
488}
489
490//------------------------------------------------------------------------------
493template<class KEYTYPE, class VALUETYPE>
494inline Array<VALUETYPE>
496{
497 return this->ValuesAs<Array<VALUETYPE> >();
498}
499
500//------------------------------------------------------------------------------
503template<class KEYTYPE, class VALUETYPE>
504template<class RETURNTYPE>
505inline RETURNTYPE
507{
508 #if NEBULA_BOUNDSCHECKS
509 n_assert(!this->inBulkInsert);
510 #endif
511 RETURNTYPE result(this->Size(),this->Size());
512 IndexT i;
513 for (i = 0; i < this->keyValuePairs.Size(); i++)
514 {
515 result.Append(this->keyValuePairs[i].Key());
516 }
517 return result;
518}
519
520//------------------------------------------------------------------------------
523template<class KEYTYPE, class VALUETYPE>
524inline Array<KEYTYPE>
526{
527 return this->KeysAs<Array<KEYTYPE> >();
528}
529
530//------------------------------------------------------------------------------
533template<class KEYTYPE, class VALUETYPE>
536{
537 return this->keyValuePairs.begin();
538}
539//------------------------------------------------------------------------------
542template<class KEYTYPE, class VALUETYPE>
545{
546 return this->keyValuePairs.end();
547}
548//------------------------------------------------------------------------------
551template<class KEYTYPE, class VALUETYPE>
552inline void
554{
555 this->Clear();
556}
557//------------------------------------------------------------------------------
560template<class KEYTYPE, class VALUETYPE>
561inline void
562Dictionary<KEYTYPE, VALUETYPE>::emplace(KEYTYPE&&key, VALUETYPE&&value)
563{
564 this->Add(key, value);
565}
566} // namespace Util
567//------------------------------------------------------------------------------
Nebula's dynamic array class.
Definition array.h:60
A collection of key/value pairs with quick value retrieval by key at roughly O(log n).
Definition dictionary.h:34
void BeginBulkAdd()
begin a bulk insert (array will be sorted at End)
Definition dictionary.h:223
void operator=(Dictionary< KEYTYPE, VALUETYPE > &&rhs) noexcept
move operator
Definition dictionary.h:166
Dictionary(const Dictionary< KEYTYPE, VALUETYPE > &rhs)
copy constructor
Definition dictionary.h:125
void Reserve(SizeT numElements)
reserve space (useful if number of elements is known beforehand)
Definition dictionary.h:213
bool Contains(const KEYTYPE &key) const
return true if key exists in the array
Definition dictionary.h:368
void Clear()
clear the dictionary
Definition dictionary.h:180
SizeT Size() const
return number of key/value pairs in the dictionary
Definition dictionary.h:193
KeyValuePair< KEYTYPE, VALUETYPE > * end() const
Definition dictionary.h:544
const KEYTYPE & KeyAtIndex(IndexT index) const
get a key at given index
Definition dictionary.h:395
IndexT FindIndex(const KEYTYPE &key) const
find index of key/value pair (InvalidIndex if doesn't exist)
Definition dictionary.h:355
Array< KEYTYPE > KeysAsArray() const
get all keys as an Util::Array
Definition dictionary.h:525
Dictionary(Dictionary< KEYTYPE, VALUETYPE > &&rhs) noexcept
move constructor
Definition dictionary.h:138
const VALUETYPE & ValueAtIndex(IndexT index) const
get a value at given index
Definition dictionary.h:421
IndexT Add(const KeyValuePair< KEYTYPE, VALUETYPE > &kvp)
add a key/value pair
Definition dictionary.h:267
void clear()
Definition dictionary.h:553
void EraseAtIndex(IndexT index)
erase a key at index
Definition dictionary.h:342
KeyValuePair< KEYTYPE, VALUETYPE > & KeyValuePairAtIndex(IndexT index) const
get key/value pair at index
Definition dictionary.h:434
const VALUETYPE & operator[](const KEYTYPE &key) const
read-only [] operator
Definition dictionary.h:461
RETURNTYPE ValuesAs() const
get all keys as (typically) an array
Definition dictionary.h:476
bool IsEmpty() const
return true if empty
Definition dictionary.h:203
VALUETYPE & ValueAtIndex(IndexT index)
access to value at given index
Definition dictionary.h:408
RETURNTYPE KeysAs() const
get all keys as (typically) an array
Definition dictionary.h:506
Array< VALUETYPE > ValuesAsArray() const
get all keys as an Util::Array
Definition dictionary.h:495
void emplace(KEYTYPE &&key, VALUETYPE &&value)
Definition dictionary.h:562
void Erase(const KEYTYPE &key)
erase a key and its associated value
Definition dictionary.h:325
VALUETYPE & operator[](const KEYTYPE &key)
read/write [] operator
Definition dictionary.h:447
bool Contains(const KEYTYPE &key, IndexT &index) const
return true if key exists in the array, and saves index
Definition dictionary.h:381
bool inBulkInsert
Definition dictionary.h:108
void Merge(const Dictionary< KEYTYPE, VALUETYPE > &rhs)
merge two dictionaries
Definition dictionary.h:250
IndexT Add(const KEYTYPE &key, const VALUETYPE &value)
add a key and associated value
Definition dictionary.h:285
KeyValuePair< KEYTYPE, VALUETYPE > * begin() const
functions for stl like behaviour
Definition dictionary.h:535
void EndBulkAdd()
end a bulk insert (this will sort the internal array)
Definition dictionary.h:236
void operator=(const Dictionary< KEYTYPE, VALUETYPE > &rhs)
assignment operator
Definition dictionary.h:152
Array< KeyValuePair< KEYTYPE, VALUETYPE > > keyValuePairs
Definition dictionary.h:107
Dictionary()
default constructor
Definition dictionary.h:115
VALUETYPE & Emplace(const KEYTYPE &key)
creates a new entry of VALUETYPE if key does not exist, or returns the existing element
Definition dictionary.h:307
void SortIfDirty() const
make sure the key value pair array is sorted
Key/Value pair objects are used by most assiociative container classes, like Dictionary or HashTable.
Definition keyvaluepair.h:19
#define n_assert(exp)
Definition debug.h:50
A pinned array is an array which manages its own virtual memory.
Definition String.cs:6
static const int InvalidIndex
Definition types.h:54
int SizeT
Definition types.h:49
int IndexT
Definition types.h:48