utils/dataStructures/IntervalHeap.java

package ags.utils.dataStructures;

import java.util.Arrays;

/**
 * An implementation of an implicit binary interval heap.
 */
public class IntervalHeap<T> implements MinHeap<T>, MaxHeap<T> {
    private static final int defaultCapacity = 64;
    private Object[] data;
    private double[] keys;
    private int capacity;
    private int size;

    public IntervalHeap() {
        this(defaultCapacity);
    }

    public IntervalHeap(int capacity) {
        this.data = new Object[capacity];
        this.keys = new double[capacity];
        this.capacity = capacity;
        this.size = 0;
    }

    public void offer(double key, T value) {
        // If move room is needed, double array size
        if (size >= capacity) {
            capacity *= 2;
            data = Arrays.copyOf(data, capacity);
            keys = Arrays.copyOf(keys, capacity);
        }

        // Insert new value at the end
        size++;
        data[size-1] = value;
        keys[size-1] = key;
        siftInsertedValueUp();
    }

    public void removeMin() {
        if (size == 0) {
            throw new IllegalStateException();
        }

        size--;
        data[0] = data[size];
        keys[0] = keys[size];
        data[size] = null;
        siftDownMin(0);
    }

    public void replaceMin(double key, T value) {
        if (size == 0) {
            throw new IllegalStateException();
        }

        data[0] = value;
        keys[0] = key;
        if (size > 1) {
            // Swap with pair if necessary
            if (keys[1] < key) {
                swap(0, 1);
            }
            siftDownMin(0);
        }
    }

    public void removeMax() {
        if (size == 0) {
            throw new IllegalStateException();
        } else if (size == 1) {
            removeMin();
            return;
        }

        size--;
        data[1] = data[size];
        keys[1] = keys[size];
        data[size] = null;
        siftDownMax(1);
    }

    public void replaceMax(double key, T value) {
        if (size == 0) {
            throw new IllegalStateException();
        } else if (size == 1) {
            replaceMin(key, value);
            return;
        }

        data[1] = value;
        keys[1] = key;
        // Swap with pair if necessary
        if (key < keys[0]) {
            swap(0, 1);
        }
        siftDownMax(1);
    }

    @SuppressWarnings("unchecked")
    public T getMin() {
        if (size == 0) {
            throw new IllegalStateException();
        }

        return (T) data[0];
    }

    @SuppressWarnings("unchecked")
    public T getMax() {
        if (size == 0) {
            throw new IllegalStateException();
        } else if (size == 1) {
            return (T) data[0];
        }

        return (T) data[1];
    }

    public double getMinKey() {
        if (size == 0) {
            throw new IllegalStateException();
        }

        return keys[0];
    }

    public double getMaxKey() {
        if (size == 0) {
            throw new IllegalStateException();
        } else if (size == 1) {
            return keys[0];
        }

        return keys[1];
    }

    private int swap(int x, int y) {
        Object yData = data[y];
        double yDist = keys[y];
        data[y] = data[x];
        keys[y] = keys[x];
        data[x] = yData;
        keys[x] = yDist;
        return y;
    }

    /**
     * Min-side (u % 2 == 0):
     * - leftchild:  2u + 2
     * - rightchild: 2u + 4
     * - parent:     (x/2-1)&~1
     *
     * Max-side (u % 2 == 1):
     * - leftchild:  2u + 1
     * - rightchild: 2u + 3
     * - parent:     (x/2-1)|1
     */

    private void siftInsertedValueUp() {
        int u = size-1;
        if (u == 0) {
            // Do nothing if it's the only element!
        }
        else if (u == 1) {
            // If it is the second element, just sort it with it's pair
            if  (keys[u] < keys[u-1]) { // If less than it's pair
                swap(u, u-1); // Swap with it's pair
            }
        }
        else if (u % 2 == 1) {
            // Already paired. Ensure pair is ordered right
            int p = (u/2-1)|1; // The larger value of the parent pair
            if  (keys[u] < keys[u-1]) { // If less than it's pair
                u = swap(u, u-1); // Swap with it's pair
                if (keys[u] < keys[p-1]) { // If smaller than smaller parent pair
                    // Swap into min-heap side
                    u = swap(u, p-1);
                    siftUpMin(u);
                }
            } else {
                if (keys[u] > keys[p]) { // If larger that larger parent pair
                    // Swap into max-heap side
                    u = swap(u, p);
                    siftUpMax(u);
                }
            }
        } else {
            // Inserted in the lower-value slot without a partner
            int p = (u/2-1)|1; // The larger value of the parent pair
            if (keys[u] > keys[p]) { // If larger that larger parent pair
                // Swap into max-heap side
                u = swap(u, p);
                siftUpMax(u);
            } else if (keys[u] < keys[p-1]) { // If smaller than smaller parent pair
                // Swap into min-heap side
                u = swap(u, p-1);
                siftUpMin(u);
            }
        }
    }

