00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033 #ifndef _AKSET_H_
00034 #define _AKSET_H_
00035
00036 #include <AK/Tools/Common/AkKeyArray.h>
00037
00038
00039
00040
00041 enum AkSetType
00042 {
00043 SetType_Inclusion,
00044
00045 SetType_Exclusion
00046
00047 };
00048
00049 template<typename T>
00050 struct AkSetGetKey{ static AkForceInline T& Get(T& in_item){ return in_item; } };
00051
00052
00053
00054
00055
00056 template< typename T, class U_POOL, AkUInt32 uGrowBy = 1 >
00057 class AkSet : public AkSortedKeyArray < T, T, U_POOL, AkSetGetKey<T>, uGrowBy >
00058 {
00059 public:
00060 bool Contains(T in_item) const { return AkSortedKeyArray < T, T, U_POOL, AkSetGetKey<T>, uGrowBy >::Exists(in_item) != NULL; }
00061 };
00062
00063
00064
00065
00066 template< typename T, class U_POOL, AkUInt32 uGrowBy >
00067 static bool AkDisjoint(const AkSet<T, U_POOL, uGrowBy>& in_A, const AkSet<T, U_POOL, uGrowBy>& in_B)
00068 {
00069 typename AkSet<T, U_POOL, uGrowBy>::Iterator itA = in_A.Begin();
00070 typename AkSet<T, U_POOL, uGrowBy>::Iterator itB = in_B.Begin();
00071 while (itA != in_A.End() && itB != in_B.End())
00072 {
00073 if (*itA == *itB)
00074 return false;
00075 else if (*itA < *itB)
00076 ++itA;
00077 else
00078 ++itB;
00079 }
00080 return true;
00081 }
00082
00083
00084
00085
00086 template< typename T, class U_POOL, AkUInt32 uGrowBy >
00087 static bool AkIntersect(const AkSet<T, U_POOL, uGrowBy>& in_A, const AkSet<T, U_POOL, uGrowBy>& in_B)
00088 {
00089 return !AkDisjoint(in_A, in_B);
00090 }
00091
00092
00093
00094
00095 template< typename T, class U_POOL, AkUInt32 uGrowBy >
00096 static bool AkIsSubset(const AkSet<T, U_POOL, uGrowBy>& in_A, const AkSet<T, U_POOL, uGrowBy>& in_B)
00097 {
00098 typename AkSet<T, U_POOL, uGrowBy>::Iterator itA = in_A.Begin();
00099 typename AkSet<T, U_POOL, uGrowBy>::Iterator itB = in_B.Begin();
00100 while (itA != in_A.End() && itB != in_B.End())
00101 {
00102 if (*itA == *itB)
00103 {
00104 ++itA; ++itB;
00105 }
00106 else if (*itA < *itB)
00107 {
00108 return false;
00109 }
00110 else
00111 ++itB;
00112 }
00113 return (itA == in_A.End());
00114 }
00115
00116
00117
00118
00119 template< typename T, class U_POOL, AkUInt32 uGrowBy >
00120 static AkUInt32 AkCountIntersection(const AkSet<T, U_POOL, uGrowBy>& in_A, const AkSet<T, U_POOL, uGrowBy>& in_B)
00121 {
00122 AkUInt32 uSize = 0;
00123 typename AkSet<T, U_POOL, uGrowBy>::Iterator itA = in_A.Begin();
00124 typename AkSet<T, U_POOL, uGrowBy>::Iterator itB = in_B.Begin();
00125 while (itA != in_A.End() && itB != in_B.End())
00126 {
00127 if (*itA == *itB)
00128 {
00129 ++uSize; ++itA; ++itB;
00130 }
00131 else if (*itA < *itB)
00132 {
00133 ++itA;
00134 }
00135 else
00136 {
00137 ++itB;
00138 }
00139 }
00140 return uSize;
00141 }
00142
00143
00144
00145
00146 template< typename T, class U_POOL, AkUInt32 uGrowBy >
00147 static bool AkSubtraction(AkSet<T, U_POOL, uGrowBy>& in_A, const AkSet<T, U_POOL, uGrowBy>& in_B)
00148 {
00149 typename AkSet<T, U_POOL, uGrowBy>::Iterator itAr, itAw;
00150 itAr = itAw = in_A.Begin();
00151 typename AkSet<T, U_POOL, uGrowBy>::Iterator itB = in_B.Begin();
00152 while (itAr != in_A.End())
00153 {
00154 if (itB == in_B.End() || *itAr < *itB)
00155 {
00156 if (itAw != itAr)
00157 *itAw = *itAr;
00158
00159 ++itAw;
00160 ++itAr;
00161 }
00162 else if (*itAr == *itB)
00163 {
00164 ++itB;
00165 ++itAr;
00166 }
00167 else
00168 {
00169 ++itB;
00170 }
00171 }
00172 in_A.Resize((AkUInt32)(itAw.pItem - in_A.Begin().pItem));
00173 return true;
00174 }
00175
00176
00177
00178
00179 template< typename T, class U_POOL, AkUInt32 uGrowBy >
00180 static bool AkIntersection(AkSet<T, U_POOL, uGrowBy>& in_A, const AkSet<T, U_POOL, uGrowBy>& in_B)
00181 {
00182 typename AkSet<T, U_POOL, uGrowBy>::Iterator itAr, itAw;
00183 itAr = itAw = in_A.Begin();
00184 typename AkSet<T, U_POOL, uGrowBy>::Iterator itB = in_B.Begin();
00185 while (itAr != in_A.End() && itB != in_B.End())
00186 {
00187 if (*itAr == *itB)
00188 {
00189 if (itAw != itAr)
00190 *itAw = *itAr;
00191
00192 ++itAw;
00193 ++itAr;
00194 ++itB;
00195 }
00196 else if (*itAr < *itB)
00197 {
00198 ++itAr;
00199 }
00200 else
00201 {
00202 ++itB;
00203 }
00204 }
00205 in_A.Resize((AkUInt32)(itAw.pItem - in_A.Begin().pItem));
00206 return true;
00207 }
00208
00209
00210
00211
00212
00213 template< typename T, class U_POOL, AkUInt32 uGrowBy >
00214 static bool AkUnion(AkSet<T, U_POOL, uGrowBy>& io_A, const AkSet<T, U_POOL, uGrowBy>& in_B)
00215 {
00216 AkInt32 uSizeNeeded = io_A.Length() + in_B.Length() - AkCountIntersection(io_A, in_B);
00217 AkSet<T, U_POOL, uGrowBy> result;
00218
00219 if (result.Resize(uSizeNeeded))
00220 {
00221 typename AkSet<T, U_POOL, uGrowBy>::Iterator itRes = result.Begin();
00222 typename AkSet<T, U_POOL, uGrowBy>::Iterator itA = io_A.Begin();
00223 typename AkSet<T, U_POOL, uGrowBy>::Iterator itB = in_B.Begin();
00224
00225 while (itB != in_B.End() || itA != io_A.End())
00226 {
00227 if ( itB != in_B.End() && (itA == io_A.End() || *itB < *itA))
00228 {
00229 *itRes = *itB;
00230 ++itB;
00231 }
00232 else if (itB == in_B.End() || *itA < *itB)
00233 {
00234 *itRes = *itA;
00235 ++itA;
00236 }
00237 else
00238 {
00239 *itRes = *itA;
00240 ++itA;
00241 ++itB;
00242 }
00243
00244 ++itRes;
00245 }
00246
00247 io_A.Transfer(result);
00248 return true;
00249 }
00250
00251 return false;
00252 }
00253
00254 typedef AkSet< AkUniqueID, ArrayPoolDefault > AkUniqueIDSet;
00255
00256
00257
00258
00259 template< typename T, class U_POOL, AkUInt32 uGrowBy >
00260 static inline bool AkIntersect(const AkSet<T, U_POOL, uGrowBy>& in_A, AkSetType in_typeA, const AkSet<T, U_POOL, uGrowBy>& in_B, AkSetType in_typeB)
00261 {
00262 if (in_typeA == SetType_Inclusion)
00263 {
00264 if (in_typeB == SetType_Inclusion)
00265 return !AkDisjoint(in_A, in_B);
00266 else
00267 return !AkIsSubset(in_A, in_B);
00268 }
00269 else
00270 {
00271 if (in_typeB == SetType_Inclusion)
00272 return !AkIsSubset(in_B, in_A);
00273 else
00274 return true;
00275 }
00276 }
00277
00278
00279
00280
00281 template< typename T, class U_POOL, AkUInt32 uGrowBy >
00282 static inline bool AkContains(const AkSet<T, U_POOL, uGrowBy>& in_Set, AkSetType in_type, T in_item)
00283 {
00284 return (in_type == SetType_Inclusion && in_Set.Contains(in_item)) ||
00285 (in_type == SetType_Exclusion && !in_Set.Contains(in_item));
00286 }
00287
00288
00289
00290
00291
00292 template< typename T, class U_POOL, AkUInt32 uGrowBy >
00293 static inline bool AkSubtraction(AkSet<T, U_POOL, uGrowBy>& in_A, AkSetType in_typeA, const AkSet<T, U_POOL, uGrowBy>& in_B, AkSetType in_typeB)
00294 {
00295 if (in_typeA == SetType_Inclusion)
00296 {
00297 if (in_typeB == SetType_Inclusion)
00298 return AkSubtraction(in_A, in_B);
00299 else
00300 return AkIntersection(in_A, in_B);
00301 }
00302 else
00303 {
00304 if (in_typeB == SetType_Inclusion)
00305 return AkUnion(in_A, in_B);
00306 else
00307 return AkIntersection(in_A, in_B);
00308 }
00309 }
00310
00311
00312
00313
00314
00315 template< typename T, class U_POOL, AkUInt32 uGrowBy >
00316 static inline bool AkUnion(AkSet<T, U_POOL, uGrowBy>& io_A, AkSetType& io_typeA, const AkSet<T, U_POOL, uGrowBy>& in_B, AkSetType in_typeB)
00317 {
00318 if (io_typeA == SetType_Inclusion)
00319 {
00320 if (in_typeB == SetType_Inclusion)
00321 return AkUnion(io_A, in_B);
00322 else
00323 {
00324 AkSet<T, U_POOL, uGrowBy> temp;
00325 temp.Transfer(io_A);
00326 if (io_A.Copy(in_B) == AK_Success)
00327 {
00328 io_typeA = SetType_Exclusion;
00329 AkSubtraction(io_A, temp);
00330 temp.Term();
00331 return true;
00332 }
00333 else
00334 {
00335 io_A.Transfer(temp);
00336 return false;
00337 }
00338 }
00339 }
00340 else
00341 {
00342 if (in_typeB == SetType_Inclusion)
00343 return AkSubtraction(io_A, in_B);
00344 else
00345 return AkIntersection(io_A, in_B);
00346 }
00347 }
00348
00349 #endif
00350