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 keys

V - 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 entries
protected class	TreeValueSortedMap.KeyListIterator	An iterator of the keys
protected class	TreeValueSortedMap.Node	An entry in the map.
protected class	TreeValueSortedMap.ValueListIterator	An iterator of the values
protected class	TreeValueSortedMap.ValueSortedTreeMapEntrySet	A public view of the map as a set of entries In addition to Set, this view implements List and Deque, 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 to Set, this view implements List and Deque, 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 implements SortedList and Deque, 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

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, or null 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 values
static <K,V extends java.lang.Comparable<V>> TreeValueSortedMap<K,V>	createWithNaturalOrder()	Create a tree using the values' natural ordering
TreeValueSortedMap.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, or null 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, if inclusive 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, or null 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, or null 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 from fromValue to toValue.
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, if inclusive is true) toValue.
boolean	update(K key)	Notify the map of an external change to the cost of a key's associated value
TreeValueSortedMap.ValueSortedTreeMapValues	values()

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, equals, forEach, getOrDefault, hashCode, merge, putIfAbsent, remove, replace, replace, replaceAll

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

Specified by:

clear in interface java.util.Map<K,V>

Overrides:

clear in class java.util.AbstractMap<K,V>

containsKey

public boolean containsKey(java.lang.Object key)

Specified by:

containsKey in interface java.util.Map<K,V>

Overrides:

containsKey in class java.util.AbstractMap<K,V>

containsValue

public boolean containsValue(java.lang.Object value)

Specified by:

containsValue in interface java.util.Map<K,V>

Overrides:

containsValue in class java.util.AbstractMap<K,V>

entrySet

public TreeValueSortedMap.ValueSortedTreeMapEntrySet entrySet()

Specified by:

entrySet in interface java.util.Map<K,V>

Specified by:

entrySet in interface ValueSortedMap<K,V>

Specified by:

entrySet in class java.util.AbstractMap<K,V>

See Also:

TreeValueSortedMap.ValueSortedTreeMapEntrySet

get

public V get(java.lang.Object key)

Specified by:

get in interface java.util.Map<K,V>

Overrides:

get in class java.util.AbstractMap<K,V>

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, or null if there is no such value.

Specified by:

lowerEntryByValue in interface ValueSortedMap<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, or null if there is no such value.

Specified by:

floorEntryByValue in interface ValueSortedMap<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, or null if there is no such value.

Specified by:

ceilingEntryByValue in interface ValueSortedMap<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, or null if there is no such value.

Specified by:

higherEntryByValue in interface ValueSortedMap<K,V>

Parameters:

value - the value

Returns:

the found entry, or null

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Map<K,V>

Overrides:

isEmpty in class java.util.AbstractMap<K,V>

keySet

public TreeValueSortedMap.ValueSortedTreeMapKeySet keySet()

Specified by:

keySet in interface java.util.Map<K,V>

Specified by:

keySet in interface ValueSortedMap<K,V>

Overrides:

keySet in class java.util.AbstractMap<K,V>

See Also:

TreeValueSortedMap.ValueSortedTreeMapKeySet

put

public V put(K key,
             V value)

Specified by:

put in interface java.util.Map<K,V>

Overrides:

put in class java.util.AbstractMap<K,V>

putAll

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

Specified by:

putAll in interface java.util.Map<K,V>

Overrides:

putAll in class java.util.AbstractMap<K,V>

remove

public V remove(java.lang.Object key)

Specified by:

remove in interface java.util.Map<K,V>

Overrides:

remove in class java.util.AbstractMap<K,V>

size

public int size()

Specified by:

size in interface java.util.Map<K,V>

Overrides:

size in class java.util.AbstractMap<K,V>

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 value

This 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 interface ValueSortedMap<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 interface java.util.Map<K,V>

Specified by:

values in interface ValueSortedMap<K,V>

Overrides:

values in class java.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 from fromValue to toValue. The returned map is an unmodifiable view.

Specified by:

subMapByValue in interface ValueSortedMap<K,V>

Parameters:

fromValue - low endpoint of the values in the returned map

fromInclusive - true if the low endpoint is to be included in the returned view

toValue - high endpoint of the values in the returned map

toInclusive - 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, if inclusive is true) toValue. The returned map is an unmodifiable view.

Specified by:

headMapByValue in interface ValueSortedMap<K,V>

Parameters:

toValue - high endpoint of the values in the returned map

inclusive - 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, if inclusive is true) toValue. The returned map is an unmodifiable view.

Specified by:

tailMapByValue in interface ValueSortedMap<K,V>

Parameters:

fromValue - low endpoint of the values in the returned map

inclusive - true if the low endpoint is to be included in the returned view

Returns:

the view