    private void siftUpMin(int c) {
        // Min-side parent: (x/2-1)&~1
        for (int p = (c/2-1)&~1; p >= 0 && keys[c] < keys[p]; c = p, p = (c/2-1)&~1) {
            swap(c, p);
        }
    }

    private void siftUpMax(int c) {
        // Max-side parent: (x/2-1)|1
        for (int p = (c/2-1)|1; p >= 0 && keys[c] > keys[p]; c = p, p = (c/2-1)|1) {
            swap(c, p);
        }
    }

    private void siftDownMin(int p) {
        for (int c = p * 2 + 2; c < size; p = c, c = p * 2 + 2) {
            if (c + 2 < size && keys[c + 2] < keys[c]) {
                c += 2;
            }
            if (keys[c] < keys[p]) {
                swap(p, c);
                // Swap with pair if necessary
                if (c+1 < size && keys[c+1] < keys[c]) {
                    swap(c, c+1);
                }
            } else {
                break;
            }
        }
    }

    private void siftDownMax(int p) {
        for (int c = p * 2 + 1; c <= size; p = c, c = p * 2 + 1) {
            if (c == size) {
                // If the left child only has half a pair
                if (keys[c - 1] > keys[p]) {
                    swap(p, c - 1);
                }
                break;
            } else if (c + 2 == size) {
                // If there is only room for a right child lower pair
                if (keys[c + 1] > keys[c]) {
                    if (keys[c + 1] > keys[p]) {
                       swap(p, c + 1);
                    }
                    break;
                }
            } else if (c + 2 < size) {
                // If there is room for a right child upper pair
                if (keys[c + 2] > keys[c]) {
                    c += 2;
                }
            }
            if (keys[c] > keys[p]) {
                swap(p, c);
                // Swap with pair if necessary
                if (keys[c-1] > keys[c]) {
                    swap(c, c-1);
                }
            } else {
                break;
            }
        }
    }

    public int size() {
        return size;
    }

    public int capacity() {
        return capacity;
    }

    @Override
    public String toString() {
        java.text.DecimalFormat twoPlaces = new java.text.DecimalFormat("0.00");
        StringBuffer str = new StringBuffer(IntervalHeap.class.getCanonicalName());
        str.append(", size: ").append(size()).append(" capacity: ").append(capacity());
        int i = 0, p = 2;
        while (i < size()) {
            int x = 0;
            str.append("\t");
            while ((i+x) < size() && x < p) {
                str.append(twoPlaces.format(keys[i + x])).append(", ");
                x++;
            }
            str.append("\n");
            i += x;
            p *= 2;
        }
        return str.toString();
    }

