include/opencascade/NCollection_PackedMapAlgo.hxx

0001 // Copyright (c) 2005-2026 OPEN CASCADE SAS
0002 //
0003 // This file is part of Open CASCADE Technology software library.
0004 //
0005 // This library is free software; you can redistribute it and/or modify it under
0006 // the terms of the GNU Lesser General Public License version 2.1 as published
0007 // by the Free Software Foundation, with special exception defined in the file
0008 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
0009 // distribution for complete text of the license and disclaimer of any warranty.
0010 //
0011 // Alternatively, this file may be used under the terms of Open CASCADE
0012 // commercial license or contractual agreement.
0013
0014 #ifndef NCollection_PackedMapAlgo_HeaderFile
0015 #define NCollection_PackedMapAlgo_HeaderFile
0016
0017 #include <NCollection_PackedMap.hxx>
0018
0019 //! @brief Algorithms and utilities for NCollection_PackedMap operations.
0020 //!
0021 //! This namespace provides template functions for boolean operations
0022 //! on packed maps: union, intersection, subtraction, and symmetric difference.
0023 //! These algorithms are optimized for the packed bit representation.
0024 namespace NCollection_PackedMapAlgo
0025 {
0026 //! Apply to theMap the boolean operation union (aka addition, fuse, merge, boolean OR)
0027 //! with another (given) Map. The result contains the values that were previously
0028 //! contained in theMap or contained in the given (operand) map.
0029 //! @return True if content of theMap is changed
0030 template <class IntType>
0031 bool Unite(NCollection_PackedMap<IntType>&       theMap,
0032            const NCollection_PackedMap<IntType>& theOtherMap)
0033 {
0034   if (theOtherMap.IsEmpty() || &theMap == &theOtherMap)
0035     return false;
0036   else if (theMap.IsEmpty())
0037   {
0038     theMap.Assign(theOtherMap);
0039     return true;
0040   }
0041
0042   const int anOldExtent = theMap.Extent();
0043   for (typename NCollection_PackedMap<IntType>::Iterator anIter(theOtherMap); anIter.More();
0044        anIter.Next())
0045   {
0046     theMap.Add(anIter.Key());
0047   }
0048   return anOldExtent != theMap.Extent();
0049 }
0050
0051 //! Sets theMap to be the result of union (aka addition, fuse, merge, boolean OR)
0052 //! operation between two given Maps. The new Map contains the values that are
0053 //! contained either in the first map or in the second map or in both.
0054 //! All previous content of theMap is cleared. theMap (result of the boolean
0055 //! operation) can also be passed as one of operands.
0056 template <class IntType>
0057 void Union(NCollection_PackedMap<IntType>&       theMap,
0058            const NCollection_PackedMap<IntType>& theLeftMap,
0059            const NCollection_PackedMap<IntType>& theRightMap)
0060 {
0061   if (theLeftMap.IsEmpty())
0062     theMap.Assign(theRightMap);
0063   else if (theRightMap.IsEmpty())
0064     theMap.Assign(theLeftMap);
0065   else if (&theMap == &theLeftMap)
0066     Unite(theMap, theRightMap);
0067   else if (&theMap == &theRightMap)
0068     Unite(theMap, theLeftMap);
0069   else
0070   {
0071     theMap.Clear();
0072     for (typename NCollection_PackedMap<IntType>::Iterator anIter(theLeftMap); anIter.More();
0073          anIter.Next())
0074     {
0075       theMap.Add(anIter.Key());
0076     }
0077     for (typename NCollection_PackedMap<IntType>::Iterator anIter(theRightMap); anIter.More();
0078          anIter.Next())
0079     {
0080       theMap.Add(anIter.Key());
0081     }
0082   }
0083 }
0084
0085 //! Apply to theMap the intersection operation (aka multiplication, common, boolean AND)
0086 //! with another (given) Map. The result contains only the values that are contained in
0087 //! both theMap and the given map.
0088 //! @return True if content of theMap is changed
0089 template <class IntType>
0090 bool Intersect(NCollection_PackedMap<IntType>&       theMap,
0091                const NCollection_PackedMap<IntType>& theOtherMap)
0092 {
0093   if (theMap.IsEmpty())
0094     return false;
0095   else if (theOtherMap.IsEmpty())
0096   {
0097     theMap.Clear();
0098     return true;
0099   }
0100   else if (&theMap == &theOtherMap)
0101     return false;
0102
0103   const int                      anOldExtent = theMap.Extent();
0104   NCollection_PackedMap<IntType> aCopy;
0105   for (typename NCollection_PackedMap<IntType>::Iterator anIter(theMap); anIter.More();
0106        anIter.Next())
0107   {
0108     if (theOtherMap.Contains(anIter.Key()))
0109     {
0110       aCopy.Add(anIter.Key());
0111     }
0112   }
0113   theMap = std::move(aCopy);
0114   return anOldExtent != theMap.Extent();
0115 }
0116
0117 //! Sets theMap to be the result of intersection (aka multiplication, common, boolean AND)
0118 //! operation between two given Maps. The new Map contains only the values that are
0119 //! contained in both map operands. All previous content of theMap is cleared.
0120 //! theMap (result of the boolean operation) can also be used as one of operands.
0121 template <class IntType>
0122 void Intersection(NCollection_PackedMap<IntType>&       theMap,
0123                   const NCollection_PackedMap<IntType>& theLeftMap,
0124                   const NCollection_PackedMap<IntType>& theRightMap)
0125 {
0126   if (theLeftMap.IsEmpty() || theRightMap.IsEmpty())
0127     theMap.Clear();
0128   else if (&theMap == &theLeftMap)
0129     Intersect(theMap, theRightMap);
0130   else if (&theMap == &theRightMap)
0131     Intersect(theMap, theLeftMap);
0132   else
0133   {
0134     theMap.Clear();
0135     const NCollection_PackedMap<IntType>* aSmaller = &theLeftMap;
0136     const NCollection_PackedMap<IntType>* aLarger  = &theRightMap;
0137     if (theLeftMap.Extent() > theRightMap.Extent())
0138     {
0139       aSmaller = &theRightMap;
0140       aLarger  = &theLeftMap;
0141     }
0142     for (typename NCollection_PackedMap<IntType>::Iterator anIter(*aSmaller); anIter.More();
0143          anIter.Next())
0144     {
0145       if (aLarger->Contains(anIter.Key()))
0146       {
0147         theMap.Add(anIter.Key());
0148       }
0149     }
0150   }
0151 }
0152
0153 //! Apply to theMap the subtraction (aka set-theoretic difference, relative complement,
0154 //! exclude, cut, boolean NOT) operation with another (given) Map. The result contains
0155 //! only the values that were previously contained in theMap and not contained in theOtherMap.
0156 //! @return True if content of theMap is changed
0157 template <class IntType>
0158 bool Subtract(NCollection_PackedMap<IntType>&       theMap,
0159               const NCollection_PackedMap<IntType>& theOtherMap)
0160 {
0161   if (&theMap == &theOtherMap)
0162   {
0163     if (theMap.IsEmpty())
0164     {
0165       return false;
0166     }
0167     theMap.Clear();
0168     return true;
0169   }
0170
0171   if (theMap.IsEmpty() || theOtherMap.IsEmpty())
0172     return false;
0173
0174   const int anOldExtent = theMap.Extent();
0175   for (typename NCollection_PackedMap<IntType>::Iterator anIter(theOtherMap); anIter.More();
0176        anIter.Next())
0177   {
0178     theMap.Remove(anIter.Key());
0179   }
0180   return anOldExtent != theMap.Extent();
0181 }
0182
0183 //! Sets theMap to be the result of subtraction (aka set-theoretic difference, relative
0184 //! complement, exclude, cut, boolean NOT) operation between two given Maps. The new Map
0185 //! contains only the values that are contained in the first map operand and not contained
0186 //! in the second one. All previous content of theMap is cleared.
0187 template <class IntType>
0188 void Subtraction(NCollection_PackedMap<IntType>&       theMap,
0189                  const NCollection_PackedMap<IntType>& theLeftMap,
0190                  const NCollection_PackedMap<IntType>& theRightMap)
0191 {
0192   if (&theMap == &theLeftMap)
0193   {
0194     Subtract(theMap, theRightMap);
0195     return;
0196   }
0197   else if (&theMap == &theRightMap)
0198   {
0199     NCollection_PackedMap<IntType> aCopy;
0200     Subtraction(aCopy, theLeftMap, theRightMap);
0201     theMap = std::move(aCopy);
0202     return;
0203   }
0204
0205   theMap.Assign(theLeftMap);
0206   Subtract(theMap, theRightMap);
0207 }
0208
0209 //! Apply to theMap the symmetric difference (aka exclusive disjunction, boolean XOR)
0210 //! operation with another (given) Map. The result contains the values that are contained
0211 //! only in theMap or the operand map, but not in both.
0212 //! @return True if content of theMap is changed
0213 template <class IntType>
0214 bool Differ(NCollection_PackedMap<IntType>&       theMap,
0215             const NCollection_PackedMap<IntType>& theOtherMap)
0216 {
0217   if (&theMap == &theOtherMap)
0218   {
0219     if (theMap.IsEmpty())
0220     {
0221       return false;
0222     }
0223     theMap.Clear();
0224     return true;
0225   }
0226
0227   if (theOtherMap.IsEmpty())
0228     return false;
0229   else if (theMap.IsEmpty())
0230   {
0231     theMap.Assign(theOtherMap);
0232     return true;
0233   }
0234
0235   const int anOldExtent = theMap.Extent();
0236   for (typename NCollection_PackedMap<IntType>::Iterator anIter(theOtherMap); anIter.More();
0237        anIter.Next())
0238   {
0239     const IntType aKey = anIter.Key();
0240     if (theMap.Contains(aKey))
0241       theMap.Remove(aKey);
0242     else
0243       theMap.Add(aKey);
0244   }
0245   return anOldExtent != theMap.Extent();
0246 }
0247
0248 //! Sets theMap to be the result of symmetric difference (aka exclusive disjunction,
0249 //! boolean XOR) operation between two given Maps. The new Map contains the values that
0250 //! are contained only in the first or the second operand maps but not in both.
0251 //! All previous content of theMap is cleared. theMap (result of the boolean operation)
0252 //! can also be used as one of operands.
0253 template <class IntType>
0254 void Difference(NCollection_PackedMap<IntType>&       theMap,
0255                 const NCollection_PackedMap<IntType>& theLeftMap,
0256                 const NCollection_PackedMap<IntType>& theRightMap)
0257 {
0258   if (&theLeftMap == &theRightMap)
0259   {
0260     theMap.Clear();
0261     return;
0262   }
0263   else if (&theMap == &theLeftMap)
0264   {
0265     Differ(theMap, theRightMap);
0266     return;
0267   }
0268   else if (&theMap == &theRightMap)
0269   {
0270     Differ(theMap, theLeftMap);
0271     return;
0272   }
0273
0274   theMap.Clear();
0275   for (typename NCollection_PackedMap<IntType>::Iterator anIter(theLeftMap); anIter.More();
0276        anIter.Next())
0277   {
0278     if (!theRightMap.Contains(anIter.Key()))
0279     {
0280       theMap.Add(anIter.Key());
0281     }
0282   }
0283   for (typename NCollection_PackedMap<IntType>::Iterator anIter(theRightMap); anIter.More();
0284        anIter.Next())
0285   {
0286     if (!theLeftMap.Contains(anIter.Key()))
0287     {
0288       theMap.Add(anIter.Key());
0289     }
0290   }
0291 }
0292
0293 //! Returns True if theMap and theOtherMap have common elements.
0294 template <class IntType>
0295 bool HasIntersection(const NCollection_PackedMap<IntType>& theMap,
0296                      const NCollection_PackedMap<IntType>& theOtherMap)
0297 {
0298   if (theMap.IsEmpty() || theOtherMap.IsEmpty())
0299     return false;
0300
0301   if (&theMap == &theOtherMap)
0302     return true;
0303
0304   const NCollection_PackedMap<IntType>* aSmaller = &theMap;
0305   const NCollection_PackedMap<IntType>* aLarger  = &theOtherMap;
0306   if (theMap.Extent() > theOtherMap.Extent())
0307   {
0308     aSmaller = &theOtherMap;
0309     aLarger  = &theMap;
0310   }
0311
0312   for (typename NCollection_PackedMap<IntType>::Iterator anIter(*aSmaller); anIter.More();
0313        anIter.Next())
0314   {
0315     if (aLarger->Contains(anIter.Key()))
0316     {
0317       return true;
0318     }
0319   }
0320
0321   return false;
0322 }
0323
0324 //! Checks if theMap contains all keys of theOtherMap.
0325 //! Returns True if theMap is a superset of theOtherMap (theOtherMap is a subset of theMap).
0326 template <class IntType>
0327 bool Contains(const NCollection_PackedMap<IntType>& theMap,
0328               const NCollection_PackedMap<IntType>& theOtherMap)
0329 {
0330   if (&theMap == &theOtherMap || theOtherMap.IsEmpty())
0331   {
0332     return true;
0333   }
0334   else if (theMap.Extent() < theOtherMap.Extent())
0335   {
0336     return false;
0337   }
0338
0339   for (typename NCollection_PackedMap<IntType>::Iterator anIter(theOtherMap); anIter.More();
0340        anIter.Next())
0341   {
0342     if (!theMap.Contains(anIter.Key()))
0343     {
0344       return false;
0345     }
0346   }
0347
0348   return true;
0349 }
0350
0351 //! Returns True if theMap is a subset of theOtherMap, i.e. all elements
0352 //! contained in theMap are also contained in theOtherMap.
0353 //! If theMap is empty, this method returns true for any operand map.
0354 template <class IntType>
0355 bool IsSubset(const NCollection_PackedMap<IntType>& theMap,
0356               const NCollection_PackedMap<IntType>& theOtherMap)
0357 {
0358   return Contains(theOtherMap, theMap);
0359 }
0360
0361 //! Checks if two maps contain exactly the same keys.
0362 //! Returns True if theMap and theOtherMap are equal.
0363 template <class IntType>
0364 bool IsEqual(const NCollection_PackedMap<IntType>& theMap,
0365              const NCollection_PackedMap<IntType>& theOtherMap)
0366 {
0367   if (&theMap == &theOtherMap)
0368   {
0369     return true;
0370   }
0371   return theMap.Extent() == theOtherMap.Extent() && Contains(theMap, theOtherMap);
0372 }
0373
0374 } // namespace NCollection_PackedMapAlgo
0375
0376 #endif // NCollection_PackedMapAlgo_HeaderFile