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 typeV
- 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:
-
Nested Class Summary
Nested classes/interfaces inherited from class java.util.AbstractMap
AbstractMap.SimpleEntry<K extends Object,
V extends Object>, AbstractMap.SimpleImmutableEntry<K extends Object, V extends Object> -
Constructor Summary
ConstructorsModifierConstructorDescriptionCreate a segment-map that uses natural comparison for the keys.SegmentMap
(SegmentMap<K, V> o) Copy-constructor.protected
SegmentMap
(Comparator<? super K> comparator) Create a segment-map using the provided key comparator. -
Method Summary
Modifier and TypeMethodDescriptionAdd a segment to the map.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.contiguousSubMap
(K begin, K end, ISegmentFactory<K, V> factory) Get a map containing all the segments in the ranges, without any gap.boolean
Create segments to fill in the gaps in the provided range of addresses.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.generateGaps
(K begin, boolean allowHeader, K end, boolean allowTrailer) Generate a list of segments that correspond to the ordered gaps list of this map.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.getOverlappingSegmentsMap
(K begin, boolean includeFirstPartialSegment, K end, boolean includeLastPartialSegment) Get all segments partially or fully present in the given range.getSegmentAfter
(K key) Get the closest segment after the provided address, which does not contain it.getSegmentBefore
(K key) Get the closest segment before the provided address, which does not contain it.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
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.Add a segment to the map.void
Add multiple segments to the map.void
setRemoveSegmentsOnOverlap
(boolean removeSegmentsOnOverlap) Set the map behavior when the insertion of a segment would overlap existing segments.toString()
Methods inherited from class java.util.concurrent.ConcurrentSkipListMap
ceilingEntry, ceilingKey, clear, clone, comparator, compute, computeIfAbsent, computeIfPresent, containsKey, containsValue, descendingKeySet, descendingMap, entrySet, firstEntry, firstKey, floorEntry, floorKey, forEach, get, getOrDefault, headMap, headMap, higherEntry, higherKey, isEmpty, keySet, lastEntry, lastKey, lowerEntry, lowerKey, merge, navigableKeySet, pollFirstEntry, pollLastEntry, putIfAbsent, remove, remove, replace, replace, replaceAll, size, subMap, tailMap, tailMap, values
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.util.Map
clear, containsKey, containsValue, get, isEmpty, remove, size
Methods inherited from interface java.util.NavigableMap
ceilingEntry, ceilingKey, firstEntry, floorEntry, floorKey, higherEntry, higherKey, lastEntry, lowerEntry, lowerKey, pollFirstEntry, pollLastEntry
-
Constructor Details
-
SegmentMap
public SegmentMap()Create a segment-map that uses natural comparison for the keys. -
SegmentMap
Copy-constructor. -
SegmentMap
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
Description copied from interface:ISegmentMap
Add a segment to the map. Convenience method, similar toput
.- Specified by:
add
in interfaceISegmentMap<K extends Comparable<K>,
V extends ISegment<K>> - Parameters:
v
- value to add- Returns:
- the added value
-
addAndMerge
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 callsISegmentMap.add(ISegment)
.- Specified by:
addAndMerge
in interfaceISegmentMap<K extends Comparable<K>,
V extends ISegment<K>> - Parameters:
v
- value to addmerge
- Merge function. First parameter is aCouple
(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
Description copied from interface:ISegmentMap
Add multiple segments to the map.- Specified by:
putAll
in interfaceISegmentMap<K extends Comparable<K>,
V extends ISegment<K>> - Specified by:
putAll
in interfaceMap<K extends Comparable<K>,
V extends ISegment<K>> - Overrides:
putAll
in classAbstractMap<K extends Comparable<K>,
V extends ISegment<K>>
-
compareKeys
Compare two keys using the map's actual comparator.- Parameters:
a
-b
-- Returns:
-
put
Description copied from interface:ISegmentMap
Add a segment to the map. This method throwsIllegalArgumentException
if:
- the key is null or invalid
- the key differs fromvalue.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 interfaceISegmentMap<K extends Comparable<K>,
V extends ISegment<K>> - Specified by:
put
in interfaceMap<K extends Comparable<K>,
V extends ISegment<K>> - Overrides:
put
in classConcurrentSkipListMap<K extends Comparable<K>,
V extends ISegment<K>>
-
isValidKey
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 ofMap
.This method is called when attempting to insert an entry into a map (using
add
,put
, orputall
).- Parameters:
k
- a key- Returns:
- true or false
-
isValidSegment
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
, orputall
).- Parameters:
v
- a segment- Returns:
-
getSegmentContaining
Description copied from interface:ISegmentMap
Get the segment containing the provided address.- Specified by:
getSegmentContaining
in interfaceISegmentMap<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
Description copied from interface:ISegmentMap
Get the closest segment after the provided address, which does not contain it.- Specified by:
getSegmentAfter
in interfaceISegmentMap<K extends Comparable<K>,
V extends ISegment<K>> - Parameters:
key
- address to probe- Returns:
- the next segment, null if none (final gap)
-
getSegmentBefore
Description copied from interface:ISegmentMap
Get the closest segment before the provided address, which does not contain it.- Specified by:
getSegmentBefore
in interfaceISegmentMap<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 interfaceISegmentMap<K extends Comparable<K>,
V extends ISegment<K>> - Returns:
- a map
-
isEmptyRange
Description copied from interface:ISegmentMap
Determine is the provided range is unencumbered.- Specified by:
isEmptyRange
in interfaceISegmentMap<K extends Comparable<K>,
V extends ISegment<K>> - Parameters:
begin
- inclusive start addressend
- exclusive end address- Returns:
-
contiguousSubMap
Description copied from interface:ISegmentMap
Get a map containing all the segments in the ranges, without any gap. UnlikesubMap
, 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 interfaceISegmentMap<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, exclusivefactory
- a factory used to generate gap items- Returns:
-
fillGaps
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 interfaceISegmentMap<K extends Comparable<K>,
V extends ISegment<K>> - Parameters:
begin
- begin addressend
- end addressfactory
- 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 interfaceISegmentMap<K extends Comparable<K>,
V extends ISegment<K>> - Parameters:
begin
- begin addressallowHeader
- determine if an unbounded gap header can be filledend
- end addressallowTrailer
- determine if an unbounded gap trailer can be filledfactory
- a factory object used to create segmentsaddItemsToMap
- 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 interfaceISegmentMap<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
Description copied from interface:ISegmentMap
Generate a list of segments that correspond to the ordered gaps list of this map.- Specified by:
generateGaps
in interfaceISegmentMap<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 interfaceConcurrentNavigableMap<K extends Comparable<K>,
V extends ISegment<K>> - Specified by:
subMap
in interfaceNavigableMap<K extends Comparable<K>,
V extends ISegment<K>> - Overrides:
subMap
in classConcurrentSkipListMap<K extends Comparable<K>,
V extends ISegment<K>>
-
hashCode
public int hashCode() -
equals
-
toString
- Overrides:
toString
in classAbstractMap<K extends Comparable<K>,
V extends ISegment<K>>
-