statesystem/org.eclipse.tracecompass.segmentstore.core.tests/src/org/eclipse/tracecompass/segmentstore/core/tests/AbstractTestSegmentStore.java

   1 /*******************************************************************************
   2  * Copyright (c) 2016 Ericsson
   3  *
   4  * All rights reserved. This program and the accompanying materials are
   5  * made available under the terms of the Eclipse Public License v1.0 which
   6  * accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *******************************************************************************/
   9
  10 package org.eclipse.tracecompass.segmentstore.core.tests;
  11
  12 import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
  13 import static org.junit.Assert.assertEquals;
  14 import static org.junit.Assert.assertFalse;
  15 import static org.junit.Assert.assertTrue;
  16
  17 import java.util.ArrayList;
  18 import java.util.Arrays;
  19 import java.util.Collection;
  20 import java.util.Collections;
  21 import java.util.Comparator;
  22 import java.util.Iterator;
  23 import java.util.LinkedList;
  24 import java.util.List;
  25
  26 import org.eclipse.jdt.annotation.NonNull;
  27 import org.eclipse.tracecompass.common.core.NonNullUtils;
  28 import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
  29 import org.eclipse.tracecompass.segmentstore.core.ISegment;
  30 import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
  31 import org.eclipse.tracecompass.segmentstore.core.SegmentComparators;
  32 import org.junit.After;
  33 import org.junit.Before;
  34 import org.junit.Test;
  35
  36 import com.google.common.collect.ImmutableList;
  37 import com.google.common.collect.Iterables;
  38 import com.google.common.collect.Lists;
  39
  40 /**
  41  * Unit tests for intersecting elements in an SegmentStore
  42  *
  43  * Originally the TreeMapStoreTest, copied for this internal implementation. The
  44  * test was barely changed as it tests the interface and not the internals.
  45  *
  46  * @author Matthew Khouzam
  47  */
  48 public abstract class AbstractTestSegmentStore {
  49
  50     /**
  51      * The segment store
  52      */
  53     protected ISegmentStore<@NonNull ISegment> fSegmentStore;
  54
  55     /**
  56      * Get the segment store to test
  57      *
  58      * @return the segment store
  59      */
  60     protected abstract ISegmentStore<@NonNull ISegment> getSegmentStore();
  61
  62     /**
  63      * Get the segment store to test with initial data
  64      *
  65      * @param data
  66      *            the data
  67      *
  68      * @return the segment store
  69      */
  70     protected abstract ISegmentStore<@NonNull ISegment> getSegmentStore(@NonNull ISegment @NonNull [] data);
  71
  72     private static final @NonNull ISegment SEGMENT_2_6 = new BasicSegment(2, 6);
  73     private static final @NonNull ISegment SEGMENT_4_6 = new BasicSegment(4, 6);
  74     private static final @NonNull ISegment SEGMENT_4_8 = new BasicSegment(4, 8);
  75     private static final @NonNull ISegment SEGMENT_6_8 = new BasicSegment(6, 8);
  76     private static final @NonNull ISegment SEGMENT_10_14 = new BasicSegment(10, 14);
  77     /**
  78      * A sample segment list
  79      */
  80     protected static final List<@NonNull ISegment> SEGMENTS = ImmutableList.of(SEGMENT_2_6, SEGMENT_4_6, SEGMENT_4_8, SEGMENT_6_8, SEGMENT_10_14);
  81     private static final List<@NonNull ISegment> REVERSE_SEGMENTS = Lists.reverse(SEGMENTS);
  82
  83     /**
  84      * Constructor
  85      */
  86     public AbstractTestSegmentStore() {
  87         super();
  88     }
  89
  90     /**
  91      * Initialize data (test vector) that will be tested
  92      */
  93     @Before
  94     public void setup() {
  95         fSegmentStore = getSegmentStore();
  96         for (ISegment segment : SEGMENTS) {
  97             fSegmentStore.add(segment);
  98         }
  99     }
 100
 101     /**
 102      * Dispose of the segment store
 103      */
 104     @After
 105     public void teardown() {
 106         fSegmentStore.dispose();
 107     }
 108
 109     /**
 110      * Testing method size()
 111      */
 112     @Test
 113     public void testSize() {
 114         assertEquals(SEGMENTS.size(), fSegmentStore.size());
 115     }
 116
 117     /**
 118      * Testing isEmpty() method
 119      */
 120     @Test
 121     public void testIsEmpty() {
 122         assertFalse(fSegmentStore.isEmpty());
 123         fSegmentStore.clear();
 124         assertTrue(fSegmentStore.isEmpty());
 125     }
 126
 127     /**
 128      * Testing adding a collection with the addAll method
 129      */
 130     @Test
 131     public void testAddAll() {
 132         assertFalse(fSegmentStore.isEmpty());
 133         fSegmentStore.clear();
 134         assertTrue(fSegmentStore.isEmpty());
 135         fSegmentStore.addAll(SEGMENTS);
 136         assertTrue(fSegmentStore.containsAll(SEGMENTS));
 137     }
 138
 139     /**
 140      * Testing "copy" constructor
 141      */
 142     @Test
 143     public void testAddAllConstructor() {
 144         @SuppressWarnings("null")
 145         ISegmentStore<@NonNull ISegment> other = getSegmentStore(fSegmentStore.toArray(new ISegment[fSegmentStore.size()]));
 146         assertTrue(fSegmentStore.containsAll(other));
 147         assertTrue(other.containsAll(fSegmentStore));
 148     }
 149
 150     /**
 151      * Testing "copy" constructor out of order
 152      */
 153     @Test
 154     public void testAddAllConstructorOutOfOrder() {
 155         @SuppressWarnings("null")
 156         ISegmentStore<@NonNull ISegment> other = getSegmentStore(REVERSE_SEGMENTS.toArray(new ISegment[fSegmentStore.size()]));
 157         assertTrue(fSegmentStore.containsAll(other));
 158         assertTrue(other.containsAll(fSegmentStore));
 159     }
 160
 161     /**
 162      * Testing adding an out of order collection with the addAll method
 163      */
 164     @Test
 165     public void testAddAllOutOfOrder() {
 166         assertFalse(fSegmentStore.isEmpty());
 167         fSegmentStore.clear();
 168         assertTrue(fSegmentStore.isEmpty());
 169         fSegmentStore.addAll(REVERSE_SEGMENTS);
 170         assertTrue(fSegmentStore.containsAll(SEGMENTS));
 171     }
 172
 173     /**
 174      * Test the contains() method.
 175      */
 176     @Test
 177     public void testContains() {
 178         ISegment otherSegment = new BasicSegment(0, 20);
 179
 180         assertTrue(fSegmentStore.contains(SEGMENT_2_6));
 181         assertTrue(fSegmentStore.contains(SEGMENT_4_8));
 182         assertFalse(fSegmentStore.contains(otherSegment));
 183     }
 184
 185     /**
 186      * Test containsAll() method
 187      */
 188     public void testContainsAll() {
 189         ISegmentStore<@NonNull ISegment> store = getSegmentStore();
 190
 191         store.add(SEGMENT_2_6);
 192         assertTrue(store.containsAll(Collections.emptyList()));
 193         assertTrue(store.containsAll(Collections.singleton(SEGMENT_2_6)));
 194         assertFalse(store.containsAll(Collections.singleton(SEGMENT_4_6)));
 195     }
 196
 197     /**
 198      * Test the toArray() method.
 199      */
 200     @Test
 201     public void testToObjectArray() {
 202         Object[] array = fSegmentStore.toArray();
 203
 204         assertEquals(SEGMENTS.size(), array.length);
 205         assertTrue(Arrays.asList(array).containsAll(SEGMENTS));
 206     }
 207
 208     /**
 209      * Test the toArray(T[]) method.
 210      */
 211     @Test
 212     public void testToSpecificArray() {
 213         ISegment[] array = fSegmentStore.toArray(new ISegment[0]);
 214
 215         assertEquals(SEGMENTS.size(), array.length);
 216         assertTrue(Arrays.asList(array).containsAll(SEGMENTS));
 217     }
 218
 219     /**
 220      * Test the toArray(T[]) method with a subtype of ISegment.
 221      */
 222     @Test
 223     public void testToSpecifyArraySubtype() {
 224         ISegmentStore<@NonNull ISegment> tms2 = getSegmentStore();
 225         BasicSegment otherSegment = new BasicSegment(2, 6);
 226         tms2.add(otherSegment);
 227         BasicSegment[] array = tms2.toArray(new BasicSegment[0]);
 228
 229         assertEquals(1, array.length);
 230         assertTrue(Arrays.asList(array).contains(otherSegment));
 231
 232         tms2.dispose();
 233     }
 234
 235     /**
 236      * Test the iteration order of the complete segment store.
 237      */
 238     @Test
 239     public void testIterationOrder() {
 240         int i = 0;
 241         for (ISegment segment : fSegmentStore) {
 242             assertEquals(SEGMENTS.get(i++), segment);
 243         }
 244     }
 245
 246     /**
 247      * Test the iteration order when the elements are not inserted in sorted
 248      * order.
 249      */
 250     @Test
 251     public void testIterationOrderNonSortedInsertion() {
 252         /* Prepare the segment store, we don't use the 'fixture' in this test */
 253         ISegmentStore<@NonNull ISegment> store = getSegmentStore();
 254         for (ISegment segment : REVERSE_SEGMENTS) {
 255             store.add(checkNotNull(segment));
 256         }
 257
 258         /*
 259          * Test each element one by one, the iteration order should follow the
 260          * start times, not the insertion order.
 261          */
 262         int i = 0;
 263         for (ISegment segment : store) {
 264             assertEquals(SEGMENTS.get(i++), segment);
 265         }
 266
 267         /* Manually dispose our own store */
 268         store.dispose();
 269     }
 270
 271     /**
 272      * Testing method
 273      * {@link ISegmentStore#getIntersectingElements(long start, long end)}
 274      */
 275     @Test
 276     public void testGetIntersectingElementsRange() {
 277
 278         Iterable<ISegment> intersectingElements;
 279
 280         /*
 281          * Range that does not include any segment
 282          */
 283         intersectingElements = fSegmentStore.getIntersectingElements(16, 20);
 284         assertEquals(0, Iterables.size(intersectingElements));
 285
 286         /*
 287          * Range start time : Before first segment start time Range end time :
 288          * After last segment end time
 289          */
 290         intersectingElements = fSegmentStore.getIntersectingElements(1, 15);
 291         assertEquals(5, Iterables.size(intersectingElements));
 292
 293         /*
 294          * Range start time : On first segment start time Range end time : On
 295          * last segment end time
 296          */
 297         intersectingElements = fSegmentStore.getIntersectingElements(2, 14);
 298         assertEquals(5, Iterables.size(intersectingElements));
 299
 300         /*
 301          * Range start time : After one segment start time Range end time :
 302          * Before one segment end time
 303          */
 304         intersectingElements = fSegmentStore.getIntersectingElements(11, 13);
 305         assertEquals(1, Iterables.size(intersectingElements));
 306         assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
 307
 308         /*
 309          * Range start time : On one segment start time Range end time : On one
 310          * segment end time
 311          */
 312         intersectingElements = fSegmentStore.getIntersectingElements(10, 14);
 313         assertEquals(1, Iterables.size(intersectingElements));
 314         assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
 315
 316         /*
 317          * Range start time : On last segment end time Range end time : After
 318          * last segment end time
 319          */
 320         intersectingElements = fSegmentStore.getIntersectingElements(14, 18);
 321         assertEquals(1, Iterables.size(intersectingElements));
 322         assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
 323
 324         /*
 325          * Range start time : Before first segment start time Range end time :
 326          * On first segment start time
 327          */
 328         intersectingElements = fSegmentStore.getIntersectingElements(1, 2);
 329         assertEquals(1, Iterables.size(intersectingElements));
 330         assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
 331     }
 332
 333     /**
 334      * Testing method {@link ISegmentStore#getIntersectingElements(long time)}
 335      */
 336     @Test
 337     public void testGetIntersectingElementsTime() {
 338
 339         Iterable<ISegment> intersectingElements;
 340
 341         /*
 342          * Time between segment start time and end time
 343          */
 344         intersectingElements = fSegmentStore.getIntersectingElements(3);
 345         assertEquals(1, Iterables.size(intersectingElements));
 346         assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
 347
 348         /*
 349          * Time on segment start time
 350          */
 351         intersectingElements = fSegmentStore.getIntersectingElements(2);
 352         assertEquals(1, Iterables.size(intersectingElements));
 353         assertEquals(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
 354
 355         /*
 356          * Time on segment end time
 357          */
 358         intersectingElements = fSegmentStore.getIntersectingElements(14);
 359         assertEquals(1, Iterables.size(intersectingElements));
 360         assertEquals(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
 361
 362         /*
 363          * Time overlapping many segments
 364          */
 365         intersectingElements = fSegmentStore.getIntersectingElements(6);
 366         assertEquals(4, Iterables.size(intersectingElements));
 367
 368         /*
 369          * Time between segments
 370          */
 371         intersectingElements = fSegmentStore.getIntersectingElements(9);
 372         assertEquals(0, Iterables.size(intersectingElements));
 373
 374         /*
 375          * Time before all segment start time
 376          */
 377         intersectingElements = fSegmentStore.getIntersectingElements(1);
 378         assertEquals(0, Iterables.size(intersectingElements));
 379
 380         /*
 381          * Time after all segment end time
 382          */
 383         intersectingElements = fSegmentStore.getIntersectingElements(15);
 384         assertEquals(0, Iterables.size(intersectingElements));
 385     }
 386
 387     /**
 388      * Testing method {@link ISegmentStore#dispose()}
 389      */
 390     @Test
 391     public void testDispose() {
 392         ISegmentStore<@NonNull ISegment> store = getSegmentStore();
 393         store.add(SEGMENT_2_6);
 394         store.dispose();
 395         assertEquals(0, store.size());
 396     }
 397
 398     /**
 399      * Test iterating over a store being built.
 400      *
 401      * bug 500607
 402      */
 403     @Test
 404     public void testIterator() {
 405         Collection<@NonNull ISegment> beforeExpected = ImmutableList.of(SEGMENT_2_6);
 406         Collection<@NonNull ISegment> afterExpected = ImmutableList.of(SEGMENT_2_6, SEGMENT_4_8);
 407         Collection<@NonNull ISegment> lastExpected = ImmutableList.of(SEGMENT_2_6, SEGMENT_4_8, SEGMENT_6_8);
 408         Collection<@NonNull ISegment> fixture = new ArrayList<>();
 409         ISegmentStore<@NonNull ISegment> store = getSegmentStore();
 410
 411         // Add one segment to the segment store and iterate
 412         store.add(SEGMENT_2_6);
 413         for (ISegment item : store) {
 414             fixture.add(item);
 415         }
 416         assertEquals(beforeExpected, fixture);
 417
 418         // Add a second segment to the store and iterate
 419         fixture.clear();
 420         store.add(SEGMENT_4_8);
 421         for (ISegment item : store) {
 422             fixture.add(item);
 423         }
 424         assertEquals(afterExpected, fixture);
 425
 426         fixture.clear();
 427         // Take an iterator
 428         Iterator<@NonNull ISegment> iter = store.iterator();
 429
 430         // Add a third segment to the store and iterate
 431         store.add(SEGMENT_6_8);
 432         Iterator<@NonNull ISegment> iter2 = store.iterator();
 433         fixture.clear();
 434
 435         // Make sure the first iterator take has only 2 elements and the second
 436         // has 3 elements
 437         while (iter.hasNext()) {
 438             fixture.add(iter.next());
 439         }
 440         assertEquals(afterExpected, fixture);
 441         fixture.clear();
 442         while (iter2.hasNext()) {
 443             fixture.add(iter2.next());
 444         }
 445         assertEquals(lastExpected, fixture);
 446     }
 447
 448     /**
 449      *  Test to check ordered iterators
 450      */
 451     @Test
 452     public void testSortedIterator() {
 453         List<@NonNull Comparator<ISegment>> comparators = new LinkedList<>();
 454         comparators.add(SegmentComparators.INTERVAL_END_COMPARATOR);
 455         comparators.add(NonNullUtils.checkNotNull(SegmentComparators.INTERVAL_END_COMPARATOR.reversed()));
 456         comparators.add(SegmentComparators.INTERVAL_START_COMPARATOR);
 457         comparators.add(NonNullUtils.checkNotNull(SegmentComparators.INTERVAL_START_COMPARATOR.reversed()));
 458         comparators.add(SegmentComparators.INTERVAL_LENGTH_COMPARATOR);
 459         comparators.add(NonNullUtils.checkNotNull(SegmentComparators.INTERVAL_LENGTH_COMPARATOR.reversed()));
 460
 461         Iterable<ISegment> iterable;
 462         for (Comparator<ISegment> comparator : comparators) {
 463             iterable = fSegmentStore.iterator(comparator);
 464             verifySortedIterable(iterable, 5, comparator);
 465             iterable = fSegmentStore.getIntersectingElements(5, comparator);
 466             verifySortedIterable(iterable, 3, comparator);
 467             iterable = fSegmentStore.getIntersectingElements(7, 14, comparator);
 468             verifySortedIterable(iterable, 3, comparator);
 469         }
 470     }
 471
 472     private static void verifySortedIterable(Iterable<ISegment> iterable, int expectedSize, Comparator<ISegment> comparator) {
 473         // check its size
 474         assertEquals(expectedSize, Iterables.size(iterable));
 475         Iterator<ISegment> iterator = iterable.iterator();
 476         // check the order
 477         ISegment prev, current = iterator.next();
 478         while (iterator.hasNext()) {
 479             prev = current;
 480             current = iterator.next();
 481             assertTrue(comparator.compare(prev, current) <= 0);
 482         }
 483     }
 484
 485     /**
 486      * Test retainAll() contract
 487      */
 488     @Test(expected = UnsupportedOperationException.class)
 489     public void testRetainAll() {
 490         ISegmentStore<@NonNull ISegment> store = getSegmentStore();
 491
 492         store.add(SEGMENT_2_6);
 493         store.retainAll(Collections.emptyList());
 494     }
 495
 496     /**
 497      * Test remove() contract
 498      */
 499     @Test(expected = UnsupportedOperationException.class)
 500     public void testRemove() {
 501         ISegmentStore<@NonNull ISegment> store = getSegmentStore();
 502
 503         store.add(SEGMENT_2_6);
 504         store.remove(SEGMENT_2_6);
 505     }
 506
 507     /**
 508      * Test removeAll() contract
 509      */
 510     @Test(expected = UnsupportedOperationException.class)
 511     public void testRemoveAll() {
 512         ISegmentStore<@NonNull ISegment> store = getSegmentStore();
 513
 514         store.add(SEGMENT_2_6);
 515         store.removeAll(Collections.emptyList());
 516     }
 517 }