Package ghidra.generic.util.datastruct

# Class DynamicSortedTreeSet<E>

java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractSet<E>
ghidra.generic.util.datastruct.DynamicSortedTreeSet<E>

Type Parameters:
  `E` - the type of the elements

All Implemented Interfaces:
  `Iterable<E>`, `Collection<E>`, `Set<E>`

public class DynamicSortedTreeSet<E> extends AbstractSet<E>
A set where the ordering of elements may change over time, based on an alternative comparator

This is an implementation of `Set` where elements may be sorted by an alternative comparator (usually by "cost"), rather than by the natural ordering. It may seem odd, but the natural ordering is still used to determine the uniqueness of keys. That is, two elements that are unequal -- but are considered equal by the alternative comparator -- may co-exist in the set. (Note: in such cases, the two elements are ordered first-in first-out). Additionally, if the elements are mutable, then their ordering may change over time. This mode of operation is enabled by the `update(Object)` method, which must be called to notify the set of any change to an element that may affect its order. This set also implements the `List` and `Deque` interfaces. Since the set is ordered, it makes sense to treat it as a list. It provides fairly efficient implementations of `get(int)` and `indexOf(Object)`. Sequential access is best performed via `iterator()`, since this will use a linked list.

The underlying implementation is backed by `TreeValueSortedMap`. Currently, it is not thread safe.

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `DynamicSortedTreeSet()`
  Construct a dynamic sorted tree set using the elements' natural ordering
  `DynamicSortedTreeSet(Comparator<E> comparator)`
  Construct a dynamic sorted tree set using a custom comparator to order the elements

- ## Method Summary

  Modifier and Type
  Method
  Description
  `boolean`
  `add(E e)`
  `void`
  `clear()`
  `boolean`
  `contains(Object o)`
  `E`
  `get(int index)`
  `int`
  `indexOf(Object o)`
  `boolean`
  `isEmpty()`
  `Iterator<E>`
  `iterator()`
  `boolean`
  `remove(Object o)`
  `boolean`
  `removeAll(Collection<?> c)`
  `boolean`
  `retainAll(Collection<?> c)`
  `int`
  `size()`
  `Spliterator<E>`
  `spliterator()`
  `boolean`
  `update(E e)`
  Notify the queue of a change to an element's cost.

  ### Methods inherited from class java.util.AbstractSet

  `equals, hashCode`

  ### Methods inherited from class java.util.AbstractCollection

  `addAll, containsAll, toArray, toArray, toString`

  ### Methods inherited from class java.lang.Object

  `clone, finalize, getClass, notify, notifyAll, wait, wait, wait`

  ### Methods inherited from interface java.util.Collection

  `parallelStream, removeIf, stream, toArray`

  ### Methods inherited from interface java.lang.Iterable

  `forEach`

  ### Methods inherited from interface java.util.Set

  `addAll, containsAll, toArray, toArray`

- ## Constructor Details

  - ### DynamicSortedTreeSet

    public DynamicSortedTreeSet()
    Construct a dynamic sorted tree set using the elements' natural ordering

    Other than, perhaps, a more convenient interface, this offers few if any benefits over the stock `Set`.

  - ### DynamicSortedTreeSet

    public DynamicSortedTreeSet(Comparator<E> comparator)
    Construct a dynamic sorted tree set using a custom comparator to order the elements
    Parameters:
      `comparator` - the comparator, providing a total ordering of the values

- ## Method Details

  - ### add

    public boolean add(E e)
    Specified by:
      `add` in interface `Collection<E>`
    Specified by:
      `add` in interface `Set<E>`
    Overrides:
      `add` in class `AbstractCollection<E>`

  - ### clear

    public void clear()
    Specified by:
      `clear` in interface `Collection<E>`
    Specified by:
      `clear` in interface `Set<E>`
    Overrides:
      `clear` in class `AbstractCollection<E>`

  - ### contains

    public boolean contains(Object o)
    Specified by:
      `contains` in interface `Collection<E>`
    Specified by:
      `contains` in interface `Set<E>`
    Overrides:
      `contains` in class `AbstractCollection<E>`

  - ### get

    public E get(int index)

  - ### indexOf

    public int indexOf(Object o)

  - ### isEmpty

    public boolean isEmpty()
    Specified by:
      `isEmpty` in interface `Collection<E>`
    Specified by:
      `isEmpty` in interface `Set<E>`
    Overrides:
      `isEmpty` in class `AbstractCollection<E>`

  - ### iterator

    public Iterator<E> iterator()
    Specified by:
      `iterator` in interface `Collection<E>`
    Specified by:
      `iterator` in interface `Iterable<E>`
    Specified by:
      `iterator` in interface `Set<E>`
    Specified by:
      `iterator` in class `AbstractCollection<E>`

  - ### remove

    public boolean remove(Object o)
    Specified by:
      `remove` in interface `Collection<E>`
    Specified by:
      `remove` in interface `Set<E>`
    Overrides:
      `remove` in class `AbstractCollection<E>`

  - ### removeAll

    public boolean removeAll(Collection<?> c)
    Specified by:
      `removeAll` in interface `Collection<E>`
    Specified by:
      `removeAll` in interface `Set<E>`
    Overrides:
      `removeAll` in class `AbstractSet<E>`

  - ### retainAll

    public boolean retainAll(Collection<?> c)
    Specified by:
      `retainAll` in interface `Collection<E>`
    Specified by:
      `retainAll` in interface `Set<E>`
    Overrides:
      `retainAll` in class `AbstractCollection<E>`

  - ### size

    public int size()
    Specified by:
      `size` in interface `Collection<E>`
    Specified by:
      `size` in interface `Set<E>`
    Specified by:
      `size` in class `AbstractCollection<E>`

  - ### spliterator

    public Spliterator<E> spliterator()

  - ### update

    public boolean update(E e)
    Notify the queue of a change to an element's cost.

    This may cause the element's index to change.

    Parameters:
      `e` - the element whose cost may have changed
    Returns:
      true if the index changed