WOLFRAM

Wolfram Language & System Documentation Center

"ExtensibleVector" (Data Structure)

"ExtensibleVector"

represents a dynamically extensible vector where the elements are general expressions.

Details

  • An extensible vector is useful for continuously appending and prepending elements, as well as for efficient element extraction and updating.
  • CreateDataStructure[ "ExtensibleVector"]create a new empty "ExtensibleVector"
    CreateDataStructure[ "ExtensibleVector",elems]create a new "ExtensibleVector"containing elems
    Typed[x,"ExtensibleVector"]give x the type "ExtensibleVector"
  • For a data structure of type "ExtensibleVector", the following operations can be used:
  • ds["Append",x]append x to dstime: O(1)
    ds["Copy"]return a copy of dstime: O(n)
    ds["Drop",i]drop the i^(th) part of dstime: O(n)
    ds["DropAll"]drop all the elements from dstime: O(n)
    ds["DropLast"]drop the last element of dstime: O(1)
    ds["Elements"]return a list of the elements of dstime: O(n)
    ds["EmptyQ"]True, if ds has no elementstime: O(1)
    		ds["Fold",fun]apply fun to the elements of ds, accumulating a resulttime: O(n)
    ds["Fold",fun,init]apply fun to the elements of ds, starting with init, accumulating a resulttime: O(n)
    ds["Insert",x,i ]insert x into ds at position itime: O(1)
    ds["JoinBack",elems ]join elems to the back of dstime: O(nelems)
    ds["JoinFront",elems ]join elems to the front of dstime: O(nelems)
    ds["Length"]the number of elements stored in dstime: O(1)
    ds["Part",i]give the i^(th) part of dstime: O(1)
    ds["Prepend",x]prepend x to dstime: O(1)
    ds["SetPart",i,elem]update the i^(th) part of dstime: O(1)
    ds["SwapPart",i,j]swap the i^(th) and j^(th) parts of dstime: O(1)
    ds["Visualization"]return a visualization of dstime: O(n)
  • The following functions are also supported:
  • dsi===dsjTrue, if dsi equals dsj
    ds["Part",i]=valset i^(th) element of ds to val
    FullForm[ds]full form of ds
    Information[ds]information about ds
    InputForm[ds]input form of ds
    Normal[ds]convert ds to a normal expression

Examples

open all close all

Basic Examples  (2)

A new "ExtensibleVector" can be created with CreateDataStructure:

Wolfram Language code: ds = CreateDataStructure["ExtensibleVector"]

Elements can be appended:

Wolfram Language code: ds["Append", f[1]]

Elements can be prepended:

Wolfram Language code: ds["Prepend", f[5]]

Return the length:

Wolfram Language code: ds["Length"]

Extract the first element:

Wolfram Language code: ds["Part", 1]

Change an element:

Wolfram Language code: ds["Part", 1] = f[2]

The element has updated:

Wolfram Language code: ds["Part", 1]

Return an expression version of ds:

Wolfram Language code: Normal[ds]

It is fast to append:

Wolfram Language code: ds = CreateDataStructure["ExtensibleVector"]; Do[ds["Append", i], {i, 1000}]

A visualization of the data structure can be generated:

Wolfram Language code: ds["Visualization"]

Sum all the elements:

Wolfram Language code: ds["Fold", Plus, 0]

Scope  (1)

Information  (1)

A new "ExtensibleVector" can be created with CreateDataStructure:

Wolfram Language code: ds = CreateDataStructure["ExtensibleVector"]

Information about the data structure ds:

Wolfram Language code: Information[ds]

Applications  (11)

Reverse  (1)

A simple function that carries out an in-place reverse of a "ExtensibleVector":

Wolfram Language code: ArrayReverse[ ds : DataStructure["ExtensibleVector", _]] := Module[{start = 0, end = ds["Length"] + 1}, While[++start < --end, ds["SwapPart", start, end] ]; ds];

A sample data structure to use:

