Index handler: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 7: Line 7:
# The key type is the range <math>\{1,\ldots,N\}</math>.
# The key type is the range <math>\{1,\ldots,N\}</math>.
# Instead of a method for inserting (key,value)-pairs, a value can be inserted alone, and the key for referring to the value is returned. As a precondition, less than <math>N</math> values must be currently stored in that index handler object.
# Instead of a method for inserting (key,value)-pairs, a value can be inserted alone, and the key for referring to the value is returned. As a precondition, less than <math>N</math> values must be currently stored in that index handler object.
# The methods to retrieve a value for a key and to remove a key and the associated value from the index handler object are identical to te correspnding metods of normal maps. A key may be reused by the index handler object after removal.
# The methods to retrieve a value for a key and to remove a key and the associated value from the index handler object are basically identical to the corresponding methods of normal maps. A key may be reused by the index handler object after removal.





Revision as of 08:49, 10 October 2014

Abstract view

Abstract data structure: A variation of map, where:

  1. The number of elements is bounded by some fixed positive natural number [math]\displaystyle{ N }[/math].
  2. The key type is the range [math]\displaystyle{ \{1,\ldots,N\} }[/math].
  3. Instead of a method for inserting (key,value)-pairs, a value can be inserted alone, and the key for referring to the value is returned. As a precondition, less than [math]\displaystyle{ N }[/math] values must be currently stored in that index handler object.
  4. The methods to retrieve a value for a key and to remove a key and the associated value from the index handler object are basically identical to the corresponding methods of normal maps. A key may be reused by the index handler object after removal.


Implementation invariant:

  1. There is an array [math]\displaystyle{ A }[/math] with index range [math]\displaystyle{ 1,...,N }[/math], and the component type is the value type of the map.
  2. There is a set [math]\displaystyle{ U }[/math] (for unused) of natural numbers of natural numbers.
  3. For each [math]\displaystyle{ i\in\{1,...,N_\text{max}\} }[/math] not in [math]\displaystyle{ Unused }[/math], [math]\displaystyle{ A[i] }[/math] is the value associated with key [math]\displaystyle{ i }[/math].

Methods

  1. The constructor takes [math]\displaystyle{ N }[/math] as an argument, creates [math]\displaystyle{ A }[/math] and [math]\displaystyle{ U }[/math], and stores all potential keys [math]\displaystyle{ 1,\ldots,N }[/math] in [math]\displaystyle{ U }[/math].
  2. The method for inserting a new value extracts a key [math]\displaystyle{ i }[/math] from [math]\displaystyle{ U }[/math], stores the value at <mah>A[i]</math>and returns [math]\displaystyle{ i }[/math].
  3. The method to look up a value for a given key [math]\displaystyle{ i }[/math] returns [math]\displaystyle{ A[i] }[/math].
  4. The method to remove a key re-inserts the key in [math]\displaystyle{ U }[/math].