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>();
lmpx.com only provides a reader for public news (NNTP) servers. It is not
affiliated with the servers or forums shown here and is not responsible for
the content of articles, which is written by their respective authors.