Wolfram Language code: ds = CreateDataStructure["ExtensibleVector", {9, 2, 7, 0}];

Reverse the elements:

Wolfram Language code: Normal[ArrayReverse[ds]]

Bubble Sort  (1)

Bubble sort is a simple sorting algorithm that is easy to code but typically has poor performance:

Wolfram Language code: BubbleSort[ ds : DataStructure["ExtensibleVector", _]] := Module[{repeat = True}, While[repeat, repeat = False; Do[ If[ds["Part", i] > ds["Part", i + 1], ds["SwapPart", i, i + 1]; repeat = True];, {i, ds["Length"] - 1}]]; ds];

A sample data structure to use:

Wolfram Language code: ds = CreateDataStructure["ExtensibleVector", {9, 2, 7, 0}];

Sort the elements:

Wolfram Language code: Normal[BubbleSort[ds]]

The data structure is sorted in place:

Wolfram Language code: Normal[ds]

Insertion Sort  (1)

Insertion sort is a simple sorting algorithm that is easy to code and typically has poor performance for large arrays, but can be useful for small arrays:

Wolfram Language code: InsertionSort[ ds : DataStructure["ExtensibleVector", _]] := Module[{len, i, j}, len = ds["Length"]; Do[j = i; While[j > 1 && ds["Part", j - 1] > ds["Part", j], ds["SwapPart", j, j - 1];j--], {i, 2, len}]; ds]

A sample data structure to use:

Wolfram Language code: ds = CreateDataStructure["ExtensibleVector", {9, 2, 7, 0}];

Sort the elements:

Wolfram Language code: Normal[InsertionSort[ds]]

The data structure is sorted in place:

Wolfram Language code: Normal[ds]

Quicksort  (1)

Quicksort is an efficient sorting algorithm. This basic implementation uses nested functions:

Wolfram Language code: Quicksort[ ds : DataStructure["ExtensibleVector", _]] := Module[{partitionFun, sortFun}, partitionFun = Function[{low, high}, Module[{pivot = ds["Part", high], i = low, j}, Do[ If[ds["Part", j] ≤ pivot, ds["SwapPart", i, j];i = i + 1], {j, low, high - 1}]; ds["SwapPart", i, high]; i]]; sortFun = Function[{low, high}, If[low < high, Module[{p = partitionFun[low, high]}, sortFun[low, p - 1]; sortFun[p + 1, high] ] ]]; sortFun[1, ds["Length"]]; ds]

A sample data structure to use:

Wolfram Language code: ds = CreateDataStructure["ExtensibleVector", {9, 2, 7, 0}];

Sort the elements:

Wolfram Language code: Normal[Quicksort[ds]]

The data structure is sorted in place:

Wolfram Language code: Normal[ds]

Merge Sort  (1)

Merge sort is an efficient sorting algorithm. This is a simple implementation that uses a workspace:

Wolfram Language code: MergeSort[ ds : DataStructure["ExtensibleVector", _]] := MergeSortSplit[ds["Copy"] , 1, ds["Length"] + 1, ds]
Wolfram Language code: MergeSortSplit[ b_, start_, end_, a_] := Module[{mid}, If[end - start > 1, mid = Quotient[end + start, 2]; MergeSortSplit[a, start, mid, b]; MergeSortSplit[a, mid, end, b]; MergeSortJoin[ b, start, mid, end, a] ]; a]
Wolfram Language code: MergeSortJoin[ a_, start_, mid_, end_, b_] := Module[{i = start, j = mid, k}, Do[ If[i < mid && (j ≥ end || a["Part", i] ≤ a["Part", j]), b["Part", k] = a["Part", i];i++, b["Part", k] = a["Part", j];j++], {k, start, end - 1}]; ]

A sample data structure to use:

Wolfram Language code: ds = CreateDataStructure["ExtensibleVector", {9, 2, 7, 0}];

Sort the elements:

Wolfram Language code: Normal[MergeSort[ds]]

