IndexedFlexibleArray(S, mn)

array1.spad line 100 [edit on github]

• S: Type

• mn: Integer

Author: Michael Monagan July/87, modified SMW June/91 A FlexibleArray is the notion of an array intended to allow for growth at the end only. Hence the following efficient operations concat!(a, x) meaning append item x at the end of the array a delete!(a, n) meaning delete the last item from the array a Flexible arrays support the other operations inherited from ExtensibleLinearAggregate. However, these are not efficient. Flexible arrays combine the O(1) access time property of arrays with growing and shrinking at the end in O(1) (average) time. This is done by using an ordinary array which may have zero or more empty slots at the end. When the array becomes full it is copied into a new larger (50% larger) array. Conversely, when the array becomes less than 1/2 full, it is copied into a smaller array. Flexible arrays provide for an efficient implementation of many data structures in particular heaps, stacks and sets.

#: % -> NonNegativeInteger

from Aggregate

<=: (%, %) -> Boolean if S has OrderedSet

from PartialOrder

<: (%, %) -> Boolean if S has OrderedSet

from PartialOrder

=: (%, %) -> Boolean if S has BasicType

from BasicType

>=: (%, %) -> Boolean if S has OrderedSet

from PartialOrder

>: (%, %) -> Boolean if S has OrderedSet

from PartialOrder

~=: (%, %) -> Boolean if S has BasicType

from BasicType

any?: (S -> Boolean, %) -> Boolean

from HomogeneousAggregate S

coerce: % -> OutputForm if S has CoercibleTo OutputForm

from CoercibleTo OutputForm

concat!: (%, %) -> %

from ExtensibleLinearAggregate S

concat!: (%, S) -> %

from ExtensibleLinearAggregate S

concat: (%, %) -> %

from LinearAggregate S

concat: (%, S) -> %

from LinearAggregate S

concat: (S, %) -> %

from LinearAggregate S

concat: List % -> %

from LinearAggregate S

construct: List S -> %

from Collection S

convert: % -> InputForm if S has ConvertibleTo InputForm

from ConvertibleTo InputForm

copy: % -> %

from Aggregate

copyInto!: (%, %, Integer) -> %

from LinearAggregate S

count: (S -> Boolean, %) -> NonNegativeInteger

from HomogeneousAggregate S

count: (S, %) -> NonNegativeInteger if S has BasicType

from HomogeneousAggregate S

delete!: (%, Integer) -> %

from ExtensibleLinearAggregate S

delete!: (%, UniversalSegment Integer) -> %

from ExtensibleLinearAggregate S

delete: (%, Integer) -> %

from LinearAggregate S

delete: (%, UniversalSegment Integer) -> %

from LinearAggregate S

elt: (%, Integer) -> S

from Eltable(Integer, S)

elt: (%, Integer, S) -> S

from EltableAggregate(Integer, S)

elt: (%, UniversalSegment Integer) -> %

from Eltable(UniversalSegment Integer, %)

empty?: % -> Boolean

from Aggregate

empty: () -> %

from Aggregate

entries: % -> List S

from IndexedAggregate(Integer, S)

entry?: (S, %) -> Boolean if S has BasicType

from IndexedAggregate(Integer, S)

eq?: (%, %) -> Boolean

from Aggregate

eval: (%, Equation S) -> % if S has SetCategory and S has Evalable S

from Evalable S

eval: (%, List Equation S) -> % if S has SetCategory and S has Evalable S

from Evalable S

eval: (%, List S, List S) -> % if S has SetCategory and S has Evalable S

from InnerEvalable(S, S)

eval: (%, S, S) -> % if S has SetCategory and S has Evalable S

from InnerEvalable(S, S)

every?: (S -> Boolean, %) -> Boolean

from HomogeneousAggregate S

fill!: (%, S) -> %

from IndexedAggregate(Integer, S)

find: (S -> Boolean, %) -> Union(S, failed)

from Collection S

first: % -> S

from IndexedAggregate(Integer, S)

first: (%, NonNegativeInteger) -> %

from LinearAggregate S

flexibleArray: List S -> %

flexibleArray(l) creates a flexible array from the list of elements l

hash: % -> SingleInteger if S has Hashable

from Hashable

hashUpdate!: (HashState, %) -> HashState if S has Hashable

from Hashable

index?: (Integer, %) -> Boolean

from IndexedAggregate(Integer, S)

indices: % -> List Integer

from IndexedAggregate(Integer, S)

insert!: (%, %, Integer) -> %

from ExtensibleLinearAggregate S

insert!: (S, %, Integer) -> %

from ExtensibleLinearAggregate S

insert: (%, %, Integer) -> %

from LinearAggregate S

insert: (S, %, Integer) -> %

from LinearAggregate S

latex: % -> String if S has SetCategory

from SetCategory

leftTrim: (%, S) -> % if S has BasicType

from LinearAggregate S

less?: (%, NonNegativeInteger) -> Boolean

from Aggregate

map!: (S -> S, %) -> %

from HomogeneousAggregate S

map: ((S, S) -> S, %, %) -> %

