0027895: Correction in the constructor Extrema_ExtElC::Extrema_ExtElC (const gp_Lin...
[occt.git] / src / NCollection / NCollection_QuickSort.hxx
CommitLineData
b311480e 1// Created on: 2011-01-27
2// Created by: KGV
973c2be1 3// Copyright (c) 2011-2014 OPEN CASCADE SAS
b311480e 4//
973c2be1 5// This file is part of Open CASCADE Technology software library.
b311480e 6//
d5f74e42 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
973c2be1 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.
b311480e 12//
973c2be1 13// Alternatively, this file may be used under the terms of Open CASCADE
14// commercial license or contractual agreement.
e0a67999 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 */
36template<class TheCollType, class TheItemType>
37class NCollection_QuickSort
38{
39public:
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
63private:
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*/