The data structure is sorted in place:

Wolfram Language code: Normal[ds]

Heapsort  (1)

Heapsort is an efficient sorting algorithm that works in place by constructing a heap:

Wolfram Language code: Heapsort[ds : DataStructure["ExtensibleVector", _]] := Module[{len = ds["Length"]}, Do[Heapify[ds, ii], {ii, Quotient[len, 2], 1, -1}]; ds ]
Wolfram Language code: Heapify[p : DataStructure["ExtensibleVector", _], k_Integer] := Module[{i = k, l, n = p["Length"]}, While[(l = 2 i) ≤ n, If[(l < n) && (p["Part", l] > p["Part", l + 1]), l++]; If[p["Part", i] > p["Part", l], p["SwapPart", l, i]; i = l, i = n + 1];];]

A sample data structure to use:

Wolfram Language code: ds = CreateDataStructure["ExtensibleVector", {9, 2, 7, 0}];

The elements are sorted in place:

Wolfram Language code: Heapsort[ds]; Normal[ds]

Timsort  (1)

Timsort is a hybrid and efficient sorting algorithm:

Wolfram Language code: Timsort[ds : DataStructure["ExtensibleVector", _]] := Module[{blockSize = 32, len = ds["Length"], size, mid, right}, Do[InsertionWorker[ds, ii, Min[ii + 32, len]], {ii, 1, len, blockSize}]; size = blockSize; While[size < len, Do[ mid = left + size; right = Min[left + 2 * size, len]; MergeWorker[ds, left, mid, right] , {left, 1, len, 2 * size} ]; size *= 2 ]; ]
Wolfram Language code: InsertionWorker[ ds : DataStructure["ExtensibleVector", _], left_, right_] := Module[{i, j}, Do[j = i; While[j > left && ds["Part", j - 1] > ds["Part", j], ds["SwapPart", j, j - 1];j--], {i, left, right}]; ds]
Wolfram Language code: MergeWorker[ b_, start_, mid_, end_] := Module[{a, i = start, j = mid, k}, a = b["Copy"]; Do[ If[i < mid && (j ≥ end || a["Part", i] ≤ a["Part", j]), b["Part", k] = a["Part", i];i++, b["Part", k] = a["Part", j];j++], {k, start, end - 1}]; ]

A sample data structure to use:

Wolfram Language code: ds = CreateDataStructure["ExtensibleVector", {9, 2, 7, 0}];

The elements are sorted in place:

Wolfram Language code: Timsort[ds]; Normal[ds]

Fisher–Yates Shuffle  (1)

The Fisher–Yates shuffle generates a random permutation of a finite sequence:

Wolfram Language code: FisherYatesShuffle[ ds : DataStructure["ExtensibleVector", _]] := ( Do[ ds["SwapPart", i, RandomInteger[{1, i}]], {i, ds["Length"] - 1, 1, -1} ]; ds );

A sample array to use for the shuffle:

Wolfram Language code: ds = CreateDataStructure["ExtensibleVector", {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100} ];

Apply the shuffle:

Wolfram Language code: Normal[FisherYatesShuffle[ds]]

Palindrome  (1)

An array is a palindrome if it is symmetric around the middle:

Wolfram Language code: IsPalindrome[ ds : DataStructure["ExtensibleVector", _]] := Module[{start = 0, end = ds["Length"] + 1}, While[++start < --end, If[ds["Part", start] =!= ds["Part", end], Return[False] ] ]; True];

This is not a palindrome:

Wolfram Language code: ds = CreateDataStructure["ExtensibleVector", {9, 2, 7, 0}]; IsPalindrome[ds]

This is a palindrome:

Wolfram Language code: ds = CreateDataStructure["ExtensibleVector", {9, 2, 2, 9}]; IsPalindrome[ds]

Quickselect  (1)

Quickselect is a selection algorithm related to the Quicksort algorithm. It returns the k^(th) smallest element in a list:

