src/NCollection/NCollection_QuickSort.hxx

   1 // Created on: 2011-01-27
   2 // Created by: KGV
   3 // Copyright (c) 2011-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 #ifndef _NCollection_QuickSort_HeaderFile
  17 #define _NCollection_QuickSort_HeaderFile
  18
  19 #include <NCollection_Comparator.hxx>
  20 #include <Standard_Integer.hxx>
  21
  22 /**
  23  * Perform sorting of enumerable collection with QuickSort algorithm.
  24  * Enumerable collection should provide the random access to its values
  25  * by index number with methods Value(theId) and ChangeValue(theId).
  26  * Currently it supposed to be used with NCollection_Sequence and NCollection_Vector.
  27  *
  28  * Usage sample:
  29  *   // input sequence
  30  *   NCollection_Sequence<Standard_Real> aSequence;
  31  *   // perform sorting for the whole sequence.
  32  *   NCollection_QuickSort<NCollection_Sequence<Standard_Real>, Standard_Real>
  33  *     ::Perform (aSequence, NCollection_Comparator<Standard_Real>(),
  34  *                1, aSequence.Size());
  35  */
  36 template<class TheCollType, class TheItemType>
  37 class NCollection_QuickSort
  38 {
  39 public:
  40
  41   //! Main entry call to perform sorting
  42   static void Perform (TheCollType& theEnumColl,
  43                        const NCollection_Comparator<TheItemType>& theComparator,
  44                        const Standard_Integer theLower,
  45                        const Standard_Integer theUpper)
  46   {
  47     if (theLower < theUpper)
  48     {
  49       Standard_Integer aPivotPosition = Partition (theEnumColl, theComparator,
  50                                                    theLower, theUpper);
  51       if (theLower < aPivotPosition)
  52       {
  53         // recursive call
  54         Perform (theEnumColl, theComparator,
  55                  theLower, aPivotPosition - 1);
  56       }
  57       // recursive call
  58       Perform (theEnumColl, theComparator,
  59                aPivotPosition + 1, theUpper);
  60     }
  61   }
  62
  63 private:
  64
  65   //! Auxiliary function
  66   static void SwapValues (TheItemType& x, TheItemType& y)
  67   {
  68     TheItemType aCopy = x;
  69     x = y;
  70     y = aCopy;
  71   }
  72
  73   static Standard_Integer Partition (TheCollType& theEnumColl,
  74                                      const NCollection_Comparator<TheItemType>& theComparator,
  75                                      const Standard_Integer theLower,
  76                                      const Standard_Integer theUpper)
  77   {
  78     Standard_Integer anIdLeft (theLower), anIdRight (theUpper);
  79     const TheItemType aPivot = theEnumColl.Value (theLower);
  80
  81     while (anIdLeft < anIdRight)
  82     {
  83       while (theComparator.IsGreater (theEnumColl.Value (anIdRight), aPivot))
  84       {
  85         --anIdRight;
  86       }
  87       while ((anIdLeft < anIdRight) &&
  88              theComparator.IsLowerEqual (theEnumColl.Value (anIdLeft), aPivot))
  89       {
  90         ++anIdLeft;
  91       }
  92
  93       if (anIdLeft < anIdRight)
  94       {
  95         SwapValues (theEnumColl.ChangeValue (anIdLeft),
  96                     theEnumColl.ChangeValue (anIdRight));
  97       }
  98     }
  99
 100     theEnumColl.ChangeValue (theLower) = theEnumColl.Value (anIdRight);
 101     theEnumColl.ChangeValue (anIdRight) = aPivot;
 102     return anIdRight;
 103   }
 104
 105 };
 106
 107 #endif /*_NCollection_QuickSort_HeaderFile*/