Index handler with list of unused: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
(5 intermediate revisions by the same user not shown) | |||
Line 5: | Line 5: | ||
'''Implementation invariant:''' | '''Implementation invariant:''' | ||
# There is an array <math>A</math> with index range <math>1,...,N</math> | # 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| | # 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>. | ||
# | # '''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>. | ||
# | # '''Release index:''' Re-inserts <math>i</math> in <math>U</math>. | ||
# | # '''Get value:''' Returns <math>A[i]</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:
- There is an array [math]\displaystyle{ A }[/math] with index range [math]\displaystyle{ 1,...,N }[/math] and component type [math]\displaystyle{ \mathcal{V} }[/math].
- There is a subset [math]\displaystyle{ U }[/math] (for unused) of [math]\displaystyle{ \{1,\ldots,N\} }[/math].
- 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
- 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].
- 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].
- Release index: Re-inserts [math]\displaystyle{ i }[/math] in [math]\displaystyle{ U }[/math].
- Get value: Returns [math]\displaystyle{ A[i] }[/math].
- Change value: Overwrites [math]\displaystyle{ A[i] }[/math] by [math]\displaystyle{ V }[/math].