Wolfram Language code: Quickselect[ds : DataStructure["ExtensibleVector", _], k_] := QuickselectWorker[ds, 1, ds["Length"], k];
Wolfram Language code: QuickselectWorker[ds_, low0_, high0_, k_] := Module[{pivotIdx, low = low0, high = high0}, While[True, If[low === high, Return[ds["Part", low]]]; pivotIdx = SelectPartition[ds, low, high]; Which[ k === pivotIdx, Return[ds["Part", k]], k < pivotIdx, high = pivotIdx - 1, True, low = pivotIdx + 1 ] ] ];
Wolfram Language code: SelectPartition[ds_, low_, high_] := Module[{pivot = ds["Part", high], i = low, j}, Do[ If[ds["Part", j] ≤ pivot, ds["SwapPart", i, j];i = i + 1], {j, low, high - 1}]; ds["SwapPart", i, high]; i];

A sample data structure to use:

Wolfram Language code: ds = CreateDataStructure["ExtensibleVector", {9, 2, 7, 0}];

The third smallest element is 7:

Wolfram Language code: Quickselect[ds, 3]

Heap  (1)

A heap is a tree-based data structure where the value stored at children is smaller than that stored in their parents (for a min heap). It is commonly used to implement a priority queue and typically implemented with an array rather than a tree.

The following converts an array into a heap:

Wolfram Language code: MinHeapify[ds : DataStructure["ExtensibleVector", _]] := MinHeapify[ds, 1]
Wolfram Language code: MinHeapify[ds_, i_] := Module[{l, r, p, smallest}, l = If[getLeftChildIdx[i] <= ds["Length"], ds["Part", getLeftChildIdx[i]], -Infinity ]; r = If[getRightChildIdx[i] <= ds["Length"], ds["Part", getRightChildIdx[i]], -Infinity ]; p = ds["Part", i]; smallest = If[getLeftChildIdx[i] <= ds["Length"] && l < p, getLeftChildIdx[i], i]; If[getRightChildIdx[i] <= ds["Length"] && r < ds["Part", smallest], smallest = getRightChildIdx[i]]; If[smallest =!= i, ds["SwapPart", i, smallest]; MinHeapify[ds, smallest] ]; ];
Wolfram Language code: getLeftChildIdx[i_] := 2i
Wolfram Language code: getRightChildIdx[i_] := 2i + 1
Wolfram Language code: getParentIdx[i_] := Quotient[i, 2]

A sample data structure to use:

Wolfram Language code: ds = CreateDataStructure["ExtensibleVector", Reverse[{9, 8, 7, 6, 5, 4, 3, 2, 1}]];

This converts the array into a heap; it is hard to see the heap property:

Wolfram Language code: MinHeapify[ds]; Normal[ds]

This function generates a tree:

Wolfram Language code: MakeHeapTree[array_] := Module[{data = Normal[array]}, TreeGraph[Flatten[MakeHeapTree[data, 1]], VertexLabels -> "Name", GraphLayout -> {"LayeredEmbedding", "RootVertex" -> First[data]}] ] MakeHeapTree[arry_, idx_] := { If[getLeftChildIdx[idx] <= Length[arry], { DirectedEdge[arry[[idx]], arry[[getLeftChildIdx[idx]]]], MakeHeapTree[arry, getLeftChildIdx[idx]] }, Nothing ], If[getRightChildIdx[idx] <= Length[arry], { DirectedEdge[arry[[idx]], arry[[getRightChildIdx[idx]]]], MakeHeapTree[arry, getRightChildIdx[idx]] }, Nothing ] }

A visualization makes it easier to see the min heap property:

Wolfram Language code: MakeHeapTree[ds]

Properties & Relations  (2)

"FixedArray"  (1)

Many algorithms that work for "ExtensibleVector" also work for "FixedArray".

"DynamicArray"  (1)

Many algorithms that work for "ExtensibleVector" also work for "DynamicArray".