package org.eclipse.tracecompass.segmentstore.core.tests.treemap;
+import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
import static org.junit.Assert.assertEquals;
import java.util.List;
-import org.eclipse.tracecompass.common.core.NonNullUtils;
import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
import org.eclipse.tracecompass.segmentstore.core.ISegment;
import org.eclipse.tracecompass.segmentstore.core.treemap.TreeMapStore;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
/**
* Unit tests for intersecting elements in a TreeMapStore
private TreeMapStore<ISegment> fSegmentStore;
- private static final ISegment SEGMENT_2_4 = new BasicSegment(2, 4);
+ private static final ISegment SEGMENT_2_6 = new BasicSegment(2, 6);
+ private static final ISegment SEGMENT_4_6 = new BasicSegment(4, 6);
+ private static final ISegment SEGMENT_4_8 = new BasicSegment(4, 8);
private static final ISegment SEGMENT_6_8 = new BasicSegment(6, 8);
private static final ISegment SEGMENT_10_14 = new BasicSegment(10, 14);
- private static final List<ISegment> SEGMENTS = ImmutableList.of(SEGMENT_2_4, SEGMENT_6_8, SEGMENT_10_14);
+ private static final List<ISegment> SEGMENTS = ImmutableList.of(SEGMENT_2_6, SEGMENT_4_6, SEGMENT_4_8, SEGMENT_6_8, SEGMENT_10_14);
+ private static final List<ISegment> REVERSE_SEGMENTS = Lists.reverse(SEGMENTS);
/**
* Initialize data (test vector) that will be tested
@Before
public void setup() {
fSegmentStore = new TreeMapStore<>();
- for (int i = 0; i < SEGMENTS.size(); i++) {
- fSegmentStore.addElement(NonNullUtils.checkNotNull(SEGMENTS.get(i)));
+ for (ISegment segment : SEGMENTS) {
+ fSegmentStore.addElement(checkNotNull(segment));
}
}
}
/**
- * Testing method getElementAtIndex
+ * Try adding duplicate elements, they should be ignored
*/
@Test
- public void testGetElementAtIndex() {
- for (int i = 0; i < SEGMENTS.size(); i++) {
- assertEquals(SEGMENTS.get(i), fSegmentStore.getElementAtIndex(i));
+ public void testNoDuplicateElements() {
+ for (ISegment segment : SEGMENTS) {
+ fSegmentStore.addElement(new BasicSegment(segment.getStart(), segment.getEnd()));
+ }
+ assertEquals(SEGMENTS.size(), fSegmentStore.getNbElements());
+ }
+
+ /**
+ * Test the iteration order of the complete segment store.
+ */
+ @Test
+ public void testIterationOrder() {
+ int i = 0;
+ for (ISegment segment : fSegmentStore) {
+ assertEquals(SEGMENTS.get(i++), segment);
}
}
+ /**
+ * Test the iteration order when the elements are not inserted in sorted
+ * order.
+ */
+ @Test
+ public void testIterationOrderNonSortedInsertion() {
+ /* Prepare the segment store, we don't use the 'fixture' in this test */
+ TreeMapStore<ISegment> store = new TreeMapStore<>();
+ for (ISegment segment : REVERSE_SEGMENTS) {
+ store.addElement(checkNotNull(segment));
+ }
+
+ /*
+ * Test each element one by one, the iteration order should follow the
+ * start times, not the insertion order.
+ */
+ int i = 0;
+ for (ISegment segment : store) {
+ assertEquals(SEGMENTS.get(i++), segment);
+ }
+
+ /* Manually dispose our own store */
+ store.dispose();
+ }
+
/**
* Testing method getIntersectingElements(long start, long end)
*/
assertEquals(0, Iterables.size(intersectingElements));
/*
- * Range start time : Before first segment start time Range end time :
- * After last segment end time
+ * Range start time : Before first segment start time
+ * Range end time : After last segment end time
*/
intersectingElements = fSegmentStore.getIntersectingElements(1, 15);
- assertEquals(3, Iterables.size(intersectingElements));
+ assertEquals(5, Iterables.size(intersectingElements));
/*
- * Range start time : On first segment start time Range end time : On
- * last segment end time
+ * Range start time : On first segment start time
+ * Range end time : On last segment end time
*/
intersectingElements = fSegmentStore.getIntersectingElements(2, 14);
- assertEquals(3, Iterables.size(intersectingElements));
+ assertEquals(5, Iterables.size(intersectingElements));
/*
- * Range start time : After one segment start time Range end time :
- * Before one segment end time
+ * Range start time : After one segment start time
+ * Range end time : Before one segment end time
*/
intersectingElements = fSegmentStore.getIntersectingElements(11, 13);
assertEquals(1, Iterables.size(intersectingElements));
- assert (SEGMENT_10_14.equals(intersectingElements));
+ assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
/*
- * Range start time : On one segment start time Range end time : On one
- * segment end time
+ * Range start time : On one segment start time
+ * Range end time : On one segment end time
*/
- intersectingElements = fSegmentStore.getIntersectingElements(6, 8);
+ intersectingElements = fSegmentStore.getIntersectingElements(10, 14);
assertEquals(1, Iterables.size(intersectingElements));
- assert (SEGMENT_6_8.equals(intersectingElements));
+ assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
/*
- * Range start time : On last segment end time Range end time : After
- * last segment end time
+ * Range start time : On last segment end time
+ * Range end time : After last segment end time
*/
intersectingElements = fSegmentStore.getIntersectingElements(14, 18);
assertEquals(1, Iterables.size(intersectingElements));
- assert (SEGMENT_10_14.equals(intersectingElements));
+ assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
/*
- * Range start time : Before first segment start time Range end time :
- * On first segment start time
+ * Range start time : Before first segment start time
+ * Range end time : On first segment start time
*/
intersectingElements = fSegmentStore.getIntersectingElements(1, 2);
assertEquals(1, Iterables.size(intersectingElements));
- assert (SEGMENT_2_4.equals(intersectingElements));
+ assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
}
/**
*/
intersectingElements = fSegmentStore.getIntersectingElements(3);
assertEquals(1, Iterables.size(intersectingElements));
- assert (SEGMENT_2_4.equals(intersectingElements));
+ assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
/*
* Time on segment start time
*/
intersectingElements = fSegmentStore.getIntersectingElements(2);
assertEquals(1, Iterables.size(intersectingElements));
- assert (SEGMENT_2_4.equals(intersectingElements));
+ assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
/*
* Time on segment end time
*/
- intersectingElements = fSegmentStore.getIntersectingElements(4);
+ intersectingElements = fSegmentStore.getIntersectingElements(14);
assertEquals(1, Iterables.size(intersectingElements));
- assert (SEGMENT_2_4.equals(intersectingElements));
+ assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
+
+ /*
+ * Time overlapping many segments
+ */
+ intersectingElements = fSegmentStore.getIntersectingElements(6);
+ assertEquals(4, Iterables.size(intersectingElements));
+
+ /*
+ * Time between segments
+ */
+ intersectingElements = fSegmentStore.getIntersectingElements(9);
+ assertEquals(0, Iterables.size(intersectingElements));
/*
* Time before all segment start time
@Test
public void testDispose() {
TreeMapStore<ISegment> store = new TreeMapStore<>();
- store.addElement(NonNullUtils.checkNotNull(SEGMENT_2_4));
+ store.addElement(checkNotNull(SEGMENT_2_6));
store.dispose();
assertEquals(0, store.getNbElements());
}
package org.eclipse.tracecompass.segmentstore.core;
+import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
+
+import java.util.Comparator;
+
+import org.eclipse.jdt.annotation.Nullable;
+
+import com.google.common.collect.Ordering;
+
/**
* Basic implementation of {@link ISegment}.
*
private static final long serialVersionUID = -3257452887960883177L;
+ private static final Comparator<ISegment> COMPARATOR = checkNotNull(Ordering
+ .from(SegmentComparators.INTERVAL_START_COMPARATOR)
+ .compound(SegmentComparators.INTERVAL_END_COMPARATOR));
+
private final long fStart;
private final long fEnd;
return (fEnd - fStart);
}
+ @Override
+ public int compareTo(@Nullable ISegment o) {
+ if (o == null) {
+ throw new IllegalArgumentException();
+ }
+ return COMPARATOR.compare(this, o);
+ }
+
@Override
public String toString() {
return new String('[' + String.valueOf(fStart) + ", " + String.valueOf(fEnd) + ']'); //$NON-NLS-1$
}
-
}
*
* @author Alexandre Montplaisir
*/
-public interface ISegment extends Serializable {
+public interface ISegment extends Serializable, Comparable<ISegment> {
/**
* The start position/time of the segment.
*/
long getNbElements();
- /**
- * To seek rapidly among all elements, the elements should be indexed by
- * their ascending order of start times.
- *
- * This method returns an individual element, given a position in this
- * index.
- *
- * @param index
- * Retrieve the element at this index
- * @return The element at this index
- */
- T getElementAtIndex(long index);
-
/**
* Retrieve all elements that inclusively cross the given position.
*
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2015 EfficiOS Inc., Alexandre Montplaisir
+ *
+ * All rights reserved. This program and the accompanying materials are
+ * made available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.segmentstore.core;
+
+import java.util.Comparator;
+
+import org.eclipse.jdt.annotation.Nullable;
+
+/**
+ * Segments comparators. These do not allow for null arguments.
+ *
+ * @author Alexandre Montplaisir
+ * @noimplement This interface only contains static definitions.
+ */
+public interface SegmentComparators {
+
+ /**
+ * Basic long comparator
+ */
+ Comparator<Long> LONG_COMPARATOR = new Comparator<Long>() {
+ @Override
+ public int compare(@Nullable Long o1, @Nullable Long o2) {
+ if (o1 == null || o2 == null) {
+ throw new IllegalArgumentException();
+ }
+ return o1.compareTo(o2);
+ }
+ };
+
+ /**
+ * Start time comparator
+ */
+ Comparator<ISegment> INTERVAL_START_COMPARATOR = new Comparator<ISegment>() {
+ @Override
+ public int compare(@Nullable ISegment o1, @Nullable ISegment o2) {
+ if (o1 == null || o2 == null) {
+ throw new IllegalArgumentException();
+ }
+ return Long.compare(o1.getStart(), o2.getStart());
+ }
+ };
+
+ /**
+ * End time comparator
+ */
+ Comparator<ISegment> INTERVAL_END_COMPARATOR = new Comparator<ISegment>() {
+ @Override
+ public int compare(@Nullable ISegment o1, @Nullable ISegment o2) {
+ if (o1 == null || o2 == null) {
+ throw new IllegalArgumentException();
+ }
+ return Long.compare(o1.getEnd(), o2.getEnd());
+ }
+ };
+
+ /**
+ * Length comparator
+ */
+ Comparator<ISegment> INTERVAL_LENGTH_COMPARATOR = new Comparator<ISegment>() {
+ @Override
+ public int compare(@Nullable ISegment o1, @Nullable ISegment o2) {
+ if (o1 == null || o2 == null) {
+ throw new IllegalArgumentException();
+ }
+ return Long.compare(o1.getLength(), o2.getLength());
+ }
+ };
+
+}
/*******************************************************************************
- * Copyright (c) 2015 EfficiOS Inc., Alexandre Montplaisir
+ * Copyright (c) 2015 EfficiOS Inc., Alexandre Montplaisir and others.
*
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
-import java.util.Comparator;
-import java.util.HashMap;
import java.util.Iterator;
-import java.util.Map;
import java.util.TreeMap;
-import org.eclipse.jdt.annotation.Nullable;
import org.eclipse.tracecompass.segmentstore.core.ISegment;
import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
+import org.eclipse.tracecompass.segmentstore.core.SegmentComparators;
import com.google.common.collect.Iterables;
+import com.google.common.collect.Ordering;
import com.google.common.collect.Sets;
import com.google.common.collect.TreeMultimap;
* This relatively simple implementation holds everything in memory, and as such
* cannot contain too much data.
*
+ * The TreeMapStore itself is Iterable, and its iteration order will be by
+ * ascending order of start times. For segments with identical start times, the
+ * secondary comparator will be the end time. If even those are equal, it will
+ * defer to the segments' natural ordering ({@link ISegment#compareTo}).
+ *
+ * The store's tree maps will not accept duplicate key-value pairs, which means
+ * that if you want several segments with the same start and end times, make
+ * sure their compareTo() differentiates them.
+ *
* @param <T>
- * The time of time range held
+ * The type of segment held in this store
*
* @author Alexandre Montplaisir
*/
private final TreeMultimap<Long, T> fStartTimesIndex;
private final TreeMultimap<Long, T> fEndTimesIndex;
- private final Map<Long, T> fPositionMap;
-
private volatile long fSize;
/**
- *Constructor
+ * Constructor
*/
public TreeMapStore() {
- fStartTimesIndex = checkNotNull(TreeMultimap.<Long, T> create(LONG_COMPARATOR, INTERVAL_START_COMPARATOR));
- fEndTimesIndex = checkNotNull(TreeMultimap.<Long, T> create(LONG_COMPARATOR, INTERVAL_END_COMPARATOR));
- fPositionMap = new HashMap<>();
+ /*
+ * For the start times index, the "key comparator" will compare the
+ * start times as longs directly. This is the primary comparator for its
+ * tree map.
+ *
+ * The secondary "value" comparator will check the end times first, and
+ * in the event of a tie, defer to the ISegment's Comparable
+ * implementation, a.k.a. its natural ordering.
+ *
+ * The same is done for the end times index, but swapping the first two
+ * comparators instead.
+ */
+ fStartTimesIndex = checkNotNull(TreeMultimap.<Long, T> create(
+ SegmentComparators.LONG_COMPARATOR,
+ Ordering.from(SegmentComparators.INTERVAL_END_COMPARATOR).compound(Ordering.natural())));
+
+ fEndTimesIndex = checkNotNull(TreeMultimap.<Long, T> create(
+ SegmentComparators.LONG_COMPARATOR,
+ Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR).compound(Ordering.natural())));
+
fSize = 0;
}
@Override
public synchronized void addElement(T val) {
- fStartTimesIndex.put(Long.valueOf(val.getStart()), val);
- fEndTimesIndex.put(Long.valueOf(val.getEnd()), val);
- fPositionMap.put(fSize, val);
- fSize++;
+ if (fStartTimesIndex.put(Long.valueOf(val.getStart()), val)) {
+ fEndTimesIndex.put(Long.valueOf(val.getEnd()), val);
+ fSize++;
+ }
}
@Override
return fSize;
}
- @Override
- public T getElementAtIndex(long index) {
- return checkNotNull(fPositionMap.get(Long.valueOf(index)));
- }
-
@Override
public Iterable<T> getIntersectingElements(long position) {
/*
public synchronized void dispose() {
fStartTimesIndex.clear();
fEndTimesIndex.clear();
- fPositionMap.clear();
fSize = 0;
}
-
- // ------------------------------------------------------------------------
- // Comparators, used for the tree maps
- // ------------------------------------------------------------------------
-
- private static final Comparator<Long> LONG_COMPARATOR = new Comparator<Long>() {
- @Override
- public int compare(@Nullable Long o1, @Nullable Long o2) {
- if (o1 == null || o2 == null) {
- throw new IllegalArgumentException();
- }
- return o1.compareTo(o2);
- }
- };
-
- private static final Comparator<ISegment> INTERVAL_START_COMPARATOR = new Comparator<ISegment>() {
- @Override
- public int compare(@Nullable ISegment o1, @Nullable ISegment o2) {
- if (o1 == null || o2 == null) {
- throw new IllegalArgumentException();
- }
- return Long.compare(o1.getStart(), o2.getStart());
- }
- };
-
- private static final Comparator<ISegment> INTERVAL_END_COMPARATOR = new Comparator<ISegment>() {
- @Override
- public int compare(@Nullable ISegment o1, @Nullable ISegment o2) {
- if (o1 == null || o2 == null) {
- throw new IllegalArgumentException();
- }
- return Long.compare(o1.getEnd(), o2.getEnd());
- }
- };
-
-
}
projects / deliverable / tracecompass.git / commitdiff
