Mercurial > hg > CbC > CbC_gcc
comparison gcc/ada/libgnat/g-hesorg.adb @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
1 ------------------------------------------------------------------------------ | |
2 -- -- | |
3 -- GNAT RUN-TIME COMPONENTS -- | |
4 -- -- | |
5 -- G N A T . H E A P _ S O R T _ G -- | |
6 -- -- | |
7 -- B o d y -- | |
8 -- -- | |
9 -- Copyright (C) 1995-2017, AdaCore -- | |
10 -- -- | |
11 -- GNAT is free software; you can redistribute it and/or modify it under -- | |
12 -- terms of the GNU General Public License as published by the Free Soft- -- | |
13 -- ware Foundation; either version 3, or (at your option) any later ver- -- | |
14 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- | |
15 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- | |
16 -- or FITNESS FOR A PARTICULAR PURPOSE. -- | |
17 -- -- | |
18 -- As a special exception under Section 7 of GPL version 3, you are granted -- | |
19 -- additional permissions described in the GCC Runtime Library Exception, -- | |
20 -- version 3.1, as published by the Free Software Foundation. -- | |
21 -- -- | |
22 -- You should have received a copy of the GNU General Public License and -- | |
23 -- a copy of the GCC Runtime Library Exception along with this program; -- | |
24 -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -- | |
25 -- <http://www.gnu.org/licenses/>. -- | |
26 -- -- | |
27 -- GNAT was originally developed by the GNAT team at New York University. -- | |
28 -- Extensive contributions were provided by Ada Core Technologies Inc. -- | |
29 -- -- | |
30 ------------------------------------------------------------------------------ | |
31 | |
32 package body GNAT.Heap_Sort_G is | |
33 | |
34 ---------- | |
35 -- Sort -- | |
36 ---------- | |
37 | |
38 -- We are using the classical heapsort algorithm (i.e. Floyd's Treesort3) | |
39 -- as described by Knuth ("The Art of Programming", Volume III, first | |
40 -- edition, section 5.2.3, p. 145-147) with the modification that is | |
41 -- mentioned in exercise 18. For more details on this algorithm, see | |
42 -- Robert B. K. Dewar PhD thesis "The use of Computers in the X-ray | |
43 -- Phase Problem". University of Chicago, 1968, which was the first | |
44 -- publication of the modification, which reduces the number of compares | |
45 -- from 2NlogN to NlogN. | |
46 | |
47 procedure Sort (N : Natural) is | |
48 | |
49 Max : Natural := N; | |
50 -- Current Max index in tree being sifted | |
51 | |
52 procedure Sift (S : Positive); | |
53 -- This procedure sifts up node S, i.e. converts the subtree rooted | |
54 -- at node S into a heap, given the precondition that any sons of | |
55 -- S are already heaps. On entry, the contents of node S is found | |
56 -- in the temporary (index 0), the actual contents of node S on | |
57 -- entry are irrelevant. This is just a minor optimization to avoid | |
58 -- what would otherwise be two junk moves in phase two of the sort. | |
59 | |
60 ---------- | |
61 -- Sift -- | |
62 ---------- | |
63 | |
64 procedure Sift (S : Positive) is | |
65 C : Positive := S; | |
66 Son : Positive; | |
67 Father : Positive; | |
68 -- Note: by making the above all Positive, we ensure that a test | |
69 -- against zero for the temporary location can be resolved on the | |
70 -- basis of types when the routines are inlined. | |
71 | |
72 begin | |
73 -- This is where the optimization is done, normally we would do a | |
74 -- comparison at each stage between the current node and the larger | |
75 -- of the two sons, and continue the sift only if the current node | |
76 -- was less than this maximum. In this modified optimized version, | |
77 -- we assume that the current node will be less than the larger | |
78 -- son, and unconditionally sift up. Then when we get to the bottom | |
79 -- of the tree, we check parents to make sure that we did not make | |
80 -- a mistake. This roughly cuts the number of comparisons in half, | |
81 -- since it is almost always the case that our assumption is correct. | |
82 | |
83 -- Loop to pull up larger sons | |
84 | |
85 loop | |
86 Son := 2 * C; | |
87 | |
88 if Son < Max then | |
89 if Lt (Son, Son + 1) then | |
90 Son := Son + 1; | |
91 end if; | |
92 elsif Son > Max then | |
93 exit; | |
94 end if; | |
95 | |
96 Move (Son, C); | |
97 C := Son; | |
98 end loop; | |
99 | |
100 -- Loop to check fathers | |
101 | |
102 while C /= S loop | |
103 Father := C / 2; | |
104 | |
105 if Lt (Father, 0) then | |
106 Move (Father, C); | |
107 C := Father; | |
108 else | |
109 exit; | |
110 end if; | |
111 end loop; | |
112 | |
113 -- Last step is to pop the sifted node into place | |
114 | |
115 Move (0, C); | |
116 end Sift; | |
117 | |
118 -- Start of processing for Sort | |
119 | |
120 begin | |
121 -- Phase one of heapsort is to build the heap. This is done by | |
122 -- sifting nodes N/2 .. 1 in sequence. | |
123 | |
124 for J in reverse 1 .. N / 2 loop | |
125 Move (J, 0); | |
126 Sift (J); | |
127 end loop; | |
128 | |
129 -- In phase 2, the largest node is moved to end, reducing the size | |
130 -- of the tree by one, and the displaced node is sifted down from | |
131 -- the top, so that the largest node is again at the top. | |
132 | |
133 while Max > 1 loop | |
134 Move (Max, 0); | |
135 Move (1, Max); | |
136 Max := Max - 1; | |
137 Sift (1); | |
138 end loop; | |
139 | |
140 end Sort; | |
141 | |
142 end GNAT.Heap_Sort_G; |