Deque<T> structv0.1.0

pub struct Deque<T> {
    // private fields
}

Move-only: it owns its elements and storage, prohibits copying, and destroys both with ~Deque.

Type parameters

Constructors

Deque

pub func Deque(allocator: Allocator) -> Deque<T>

An empty deque that has not allocated anything. allocator is borrowed for the call and kept. Costs nothing: a deque that is never pushed to never allocates. Cannot fail. Runs in constant time.

Returns: an empty collection that has taken no storage yet

Source

Associated functions

WithCapacity

pub func WithCapacity(
    allocator: Allocator,
    capacity: uint
) -> Deque<T> ! CollectionError

An empty deque with room for capacity elements already taken. allocator is borrowed for the call and kept. The capacity actually taken is rounded up to a power of two, since that is what the ring's masking needs.

Returns: an empty deque with room for that many elements already taken

Source

FromSlice

pub func FromSlice(
    allocator: Allocator,
    items: T[..]
) -> Deque<T> ! CollectionError

A deque holding a copy of every element of items, front to back. allocator is borrowed for the call and kept; items is borrowed and read. Copies its elements, so a move-only element type is built with PushBack instead.

Returns: a deque holding a copy of those elements

Source

Methods

Clone

pub func Clone(self: &Deque<T>) -> Deque<T> ! CollectionError

An independent deque holding a copy of every element of this one, in order. self is borrowed and left alone. The copy starts contiguous whatever this one's elements were doing.

Returns: an independent copy

Source

Length

pub func Length(self: &Deque<T>) -> uint

How many elements the deque holds. self is borrowed.

Returns: how many elements it holds

Source

Capacity

pub func Capacity(self: &Deque<T>) -> uint

How many elements the ring could hold without growing. self is borrowed. A power of two, or zero.

Returns: how many elements fit before the next growth

Source

IsEmpty

pub func IsEmpty(self: &Deque<T>) -> bool

Whether the deque holds no elements. self is borrowed.

Returns: whether it holds nothing

Source

Reserve

pub func Reserve(
    self: &var Deque<T>,
    additional: uint
) -> ! CollectionError

Makes room for additional more elements on top of those already present. self is borrowed mutably; the length does not change. A failure leaves the deque exactly as it was.

Returns: nothing when the operation succeeded, or why it did not

Source

ShrinkToFit

pub func ShrinkToFit(self: &var Deque<T>) -> ! CollectionError

Releases the capacity the length does not need. self is borrowed mutably. The capacity stays a power of two, so this gives back what rounding leaves spare rather than everything above the length. An empty deque gives up its storage entirely. A failure leaves the deque usable at its current capacity: failing to hand memory back is never a reason to stop working.

Returns: nothing when the operation succeeded, or why it did not

Source

Clear

pub func Clear(self: &var Deque<T>)

Destroys every element, keeping the storage. self is borrowed mutably. The front returns to physical zero, so the next run of additions does not wrap. Runs in time proportional to the length.

Source

PushFront

pub func PushFront(
    self: &var Deque<T>,
    value: T
) -> ! CollectionError

Adds an element at the front, growing the ring when it is full. self is borrowed mutably; value is moved in. A failure leaves the deque exactly as it was and the value with the caller. Amortized constant time.

Returns: nothing when the operation succeeded, or why it did not

Source

PushBack

pub func PushBack(
    self: &var Deque<T>,
    value: T
) -> ! CollectionError

Adds an element at the back, growing the ring when it is full. self is borrowed mutably; value is moved in. A failure leaves the deque exactly as it was. Amortized constant time.

Returns: nothing when the operation succeeded, or why it did not

Source

PopFront

pub func PopFront(self: &var Deque<T>) -> T?

Takes the front element out. self is borrowed mutably. The element is moved out and handed to the caller rather than destroyed, so one that owns something leaves intact. Reports none for an empty deque. The storage is kept, so a deque emptied this way costs nothing to refill.

Returns: the element taken from the front, or none when empty

Source

PopBack

pub func PopBack(self: &var Deque<T>) -> T?

Takes the back element out. self is borrowed mutably. The element is moved out and handed to the caller. Reports none for an empty deque.

Returns: the element taken from the back, or none when empty

Source

Front

pub func Front(self: &Deque<T>) -> (*T)?

A pointer to the front element, or none for an empty deque. self is borrowed; the pointer borrows the element where it sits. The pointer is valid until the deque grows, shrinks, or is made contiguous.

Returns: the address of the first element, or none when empty

Source

Back

pub func Back(self: &Deque<T>) -> (*T)?

A pointer to the back element, or none for an empty deque. self is borrowed; the pointer borrows the element where it sits.

Returns: the address of the last element, or none when empty

Source

Get

