Commit | Line | Data |
---|---|---|
aac2f975 FT |
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 | } |