array: Generic and Dynamic Arrays

8.12

array: Generic and Dynamic Arrays🔗ℹ

rvs314

package: array

The array module provides a generic interface for the array, a data structure that uses compact, constant-time, natural-number indexing and updating. Racket has many built-in types which act as either homogeneous (all elements have the same type) or heterogeneous (elements can have different types) arrays, such as the vector, byte string, string, flvector, and others. This module also provides an implementation of the dynamic array, an array which grows exponentially, allowing for an amortized O(1) append operation.

1 Generic Arrays🔗ℹ

syntax
gen:array

A generic interface for arrays. The interface defines the following methods:

array-set!
array-ref
array-length
array-alloc
array-copy!
in-array

procedure
(array? obj) → boolean?
obj : any/c

Returns #t if the object implements the gen:array interface, #f otherwise.

procedure
(array-set! array idx val) → void?
  array : array?
  idx : exact-nonnegative-integer?
  val : any/c

Sets slot idx of array to be val.

procedure
(array-ref array idx) → any/c
array : array?
idx : exact-nonnegative-integer?

Returns slot idx of array.

procedure
(array-length array) → exact-nonnegative-integer?
array : array?

Returns the number of valid slots in array.

procedure
(array-alloc array len) → array?
array : array?
len : exact-nonnegative-integer?

Returns a new array of the same type as array with len elements. The elements of the returned array are not defined.

procedure
(array-copy! dest
dest-start
array
[ array-start
array-end]) → void?
  dest : array?
  dest-start : exact-nonnegative-integer?
  array : array?
  array-start : exact-nonnegative-integer? = 0
  array-end : exact-nonnegative-integer? = (array-length array)

Changes the elements of dest starting at position dest-start to match the elements in array from array-start (inclusive) to array-end (exclusive). There is a fallback implementation for this method.

procedure
(in-array array) → sequence?
array : array?

Returns a sequence containing all the elements of array. There is a fallback implementation for this method. Using this is often faster than indexing each element individually, as it avoids redundant method lookups.

procedure
(array-empty? array) → boolean?
array : array?

Returns #t if array has a length of zero, #f otherwise.

procedure
(array-first array) → any/c
array : array?

Returns the element at index zero of array.

procedure
(array-last array) → any/c
array : array?

Returns the element at index (sub1 (array-length array)) of array.

procedure
(array->list array) → list?
array : array?

Returns the elements of array as a newly allocated list.

procedure
(array->vector array) → vector?
array : array?

Returns the elements of array as a newly allocated vector.

2 Dynamic Arrays🔗ℹ

(require array/dynamic)

package: array

struct
(struct dynamic-array (buffer length))
buffer : array?
length : exact-nonnegative-integer?

A dynamic array (also called an array-list or growable array) is an array that can grow in amortized O(1) time. It’s implemented using a traditional, static array (called the dynamic-array-buffer), where only the first dynamic-array-length elements are meaningful. By increasing the length field of the dynamic array, we can increase the number of elements until we run out of space in the underlying buffer, in which case we allocate a new underlying buffer and continue. Notice that for a given dynamic array arr, (dynamic-array-length arr) is not the same as (array-length (dynamic-array-buffer arr)).

procedure
(dynamic-array? obj) → boolean?
obj : any/c

Returns #t if obj is an instance of the dynamic-array structure type, #f otherwise.

procedure
(dynamic-array arr [len]) → dynamic-array?
arr : array?
len : exact-nonnegative-integer? = (array-length arr)

Returns a new dynamic array.

procedure
(dynamic-array-buffer array) → array?
array : dynamic-array?

Returns the underling buffer of the dynamic array array.

procedure
(dynamic-array-length array) → exact-nonnegative-integer?
array : dynamic-array?

Returns the length of the dynamic array array.

procedure
(dynamic-array-capacity array) → exact-nonnegative-integer?
array : dynamic-array?

Returns the capacity of the dynamic array array. This is increased automatically by dynamic-array-append! and dynamic-array-push! and can be increased manually by calling dynamic-array-ensure-capacity!.

procedure
(dynamic-array-ensure-capacity array
min-cap) → void?
array : dynamic-array?
min-cap : exact-nonnegative-integer?

Grows the underlying buffer of array until it has a capacity of at least min-cap.

procedure
(dynamic-array-append! array new-values) → void?
array : dynamic-array?
new-values : array?

Pushes an array of new values onto the array. This will cause at most one new allocation.

procedure
(dynamic-array-push! array new-value)
→ exact-nonnegative-integer?
array : dynamic-array?
new-value : any/c

Pushes a new values onto the array. This will cause at most one new allocation. Returns the index of the element pushed.

procedure
(dynamic-array-pop! array) → any/c
array : dynamic-array?

Returns the last element of array and decreases the dynamic-array-length by one. Raises an exn:fail:contract if the array is empty.

procedure
(dynamic-array-contents array) → array?
array : dynamic-array?

Returns a newly allocated array of the same type as (dynamic-array-buffer array) with the contents of array.