RVS_FIFOQueue

public struct RVS_FIFOQueue<Element> : OLEB_Queue
extension RVS_FIFOQueue: ExpressibleByArrayLiteral
extension RVS_FIFOQueue: MutableCollection

An efficient variable-size FIFO queue of elements of type “Element.”

  • This is the “delivery” queue. Elements are removed, one by one, from the top of this queue. When the queue is empty, and a request is made for an element, it first asks for the reveresed contents of the right queue, which is then emptied.

    Declaration

    Swift

    private var _leftQueue: [Element]

  • This is the “staging queue.” We add elements, one by one, to the top of this queue.

    Declaration

    Swift

    private var _rightQueue: [Element]

  • This will push the single element into the 0th (first) place. It is not an efficient operation, but may be necessary, in some cases.

    Declaration

    Swift

    mutating public func cutTheLine(_ inNewElement: Element)

    Parameters

    inNewElement

    The Element to be enqueued (placed on the front of the list).

  • Add an Element to the end of the queue.

    Complexity

    O(1).

    Declaration

    Swift

    mutating public func enqueue(_ inNewElement: Element)

    Parameters

    inNewElement

    The Element to be enqueued (placed on the end of the list).

  • Add an Array of Element to the end of the queue.

    Complexity

    O(n), where n is the number of elements in the input Array.

    Declaration

    Swift

    mutating public func enqueue(_ inNewElements: [Element])

    Parameters

    inNewElements

    The Elements to be enqueued (placed on the end of the list). They are appened in the order presented.

  • Removes and returns from the front of the queue. Returns nil for an empty queue.

    Complexity

    Amortized O(1). The “Amortized” is because there’s a one-time “charge” for dumping the right queue into the left queue. The way that this works, is that the right queue is a “staging” queue. It’s cheap to shove elements onto the top. We remove elements from the top of the left queue, so there’s no moving of memory. When the left queue is empty, we dump the entire right (staging) queue into it, as reversed. The idea is to keep all the operations on the tops of the queues. That prevents massive memory movements every time we access the bottom.

    Declaration

    Swift

    @discardableResult
mutating public func dequeue() -> Element?

    Return Value

    The first Element. Nil, if none. Can be ignored.

  • Deletes all data in the queue.

    Complexity

    O(1).

    Declaration

    Swift

    mutating public func removeAll()

ExpressibleByArrayLiteral Support

  • Variadic initializer.

    Declaration

    Swift

    public init(arrayLiteral inElements: Element...)

MutableCollection Support

  • Declaration

    Swift

    public var startIndex: Int { get }

    Return Value

    0. The start is always 0.

  • Declaration

    Swift

    public var endIndex: Int { get }

    Return Value

    The length of both internal queues, combined.

  • Declaration

    Swift

    public func index(after inIndex: Int) -> Int

    Parameters

    after

    The index we want to get after.

    Return Value

    The input plus one (Can’t get simpler than that). It can return the endIndex, which is past the last element.

  • Declaration

    Swift

    public subscript(inPosition: Int) -> Element { get set }

    Parameters

    inPosition

    The position of the element we are working on.

    Return Value

    The element we are subscripting.