Sorted sequence: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(17 intermediate revisions by 2 users not shown)
Line 4: Line 4:
== General Information ==
== General Information ==
'''Representation invariant:'''
'''Representation invariant:'''
# The abstract data structure '''sorted sequence''' implements sorted sequences as defined [[Sets and sequences|here]].
# The abstract data structure '''sorted sequence''' implements sorted sequences as defined [[Sets and sequences#Ordered and sorted sequences|here]].
# This abstract data structure is [[Genericity|generic]] and parameterized by a fixed key type <math>\kappa</math> and a fixed [[Genericity|comparision]] <math>c</math> defined on <math>\kappa</math>.
# This abstract data structure is [[Genericity|generic]] and parameterized by a fixed key type <math>\mathcal{K}</math> and a fixed [[Genericity#Comparison|comparison]] <math>c</math> defined on <math>\mathcal{K}</math>.
 
== Constructor ==
 
Gets a [[Genericity#Comparison|comparison]] <math>c</math> to maintain and initializes the sequence so as to be empty.


'''Constructor:''' Gets a [[Genericity|comparision]] <math>c</math> and initializes ths sequence so as to be empty.


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


'''Output:'''
'''Output:''' None.


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


'''Postcondition:''' A new element with the key <math>K</math> is inserted at the appropriate position in sorting order.
'''Postcondition:''' A new element with the key <math>K</math> is inserted at an appropriate position in sorting order, so the sorting order is maintained.


== Traverse ==
== Traverse ==


'''Input:'''
'''Input:''' None.


'''Output:''' A [[Linear sequence]] <math>L</math> containing all elements of the sorted sequence in acending order.
'''Output:''' A linear list structure <math>L</math> containing all elements of the sorted sequence in ascending order.


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


'''Postcondition:''' All keys of the sorted sequence are appended to <math>L</math> in ascending order.
'''Postcondition:''' None.


== Find ==
== Find ==
'''Input:''' A key <math>K \in \mathcal{K} </math>.
'''Output:''' A Boolean value, which is '''true''' if, and only if, at least one occurrence of <math>K</math> is currently contained in the sequence.
'''Precondition:''' None.
'''Postcondition:''' None.


== Remove ==
== Remove ==
'''Input:''' A key <math>K \in \mathcal{K}</math>.
'''Output:''' A Boolean value, which is '''true''' if, and only if, at least one occurrence of <math>K</math> is currently contained in the sequence.
'''Precondition:''' None.
'''Postcondition:''' If the output is '''true''', exactly one occurrence of <math>K</math> is removed. The choice of the occurrence to be removed is unspecified.


== Known Implementations ==
== Known Implementations ==
 
# [[B-Trees]]
== Remark ==
# [[Binary Search Tree]]

Latest revision as of 13:06, 21 May 2015


General Information

Representation invariant:

  1. The abstract data structure sorted 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] and a fixed comparison [math]\displaystyle{ c }[/math] defined on [math]\displaystyle{ \mathcal{K} }[/math].

Constructor

Gets a comparison [math]\displaystyle{ c }[/math] to maintain and initializes the sequence so as to be empty.


Insert

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

Output: None.

Precondition: None.

Postcondition: A new element with the key [math]\displaystyle{ K }[/math] is inserted at an appropriate position in sorting order, so the sorting order is maintained.

Traverse

Input: None.

Output: A linear list structure [math]\displaystyle{ L }[/math] containing all elements of the sorted sequence in ascending order.

Precondition: None.

Postcondition: None.

Find

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

Output: A Boolean value, which is true if, and only if, at least one occurrence of [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, at least one occurrence of [math]\displaystyle{ K }[/math] is currently contained in the sequence.

Precondition: None.

Postcondition: If the output is true, exactly one occurrence of [math]\displaystyle{ K }[/math] is removed. The choice of the occurrence to be removed is unspecified.

Known Implementations

  1. B-Trees
  2. Binary Search Tree