Queue

Double-ended queue of a generic element type T.

The interface is imperative, not purely functional. In particular, Queue operations such as push and pop update their input queue instead of returning the value of the modified Queue.

Examples of use-cases: Queue (FIFO) by using pushBack() and popFront(). Stack (LIFO) by using pushFront() and popFront().

A Queue is internally implemented as two lists, a head access list and a (reversed) tail access list, that are dynamically size-balanced by splitting.

Construction: Create a new queue with the empty<T>() function.

Note on the costs of push and pop functions:

n denotes the number of elements stored in the queue.

type Queue<T> = { var immutable : Immutable.Queue<T> }

public func freeze<T>(queue : Queue<T>) : Immutable.Queue<T>

public func thaw<T>(queue : Immutable.Queue<T>) : Queue<T>

public func empty<T>() : Queue<T>

public func singleton<T>(item : T) : Queue<T>

public func clear<T>(queue : Queue<T>)

public func clone<T>(queue : Queue<T>) : Queue<T>

public func isEmpty<T>(queue : Queue<T>) : Bool

public func size<T>(queue : Queue<T>) : Nat

public func contains<T>(queue : Queue<T>, item : T) : Bool

public func peekFront<T>(queue : Queue<T>) : ?T

public func peekBack<T>(queue : Queue<T>) : ?T

public func push<T>(queue : Queue<T>, element : T) : ()

public func pop<T>(queue : Queue<T>) : ?T

public func pushFront<T>(queue : Queue<T>, element : T) : ()

public func pushBack<T>(queue : Queue<T>, element : T) : ()

public func popFront<T>(queue : Queue<T>) : ?T

public func popBack<T>(queue : Queue<T>) : ?T

public func fromIter<T>(iter : Iter.Iter<T>) : Queue<T>

public func values<T>(queue : Queue<T>) : Iter.Iter<T>

public func all<T>(queue : Queue<T>, predicate : T -> Bool) : Bool

public func any<T>(queue : Queue<T>, predicate : T -> Bool) : Bool

public func forEach<T>(queue : Queue<T>, f : T -> ())

public func map<T1, T2>(queue : Queue<T1>, f : T1 -> T2) : Queue<T2>

public func filter<T>(queue : Queue<T>, f : T -> Bool) : Queue<T>

public func filterMap<T, U>(queue : Queue<T>, f : T -> ?U) : Queue<U>

public func equal<T>(queue1 : Queue<T>, queue2 : Queue<T>) : Bool

public func toText<T>(queue : Queue<T>, f : T -> Text) : Text

public func compare<T>(
  queue1 : Queue<T>,
  queue2 : Queue<T>,
  compare : (T, T) -> Order.Order
) : Order.Order