statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/segmentstore/core/treemap/TreeMapStore.java

   1 /*******************************************************************************
   2  * Copyright (c) 2015 EfficiOS Inc., Alexandre Montplaisir
   3  *
   4  * All rights reserved. This program and the accompanying materials
   5  * are made available under the terms of the Eclipse Public License v1.0
   6  * which accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *
   9  * Contributors:
  10  *    Alexandre Montplaisir - Initial API and implementation
  11  *******************************************************************************/
  12
  13 package org.eclipse.tracecompass.segmentstore.core.treemap;
  14
  15 import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
  16
  17 import java.util.Comparator;
  18 import java.util.HashMap;
  19 import java.util.Iterator;
  20 import java.util.Map;
  21 import java.util.TreeMap;
  22
  23 import org.eclipse.jdt.annotation.Nullable;
  24 import org.eclipse.tracecompass.segmentstore.core.ISegment;
  25 import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
  26
  27 import com.google.common.collect.Iterables;
  28 import com.google.common.collect.Sets;
  29 import com.google.common.collect.TreeMultimap;
  30
  31 /**
  32  * Implementation of a {@link ISegmentStore} using in-memory {@link TreeMap}'s.
  33  * This relatively simple implementation holds everything in memory, and as such
  34  * cannot contain too much data.
  35  *
  36  * @param <T>
  37  *            The time of time range held
  38  *
  39  * @author Alexandre Montplaisir
  40  */
  41 public class TreeMapStore<T extends ISegment> implements ISegmentStore<T> {
  42
  43     private final TreeMultimap<Long, T> fStartTimesIndex;
  44     private final TreeMultimap<Long, T> fEndTimesIndex;
  45
  46     private final Map<Long, T> fPositionMap;
  47     private long fSize;
  48
  49     /**
  50      *Constructor
  51      */
  52     public TreeMapStore() {
  53         fStartTimesIndex = checkNotNull(TreeMultimap.<Long, T> create(LONG_COMPARATOR, INTERVAL_START_COMPARATOR));
  54         fEndTimesIndex = checkNotNull(TreeMultimap.<Long, T> create(LONG_COMPARATOR, INTERVAL_END_COMPARATOR));
  55         fPositionMap = new HashMap<>();
  56         fSize = 0;
  57     }
  58
  59     @Override
  60     public Iterator<T> iterator() {
  61         return checkNotNull(fStartTimesIndex.values().iterator());
  62     }
  63
  64     @Override
  65     public synchronized void addElement(T val) {
  66         fStartTimesIndex.put(Long.valueOf(val.getStart()), val);
  67         fEndTimesIndex.put(Long.valueOf(val.getEnd()), val);
  68         fPositionMap.put(fSize, val);
  69         fSize++;
  70     }
  71
  72     @Override
  73     public long getNbElements() {
  74         return fSize;
  75     }
  76
  77     @Override
  78     public T getElementAtIndex(long index) {
  79         return checkNotNull(fPositionMap.get(Long.valueOf(index)));
  80     }
  81
  82     @Override
  83     public Iterable<T> getIntersectingElements(long position) {
  84         /*
  85          * The intervals intersecting 't' are those whose 1) start time is
  86          * *lower* than 't' AND 2) end time is *higher* than 't'.
  87          */
  88         Iterable<T> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(position, true).values());
  89         Iterable<T> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(position, true).values());
  90
  91         return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds)));
  92     }
  93
  94     @Override
  95     public Iterable<T> getIntersectingElements(long start, long end) {
  96         Iterable<T> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(end, true).values());
  97         Iterable<T> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(start, true).values());
  98
  99         return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds)));
 100     }
 101
 102     @Override
 103     public void dispose() {
 104         fStartTimesIndex.clear();
 105         fEndTimesIndex.clear();
 106         fPositionMap.clear();
 107     }
 108
 109     // ------------------------------------------------------------------------
 110     // Comparators, used for the tree maps
 111     // ------------------------------------------------------------------------
 112
 113     private static final Comparator<Long> LONG_COMPARATOR = new Comparator<Long>() {
 114         @Override
 115         public int compare(@Nullable Long o1, @Nullable Long o2) {
 116             if (o1 == null || o2 == null) {
 117                 throw new IllegalArgumentException();
 118             }
 119             return o1.compareTo(o2);
 120         }
 121     };
 122
 123     private static final Comparator<ISegment> INTERVAL_START_COMPARATOR = new Comparator<ISegment>() {
 124         @Override
 125         public int compare(@Nullable ISegment o1, @Nullable ISegment o2) {
 126             if (o1 == null || o2 == null) {
 127                 throw new IllegalArgumentException();
 128             }
 129             return Long.compare(o1.getStart(), o2.getStart());
 130         }
 131     };
 132
 133     private static final Comparator<ISegment> INTERVAL_END_COMPARATOR = new Comparator<ISegment>() {
 134         @Override
 135         public int compare(@Nullable ISegment o1, @Nullable ISegment o2) {
 136             if (o1 == null || o2 == null) {
 137                 throw new IllegalArgumentException();
 138             }
 139             return Long.compare(o1.getEnd(), o2.getEnd());
 140         }
 141     };
 142
 143
 144 }