public class

SegmentMap

extends ConcurrentSkipListMap<K, V>
implements ISegmentMap<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 extends java.lang.Comparable<K>, V extends com.pnfsoftware.jeb.util.collect.ISegment<K>>
Known Direct Subclasses

Class Overview

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').

Summary

Public Constructors
SegmentMap()
Create a segment-map that uses natural comparison for the keys.
SegmentMap(SegmentMap<K, V> o)
Copy-constructor.
Protected Constructors
SegmentMap(Comparator<? super K> comparator)
Create a segment-map using the provided key comparator.
Public Methods
V add(V v)
Add a segment to the map.
V addAndMerge(V v, BiFunction<Couple<K, K>, List<V>, V> merge)
Adds a segment to the map and merge all the values within the overlap.
int compareKeys(K a, K b)
Compare two keys using the map's actual comparator.
SortedMap<K, V> contiguousSubMap(K begin, K end, ISegmentFactory<K, V> factory)
Get a map containing all the segments in the ranges, without any gap.
boolean equals(Object obj)
List<V> fillGaps(K begin, K end, ISegmentFactory<K, V> factory)
Create segments to fill in the gaps in the provided range of addresses.
List<V> generateGapItems(K begin, boolean allowHeader, K end, boolean allowTrailer, ISegmentFactory<K, V> factory, boolean addItemsToMap)
Create segments to fill in the gaps in the provided range of addresses.
List<Couple<K, K>> generateGaps(K begin, boolean allowHeader, K end, boolean allowTrailer, ISegmentGapVerifier<K> verifier)
Generate a list of segments that correspond to the ordered gaps list of this map.
List<Couple<K, K>> generateGaps(K begin, boolean allowHeader, K end, boolean allowTrailer)
Generate a list of segments that correspond to the ordered gaps list of this map.
SortedMap<K, V> getOverlappingSegmentsMap(K begin, boolean includeFirstPartialSegment, K end, boolean includeLastPartialSegment)
Get all segments partially or fully present in the given range.
V getSegmentAfter(K key)
Get the closest segment after the provided address, which does not contain it.
V getSegmentBefore(K key)
Get the closest segment before the provided address, which does not contain it.
V getSegmentContaining(K key)
Get the segment containing the provided address.
int hashCode()
boolean isEmptyRange(K begin, K end)
Determine is the provided range is unencumbered.
boolean isRemoveSegmentsOnOverlap()
Get the map behavior when the insertion of a segment would overlap existing segments.
boolean isValidKey(K k)
Validate whether or not the provided key is valid.
boolean isValidSegment(V v)
Validate whether or not the provided key is valid.
V put(K k, V v)
void putAll(Map<? extends K, ? extends V> m)
void setRemoveSegmentsOnOverlap(boolean removeSegmentsOnOverlap)
Set the map behavior when the insertion of a segment would overlap existing segments.
ConcurrentNavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
String toString()
[Expand]
Inherited Methods
From class java.util.concurrent.ConcurrentSkipListMap
From class java.util.AbstractMap
From class java.lang.Object
From interface com.pnfsoftware.jeb.util.collect.ISegmentMap
From interface java.util.Map
From interface java.util.NavigableMap
From interface java.util.SortedMap
From interface java.util.concurrent.ConcurrentMap
From interface java.util.concurrent.ConcurrentNavigableMap

Public Constructors

public SegmentMap ()

Create a segment-map that uses natural comparison for the keys.

public SegmentMap (SegmentMap<K, V> o)

Copy-constructor.

Protected Constructors

protected SegmentMap (Comparator<? super K> comparator)

Create a segment-map using the provided key comparator.

Parameters
comparator a custom comparator for the keys

Public Methods

public V add (V v)

Add a segment to the map. Convenience method, similar to put.

Parameters
v value to add
Returns
  • the added value

public V addAndMerge (V v, BiFunction<Couple<K, K>, List<V>, V> merge)

Adds a segment to the map and merge all the values within the overlap. If no overlap, this method just calls add(ISegment).

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())
            

public int compareKeys (K a, K b)

Compare two keys using the map's actual comparator.

public SortedMap<K, V> contiguousSubMap (K begin, K end, ISegmentFactory<K, V> factory)

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.

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

public boolean equals (Object obj)

public List<V> fillGaps (K begin, K end, ISegmentFactory<K, V> factory)

Create segments to fill in the gaps in the provided range of addresses. Trailer and header gaps will be created if need be.

Parameters
begin begin address
end end address
factory a factory object used to create segments
Returns
  • the list of segments that were created

public List<V> generateGapItems (K begin, boolean allowHeader, K end, boolean allowTrailer, ISegmentFactory<K, V> factory, boolean addItemsToMap)

Create segments to fill in the gaps in the provided range of addresses.

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

public List<Couple<K, K>> generateGaps (K begin, boolean allowHeader, K end, boolean allowTrailer, ISegmentGapVerifier<K> verifier)

Generate a list of segments that correspond to the ordered gaps list of this map.

Parameters
verifier optional verifier to customize the generated list
Returns
  • a list of [begin, end) keys representing the gap segments

public List<Couple<K, K>> generateGaps (K begin, boolean allowHeader, K end, boolean allowTrailer)

Generate a list of segments that correspond to the ordered gaps list of this map.

Returns
  • a list of [begin, end) keys representing the gap segments

public SortedMap<K, V> getOverlappingSegmentsMap (K begin, boolean includeFirstPartialSegment, K end, boolean includeLastPartialSegment)

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.

Returns
  • a map

public V getSegmentAfter (K key)

Get the closest segment after the provided address, which does not contain it.

Parameters
key address to probe
Returns
  • the next segment, null if none (final gap)

public V getSegmentBefore (K key)

Get the closest segment before the provided address, which does not contain it.

Parameters
key address to probe
Returns
  • the previous segment, null if none

public V getSegmentContaining (K key)

Get the segment containing the provided address.

Parameters
key address to probe
Returns
  • the containing segment, null if none (it is a gap)

public int hashCode ()

public boolean isEmptyRange (K begin, K end)

Determine is the provided range is unencumbered.

Parameters
begin inclusive start address
end exclusive end address

public boolean isRemoveSegmentsOnOverlap ()

Get the map behavior when the insertion of a segment would overlap existing segments.

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

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

public V put (K k, V v)

public void putAll (Map<? extends K, ? extends V> m)

public void setRemoveSegmentsOnOverlap (boolean removeSegmentsOnOverlap)

Set the map behavior when the insertion of a segment would overlap existing segments.

public ConcurrentNavigableMap<K, V> subMap (K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)

public String toString ()