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