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         index.remove(ret);
  75         return(ret);
  76     }
  77
  78     public V remove() {
  79         if(size == 0)
  80             throw(new NoSuchElementException());
  81         V ret = val(0);
  82         remove(0);
  83         index.remove(ret);
  84         return(ret);
  85     }
  86
  87     public K keypeek() {
  88         return((size > 0) ? key(0) : null);
  89     }
  90
  91     public void add(V val, K key) {
  92         if(index.containsKey(val))
  93             throw(new IllegalStateException());
  94         int p = size++;
  95         if(p >= vbuf.length) {
  96             int n = Math.max(vbuf.length * 2, 16);
  97             vbuf = Arrays.copyOf(vbuf, n);
  98             kbuf = Arrays.copyOf(kbuf, n);
  99         }
 100         raise(val, key, p);
 101     }
 102
 103     public K update(V val, K key) {
 104         Integer p = index.get(val);
 105         if(p == null)
 106             throw(new NoSuchElementException());
 107         K ret = key(p);
 108         adjust(val, key, p);
 109         return(ret);
 110     }
 111
 112     public K set(V val, K key) {
 113         Integer p = index.get(val);
 114         if(p == null) {
 115             add(val, key);
 116             return(null);
 117         }
 118         K ret = key(p);
 119         adjust(val, key, p);
 120         return(ret);
 121     }
 122
 123     private K remove(int p) {
 124         K ret = key(p);
 125         size--;
 126         if(p == size) {
 127         } else if(p < size) {
 128             adjust(val(size), key(size), p);
 129         } else {
 130             throw(new AssertionError());
 131         }
 132         vbuf[size] = null;
 133         kbuf[size] = null;
 134         return(ret);
 135     }
 136
 137     public K remove(V val) {
 138         Integer p = index.remove(val);
 139         if(p == null)
 140             return(null);
 141         return(remove(p));
 142     }
 143
 144     public boolean contains(V val) {
 145         return(index.containsKey(val));
 146     }
 147
 148     public String toString() {
 149         StringBuilder buf = new StringBuilder();
 150         buf.append('[');
 151         for(int i = 0; i < size; i++) {
 152             if(i > 0)
 153                 buf.append(", ");
 154             buf.append(String.valueOf(kbuf[i]));
 155             buf.append('=');
 156             buf.append(String.valueOf(vbuf[i]));
 157         }
 158         buf.append(']');
 159         return(buf.toString());
 160     }
 161 }