abstract class PQueue[F[_], A] extends PQueueSource[F, A] with PQueueSink[F, A]
A purely functional Priority Queue implementation based on a binomial heap (Okasaki)
Assumes an Order instance is in scope for A
- Self Type
- PQueue[F, A]
- Source
- PQueue.scala
- Alphabetic
- By Inheritance
- PQueue
- PQueueSink
- PQueueSource
- AnyRef
- Any
- Hide All
- Show All
- Public
- Protected
Instance Constructors
- new PQueue()
Abstract Value Members
- abstract def offer(a: A): F[Unit]
Enqueues the given element, possibly fiber blocking until sufficient capacity becomes available.
Enqueues the given element, possibly fiber blocking until sufficient capacity becomes available.
O(log(n))
- a
the element to be put in the PQueue
- Definition Classes
- PQueueSink
- abstract def size: F[Int]
- Definition Classes
- PQueueSource
- abstract def take: F[A]
Dequeues the least element from the PQueue, possibly fiber blocking until an element becomes available.
Dequeues the least element from the PQueue, possibly fiber blocking until an element becomes available.
O(log(n))
Note: If there are multiple elements with least priority, the order in which they are dequeued is undefined. If you want to break ties with FIFO order you will need an additional
Ref[F, Long]to track insertion, and embed that information into your instance forOrder[A].- Definition Classes
- PQueueSource
- abstract def tryOffer(a: A): F[Boolean]
Attempts to enqueue the given element without fiber blocking.
Attempts to enqueue the given element without fiber blocking.
O(log(n))
- a
the element to be put in the PQueue
- returns
an effect that describes whether the enqueuing of the given element succeeded without blocking
- Definition Classes
- PQueueSink
- abstract def tryTake: F[Option[A]]
Attempts to dequeue the least element from the PQueue, if one is available without fiber blocking.
Attempts to dequeue the least element from the PQueue, if one is available without fiber blocking.
O(log(n))
- returns
an effect that describes whether the dequeueing of an element from the PQueue succeeded without blocking, with
Nonedenoting that no element was available Note: If there are multiple elements with least priority, the order in which they are dequeued is undefined. If you want to break ties with FIFO order you will need an additionalRef[F, Long]to track insertion, and embed that information into your instance forOrder[A].
- Definition Classes
- PQueueSource
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()
- final def eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- def equals(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef → Any
- def finalize(): Unit
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.Throwable])
- final def getClass(): Class[_ <: AnyRef]
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
- def hashCode(): Int
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
- final def isInstanceOf[T0]: Boolean
- Definition Classes
- Any
- def mapK[G[_]](f: ~>[F, G]): PQueue[G, A]
Modifies the context in which this PQueue is executed using the natural transformation
f.Modifies the context in which this PQueue is executed using the natural transformation
f.O(1)
- returns
a PQueue in the new context obtained by mapping the current one using
f
- final def ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- final def notify(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
- final def notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
- final def synchronized[T0](arg0: => T0): T0
- Definition Classes
- AnyRef
- def toString(): String
- Definition Classes
- AnyRef → Any
- def tryOfferN(list: List[A])(implicit F: Monad[F]): F[List[A]]
Attempts to enqueue the given elements without semantically blocking.
Attempts to enqueue the given elements without semantically blocking. If an item in the list cannot be enqueued, the remaining elements will be returned. This is a convenience method that recursively runs
tryOfferand does not offer any additional performance benefits.- list
the elements to be put in the PQueue
- returns
an effect that contains the remaining valus that could not be offered.
- Definition Classes
- PQueueSink
- def tryTakeN(maxN: Option[Int])(implicit F: Monad[F]): F[List[A]]
Attempts to dequeue elements from the PQueue, if they are available without semantically blocking.
Attempts to dequeue elements from the PQueue, if they are available without semantically blocking. This is a convenience method that recursively runs
tryTake. It does not provide any additional performance benefits.- maxN
The max elements to dequeue. Passing
Nonewill try to dequeue the whole queue.- returns
an effect that contains the dequeued elements from the PQueue Note: If there are multiple elements with least priority, the order in which they are dequeued is undefined.
- Definition Classes
- PQueueSource
- final def wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- 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()