Index handler: Difference between revisions
(→Method) |
No edit summary |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 6: | Line 6: | ||
# A mapping <math>I\rightarrow\mathcal{V}</math>. | # 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, | |||
== Method == | == Method == | ||
| Line 12: | Line 14: | ||
'''Name:''' reserve index | '''Name:''' reserve index | ||
''' | '''Input:''' A value <math>V\in\mathcal{V}</math>. | ||
'''Precondition:''' <math>|I|<N</math>. | '''Precondition:''' <math>|I|<N</math>. | ||
| Line 24: | Line 26: | ||
'''Name:''' release index | '''Name:''' release index | ||
''' | '''Input:''' An integral number <math>i</math>. | ||
'''Precondition:''' <math>i\in I</math>. | '''Precondition:''' <math>i\in I</math>. | ||
'''Postcondition:''' <math>i</math> is extracted from <math> | '''Postcondition:''' <math>i</math> is extracted from <math>I</math>, and the associated value is dropped. | ||
== Method == | == Method == | ||
| Line 34: | Line 36: | ||
'''Name:''' get value | '''Name:''' get value | ||
''' | '''Input:''' An integral number <math>i</math>. | ||
'''Precondition:''' <math>i\in I</math>. | '''Precondition:''' <math>i\in I</math>. | ||
| Line 44: | Line 46: | ||
'''Name:''' change value | '''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>. | '''Precondition:''' <math>i\in I</math>. | ||
'''Postcondition:''' The value currently associated with <math>i</math> is overwritten by <math>V</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:
- A positive integral number [math]\displaystyle{ N }[/math].
- A subset [math]\displaystyle{ I }[/math] of [math]\displaystyle{ \{1,\ldots,N\} }[/math], the currently used indexes.
- A mapping [math]\displaystyle{ I\rightarrow\mathcal{V} }[/math].
Remarks:
- This abstract data structure may be viewed as a specific, quite restricted type of 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,
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].