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 // AkUnion
00210 //  - Set union ( A = A U B ).  
00211 //  NOTE: Preforms a memory allocation and may fail.
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 //if ( *itA == *itC)
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 // AkIntersect
00257 //  - 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.
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//(in_typeB == SetType_Exclusion)
00267             return !AkIsSubset(in_A, in_B);
00268     }
00269     else//(in_typeA == SetType_Exclusion)
00270     {
00271         if (in_typeB == SetType_Inclusion)
00272             return !AkIsSubset(in_B, in_A);
00273         else//(in_typeB == SetType_Exclusion)
00274             return true;//Assuming an infinite space of possible elements.
00275     }
00276 }
00277 
00278 // AkContains
00279 //  - Return true if the element in_item is contained in in_Set, a set of type in_type.
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 // AkSubtraction
00289 //  - pseudo in-place set subtraction (A = A - B) with set type specifiers.
00290 //  NOTE: Memory may be allocated (in AkUnion) so prepare for failure.
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//(in_typeB == SetType_Exclusion)
00300             return AkIntersection(in_A, in_B);
00301     }
00302     else//(in_typeA == SetType_Exclusion)
00303     {
00304         if (in_typeB == SetType_Inclusion)
00305             return AkUnion(in_A, in_B);
00306         else//(in_typeB == SetType_Exclusion)
00307             return AkIntersection(in_A, in_B);
00308     }
00309 }
00310 
00311 // AkUnion
00312 //  - Pseudo in-place set union (A = A + B)
00313 //  NOTE: Memory may be allocated (in AkUnion) so prepare for failure.
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//(in_typeB == SetType_Exclusion)
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//(in_typeA == SetType_Exclusion)
00341     {
00342         if (in_typeB == SetType_Inclusion)
00343             return AkSubtraction(io_A, in_B);
00344         else//(in_typeB == SetType_Exclusion)
00345             return AkIntersection(io_A, in_B);
00346     }
00347 }
00348 
00349 #endif
00350