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	torben	2744	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			}