1 //
2 // Datastructures: GAP package providing common datastructures.
3 //
4 // Copyright (C) 2015-2017 The datastructures team.
5 // For list of the team members, please refer to the COPYRIGHT file.
6 //
7 // This package is licensed under the GPL 2 or later, please refer
8 // to the COPYRIGHT.md and LICENSE files for details.
9 //
10 // Implementation of a binary heap.
11 //
12 // Binary heaps are of course pretty standard data structures.
13 // However, a few design choices are possible. The implementation
14 // below has been influenced by this StackOverflow answer:
15 // <https://stackoverflow.com/questions/6531543>
16 //
17
18 #include "src/compiled.h"
19 #include "binaryheap.h"
20
21 #define DS_BINARYHEAP_ISLESS(heap) ELM_PLIST(heap, 1)
22 #define DS_BINARYHEAP_DATA(heap) ELM_PLIST(heap, 2)
23
24 // "Bubble-up" helper used for insertion: Given a heap <data> (represented by
25 // a GAP plist), and a comparison operation <isLess>, insert the <elm> at
26 // position <i>. Then compare it to its parent; if they are in the right
27 // order,
28 // stop; otherwise, swap them, and repeat the process, now with the new parent
29 // of our object, until we reach the root.
30 //
31 // In practice, we actually only insert the element as the very last step,
32 // and don't perform actual swaps. That's a simple optimization.
33 //
34 // Note that for normal insertions into the heap, as performed by
35 // DS_BinaryHeap_Insert(), <i> will be equal to the length of <data> plus 1.
36 // But in DS_BinaryHeap_ReplaceMax(), it can be less than that.
DS_BinaryHeap_BubbleUp(Obj data,Obj isLess,Int i,Obj elm)37 static void DS_BinaryHeap_BubbleUp(Obj data, Obj isLess, Int i, Obj elm)
38 {
39 const Int useLt = (isLess == LtOper);
40
41 if (LEN_PLIST(data) < i) {
42 GROW_PLIST(data, i);
43 SET_LEN_PLIST(data, i);
44 }
45
46 while (i > 1) {
47 Obj parent = ELM_PLIST(data, i >> 1);
48 if (useLt) {
49 if (0 == LT(parent, elm))
50 break;
51 }
52 else {
53 if (False == CALL_2ARGS(isLess, parent, elm))
54 break;
55 }
56 SET_ELM_PLIST(data, i, parent);
57 i >>= 1;
58 }
59
60 SET_ELM_PLIST(data, i, elm);
61 CHANGED_BAG(data);
62 }
63
64 // "Bubble down" helper used for extraction: Given a heap <data> (represented
65 // by a GAP plist), and a comparison operation <isLess>, start with a "hole"
66 // or "bubble" at position <i>, and push it down through the heap.
DS_BinaryHeap_BubbleDown(Obj data,Obj isLess,Int i)67 static Int DS_BinaryHeap_BubbleDown(Obj data, Obj isLess, Int i)
68 {
69 const Int useLt = (isLess == LtOper);
70 const Int len = LEN_PLIST(data);
71
72 while (2 * i <= len) {
73 // get positions of the children of <i>
74 Int left = 2 * i;
75 Int right = 2 * i + 1;
76
77 // if there is no right child, move the left child up
78 // and exit
79 if (right > len) {
80 SET_ELM_PLIST(data, i, ELM_PLIST(data, left));
81 i = left;
82 break; // next iteration would stop anyway
83 }
84
85 // otherwise, compare left and right child, and move the larger one up
86 Obj leftObj = ELM_PLIST(data, left);
87 Obj rightObj = ELM_PLIST(data, right);
88 if (useLt ? LT(rightObj, leftObj)
89 : (True == CALL_2ARGS(isLess, rightObj, leftObj))) {
90 SET_ELM_PLIST(data, i, leftObj);
91 i = left;
92 }
93 else {
94 SET_ELM_PLIST(data, i, rightObj);
95 i = right;
96 }
97 }
98
99 return i;
100 }
101
DS_BinaryHeap_Insert(Obj self,Obj heap,Obj elm)102 Obj DS_BinaryHeap_Insert(Obj self, Obj heap, Obj elm)
103 {
104 Obj data = DS_BINARYHEAP_DATA(heap);
105 Obj isLess = DS_BINARYHEAP_ISLESS(heap);
106
107 if (!IS_DENSE_PLIST(data))
108 ErrorQuit("<data> is not a dense plist", 0L, 0L);
109
110 Int len = LEN_PLIST(data);
111 if (len == 0) {
112 AssPlist(data, 1, elm);
113 RetypeBag(data, T_PLIST_DENSE);
114 }
115 else {
116 DS_BinaryHeap_BubbleUp(data, isLess, len + 1, elm);
117 }
118 return 0;
119 }
120
DS_BinaryHeap_ReplaceMax(Obj self,Obj heap,Obj elm)121 Obj DS_BinaryHeap_ReplaceMax(Obj self, Obj heap, Obj elm)
122 {
123 Obj data = DS_BINARYHEAP_DATA(heap);
124 Obj isLess = DS_BINARYHEAP_ISLESS(heap);
125
126 if (!IS_DENSE_PLIST(data))
127 ErrorQuit("<data> is not a dense plist", 0L, 0L);
128
129 // treat the head slot as a hole that we move down into a leaf
130 Int i = DS_BinaryHeap_BubbleDown(data, isLess, 1);
131
132 // insert the new element into the leaf-hole and move it up
133 DS_BinaryHeap_BubbleUp(data, isLess, i, elm);
134
135 return 0;
136 }
137
138 static StructGVarFunc GVarFuncs[] = {
139 GVARFUNC(DS_BinaryHeap_Insert, 2, "heap, elm"),
140 GVARFUNC(DS_BinaryHeap_ReplaceMax, 2, "heap, elm"),
141 { 0 }
142 };
143
InitKernel(void)144 static Int InitKernel(void)
145 {
146 InitHdlrFuncsFromTable(GVarFuncs);
147 return 0;
148 }
149
InitLibrary(void)150 static Int InitLibrary(void)
151 {
152 InitGVarFuncsFromTable(GVarFuncs);
153 return 0;
154 }
155
156 struct DatastructuresModule BinaryHeapModule = {
157 .initKernel = InitKernel, .initLibrary = InitLibrary,
158 };
159