ezEngine  Milestone 7
ArrayMap_inl.h
1 #pragma once
2 
3 template<typename KEY, typename VALUE>
4 inline ezArrayMapBase<KEY, VALUE>::ezArrayMapBase(ezAllocatorBase* pAllocator) : m_Data(pAllocator)
5 {
6  m_bSorted = true;
7 }
8 
9 template<typename KEY, typename VALUE>
10 inline ezArrayMapBase<KEY, VALUE>::ezArrayMapBase(const ezArrayMapBase& rhs, ezAllocatorBase* pAllocator) : m_bSorted(rhs.m_bSorted), m_Data(pAllocator)
11 {
12  m_Data = rhs.m_Data;
13 }
14 
15 template<typename KEY, typename VALUE>
17 {
18  m_bSorted = rhs.m_bSorted;
19  m_Data = rhs.m_Data;
20 }
21 
22 template<typename KEY, typename VALUE>
23 EZ_FORCE_INLINE ezUInt32 ezArrayMapBase<KEY, VALUE>::GetCount() const
24 {
25  return m_Data.GetCount();
26 }
27 
28 template<typename KEY, typename VALUE>
29 EZ_FORCE_INLINE bool ezArrayMapBase<KEY, VALUE>::IsEmpty() const
30 {
31  return m_Data.IsEmpty();
32 }
33 
34 template<typename KEY, typename VALUE>
36 {
37  m_bSorted = true;
38  m_Data.Clear();
39 }
40 
41 template<typename KEY, typename VALUE>
42 inline ezUInt32 ezArrayMapBase<KEY, VALUE>::Insert(const KEY& key, const VALUE& value)
43 {
44  Pair& ref = m_Data.ExpandAndGetRef();
45  ref.key = key;
46  ref.value = value;
47  m_bSorted = false;
48 
49  return m_Data.GetCount() - 1;
50 }
51 
52 template<typename KEY, typename VALUE>
54 {
55  if (m_bSorted)
56  return;
57 
58  m_bSorted = true;
59  m_Data.Sort();
60 }
61 
62 template<typename KEY, typename VALUE>
63 ezUInt32 ezArrayMapBase<KEY, VALUE>::Find(const KEY& key) const
64 {
65  if (!m_bSorted)
66  {
67  m_bSorted = true;
68  m_Data.Sort();
69  }
70 
71  ezUInt32 lb = 0;
72  ezUInt32 ub = m_Data.GetCount();
73 
74  while (lb < ub)
75  {
76  const ezUInt32 middle = lb + ((ub - lb) >> 1);
77 
78  if (m_Data[middle].key < key)
79  {
80  lb = middle + 1;
81  }
82  else if (key < m_Data[middle].key)
83  {
84  ub = middle;
85  }
86  else // equal
87  {
88  return middle;
89  }
90  }
91 
92  return ezInvalidIndex;
93 }
94 
95 template<typename KEY, typename VALUE>
96 ezUInt32 ezArrayMapBase<KEY, VALUE>::LowerBound(const KEY& key) const
97 {
98  if (!m_bSorted)
99  {
100  m_bSorted = true;
101  m_Data.Sort();
102  }
103 
104  ezUInt32 lb = 0;
105  ezUInt32 ub = m_Data.GetCount();
106 
107  while (lb < ub)
108  {
109  const ezUInt32 middle = lb + ((ub - lb) >> 1);
110 
111  if (m_Data[middle].key < key)
112  {
113  lb = middle + 1;
114  }
115  else
116  {
117  ub = middle;
118  }
119  }
120 
121  if (lb == m_Data.GetCount())
122  return ezInvalidIndex;
123 
124  return lb;
125 }
126 
127 template<typename KEY, typename VALUE>
128 ezUInt32 ezArrayMapBase<KEY, VALUE>::UpperBound(const KEY& key) const
129 {
130  if (!m_bSorted)
131  {
132  m_bSorted = true;
133  m_Data.Sort();
134  }
135 
136  ezUInt32 lb = 0;
137  ezUInt32 ub = m_Data.GetCount();
138 
139  while (lb < ub)
140  {
141  const ezUInt32 middle = lb + ((ub - lb) >> 1);
142 
143  if (key < m_Data[middle].key)
144  {
145  ub = middle;
146  }
147  else
148  {
149  lb = middle + 1;
150  }
151  }
152 
153  if (ub == m_Data.GetCount())
154  return ezInvalidIndex;
155 
156  return ub;
157 }
158 
159 template<typename KEY, typename VALUE>
160 EZ_FORCE_INLINE const KEY& ezArrayMapBase<KEY, VALUE>::GetKey(ezUInt32 index) const
161 {
162  return m_Data[index].key;
163 }
164 
165 template<typename KEY, typename VALUE>
166 EZ_FORCE_INLINE const VALUE& ezArrayMapBase<KEY, VALUE>::GetValue(ezUInt32 index) const
167 {
168  return m_Data[index].value;
169 }
170 
171 template<typename KEY, typename VALUE>
173 {
174  return m_Data[index].value;
175 }
176 
177 template<typename KEY, typename VALUE>
178 VALUE& ezArrayMapBase<KEY, VALUE>::FindOrAdd(const KEY& key, bool* bExisted)
179 {
180  ezUInt32 index = Find(key);
181 
182  if (bExisted)
183  *bExisted = index != ezInvalidIndex;
184 
185  if (index == ezInvalidIndex)
186  {
187  index = Insert(key, VALUE());
188  }
189 
190  return GetValue(index);
191 }
192 
193 template<typename KEY, typename VALUE>
194 EZ_FORCE_INLINE VALUE& ezArrayMapBase<KEY, VALUE>::operator[](const KEY& key)
195 {
196  return FindOrAdd(key);
197 }
198 
199 template<typename KEY, typename VALUE>
200 EZ_FORCE_INLINE const typename ezArrayMapBase<KEY, VALUE>::Pair& ezArrayMapBase<KEY, VALUE>::operator[](ezUInt32 index) const
201 {
202  return m_Data[index];
203 }
204 
205 template<typename KEY, typename VALUE>
206 void ezArrayMapBase<KEY, VALUE>::RemoveAt(ezUInt32 index, bool bKeepSorted)
207 {
208  if (bKeepSorted && m_bSorted)
209  {
210  m_Data.RemoveAt(index);
211  }
212  else
213  {
214  m_Data.RemoveAtSwap(index);
215  m_bSorted = false;
216  }
217 }
218 
219 template<typename KEY, typename VALUE>
220 bool ezArrayMapBase<KEY, VALUE>::Remove(const KEY& key, bool bKeepSorted)
221 {
222  const ezUInt32 uiIndex = Find(key);
223 
224  if (uiIndex == ezInvalidIndex)
225  return false;
226 
227  RemoveAt(uiIndex, bKeepSorted);
228  return true;
229 }
230 
231 template<typename KEY, typename VALUE>
232 EZ_FORCE_INLINE bool ezArrayMapBase<KEY, VALUE>::Contains(const KEY& key) const
233 {
234  return Find(key) != ezInvalidIndex;
235 }
236 
237 template<typename KEY, typename VALUE>
238 EZ_FORCE_INLINE void ezArrayMapBase<KEY, VALUE>::Reserve(ezUInt32 size)
239 {
240  m_Data.Reserve(size);
241 }
242 
243 template<typename KEY, typename VALUE>
245 {
246  m_Data.Compact();
247 }
248 
249 template<typename KEY, typename VALUE>
251 {
252  Sort();
253  rhs.Sort();
254 
255  return m_Data == rhs.m_Data;
256 }
257 
258 template<typename KEY, typename VALUE>
260 {
261  return !(*this == rhs);
262 }
263 
264 template<typename KEY, typename VALUE, typename A>
265 ezArrayMap<KEY, VALUE, A>::ezArrayMap() : ezArrayMapBase<KEY, VALUE>(A::GetAllocator())
266 {
267 }
268 
269 template<typename KEY, typename VALUE, typename A>
270 ezArrayMap<KEY, VALUE, A>::ezArrayMap(ezAllocatorBase* pAllocator) : ezArrayMapBase<KEY, VALUE>(pAllocator)
271 {
272 }
273 
274 template<typename KEY, typename VALUE, typename A>
275 ezArrayMap<KEY, VALUE, A>::ezArrayMap(const ezArrayMap<KEY, VALUE, A>& rhs) : ezArrayMapBase<KEY, VALUE>(rhs, A::GetAllocator())
276 {
277 }
278 
279 template<typename KEY, typename VALUE, typename A>
280 ezArrayMap<KEY, VALUE, A>::ezArrayMap(const ezArrayMapBase<KEY, VALUE>& rhs) : ezArrayMapBase<KEY, VALUE>(rhs, A::GetAllocator())
281 {
282 }
283 
284 template<typename KEY, typename VALUE, typename A>
286 {
288 }
289 
290 template<typename KEY, typename VALUE, typename A>
292 {
294 }