Basic Data Structures

Joachim Niehren

provides
x-ozlib://base/stack.ozf
x-ozlib://base/queue.ozf
x-ozlib://base/counter.ozf
x-ozlib://base/dictionary.ozf
x-ozlib://base/bag.ozf
x-ozlib://base/array.ozf
x-ozlib://base/gensym.ozf
x-ozlib://base/cell.ozf
--------------
x-ozlib://base/lib/stack.ozf
x-ozlib://base/lib/queue.ozf
x-ozlib://base/lib/counter.ozf
x-ozlib://base/lib/dictionary.ozf
x-ozlib://base/lib/bag.ozf
x-ozlib://base/lib/cell.ozf
x-ozlib://base/lib/array.ozf
requires
no other Mogul package required

Overview

This package extends Mozart's base environment by the most frequent data types that are not directly supported otherwise: stack, queue, counter, bag, gensym All data structures come with a uniform user interface. They are implemented efficiently on the basis of the Oz base environment. All data structures are given in two styles: the Oz-library style and the object-as-record style. The package also contains some further data structures. They previously were only available in the Oz-library style: dictionary, array, cell

Uniform Interface

Every data structures has functions with the same name to put data into and get data from it: put, get These functions are not only available with the uniform names, but also with their standard names. The put function of a cell for instance is usally called assign and its get function access. And of course, you can push or pop elements onto or from a stack, as you might expect. Other uniform function names that are only available if they make sense are: condGet, member, isEmpty, size, clone, toList, toRecord, toRecordLabel

Oz-Library Style versus Object-as-Record Style

All datastructures in this package are provided in two styles: the Oz-Library style and the object-as-record style.

The Oz library style is the same style as used in the Oz base environment. The idea is that the functions of all instances of data structures are provided by a comon module. For example, the functionalities for all dictionaries are collected in the module This package provides implementations of data structure in the object-as-record style at the URI x-ozlib://niehren/base. The corresponding versions in the Oz-library style are available at the URI x-ozlib://niehren/base/lib.

Example

We first show how to use a stack in object as record style. Here, the stack S is a record of functions push, pop, etc: 

   declare [Stack] = {Module.link ['x-ozlib://niehren/base/stack.ozf']}
   declare S = {Stack.new}
   {S.push 1}            %% push 1 onto the stack
   {S.push 2}            %% push 2 onto the stack
   {Inspect {S.pop}}     %% remove and inspect the top most element
   {Inspect {S.toList}}  %% inspect the stack's content
