From e0a679997086973673798814865616b0f2faf075 Mon Sep 17 00:00:00 2001 From: bugmaster <> Date: Thu, 19 May 2011 10:43:28 +0000 Subject: [PATCH] OCC22278 No any sorting algorithm implemented for NCollection templates Developen by : KGV --- src/NCollection/FILES | 3 + src/NCollection/NCollection_Comparator.hxx | 69 +++++++++++++++ src/NCollection/NCollection_QuickSort.hxx | 97 ++++++++++++++++++++++ 3 files changed, 169 insertions(+) create mode 100755 src/NCollection/NCollection_Comparator.hxx create mode 100755 src/NCollection/NCollection_QuickSort.hxx diff --git a/src/NCollection/FILES b/src/NCollection/FILES index 47b1820737..799d7ec57a 100755 --- a/src/NCollection/FILES +++ b/src/NCollection/FILES @@ -74,3 +74,6 @@ NCollection_SparseArrayBase.cxx NCollection_CellFilter.hxx NCollection_Handle.hxx NCollection_Handle.cxx + +NCollection_Comparator.hxx +NCollection_QuickSort.hxx diff --git a/src/NCollection/NCollection_Comparator.hxx b/src/NCollection/NCollection_Comparator.hxx new file mode 100755 index 0000000000..17040f7473 --- /dev/null +++ b/src/NCollection/NCollection_Comparator.hxx @@ -0,0 +1,69 @@ +// File NCollection_Comparator.hxx +// Created 27 January 2011 +// Author KGV +// Copyright OpenCASCADE 2011 + +#ifndef _NCollection_Comparator_HeaderFile +#define _NCollection_Comparator_HeaderFile + +#include + +/** + * Class to define basic compare operations. + * Basic implementation use redirection to standard C++ operators. + * You can use standard C++ templates mechanisms to redefine these methods + * or to inherit basic implementation to create multiple comparators + * for same type with different rules. + */ +template +class NCollection_Comparator +{ +public: + + NCollection_Comparator (const Standard_Real theTolerance = Precision::Confusion()) + : myTolerance (theTolerance) {} + + virtual ~NCollection_Comparator() {} + +public: + //! Comparison functions which should be overridden + //! if standard operators are not defined for user type. + + //! Should return true if Left value is greater than Right + virtual Standard_Boolean IsGreater (const TheItemType& theLeft, const TheItemType& theRight) const + { + return theLeft > theRight; + } + + //! Should return true if values are equal + virtual Standard_Boolean IsEqual (const TheItemType& theLeft, const TheItemType& theRight) const + { + return theLeft == theRight; + } + +public: + //! Comparison functions which may be overridden for performance reasons + + //! Should return true if Left value is lower than Right + virtual Standard_Boolean IsLower (const TheItemType& theLeft, const TheItemType& theRight) const + { + return !IsGreater (theLeft, theRight) && !IsEqual (theLeft, theRight); + } + + virtual Standard_Boolean IsLowerEqual (const TheItemType& theLeft, const TheItemType& theRight) const + { + return !IsGreater (theLeft, theRight); + } + + virtual Standard_Boolean IsGreaterEqual (const TheItemType& theLeft, const TheItemType& theRight) const + { + return IsGreater (theLeft, theRight) || IsEqual (theLeft, theRight); + } + +protected: + + Standard_Real myTolerance; + +}; + +#endif /*_NCollection_Comparator_HeaderFile*/ diff --git a/src/NCollection/NCollection_QuickSort.hxx b/src/NCollection/NCollection_QuickSort.hxx new file mode 100755 index 0000000000..c6b5f6d47f --- /dev/null +++ b/src/NCollection/NCollection_QuickSort.hxx @@ -0,0 +1,97 @@ +// File NCollection_QuickSort.hxx +// Created 27 January 2011 +// Author KGV +// Copyright OpenCASCADE 2011 + +#ifndef _NCollection_QuickSort_HeaderFile +#define _NCollection_QuickSort_HeaderFile + +#include +#include + +/** + * Perform sorting of enumerable collection with QuickSort algorithm. + * Enumerable collection should provide the random access to its values + * by index number with methods Value(theId) and ChangeValue(theId). + * Currently it supposed to be used with NCollection_Sequence and NCollection_Vector. + * + * Usage sample: + * // input sequence + * NCollection_Sequence aSequence; + * // perform sorting for the whole sequence. + * NCollection_QuickSort, Standard_Real> + * ::Perform (aSequence, NCollection_Comparator(), + * 1, aSequence.Size()); + */ +template +class NCollection_QuickSort +{ +public: + + //! Main entry call to perform sorting + static void Perform (TheCollType& theEnumColl, + const NCollection_Comparator& theComparator, + const Standard_Integer theLower, + const Standard_Integer theUpper) + { + if (theLower < theUpper) + { + Standard_Integer aPivotPosition = Partition (theEnumColl, theComparator, + theLower, theUpper); + if (theLower < aPivotPosition) + { + // recursive call + Perform (theEnumColl, theComparator, + theLower, aPivotPosition - 1); + } + // recursive call + Perform (theEnumColl, theComparator, + aPivotPosition + 1, theUpper); + } + } + +private: + + //! Auxiliary function + static void SwapValues (TheItemType& x, TheItemType& y) + { + TheItemType aCopy = x; + x = y; + y = aCopy; + } + + static Standard_Integer Partition (TheCollType& theEnumColl, + const NCollection_Comparator& theComparator, + const Standard_Integer theLower, + const Standard_Integer theUpper) + { + Standard_Integer anIdLeft (theLower), anIdRight (theUpper); + const TheItemType aPivot = theEnumColl.Value (theLower); + + while (anIdLeft < anIdRight) + { + while (theComparator.IsGreater (theEnumColl.Value (anIdRight), aPivot)) + { + --anIdRight; + } + while ((anIdLeft < anIdRight) && + theComparator.IsLowerEqual (theEnumColl.Value (anIdLeft), aPivot)) + { + ++anIdLeft; + } + + if (anIdLeft < anIdRight) + { + SwapValues (theEnumColl.ChangeValue (anIdLeft), + theEnumColl.ChangeValue (anIdRight)); + } + } + + theEnumColl.ChangeValue (theLower) = theEnumColl.Value (anIdRight); + theEnumColl.ChangeValue (anIdRight) = aPivot; + return anIdRight; + } + +}; + +#endif /*_NCollection_QuickSort_HeaderFile*/ -- 2.20.1