mergearray.seqpq.skewheap source code

1 module mergearray.seqpq.skewheap;
2 
3 /++
4 A sequential Skew Heap implementation of a priority queue of elements T using
5 allocator Alloc.
6 +/
7 struct SkewHeap(T, Alloc) {
8 private:
9     struct Node {
10         Node* left = null;
11         Node* right = null;
12         T value = void;
13         
14         this(T t) {
15             value = t;
16         }
17     }
18     
19     Node* head = null;
20     size_t size = 0;
21     
22     static Node* merge(Node* a, Node* b) {
23         enum useRecursion = true;
24         
25         static if (useRecursion) {
26             static join(Node* x, Node* y) {
27                 auto l = x.left;
28                 x.left = x.right;
29                 x.right = merge(l, y);
30                 return x;
31             }
32             
33             if (a is null) {
34                 return b;
35             }
36             else if (b is null) {
37                 return a;
38             }
39             else if (a.value < b.value) {
40                 return join(a,b);
41             }
42             else {
43                 return join(b,a);
44             }
45             
46             assert(false);
47         }
48         else {
49             Node* root = null;
50             Node** result = &root;
51             
52             while(true) {
53                 if (a is null) {
54                     *result = b;
55                     break;
56                 }
57                 else if (b is null) {
58                     *result = a;
59                     break;
60                 }
61                 
62                 if (a.value >= b.value) {
63                     import std.algorithm;
64                     
65                     swap(a,b);
66                 }
67                 
68                 *result = a;
69                 result = &a.right;
70                 
71                 auto l = a.left;
72                 a.left = a.right;
73                 a = l;
74             }
75             
76             return root;
77         }
78     }
79     
80     void insert(Node* n) {
81         size++;
82         head = merge(head, n);
83     }
84     
85 public:
86     /++
87     The number of bytes allocated per element inserted.
88     +/
89     enum size_t NodeSize = Node.sizeof;
90     
91     /++
92     Property returning true if and only if the container has no elements.
93     Complexity: O(1)
94     +/
95     @property
96     bool empty() const {
97         return head is null;
98     }
99     
100     /++
101     Returns the number of elements in the container.
102     Complexity: O(1)
103     +/
104     @property
105     size_t length() const {
106         return size;
107     }
108     
109     /++
110     Inserts t into the container.
111     Complexity: O(log n)
112     +/
113     void insert(T t) {
114         size++;
115         
116         Node* n = Alloc.alloc!Node(t);
117         
118         head = merge(head, n);
119     }
120     
121     import std.typecons : Nullable;
122     /++
123     Removes the element with the minimum value.
124     Complexity: O(log n)
125     +/
126     Nullable!T deleteMin() {
127         if (empty) {
128             return Nullable!T();
129         }
130         else {
131             auto t = Nullable!T(head.value);
132             
133             Node* oldhead = head;
134             
135             head = merge(head.left, head.right);
136             
137             size--;
138             
139             return t;
140         }
141     }
142     
143     /++
144     Returns the minimum element of the container.
145     Complexity: O(1)
146     +/
147     Nullable!T peekMin() {
148         if (empty) {
149             return Nullable!T();
150         }
151         else {
152             return Nullable!T(head.value);
153         }
154     }
155     
156     /++
157     Steals the elements of other and inserts them (in bulk) into this container.
158     
159     Other is left empty.
160     
161     Complexity: O(log n + log m), where m = other.length
162     +/
163     void mergeSteal(ref SkewHeap other) {
164         head = merge(head, other.head);
165         other.head = null;
166         
167         size += other.size;
168         other.size = 0;
169     }
170 }