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>, Map<K,V>

public class TreeValueSortedMap<K,V>
extends 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

AbstractMap.SimpleEntry<K extends Object,V extends Object>, AbstractMap.SimpleImmutableEntry<K extends Object,V extends Object>

Nested classes/interfaces inherited from interface java.util.Map

Map.Entry<K extends Object,V extends Object>

Nested classes/interfaces inherited from interface ghidra.generic.util.datastruct.ValueSortedMap

ValueSortedMap.LesserList<E>, ValueSortedMap.ValueSortedMapEntryList<K,V>, ValueSortedMap.ValueSortedMapKeyList<K>

Field Summary

Fields

Modifier and Type	Field	Description
protected final Comparator<V>	comparator
protected TreeValueSortedMap<K,V>.Node	head
protected final Map<K,TreeValueSortedMap<K,V>.Node>	nodeMap
protected TreeValueSortedMap<K,V>.Node	root
protected TreeValueSortedMap<K,V>.Node	tail

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	TreeValueSortedMap()
protected	TreeValueSortedMap(Comparator<V> comparator)

Method Summary

Modifier and Type	Method	Description
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(Object key)
boolean	containsValue(Object value)
protected TreeValueSortedMap<K,V>.ValueSortedTreeMapEntrySet	createEntrySet()
protected TreeValueSortedMap<K,V>.ValueSortedTreeMapKeySet	createKeySet()
protected TreeValueSortedMap<K,V>.Node	createNode(K key, V value)
protected TreeValueSortedMap<K,V>.ValueSortedTreeMapValues	createValues()
static <K, V> TreeValueSortedMap<K,V>	createWithComparator(Comparator<V> comparator)	Create a tree using a custom comparator to order the values
static <K, V extends Comparable<V>> TreeValueSortedMap<K,V>	createWithNaturalOrder()	Create a tree using the values' natural ordering
TreeValueSortedMap<K,V>.ValueSortedTreeMapEntrySet	entrySet()
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(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.
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<K,V>.ValueSortedTreeMapKeySet	keySet()
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(Map<? extends K,? extends V> m)
V	remove(Object key)
protected TreeValueSortedMap<K,V>.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<K,V>.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, forEach, getOrDefault, merge, putIfAbsent, remove, replace, replace, replaceAll

Field Details

comparator

protected final Comparator<V> comparator

nodeMap

protected final Map<K,TreeValueSortedMap<K,V>.Node> nodeMap

root

protected TreeValueSortedMap<K,V>.Node root

head

protected TreeValueSortedMap<K,V>.Node head

tail

protected TreeValueSortedMap<K,V>.Node tail

Constructor Details

TreeValueSortedMap

protected TreeValueSortedMap()

TreeValueSortedMap

protected TreeValueSortedMap(Comparator<V> comparator)

Method Details

createWithNaturalOrder

public static <K,
V extends Comparable<V>>
TreeValueSortedMap<K,V> createWithNaturalOrder()

Create a tree using the values' natural ordering

createWithComparator

public static <K,
V> TreeValueSortedMap<K,V> createWithComparator(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<K,V>.ValueSortedTreeMapEntrySet createEntrySet()

createKeySet

protected TreeValueSortedMap<K,V>.ValueSortedTreeMapKeySet createKeySet()

createValues

protected TreeValueSortedMap<K,V>.ValueSortedTreeMapValues createValues()

createNode

protected TreeValueSortedMap<K,V>.Node createNode(K key,
 V value)

searchValue

protected TreeValueSortedMap<K,V>.Node searchValue(V value,
 ghidra.generic.util.datastruct.TreeValueSortedMap.SearchMode mode)

clear

public void clear()

Specified by:

clear in interface Map<K,V>

Specified by:

clear in interface ValueSortedMap<K,V>

Overrides:

clear in class AbstractMap<K,V>

containsKey

public boolean containsKey(Object key)

Specified by:

containsKey in interface Map<K,V>

Specified by:

containsKey in interface ValueSortedMap<K,V>

Overrides:

containsKey in class AbstractMap<K,V>

containsValue

public boolean containsValue(Object value)

Specified by:

containsValue in interface Map<K,V>

Specified by:

containsValue in interface ValueSortedMap<K,V>

Overrides:

containsValue in class AbstractMap<K,V>

entrySet

public TreeValueSortedMap<K,V>.ValueSortedTreeMapEntrySet entrySet()

Specified by:

entrySet in interface Map<K,V>

Specified by:

entrySet in interface ValueSortedMap<K,V>

Specified by:

entrySet in class AbstractMap<K,V>

See Also:

• TreeValueSortedMap<K,V>.ValueSortedTreeMapEntrySet

get

public V get(Object key)

Specified by:

get in interface Map<K,V>

Specified by:

get in interface ValueSortedMap<K,V>

Overrides:

get in class AbstractMap<K,V>

lowerEntryByValue

public 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 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 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 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 Map<K,V>

Specified by:

isEmpty in interface ValueSortedMap<K,V>

Overrides:

isEmpty in class AbstractMap<K,V>

keySet

public TreeValueSortedMap<K,V>.ValueSortedTreeMapKeySet keySet()

Specified by:

keySet in interface Map<K,V>

Specified by:

keySet in interface ValueSortedMap<K,V>

Overrides:

keySet in class AbstractMap<K,V>

See Also:

• TreeValueSortedMap<K,V>.ValueSortedTreeMapKeySet

put

public V put(K key,
 V value)

Specified by:

put in interface Map<K,V>

Specified by:

put in interface ValueSortedMap<K,V>

Overrides:

put in class AbstractMap<K,V>

putAll

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

Specified by:

putAll in interface Map<K,V>

Overrides:

putAll in class AbstractMap<K,V>

remove

public V remove(Object key)

Specified by:

remove in interface Map<K,V>

Specified by:

remove in interface ValueSortedMap<K,V>

Overrides:

remove in class AbstractMap<K,V>

size

public int size()

Specified by:

size in interface Map<K,V>

Specified by:

size in interface ValueSortedMap<K,V>

Overrides:

size in class 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<K,V>.ValueSortedTreeMapValues values()

Specified by:

values in interface Map<K,V>

Specified by:

values in interface ValueSortedMap<K,V>

Overrides:

values in class AbstractMap<K,V>

See Also:

• TreeValueSortedMap<K,V>.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