Author: j16sdiz
Date: 2009-04-07 07:59:26 +0000 (Tue, 07 Apr 2009)
New Revision: 26596
Modified:
trunk/freenet/src/freenet/support/TimeSortedHashtable.java
trunk/freenet/test/freenet/support/TimeSortedHashtableTest.java
Log:
Simplify TimeSortedHashtable and make *after() exclusive
Modified: trunk/freenet/src/freenet/support/TimeSortedHashtable.java
===================================================================
--- trunk/freenet/src/freenet/support/TimeSortedHashtable.java 2009-04-07
07:59:01 UTC (rev 26595)
+++ trunk/freenet/src/freenet/support/TimeSortedHashtable.java 2009-04-07
07:59:26 UTC (rev 26596)
@@ -1,6 +1,5 @@
package freenet.support;
-import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
@@ -9,19 +8,16 @@
/**
* Variant on LRUHashtable which provides an efficient how-many-since-time-T
operation.
*/
-public class TimeSortedHashtable<T extends Comparable> {
+public class TimeSortedHashtable<T extends Comparable<T>> {
public TimeSortedHashtable() {
- this.elements = new TreeSet<Comparable>(new MyComparator());
+ this.elements = new TreeSet<Element<T>>();
this.valueToElement = new HashMap<T, Element<T>>();
}
- private static class Element<T extends Comparable> implements
Comparable<Element<T>> {
-
+ private static class Element<T extends Comparable<T>> implements
Comparable<Element<T>> {
Element(long t, T v) {
time = t;
value = v;
- if(value == null)
- throw new NullPointerException();
}
long time;
@@ -30,37 +26,15 @@
public int compareTo(Element<T> o) {
if(time > o.time) return 1;
if(time < o.time) return -1;
+ if (value == null && o.value == null) return 0;
+ if (value == null && o.value != null) return 1;
+ if (value != null && o.value == null) return -1;
return value.compareTo(o.value);
}
}
- private static class MyComparator implements Comparator /* <Long ||
Element<T>> */{
-
- public int compare(Object arg0, Object arg1) {
- if(arg0 instanceof Long && arg1 instanceof Long) return
((Long)arg0).compareTo((Long)arg1);
- if (arg0 instanceof Element && arg1 instanceof Element)
- return ((Element) arg0).compareTo((Element)
arg1);
- // Comparing a Long with an Element, because we are
searching for an Element by the value of a Long.
- // Hence we do not need to consider the element value.
- if(arg0 instanceof Long) {
- long l = ((Long)arg0).longValue();
- Element e = (Element)arg1;
- if(l > e.time) return 1;
- if(l < e.time) return -1;
- return 0;
- } else {
- // arg1 instanceof Long
- Element e = (Element)arg0;
- long l = ((Long)arg1).longValue();
- if(e.time > l) return 1;
- if(e.time < l) return -1;
- return 0;
- }
- }
-
- }
- private final TreeSet<Comparable> /* <Long || Element<T>> */elements;
+ private final TreeSet<Element<T>> elements;
private final HashMap<T, Element<T>> valueToElement;
/**
@@ -91,7 +65,7 @@
public final int size() {
return elements.size();
}
-
+
public final synchronized boolean removeValue(T value) {
assert(elements.size() == valueToElement.size());
Element<T> e = valueToElement.remove(value);
@@ -114,52 +88,27 @@
if(e == null) return -1;
return e.time;
}
-
+
/**
- * @return The set of times after the given time.
+ * Count the number of values after specified timestamp
+ * @param timestamp
+ * @return value count
*/
- private final synchronized Long[] timesAfter(long t) {
- Set<Comparable> s = elements.tailSet(t);
-
- Long[] times = new Long[s.size()];
- int x = 0;
- for(Iterator<Comparable> i = s.iterator();i.hasNext();) {
- times[x++] = ((Element<T>) i.next()).time;
- }
-
- return times;
- }
-
- /**
- * @return The set of values after the given time.
- */
- // FIXME this is broken if timestamp != -1
- private final synchronized <E extends Comparable> E[] valuesAfter(long t,
E[] values) {
- Set<Comparable> s = elements.tailSet(t);
-
- int x = 0;
- for(Iterator<Comparable> i = s.iterator();i.hasNext();) {
- values[x++] = (E) ((Element<T>) i.next()).value;
- }
-
- return values;
- }
-
public synchronized int countValuesAfter(long t) {
- Set<Comparable> s = elements.tailSet(t);
+ Set<Comparable> s = elements.tailSet(new Element<T>(t, null));
return s.size();
}
/**
- * Remove all entries before the given time.
+ * Remove all entries on or before the given time.
*/
public final synchronized void removeBefore(long t) {
assert(elements.size() == valueToElement.size());
- Set<Comparable> s = elements.headSet(t);
+ Set<Element<T>> s = elements.headSet(new Element<T>(t, null));
- for(Iterator<Comparable> i = s.iterator();i.hasNext();) {
- Element<T> e = (Element<T>) i.next();
+ for(Iterator<Element<T>> i = s.iterator();i.hasNext();) {
+ Element<T> e = i.next();
valueToElement.remove(e.value);
i.remove();
}
@@ -168,7 +117,17 @@
}
// FIXME this is broken if timestamp != -1
- public final synchronized <E extends Comparable> Object[]
pairsAfter(long timestamp, E[] valuesArray) {
- return new Object[] { valuesAfter(timestamp, valuesArray),
timesAfter(timestamp) };
+ public final synchronized <E> Object[] pairsAfter(long timestamp, E[]
valuesArray) {
+ Set<Element<T>> s = elements.tailSet(new Element<T>(timestamp, null));
+ Long[] timeArray = new Long[s.size()];
+
+ int i = 0;
+ for (Element<T> e : s) {
+ timeArray[i] = e.time;
+ valuesArray[i] = (E) e.value;
+ i++;
+ }
+
+ return new Object[] { valuesArray, timeArray };
}
-}
\ No newline at end of file
+}
Modified: trunk/freenet/test/freenet/support/TimeSortedHashtableTest.java
===================================================================
--- trunk/freenet/test/freenet/support/TimeSortedHashtableTest.java
2009-04-07 07:59:01 UTC (rev 26595)
+++ trunk/freenet/test/freenet/support/TimeSortedHashtableTest.java
2009-04-07 07:59:26 UTC (rev 26596)
@@ -13,14 +13,15 @@
tsh.push("KEY1", 100);
assertEquals(1, tsh.countValuesAfter(0));
assertEquals(1, tsh.size());
- //assertEquals(0, tsh.countValuesAfter(100));
+ assertEquals(1, tsh.countValuesAfter(99));
+ assertEquals(0, tsh.countValuesAfter(100));
assertEquals(0, tsh.countValuesAfter(101));
assertTrue(tsh.containsValue("KEY1"));
tsh.push("KEY2", 100);
assertEquals(2, tsh.countValuesAfter(0));
assertEquals(2, tsh.size());
- //assertEquals(0, tsh.countValuesAfter(100));
+ assertEquals(0, tsh.countValuesAfter(100));
assertEquals(0, tsh.countValuesAfter(101));
assertTrue(tsh.containsValue("KEY1"));
assertTrue(tsh.containsValue("KEY2"));
@@ -28,7 +29,7 @@
tsh.push("KEY3", 300);
assertEquals(3, tsh.countValuesAfter(0));
assertEquals(3, tsh.size());
- //assertEquals(1, tsh.countValuesAfter(100));
+ assertEquals(1, tsh.countValuesAfter(100));
assertEquals(1, tsh.countValuesAfter(101));
assertTrue(tsh.containsValue("KEY1"));
assertTrue(tsh.containsValue("KEY2"));
@@ -37,7 +38,7 @@
tsh.push("KEY1", 200);
assertEquals(3, tsh.countValuesAfter(0));
assertEquals(3, tsh.size());
- //assertEquals(2, tsh.countValuesAfter(100));
+ assertEquals(2, tsh.countValuesAfter(100));
assertEquals(2, tsh.countValuesAfter(101));
assertTrue(tsh.containsValue("KEY1"));
assertTrue(tsh.containsValue("KEY2"));
@@ -46,7 +47,7 @@
assertTrue(tsh.removeValue("KEY1"));
assertEquals(2, tsh.countValuesAfter(0));
assertEquals(2, tsh.size());
- //assertEquals(1, tsh.countValuesAfter(100));
+ assertEquals(1, tsh.countValuesAfter(100));
assertEquals(1, tsh.countValuesAfter(101));
assertFalse(tsh.containsValue("KEY1"));
assertTrue(tsh.containsValue("KEY2"));
@@ -55,7 +56,7 @@
tsh.removeBefore(105);
assertEquals(1, tsh.countValuesAfter(0));
assertEquals(1, tsh.size());
- //assertEquals(1, tsh.countValuesAfter(100));
+ assertEquals(1, tsh.countValuesAfter(100));
assertEquals(1, tsh.countValuesAfter(101));
assertFalse(tsh.containsValue("KEY1"));
assertFalse(tsh.containsValue("KEY2"));
@@ -86,6 +87,17 @@
assertEquals(300, tsh.getTime("KEY3"));
}
+ public void testBeforeInclusive() {
+ TimeSortedHashtable<String> tsh = new
TimeSortedHashtable<String>();
+
+ tsh.push("KEY1", 100); // 100=KEY1
+ tsh.push("KEY2", 100); // 100=KEY1, 100=KEY2
+ tsh.push("KEY3", 300); // 100=KEY1, 100=KEY2, 300=KEY3
+ tsh.removeBefore(100);
+
+ assertEquals(1, tsh.size());
+ }
+
public void testPairs() {
TimeSortedHashtable<String> tsh = new
TimeSortedHashtable<String>();
_______________________________________________
cvs mailing list
[email protected]
http://emu.freenetproject.org/cgi-bin/mailman/listinfo/cvs
