utils/dataStructures/BinaryHeap.java

package ags.utils.dataStructures;

import java.util.Arrays;

/**
 * An implementation of an implicit binary heap. Min-heap and max-heap both supported 
 */
public abstract class BinaryHeap<T> {
    protected static final int defaultCapacity = 64;
    private final int direction;
    private Object[] data;
    private double[] keys;
    private int capacity;
    private int size;

    protected BinaryHeap(int capacity, int direction) {
        this.direction = direction;
        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
        data[size] = value;
        keys[size] = key;
        siftUp(size);
        size++;
    }

    protected void removeTip() {
        if (size == 0) {
            throw new IllegalStateException();
        }

        size--;
        data[0] = data[size];
        keys[0] = keys[size];
        data[size] = null;
        siftDown(0);
    }
    
    protected void replaceTip(double key, T value) {
        if (size == 0) {
            throw new IllegalStateException();
        }

        data[0] = value;
        keys[0] = key;
        siftDown(0);
    }

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

        return (T) data[0];
    }

    protected double getTipKey() {
        if (size == 0) {
            throw new IllegalStateException();
        }

        return keys[0];
    }

    private void siftUp(int c) {
        for (int p = (c - 1) / 2; c != 0 && direction*keys[c] > direction*keys[p]; c = p, p = (c - 1) / 2) {
            Object pData = data[p];
            double pDist = keys[p];
            data[p] = data[c];
            keys[p] = keys[c];
            data[c] = pData;
            keys[c] = pDist;
        }
    }

    private void siftDown(int p) {
        for (int c = p * 2 + 1; c < size; p = c, c = p * 2 + 1) {
            if (c + 1 < size && direction*keys[c] < direction*keys[c + 1]) {
                c++;
            }
            if (direction*keys[p] < direction*keys[c]) {
                // Swap the points
                Object pData = data[p];
                double pDist = keys[p];
                data[p] = data[c];
                keys[p] = keys[c];
                data[c] = pData;
                keys[c] = pDist;
            } else {
                break;
            }
        }
    }

    public int size() {
        return size;
    }

    public int capacity() {
        return capacity;
    }

    public static final class Max<T> extends BinaryHeap<T> implements MaxHeap<T> {
        public Max() {
            super(defaultCapacity, 1);
        }
        public Max(int capacity) {
            super(capacity, 1);
        }
        public void removeMax() {
            removeTip();
        }
        public void replaceMax(double key, T value) {
            replaceTip(key, value);
        }
        public T getMax() {
            return getTip();
        }
        public double getMaxKey() {
            return getTipKey();
        }
    }
    public static final class Min<T> extends BinaryHeap<T> implements MinHeap<T> {
        public Min() {
            super(defaultCapacity, -1);
        }
        public Min(int capacity) {
            super(capacity, -1);
        }
        public void removeMin() {
            removeTip();
        }
        public void replaceMin(double key, T value) {
            replaceTip(key, value);
        }
        public T getMin() {
            return getTip();
        }
        public double getMinKey() {
            return getTipKey();
        }
    }
}
1	torben	2744	package ags.utils.dataStructures;
2
3			import java.util.Arrays;
4
5			/**
6			* An implementation of an implicit binary heap. Min-heap and max-heap both supported
7			*/
8			public abstract class BinaryHeap<T> {
9			protected static final int defaultCapacity = 64;
10			private final int direction;
11			private Object[] data;
12			private double[] keys;
13			private int capacity;
14			private int size;
15
16			protected BinaryHeap(int capacity, int direction) {
17			this.direction = direction;
18			this.data = new Object[capacity];
19			this.keys = new double[capacity];
20			this.capacity = capacity;
21			this.size = 0;
22			}
23
24			public void offer(double key, T value) {
25			// If move room is needed, double array size
26			if (size >= capacity) {
27			capacity *= 2;
28			data = Arrays.copyOf(data, capacity);
29			keys = Arrays.copyOf(keys, capacity);
30			}
31
32			// Insert new value at the end
33			data[size] = value;
34			keys[size] = key;
35			siftUp(size);
36			size++;
37			}
38
39			protected void removeTip() {
40			if (size == 0) {
41			throw new IllegalStateException();
42			}
43
44			size--;
45			data[0] = data[size];
46			keys[0] = keys[size];
47			data[size] = null;
48			siftDown(0);
49			}
50
51			protected void replaceTip(double key, T value) {
52			if (size == 0) {
53			throw new IllegalStateException();
54			}
55
56			data[0] = value;
57			keys[0] = key;
58			siftDown(0);
59			}
60
61			@SuppressWarnings("unchecked")
62			protected T getTip() {
63			if (size == 0) {
64			throw new IllegalStateException();
65			}
66
67			return (T) data[0];
68			}
69
70			protected double getTipKey() {
71			if (size == 0) {
72			throw new IllegalStateException();
73			}
74
75			return keys[0];
76			}
77
78			private void siftUp(int c) {
79			for (int p = (c - 1) / 2; c != 0 && directionkeys[c] > directionkeys[p]; c = p, p = (c - 1) / 2) {
80			Object pData = data[p];
81			double pDist = keys[p];
82			data[p] = data[c];
83			keys[p] = keys[c];
84			data[c] = pData;
85			keys[c] = pDist;
86			}
87			}
88
89			private void siftDown(int p) {
90			for (int c = p * 2 + 1; c < size; p = c, c = p * 2 + 1) {
91			if (c + 1 < size && directionkeys[c] < directionkeys[c + 1]) {
92			c++;
93			}
94			if (directionkeys[p] < directionkeys[c]) {
95			// Swap the points
96			Object pData = data[p];
97			double pDist = keys[p];
98			data[p] = data[c];
99			keys[p] = keys[c];
100			data[c] = pData;
101			keys[c] = pDist;
102			} else {
103			break;
104			}
105			}
106			}
107
108			public int size() {
109			return size;
110			}
111
112			public int capacity() {
113			return capacity;
114			}
115
116			public static final class Max<T> extends BinaryHeap<T> implements MaxHeap<T> {
117			public Max() {
118			super(defaultCapacity, 1);
119			}
120			public Max(int capacity) {
121			super(capacity, 1);
122			}
123			public void removeMax() {
124			removeTip();
125			}
126			public void replaceMax(double key, T value) {
127			replaceTip(key, value);
128			}
129			public T getMax() {
130			return getTip();
131			}
132			public double getMaxKey() {
133			return getTipKey();
134			}
135			}
136			public static final class Min<T> extends BinaryHeap<T> implements MinHeap<T> {
137			public Min() {
138			super(defaultCapacity, -1);
139			}
140			public Min(int capacity) {
141			super(capacity, -1);
142			}
143			public void removeMin() {
144			removeTip();
145			}
146			public void replaceMin(double key, T value) {
147			replaceTip(key, value);
148			}
149			public T getMin() {
150			return getTip();
151			}
152			public double getMinKey() {
153			return getTipKey();
154			}
155			}
156			}