ADT:Dictionary

This module is a reimplementation of the Python dictionary code in Oberon-2. It is based on version 2.65 of the python file `src/Objects/dictobject.c'. It maps objects on other objects. Some bit twiddling is required, partially due to the algorithm and partially due to performance, which may impede portability of the code.

Differences between `dictobject.c' and this implementation:

Import List

    ADT:Storable
    IO
    Object
    Object
    RT0
 
Class List
DictionaryDesc
Dummy
Class Summary: DictionaryDesc [Detail]
  +---RT0.Object
       |
       +---Object.Object
            |
            +---ADT:Storable.Object
                 |
                 +--ADT:Dictionary.DictionaryDesc
Inherited Methods

From RT0.Object:

          Finalize

From Object.Object:

          Equals, HashCode, ToString

From ADT:Storable.Object:

          Load, Store

 
Class Summary: Dummy [Detail]
  +---RT0.Object
       |
       +---Object.Object
            |
            +--ADT:Dictionary.Dummy
Method Summary
Destroy()

          
Inherited Methods

From RT0.Object:

          Finalize

From Object.Object:

          Equals, HashCode, ToString

 
Type Summary
Dictionary = POINTER TO DictionaryDescKV

          
[Entry] = RECORD ... END

          
[Hash] = LONGINT

          
[Index] = LONGINT

          
Item = RECORD ... END

          
ItemArrayPtr = POINTER TO ARRAY OF ItemKV

          
IterKeys = POINTER TO IterKeysDescKV

          
[IterKeysDesc] = RECORD ... END

          
IterValues = POINTER TO IterValuesDescKV

          
[IterValuesDesc] = RECORD ... END

          
Key = Object

          Type of key entries in the dictionary.
[Table] = POINTER TO ARRAY OF EntryKV

          
Value = Object

          Type of value entries in the dictionary.
Procedure Summary
Clear()

          Removes all items from the dictionary dict.
Copy(): DictionaryKV

          Creates a shallow copy of the dictionary dict.
Delete(K)

          Removes the item with the key key from the dictionary dict.
Destroy()

          
Equals(Object): BOOLEAN

          Indicates whether some other object is "equal to" this one.
Get(K): V

          Retrieves the value associated with key in the dictionary dict.
HasKey(K): BOOLEAN

          Tests if an item in dict exists with the key key.
HashCode(): Hash

          Returns a hash code value for the object.
INIT()

          Initializes dict to an empty dictionary.
INIT(DictionaryKV)

          
INIT(DictionaryKV)

          
[Insert](K, Hash, V)

          
[InternalLookup](K, Hash): LONGINT

          
Items(): ItemArrayPtrKV

          Returns the list of items of the dictionary dict.
IterKeys(): IterKeysKV

          Returns an iterator that traverses the keys of dict in no particular.
IterValues(): IterValuesKV

          Returns an iterator that traverses the values of dict in no particular.
Keys(): ObjectArrayPtrK

          Returns the list of keys of the dictionary dict.
Load(Reader)

          Loads data of dict from r.
Lookup(K, VAR V): BOOLEAN

          If key exists in the dictionary dict, then the procedure assigns the value of key to value and returns TRUE; otherwise, it returns FALSE and value is undefined.
New(): Dictionary

          Creates a new, empty dictionary.
Next(VAR K): BOOLEAN

          
Next(VAR V): BOOLEAN

          
[Resize](LONGINT)

          
Set(K, V)

          Sets the value for key key in the dictionary dict to value.
Size(): LONGINT

          Returns the number of items in the dictionary.
Store(Writer)

          Stores data of dict to w.
Values(): ObjectArrayPtrV

          Returns the list of values of the dictionary dict.

Class Detail: DictionaryDesc
 
Class Detail: Dummy
Method Detail

Destroy

PROCEDURE (dummy: Dummy) Destroy()
 
Type Detail

Dictionary

TYPE Dictionary = POINTER TO DictionaryDescKV

Entry

TYPE [Entry] = RECORD
             END

Hash

TYPE [Hash] = LONGINT

Index

TYPE [Index] = LONGINT

Item

TYPE Item = RECORD
                key: K;
                value: V;
            END

ItemArrayPtr

TYPE ItemArrayPtr = POINTER TO ARRAY OF ItemKV

IterKeys

TYPE IterKeys = POINTER TO IterKeysDescKV

IterKeysDesc

TYPE [IterKeysDesc] = RECORD
                    END

IterValues

TYPE IterValues = POINTER TO IterValuesDescKV

IterValuesDesc

TYPE [IterValuesDesc] = RECORD
                      END

Key

TYPE Key = Object

Type of key entries in the dictionary.


Table

TYPE [Table] = POINTER TO ARRAY OF EntryKV

Value

TYPE Value = Object

Type of value entries in the dictionary.

Procedure Detail

Clear

PROCEDURE (dict: Dictionary) Clear()

Removes all items from the dictionary dict.


Copy

PROCEDURE (dict: Dictionary) Copy(): DictionaryKV

Creates a shallow copy of the dictionary dict. The key and value objects themselves are not copied.


Delete

PROCEDURE (dict: Dictionary) Delete(key: K)

Removes the item with the key key from the dictionary dict.

Pre-condition: n item with the key key exists in the dictionary dict. This implies that key is not NIL.


