b311480e |
1 | // Copyright (c) 1998-1999 Matra Datavision |
973c2be1 |
2 | // Copyright (c) 1999-2014 OPEN CASCADE SAS |
b311480e |
3 | // |
973c2be1 |
4 | // This file is part of Open CASCADE Technology software library. |
b311480e |
5 | // |
d5f74e42 |
6 | // This library is free software; you can redistribute it and/or modify it under |
7 | // the terms of the GNU Lesser General Public License version 2.1 as published |
973c2be1 |
8 | // by the Free Software Foundation, with special exception defined in the file |
9 | // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT |
10 | // distribution for complete text of the license and disclaimer of any warranty. |
b311480e |
11 | // |
973c2be1 |
12 | // Alternatively, this file may be used under the terms of Open CASCADE |
13 | // commercial license or contractual agreement. |
b311480e |
14 | |
7fd59977 |
15 | // SortTools_HeapSort.gxx |
16 | // cree le 04/11/91 par ASI |
17 | // Reference : Software Conponents with ADA, Grady Booch. |
18 | |
19 | void Shift(Array& TheArray, |
20 | const Comparator& Comp, |
21 | const Standard_Integer Left, const Standard_Integer Right) |
22 | { |
23 | Item Temp = TheArray(Left); |
24 | Standard_Integer Front = Left; |
25 | Standard_Integer Back = Front * 2; |
26 | while (Back <= Right) { |
27 | if (Back < Right) { |
28 | if(Comp.IsLower(TheArray(Back), TheArray(Back + 1))) { |
29 | Back = Back + 1; |
30 | } |
31 | } |
32 | if(!Comp.IsLower(Temp, TheArray(Back))) break; |
33 | TheArray(Front) = TheArray(Back); |
34 | Front = Back; |
35 | if(Front * 2 > TheArray.Upper()) break; |
36 | Back = Front * 2; |
37 | } |
38 | TheArray(Front) = Temp; |
39 | } |
40 | |
41 | void SortTools_HeapSort::Sort(Array& TheArray, |
42 | const Comparator& Comp) |
43 | { |
44 | Item TempItem; |
45 | Standard_Integer Left; |
46 | Standard_Integer Right; |
47 | |
48 | Left = ((TheArray.Upper() - TheArray.Lower() + 1) / 2) + 1; |
49 | Right = TheArray.Upper(); |
50 | while (Left > TheArray.Lower()) { |
51 | Left = Left - 1; |
52 | Shift(TheArray, Comp, Left, Right); |
53 | } |
54 | while (Right > TheArray.Lower()) { |
55 | TempItem = TheArray(TheArray.Lower()); |
56 | TheArray(TheArray.Lower()) = TheArray(Right); |
57 | TheArray(Right) = TempItem; |
58 | Right = Right - 1; |
59 | Shift(TheArray, Comp, Left, Right); |
60 | } |
61 | } |
62 | |
63 | |
64 | |
65 | |
66 | |