| 1 | package jagi.event; |
| 2 | |
| 3 | import java.util.*; |
| 4 | |
| 5 | public class Heap<V, K> { |
| 6 | private static final Object[] empty = {}; |
| 7 | private final Comparator<? super K> cmp; |
| 8 | private final Map<V, Integer> index = new IdentityHashMap<>(); |
| 9 | private Object[] vbuf = empty, kbuf = empty; |
| 10 | private int size; |
| 11 | |
| 12 | public Heap(Comparator<? super K> cmp) { |
| 13 | this.cmp = cmp; |
| 14 | } |
| 15 | |
| 16 | @SuppressWarnings("unchecked") |
| 17 | private V val(int i) {return((V)vbuf[i]);} |
| 18 | @SuppressWarnings("unchecked") |
| 19 | private K key(int i) {return((K)kbuf[i]);} |
| 20 | |
| 21 | private void raise(V val, K key, int i) { |
| 22 | while(i > 0) { |
| 23 | int p = (i - 1) >>> 1; |
| 24 | if(cmp.compare(key(p), key) <= 0) |
| 25 | break; |
| 26 | vbuf[i] = vbuf[p]; |
| 27 | kbuf[i] = kbuf[p]; |
| 28 | index.put(val(i), i); |
| 29 | i = p; |
| 30 | } |
| 31 | vbuf[i] = val; |
| 32 | kbuf[i] = key; |
| 33 | index.put(val, i); |
| 34 | } |
| 35 | |
| 36 | private void lower(V val, K key, int i) { |
| 37 | while(true) { |
| 38 | int c1 = (i << 1) + 1, c2 = c1 + 1; |
| 39 | if(c1 >= size) |
| 40 | break; |
| 41 | int c = ((c2 < size) && (cmp.compare(key(c1), key(c2)) > 0)) ? c2 : c1; |
| 42 | if(cmp.compare(key(c), key) > 0) |
| 43 | break; |
| 44 | vbuf[i] = vbuf[c]; |
| 45 | kbuf[i] = kbuf[c]; |
| 46 | index.put(val(i), i); |
| 47 | i = c; |
| 48 | } |
| 49 | vbuf[i] = val; |
| 50 | kbuf[i] = key; |
| 51 | index.put(val, i); |
| 52 | } |
| 53 | |
| 54 | private void adjust(V val, K key, int i) { |
| 55 | if((i > 0) && cmp.compare(key((i - 1) >> 1), key) > 0) |
| 56 | raise(val, key, i); |
| 57 | else |
| 58 | lower(val, key, i); |
| 59 | } |
| 60 | |
| 61 | public int size() { |
| 62 | return(size); |
| 63 | } |
| 64 | |
| 65 | public V peek() { |
| 66 | return((size > 0) ? val(0) : null); |
| 67 | } |
| 68 | |
| 69 | public V poll() { |
| 70 | if(size == 0) |
| 71 | return(null); |
| 72 | V ret = val(0); |
| 73 | remove(0); |
| 74 | return(ret); |
| 75 | } |
| 76 | |
| 77 | public V remove() { |
| 78 | if(size == 0) |
| 79 | throw(new NoSuchElementException()); |
| 80 | V ret = val(0); |
| 81 | remove(0); |
| 82 | return(ret); |
| 83 | } |
| 84 | |
| 85 | public K keypeek() { |
| 86 | return((size > 0) ? key(0) : null); |
| 87 | } |
| 88 | |
| 89 | public void add(V val, K key) { |
| 90 | if(index.containsKey(val)) |
| 91 | throw(new IllegalStateException()); |
| 92 | int p = size++; |
| 93 | if(p >= vbuf.length) { |
| 94 | int n = Math.max(vbuf.length * 2, 16); |
| 95 | vbuf = Arrays.copyOf(vbuf, n); |
| 96 | kbuf = Arrays.copyOf(kbuf, n); |
| 97 | } |
| 98 | raise(val, key, p); |
| 99 | } |
| 100 | |
| 101 | public K update(V val, K key) { |
| 102 | Integer p = index.get(val); |
| 103 | if(p == null) |
| 104 | throw(new NoSuchElementException()); |
| 105 | K ret = key(p); |
| 106 | adjust(val, key, p); |
| 107 | return(ret); |
| 108 | } |
| 109 | |
| 110 | public K set(V val, K key) { |
| 111 | Integer p = index.get(val); |
| 112 | if(p == null) { |
| 113 | add(val, key); |
| 114 | return(null); |
| 115 | } |
| 116 | K ret = key(p); |
| 117 | adjust(val, key, p); |
| 118 | return(ret); |
| 119 | } |
| 120 | |
| 121 | private K remove(int p) { |
| 122 | K ret = key(p); |
| 123 | size--; |
| 124 | if(p == size) { |
| 125 | } else if(p < size) { |
| 126 | adjust(val(size), key(size), p); |
| 127 | } else { |
| 128 | throw(new AssertionError()); |
| 129 | } |
| 130 | vbuf[size] = null; |
| 131 | kbuf[size] = null; |
| 132 | return(ret); |
| 133 | } |
| 134 | |
| 135 | public K remove(V val) { |
| 136 | Integer p = index.remove(val); |
| 137 | if(p == null) |
| 138 | return(null); |
| 139 | return(remove(p)); |
| 140 | } |
| 141 | |
| 142 | public boolean contains(V val) { |
| 143 | return(index.containsKey(val)); |
| 144 | } |
| 145 | |
| 146 | public String toString() { |
| 147 | StringBuilder buf = new StringBuilder(); |
| 148 | buf.append('['); |
| 149 | for(int i = 0; i < size; i++) { |
| 150 | if(i > 0) |
| 151 | buf.append(", "); |
| 152 | buf.append(String.valueOf(kbuf[i])); |
| 153 | buf.append('='); |
| 154 | buf.append(String.valueOf(vbuf[i])); |
| 155 | } |
| 156 | buf.append(']'); |
| 157 | return(buf.toString()); |
| 158 | } |
| 159 | } |