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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
|
------------------------------------------------------------------------------
-- --
-- GNAT LIBRARY COMPONENTS --
-- --
-- A D A . C O N T A I N E R S . S T A B L E _ S O R T I N G --
-- --
-- B o d y --
-- --
-- Copyright (C) 1995-2024, AdaCore --
-- --
-- GNAT is free software; you can redistribute it and/or modify it under --
-- terms of the GNU General Public License as published by the Free Soft- --
-- ware Foundation; either version 3, or (at your option) any later ver- --
-- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
-- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE. --
-- --
-- As a special exception under Section 7 of GPL version 3, you are granted --
-- additional permissions described in the GCC Runtime Library Exception, --
-- version 3.1, as published by the Free Software Foundation. --
-- --
-- You should have received a copy of the GNU General Public License and --
-- a copy of the GCC Runtime Library Exception along with this program; --
-- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
-- <http://www.gnu.org/licenses/>. --
-- --
-- GNAT was originally developed by the GNAT team at New York University. --
-- Extensive contributions were provided by Ada Core Technologies Inc. --
-- --
------------------------------------------------------------------------------
package body Ada.Containers.Stable_Sorting is
package body List_Descriptors is
procedure Doubly_Linked_List_Sort (List : List_Descriptor) is
Empty : constant List_Descriptor := (Nil, Nil, 0);
function Merge_Sort (Arg : List_Descriptor) return List_Descriptor;
-- Sort list of given length using MergeSort; length must be >= 2.
-- As required by RM, the sort is stable.
----------------
-- Merge_Sort --
----------------
function Merge_Sort (Arg : List_Descriptor) return List_Descriptor
is
procedure Split_List
(Unsplit : List_Descriptor; Part1, Part2 : out List_Descriptor);
-- Split list into two parts for divide-and-conquer.
-- Unsplit.Length must be >= 2.
function Merge_Parts
(Part1, Part2 : List_Descriptor) return List_Descriptor;
-- Merge two sorted lists, preserving sorted property.
----------------
-- Split_List --
----------------
procedure Split_List
(Unsplit : List_Descriptor; Part1, Part2 : out List_Descriptor)
is
Rover : Node_Ref := Unsplit.First;
Bump_Count : constant Count_Type := (Unsplit.Length - 1) / 2;
begin
for Iter in 1 .. Bump_Count loop
Rover := Next (Rover);
end loop;
Part1 := (First => Unsplit.First,
Last => Rover,
Length => Bump_Count + 1);
Part2 := (First => Next (Rover),
Last => Unsplit.Last,
Length => Unsplit.Length - Part1.Length);
-- Detach
Set_Next (Part1.Last, Nil);
Set_Prev (Part2.First, Nil);
end Split_List;
-----------------
-- Merge_Parts --
-----------------
function Merge_Parts
(Part1, Part2 : List_Descriptor) return List_Descriptor
is
procedure Detach_First (Source : in out List_Descriptor;
Detached : out Node_Ref);
-- Detach the first element from a non-empty list and
-- return the detached node via the Detached parameter.
------------------
-- Detach_First --
------------------
procedure Detach_First (Source : in out List_Descriptor;
Detached : out Node_Ref) is
begin
Detached := Source.First;
if Source.Length = 1 then
Source := Empty;
else
Source := (Next (Source.First),
Source.Last,
Source.Length - 1);
Set_Prev (Next (Detached), Nil);
Set_Next (Detached, Nil);
end if;
end Detach_First;
P1 : List_Descriptor := Part1;
P2 : List_Descriptor := Part2;
Merged : List_Descriptor := Empty;
Take_From_P2 : Boolean;
Detached : Node_Ref;
-- Start of processing for Merge_Parts
begin
while P1.Length /= 0 or P2.Length /= 0 loop
if P1.Length = 0 then
Take_From_P2 := True;
elsif P2.Length = 0 then
Take_From_P2 := False;
else
-- If the compared elements are equal then Take_From_P2
-- must be False in order to ensure stability.
Take_From_P2 := P2.First < P1.First;
end if;
if Take_From_P2 then
Detach_First (P2, Detached);
else
Detach_First (P1, Detached);
end if;
if Merged.Length = 0 then
Merged := (First | Last => Detached, Length => 1);
else
Set_Prev (Detached, Merged.Last);
Set_Next (Merged.Last, Detached);
Merged.Last := Detached;
Merged.Length := Merged.Length + 1;
end if;
end loop;
return Merged;
end Merge_Parts;
-- Start of processing for Merge_Sort
begin
if Positive (Arg.Length) < 2 then
-- already sorted
return Arg;
end if;
declare
Part1, Part2 : List_Descriptor;
begin
Split_List (Unsplit => Arg, Part1 => Part1, Part2 => Part2);
Part1 := Merge_Sort (Part1);
Part2 := Merge_Sort (Part2);
return Merge_Parts (Part1, Part2);
end;
end Merge_Sort;
-- Start of processing for Sort
begin
if List.Length > 1 then
-- If a call to the formal "<" op references the container
-- during sorting, seeing an empty container seems preferable
-- to seeing an internally inconsistent container.
--
Update_Container (Empty);
Update_Container (Merge_Sort (List));
end if;
end Doubly_Linked_List_Sort;
end List_Descriptors;
end Ada.Containers.Stable_Sorting;
|
