1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
// File NCollection_QuickSort.hxx
// Created 27 January 2011
// Author KGV
// Copyright OpenCASCADE 2011
#ifndef _NCollection_QuickSort_HeaderFile
#define _NCollection_QuickSort_HeaderFile
#include <NCollection_Comparator.hxx>
#include <Standard_Integer.hxx>
/**
* 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<Standard_Real> aSequence;
* // perform sorting for the whole sequence.
* NCollection_QuickSort<NCollection_Sequence<Standard_Real>, Standard_Real>
* ::Perform (aSequence, NCollection_Comparator<Standard_Real>(),
* 1, aSequence.Size());
*/
template<class TheCollType, class TheItemType>
class NCollection_QuickSort
{
public:
//! Main entry call to perform sorting
static void Perform (TheCollType& theEnumColl,
const NCollection_Comparator<TheItemType>& 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<TheItemType>& 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*/
|
