Package components.sortingmachine

Class SortingMachine5<T>

java.lang.Object
components.sortingmachine.SortingMachineSecondary<T>
components.sortingmachine.SortingMachine5<T>
Type Parameters:
T - type of SortingMachine entries
All Implemented Interfaces:
SortingMachine<T>, SortingMachineKernel<T>, Standard<SortingMachine<T>>, Iterable<T>
public class SortingMachine5<T> extends SortingMachineSecondary<T>
SortingMachine represented as a Queue and an array (using an embedding of heap sort), with implementations of primary methods. The representation invariant is designed to have the implementation release references returned by removeFirst.
Mathematical Definitions:
IS_TOTAL_PREORDER (
  r: binary relation on T
 ) : boolean is
 for all x, y, z: T
  ((r(x, y) or r(y, x))  and
   (if (r(x, y) and r(y, z)) then r(x, z)))

SUBTREE_IS_HEAP (
  a: string of T,
  start: integer,
  stop: integer,
  r: binary relation on T
 ) : boolean is
 [the subtree of a (when a is interpreted as a complete binary tree) rooted
  at index start and only through entry stop of a satisfies the heap
  ordering property according to the relation r]

SUBTREE_ARRAY_ENTRIES (
  a: string of T,
  start: integer,
  stop: integer
 ) : finite multiset of T is
 [the multiset of entries in a that belong to the subtree of a
  (when a is interpreted as a complete binary tree) rooted at
  index start and only through entry stop]
Representation Invariant (concrete invariant of $this):
IS_TOTAL_PREORDER([relation computed by $this.machineOrder.compare method])  and
if $this.insertionMode then
  $this.heapSize = 0
else
  $this.entries = <>  and
  for all i: integer
      where (0 <= i  and  i < $this.heapSize)
    ([entry at position i in $this.heap is not null])  and
  for all i: integer
      where ($this.heapSize <= i  and  i < |$this.heap|)
    ([entry at position i in $this.heap is null])  and
  SUBTREE_IS_HEAP($this.heap, 0, $this.heapSize - 1,
    [relation computed by $this.machineOrder.compare method])  and
  0 <= $this.heapSize <= |$this.heap|
Abstraction Relation (interpretation mapping between $this and this):
if $this.insertionMode then
  this = (true, $this.machineOrder, multiset_entries($this.entries))
else
  this = (false, $this.machineOrder,
    multiset_entries($this.heap[0, $this.heapSize)))

  • Constructor Details

    • SortingMachine5

      public SortingMachine5(Comparator<T> order)
      Constructor from order.
      Parameters:
      order - total preorder for sorting

  • Method Details

    • newInstance

      public final SortingMachine<T> newInstance()
      Description copied from interface: Standard
      Returns a new object with the same dynamic type as this, having an initial value. If the type T has a no-argument constructor, then the value of the new returned object satisfies the contract of the no-argument constructor for T. If T does not have a no-argument constructor, then the value of the new returned object satisfies the contract of the constructor call that was used to initialize this .
      Returns:
      new object "like" this with an initial value

    • clear

      public final void clear()
      Description copied from interface: Standard
      Resets this to an initial value. If the type T has a no-argument constructor, then this satisfies the contract of the no-argument constructor for T. If T does not have a no-argument constructor, then this satisfies the contract of the constructor call that was used to initialize #this.

    • transferFrom

      public final void transferFrom(SortingMachine<T> source)
      Description copied from interface: Standard
      Sets this to the incoming value of source, and resets source to an initial value; the declaration notwithstanding, the dynamic type of source must be the same as the dynamic type of this. If the type T has a no-argument constructor, then source satisfies the contract of the no-argument constructor for T. If T does not have a no-argument constructor, then source satisfies the contract of the constructor call that was used to initialize #source.
      Parameters:
      source - object whose value is to be transferred

    • add

      public final void add(T x)
      Description copied from interface: SortingMachineKernel
      Adds x to the contents of this.
      Parameters:
      x - the element to be added

    • changeToExtractionMode

      public final void changeToExtractionMode()
      Description copied from interface: SortingMachineKernel
      Changes the mode of this from insertion to extraction.

    • removeFirst

      public final T removeFirst()
      Description copied from interface: SortingMachineKernel
      Removes and returns some "first" ("smallest") entry from the contents of this.
      Returns:
      the entry removed

    • isInInsertionMode

      public final boolean isInInsertionMode()
      Description copied from interface: SortingMachineKernel
      Reports whether this is in insertion mode.
      Returns:
      true iff this is in insertion mode

    • order

      public final Comparator<T> order()
      Description copied from interface: SortingMachineKernel
      Reports Comparator being used for sorting by this.
      Returns:
      Comparator used for sorting

    • size

      public final int size()
      Description copied from interface: SortingMachineKernel
      Reports the number of entries in this.
      Returns:
      the (multiset) size of this.contents

    • iterator

      public final Iterator<T> iterator()