=== This page is now outdated ===

Objective

The objective of this facility is to provide a means to construct associative array types and use associative array variables with a convenient syntax for the most important operations:

• create an associative array: NEW(dict);
• store an entry: dict["foo"] := 123;
• retrieve an entry: value := dict["foo"];
• remove an entry: dict["foo"] := NIL;
• test if an entry exists: IF "foo" IN dict THEN ... or IF dict["foo"] # NIL THEN ...
• iterate over all entries: FOR item IN dict DO ... END;
• obtain entry count: entryCount := COUNT(dict);
• destroy an associative array: DISPOSE(dict);

Always Opaque

Regardless of how associative array types would be constructed, an associative array type object would always be an opaque pointer. The use of NEW and DISPOSE would always be required to create and destroy the actual associative array structure. Also, there would be no open array parameter that matches an associative array.

TYPE Dictionary = (* associative array *) OF Bar;

VAR dict : Dictionary;

PROCEDURE foo ( a : ARRAY OF Bar );

BEGIN
    NEW(dict);
    foo(dict); (* compile time error: incompatible type *)

Constructing Associative Arrays using ARRAY Syntax

Associative array types could be constructed by extending the ARRAY type constructor syntax and semantics. In any case it is assumed that the retrieval key for associative arrays will always be of type ARRAY OF CHAR.

The most obvious syntax would be ...

TYPE Dictionary : ARRAY ARRAY OF CHAR OF ValueType;

but this seems unnecessarily cluttered.

This may be alleviated by indirection ...

TYPE KeyStr = ARRAY 20 OF CHAR;
TYPE Dictionary = ARRAY KeyStr OF ValueType;

but might unnecessarily limit keys to the string type used in the declaration.

A more flexible alternative may be ...

TYPE Dictionary = ARRAY "" OF ValueType;

Other alternatives would be ...

TYPE Dictionary = ASSOCIATIVE ARRAY OF ValueType;

TYPE Dictionary = DICTIONARY OF ValueType;

TYPE Dictionary = COLLECTION OF ValueType;

any of these would require a new reserved word.

Constructing Associative Arrays using Library Types

An alternative approach to constructing associative array types would be to define them as opaque types in a library module and then provide bindings to facilitate the more convenient syntax.

DEFINITION MODULE Dictionary;

TYPE Dictionary = OPAQUE;

PROCEDURE [NEW] new ( dict : Dictionary );

PROCEDURE [.] valueForKey ( dict : Dictionary; key : ARRAY OF CHAR ) : <valueType>;

PROCEDURE [!] storeValue ( dict : Dictionary; key : ARRAY OF CHAR; value : <valueType> );

PROCEDURE [IN] keyExists ( dict : Dictionary; key : ARRAY OF CHAR ) : BOOLEAN;

PROCEDURE [FOR] nextValue ( dict : Dictionary; VAR key : ARRAY OF CHAR; VAR value : <valueType> );

PROCEDURE [COUNT] entryCount ( dict : Dictionary ) : LONGCARD;

PROCEDURE [DISPOSE] dispose ( dict : Dictionary );

END Dictionary.

Example: TypeSampleCollection

However, this approach requires far more effort to construct a new associative array type.

Combined Approach

The best solution might be a combined approach.

The built in type constructor would be the convenient general use tool, like CARDINAL, INTEGER and REAL for numerics, and library defined collection types that use bindings to provide the same syntax as used with the built in variant would be for more specialised uses, just like library defined BCD, COMPLEX and vector types are for numerics.

Builtin associative array constructor ...

TYPE Dictionary = DICTIONARY OF ValueType;

TYPE Dictionary = COLLECTION OF ValueType; (* alternative *)

Library defined complement ...

DEFINITION MODULE SearchTree;

TYPE SearchTree = OPAQUE; (* any unspecified opaque type is considered a collection *)

TYPE SearchTree = OPAQUE DICTIONARY; (* alternatively this, or ... *)

TYPE SearchTree = DICTIONARY; (* another possible alternative *)

TYPE SearchTree = OPAQUE COLLECTION; (* yet another alternative *)

TYPE SearchTree = COLLECTION; (* yet another alternative *)

(* define bindings *)

END SearchTree.