IndexedFlexibleArray(S, mn)ΒΆ

array1.spad line 100

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.

<: (%, %) -> 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
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
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: () -> %
from Aggregate
empty?: % -> Boolean
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 Evalable S and S has SetCategory
from Evalable S
eval: (%, List Equation S) -> % if S has Evalable S and S has SetCategory
from Evalable S
eval: (%, List S, List S) -> % if S has Evalable S and S has SetCategory
from InnerEvalable(S, S)
eval: (%, S, S) -> % if S has Evalable S and S has SetCategory
from InnerEvalable(S, S)
find: (S -> Boolean, %) -> Union(S, failed)
from Collection S
first: % -> S
from IndexedAggregate(Integer, S)
flexibleArray: List S -> %
flexibleArray(l) creates a flexible array from the list of elements l
hash: % -> SingleInteger if S has SetCategory
from SetCategory
hashUpdate!: (HashState, %) -> HashState if S has SetCategory
from SetCategory
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) -> S, %, %) -> %
from LinearAggregate S
map: (S -> S, %) -> %
from HomogeneousAggregate S
max: (%, %) -> % if S has OrderedSet
from OrderedSet
maxIndex: % -> Integer
from IndexedAggregate(Integer, S)
member?: (S, %) -> Boolean if S has BasicType
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
min: (%, %) -> % if S has OrderedSet
from OrderedSet
minIndex: % -> Integer
from IndexedAggregate(Integer, S)
more?: (%, NonNegativeInteger) -> Boolean
from Aggregate
new: (NonNegativeInteger, S) -> %
from LinearAggregate 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 accomodate before growing
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)
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, %) -> % 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 consequtive equal elements of u by single elements.
rightTrim: (%, S) -> % if S has BasicType
from LinearAggregate S
sample: %
from Aggregate
select!: (S -> Boolean, %) -> %
from ExtensibleLinearAggregate 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: % -> % if S has OrderedSet
from LinearAggregate S
sorted?: % -> Boolean if S has OrderedSet
from LinearAggregate 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 Evalable S and S has SetCategory

ExtensibleLinearAggregate S

finiteAggregate

FiniteLinearAggregate S

HomogeneousAggregate S

IndexedAggregate(Integer, S)

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

LinearAggregate S

OneDimensionalArrayAggregate S

OrderedSet if S has OrderedSet

PartialOrder if S has OrderedSet

SetCategory if S has SetCategory

shallowlyMutable