Here is how to use a stack in the Oz-library style. Now a stack S is the first argument expected by the functions of the module stack: 
   declare [Stack] = {Module.link ['x-ozlib://niehren/base/lib/stack.ozf']}
   declare S = {Stack.new}
   {Stack.push S 1}           %% push 1 onto the stack
   {Stack.push S 2}           %% push 2 onto the stack
   {Inspect {Stack.pop S}     %% remove and return the top most element
   {Inspect {Stack.toList S}} %% inspect the stack's content

Manual

In the following we will describe all data structures in detail. We will use the object-as-record style variants for explanation because function types are smaller and therefore more concise. However, with the above information the following is easy applicable to the Oz-library style variants.

The documenting style is adopted from the Oz Base Environment Documentation. It is described in the sections "Variable Status" and "Description Format" in chapter Type Structure and Description Format.

Stack

There are two constructors for stacks: 

Stack.new : -> stack
creates a new and empty stack and 
Stack.newFromList : list(value) -> stack
 creates a new stack initialized with the given list, so that the head of the list becomes the topmost element. A stack has the following type: 
    type stack = unit(push          : value ->
                      pop           : -> value
                      isEmpty       : -> bool
                      toList        : -> list(value)
                      top           : -> value
                      clear         : ->
                      clone         : -> stack
                      member        : value -> bool
                      size          : -> int 
                      put           : value ->
                      get           : -> value)
The type can also be specified by modes as usual in the Oz documentation:

{S.push X}

pushes X onto the stack S.

{S.pop ?X}

pops the topmost element from S and returns it in X. Raises empty iff S is empty.

{S.isEmpty ?B}

tests whether S is empty and returns the boolean result in B.

{S.toList ?Xs}

returns the list containing the elements of S in Xs. The list returned is the list that is used to implement the stack, so this operation needs constant time. The elements in Xs are in the same order they would appear by subsequent calls to get.

{S.top ?X}

returns the topmost element from S into X without changing S's state. Raises empty iff S is empty.

{S.clear}

erases S to an empty stack.

{S.clone ?R}

returns an independent clone of S in R.

{S.member +X ?B}

tests whether S contains X using == and returns the boolean result in B.

{S.size ?I}

returns the size of S in I.

{S.put X}

is a synonym for {S.push X}.

{S.get ?X}

is a synonym for {S.pop ?X}.

Queue

There are two constructors for queues: 
Queue.new : -> queue
 creates a new and empty queue and 
Queue.newFromList : list(value) -> queue
 creates a new queue initialized with the given list, so that the elements in the list are in the same order they would appear by subsequent calls to deq. A queue has the following type: 
    type queue = unit(deq           : -> value
                      enq           : value ->
                      isEmpty       : -> bool
                      toList        : -> list(value)
                      top           : -> value
                      clear         : ->
                      clone         : -> queue
                      member        : value -> bool
                      size          : -> int 
                      put           : value ->
                      get           : -> value)
The type can also be specified by modes as usual in the Oz documentation:

{Q.enq X}

enqueues X into Q.

{Q.deq ?X}

dequeues the next element from Q and returns it in X. Raises empty iff Q is empty.

{Q.isEmpty ?B}

tests whether Q is empty and returns the boolean result in B.

{Q.toList ?Xs}

returns the list containing the elements of Q in ?Xs. This operation needs linear time. The elements in ?Xs are in the same order they would appear by subsequent calls to deq.

{Q.top ?X}

returns the topmost element from Q into X without changing Q's state. Raises empty iff Q is empty.

{Q.clear}

erases Q to an empty queue.

{Q.clone ?R}

returns an independent clone of Q in R.

{Q.member +X ?B}

tests whether Q contains X using == and returns the boolean result in B.

{Q.size ?I}

returns the size of Q in I.

{Q.put X}

is a synonym for {Q.push X}.

{Q.get ?X}

is a synonym for {Q.pop X}.

Counter

A counter holds one integer that can be incremented or set to an arbitrary integer. There are two constructors for counters: 
Counter.new : -> counter
 creates a new counter initialized with 0 and 
Counter.newFromInt : int -> counter
 creates a new counter initialized with the given integer. A counter has the following type: 
    type counter = unit(inc   : ->
                        set   : int ->
                        show  : -> int
                        next  : -> int
                        clone : -> counter
                        put   : int ->
                        incr  : ->
                        init  : int ->
                        get   : -> int
                        toInt : -> int
The type can also be specified by modes as usual in the Oz documentation:

{C.inc}

increments C by 1.

{C.set +I}

sets the current value of C to I.

{C.show ?I}

returns the current value of C in I.

{C.next ?I}

increments C by 1 and returns the resulting integer in I.

{C.clone ?R}

returns an independent clone of C in R.

{C.incr +I}

is a synonym for {C.inc +I}.

{C.put +I}

is a synonym for {C.set +I}.

{C.init +I}

is a synonym for {C.set +I}.

{C.get ?I}

is a synonym for {C.show ?I}.

{C.toInt ?I}

is a synonym for {C.show ?I}.

Dictionary

Dictionaries in the object-record style are derived straightforwardly from those in the Oz base environment. But there are two important differences that we would like to point out.

First there is a quite useful procedure collect: feature x value -> which adds a value for some key to a collecting list. The actual list can be access as the entry of the key. Second, the type of toRecord:->record differs from what one might expect. This function converts the dicitionary to a record whose label is the unit. If you want to specify another label then you can still use toRecordLabel:literal->record that does exactly what the toRecord function of the Oz base environment does.

There are two constructors for dictionaries: 

Dictionary.new : -> dictionary
creates a new and empty dictionary and 
Dictionary.newFromRecord : record -> dictionary
 creates a new dictionary initialized with the feature/value pairs of the given record. A dictionary is a record with the following type: 
    type feature = literal | integer
    type dictionary = unit(put           : feature x value -> dict
                           get           : feature -> value
                           hasFeature    : feature -> bool
                           condGet       : feature x value -> value
                           remove        : feature ->
                           removeAll     : ->
                           keys          : -> list(feature)
                           entries       : -> list(feature#value)
                           items         : -> list(value)
                           toRecord      : -> record
                           toRecordLabel : literal -> record
                           isEmpty       : -> bool
                           size          : -> int
                           collect       : feature x value -> dict
                           clone         : -> dict
                           dict          : -> stdlib-dict
                           clear         : ->
                           condSelect    : feature x value -> value
                           member        : feature -> bool
                           toKeys        : -> list(feature))
The type can also be specified by modes as usual in the Oz documentation:

{D.put +LI X}

sets the item of D under the key LI to X.

{D.get +LI ?X}

returns the item of D under the key LI in X. Raises an exception if LI is not a valid key of D.

{D.hasFeature +LI ?B}

tests whether D has an entry with the feature LI and returns the boolean result in B.

{D.condGet +LI Default ?Y}

returns the item of D under the key LI as Y iff LI is a valid key of D. Otherwise, returns Default.

{D.remove +LI}

removes the entry with the key LI from D iff LI is a valid key of D. Otherwise, does nothing.

{D.removeAll}

resets D to an empty dictionary.

{D.keys ?LIs}

returns a list of all valid features for D in LIs.

{D.entries ?Ts}

returns a list of all entries in Ts where each entry has the form Feature#Item.

{D.items ?Xs}

returns a list of all items in Xs.

{D.toRecord ?R}

returns a record containing all feature/item pairs of D as its fields in R. This record R will get the label unit. Note that ToRecord differs to the corresponding function in the Oz base environment. But you can still use toRecordLabel if you want to custom your own label.

{D.toRecordLabel +LI ?R}

works like toRecord except that it gives the possibility to specify a custom label (LI). Note that this function does exactly what the function ToRecord in the Oz base environment does despite of its different name.

{D.isEmpty ?B}

tests whether D is empty and returns the boolean result in B.

{D.size ?I}

returns the element count of D in I.

{D.collect +LI X}

collects X in the list under the feature LI in D. More precise, it will set D's item under LI to X|{D.condGet LI nil}. Note that collectors are not available for the dictionaries of the base environment.

{D.clone +R}

returns an independent clone of D in R.

{D.dict}

returns the Oz base environment dictionary through which D is implemented.

{D.clear}

is a synonym for {D.removeAll}.

{D.condSelect +LI X ?Y}

is a synonym for {D.condGet +LI X ?Y}.

{D.member +LI ?B}

is a synonym for {D.hasFeature +LI ?B}.

{D.toKeys ?LIs}

is a synonym for {D.keys ?LIs}.

Bag

A bag is a simple data structure that gives the possibility to put values into the bag, to test whether a given value is in the bag and to return the elements in a bag as a list. A bag is essentially the same as a stack. The only difference is that it does not provide functions for getting single elements from it (with pop or top). There are two constructors for bags: 
Bag.new : -> bag
 creates a new and empty bag and 
Bag.newFromList : list(value) -> bag
 creates a new bag initialized with the elements of the given list. A bag has the following type: 
    type queue = unit(put           : -> value
                      member        : value -> bool
                      isEmpty       : -> bool
                      toList        : -> list(value)
                      clear         : ->
                      clone         : -> queue
                      size          : -> int)
The type can also be specified by modes as usual in the Oz documentation:

{B.put X}

puts X into B.

{B.member +X ?B1}

tests whether B contains X using ==. Returns the boolean result in B1.

{B.isEmpty ?B1}

tests whether B is empty and returns the boolean result in B1.

{B.toList ?Xs}

returns the list containing the elements of B in Xs. The list returned is the list that is used to implement the stack, so this operation needs constant time.

{B.clear}

resets B to an empty queue.

{B.clone ?R}

returns an independent clone of B in R.

{B.size ?I}

returns the size of B in I.

Array

Arrays in are, very much like dictionaries, derived straightforwardly from the arrays in the Oz base environment. Like the dictionaries the arrays provide a collect: int x value -> procedure that lets you collect values in a list at a given index in the array. 

{Array.new +Low +High +InitVal ?A}
creates a new and empty array A. Low and High (both integers) are the bounds for the indices of the resulting array. So {A.put I X} and X={A.get I} are legal iff Low<=I<=High. All items of the array are initialized to InitVal.

An array is a record with the following type: 

    type array = unit(low           : int
                      high          : int
                      put           : int x value ->
                      get           : int -> value
                      collect       : int x value ->
                      inc           : int ->
                      clone         : -> array
                      toRecord      : -> record
                      toRecordLabel : literal -> record)
low and high are the index bounds.

{A.put +I X}

sets the item of A under the index I to X.

{A.get +I ?X}

returns the item of A under the index I in X. Raises an exception if I is not a valid index of A, i.e. if I is not in A.low...A.high.

{A.collect +I X}

has the same semantics as {A.put I X|{A.get I}}.

{A.inc +I X}

has the same semantics as {A.put I 1+{A.get I}}. As a precondition {A.get I} must be an integer. Otherwise an exception will be raised.

{A.clone ?R}

returns a copy of A in R, such that {A.get I} is token equal to {R.get I} for I in A.low...A.high.

{A.toRecord ?R}

returns a record R with label unit and features A.low...A.high such that {A.get I} is token equal to R.I for I in A.low...A.high.

{A.toRecordLabel +LI ?R}

is like toRecord except that you can specify an custom label LI.

Gensym

The gensym.ozf functor provides generators for successively different atoms. Such a generator is a function in 

   virtual-string -> atom.
A generator takes a virtual string V and returns a concatenation of V and an integer I. Successive calls increment I. Counting starts from 1.

An important fact about the Gensym functions is that you can even use them in search and in different computation spaces, where they still return the expected values, unlike {NewName} which can return equal names in different spaces.

With G={New} you create a new symbol generator G. Additionally the Gensym functor provides a default symbol generator Gensym.

Example: 

   declare [Gensym] = {Link ['x-ozlib://base/gensym.ozf']} in
   {Show {Gensym.gensym 'stem'}}
   {Show {Gensym.gensym 'stem'}}
   {Show {Gensym.gensym 'stem'}}
   local
      G = {Gensym.new}
   in
      {Show {G 'kuckuck'}}
   end
   {Show {Gensym.gensym 'stem'}}
This shows: 
   stem1
   stem2
   stem3
   kuckuck1
   stem4

Cell

Cells are directly implemented through the cells of the Oz base environment. But this package's cells have a slightly different exchange function that takes the old value instead of the new one as its last argument. Apart from that the uniform names put and get are given. There is one constructor 
Cell.new : value -> cell
 that expects a value X and creates a new cell with X as its initial element. A cell is a record with the following type: 
    type cell = unit(put      : value ->
                     get      : -> value
                     exchange : value -> value
                     clone    : -> cell
                     access   : -> value
                     assign   : value ->
                     set      : value ->)
The type can also be specified by modes as usual in the Oz documentation:

{C.put X}

sets the content of C to X.

{C.get ?X}

returns the current content of C in X.

{C.exchange New ?Old}

sets the cells content to New and returns the old content in Old. Note that the order of the arguments New and Old are reverse in comparison to the Oz base environment's Exchange function. This way you can use exchange like a usual function that takes the new value and evaluates to the old one.

{C.clone ?R}

returns a clone of C in R.

{C.assign X}

is a synonym for {C.put X}.

{C.set X}

is a synonym for {C.put X}.

{C.access ?X}

is a synonym for {C.get ?X}.

Installation

Download the file base-xx.pkg, where xx should be replaced by the current version number, and execute ozmake --freshen --package=base-xx.pkg

In case that you did not already install ozmake on your machine, note that it is also available in the Mogul archive.

By default, all files of the package are installed in the user's ~/.oz directory tree. In particular, all modules are installed in the user's private cache.

Joachim Niehren