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 fbxset.h
13#ifndef _FBXSDK_CORE_BASE_SET_H_
14#define _FBXSDK_CORE_BASE_SET_H_
15
16#include <fbxsdk/fbxsdk_def.h>
17
18#include <fbxsdk/core/base/fbxredblacktree.h>
19#include <fbxsdk/core/base/fbxmap.h>
20
21#include <fbxsdk/fbxsdk_nsbegin.h>
22
23/** This class implements an efficient set based on value comparison, which stores values.
24* It executes insertion, deletion and query operations in O(log(n)) time. */
25template <typename Type, typename Compare=FbxLessCompare<Type>, typename Allocator=FbxBaseAllocator> class FbxSet
26{
27protected:
28 //! This class defines the value type used by the set.
29 class Value
30 {
31 /*****************************************************************************************************************************
32 ** WARNING! Anything beyond these lines is for internal use, may not be documented and is subject to change without notice! **
33 *****************************************************************************************************************************/
34 #ifndef DOXYGEN_SHOULD_SKIP_THIS
35 public:
36 typedef const Type KeyType;
37 typedef const Type ConstKeyType;
38 typedef const Type ValueType;
39 typedef const Type ConstValueType;
40
41 inline Value(const Type& pValue) : mValue(pValue){}
42 inline KeyType& GetKey() const { return mValue; }
43 inline ConstKeyType& GetKey(){ return mValue; }
44 inline ValueType& GetValue() const { return mValue; }
45 inline ConstValueType& GetValue(){ return mValue; }
46
47 protected:
48 ValueType mValue;
49
50 private:
51 Value& operator=(const Value&);
52 #endif /* !DOXYGEN_SHOULD_SKIP_THIS *****************************************************************************************/
53 };
54
55 //! Declaration of the storage type used by the set.
56 typedef FbxRedBlackTree<Value, Compare, Allocator> StorageType;
57
58public:
59 typedef Type ValueType;
60 typedef typename StorageType::RecordType RecordType;
61 typedef typename StorageType::IteratorType Iterator;
62 typedef typename StorageType::ConstIteratorType ConstIterator;
63
64 /** Preallocate memory.
65 * \param pRecordCount The number of elements.
66 */
67 inline void Reserve(unsigned int pRecordCount)
68 {
69 mTree.Reserve(pRecordCount);
70 }
71
72 //! Retrieve the number of values it holds.
73 inline int GetSize() const
74 {
75 return mTree.GetSize();
76 }
77
78 /** Insert a value.
79 * \param pValue The value.
80 * \return If the value is already present in the map, returns the existing value and false; else returns the pointer to the new value and true. */
81 inline FbxPair<RecordType*, bool> Insert(const ValueType& pValue)
82 {
83 return mTree.Insert(Value(pValue));
84 }
85
86 /** Delete a value.
87 * \param pValue The value.
88 * \return \c true if success, \c false if value is not found. */
89 inline int Remove(const ValueType& pValue)
90 {
91 return mTree.Remove(pValue);
92 }
93
94 //! Clear the set.
95 inline void Clear()
96 {
97 mTree.Clear();
98 }
99
100 //! Query whether the set is empty.
101 inline bool Empty() const
102 {
103 return mTree.Empty();
104 }
105
106 //! Retrieve the begin iterator of the set.
107 Iterator Begin()
108 {
109 return Iterator(Minimum());
110 }
111
112 //! Retrieve the end iterator of the set.
113 Iterator End()
114 {
115 return Iterator();
116 }
117
118 //! Retrieve the begin iterator of the set.
119 ConstIterator Begin() const
120 {
121 return ConstIterator(Minimum());
122 }
123
124 //! Retrieve the end iterator of the set.
125 ConstIterator End() const
126 {
127 return ConstIterator();
128 }
129
130 /** Find a given value in the set.
131 * \param pValue The value to find.
132 * \return The value in the set, or NULL if the value is not found in the set. */
133 inline const RecordType* Find(const ValueType& pValue) const
134 {
135 return mTree.Find(pValue);
136 }
137
138 /** Find a given value in the set.
139 * \param pValue The value to find.
140 * \return The value in the set, or NULL if the value is not found in the set. */
141 inline RecordType* Find(const ValueType& pValue)
142 {
143 return mTree.Find(pValue);
144 }
145
146 //! Retrieve the minimum value in the set.
147 inline const RecordType* Minimum() const
148 {
149 return mTree.Minimum();
150 }
151
152 //! Retrieve the minimum value in the set.
153 inline RecordType* Minimum()
154 {
155 return mTree.Minimum();
156 }
157
158 //! Retrieve the maximum value in the set.
159 inline const RecordType* Maximum() const
160 {
161 return mTree.Maximum();
162 }
163
164 //! Retrieve the maximum value in the set.
165 inline RecordType* Maximum()
166 {
167 return mTree.Maximum();
168 }
169
170 //! Equality operator.
171 inline bool operator==(const FbxSet<Type, Compare, Allocator>& pOther) const
172 {
173 return (this == &pOther) || (mTree == pOther.mTree);
174 }
175
176 //! Inequality operator.
177 inline bool operator != (const FbxSet<Type, Compare, Allocator>& pOther) const
178 {
179 return !(*this == pOther);
180 }
181
182 /** Intersect with another set.
183 * \param pOther The other set.
184 * \return The intersection set of the two sets. */
185 inline FbxSet Intersect(const FbxSet& pOther) const
186 {
187 FbxSet lReturn;
188 ConstIterator lBegin = Begin();
189 for (; lBegin != End(); ++lBegin)
190 {
191 if (pOther.Find(lBegin->GetValue()) != NULL)
192 lReturn.Insert(lBegin->GetValue());
193 }
194 return lReturn;
195 }
196
197 /** Unite with another set.
198 * \param pOther The other set.
199 * \return The union set of the two sets (no duplicated items). */
200 inline FbxSet Union(const FbxSet& pOther) const
201 {
202 FbxSet lReturn(*this);
203 ConstIterator lBegin = pOther.Begin();
204 for (; lBegin != End(); ++lBegin)
205 {
206 if (Find(lBegin->GetValue()) == NULL)
207 lReturn.Insert(lBegin->GetValue());
208 }
209 return lReturn;
210 }
211
212/*****************************************************************************************************************************
213** WARNING! Anything beyond these lines is for internal use, may not be documented and is subject to change without notice! **
214*****************************************************************************************************************************/
215#ifndef DOXYGEN_SHOULD_SKIP_THIS
216 inline FbxSet(){}
217 inline FbxSet(const FbxSet& pSet) : mTree(pSet.mTree){}
218 inline ~FbxSet(){ Clear(); }
219
220private:
221 StorageType mTree;
222#endif /* !DOXYGEN_SHOULD_SKIP_THIS *****************************************************************************************/
223};
224
225#include <fbxsdk/fbxsdk_nsend.h>
226
227#endif /* _FBXSDK_CORE_BASE_SET_H_ */
228