pub func Get(self: &Deque<T>, index: uint) -> T?

The element at index, counting from the front, or none when there is no such index. self is borrowed; the element is returned by copy. The index is logical: element zero is the front wherever it happens to sit physically.

Returns: a copy of the element, or none when the index is out of range

Source

Reference

pub func Reference(self: &Deque<T>, index: uint) -> (*T)?

A pointer to the element at index, or none when there is no such index. self is borrowed; the pointer borrows the element where it sits. The pointer is valid until the deque grows, shrinks, or is made contiguous.

Returns: the address of the element, or none when the index is out of range

Source

Set

pub func Set(
    self: &var Deque<T>,
    index: uint,
    value: T
) -> ! CollectionError

Replaces the element at index with value. self is borrowed mutably. Reports IndexOutOfRange and changes nothing when there is no such index. The old element is overwritten rather than destroyed. For an element that owns something, take it out first.

Returns: nothing when the element was written, or IndexOutOfRange

Source

IsContiguous

pub func IsContiguous(self: &Deque<T>) -> bool

Whether the elements occupy one unbroken run. self is borrowed. True for an empty deque and for one whose elements have not wrapped past the end of the ring. This is what says whether AsSlice will move anything.

Returns: whether the elements sit in one run, which is what AsSlice needs

Source

AsSlices

pub func AsSlices(
    self: &Deque<T>,
    front: *var T[..],
    back: *var T[..]
)

The elements as at most two runs, front run first, without moving anything. self is borrowed; front and back receive the two runs and either may be null. The second run is empty whenever the storage is already contiguous, so joining the two always gives the elements in order. This is the view that costs nothing. AsSlice gives one run instead, and pays a rotation for it. Both views are valid until the deque grows, shrinks, or is made contiguous.

Source

MakeContiguous

pub func MakeContiguous(self: &var Deque<T>)

Moves the elements so they occupy one unbroken run starting at physical zero. self is borrowed mutably. Allocates nothing: rotating the whole ring left by the head brings the front element to zero and preserves cyclic order for every slot at once, so no element has to be tracked individually. Every pointer and view into the deque is invalidated, and so is any physical index a caller recorded.

Source

AsSlice

pub func AsSlice(self: &var Deque<T>) -> T[..]

Every element as one borrowed read-only view, moving them together first. self is borrowed mutably — unlike a vector's, producing a single view can move the elements, which is why this asks for a writable receiver rather than a read-only one. The view is valid until the deque grows, shrinks, or is made contiguous again.

Returns: the elements, borrowed; empty unless the storage is contiguous

Source

AsMutableSlice

pub func AsMutableSlice(self: &var Deque<T>) -> var T[..]

Every element as one borrowed writable view, moving them together first. self is borrowed mutably. The view is valid until the deque grows, shrinks, or is made contiguous again.

Returns: the elements borrowed for writing; empty unless the storage is contiguous

Source

Iterate

pub func Iterate(self: &var Deque<T>) -> ValueIterator<T>

An iterator over the elements, front to back, by copy. self is borrowed mutably and must outlive the iterator, and the elements are moved together first so one run can be walked. This is the method a for loop finds. The deque must not grow or shrink while the iterator is alive.

Returns: a cursor yielding copies of the elements, front to back

Source

References

pub func References(self: &var Deque<T>) -> ReferenceIterator<T>

An iterator over pointers to the elements, front to back. self is borrowed mutably and must outlive the iterator, and the elements are moved together first.

Returns: a cursor yielding the elements' addresses, front to back

Source

Destructor

func ~Deque(self: &var Deque<T>)

Destroys every element and releases the storage. Runs when the deque's life ends. The elements go first and the block second, since an element destroyed after its storage was released would be read from freed memory.

Source

Related

MinimumDequeCapacity

pub const MinimumDequeCapacity: uint = 4;

The capacity a deque takes when it first has to allocate. Four slots, and a power of two like every capacity after it.

Source

WriteDequeDebug<T>

pub func WriteDequeDebug<T: Debug>(
    writer: &var TextWriter,
    value: &Deque<T>,
    spec: FormatSpec
) -> ! FormatError

Writes a borrowed deque as [front, ..., back], front element first. The order is the deque's own — what PopFront would yield, in the order it would yield it — whether or not the ring has wrapped. A wrapped deque holds its elements in two runs, and both are walked inside one pair of brackets, so where the ring happens to be split is not visible in the output and does not need to be. Nothing is rearranged to write it: this is the reason the deque is borrowed rather than borrowed mutably, since making the elements contiguous first would be a diagnostic quietly moving a caller's data around. spec describes the elements, exactly as for a vector. Reports whatever the writer or an element's implementation reported, stopping at the first refusal.

Source

Type parameters

Parameters

Returns: success when the whole rendering was accepted