Destroy

PROCEDURE (dict: Dictionary) Destroy()

Equals

PROCEDURE (dict: Dictionary) Equals(obj: Object): BOOLEAN

Indicates whether some other object is "equal to" this one.

The Object.Equals method implements an equivalence relation:

The `Equals' method for class Object implements the most discriminating possible equivalence relation on objects; that is, for any reference values `x' and `y', this method returns TRUE if and only if `x' and `y' refer to the same object (`x=y' has the value TRUE).

[Description inherited from Equals]


Get

PROCEDURE (dict: Dictionary) Get(key: K): V

Retrieves the value associated with key in the dictionary dict.

Pre-condition: An item with the key key exists in the dictionary dict. This implies that key is not NIL.


HasKey

PROCEDURE (dict: Dictionary) HasKey(key: K): BOOLEAN

Tests if an item in dict exists with the key key.

Pre-condition: key is not NIL.


HashCode

PROCEDURE (dict: Dictionary) HashCode(): Hash

Returns a hash code value for the object. This method is supported for the benefit of dictionaries such as those provided by ADT:Dictionary.

The general contract of Object.HashCode is:

As much as is reasonably practical, the Object.HashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required.)

[Description inherited from HashCode]


INIT

PROCEDURE (dict: Dictionary) INIT()

Initializes dict to an empty dictionary.


INIT

PROCEDURE (iter: IterKeys) INIT(dict: DictionaryKV)

INIT

PROCEDURE (iter: IterValues) INIT(dict: DictionaryKV)

Insert

PROCEDURE (dict: Dictionary) [Insert](key: K; 
                 hash: Hash; 
                 value: V)

InternalLookup

PROCEDURE (dict: Dictionary) [InternalLookup](key: K; 
                         hash: Hash): LONGINT

Items

PROCEDURE (dict: Dictionary) Items(): ItemArrayPtrKV

Returns the list of items of the dictionary dict. The items are listed in no particular order.


IterKeys

PROCEDURE (dict: Dictionary) IterKeys(): IterKeysKV

Returns an iterator that traverses the keys of dict in no particular. If no changes are made two the dictionary in between, then two iterations over the keys will return the key objects in the same order. Beyond this, no ordering guarantees are made.

Behaviour of the iterator is undefined if the dictionary is changed while the iterator is traversing it.


IterValues

PROCEDURE (dict: Dictionary) IterValues(): IterValuesKV

Returns an iterator that traverses the values of dict in no particular. If no changes are made two the dictionary in between, then two iterations over the values will return the value objects in the same order. Beyond this, no ordering guarantees are made.

Behaviour of the iterator is undefined if the dictionary is changed while the iterator is traversing it.


Keys

PROCEDURE (dict: Dictionary) Keys(): ObjectArrayPtrK

Returns the list of keys of the dictionary dict. The keys are listed in no particular order.


Load

PROCEDURE (dict: Dictionary) Load(r: Reader)
  RAISES Error;

Loads data of dict from r. Nested record pointers are loaded by calling the type-bound procecdure Reader.ReadObject. This procedure must be symmetric to Object.Store, or data internalization will break, causing undefined object state or program termination.

Note: When internalizing a file with alien objects, it is possible that the type-bound procedure Object.Load is invoked more than once for a single object. Except for the results of the last call, all duplicates are discarded. Because of this, all changes by this procedure to any program state that is not part of the object dict are deprecated.

Pre-condition: This procedure is either activated by a super call, or from the procedure Reader.ReadObject.

[Description inherited from Load]


Lookup

PROCEDURE (dict: Dictionary) Lookup(key: K; 
                 VAR value: V): BOOLEAN

If key exists in the dictionary dict, then the procedure assigns the value of key to value and returns TRUE; otherwise, it returns FALSE and value is undefined.

Pre-condition: key is not NIL.


New

PROCEDURE New(): Dictionary

Creates a new, empty dictionary.


Next

PROCEDURE (iter: IterKeys) Next(VAR key: K): BOOLEAN

Next

PROCEDURE (iter: IterValues) Next(VAR value: V): BOOLEAN

Resize

PROCEDURE (dict: Dictionary) [Resize](minUsed: LONGINT)

Set

PROCEDURE (dict: Dictionary) Set(key: K; 
              value: V)

Sets the value for key key in the dictionary dict to value. If an item with this key already exists, its value is replaced. Otherwise, a new item is created with the given (key, value) pair.

Pre-condition: key is not NIL.


Size

PROCEDURE (dict: Dictionary) Size(): LONGINT

Returns the number of items in the dictionary.


Store

PROCEDURE (dict: Dictionary) Store(w: Writer)
  RAISES Error;

Stores data of dict to w. Nested record pointers are stored by calling the type-bound procedure Writer.WriteObject. The procedure is not allowed to make any changes to the global state of the program, except for calling the `Write' methods of the writer w. Any redefinition of this procedure must include a super call, preferably as the first statement of the procedure body.

Pre-condition: This procedure is either activated by a super call, or from the procedure Writer.WriteObject.

[Description inherited from Store]


Values

PROCEDURE (dict: Dictionary) Values(): ObjectArrayPtrV

Returns the list of values of the dictionary dict. The values are listed in no particular order.