Data Structures

  The module DataStructure contains classes implementing arrays and dictionaries.

Array

   The class Array=DataStructure.array provides for arrays. Array has the following methods:

init(low:+I1<=0 high:+I2)

    initialize to array ranging from I1 to I2 with fresh variables as values. Error if I2 < I1. For example,

create A from Array 
   with init(low:100 high:1000)
end

creates an array whose indices range from 100 to 1000.

get(+I ?X)

    retrieve value X stored under index I. Error if bounds are exceeded.

put(+I X)

    store X under index I. Error if bounds are exceeded.

size(low:?I1 high:?I2)

     I1 is lower and I2 is upper bound of array.

The following methods take an object or class OC that provides a method to be applied iteratively (similar to the method forAll in Class.list). Therefore, we call them higher-order methods. They iterate over all elements of the array, using the methods get and put of self. Thus, redefinition of get and put redefines also these higher-order methods. Similar to the higher-order methods in Class.list they take use as default for the last argument a local name Private (see Class, list, forAllB).    

forAllB(+OC ?B +L<=Private)

        Similar to the method forAll in Class.list, except that iteration proceeds over all elements of the array, starting with the lowest index. Example of usage:

create A from Array
   attr setValue:0
   with [init(high:100) set]
   meth set
      <<forAll(class meth set(X) X=@setValue end end)>>
   end
end

Every entry of the array A is initialized with 0.

forSomeB(+OC ?B +L<=Private)

        Similar to the method forSomeB in Class.list, except that iteration proceeds over all elements of the array, starting with the lowest index.

map(+OC +L<=Private)

    Similar to the method map in Class.list, except that iteration proceeds over all elements of the array. starting with the lowest index. Example of usage:

create A from Array
   attr incVal:10
   with init(high:100)
   meth incAll
      <<map(class meth inc(Old New) New=Old+@incVal end end)>>
   end
end

Message sending {A incAll} increments every entry of the array A by the value of the attribute incVal.

foldL(+OC X ?Y +L<=Private)

    Similar to the method foldL in Class.list, except that iteration proceeds over all elements of the array, starting with the lowest index. Example of usage:

create ShoppingList from Array
   attr taxRate:15.0
   with init(high:100)
   meth sum(?X)
      <<foldL(class meth add(Old Entry New) 
                       New=Old+Entry+Entry*@taxRate/100.0
                    end
              end 0.0 X)>>
   end
end

Message sending {ShoppingList sum(X)} binds X to the sum of all entries of the array A where the taxes are added.

foldR(+OC X ?Y +L<=L)

    Similar to the method foldR in Class.list, except that iteration proceeds over all elements of the array, starting with the lowest index.

forAllIndB(+OC ?B +L<=Private)
forSomeIndB(+OC ?B +L<=Private)
mapInd(+OC +L<=Private)
foldLInd(+OC X ?Y +L<=Private)
foldRInd(+OC X ?Y +L<=Private)

                                          Similar to the respective method without Ind, except that the first argument of the higher-order method is the current index of of the array, see also the method forAllInd of Class.list.

Resizable Array

   The class DataStructure.resizableArray provides for array objects that can be resized with the method resize. DataStructure.resizableArray inherits from Array.

resize(low:+ILow<={\it current low} high:IHigh<={\it current high})

   resize to the given low bound ILow and high bound IHigh; ILow must be smaller or equal the current low bound and IHigh must be greater or equal the current high bound.

AutomaticArray

   The class DataStructure.automaticArray provides for array objects that are automatically resized when put exceeds the upper boundary. DataStructure.automaticArray inherits from DataStructure.resizableArray and redefines the method put.

put(+I X)

   store X under index I. Automatic resize if I < current low bound or I > current high bound to the necessary size augmented by the current size.

MultiArray

   The class DataStructure.multiArray provides for multi-dimensional arrays. DataStructure.multiArray has the following methods:

init(+Xs)

   Initialization, where the list Xs represents the dimension of the array. Xs is a list of pairs, each representing one dimension. The first component of the pairs contain the lower bound and the second the upper bound of that dimension. For example

create A from DataStructure.multiArray
   with init([0#100 10#20])
end

creates an array A where the first dimension ranges from 0 to 100 and the second from 10 to 20.

get(+Is ?X)

   retrieve value stored under index Is. Error if dimension violated.

put(+Is X)

   store X under index Is. Error if dimension violated.

dim(+Is X)

    Xs is dimension of array as given in init.

forAllB(+OC ?B +L<=Private)
forSomeB(+OC ?B +L<=Private)
map(+OC +L<=Private)
foldL(+OC X Y +L<=Private)
foldR(+OC X Y +L<=Private)
forAllIndB(+OC +L<=Private)
forSomeIndB(+OC +L<=Private)
mapInd(+OC +L<=Private)
foldLInd(+OC X ?Y +L<=Private)
foldRInd(+OC X ?Y +L<=Private)

                                                 similar to the respective methods of Array, see remarks on higher-order methods of Array on page .

Dictionary

   The class Dictionary=DataStructure.dictionary provides for dictionaries, which are mappings from literals to values.

init(+Xs)

    initialize to dictionary with information list of pairs Xs. Example: init([monkey#"eats bananas" bear#"eats fish"]) initializes to dictionary where the string "eats bananas" is stored under index monkey and "eats fish" stored under index bear.

get(+L  ?X)

    retrieve X stored under index L. Error if no entry.

put(+L X)

    store X under index L.

remove(+L<=Private)

    remove entry under index L.

entries(?As)

     As is list of public (atomic) entries entered so far.

memberB(+L ?B)

        dictionary has entry under index L.

forAllB(+OC ?B +L<=Private)
forAllIndB(+OC ?B +L<=Private)
forSomeB(+OC ?B +L<=Private)
forSomeIndB(+OC ?B +L<=Private)
map(+OC +L<=Private)
mapInd(+OC +L<=Private)
foldL(+OC X ?Y +L<=Private)
foldR(+OC X ?Y +L<=Private)
forAllIndB(+OC +L<=Private)
forSomeIndB(+OC +L<=Private)
mapInd(+OC +L<=Private)
foldLInd(+OC X ?Y +L<=Private)
foldRInd(+OC X ?Y +L<=Private)

                                                                      similar to the respective methods of Array, see remarks on higher-order methods of Array on page . Iteration processes all public entries in alphabetical order. Note that the higher-order methods iterate over the entries of the array at the time when the higher-order method was applied, i.e. do not treat the entries that were added during iteration.

oldsectionmark