package imbusy;

import java.util.concurrent.ConcurrentSkipListSet;
import java.util.concurrent.ConcurrentHashMap;
import static java.lang.System.currentTimeMillis;
import java.util.Comparator;
import java.util.Iterator;

import imbusy.ExpireMap;

public class ConcurrentExpireHashMap<K,V> implements ExpireMap<K,V> {
  
  // store values together with their expiration time in milliseconds
  // in the underlying hash map.
  private static class ValueTimestamp<V> {
    public ValueTimestamp(V value, long timeoutMs) {
      this.value = value;
      this.timeout = currentTimeMillis() + timeoutMs;
    }
    public V value;
    public long timeout;
  }
   
  // the underlying hash map
  private ConcurrentHashMap<K, ValueTimestamp<V>> hashMap;
  
  private static class KeyValueTimestamp<K, V> {
    public KeyValueTimestamp(K key, ValueTimestamp<V> valueTimestamp) {
      this.key = key;
      this.valueTimestamp = valueTimestamp;
    }
    public K key;
    public ValueTimestamp<V> valueTimestamp;
    
    @Override
    public boolean equals(Object o) {
      KeyValueTimestamp<K, V> other = (KeyValueTimestamp<K, V>)o;
      if(other == null) return false;
      if(this.key == other.key &&
         this.valueTimestamp.value == other.valueTimestamp.value &&
         this.valueTimestamp.timeout == other.valueTimestamp.timeout) {
        return true;
      }
      return false;
    }
  }
  
  // an ordered set where we store element expiration times
  ConcurrentSkipListSet<KeyValueTimestamp<K,V>> expirationSet;
  RemovalLoop removalLoop;
  
  // a task that removes elements from the hash map once they expire
  private class RemovalLoop implements Runnable {
    public void run() {
      while(true) {
        long nextTimestamp = -1;
        long curTimestamp = currentTimeMillis();
        
        // remove elements that timed out and figure out the length
        // of time to sleep in milliseconds till next expiration
        for(KeyValueTimestamp<K, V> element : expirationSet) {
          if(element.valueTimestamp.timeout <= curTimestamp) {
            hashMap.remove(element.key, element.valueTimestamp);
            expirationSet.remove(element);
          } else {
            nextTimestamp = element.valueTimestamp.timeout;
            break;
          }
        }
        
        try {
          if(nextTimestamp > 0) {
            Thread.sleep(nextTimestamp - curTimestamp);
          } else {
            Thread.sleep(1000);
          }
        } catch(InterruptedException e) {
        }
      }
    }
    
    public synchronized void newValue() {
      notify();
    }
  }
  
  public ConcurrentExpireHashMap() {
    hashMap = new ConcurrentHashMap<K, ValueTimestamp<V>>();
    
    expirationSet = new ConcurrentSkipListSet<KeyValueTimestamp<K,V>>(
      new Comparator<KeyValueTimestamp<K, V>>() {
        public int compare(KeyValueTimestamp<K, V> a, KeyValueTimestamp<K, V> b) {
          return a.valueTimestamp.timeout > b.valueTimestamp.timeout ? 1 
                  : a.valueTimestamp.timeout < b.valueTimestamp.timeout ? -1 : 0;
        }
      }
    );
    
    removalLoop = new RemovalLoop();
    Thread t = new Thread(removalLoop);
    t.start();
  }
   
  public void put(K key, V value, long timeoutMs) {
    if(timeoutMs > 0) {
      ValueTimestamp<V> vt = new ValueTimestamp<V>(value, timeoutMs);
      hashMap.put(key, vt);
      expirationSet.add(new KeyValueTimestamp(key, vt));
      removalLoop.newValue();
    }
  }
   
  public V get(K key) {
    ValueTimestamp value = hashMap.get(key);
    if(value != null) {
      if(value.timeout <= currentTimeMillis()) {
        return null;
      } else {
        return (V)value.value;
      }
    }
    return null;
  }
   
  public void remove(K key) {
    hashMap.remove(key);
  }
}

@@ -743,16 +743,109 @@
 Map;%0A  %0A
+  // used in RemovalLoop to store the exact key, value, timestamp%0A  // triples to be removed%0A
   privat
@@ -1488,21 +1488,149 @@
 %7D%0A  %7D%0A  
+  
 %0A  //
+ a task that removes elements from the hash map once they expire%0A  private class RemovalLoop implements Runnable %7B%0A    %0A    //
  an orde
@@ -1677,16 +1677,18 @@
 n times%0A
+  
   Concur
@@ -1748,154 +1748,471 @@
 ;%0A  
-RemovalLoop removalLoop;%0A
+  %0A    public RemovalLoop() %7B%0A      expirationSet = new ConcurrentSkipListSet%3CKeyValueTimestamp%3CK,V%3E%3E(%0A 
   
-%0A
   
-// a task that removes elements from the hash map once they expire%0A  private class RemovalLoop implements Runnable %7B
+   new Comparator%3CKeyValueTimestamp%3CK, V%3E%3E() %7B // order by timestamp%0A          public int compare(KeyValueTimestamp%3CK, V%3E a, KeyValueTimestamp%3CK, V%3E b) %7B%0A            return a.valueTimestamp.timeout %3E b.valueTimestamp.timeout ? 1 %0A                    : a.valueTimestamp.timeout %3C b.valueTimestamp.timeout ? -1 : 0;%0A          %7D%0A        %7D%0A      );%0A    %7D%0A    
 %0A   
@@ -3092,21 +3092,8 @@
 lic 
-synchronized 
 void
@@ -3106,115 +3106,13 @@
 lue(
-) %7B%0A      notify();%0A    %7D%0A  %7D%0A  %0A  public ConcurrentExpireHashMap() %7B%0A    hashMap = new ConcurrentHashMap%3CK
+K key
 , Va
@@ -3127,21 +3127,17 @@
 tamp
-%3CV%3E%3E();%0A  
+ vt) %7B%0A
   
-%0A
     
@@ -3153,373 +3153,237 @@
 nSet
- = new ConcurrentSkipListSet%3CKeyValueTimestamp%3CK,V%3E%3E(%0A      new Comparator%3CKeyValueTimestamp%3CK, V%3E%3E() %7B%0A        public int compare(KeyValueTimestamp%3CK, V%3E a, KeyValueTimestamp%3CK, V%3E b) %7B%0A      
+.add(new KeyValueTimestamp(key, vt));%0A      synchronized(this) %7B%0A        notify();%0A      %7D%0A    %7D%0A  %7D%0A
   
+%0A
   
-return a.valueTimestamp.timeout %3E b.valueTimestamp.timeout ? 1 %0A                  : a.valueTimestamp.timeout %3C b.valueTimestamp.timeout ? -1 : 0;%0A        %7D%0A      %7D%0A    
+RemovalLoop removalLoop;%0A  %0A  public ConcurrentExpireHashMap() %7B%0A    hashMap = new ConcurrentHashMap%3CK, ValueTimestamp%3CV%3E%3E(
 );%0A 
@@ -3664,65 +3664,8 @@
 t);%0A
-      expirationSet.add(new KeyValueTimestamp(key, vt));%0A
     
@@ -3687,16 +3687,23 @@
 ewValue(
+key, vt
 );%0A    %7D

reorganize code