b83a4c50ceff4989aa3c63b0540d4c10b3978c14
[occt.git] / 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*/