Table of Contents

include/AK/Tools/Common/AkSet.h

Go to the documentation of this file.
00001 /*******************************************************************************
00002 The content of this file includes portions of the AUDIOKINETIC Wwise Technology
00003 released in source code form as part of the SDK installer package.
00004 
00005 Commercial License Usage
00006 
00007 Licensees holding valid commercial licenses to the AUDIOKINETIC Wwise Technology
00008 may use this file in accordance with the end user license agreement provided 
00009 with the software or, alternatively, in accordance with the terms contained in a
00010 written agreement between you and Audiokinetic Inc.
00011 
00012 Apache License Usage
00013 
00014 Alternatively, this file may be used under the Apache License, Version 2.0 (the 
00015 "Apache License"); you may not use this file except in compliance with the 
00016 Apache License. You may obtain a copy of the Apache License at 
00017 http://www.apache.org/licenses/LICENSE-2.0.
00018 
00019 Unless required by applicable law or agreed to in writing, software distributed
00020 under the Apache License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES
00021 OR CONDITIONS OF ANY KIND, either express or implied. See the Apache License for
00022 the specific language governing permissions and limitations under the License.
00023 
00024   Version: <VERSION>  Build: <BUILDNUMBER>
00025   Copyright (c) <COPYRIGHTYEAR> Audiokinetic Inc.
00026 *******************************************************************************/
00027 
00028 //////////////////////////////////////////////////////////////////////
00029 //
00030 // AkSet.h
00031 //
00032 //////////////////////////////////////////////////////////////////////
00033 #ifndef _AKSET_H_
00034 #define _AKSET_H_
00035 
00036 #include <AK/Tools/Common/AkKeyArray.h>
00037 
00038 // AkSetType
00039 //  - An optional set type specifier which is passed into some set operations.  If it is not included, SetType_Inclusion is assumed.
00040 //
00041 enum AkSetType
00042 {
00043     SetType_Inclusion,  // <- An AkSet object with type SetType_Inclusion is a set where each element in the array 
00044                         //      represents an element in the set.  An empty array represents the empty set.
00045     SetType_Exclusion   // <- An AkSet object with type SetType_Exclusion is an 'inverted' set, where each element in the array 
00046                         //      represents and element NOT in the set. An empty array represents the universal set.  
00047 };
00048 
00049 template<typename T>
00050 struct AkSetGetKey{ static AkForceInline T& Get(T& in_item){ return in_item; } };
00051 
00052 // AkSet
00053 //
00054 //  Set container type, implemented as a sorted array of unique items
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 // AkDisjoint
00064 //  - Returns true if the intersection of A and B is the empty set.
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 // AkIntersect
00084 //  - Return true if the intersection of A and B is not the empty set.
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 // AkIsSubset
00093 //  - Return true if in_A is a subset of in_B
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;//an element of A is not in B
00109         }
00110         else
00111             ++itB;
00112     }
00113     return (itA == in_A.End());
00114 }
00115 
00116 // AkCountIntersection
00117 //  - Helper function to count the number of elements that are in both in_A and in_B.
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 // AkSubtraction
00144 //  - In-place set subtraction ( A = A - B )
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 // AkIntersection
00177 //  - In-place set intersection ( A = A n B )
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 // AkIntersection
00210 //  - Out-of-place set intersection ( res = A n B )
00211 //
00212 template< typename T, class U_POOL, AkUInt32 uGrowBy >
00213 static bool AkIntersection(AkSet<T, U_POOL, uGrowBy>& out_res, const AkSet<T, U_POOL, uGrowBy>& in_A, const AkSet<T, U_POOL, uGrowBy>& in_B)
00214 {
00215     out_res.RemoveAll();
00216 
00217     typename AkSet<T, U_POOL, uGrowBy>::Iterator itA = in_A.Begin();
00218     typename AkSet<T, U_POOL, uGrowBy>::Iterator itB = in_B.Begin();
00219     while (itA != in_A.End() && itB != in_B.End())
00220     {
00221         if (*itA == *itB)
00222         {
00223             out_res.AddLast(*itA);
00224 
00225             ++itA;
00226             ++itB;
00227         }
00228         else if (*itA < *itB)
00229         {
00230             ++itA;
00231         }
00232         else
00233         {
00234             ++itB;
00235         }
00236     }
00237     return true;
00238 }
00239 
00240 // AkUnion
00241 //  - Set union ( A = A U B ).  
00242 //  NOTE: Preforms a memory allocation and may fail.
00243 //
00244 template< typename T, class U_POOL, AkUInt32 uGrowBy >
00245 static bool AkUnion(AkSet<T, U_POOL, uGrowBy>& io_A, const AkSet<T, U_POOL, uGrowBy>& in_B)
00246 {
00247     AkInt32 uSizeNeeded = io_A.Length() + in_B.Length() - AkCountIntersection(io_A, in_B);
00248     AkSet<T, U_POOL, uGrowBy> result;
00249 
00250     if (result.Resize(uSizeNeeded))
00251     {
00252         typename AkSet<T, U_POOL, uGrowBy>::Iterator itRes = result.Begin();
00253         typename AkSet<T, U_POOL, uGrowBy>::Iterator itA = io_A.Begin();
00254         typename AkSet<T, U_POOL, uGrowBy>::Iterator itB = in_B.Begin();
00255 
00256         while (itB != in_B.End() || itA != io_A.End())
00257         {
00258             if ( itB != in_B.End() && (itA == io_A.End() || *itB < *itA))
00259             {
00260                 *itRes = *itB;
00261                 ++itB;
00262             }
00263             else if (itB == in_B.End() || *itA < *itB)
00264             {
00265                 *itRes = *itA;
00266                 ++itA;
00267             }
00268             else //if ( *itA == *itC)
00269             {
00270                 *itRes = *itA;
00271                 ++itA;
00272                 ++itB;
00273             }
00274 
00275             ++itRes;
00276         }
00277 
00278         io_A.Transfer(result);
00279         return true;
00280     }
00281 
00282     return false;
00283 }
00284 
00285 typedef AkSet< AkUniqueID, ArrayPoolDefault >  AkUniqueIDSet;
00286 
00287 // AkIntersect
00288 //  - Return true if the intersection of in_A (a set of type in_typeA), and in_B (a set of type in_typeB) is not the empty set.
00289 //
00290 template< typename T, class U_POOL, AkUInt32 uGrowBy >
00291 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)
00292 {
00293     if (in_typeA == SetType_Inclusion)
00294     {
00295         if (in_typeB == SetType_Inclusion)
00296             return !AkDisjoint(in_A, in_B);
00297         else//(in_typeB == SetType_Exclusion)
00298             return !AkIsSubset(in_A, in_B);
00299     }
00300     else//(in_typeA == SetType_Exclusion)
00301     {
00302         if (in_typeB == SetType_Inclusion)
00303             return !AkIsSubset(in_B, in_A);
00304         else//(in_typeB == SetType_Exclusion)
00305             return true;//Assuming an infinite space of possible elements.
00306     }
00307 }
00308 
00309 // AkContains
00310 //  - Return true if the element in_item is contained in in_Set, a set of type in_type.
00311 //
00312 template< typename T, class U_POOL, AkUInt32 uGrowBy >
00313 static inline bool AkContains(const AkSet<T, U_POOL, uGrowBy>& in_Set, AkSetType in_type, T in_item)
00314 {
00315     return  (in_type == SetType_Inclusion && in_Set.Contains(in_item)) ||
00316         (in_type == SetType_Exclusion && !in_Set.Contains(in_item));
00317 }
00318 
00319 // AkSubtraction
00320 //  - pseudo in-place set subtraction (A = A - B) with set type specifiers.
00321 //  NOTE: Memory may be allocated (in AkUnion) so prepare for failure.
00322 //
00323 template< typename T, class U_POOL, AkUInt32 uGrowBy >
00324 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)
00325 {
00326     if (in_typeA == SetType_Inclusion)
00327     {
00328         if (in_typeB == SetType_Inclusion)
00329             return AkSubtraction(in_A, in_B);
00330         else//(in_typeB == SetType_Exclusion)
00331             return AkIntersection(in_A, in_B);
00332     }
00333     else//(in_typeA == SetType_Exclusion)
00334     {
00335         if (in_typeB == SetType_Inclusion)
00336             return AkUnion(in_A, in_B);
00337         else//(in_typeB == SetType_Exclusion)
00338             return AkIntersection(in_A, in_B);
00339     }
00340 }
00341 
00342 // AkUnion
00343 //  - Pseudo in-place set union (A = A + B)
00344 //  NOTE: Memory may be allocated (in AkUnion) so prepare for failure.
00345 //
00346 template< typename T, class U_POOL, AkUInt32 uGrowBy >
00347 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)
00348 {
00349     if (io_typeA == SetType_Inclusion)
00350     {
00351         if (in_typeB == SetType_Inclusion)
00352             return AkUnion(io_A, in_B);
00353         else//(in_typeB == SetType_Exclusion)
00354         {
00355             AkSet<T, U_POOL, uGrowBy> temp;
00356             temp.Transfer(io_A);
00357             if (io_A.Copy(in_B) == AK_Success)
00358             {
00359                 io_typeA = SetType_Exclusion;
00360                 AkSubtraction(io_A, temp);
00361                 temp.Term();
00362                 return true;
00363             }
00364             else
00365             {
00366                 io_A.Transfer(temp);
00367                 return false;
00368             }
00369         }
00370     }
00371     else//(in_typeA == SetType_Exclusion)
00372     {
00373         if (in_typeB == SetType_Inclusion)
00374             return AkSubtraction(io_A, in_B);
00375         else//(in_typeB == SetType_Exclusion)
00376             return AkIntersection(io_A, in_B);
00377     }
00378 }
00379 
00380 #endif
00381