Ordered sequence: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(13 intermediate revisions by the same user not shown)
Line 5: Line 5:
'''Representation invariant:'''
'''Representation invariant:'''
# The abstract data structure '''ordered sequence''' implements sorted sequences as defined [[Sets and sequences|here]].
# The abstract data structure '''ordered sequence''' implements sorted sequences as defined [[Sets and sequences|here]].
# This abstract data structure is [[Genericity|generic]] and parameterized by a fixed key type <math>\kappa</math>.
# This abstract data structure is [[Genericity|generic]] and parameterized by a fixed key type <math>\mathcal{K}</math>.


== Insert at position ==
== Insert at position ==
'''Input:''' A key <math>K \in \kappa</math> and a nonnegative integral position <math>p</math>.
'''Input:''' A key <math>K \in \mathcal{K}</math> and a nonnegative integral position <math>\ell</math>.


'''Output:''' a Boolean value, which is true if, and only if, <math>p\in\{0,\ldots,n\}</math>, where <math>n</math> is the length of the list.
'''Output:''' a Boolean value, which is '''true''' if, and only if, <math>\ell\in\{0,\ldots,n\}</math>, where <math>n</math> is the length of the list.


'''Precondition:'''
'''Precondition:''' None.


'''Postcondition:''' If the output ist '''true''', a new element with the key <math>K</math> is inserted at position <math>p</math>.
'''Postcondition:''' If the output ist '''true''', a new element with the key <math>K</math> is inserted at position <math>\ell</math>. If <math>\ell=0</math>, this means the new element is attached before the prior first element. Otherwise, this means it is inserted between the <math>(\ell-1)</math>-th element and the prior <math>\ell</math>-th element.


== Find ==
== Find ==
'''Input:''' A key <math>K \in \kappa </math>.
'''Input:''' A key <math>K \in \mathcal{K} </math>.


'''Output:''' A Boolean value, which is '''''true''''' if, and only if, <math>K</math> is currently contained in the sequence.
'''Output:''' A Boolean value, which is '''true''' if, and only if, <math>K</math> is currently contained in the sequence.


'''Precondition:'''
'''Precondition:''' None.


'''Postcondition:'''
'''Postcondition:''' None.


== Remove ==
== Remove ==
'''Input:''' A key <math>K \in \kappa</math>.
'''Input:''' A key <math>K \in \mathcal{K}</math>.


'''Output:''' A Boolean value, which is '''''true''''' if, and only if, <math>K</math> is currently stored in the sequence.
'''Output:''' A Boolean value, which is '''true''' if, and only if, <math>K</math> is currently stored in the sequence.


'''Precondition:'''
'''Precondition:''' None.


'''Postcondition:''' If the output is '''''true''''', one occurrence of <math>K</math> is removed.
'''Postcondition:''' If the output is '''true''', one occurrence of <math>K</math> is removed.


== Known Implementations ==
== Known Implementations ==

Latest revision as of 12:52, 21 May 2015


General Information

Representation invariant:

  1. The abstract data structure ordered sequence implements sorted sequences as defined here.
  2. This abstract data structure is generic and parameterized by a fixed key type [math]\displaystyle{ \mathcal{K} }[/math].

Insert at position

Input: A key [math]\displaystyle{ K \in \mathcal{K} }[/math] and a nonnegative integral position [math]\displaystyle{ \ell }[/math].

Output: a Boolean value, which is true if, and only if, [math]\displaystyle{ \ell\in\{0,\ldots,n\} }[/math], where [math]\displaystyle{ n }[/math] is the length of the list.

Precondition: None.

Postcondition: If the output ist true, a new element with the key [math]\displaystyle{ K }[/math] is inserted at position [math]\displaystyle{ \ell }[/math]. If [math]\displaystyle{ \ell=0 }[/math], this means the new element is attached before the prior first element. Otherwise, this means it is inserted between the [math]\displaystyle{ (\ell-1) }[/math]-th element and the prior [math]\displaystyle{ \ell }[/math]-th element.

Find

Input: A key [math]\displaystyle{ K \in \mathcal{K} }[/math].

Output: A Boolean value, which is true if, and only if, [math]\displaystyle{ K }[/math] is currently contained in the sequence.

Precondition: None.

Postcondition: None.

Remove

Input: A key [math]\displaystyle{ K \in \mathcal{K} }[/math].

Output: A Boolean value, which is true if, and only if, [math]\displaystyle{ K }[/math] is currently stored in the sequence.

Precondition: None.

Postcondition: If the output is true, one occurrence of [math]\displaystyle{ K }[/math] is removed.

Known Implementations

  1. Linked list
  2. Doubly-linked list
  3. Array list