From aaa6f547bab83053b50e3b1144ad6a0516bd1cf4 Mon Sep 17 00:00:00 2001 From: Matthew Khouzam Date: Fri, 26 Aug 2016 13:17:20 -0400 Subject: [PATCH] timing: Introduce new segment store for slightly out of order datasets The LazyArrayListStore is like an array list store but will only sort when a read operation is received. This structures are faster for handling segments that are out of order. Bug 500591 Change-Id: I466cc288dd42b6a6a002d0704a00e8ec06b7188b Signed-off-by: Matthew Khouzam Reviewed-on: https://git.eclipse.org/r/79877 Reviewed-by: Genevieve Bastien Tested-by: Genevieve Bastien Reviewed-by: Hudson CI --- .../tests/store/AbstractTestSegmentStore.java | 306 ++++++++++++++++++ .../core/tests/store/ArrayListStoreTest.java | 273 +--------------- .../tests/store/LazyArrayListStoreTest.java | 28 ++ .../timing/core/store/LazyArrayListStore.java | 304 +++++++++++++++++ 4 files changed, 642 insertions(+), 269 deletions(-) create mode 100644 analysis/org.eclipse.tracecompass.analysis.timing.core.tests/src/org/eclipse/tracecompass/analysis/timing/core/tests/store/AbstractTestSegmentStore.java create mode 100644 analysis/org.eclipse.tracecompass.analysis.timing.core.tests/src/org/eclipse/tracecompass/analysis/timing/core/tests/store/LazyArrayListStoreTest.java create mode 100644 analysis/org.eclipse.tracecompass.analysis.timing.core/src/org/eclipse/tracecompass/internal/analysis/timing/core/store/LazyArrayListStore.java diff --git a/analysis/org.eclipse.tracecompass.analysis.timing.core.tests/src/org/eclipse/tracecompass/analysis/timing/core/tests/store/AbstractTestSegmentStore.java b/analysis/org.eclipse.tracecompass.analysis.timing.core.tests/src/org/eclipse/tracecompass/analysis/timing/core/tests/store/AbstractTestSegmentStore.java new file mode 100644 index 0000000000..c8ec8f8647 --- /dev/null +++ b/analysis/org.eclipse.tracecompass.analysis.timing.core.tests/src/org/eclipse/tracecompass/analysis/timing/core/tests/store/AbstractTestSegmentStore.java @@ -0,0 +1,306 @@ +/******************************************************************************* + * Copyright (c) 2016 Ericsson + * + * 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.analysis.timing.core.tests.store; + +import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertTrue; + +import java.util.Arrays; +import java.util.List; + +import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.tracecompass.segmentstore.core.BasicSegment; +import org.eclipse.tracecompass.segmentstore.core.ISegment; +import org.eclipse.tracecompass.segmentstore.core.ISegmentStore; +import org.junit.After; +import org.junit.Before; +import org.junit.Test; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.Iterables; +import com.google.common.collect.Lists; + +/** + * Unit tests for intersecting elements in an SegmentStore + * + * Originally the TreeMapStoreTest, copied for this internal implementation. The + * test was barely changed as it tests the interface and not the internals. + * + * @author Matthew Khouzam + */ +public abstract class AbstractTestSegmentStore { + + private ISegmentStore<@NonNull ISegment> fSegmentStore; + + /** + * Get the segment store to test + * + * @return the segment store + */ + protected abstract ISegmentStore<@NonNull ISegment> getSegmentStore(); + + private static final @NonNull ISegment SEGMENT_2_6 = new BasicSegment(2, 6); + private static final @NonNull ISegment SEGMENT_4_6 = new BasicSegment(4, 6); + private static final @NonNull ISegment SEGMENT_4_8 = new BasicSegment(4, 8); + private static final @NonNull ISegment SEGMENT_6_8 = new BasicSegment(6, 8); + private static final @NonNull ISegment SEGMENT_10_14 = new BasicSegment(10, 14); + private static final @NonNull List<@NonNull ISegment> SEGMENTS = ImmutableList.of(SEGMENT_2_6, SEGMENT_4_6, SEGMENT_4_8, SEGMENT_6_8, SEGMENT_10_14); + private static final List<@NonNull ISegment> REVERSE_SEGMENTS = Lists.reverse(SEGMENTS); + + /** + * Constructor + */ + public AbstractTestSegmentStore() { + super(); + } + + /** + * Initialize data (test vector) that will be tested + */ + @Before + public void setup() { + fSegmentStore = getSegmentStore(); + for (ISegment segment : SEGMENTS) { + fSegmentStore.add(segment); + } + } + + /** + * Dispose of the segment store + */ + @After + public void teardown() { + fSegmentStore.dispose(); + } + + /** + * Testing method size() + */ + @Test + public void testSize() { + assertEquals(SEGMENTS.size(), fSegmentStore.size()); + } + + /** + * Test the contains() method. + */ + @Test + public void testContains() { + ISegment otherSegment = new BasicSegment(0, 20); + + assertTrue(fSegmentStore.contains(SEGMENT_2_6)); + assertTrue(fSegmentStore.contains(SEGMENT_4_8)); + assertFalse(fSegmentStore.contains(otherSegment)); + } + + /** + * Test the toArray() method. + */ + @Test + public void testToObjectArray() { + Object[] array = fSegmentStore.toArray(); + + assertEquals(SEGMENTS.size(), array.length); + assertTrue(Arrays.asList(array).containsAll(SEGMENTS)); + } + + /** + * Test the toArray(T[]) method. + */ + @Test + public void testToSpecificArray() { + ISegment[] array = fSegmentStore.toArray(new ISegment[0]); + + assertEquals(SEGMENTS.size(), array.length); + assertTrue(Arrays.asList(array).containsAll(SEGMENTS)); + } + + /** + * Test the toArray(T[]) method with a subtype of ISegment. + */ + @Test + public void testToSpecifyArraySubtype() { + ISegmentStore<@NonNull ISegment> tms2 = getSegmentStore(); + BasicSegment otherSegment = new BasicSegment(2, 6); + tms2.add(otherSegment); + BasicSegment[] array = tms2.toArray(new BasicSegment[0]); + + assertEquals(1, array.length); + assertTrue(Arrays.asList(array).contains(otherSegment)); + + tms2.dispose(); + } + + /** + * 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 */ + ISegmentStore<@NonNull ISegment> store = getSegmentStore(); + for (ISegment segment : REVERSE_SEGMENTS) { + store.add(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 + * {@link ISegmentStore#getIntersectingElements(long start, long end)} + */ + @Test + public void testGetIntersectingElementsRange() { + + Iterable intersectingElements; + + /* + * Range that does not include any segment + */ + intersectingElements = fSegmentStore.getIntersectingElements(16, 20); + assertEquals(0, Iterables.size(intersectingElements)); + + /* + * Range start time : Before first segment start time Range end time : + * After last segment end time + */ + intersectingElements = fSegmentStore.getIntersectingElements(1, 15); + assertEquals(5, Iterables.size(intersectingElements)); + + /* + * Range start time : On first segment start time Range end time : On + * last segment end time + */ + intersectingElements = fSegmentStore.getIntersectingElements(2, 14); + assertEquals(5, Iterables.size(intersectingElements)); + + /* + * 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)); + assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements)); + + /* + * Range start time : On one segment start time Range end time : On one + * segment end time + */ + intersectingElements = fSegmentStore.getIntersectingElements(10, 14); + assertEquals(1, Iterables.size(intersectingElements)); + assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements)); + + /* + * 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)); + assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements)); + + /* + * 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)); + assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements)); + } + + /** + * Testing method {@link ISegmentStore#getIntersectingElements(long time)} + */ + @Test + public void testGetIntersectingElementsTime() { + + Iterable intersectingElements; + + /* + * Time between segment start time and end time + */ + intersectingElements = fSegmentStore.getIntersectingElements(3); + assertEquals(1, Iterables.size(intersectingElements)); + assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements)); + + /* + * Time on segment start time + */ + intersectingElements = fSegmentStore.getIntersectingElements(2); + assertEquals(1, Iterables.size(intersectingElements)); + assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements)); + + /* + * Time on segment end time + */ + intersectingElements = fSegmentStore.getIntersectingElements(14); + assertEquals(1, Iterables.size(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 + */ + intersectingElements = fSegmentStore.getIntersectingElements(1); + assertEquals(0, Iterables.size(intersectingElements)); + + /* + * Time after all segment end time + */ + intersectingElements = fSegmentStore.getIntersectingElements(15); + assertEquals(0, Iterables.size(intersectingElements)); + } + + /** + * Testing method {@link ISegmentStore#dispose()} + */ + @Test + public void testDispose() { + ISegmentStore<@NonNull ISegment> store = getSegmentStore(); + store.add(SEGMENT_2_6); + store.dispose(); + assertEquals(0, store.size()); + } + +} \ No newline at end of file diff --git a/analysis/org.eclipse.tracecompass.analysis.timing.core.tests/src/org/eclipse/tracecompass/analysis/timing/core/tests/store/ArrayListStoreTest.java b/analysis/org.eclipse.tracecompass.analysis.timing.core.tests/src/org/eclipse/tracecompass/analysis/timing/core/tests/store/ArrayListStoreTest.java index 0d90553e06..0c61c6e25d 100644 --- a/analysis/org.eclipse.tracecompass.analysis.timing.core.tests/src/org/eclipse/tracecompass/analysis/timing/core/tests/store/ArrayListStoreTest.java +++ b/analysis/org.eclipse.tracecompass.analysis.timing.core.tests/src/org/eclipse/tracecompass/analysis/timing/core/tests/store/ArrayListStoreTest.java @@ -9,286 +9,21 @@ package org.eclipse.tracecompass.analysis.timing.core.tests.store; -import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull; -import static org.junit.Assert.assertEquals; -import static org.junit.Assert.assertFalse; -import static org.junit.Assert.assertTrue; - -import java.util.Arrays; -import java.util.List; - import org.eclipse.jdt.annotation.NonNull; import org.eclipse.tracecompass.internal.analysis.timing.core.store.ArrayListStore; -import org.eclipse.tracecompass.segmentstore.core.BasicSegment; import org.eclipse.tracecompass.segmentstore.core.ISegment; import org.eclipse.tracecompass.segmentstore.core.ISegmentStore; -import org.eclipse.tracecompass.segmentstore.core.treemap.TreeMapStore; -import org.junit.After; -import org.junit.Before; -import org.junit.Test; - -import com.google.common.collect.ImmutableList; -import com.google.common.collect.Iterables; -import com.google.common.collect.Lists; /** * Unit tests for intersecting elements in an ArrayListStore * - * Originally the TreeMapStoreTest, copied for this internal implementation. The - * test was barely changed as it tests the interface and not the internals. - * * @author France Lapointe Nguyen * @author Matthew Khouzam */ -public class ArrayListStoreTest { - - private ISegmentStore<@NonNull ISegment> fSegmentStore; - - private static final @NonNull ISegment SEGMENT_2_6 = new BasicSegment(2, 6); - private static final @NonNull ISegment SEGMENT_4_6 = new BasicSegment(4, 6); - private static final @NonNull ISegment SEGMENT_4_8 = new BasicSegment(4, 8); - private static final @NonNull ISegment SEGMENT_6_8 = new BasicSegment(6, 8); - private static final @NonNull ISegment SEGMENT_10_14 = new BasicSegment(10, 14); - - private static final List SEGMENTS = ImmutableList.of(SEGMENT_2_6, SEGMENT_4_6, SEGMENT_4_8, SEGMENT_6_8, SEGMENT_10_14); - private static final List REVERSE_SEGMENTS = Lists.reverse(SEGMENTS); - - /** - * Initialize data (test vector) that will be tested - */ - @Before - public void setup() { - fSegmentStore = new ArrayListStore<>(); - for (ISegment segment : SEGMENTS) { - fSegmentStore.add(checkNotNull(segment)); - } - } - - /** - * Dispose of the segment store - */ - @After - public void teardown() { - fSegmentStore.dispose(); - } - - /** - * Testing method size() - */ - @Test - public void testSize() { - assertEquals(SEGMENTS.size(), fSegmentStore.size()); - } - - /** - * Test the contains() method. - */ - @Test - public void testContains() { - ISegment otherSegment = new BasicSegment(0, 20); - - assertTrue(fSegmentStore.contains(SEGMENT_2_6)); - assertTrue(fSegmentStore.contains(SEGMENT_4_8)); - assertFalse(fSegmentStore.contains(otherSegment)); - } - - /** - * Test the toArray() method. - */ - @Test - public void testToObjectArray() { - Object[] array = fSegmentStore.toArray(); - - assertEquals(SEGMENTS.size(), array.length); - assertTrue(Arrays.asList(array).containsAll(SEGMENTS)); - } - - /** - * Test the toArray(T[]) method. - */ - @Test - public void testToSpecificArray() { - ISegment[] array = fSegmentStore.toArray(new ISegment[0]); - - assertEquals(SEGMENTS.size(), array.length); - assertTrue(Arrays.asList(array).containsAll(SEGMENTS)); - } - - /** - * Test the toArray(T[]) method with a subtype of ISegment. - */ - @Test - public void testToSpecifyArraySubtype() { - TreeMapStore<@NonNull BasicSegment> tms2 = new TreeMapStore<>(); - BasicSegment otherSegment = new BasicSegment(2, 6); - tms2.add(otherSegment); - BasicSegment[] array = tms2.toArray(new BasicSegment[0]); - - assertEquals(1, array.length); - assertTrue(Arrays.asList(array).contains(otherSegment)); - - tms2.dispose(); - } - - /** - * 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<@NonNull ISegment> store = new TreeMapStore<>(); - for (ISegment segment : REVERSE_SEGMENTS) { - store.add(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) - */ - @Test - public void testGetIntersectingElementsRange() { - - Iterable intersectingElements; - - /* - * Range that does not include any segment - */ - intersectingElements = fSegmentStore.getIntersectingElements(16, 20); - assertEquals(0, Iterables.size(intersectingElements)); - - /* - * Range start time : Before first segment start time Range end time : - * After last segment end time - */ - intersectingElements = fSegmentStore.getIntersectingElements(1, 15); - assertEquals(5, Iterables.size(intersectingElements)); - - /* - * Range start time : On first segment start time Range end time : On - * last segment end time - */ - intersectingElements = fSegmentStore.getIntersectingElements(2, 14); - assertEquals(5, Iterables.size(intersectingElements)); - - /* - * 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)); - assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements)); - - /* - * Range start time : On one segment start time Range end time : On one - * segment end time - */ - intersectingElements = fSegmentStore.getIntersectingElements(10, 14); - assertEquals(1, Iterables.size(intersectingElements)); - assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements)); - - /* - * 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)); - assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements)); - - /* - * 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)); - assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements)); - } - - /** - * Testing method getIntersectingElements(long start, long end) - */ - @Test - public void testGetIntersectingElementsTime() { - - Iterable intersectingElements; - - /* - * Time between segment start time and end time - */ - intersectingElements = fSegmentStore.getIntersectingElements(3); - assertEquals(1, Iterables.size(intersectingElements)); - assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements)); - - /* - * Time on segment start time - */ - intersectingElements = fSegmentStore.getIntersectingElements(2); - assertEquals(1, Iterables.size(intersectingElements)); - assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements)); - - /* - * Time on segment end time - */ - intersectingElements = fSegmentStore.getIntersectingElements(14); - assertEquals(1, Iterables.size(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 - */ - intersectingElements = fSegmentStore.getIntersectingElements(1); - assertEquals(0, Iterables.size(intersectingElements)); - - /* - * Time after all segment end time - */ - intersectingElements = fSegmentStore.getIntersectingElements(15); - assertEquals(0, Iterables.size(intersectingElements)); - } +public class ArrayListStoreTest extends AbstractTestSegmentStore { - /** - * Testing method getIntersectingElements(long start, long end) - */ - @Test - public void testDispose() { - TreeMapStore<@NonNull ISegment> store = new TreeMapStore<>(); - store.add(SEGMENT_2_6); - store.dispose(); - assertEquals(0, store.size()); + @Override + protected ISegmentStore<@NonNull ISegment> getSegmentStore() { + return new ArrayListStore<>(); } } \ No newline at end of file diff --git a/analysis/org.eclipse.tracecompass.analysis.timing.core.tests/src/org/eclipse/tracecompass/analysis/timing/core/tests/store/LazyArrayListStoreTest.java b/analysis/org.eclipse.tracecompass.analysis.timing.core.tests/src/org/eclipse/tracecompass/analysis/timing/core/tests/store/LazyArrayListStoreTest.java new file mode 100644 index 0000000000..1c99a5b1c4 --- /dev/null +++ b/analysis/org.eclipse.tracecompass.analysis.timing.core.tests/src/org/eclipse/tracecompass/analysis/timing/core/tests/store/LazyArrayListStoreTest.java @@ -0,0 +1,28 @@ +/******************************************************************************* + * Copyright (c) 2016 Ericsson + * + * 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.analysis.timing.core.tests.store; + +import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.tracecompass.internal.analysis.timing.core.store.LazyArrayListStore; +import org.eclipse.tracecompass.segmentstore.core.ISegment; +import org.eclipse.tracecompass.segmentstore.core.ISegmentStore; + +/** + * Unit tests for intersecting elements in an LazyArrayListStore + * + * @author Matthew Khouzam + */ +public class LazyArrayListStoreTest extends AbstractTestSegmentStore { + + @Override + protected ISegmentStore<@NonNull ISegment> getSegmentStore() { + return new LazyArrayListStore<>(); + } +} \ No newline at end of file diff --git a/analysis/org.eclipse.tracecompass.analysis.timing.core/src/org/eclipse/tracecompass/internal/analysis/timing/core/store/LazyArrayListStore.java b/analysis/org.eclipse.tracecompass.analysis.timing.core/src/org/eclipse/tracecompass/internal/analysis/timing/core/store/LazyArrayListStore.java new file mode 100644 index 0000000000..e5de0a7258 --- /dev/null +++ b/analysis/org.eclipse.tracecompass.analysis.timing.core/src/org/eclipse/tracecompass/internal/analysis/timing/core/store/LazyArrayListStore.java @@ -0,0 +1,304 @@ +/******************************************************************************* + * Copyright (c) 2016 Ericsson + * + * 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.internal.analysis.timing.core.store; + +import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Comparator; +import java.util.Iterator; +import java.util.List; +import java.util.concurrent.locks.ReentrantLock; +import java.util.stream.Collectors; + +import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.jdt.annotation.Nullable; +import org.eclipse.tracecompass.segmentstore.core.ISegment; +import org.eclipse.tracecompass.segmentstore.core.ISegmentStore; + +import com.google.common.collect.ImmutableList; + +/** + * Implementation of an {@link ISegmentStore} using one in-memory + * {@link ArrayList}. This relatively simple implementation holds everything in + * memory, and as such cannot contain too much data. + * + * The LazyArrayListStore itself is {@link 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}). + * + * This structure sorts in a lazy way to allow faster insertions. However, if + * the structure is out of order, the next read (getting intersecting elements, + * iterating...) will perform a sort. It may have inconsistent performance, but + * should be faster at building when receiving shuffled datasets than the + * {@link ArrayListStore}. + * + * Removal operations are not supported. + * + * @param + * The type of segment held in this store + * + * @author Matthew Khouzam + */ +public class LazyArrayListStore<@NonNull E extends ISegment> implements ISegmentStore { + + private static final String ERROR_MESSAGE = "Cannot remove from a segment store"; //$NON-NLS-1$ + + private final Comparator COMPARATOR = (o1, o2) -> { + int ret = Long.compare(o1.getStart(), o2.getStart()); + if (ret == 0) { + return Long.compare(o1.getEnd(), o2.getEnd()); + } + return ret; + }; + + private final ReentrantLock fLock = new ReentrantLock(false); + + private final @NonNull List fStore = new ArrayList<>(); + + private @Nullable transient Iterable fLastSnapshot = null; + + private volatile boolean fDirty = false; + + /** + * Constructor + */ + public LazyArrayListStore() { + // do nothing + } + + /** + * Constructor + * + * @param array + * an array of elements to wrap in the segment store + * + */ + public LazyArrayListStore(Object[] array) { + for (int i = 0; i < array.length; i++) { + if (array[i] instanceof ISegment) { + E element = (E) array[i]; + setDirtyIfNeeded(element); + fStore.add(element); + } + } + if (fDirty) { + sortStore(); + } + } + + private void setDirtyIfNeeded(@NonNull E value) { + if (!fStore.isEmpty() && COMPARATOR.compare(fStore.get(size() - 1), value) > 0) { + fDirty = true; + } + } + // ------------------------------------------------------------------------ + // Methods from Collection + // ------------------------------------------------------------------------ + + @Override + public Iterator iterator() { + fLock.lock(); + try { + if (fDirty) { + sortStore(); + } + Iterable lastSnapshot = fLastSnapshot; + if (lastSnapshot == null) { + lastSnapshot = ImmutableList.copyOf(fStore); + fLastSnapshot = lastSnapshot; + } + return checkNotNull(lastSnapshot.iterator()); + } finally { + fLock.unlock(); + } + } + + /** + * DO NOT CALL FROM OUTSIDE OF A LOCK! + */ + private void sortStore() { + fStore.sort(COMPARATOR); + fDirty = false; + } + + @Override + public boolean add(@Nullable E val) { + if (val == null) { + throw new IllegalArgumentException("Cannot add null value"); //$NON-NLS-1$ + } + + fLock.lock(); + try { + setDirtyIfNeeded(val); + fStore.add(val); + fLastSnapshot = null; + return true; + } finally { + fLock.unlock(); + } + } + + @Override + public int size() { + return fStore.size(); + } + + @Override + public boolean isEmpty() { + fLock.lock(); + try { + return fStore.isEmpty(); + } finally { + fLock.unlock(); + } + } + + @Override + public boolean contains(@Nullable Object o) { + fLock.lock(); + try { + return fStore.contains(o); + } finally { + fLock.unlock(); + } + } + + @Override + public boolean containsAll(@Nullable Collection c) { + fLock.lock(); + try { + return fStore.containsAll(c); + } finally { + fLock.unlock(); + } + } + + @Override + public Object[] toArray() { + fLock.lock(); + try { + if (fDirty) { + sortStore(); + } + return fStore.toArray(); + } finally { + fLock.unlock(); + } + } + + @Override + public T[] toArray(T[] a) { + fLock.lock(); + try { + if (fDirty) { + sortStore(); + } + return fStore.toArray(a); + } finally { + fLock.unlock(); + } + } + + @Override + public boolean addAll(@Nullable Collection c) { + if (c == null) { + throw new IllegalArgumentException(); + } + + fLock.lock(); + try { + boolean changed = false; + for (E elem : c) { + if (add(elem)) { + changed = true; + } + } + return changed; + } finally { + fLock.unlock(); + } + } + + @Override + public boolean removeAll(@Nullable Collection c) { + throw new UnsupportedOperationException(ERROR_MESSAGE); + } + + @Override + public boolean retainAll(@Nullable Collection c) { + throw new UnsupportedOperationException(ERROR_MESSAGE); + } + + @Override + public boolean remove(@Nullable Object o) { + throw new UnsupportedOperationException(ERROR_MESSAGE); + } + + @Override + public void clear() { + fLock.lock(); + try { + fStore.clear(); + fLastSnapshot = null; + fDirty = false; + } finally { + fLock.unlock(); + } + } + + // ------------------------------------------------------------------------ + // Methods added by ISegmentStore + // ------------------------------------------------------------------------ + + @Override + public Iterable getIntersectingElements(long position) { + fLock.lock(); + if (fDirty) { + sortStore(); + } + /* + * The intervals intersecting 't' are those whose 1) start time is + * *lower* than 't' AND 2) end time is *higher* than 't'. + */ + try { + return fStore.stream().filter(element -> position >= element.getStart() && position <= element.getEnd()).collect(Collectors.toList()); + } finally { + fLock.unlock(); + } + } + + @Override + public Iterable getIntersectingElements(long start, long end) { + fLock.lock(); + if (fDirty) { + sortStore(); + } + try { + return fStore.stream().filter(element -> !(start > element.getEnd() || end < element.getStart())).collect(Collectors.toList()); + } finally { + fLock.unlock(); + } + } + + @Override + public void dispose() { + fLock.lock(); + try { + fStore.clear(); + fDirty = false; + } finally { + fLock.unlock(); + } + } +} -- 2.34.1