1% Copyright (C) 2012-2017,2018 John E. Davis
2%
3% This file is part of the S-Lang Library and may be distributed under the
4% terms of the GNU General Public License.  See the file COPYING for
5% more information.
6%---------------------------------------------------------------------------
7require ("arrayfuns");
8
9private define user_sort_cmp (cd, i, j)
10{
11   variable list = cd.list;
12   return (@cd.cmp) (list[i], list[j]);
13}
14
15private define default_sort_cmp (list, i, j)
16{
17   if (list[i] > list[j]) return 1;
18   if (list[i] == list[j]) return 0;
19   return -1;
20}
21
22
23define list_sort (list)
24{
25   variable dir = qualifier ("dir", 1);
26   variable cmp = qualifier ("cmp");
27
28   variable n = length (list);
29   variable i;
30   if (cmp == NULL)
31     i = array_sort (list, &default_sort_cmp, n; dir=dir);
32   else
33     i = array_sort (struct {list=list, cmp=cmp}, &user_sort_cmp, n; dir=dir);
34
35   variable inplace = qualifier ("inplace", 0);
36   if (inplace == 0)
37     return i;
38
39   rearrange (list, i);
40}
41
42% Heap Implementation
43
44private define heap_length (h)
45{
46   return length (h.list);
47}
48
49private define upheap (list, k, cmp)
50{
51   variable obj = list[k];
52   variable k2 = (k-1)/2;
53   while (k && (@cmp)(obj,list[k2]) > 0)
54     {
55	list[k] = list[k2];
56	k = k2;
57	k2 = (k-1)/2;
58     }
59   list[k] = obj;
60}
61
62private define downheap (list, k, cmp)
63{
64   variable obj = list[k];
65   variable n = length(list), n2 = n/2;
66   n--;
67%           0
68%       1       2
69%   3     4    5     6
70% 7  8   9 10 11 12 13 14
71   while (k < n2)
72     {
73	variable j = 2*k + 1;
74	if ((j < n)
75	    && ((@cmp)(list[j], list[j+1]) < 0))
76	  j++;
77	if ((@cmp)(obj, list[j]) >= 0)
78	  break;
79	list[k] = list[j];
80	k = j;
81     }
82   list[k] = obj;
83}
84
85
86private define heap_add (h, obj)
87{
88   variable list = h.list;
89   list_append (list, obj);
90   upheap (list, length(list)-1, h.cmp);
91}
92
93private define heap_pop (h)
94{
95   variable list = h.list;
96   variable obj = list[0];
97   variable last = list_pop(list, -1);
98   if (length (list))
99     {
100	list[0] = last;
101	downheap (list, 0, h.cmp);
102     }
103   return obj;
104}
105
106private define heap_peek (h)
107{
108   return h.list[0];
109}
110
111private define default_heap_cmp (a, b)
112{
113   if (a > b) return 1;
114   if (a < b) return -1;
115   return 0;
116}
117
118private define default_heap_cmp_rev (a, b)
119{
120   if (a > b) return -1;
121   if (a < b) return 1;
122   return 0;
123}
124
125
126define heap_new ()
127{
128   if (_NARGS == 0)
129     usage (`
130h = new_heap (list; cmp=&cmpfun, dir=val);
131len = h.length();
132h.add (item);
133top = h.remove();
134top = h.peek ();
135`
136	    );
137
138   variable list = ();
139   variable cmp = qualifier ("cmp");
140   variable dir = qualifier ("dir", -1);
141
142   % The conventional interpretation of a heap is that the largest
143   % element is at the root, and smaller ones below.  For this reason,
144   % dir=-1 (ascending order) is the default for sorting.
145   list_sort (list; cmp=cmp, dir=dir, inplace);
146
147   if (cmp == NULL)
148     {
149	cmp = (dir <= 0) ? &default_heap_cmp : &default_heap_cmp_rev;
150     }
151
152   variable h = struct
153     {
154	list = list,
155	cmp = cmp,
156	length = &heap_length,
157	add = &heap_add,
158	remove = &heap_pop,
159	peek = &heap_peek,
160     };
161   return h;
162}
163