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
- Alphabetic
- By Inheritance
- PeanoQueue
- AnyRef
- Any
- Hide All
- Show All
- Public
- Protected
Abstract Value Members
- abstract def alreadyInserted(key: K): Boolean
Whether the key
key
has already beeninsert
-ed to the PeanoQueue.Whether the key
key
has already beeninsert
-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. - 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.
- abstract def get(key: K): AssociatedValue[V]
Returns the value associated with the given
key
. - 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.
- 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.frontInserting 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:
- If the key is below PeanoQueue.head, then this insert operation has no effect.
- If the key is at least PeanoQueue.head and the value is the same, this operation has no effect.
- If the key is at least PeanoQueue.head and the value is different, then the PeanoQueue is not changed and an java.lang.IllegalArgumentException is thrown.
- 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 andkey
is the maximal value, or if thekey
is above PeanoQueue.head and has been added with a different value.
- 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
- final def !=(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- final def ##: Int
- Definition Classes
- AnyRef → Any
- final def ==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- final def asInstanceOf[T0]: T0
- Definition Classes
- Any
- def clone(): AnyRef
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.CloneNotSupportedException]) @native() @IntrinsicCandidate()
- 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.
- final def eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- def equals(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef → Any
- final def getClass(): Class[_ <: AnyRef]
- Definition Classes
- AnyRef → Any
- Annotations
- @native() @IntrinsicCandidate()
- def hashCode(): Int
- Definition Classes
- AnyRef → Any
- Annotations
- @native() @IntrinsicCandidate()
- final def isInstanceOf[T0]: Boolean
- Definition Classes
- Any
- final def ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- final def notify(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native() @IntrinsicCandidate()
- final def notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native() @IntrinsicCandidate()
- final def synchronized[T0](arg0: => T0): T0
- Definition Classes
- AnyRef
- def toString(): String
- Definition Classes
- AnyRef → Any
- final def wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- final def wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException]) @native()
- final def wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])