from LinearAggregate S

map: (S -> S, %) -> %

from HomogeneousAggregate S

max: % -> S if S has OrderedSet

from HomogeneousAggregate S

max: (%, %) -> % if S has OrderedSet

from OrderedSet

max: ((S, S) -> Boolean, %) -> S

from HomogeneousAggregate S

maxIndex: % -> Integer

from IndexedAggregate(Integer, S)

member?: (S, %) -> Boolean if S has BasicType

from HomogeneousAggregate S

members: % -> List S

from HomogeneousAggregate S

merge!: (%, %) -> % if S has OrderedSet

from ExtensibleLinearAggregate S

merge!: ((S, S) -> Boolean, %, %) -> %

from ExtensibleLinearAggregate S

merge: (%, %) -> % if S has OrderedSet

from LinearAggregate S

merge: ((S, S) -> Boolean, %, %) -> %

from LinearAggregate S

min: % -> S if S has OrderedSet

from HomogeneousAggregate S

min: (%, %) -> % if S has OrderedSet

from OrderedSet

minIndex: % -> Integer

from IndexedAggregate(Integer, S)

more?: (%, NonNegativeInteger) -> Boolean

from Aggregate

new: (NonNegativeInteger, S) -> %

from LinearAggregate S

parts: % -> List S

from HomogeneousAggregate S

physicalLength!: (%, Integer) -> %

physicalLength!(x, n) changes the physical length of x to be n and returns the new array.

physicalLength: % -> NonNegativeInteger

physicalLength(x) returns the number of elements x can accommodate before growing

position: (S -> Boolean, %) -> Integer

from LinearAggregate S

position: (S, %) -> Integer if S has BasicType

from LinearAggregate S

position: (S, %, Integer) -> Integer if S has BasicType

from LinearAggregate S

qelt: (%, Integer) -> S

from EltableAggregate(Integer, S)

qsetelt!: (%, Integer, S) -> S

from EltableAggregate(Integer, S)

reduce: ((S, S) -> S, %) -> S

from Collection S

reduce: ((S, S) -> S, %, S) -> S

from Collection S

reduce: ((S, S) -> S, %, S, S) -> S if S has BasicType

from Collection S

remove!: (S -> Boolean, %) -> %

from ExtensibleLinearAggregate S

remove!: (S, %) -> % if S has BasicType

from ExtensibleLinearAggregate S

remove: (S -> Boolean, %) -> %

from Collection S

remove: (S, %) -> % if S has BasicType

from Collection S

removeDuplicates!: % -> % if S has BasicType

from ExtensibleLinearAggregate S

removeDuplicates: % -> % if S has BasicType

from Collection S

removeRepeats!: % -> %

removeRepeats!(u) destructively replaces runs of consecutive equal elements of u by single elements.

reverse!: % -> %

from LinearAggregate S

reverse: % -> %

from LinearAggregate S

rightTrim: (%, S) -> % if S has BasicType

from LinearAggregate S

sample: %

from Aggregate

select!: (S -> Boolean, %) -> %

from ExtensibleLinearAggregate S

select: (S -> Boolean, %) -> %

from Collection S

setelt!: (%, Integer, S) -> S

from EltableAggregate(Integer, S)

setelt!: (%, UniversalSegment Integer, S) -> S

from LinearAggregate S

shrinkable: Boolean -> Boolean

shrinkable(b) sets the shrinkable attribute of flexible arrays to b and returns the previous value

size?: (%, NonNegativeInteger) -> Boolean

from Aggregate

smaller?: (%, %) -> Boolean if S has Comparable

from Comparable

sort!: % -> % if S has OrderedSet

from LinearAggregate S

sort!: ((S, S) -> Boolean, %) -> %

from LinearAggregate S

sort: % -> % if S has OrderedSet

from LinearAggregate S

sort: ((S, S) -> Boolean, %) -> %

from LinearAggregate S

sorted?: % -> Boolean if S has OrderedSet

from LinearAggregate S

sorted?: ((S, S) -> Boolean, %) -> Boolean

from LinearAggregate S

swap!: (%, Integer, Integer) -> Void

from IndexedAggregate(Integer, S)

trim: (%, S) -> % if S has BasicType

from LinearAggregate S

Aggregate

BasicType if S has BasicType

CoercibleTo OutputForm if S has CoercibleTo OutputForm

Collection S

Comparable if S has Comparable

ConvertibleTo InputForm if S has ConvertibleTo InputForm

Eltable(Integer, S)

Eltable(UniversalSegment Integer, %)

EltableAggregate(Integer, S)

Evalable S if S has SetCategory and S has Evalable S

ExtensibleLinearAggregate S

finiteAggregate

FiniteLinearAggregate S

Hashable if S has Hashable

HomogeneousAggregate S

IndexedAggregate(Integer, S)

InnerEvalable(S, S) if S has SetCategory and S has Evalable S

LinearAggregate S

OneDimensionalArrayAggregate S

OrderedSet if S has OrderedSet

PartialOrder if S has OrderedSet

SetCategory if S has SetCategory

shallowlyMutable