trait PeanoQueue[K, V] extends AnyRef

A Peano priority queue is a mutable priority queue of key-value pairs with ordered keys, starting from an index called the head, where pairs may be added in any order, but are polled strictly in their natural sequence. The order on keys must be a linear sequence, i.e., isomorphic to the order on a possibly unbounded interval of the integers. If the priority queue is missing a key from the sequence, we cannot poll that key until a key-value pair for that key is added.

For example, in a priority queue with head 1, the keys polled are 1, then 2, then 3, etc.

The head index is mutable, and increments each time the priority queue is successfully polled. Keys are unique and their value associations may not be modified.

K

The type of keys

V

The type of values

Linear Supertypes
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. PeanoQueue
  2. AnyRef
  3. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. Protected

Abstract Value Members

  1. abstract def alreadyInserted(key: K): Boolean

    Whether the key key has already been insert-ed to the PeanoQueue.

    Whether the key key has already been insert-ed to the PeanoQueue. All values below the PeanoQueue.front are considered to have been inserted to the PeanoQueue, even if they are below the initial PeanoQueue.head.

  2. abstract def front: K

    Returns the front of the PeanoQueue.

    Returns the front of the PeanoQueue.

    The front is defined as the least key that is at least PeanoQueue.head and that has not yet been inserted into the PeanoQueue.

  3. abstract def get(key: K): AssociatedValue[V]

    Returns the value associated with the given key.

  4. abstract def head: K

    Returns the head of the PeanoQueue.

    Returns the head of the PeanoQueue.

    The head denotes the next key to be pulled. The head key need not yet have been inserted into the PeanoQueue.

  5. abstract def insert(key: K, value: V): Boolean

    Inserts the key-value pair (key, value) to the PeanoQueue.

    Inserts the key-value pair (key, value) to the PeanoQueue. This may change the value for PeanoQueue.front

    Inserting a key-value pair is idempotent. If the keys are bounded from above, then the maximal value must not be inserted.

    key

    The key to be inserted. If the key has been added previously, then the following applies:

    value

    The value associated with the key.

    returns

    whether the key is at least PeanoQueue.head

    Exceptions thrown

    java.lang.IllegalArgumentException if the keys are bounded from above and key is the maximal value, or if the key is above PeanoQueue.head and has been added with a different value.

  6. abstract def poll(): Option[(K, V)]

    Returns and drops the key at PeanoQueue.head and its associated value, if present.

    Returns and drops the key at PeanoQueue.head and its associated value, if present. If so, this also increments PeanoQueue.head. Returns scala.None to indicate that the key PeanoQueue.head has not yet been inserted.

Concrete Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##: Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  5. def clone(): AnyRef
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.CloneNotSupportedException]) @native() @IntrinsicCandidate()
  6. def dropUntilFront(): Option[(K, V)]

    Drops all elements from the PeanoQueue below the front and sets head to front.

    Drops all elements from the PeanoQueue below the front and sets head to front.

    returns

    scala.None$ if the head already was at the front or the value associated with the last value before head otherwise.

  7. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  8. def equals(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef → Any
  9. final def getClass(): Class[_ <: AnyRef]
    Definition Classes
    AnyRef → Any
    Annotations
    @native() @IntrinsicCandidate()
  10. def hashCode(): Int
    Definition Classes
    AnyRef → Any
    Annotations
    @native() @IntrinsicCandidate()
  11. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  12. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  13. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @IntrinsicCandidate()
  14. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @IntrinsicCandidate()
  15. final def synchronized[T0](arg0: => T0): T0
    Definition Classes
    AnyRef
  16. def toString(): String
    Definition Classes
    AnyRef → Any
  17. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  18. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException]) @native()
  19. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])

Deprecated Value Members

  1. def finalize(): Unit
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.Throwable]) @Deprecated @Deprecated
    Deprecated

Inherited from AnyRef

Inherited from Any

Ungrouped