    private boolean validateHeap() {
        // Validate left-right
        for (int i = 0; i < size-1; i+= 2) {
            if (keys[i] > keys[i+1]) return false;
        }
        // Validate within parent interval
        for (int i = 2; i < size; i++) {
            double maxParent = keys[(i/2-1)|1];
            double minParent = keys[(i/2-1)&~1];
            if (keys[i] > maxParent || keys[i] < minParent) return false;
        }
        return true;
    }
}
1	package ags.utils.dataStructures;
2
3	import java.util.Arrays;
4
5	/**
6	* An implementation of an implicit binary interval heap.
7	*/
8	public class IntervalHeap<T> implements MinHeap<T>, MaxHeap<T> {
9	private static final int defaultCapacity = 64;
10	private Object[] data;
11	private double[] keys;
12	private int capacity;
13	private int size;
14
15	public IntervalHeap() {
16	this(defaultCapacity);
17	}
18
19	public IntervalHeap(int capacity) {
20	this.data = new Object[capacity];
21	this.keys = new double[capacity];
22	this.capacity = capacity;
23	this.size = 0;
24	}
25
26	public void offer(double key, T value) {
27	// If move room is needed, double array size
28	if (size >= capacity) {
29	capacity *= 2;
30	data = Arrays.copyOf(data, capacity);
31	keys = Arrays.copyOf(keys, capacity);
32	}
33
34	// Insert new value at the end
35	size++;
36	data[size-1] = value;
37	keys[size-1] = key;
38	siftInsertedValueUp();
39	}
40
41	public void removeMin() {
42	if (size == 0) {
43	throw new IllegalStateException();
44	}
45
46	size--;
47	data[0] = data[size];
48	keys[0] = keys[size];
49	data[size] = null;
50	siftDownMin(0);
51	}
52
53	public void replaceMin(double key, T value) {
54	if (size == 0) {
55	throw new IllegalStateException();
56	}
57
58	data[0] = value;
59	keys[0] = key;
60	if (size > 1) {
61	// Swap with pair if necessary
62	if (keys[1] < key) {
63	swap(0, 1);
64	}
65	siftDownMin(0);
66	}
67	}
68
69	public void removeMax() {
70	if (size == 0) {
71	throw new IllegalStateException();
72	} else if (size == 1) {
73	removeMin();
74	return;
75	}
76
77	size--;
78	data[1] = data[size];
79	keys[1] = keys[size];
80	data[size] = null;
81	siftDownMax(1);
82	}
83
84	public void replaceMax(double key, T value) {
85	if (size == 0) {
86	throw new IllegalStateException();
87	} else if (size == 1) {
88	replaceMin(key, value);
89	return;
90	}
91
92	data[1] = value;
93	keys[1] = key;
94	// Swap with pair if necessary
95	if (key < keys[0]) {
96	swap(0, 1);
97	}
98	siftDownMax(1);
99	}
100
101	@SuppressWarnings("unchecked")
102	public T getMin() {
103	if (size == 0) {
104	throw new IllegalStateException();
105	}
106
107	return (T) data[0];
108	}
109
110	@SuppressWarnings("unchecked")
111	public T getMax() {
112	if (size == 0) {
113	throw new IllegalStateException();
114	} else if (size == 1) {
115	return (T) data[0];
116	}
117
118	return (T) data[1];
119	}
120
121	public double getMinKey() {
122	if (size == 0) {
123	throw new IllegalStateException();
124	}
125
126	return keys[0];
127	}
128
129	public double getMaxKey() {
130	if (size == 0) {
131	throw new IllegalStateException();
132	} else if (size == 1) {
133	return keys[0];
134	}
135
136	return keys[1];
137	}
138
139	private int swap(int x, int y) {
140	Object yData = data[y];
141	double yDist = keys[y];
142	data[y] = data[x];
143	keys[y] = keys[x];
144	data[x] = yData;
145	keys[x] = yDist;
146	return y;
147	}
148
149	/**
150	* Min-side (u % 2 == 0):
151	* - leftchild: 2u + 2
152	* - rightchild: 2u + 4
153	* - parent: (x/2-1)&~1
154	*
155	* Max-side (u % 2 == 1):
156	* - leftchild: 2u + 1
157	* - rightchild: 2u + 3
158	* - parent: (x/2-1)\|1
159	*/
160
161	private void siftInsertedValueUp() {
162	int u = size-1;
163	if (u == 0) {
164	// Do nothing if it's the only element!
165	}
166	else if (u == 1) {
167	// If it is the second element, just sort it with it's pair
168	if (keys[u] < keys[u-1]) { // If less than it's pair
169	swap(u, u-1); // Swap with it's pair
170	}
171	}
172	else if (u % 2 == 1) {
173	// Already paired. Ensure pair is ordered right
174	int p = (u/2-1)\|1; // The larger value of the parent pair
175	if (keys[u] < keys[u-1]) { // If less than it's pair
176	u = swap(u, u-1); // Swap with it's pair
177	if (keys[u] < keys[p-1]) { // If smaller than smaller parent pair
178	// Swap into min-heap side
179	u = swap(u, p-1);
180	siftUpMin(u);
181	}
182	} else {
183	if (keys[u] > keys[p]) { // If larger that larger parent pair
184	// Swap into max-heap side
185	u = swap(u, p);
186	siftUpMax(u);
187	}
188	}
189	} else {
190	// Inserted in the lower-value slot without a partner
191	int p = (u/2-1)\|1; // The larger value of the parent pair
192	if (keys[u] > keys[p]) { // If larger that larger parent pair
193	// Swap into max-heap side
194	u = swap(u, p);
195	siftUpMax(u);
196	} else if (keys[u] < keys[p-1]) { // If smaller than smaller parent pair
197	// Swap into min-heap side
198	u = swap(u, p-1);
199	siftUpMin(u);
200	}
201	}
202	}
203
204	private void siftUpMin(int c) {
205	// Min-side parent: (x/2-1)&~1
206	for (int p = (c/2-1)&~1; p >= 0 && keys[c] < keys[p]; c = p, p = (c/2-1)&~1) {
207	swap(c, p);
208	}
209	}
210
211	private void siftUpMax(int c) {
212	// Max-side parent: (x/2-1)\|1
213	for (int p = (c/2-1)\|1; p >= 0 && keys[c] > keys[p]; c = p, p = (c/2-1)\|1) {
214	swap(c, p);
215	}
216	}
217
218	private void siftDownMin(int p) {
219	for (int c = p * 2 + 2; c < size; p = c, c = p * 2 + 2) {
220	if (c + 2 < size && keys[c + 2] < keys[c]) {
221	c += 2;
222	}
223	if (keys[c] < keys[p]) {
224	swap(p, c);
225	// Swap with pair if necessary
226	if (c+1 < size && keys[c+1] < keys[c]) {
227	swap(c, c+1);
228	}
229	} else {
230	break;
231	}
232	}
233	}
234
235	private void siftDownMax(int p) {
236	for (int c = p * 2 + 1; c <= size; p = c, c = p * 2 + 1) {
237	if (c == size) {
238	// If the left child only has half a pair
239	if (keys[c - 1] > keys[p]) {
240	swap(p, c - 1);
241	}
242	break;
243	} else if (c + 2 == size) {
244	// If there is only room for a right child lower pair
245	if (keys[c + 1] > keys[c]) {
246	if (keys[c + 1] > keys[p]) {
247	swap(p, c + 1);
248	}
249	break;
250	}
251	} else if (c + 2 < size) {
252	// If there is room for a right child upper pair
253	if (keys[c + 2] > keys[c]) {
254	c += 2;
255	}
256	}
257	if (keys[c] > keys[p]) {
258	swap(p, c);
259	// Swap with pair if necessary
260	if (keys[c-1] > keys[c]) {
261	swap(c, c-1);
262	}
263	} else {
264	break;
265	}
266	}
267	}
268
269	public int size() {
270	return size;
271	}
272
273	public int capacity() {
274	return capacity;
275	}
276
277	@Override
278	public String toString() {
279	java.text.DecimalFormat twoPlaces = new java.text.DecimalFormat("0.00");
280	StringBuffer str = new StringBuffer(IntervalHeap.class.getCanonicalName());
281	str.append(", size: ").append(size()).append(" capacity: ").append(capacity());
282	int i = 0, p = 2;
283	while (i < size()) {
284	int x = 0;
285	str.append("\t");
286	while ((i+x) < size() && x < p) {
287	str.append(twoPlaces.format(keys[i + x])).append(", ");
288	x++;
289	}
290	str.append("\n");
291	i += x;
292	p *= 2;
293	}
294	return str.toString();
295	}
296
297	private boolean validateHeap() {
298	// Validate left-right
299	for (int i = 0; i < size-1; i+= 2) {
300	if (keys[i] > keys[i+1]) return false;
301	}
302	// Validate within parent interval
303	for (int i = 2; i < size; i++) {
304	double maxParent = keys[(i/2-1)\|1];
305	double minParent = keys[(i/2-1)&~1];
306	if (keys[i] > maxParent \|\| keys[i] < minParent) return false;
307	}
308	return true;
309	}
310	}