1/****************************************************************************************
2
3 Copyright (C) 2015 Autodesk, Inc.
4 All rights reserved.
5
6 Use of this software is subject to the terms of the Autodesk license agreement
7 provided at the time of installation or download, or which otherwise accompanies
8 this software in either electronic or hard copy form.
9
10****************************************************************************************/
11
12//! \file fbxmap.h
13#ifndef _FBXSDK_CORE_BASE_MAP_H_
14#define _FBXSDK_CORE_BASE_MAP_H_
15
16#include <fbxsdk/fbxsdk_def.h>
17
18#include <fbxsdk/core/base/fbxstring.h>
19#include <fbxsdk/core/base/fbxredblacktree.h>
20
21#include <fbxsdk/fbxsdk_nsbegin.h>
22
23class FbxObject;
24
25/** Default compare functor for FbxMap and FbxSet, which assumes operator < is defined.
26Here is examples of different compare class implementations:
27With Key = int
28\code
29class IntCompare
30{
31 inline int operator()(int pKeyA, int pKeyB) const
32 {
33 return pKeyA < pKeyB ? -1 : (pKeyA > pKeyB ? 1 : 0);
34 }
35};
36\endcode
37With Key = Class
38\code
39class ClassCompare
40{
41 inline int operator()(const Class& pKeyA, const Class& pKeyB) const
42 {
43 return pKeyA < pKeyB ? -1 : (pKeyA > pKeyB ? 1 : 0);
44 }
45};
46\endcode
47With Key = char*
48\code
49class StrCompare
50{
51 inline int operator()(const char* pKeyA, const char* pKeyB) const
52 {
53 return strcmp(pKeyA, pKeyB);
54 }
55};
56\endcode
57*/
58template <typename Type> struct FbxLessCompare
59{
60 inline int operator()(const Type& pLeft, const Type& pRight) const
61 {
62 return (pLeft < pRight) ? -1 : ((pRight < pLeft) ? 1 : 0);
63 }
64};
65
66/** This class implements an efficient map based on key comparison, which stores key-value pairs.
67It executes insertion, deletion and query operations in O(log(n)) time. */
68template <typename Key, typename Type, typename Compare=FbxLessCompare<Key>, typename Allocator=FbxBaseAllocator> class FbxMap
69{
70protected:
71 //! This class defines the key-value pairs used by the map.
72 class KeyValuePair : private FbxPair<const Key, Type>
73 {
74 /*****************************************************************************************************************************
75 ** WARNING! Anything beyond these lines is for internal use, may not be documented and is subject to change without notice! **
76 *****************************************************************************************************************************/
77 #ifndef DOXYGEN_SHOULD_SKIP_THIS
78 public:
79 typedef const Key KeyType;
80 typedef const Key ConstKeyType;
81 typedef Type ValueType;
82 typedef const Type ConstValueType;
83
84 KeyValuePair(const Key& pFirst, const Type& pSecond) : FbxPair<const Key, Type>(pFirst, pSecond){}
85 ConstKeyType& GetKey() const { return this->mFirst; }
86 KeyType& GetKey(){ return this->mFirst; }
87 ConstValueType& GetValue() const { return this->mSecond; }
88 ValueType& GetValue(){ return this->mSecond; }
89 #endif /* !DOXYGEN_SHOULD_SKIP_THIS *****************************************************************************************/
90 };
91
92 //! Declaration of the storage type used by the map.
93 typedef FbxRedBlackTree<KeyValuePair, Compare, Allocator> StorageType;
94
95public:
96 typedef Type ValueType;
97 typedef Key KeyType;
98 typedef typename StorageType::RecordType RecordType;
99 typedef typename StorageType::IteratorType Iterator;
100 typedef typename StorageType::ConstIteratorType ConstIterator;
101
102 /** Preallocate memory.
103 * \param pRecordCount The number of elements. */
104 inline void Reserve(unsigned int pRecordCount)
105 {
106 mTree.Reserve(pRecordCount);
107 }
108
109 //! Retrieve the number of key-value pairs it holds.
110 inline int GetSize() const
111 {
112 return mTree.GetSize();
113 }
114
115 /** Insert a key-value pair.
116 * \param pKey The key.
117 * \param pValue The value.
118 * \return If the key is already present in the map, returns the existing pair and false; else returns the pointer to the new key-value and true. */
119 inline FbxPair<RecordType*, bool> Insert(const KeyType& pKey, const ValueType& pValue)
120 {
121 return mTree.Insert(KeyValuePair(pKey, pValue));
122 }
123
124 /** Delete a key-value pair.
125 * \param pKey The key.
126 * \return \c true if success, \c false if key is not found. */
127 inline bool Remove(const KeyType& pKey)
128 {
129 return mTree.Remove(pKey);
130 }
131
132 //! Clear the map.
133 inline void Clear()
134 {
135 mTree.Clear();
136 }
137
138 //! Query whether the map is empty.
139 inline bool Empty() const
140 {
141 return mTree.Empty();
142 }
143
144 //! Retrieve the begin iterator of the map.
145 Iterator Begin()
146 {
147 return Iterator(Minimum());
148 }
149
150 //! Retrieve the end iterator of the map.
151 Iterator End()
152 {
153 return Iterator();
154 }
155
156 //! Retrieve the begin iterator of the map.
157 ConstIterator Begin() const
158 {
159 return ConstIterator(Minimum());
160 }
161
162 //! Retrieve the end iterator of the map.
163 ConstIterator End() const
164 {
165 return ConstIterator();
166 }
167
168 /** Query a key.
169 * \param pKey The key.
170 * \return A key-value pair if success, NULL if the key is not found. */
171 inline const RecordType* Find(const KeyType& pKey) const
172 {
173 return mTree.Find(pKey);
174 }
175
176 /** Query a key.
177 * \param pKey The key.
178 * \return A key-value pair if success, NULL if it's not found. */
179 inline RecordType* Find(const KeyType& pKey)
180 {
181 return mTree.Find(pKey);
182 }
183
184 /** Find the key-value pair with the smallest key greater than a specified key.
185 * \param pKey The key.
186 * \return The found key-value pair. */
187 inline const RecordType* UpperBound(const KeyType& pKey) const
188 {
189 return mTree.UpperBound(pKey);
190 }
191
192 /** Find the key-value pair with the smallest key greater than a specified key.
193 * \param pKey The key.
194 * \return The found key-value pair. */
195 inline RecordType* UpperBound(const KeyType& pKey)
196 {
197 return mTree.UpperBound(pKey);
198 }
199
200 /** Retrieve the reference of the value in the key-value pairs in map.
201 * \param pKey The key.
202 * \return The reference of the value.
203 * \remark If the key is not found, a new key-value pair will be inserted. */
204 inline ValueType& operator[](const KeyType& pKey)
205 {
206 RecordType* lRecord = Find(pKey);
207
208 if( !lRecord )
209 {
210 lRecord = Insert(pKey, ValueType()).mFirst;
211 }
212
213 return lRecord->GetValue();
214 }
215
216 //! Retrieve the key-value pair which is the minimum key in map.
217 inline const RecordType* Minimum() const
218 {
219 return mTree.Minimum();
220 }
221
222 //! Retrieve the key-value pair which is the minimum key in map.
223 inline RecordType* Minimum()
224 {
225 return mTree.Minimum();
226 }
227
228 //! Retrieve the key-value pair which is the maximum key in map.
229 inline const RecordType* Maximum() const
230 {
231 return mTree.Maximum();
232 }
233
234 //! Retrieve the key-value pair which is the maximum key in map.
235 inline RecordType* Maximum()
236 {
237 return mTree.Maximum();
238 }
239
240/*****************************************************************************************************************************
241** WARNING! Anything beyond these lines is for internal use, may not be documented and is subject to change without notice! **
242*****************************************************************************************************************************/
243#ifndef DOXYGEN_SHOULD_SKIP_THIS
244 inline FbxMap(){}
245 inline FbxMap(const FbxMap& pMap) : mTree(pMap.mTree){}
246 inline ~FbxMap(){ Clear(); }
247
248private:
249 StorageType mTree;
250#endif /* !DOXYGEN_SHOULD_SKIP_THIS *****************************************************************************************/
251};
252
253/** A simple map class representing a dictionary-like data structure.
254* \nosubgrouping */
255template <class Key, class Type, class Compare> class FBXSDK_DLL FbxSimpleMap
256{
257public:
258 typedef typename FbxMap<Key, Type, Compare>::RecordType* Iterator;
259
260 /** Add a key-value pair as an element.
261 * \param pKey The new key.
262 * \param pValue The new value. */
263 inline void Add(const Key& pKey, const Type& pValue)
264 {
265 mMap.Insert(pKey, pValue);
266 }
267
268 /** Find an element with a given key.
269 * \param pKey The given key.
270 * \return The iterator pointing to the found element or NULL if fails. */
271 inline Iterator Find(const Key& pKey) const
272 {
273 return (Iterator)mMap.Find(pKey);
274 }
275
276 /** Find an element with a given value.
277 * \param pValue The given value.
278 * \return The iterator pointing to the found element or NULL if fails. */
279 inline Iterator Find(const Type& pValue) const
280 {
281 Iterator lIterator = GetFirst();
282 while( lIterator )
283 {
284 if( lIterator->GetValue() == pValue )
285 {
286 return lIterator;
287 }
288 lIterator = GetNext(lIterator);
289 }
290 return 0;
291 }
292
293 /** Remove an element from the map.
294 * \param pIterator The given element. */
295 inline void Remove(Iterator pIterator)
296 {
297 if( pIterator ) mMap.Remove(pIterator->GetKey());
298 }
299
300 /** Get the first element.
301 * \return The the heading element. */
302 inline Iterator GetFirst() const
303 {
304 return (Iterator)mMap.Minimum();
305 }
306
307 /** Get the next element of a given element.
308 * \param pIterator The given element.
309 * \return The next element. */
310 inline Iterator GetNext(Iterator pIterator) const
311 {
312 return (Iterator)pIterator ? pIterator->Successor() : 0;
313 }
314
315 //! Remove all of the elements.
316 inline void Clear()
317 {
318 mMap.Clear();
319 }
320
321 /** Reserve the space for given number elements.
322 * \param pSize The given number. */
323 inline void Reserve(int pSize)
324 {
325 mMap.Reserve(pSize);
326 }
327
328 /** Query the count of elements in the map.
329 * \return The count of elements. */
330 inline int GetCount() const
331 {
332 return mMap.GetSize();
333 }
334
335/*****************************************************************************************************************************
336** WARNING! Anything beyond these lines is for internal use, may not be documented and is subject to change without notice! **
337*****************************************************************************************************************************/
338#ifndef DOXYGEN_SHOULD_SKIP_THIS
339 inline FbxSimpleMap(){}
340
341private:
342 FbxMap<Key, Type, Compare> mMap;
343#endif /* !DOXYGEN_SHOULD_SKIP_THIS *****************************************************************************************/
344};
345
346/** This class template declare a simple FbxObject map.
347* \nosubgrouping */
348template <class Type, class Compare> class FBXSDK_DLL FbxObjectMap : public FbxSimpleMap<Type, FbxObject*, Compare>
349{
350public:
351 //! Constructor
352 inline FbxObjectMap(){}
353
354 /** Get the object contained in an element.
355 * \param pIterator The given element.
356 * \return The object.
357 */
358 inline FbxObject* Get(typename FbxSimpleMap<Type, FbxObject*, Compare>::Iterator pIterator)
359 {
360 return pIterator ? pIterator->GetValue() : 0;
361 }
362};
363
364/** A class that maps strings to objects with a basic string comparator.
365* \nosubgrouping */
366class FBXSDK_DLL FbxObjectStringMap : public FbxObjectMap<FbxString, FbxStringCompare>
367{
368public:
369 //! Constructor
370 inline FbxObjectStringMap(){}
371};
372
373//! Call FbxFree on each element of the map, and then clear it.
374template <typename K, typename V, typename C, typename A> inline void FbxMapFree(FbxMap<K, V, C, A>& pMap)
375{
376 for( typename FbxMap<K, V, C, A>::Iterator i = pMap.Begin(); i != pMap.End(); ++i )
377 {
378 FbxFree(i->GetValue());
379 }
380 pMap.Clear();
381}
382
383//! Call FbxDelete on each element of the map, and then clear it.
384template <typename K, typename V, typename C, typename A> inline void FbxMapDelete(FbxMap<K, V, C, A>& pMap)
385{
386 for( typename FbxMap<K, V, C, A>::Iterator i = pMap.Begin(); i != pMap.End(); ++i )
387 {
388 FbxDelete(i->GetValue());
389 }
390 pMap.Clear();
391}
392
393//! Call Destroy on each element of the map, and then clear it.
394template <typename K, typename V, typename C, typename A> inline void FbxMapDestroy(FbxMap<K, V, C, A>& pMap)
395{
396 for( typename FbxMap<K, V, C, A>::Iterator i = pMap.Begin(); i != pMap.End(); ++i )
397 {
398 i->GetValue()->Destroy();
399 }
400 pMap.Clear();
401}
402
403template class FbxSimpleMap<FbxString, FbxObject*, FbxStringCompare>;
404template class FbxObjectMap<FbxString, FbxStringCompare>;
405
406#include <fbxsdk/fbxsdk_nsend.h>
407
408#endif /* _FBXSDK_CORE_BASE_MAP_H_ */
409