# IndexedFlexibleArray(S, mn)ΒΆ

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

CoercibleTo OutputForm if S has CoercibleTo OutputForm

Comparable if S has Comparable

ConvertibleTo InputForm if S has ConvertibleTo InputForm

Eltable(UniversalSegment Integer, %)

Evalable S if S has Evalable S and S has SetCategory

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

OneDimensionalArrayAggregate S

OrderedSet if S has OrderedSet

PartialOrder if S has OrderedSet

SetCategory if S has SetCategory