Index handler: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(29 intermediate revisions by the same user not shown)
Line 1: Line 1:
== Abstract view ==
== Representation invariant ==


'''Representation invariant:'''
This abstract data structure is [[Genericity|generic]] and parameterized by some value type <math>\mathcal{V}</math>. An object of an implementation of this abstract data structure is repesented by:
# There is a positive [[Numbers#natural numbers|natural number]] <math>N</math>.
# A positive integral number <math>N</math>.
# For each object, there is a specific, dynamically changing partition of <math>\{1,\ldots,N\}</math> into '''used''' and '''unused indexes'''.
# A subset <math>I</math> of <math>\{1,\ldots,N\}</math>, the '''currently used indexes'''.
# For each used index, a value is stored.
# A mapping <math>I\rightarrow\mathcal{V}</math>.


'''Remarks:'''
# This abstract data structure may be viewed as a specific, quite restricted type of [[Sets and sequences#Maps|map]].
# The returned indexes have to be managed outside this data structure. For example, in [[Dijkstra]] and [[Prim]], it might be a good option to make the index a node attribute,


'''Implementation invariant:'''
== Method ==


# There is an array <math>Indexes</math> with index range <math>1,...,N_\text{max}</math> and integral components from <math>\{1,...,N_\text{max}\}</math>.
'''Name:''' reserve index
# There is a [[Sets and sequences|set]] <math>U</math> (for unused) of [[Numbers#natural numbers|natural numbers]], which has length <math>N_\text{max}-N</math> and stores pairwise different numbers from <math>\{1,...,N_\text{max}\}</math>.
# For each <math>i\in\{1,...,N_\text{max}\}</math> not in <math>Unused</math>:
## <math>Positions[i]</math> is the position of one of the <math>N</math> heap items in <math>TheHeap</math>. As long as this heap item is stored, <math>i</math> is permanently associated with this heap item (and can hence be used to locate and access this heap item at any time). The correspondence between the heap items and these numbers <math>i</math> is one-to-one.


== Methods ==
'''Input:''' A value <math>V\in\mathcal{V}</math>.


# If an index is requested, <math>U\neq\emptyset</math> is a precondition. Then one index is extracted from <math>U</math> and returned.
'''Precondition:''' <math>|I|<N</math>.


# If an index is given back, it is inserted in <math>U</math>.
'''Return value:''' One of the indexes not in <math>I</math>.
 
'''Postcondition:''' The returned index is inserted in <math>I</math> and associated with <math>V</math>.
 
== Method ==
 
'''Name:''' release index
 
'''Input:''' An integral number <math>i</math>.
 
'''Precondition:''' <math>i\in I</math>.
 
'''Postcondition:''' <math>i</math> is extracted from <math>I</math>, and the associated value is dropped.
 
== Method ==
 
'''Name:''' get value
 
'''Input:''' An integral number <math>i</math>.
 
'''Precondition:''' <math>i\in I</math>.
 
'''Return value:''' The value currently associated with <math>i</math>.
 
== Method ==
 
'''Name:''' change value
 
'''Input:''' An integral number <math>i</math> and a value <math>V\in\mathcal{V}</math>.
 
'''Precondition:''' <math>i\in I</math>.
 
'''Postcondition:''' The value currently associated with <math>i</math> is overwritten by <math>V</math>.
 
== Known implementations ==
 
# [[Index handler with list of unused]]

Latest revision as of 11:02, 7 November 2014

Representation invariant

This abstract data structure is generic and parameterized by some value type [math]\displaystyle{ \mathcal{V} }[/math]. An object of an implementation of this abstract data structure is repesented by:

  1. A positive integral number [math]\displaystyle{ N }[/math].
  2. A subset [math]\displaystyle{ I }[/math] of [math]\displaystyle{ \{1,\ldots,N\} }[/math], the currently used indexes.
  3. A mapping [math]\displaystyle{ I\rightarrow\mathcal{V} }[/math].

Remarks:

  1. This abstract data structure may be viewed as a specific, quite restricted type of map.
  2. The returned indexes have to be managed outside this data structure. For example, in Dijkstra and Prim, it might be a good option to make the index a node attribute,

Method

Name: reserve index

Input: A value [math]\displaystyle{ V\in\mathcal{V} }[/math].

Precondition: [math]\displaystyle{ |I|\lt N }[/math].

Return value: One of the indexes not in [math]\displaystyle{ I }[/math].

Postcondition: The returned index is inserted in [math]\displaystyle{ I }[/math] and associated with [math]\displaystyle{ V }[/math].

Method

Name: release index

Input: An integral number [math]\displaystyle{ i }[/math].

Precondition: [math]\displaystyle{ i\in I }[/math].

Postcondition: [math]\displaystyle{ i }[/math] is extracted from [math]\displaystyle{ I }[/math], and the associated value is dropped.

Method

Name: get value

Input: An integral number [math]\displaystyle{ i }[/math].

Precondition: [math]\displaystyle{ i\in I }[/math].

Return value: The value currently associated with [math]\displaystyle{ i }[/math].

Method

Name: change value

Input: An integral number [math]\displaystyle{ i }[/math] and a value [math]\displaystyle{ V\in\mathcal{V} }[/math].

Precondition: [math]\displaystyle{ i\in I }[/math].

Postcondition: The value currently associated with [math]\displaystyle{ i }[/math] is overwritten by [math]\displaystyle{ V }[/math].

Known implementations

  1. Index handler with list of unused
Retrieved from "https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Index_handler&oldid=1790"