Package ghidra.generic.util.datastruct
Class TreeValueSortedMap<K,V>
java.lang.Object
java.util.AbstractMap<K,V>
ghidra.generic.util.datastruct.TreeValueSortedMap<K,V>
- Type Parameters:
K
- the type of the keysV
- the type of the values
- All Implemented Interfaces:
ValueSortedMap<K,
,V> Map<K,
V>
A tree-based implementation of a value-sorted map
The underlying implementation is currently an unbalanced binary tree whose nodes also comprise a
doubly-linked list. Currently, it is not thread safe.
Note this implementation isn't terribly smart, as it makes no efforts to balance the tree. It is
also not thread safe.
-
Nested Class Summary
Modifier and TypeClassDescriptionprotected class
An iterator of the entriesprotected class
An iterator of the keysprotected class
An entry in the map.protected class
An iterator of the valuesprotected class
protected class
protected class
A public view of the map as a list of values This view implementsSortedList
andDeque
, since an ordered collection ought to behave like a list, and since this implementation is meant to be used as a dynamic-cost priority queue.Nested classes/interfaces inherited from class java.util.AbstractMap
AbstractMap.SimpleEntry<K,
V>, AbstractMap.SimpleImmutableEntry<K, V> Nested classes/interfaces inherited from interface ghidra.generic.util.datastruct.ValueSortedMap
ValueSortedMap.LesserList<E>, ValueSortedMap.ValueSortedMapEntryList<K,
V>, ValueSortedMap.ValueSortedMapKeyList<K> -
Field Summary
Modifier and TypeFieldDescriptionprotected final Comparator
<V> protected TreeValueSortedMap<K,
V>.Node protected TreeValueSortedMap<K,
V>.Node protected TreeValueSortedMap<K,
V>.Node -
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptionceilingEntryByValue
(V value) Returns a key-value mapping associated with the least value greater than or equal to the given value, ornull
if there is no such value.void
clear()
boolean
containsKey
(Object key) boolean
containsValue
(Object value) protected TreeValueSortedMap<K,
V>.ValueSortedTreeMapEntrySet protected TreeValueSortedMap<K,
V>.ValueSortedTreeMapKeySet protected TreeValueSortedMap<K,
V>.Node createNode
(K key, V value) protected TreeValueSortedMap<K,
V>.ValueSortedTreeMapValues static <K,
V> TreeValueSortedMap <K, V> createWithComparator
(Comparator<V> comparator) Create a tree using a custom comparator to order the valuesstatic <K,
V extends Comparable<V>>
TreeValueSortedMap<K, V> Create a tree using the values' natural orderingentrySet()
floorEntryByValue
(V value) Returns a key-value mapping associated with the greatest value less than or equal to the given value, ornull
if there is no such value.headMapByValue
(V toValue, boolean inclusive) Returns a view of the portion of this map whose values are less than (or equal to, ifinclusive
is true)toValue
.higherEntryByValue
(V value) Returns a key-value mapping associated with the least value strictly greater than the given value, ornull
if there is no such value.boolean
isEmpty()
keySet()
lowerEntryByValue
(V value) Returns a key-value mapping associated with the greatest value strictly less than the given value, ornull
if there is no such value.void
protected TreeValueSortedMap<K,
V>.Node searchValue
(V value, ghidra.generic.util.datastruct.TreeValueSortedMap.SearchMode mode) int
size()
subMapByValue
(V fromValue, boolean fromInclusive, V toValue, boolean toInclusive) Returns a view of the portion of this map whose values range fromfromValue
totoValue
.tailMapByValue
(V fromValue, boolean inclusive) Returns a view of the portion of this map whose values are greater than (or equal to, ifinclusive
is true)toValue
.boolean
Notify the map of an external change to the cost of a key's associated valuevalues()
Methods inherited from class java.util.AbstractMap
clone, equals, hashCode, toString
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.util.Map
compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, putIfAbsent, remove, replace, replace, replaceAll
-
Field Details
-
comparator
-
nodeMap
-
root
-
head
-
tail
-
-
Constructor Details
-
TreeValueSortedMap
protected TreeValueSortedMap() -
TreeValueSortedMap
-
-
Method Details
-
createWithNaturalOrder
Create a tree using the values' natural ordering -
createWithComparator
Create a tree using a custom comparator to order the values- Parameters:
comparator
- the comparator, providing a total ordering of the values
-
createEntrySet
-
createKeySet
-
createValues
-
createNode
-
searchValue
protected TreeValueSortedMap<K,V>.Node searchValue(V value, ghidra.generic.util.datastruct.TreeValueSortedMap.SearchMode mode) -
clear
public void clear() -
containsKey
- Specified by:
containsKey
in interfaceMap<K,
V> - Specified by:
containsKey
in interfaceValueSortedMap<K,
V> - Overrides:
containsKey
in classAbstractMap<K,
V>
-
containsValue
- Specified by:
containsValue
in interfaceMap<K,
V> - Specified by:
containsValue
in interfaceValueSortedMap<K,
V> - Overrides:
containsValue
in classAbstractMap<K,
V>
-
entrySet
-
get
-
lowerEntryByValue
Description copied from interface:ValueSortedMap
Returns a key-value mapping associated with the greatest value strictly less than the given value, ornull
if there is no such value.- Specified by:
lowerEntryByValue
in interfaceValueSortedMap<K,
V> - Parameters:
value
- the value- Returns:
- the found entry, or
null
-
floorEntryByValue
Description copied from interface:ValueSortedMap
Returns a key-value mapping associated with the greatest value less than or equal to the given value, ornull
if there is no such value.- Specified by:
floorEntryByValue
in interfaceValueSortedMap<K,
V> - Parameters:
value
- the value- Returns:
- the found entry, or
null
-
ceilingEntryByValue
Description copied from interface:ValueSortedMap
Returns a key-value mapping associated with the least value greater than or equal to the given value, ornull
if there is no such value.- Specified by:
ceilingEntryByValue
in interfaceValueSortedMap<K,
V> - Parameters:
value
- the value- Returns:
- the found entry, or
null
-
higherEntryByValue
Description copied from interface:ValueSortedMap
Returns a key-value mapping associated with the least value strictly greater than the given value, ornull
if there is no such value.- Specified by:
higherEntryByValue
in interfaceValueSortedMap<K,
V> - Parameters:
value
- the value- Returns:
- the found entry, or
null
-
isEmpty
public boolean isEmpty() -
keySet
-
put
-
putAll
-
remove
-
size
public int size() -
update
Description copied from interface:ValueSortedMap
Notify the map of an external change to the cost of a key's associated valueThis is meant to update the entry's position after a change in cost. The position may not necessarily change, however, if the cost did not change significantly.
- Specified by:
update
in interfaceValueSortedMap<K,
V> - Parameters:
key
- the key whose associated value has changed in cost- Returns:
- true if the entry's position changed
-
values
-
subMapByValue
public ValueSortedMap<K,V> subMapByValue(V fromValue, boolean fromInclusive, V toValue, boolean toInclusive) Description copied from interface:ValueSortedMap
Returns a view of the portion of this map whose values range fromfromValue
totoValue
. The returned map is an unmodifiable view.- Specified by:
subMapByValue
in interfaceValueSortedMap<K,
V> - Parameters:
fromValue
- low endpoint of the values in the returned mapfromInclusive
-true
if the low endpoint is to be included in the returned viewtoValue
- high endpoint of the values in the returned maptoInclusive
-true
if the high endpoint is to be included in the returned view- Returns:
- the view
-
headMapByValue
Description copied from interface:ValueSortedMap
Returns a view of the portion of this map whose values are less than (or equal to, ifinclusive
is true)toValue
. The returned map is an unmodifiable view.- Specified by:
headMapByValue
in interfaceValueSortedMap<K,
V> - Parameters:
toValue
- high endpoint of the values in the returned mapinclusive
-true
if the high endpoint is to be included in the returned view- Returns:
- the view
-
tailMapByValue
Description copied from interface:ValueSortedMap
Returns a view of the portion of this map whose values are greater than (or equal to, ifinclusive
is true)toValue
. The returned map is an unmodifiable view.- Specified by:
tailMapByValue
in interfaceValueSortedMap<K,
V> - Parameters:
fromValue
- low endpoint of the values in the returned mapinclusive
-true
if the low endpoint is to be included in the returned view- Returns:
- the view
-