Package com.pnfsoftware.jeb.util.collect

Class SegmentMap<K extends Comparable<K>,V extends ISegment<K>>

java.lang.Object
java.util.AbstractMap<K,V>
java.util.concurrent.ConcurrentSkipListMap<K,V>
com.pnfsoftware.jeb.util.collect.SegmentMap<K,V>
Type Parameters:
K - key/address type
V - value/segment type
All Implemented Interfaces:
ISegmentMap<K,V>, Serializable, Cloneable, ConcurrentMap<K,V>, ConcurrentNavigableMap<K,V>, Map<K,V>, NavigableMap<K,V>, SortedMap<K,V>
Direct Known Subclasses:
AddressSegmentMap
@Ser public class SegmentMap<K extends Comparable<K>,V extends ISegment<K>> extends ConcurrentSkipListMap<K,V> implements ISegmentMap<K,V>
Standard implementation of a segment-map using a TreeMap as the underlying data structure. Supports auto-removal of values when inserting a new segment overlaps exisiting segments.

Thread safety: support for partial concurrency: multiple reader threads with a single writer thread is okay. However, if multiple threads are attempting to modify this object, external synchronization is required. (This is the reason why this class name is not prefixed by 'Concurrent').

See Also:

  • Constructor Details

    • SegmentMap

      public SegmentMap()
      Create a segment-map that uses natural comparison for the keys.

    • SegmentMap

      public SegmentMap(SegmentMap<K,V> o)
      Copy-constructor.

    • SegmentMap

      protected SegmentMap(Comparator<? super K> comparator)
      Create a segment-map using the provided key comparator.
      Parameters:
      comparator - a custom comparator for the keys

  • Method Details

    • setRemoveSegmentsOnOverlap

      public void setRemoveSegmentsOnOverlap(boolean removeSegmentsOnOverlap)
      Set the map behavior when the insertion of a segment would overlap existing segments.
      Parameters:
      removeSegmentsOnOverlap -

    • isRemoveSegmentsOnOverlap

      public boolean isRemoveSegmentsOnOverlap()
      Get the map behavior when the insertion of a segment would overlap existing segments.
      Returns:

    • add

      public V add(V v)
      Description copied from interface: ISegmentMap
      Add a segment to the map. Convenience method, similar to put.
      Specified by:
      add in interface ISegmentMap<K extends Comparable<K>,V extends ISegment<K>>
      Parameters:
      v - value to add
      Returns:
      the added value

    • addAndMerge

      public V addAndMerge(V v, BiFunction<Couple<K,K>,List<V>,V> merge)
      Description copied from interface: ISegmentMap
      Adds a segment to the map and merge all the values within the overlap. If no overlap, this method just calls ISegmentMap.add(ISegment).
      Specified by:
      addAndMerge in interface ISegmentMap<K extends Comparable<K>,V extends ISegment<K>>
      Parameters:
      v - value to add
      merge - Merge function. First parameter is a Couple (begin, end) of the new merged segment. Second parameter is the list of all values to merge (including the value v). For example, a valid function would be: 
       (c, l) -> new IntegerSegment(c.getFirst(), c.getSecond() - c.getFirst())

    • putAll

      public void putAll(Map<? extends K,? extends V> m)
      Description copied from interface: ISegmentMap
      Add multiple segments to the map.
      Specified by:
      putAll in interface ISegmentMap<K extends Comparable<K>,V extends ISegment<K>>
      Specified by:
      putAll in interface Map<K extends Comparable<K>,V extends ISegment<K>>
      Overrides:
      putAll in class AbstractMap<K extends Comparable<K>,V extends ISegment<K>>

    • compareKeys

      public int compareKeys(K a, K b)
      Compare two keys using the map's actual comparator.
      Parameters:
      a -
      b -
      Returns:

    • put

      public V put(K k, V v)
      Description copied from interface: ISegmentMap
      Add a segment to the map. This method throws IllegalArgumentException if:
      - the key is null or invalid
      - the key differs from value.getBegin()
      - the segment is invalid (eg, zero-length) - the segment to be inserted overlaps existing segments (alternatively, an implementation may decide to remove the overlapping segments)
      Specified by:
      put in interface ISegmentMap<K extends Comparable<K>,V extends ISegment<K>>
      Specified by:
      put in interface Map<K extends Comparable<K>,V extends ISegment<K>>
      Overrides:
      put in class ConcurrentSkipListMap<K extends Comparable<K>,V extends ISegment<K>>

    • isValidKey

      public boolean isValidKey(K k)
      Validate whether or not the provided key is valid. The default implementation simply returns true: all objects of type K are valid keys, as would be expected by an implementation of Map.

      This method is called when attempting to insert an entry into a map (using add, put, or putall).

      Parameters:
      k - a key
      Returns:
      true or false

    • isValidSegment

      public boolean isValidSegment(V v)
      Validate whether or not the provided key is valid. The default implementation verifies that the segment's begin value is strictly less than the segment's end value.

      This method is called when attempting to insert an entry into a map (using add, put, or putall).

      Parameters:
      v - a segment
      Returns:

    • getSegmentContaining

      public V getSegmentContaining(K key)
      Description copied from interface: ISegmentMap
      Get the segment containing the provided address.
      Specified by:
      getSegmentContaining in interface ISegmentMap<K extends Comparable<K>,V extends ISegment<K>>
      Parameters:
      key - address to probe
      Returns:
      the containing segment, null if none (it is a gap)

    • getSegmentAfter

      public V getSegmentAfter(K key)
      Description copied from interface: ISegmentMap
      Get the closest segment after the provided address, which does not contain it.
      Specified by:
      getSegmentAfter in interface ISegmentMap<K extends Comparable<K>,V extends ISegment<K>>
      Parameters:
      key - address to probe
      Returns:
      the next segment, null if none (final gap)

    • getSegmentBefore

      public V getSegmentBefore(K key)
      Description copied from interface: ISegmentMap
      Get the closest segment before the provided address, which does not contain it.
      Specified by:
      getSegmentBefore in interface ISegmentMap<K extends Comparable<K>,V extends ISegment<K>>
      Parameters:
      key - address to probe
      Returns:
      the previous segment, null if none

    • getOverlappingSegmentsMap

      public SortedMap<K,V> getOverlappingSegmentsMap(K begin, boolean includeFirstPartialSegment, K end, boolean includeLastPartialSegment)
      Description copied from interface: ISegmentMap
      Get all segments partially or fully present in the given range. The returned map is not a view of the original map. Modifying it will not modify the original map.
      Specified by:
      getOverlappingSegmentsMap in interface ISegmentMap<K extends Comparable<K>,V extends ISegment<K>>
      Returns:
      a map

    • getOverlappingSegmentsMap

      public SortedMap<K,V> getOverlappingSegmentsMap(K begin, boolean includeFirstPartialSegment, K end, boolean includeLastPartialSegment, Predicate<? super Map.Entry<K,V>> predicate)
      Description copied from interface: ISegmentMap
      Get all segments partially or fully present in the given range. The returned map is not a view of the original map. Modifying it will not modify the original map.
      Specified by:
      getOverlappingSegmentsMap in interface ISegmentMap<K extends Comparable<K>,V extends ISegment<K>>
      predicate - Predicate to filter the returned values.
      Returns:
      a map

    • isEmptyRange

      public boolean isEmptyRange(K begin, K end)
      Description copied from interface: ISegmentMap
      Determine is the provided range is unencumbered.
      Specified by:
      isEmptyRange in interface ISegmentMap<K extends Comparable<K>,V extends ISegment<K>>
      Parameters:
      begin - inclusive start address
      end - exclusive end address
      Returns:

    • contiguousSubMap

      public SortedMap<K,V> contiguousSubMap(K begin, K end, ISegmentFactory<K,V> factory)
      Description copied from interface: ISegmentMap
      Get a map containing all the segments in the ranges, without any gap. Unlike subMap, the map returned by this method is not a "view" of the original map; modifying this map, such as inserting or deleting items, does not modify the original map. The original segment-map is not modified; that is, if gap items, are created, they are not added to the original map.
      Specified by:
      contiguousSubMap in interface ISegmentMap<K extends Comparable<K>,V extends ISegment<K>>
      Parameters:
      begin - start address, inclusive. The first item should start at or after this address; any item simply containing (ie, spanning over) the start address will not be part of the resulting map.
      end - end address end address, exclusive
      factory - a factory used to generate gap items
      Returns:

    • fillGaps

      public List<V> fillGaps(K begin, K end, ISegmentFactory<K,V> factory)
      Description copied from interface: ISegmentMap
      Create segments to fill in the gaps in the provided range of addresses. Trailer and header gaps will be created if need be.
      Specified by:
      fillGaps in interface ISegmentMap<K extends Comparable<K>,V extends ISegment<K>>
      Parameters:
      begin - begin address
      end - end address
      factory - a factory object used to create segments
      Returns:
      the list of segments that were created

    • generateGapItems

      public List<V> generateGapItems(K begin, boolean allowHeader, K end, boolean allowTrailer, ISegmentFactory<K,V> factory, boolean addItemsToMap)
      Description copied from interface: ISegmentMap
      Create segments to fill in the gaps in the provided range of addresses.
      Specified by:
      generateGapItems in interface ISegmentMap<K extends Comparable<K>,V extends ISegment<K>>
      Parameters:
      begin - begin address
      allowHeader - determine if an unbounded gap header can be filled
      end - end address
      allowTrailer - determine if an unbounded gap trailer can be filled
      factory - a factory object used to create segments
      addItemsToMap - if true, the items created to fill in the gaps in the segment map are also added to the segment map
      Returns:
      the list of segments that were created

    • generateGaps

      public List<Couple<K,K>> generateGaps(K begin, boolean allowHeader, K end, boolean allowTrailer, ISegmentGapVerifier<K> verifier)
      Description copied from interface: ISegmentMap
      Generate a list of segments that correspond to the ordered gaps list of this map.
      Specified by:
      generateGaps in interface ISegmentMap<K extends Comparable<K>,V extends ISegment<K>>
      verifier - optional verifier to customize the generated list
      Returns:
      a list of [begin, end) keys representing the gap segments

    • generateGaps

      public List<Couple<K,K>> generateGaps(K begin, boolean allowHeader, K end, boolean allowTrailer)
      Description copied from interface: ISegmentMap
      Generate a list of segments that correspond to the ordered gaps list of this map.
      Specified by:
      generateGaps in interface ISegmentMap<K extends Comparable<K>,V extends ISegment<K>>
      Returns:
      a list of [begin, end) keys representing the gap segments

    • subMap

      public ConcurrentNavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
      Specified by:
      subMap in interface ConcurrentNavigableMap<K extends Comparable<K>,V extends ISegment<K>>
      Specified by:
      subMap in interface NavigableMap<K extends Comparable<K>,V extends ISegment<K>>
      Overrides:
      subMap in class ConcurrentSkipListMap<K extends Comparable<K>,V extends ISegment<K>>

    • hashCode

      public int hashCode()
      Specified by:
      hashCode in interface Map<K extends Comparable<K>,V extends ISegment<K>>
      Overrides:
      hashCode in class AbstractMap<K extends Comparable<K>,V extends ISegment<K>>

    • equals

      public boolean equals(Object obj)
      Specified by:
      equals in interface Map<K extends Comparable<K>,V extends ISegment<K>>
      Overrides:
      equals in class ConcurrentSkipListMap<K extends Comparable<K>,V extends ISegment<K>>

    • toString

      public String toString()
      Overrides:
      toString in class AbstractMap<K extends Comparable<K>,V extends ISegment<K>>