src/jagi/event/Heap.java

   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 }