# 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:

- NIL can be used as a value. This implies that the field ``Entry.value`' cannot be used to determine if the entry is in use or not.

- Any inefficiencies in this implementation are my fault, and do not originate in the Python 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 DictionaryDesc K V
[Entry] = RECORD ... END
[Hash] = LONGINT
[Index] = LONGINT
Item = RECORD ... END
ItemArrayPtr = POINTER TO ARRAY OF Item K V
IterKeys = POINTER TO IterKeysDesc K V
[IterKeysDesc] = RECORD ... END
IterValues = POINTER TO IterValuesDesc K V
[IterValuesDesc] = RECORD ... END
Key = Object Type of key entries in the dictionary.
[Table] = POINTER TO ARRAY OF Entry K V
Value = Object Type of value entries in the dictionary.

Procedure Summary
Clear() Removes all items from the dictionary dict.
Copy(): Dictionary K V 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(Dictionary K V)
INIT(Dictionary K V)
[Insert](K, Hash, V)
[InternalLookup](K, Hash): LONGINT
Items(): ItemArrayPtr K V Returns the list of items of the dictionary dict.
IterKeys(): IterKeys K V Returns an iterator that traverses the keys of dict in no particular.
IterValues(): IterValues K V Returns an iterator that traverses the values of dict in no particular.
Keys(): ObjectArrayPtr K 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(): ObjectArrayPtr V 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:

> - It is reflexive: for any reference value ``x`', ``x.Equals(x)`' should return TRUE.

> - It is symmetric: for any reference values ``x`' and ``y`', ``x.Equals(y)`' should return TRUE if and only if ``y.Equals(x)`' returns TRUE.

> - It is transitive: for any reference values ``x`', ``y`', and ``z`', if ``x.Equals(y)`' returns TRUE and ``y.Equals(z)`' returns TRUE, then ``x.Equals(z)`' should return TRUE.

> - It is consistent: for any reference values ``x`' and ``y`', multiple invocations of ``x.Equals(y)`' consistently return TRUE or consistently return FALSE, provided no information used in equals comparisons on the object is modified.

> - For any non-NIL reference value ``x`', ``x.Equals(NIL)`' should return FALSE.

> 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:

> - Whenever it is invoked on the same object more than once during an execution of an application, the Object.HashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.

> - If two objects are equal according to the Object.Equals method, then calling the Object.HashCode method on each of the two objects must produce the same integer result.

> - It is not required that if two objects are unequal according to the Object.Equals method, then calling the Object.HashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of dictionaries.

> 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.