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>
,java.util.Map<K,V>
public class TreeValueSortedMap<K,V> extends java.util.AbstractMap<K,V> implements ValueSortedMap<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
Nested Classes Modifier and Type Class Description protected class
TreeValueSortedMap.EntryListIterator
An iterator of the entriesprotected class
TreeValueSortedMap.KeyListIterator
An iterator of the keysprotected class
TreeValueSortedMap.Node
An entry in the map.protected class
TreeValueSortedMap.ValueListIterator
An iterator of the valuesprotected class
TreeValueSortedMap.ValueSortedTreeMapEntrySet
A public view of the map as a set of entries In addition toSet
, this view implementsList
andDeque
, since an ordered set ought to behave like a list, and since this implementation is meant to be used as a dynamic-cost priority queue.protected class
TreeValueSortedMap.ValueSortedTreeMapKeySet
A public view of the map as a set of keys In addition toSet
, this view implementsList
andDeque
, since an ordered set ought to behave like a list, and since this implementation is meant to be used as a dynamic-cost priority queue.protected class
TreeValueSortedMap.ValueSortedTreeMapValues
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
java.util.AbstractMap.SimpleEntry<K extends java.lang.Object,V extends java.lang.Object>, java.util.AbstractMap.SimpleImmutableEntry<K extends java.lang.Object,V extends java.lang.Object>
-
Nested classes/interfaces inherited from interface java.util.Map
java.util.Map.Entry<K extends java.lang.Object,V extends java.lang.Object>
-
Nested classes/interfaces inherited from interface ghidra.generic.util.datastruct.ValueSortedMap
ValueSortedMap.ValueSortedMapEntryList<K,V>, ValueSortedMap.ValueSortedMapKeyList<K>
-
-
Field Summary
Fields Modifier and Type Field Description protected java.util.Comparator<V>
comparator
protected TreeValueSortedMap.Node
head
protected java.util.Map<K,TreeValueSortedMap.Node>
nodeMap
protected TreeValueSortedMap.Node
root
protected TreeValueSortedMap.Node
tail
-
Constructor Summary
Constructors Modifier Constructor Description protected
TreeValueSortedMap()
protected
TreeValueSortedMap(java.util.Comparator<V> comparator)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description java.util.Map.Entry<K,V>
ceilingEntryByValue(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(java.lang.Object key)
boolean
containsValue(java.lang.Object value)
protected TreeValueSortedMap.ValueSortedTreeMapEntrySet
createEntrySet()
protected TreeValueSortedMap.ValueSortedTreeMapKeySet
createKeySet()
protected TreeValueSortedMap.Node
createNode(K key, V value)
protected TreeValueSortedMap.ValueSortedTreeMapValues
createValues()
static <K,V>
TreeValueSortedMap<K,V>createWithComparator(java.util.Comparator<V> comparator)
Create a tree using a custom comparator to order the valuesstatic <K,V extends java.lang.Comparable<V>>
TreeValueSortedMap<K,V>createWithNaturalOrder()
Create a tree using the values' natural orderingTreeValueSortedMap.ValueSortedTreeMapEntrySet
entrySet()
java.util.Map.Entry<K,V>
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.V
get(java.lang.Object key)
ValueSortedMap<K,V>
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
.java.util.Map.Entry<K,V>
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()
TreeValueSortedMap.ValueSortedTreeMapKeySet
keySet()
java.util.Map.Entry<K,V>
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.V
put(K key, V value)
void
putAll(java.util.Map<? extends K,? extends V> m)
V
remove(java.lang.Object key)
protected TreeValueSortedMap.Node
searchValue(V value, ghidra.generic.util.datastruct.TreeValueSortedMap.SearchMode mode)
int
size()
ValueSortedMap<K,V>
subMapByValue(V fromValue, boolean fromInclusive, V toValue, boolean toInclusive)
Returns a view of the portion of this map whose values range fromfromValue
totoValue
.ValueSortedMap<K,V>
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
update(K key)
Notify the map of an external change to the cost of a key's associated valueTreeValueSortedMap.ValueSortedTreeMapValues
values()
-
-
-
Field Detail
-
comparator
protected final java.util.Comparator<V> comparator
-
nodeMap
protected final java.util.Map<K,TreeValueSortedMap.Node> nodeMap
-
root
protected TreeValueSortedMap.Node root
-
head
protected TreeValueSortedMap.Node head
-
tail
protected TreeValueSortedMap.Node tail
-
-
Constructor Detail
-
TreeValueSortedMap
protected TreeValueSortedMap()
-
TreeValueSortedMap
protected TreeValueSortedMap(java.util.Comparator<V> comparator)
-
-
Method Detail
-
createWithNaturalOrder
public static <K,V extends java.lang.Comparable<V>> TreeValueSortedMap<K,V> createWithNaturalOrder()
Create a tree using the values' natural ordering
-
createWithComparator
public static <K,V> TreeValueSortedMap<K,V> createWithComparator(java.util.Comparator<V> comparator)
Create a tree using a custom comparator to order the values- Parameters:
comparator
- the comparator, providing a total ordering of the values
-
createEntrySet
protected TreeValueSortedMap.ValueSortedTreeMapEntrySet createEntrySet()
-
createKeySet
protected TreeValueSortedMap.ValueSortedTreeMapKeySet createKeySet()
-
createValues
protected TreeValueSortedMap.ValueSortedTreeMapValues createValues()
-
createNode
protected TreeValueSortedMap.Node createNode(K key, V value)
-
searchValue
protected TreeValueSortedMap.Node searchValue(V value, ghidra.generic.util.datastruct.TreeValueSortedMap.SearchMode mode)
-
clear
public void clear()
-
containsKey
public boolean containsKey(java.lang.Object key)
-
containsValue
public boolean containsValue(java.lang.Object value)
-
entrySet
public TreeValueSortedMap.ValueSortedTreeMapEntrySet entrySet()
- Specified by:
entrySet
in interfacejava.util.Map<K,V>
- Specified by:
entrySet
in interfaceValueSortedMap<K,V>
- Specified by:
entrySet
in classjava.util.AbstractMap<K,V>
- See Also:
TreeValueSortedMap.ValueSortedTreeMapEntrySet
-
get
public V get(java.lang.Object key)
-
lowerEntryByValue
public java.util.Map.Entry<K,V> lowerEntryByValue(V value)
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
public java.util.Map.Entry<K,V> floorEntryByValue(V value)
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
public java.util.Map.Entry<K,V> ceilingEntryByValue(V value)
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
public java.util.Map.Entry<K,V> higherEntryByValue(V value)
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
public TreeValueSortedMap.ValueSortedTreeMapKeySet keySet()
- Specified by:
keySet
in interfacejava.util.Map<K,V>
- Specified by:
keySet
in interfaceValueSortedMap<K,V>
- Overrides:
keySet
in classjava.util.AbstractMap<K,V>
- See Also:
TreeValueSortedMap.ValueSortedTreeMapKeySet
-
remove
public V remove(java.lang.Object key)
-
size
public int size()
-
update
public boolean update(K key)
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
public TreeValueSortedMap.ValueSortedTreeMapValues values()
- Specified by:
values
in interfacejava.util.Map<K,V>
- Specified by:
values
in interfaceValueSortedMap<K,V>
- Overrides:
values
in classjava.util.AbstractMap<K,V>
- See Also:
TreeValueSortedMap.ValueSortedTreeMapValues
-
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
public ValueSortedMap<K,V> headMapByValue(V toValue, boolean inclusive)
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
public ValueSortedMap<K,V> tailMapByValue(V fromValue, boolean inclusive)
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
-
-