Queue

This module provides functionalities as one-way queue. The worst-case time complexity of enqueue and dequeue is O(1).

Types

type Queue a

Represents one-way queue for any contents.

Creation

empty : Queue a

Represents queue with no element.

empty |> isEmpty --> True


empty |> head --> Nothing


empty |> rear --> Nothing

fromListLIFO : List a -> Queue a

Converts a List to a Queue in a way that last-in element in the list becomes first-out element in the queue.

list : List String
list =
    []
        |> (::) "m"
        |> (::) "l"
        |> (::) "e" -- Here is last-in element.


queue : Queue String
queue =
    fromListLIFO list


head queue --> Just "e"


rear queue --> Just "m"

fromListFIFO : List a -> Queue a

Converts a List to a Queue in a way that first-in element in the list becomes first-out element in the queue.

list : List String
list =
    []
        |> (::) "m" -- Here is first-in element.
        |> (::) "l"
        |> (::) "e"


queue : Queue String
queue =
    fromListFIFO list


head queue --> Just "m"


rear queue --> Just "e"

Query

isEmpty : Queue a -> Bool

Returns True if and only if the queue has no element.

empty
    |> isEmpty
        -->
        True


empty
    |> enqueue "test"
    |> isEmpty
        -->
        False

isEqualTo : Queue a -> Queue a -> Bool

Compare the contents and the order in two queues. Returns True if and only if all the elements contained and the orders are the same. Note that comparison in == may return false even if the contents are the same, because there is some redunduncy in the inner structure of the queue. Takes O(n) time.

q1 : Queue String
q1 =
    empty
        |> enqueue "e"
        |> enqueue "l"
        |> enqueue "m"
        |> dequeue


q2 : Queue String
q2 =
    empty
        |> enqueue "e"
        |> dequeue
        |> enqueue "l"
        |> enqueue "m"


q3 : Queue String
q3 =
    empty
        |> enqueue "m"
        |> enqueue "l"
        |> enqueue "e"
        |> dequeue


q1 |> isEqualTo q2 --> True


q1 |> isEqualTo q3 --> False

head : Queue a -> Maybe a

Returns the oldest element in the queue wrapped in Maybe. Takes O(1) time.

queue : Queue String
queue =
    empty
        |> enqueue "e"
        |> enqueue "l"
        |> enqueue "m"


head queue --> Just "e"


head empty --> Nothing

rear : Queue a -> Maybe a

Returns the newest element in the queue wrapped in Maybe. Takes _O(log_n)_ time at worst case.

queue : Queue String
queue =
    empty
        |> enqueue "e"
        |> enqueue "l"
        |> enqueue "m"


rear queue --> Just "m"


rear empty --> Nothing

length : Queue a -> Int

Returns how many elements the Queue has. Takes _O(log_n)_ time.

Update

enqueue : a -> Queue a -> Queue a

Returns a queue with the given element attached on the rear side.

empty
    |> enqueue "e"
    -- first in
    |> enqueue "l"
    |> enqueue "m"
    |> toListFIFO
        -->
        [ "e", "l", "m" ]

dequeue : Queue a -> Queue a

Returns a queue with the oldest element removed.

intermediateQueue =
    empty
        |> enqueue "e" -- this will be removed
        |> enqueue "l" -- first-in element in the final queue.
        |> enqueue "m"


finalQueue =
    dequeue intermediateQueue


finalQueue
    |> toListFIFO -->
        [ "l"
        , "m"
        ]

map : (a -> b) -> Queue a -> Queue b

Updates all elements in the Queue with given function.

 [1, 2, 3]
    |> fromListLIFO
    |> map (\x -> x * x)
    |> map (String.fromInt)
    |> toListLIFO --> ["9","4","1"]

Deconstruction

toListLIFO : Queue a -> List a

Converts a Queue to a List in a way that last-in element in the queue becomes first-out element in the list.

queue : Queue String
queue =
    empty
        |> enqueue "e"
        |> enqueue "l"
        |> enqueue "m" --Here is last-in element.


toListLIFO queue --> ["m","l","e"]

toListFIFO : Queue a -> List a

Converts a Queue to a List in a way that first-in element in the queue becomes first-out element in the list.

queue : Queue String
queue =
    empty
        |> enqueue "e" --Here is last-in element.
        |> enqueue "l"
        |> enqueue "m"


toListFIFO queue --> ["e","l","m"]

fold : (c -> a -> a) -> a -> Queue c -> a

produces one value that sums up the all elements in the queue. The fold function is applied in the order of insertion.

 ["e", "l", "m"]
    |> fromListLIFO
    |> fold (++) "" --> "mle"

Modules

Queue

kudzu-forest/elm-constant-time-queue/1.4.0