Visualization Library 2.0.0

A lightweight C++ OpenGL middleware for 2D/3D graphics

VL     Star     Watch     Fork     Issue

[Download] [Tutorials] [All Classes] [Grouped Classes]
NaryQuickMap.hpp
Go to the documentation of this file.
1 /**************************************************************************************/
2 /* */
3 /* Visualization Library */
4 /* http://visualizationlibrary.org */
5 /* */
6 /* Copyright (c) 2005-2020, Michele Bosi */
7 /* All rights reserved. */
8 /* */
9 /* Redistribution and use in source and binary forms, with or without modification, */
10 /* are permitted provided that the following conditions are met: */
11 /* */
12 /* - Redistributions of source code must retain the above copyright notice, this */
13 /* list of conditions and the following disclaimer. */
14 /* */
15 /* - Redistributions in binary form must reproduce the above copyright notice, this */
16 /* list of conditions and the following disclaimer in the documentation and/or */
17 /* other materials provided with the distribution. */
18 /* */
19 /* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND */
20 /* ANY 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 THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR */
23 /* ANY 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 ON */
26 /* 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 NaryQuickSet_INCLUDE_ONCE
33 #define NaryQuickSet_INCLUDE_ONCE
34 
35 #include <vlCore/Object.hpp>
36 
37 namespace vl
38 {
42  template<typename KeyType, typename ValueType, int MaxMapType>
43  class NaryQuickMap: public Object
44  {
45  public:
47  {
48  reset();
49  }
50 
51  void reset()
52  {
53  mMapSize = 0;
54  memset(mKeyToValue, 0, sizeof(mKeyToValue));
55  memset(mValueToKey, 0, sizeof(mValueToKey));
56  }
57 
58  void clear()
59  {
60  // no need to touch anything else.. you clever VL!
61  mMapSize = 0;
62  }
63 
64  int size() const { return mMapSize; }
65 
66  ValueType* begin() { return mValues; }
67  ValueType* end() { return mValues + mMapSize; }
68  const ValueType* begin() const { return mValues; }
69  const ValueType* end() const { return mValues + mMapSize; }
70 
71  void append(KeyType key)
72  {
73  append(key, key);
74  }
75 
76  // use this when you know that 'key' is not already in the set.
77  void append(KeyType key, ValueType value)
78  {
79  // sovrascrivi 'key' in ogni caso
80  int pos = mMapSize++;
81  mKeyToValue[key] = pos;
82  mValueToKey[pos] = key;
83  mValues[pos] = value;
84  }
85 
86  void insert(KeyType key)
87  {
88  insert(key, key);
89  }
90 
91  void insert(KeyType key, const ValueType& value)
92  {
93  VL_CHECK(key < MaxMapType)
94  int pos = find(key);
95  if (pos == -1)
96  {
97  pos = mMapSize++;
98  VL_CHECK(pos < MaxMapType)
99  mKeyToValue[key] = pos;
100  mValueToKey[pos] = key;
101  }
102  mValues[pos] = value;
103  }
104 
105  void erase(KeyType key)
106  {
107  int pos = find(key);
108  if (pos != -1)
109  {
110  // move the last object to the one being erased
111  if (mMapSize>1)
112  {
113  // move value
114  mValues[pos] = mValues[mMapSize-1];
115  // move Enum
116  mValueToKey[pos] = mValueToKey[mMapSize-1];
117  // mark moved KeyType to point to the new pos
118  mKeyToValue[mValueToKey[pos]] = pos;
119  }
120  mMapSize--;
121  VL_CHECK(mMapSize >= 0)
122  }
123  }
124 
125  int find(KeyType key) const
126  {
127  int pos = mKeyToValue[key];
128  VL_CHECK(pos >= 0)
129  VL_CHECK(pos < MaxMapType)
130  if (pos < mMapSize)
131  {
132  KeyType e = mValueToKey[pos];
133  VL_CHECK(e >= 0)
134  VL_CHECK(e < MaxMapType)
135  if (e == key)
136  return pos;
137  else
138  return -1;
139  }
140  else
141  return -1;
142  }
143 
144  bool hasKey(KeyType key) const
145  {
146  return find(key) != -1;
147  }
148 
149  const ValueType& valueFromKey(KeyType key) const
150  {
151  VL_CHECK(key >= 0)
152  VL_CHECK(key < MaxMapType)
153  VL_CHECK(mKeyToValue[key] >= 0)
154  VL_CHECK(mKeyToValue[key] < MaxMapType)
155  return mValues[mKeyToValue[key]];
156  }
157 
158  const ValueType& valueFromIndex(int i) const
159  {
160  return mValues[i];
161  }
162 
163  KeyType key(int i) const
164  {
165  return mValueToKey[i];
166  }
167 
168  protected:
169  // Note:
170  // In the case of EEnable we don't really need this
171  // (we would need only a set, not a map) but
172  // for the moment we use this for simplicity.
173  ValueType mValues[MaxMapType];
174  // given an index (< mMapSize) of a value returns it's KeyType (== index in mKeyToValue)
175  KeyType mValueToKey[MaxMapType];
176  // the number of elements in mValues and mValueToKey
177  int mMapSize;
178  // given a KeyType gives where in mValues and mValueToKey the value is.
179  int mKeyToValue[MaxMapType];
180  };
181 
182 }
183 
184 #endif
const ValueType & valueFromKey(KeyType key) const
KeyType mValueToKey[MaxMapType]
const ValueType & valueFromIndex(int i) const
void erase(KeyType key)
void insert(KeyType key)
void insert(KeyType key, const ValueType &value)
ValueType mValues[MaxMapType]
void append(KeyType key, ValueType value)
ValueType * begin()
void append(KeyType key)
Visualization Library main namespace.
int mKeyToValue[MaxMapType]
The base class for all the reference counted objects.
Definition: Object.hpp:158
const ValueType * begin() const
bool hasKey(KeyType key) const
int size() const
KeyType key(int i) const
Simple map used to add, remove, iterate, clear elements efficiently (all O(1)).
int find(KeyType key) const
ValueType * end()
#define VL_CHECK(expr)
Definition: checks.hpp:73
const ValueType * end() const