Package ghidra.generic.util.datastruct

Class DynamicValueSortedTreeMap<K,​V>

  • Type Parameters:
    K - the type of the keys
    V - the type of the values
    All Implemented Interfaces:
    java.util.Map<K,​V>
    public class DynamicValueSortedTreeMap<K,​V>
extends java.util.AbstractMap<K,​V>
    A map that is sorted by value. This is an implementation of Map where entries are sorted by value, rather than by key. Such a tree may be useful as a priority queue where the cost of an entry may change over time. As such, the collections returned by entrySet(), keySet(), and values() all implement Deque. The order of the entries will be updated on any call to {@link #put(Object, Object))}, or a call to Collection.add(Object) on the entry set. Additionally, if the values are mutable objects, whose costs may change, there is an update(Object) method, which notifies the map that the given key may need to be repositioned. The associated collections also implement the List interface, providing fairly efficient implementations of List.get(int) and List.indexOf(Object). Sequential access is best performed via Collection.iterator(), since this will use a linked list. The underlying implementation is currently an unbalanced binary tree whose nodes also comprise a doubly-linked list. Currently, it is not thread safe.

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      protected class  DynamicValueSortedTreeMap.EntryListIterator
      An iterator of the entries
      protected class  DynamicValueSortedTreeMap.KeyListIterator
      An iterator of the keys
      protected class  DynamicValueSortedTreeMap.Node
      An entry in the map.
      protected class  DynamicValueSortedTreeMap.ValueListIterator
      An iterator of the values
      class  DynamicValueSortedTreeMap.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.
      class  DynamicValueSortedTreeMap.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.
      class  DynamicValueSortedTreeMap.ValueSortedTreeMapValues
      A public view of the map as a list of values This view implements List 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>

    • Constructor Summary

      Constructors 
      Constructor Description
      DynamicValueSortedTreeMap()
      Construct a dynamic value-sorted tree map using the values' natural ordering If the values do not have a natural ordering, you will eventually encounter a ClassCastException.
      DynamicValueSortedTreeMap​(java.util.Comparator<V> comparator)
      Construct a dynamic value-sorted tree map using a custom comparator to order the values

    • Constructor Detail

      • DynamicValueSortedTreeMap

        public DynamicValueSortedTreeMap()
        Construct a dynamic value-sorted tree map using the values' natural ordering If the values do not have a natural ordering, you will eventually encounter a ClassCastException. This condition is not checked at construction.

      • DynamicValueSortedTreeMap

        public DynamicValueSortedTreeMap​(java.util.Comparator<V> comparator)
        Construct a dynamic value-sorted tree map using a custom comparator to order the values
        Parameters:
        comparator - the comparator, providing a total ordering of the values

    • Method Detail

      • eq

        protected static boolean eq​(java.lang.Object o1,
                            java.lang.Object o2)
        A convenience for null-safe comparison

      • 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>

      • 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>

      • isEmpty

        public boolean isEmpty()
        Specified by:
        isEmpty in interface java.util.Map<K,​V>
        Overrides:
        isEmpty in class java.util.AbstractMap<K,​V>

      • 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)
        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.
        Parameters:
        key - the key whose associated value has changed in cost
        Returns:
        true if the entry's position changed