Index handler with list of unused: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(6 intermediate revisions by the same user not shown)
Line 2: Line 2:




'''Abstract data structure:'''
'''Abstract data structure:''' [[Index handler]]
A variation of [[Sets and sequences#Maps|map]], where:
# The number of elements is bounded by some fixed positive [[Numbers#natural numbers|natural number]] <math>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.
# 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:'''
'''Implementation invariant:'''
# There is an array <math>A</math> with index range <math>1,...,N</math>, and the component type is the value type of the map.
# There is an array <math>A</math> with index range <math>1,...,N</math> and component type <math>\mathcal{V}</math>.
# There is a [[Sets and sequences|set]] <math>U</math> (for unused) of [[Numbers#natural numbers|natural numbers]].
# There is a [[Sets and sequences|subset]] <math>U</math> (for unused) of <math>\{1,\ldots,N\}</math>.
# For each <math>i\in\{1,...,N_\text{max}\}</math> not in <math>U</math>, <math>A[i]</math> is the value associated with key <math>i</math>.
# For each <math>i\in\{1,...,N_\text{max}\}</math> not in <math>U</math>, <math>A[i]</math> is the value associated with key <math>i</math>.


== Methods ==
== Methods ==


 
# '''Constructor:''' Takes <math>N</math> as an input, creates <math>A</math> and <math>U</math>, and inserts all numbers <math>1,\ldots,N</math> in <math>U</math>.
# The constructor takes <math>N</math> as an argument, creates <math>A</math> and <math>U</math>, and stores all potential keys <math>1,\ldots,N</math> in <math>U</math>.
# '''Reserve index:''' Extracts some <math>i</math> from <math>U</math>, stores <math>V</math> at <math>A[i]</math>, and returns <math>i</math>.
# The method for inserting a new value extracts a key <math>i</math> from <math>U</math>, stores the value at <mah>A[i]</math>and returns <math>i</math>.
# '''Release index:''' Re-inserts <math>i</math> in <math>U</math>.
# The method to look up a value for a given key <math>i</math> returns <math>A[i]</math>.
# '''Get value:''' Returns <math>A[i]</math>.
# The method to remove a key re-inserts the key in <math>U</math>.
# '''Change value:''' Overwrites <math>A[i]</math> by <math>V</math>.

Latest revision as of 11:03, 7 November 2014

Abstract view

Abstract data structure: Index handler

Implementation invariant:

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

Methods

  1. Constructor: Takes [math]\displaystyle{ N }[/math] as an input, creates [math]\displaystyle{ A }[/math] and [math]\displaystyle{ U }[/math], and inserts all numbers [math]\displaystyle{ 1,\ldots,N }[/math] in [math]\displaystyle{ U }[/math].
  2. Reserve index: Extracts some [math]\displaystyle{ i }[/math] from [math]\displaystyle{ U }[/math], stores [math]\displaystyle{ V }[/math] at [math]\displaystyle{ A[i] }[/math], and returns [math]\displaystyle{ i }[/math].
  3. Release index: Re-inserts [math]\displaystyle{ i }[/math] in [math]\displaystyle{ U }[/math].
  4. Get value: Returns [math]\displaystyle{ A[i] }[/math].
  5. Change value: Overwrites [math]\displaystyle{ A[i] }[/math] by [math]\displaystyle{ V }[/math].
Retrieved from "https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Index_handler_with_list_of_unused&oldid=1792"