ADTVector

The Vector module implements resizable container. It is fast to append and remove at end of array. and fast for random access to elements.

If life time handling of allocated elements is needed the callback procedures duplicate and dispose can be used.

By default the vectors only takes references of elements and the caller is responsible for keeping elements alive.

Types

DuplicateElementProc* = PROCEDURE(VAR dst: Element;

Procedures

DefaultDuplicateElement

defaults to assignment

PROCEDURE DefaultDuplicateElement* (VAR dst: Element; src-: Element);

DefaultDisposeElement

defaults to no operation

PROCEDURE DefaultDisposeElement* (VAR dst: Element);

Vector.Init

Initialize

PROCEDURE (VAR this : Vector) Init*(size : LENGTH);

Vector.Size

Length of vector

PROCEDURE (VAR this- : Vector) Size*(): LENGTH;

Vector.Capacity

Item capacity of vector

PROCEDURE (VAR this- : Vector) Capacity*(): LENGTH;

Vector.Clear

Clear Vector to zero size

PROCEDURE (VAR this : Vector) Clear*();

Vector.Dispose

Free storage

PROCEDURE (VAR this : Vector) Dispose*();

Vector.Reserve

Resize storage to accomodate capacity

PROCEDURE (VAR this : Vector) Reserve*(capacity  : LENGTH);

Vector.Shrink

Shrink storage

PROCEDURE (VAR this : Vector) Shrink*();

Vector.Append

Append Element to end of Vector

PROCEDURE (VAR this : Vector) Append*(value- : Element);

Vector.At

Return value at idx. Note this may return a reference to a element.

PROCEDURE (VAR this- : Vector) At*(idx : LENGTH): Element;

Vector.Set

Set value at idx

PROCEDURE (VAR this : Vector) Set*(idx : LENGTH; value- : Element);

Vector.Get

Get value at idx.

Note: this potentially set the value to a reference.

PROCEDURE (VAR this : Vector) Get*(idx : LENGTH; VAR value : Element);

Vector.Pop

Remove and return last element of vector. Return FALSE if vector is empty. Note: this potentially transfere key ownership to caller.

PROCEDURE (VAR this : Vector) Pop*(VAR element : Element) : BOOLEAN;

Vector.Reverse

Reverse array in-place

PROCEDURE (VAR this : Vector) Reverse*();

Vector.Shuffle

Random shuffle array in-place

PROCEDURE (VAR this : Vector) Shuffle*();

Vector.Sort

Sort array in-place (QuickSort)

PROCEDURE (VAR this : Vector) Sort* (Cmp : Compare);

Vector.Find

Find position in array. Expect array to be sorted in ascending order. Return -1 if not found.

PROCEDURE (VAR this- : Vector) Find* (Cmp : Compare; value- : Element): LENGTH;

Vector.BisectLeft

Find leftmost insertion position in array for value. Expect array to be sorted in ascending order.

PROCEDURE (VAR this- : Vector) BisectLeft* (Cmp : Compare; value- : Element): LENGTH;

Vector.BisectRight

Find rightmost insertion position in array for value. Expect array to be sorted in ascending order.

PROCEDURE (VAR this- : Vector) BisectRight* (Cmp : Compare; value- : Element): LENGTH;

Vector.HeapSiftDown

move a node down in the tree to restore heap relationship

PROCEDURE (VAR this : Vector) HeapSiftDown*(Cmp : Compare; i : LENGTH);

Vector.Heapify

Heapify array in-place

PROCEDURE (VAR this : Vector) Heapify*(Cmp : Compare);

Vector.HeapPop

Remove first element of heap. Return FALSE if heap is empty. Note: this potentially transfere key ownership to caller.

PROCEDURE (VAR this : Vector) HeapPop*(Cmp : Compare; VAR element : Element) : BOOLEAN;

Vector.HeapInsert

Insert Element into Vector and update heap relationship

PROCEDURE (VAR this : Vector) HeapInsert*(Cmp : Compare; value : Element);