001package components.sortingmachine;
002
003import java.util.Comparator;
004import java.util.Iterator;
005import java.util.NoSuchElementException;
006
007import components.queue.Queue;
008import components.queue.Queue1L;
009
010/**
011 * {@code SortingMachine} represented as a {@link Queue} and an array (using an
012 * embedding of heap sort), with implementations of primary methods. The
013 * representation invariant is designed to have the implementation release
014 * references returned by removeFirst.
015 *
016 * @param <T>
017 *            type of {@code SortingMachine} entries
018 * @mathdefinitions {@code
019 * IS_TOTAL_PREORDER (
020 *   r: binary relation on T
021 *  ) : boolean is
022 *  for all x, y, z: T
023 *   ((r(x, y) or r(y, x))  and
024 *    (if (r(x, y) and r(y, z)) then r(x, z)))
025 *
026 * SUBTREE_IS_HEAP (
027 *   a: string of T,
028 *   start: integer,
029 *   stop: integer,
030 *   r: binary relation on T
031 *  ) : boolean is
032 *  [the subtree of a (when a is interpreted as a complete binary tree) rooted
033 *   at index start and only through entry stop of a satisfies the heap
034 *   ordering property according to the relation r]
035 *
036 * SUBTREE_ARRAY_ENTRIES (
037 *   a: string of T,
038 *   start: integer,
039 *   stop: integer
040 *  ) : finite multiset of T is
041 *  [the multiset of entries in a that belong to the subtree of a
042 *   (when a is interpreted as a complete binary tree) rooted at
043 *   index start and only through entry stop]
044 * }
045 * @convention {@code
046 * IS_TOTAL_PREORDER([relation computed by $this.machineOrder.compare method])  and
047 * if $this.insertionMode then
048 *   $this.heapSize = 0
049 * else
050 *   $this.entries = <>  and
051 *   for all i: integer
052 *       where (0 <= i  and  i < $this.heapSize)
053 *     ([entry at position i in $this.heap is not null])  and
054 *   for all i: integer
055 *       where ($this.heapSize <= i  and  i < |$this.heap|)
056 *     ([entry at position i in $this.heap is null])  and
057 *   SUBTREE_IS_HEAP($this.heap, 0, $this.heapSize - 1,
058 *     [relation computed by $this.machineOrder.compare method])  and
059 *   0 <= $this.heapSize <= |$this.heap|
060 * }
061 * @correspondence <pre>
062 * if $this.insertionMode then
063 *   this = (true, $this.machineOrder, multiset_entries($this.entries))
064 * else
065 *   this = (false, $this.machineOrder,
066 *     multiset_entries($this.heap[0, $this.heapSize)))
067 * </pre>
068 */
069public class SortingMachine5<T> extends SortingMachineSecondary<T> {
070
071    /*
072     * 2221/2231 assignment code deleted.
073     */
074
075}