Index handler with list of unused

From Algowiki
Revision as of 14:22, 20 October 2014 by Weihe (talk | contribs) (→‎Methods)
Jump to navigation Jump to search

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 argument, 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].