CSE 2231 Midterm 2 Review

• The SortingMachine component family allows you to add elements of type T to a collection of such elements, and then to remove them one at a time in sorted order according to a client-supplied ordering
  • Queue and Stack support removal in FIFO and LIFO order, respectively

• add(T x) Adds x to the contents of this.
  • Parameters: x: the element to be added
  • Updates: this.contents
  • Requires: this.insertion_mode
  • Ensures: this.contents = #this.contents union {x}
• changeToExtractionMode() Changes the mode of this from insertion to extraction.
  • Updates: this.insertion_mode
  • Requires: this.insertion_mode
  • Ensures: not this.insertion_mode
• T removeFirst() Removes and returns some "first" ("smallest") entry from the contents of this.
  • Returns: the entry removed
  • Updates: this.contents
  • Requires: not this.insertion_mode and this.contents /= {}
  • Ensures: removeFirst is in #this.contents and for all x: T where (x is in #this.contents) (this.ordering(removeFirst, x)) and this.contents = #this.contents \ {removeFirst}
• boolean isInInsertionMode() Reports whether this is in insertion mode.
  • Returns: true iff this is in insertion mode
  • Ensures: isInInsertionMode = this.insertion_mode
• Comparator order() Reports Comparator being used for sorting by this.
  • Returns: Comparator used for sorting
  • Ensures: order = [Comparator used in the constructor call that created this]
• int size() Reports the number of entries in this.
  • Returns: the (multiset) size of this.contents
  • Ensures: size = |this.contents|

• A heap is a binary tree of T that satisfies two properties:
  • Global shape property: it is a complete binary tree
  • Local ordering property: the label in each node is "smaller than or equal to" the label in each of its child nodes
• In a complete binary tree, all levels are full except possibly the last.
• All labels in a heap are not necessarily unique.

• A heap can be used to represent the values in a SortingMachine, as follows:
  • In changeToExtractionMode, arrange all the values into a heap
  • In removeFirst, remove the root, and adjust the slightly mutilated heap to make it a heap again

• If the root is the only node in the heap, then after removing it, what remains is already a heap; nothing left to do
• Otherwise, the root is removed and replaced with the last node on the bottom level, and the new root is sifted down into place, being swapped with its smaller child.

    	
    	if (array.length > 1) {
            // Set the index of left and right in relation to the root.
            int leftIndex = 2 * top + 1;
            int rightIndex = 2 * top + 2;
            // I declared root for simplicity
            T root = array[top];
            // Make sure the right node actually exists.
            if (rightIndex <= last) {
                // Set smallerIndex to index of whichever child is smallest.
                int smallerIndex = leftIndex;
                int largerIndex = rightIndex;
                if (order.compare(array[leftIndex], array[rightIndex]) > 0) {
                    smallerIndex = rightIndex;
                    largerIndex = leftIndex;
                }
                // Move smaller node up if it is smaller than root.
                if (order.compare(root, array[smallerIndex]) > 0) {
                    exchangeEntries(array, top, smallerIndex);
                }
                // SiftDown the left and right nodes.
                siftDown(array, leftIndex, last, order);
                siftDown(array, rightIndex, last, order);
            }
            //We might still need to sift if right node doesn't exist.
            else if (leftIndex <= last) {
                T leftHeap = array[leftIndex];
                // Swap leftHeap with root if root is greater.
                if (order.compare(root, leftHeap) > 0) {
                    exchangeEntries(array, top, leftIndex);
                }
            }
        }
    	

    		Notes: 
    		rightIndex = 2 * top + 1
    		leftIndex = 2 * top + 2
    		
    		Check the root of the smaller child and swap that with the parent root.
    			Then recursively siftDown children. 
    	
    	
    	
    	

• In our singly-linked list examples, each node had two properties: Their data and next node.
• We use a SMART NODE at the beginning which has the following benefits:
  • Marginally increased speed of operations
  • Increased data structure robustness (no null pointer for end case)

• Unlike a singly-linked list, a doubly-linked list can sequentially access in both the forward AND backward directions.
  • This is done by having another property of each node.
  • Each node also has a PREVIOUS NODE element.

• Returns a new object with the same DYNAMIC type as this, having an initial value. If the type TF has a no-argument constructor, then the value of the new returned object satisfies its contract. Otherwise, the value of the new returned object satisfies the contract of the constructor call that was used to initialize this.
  • TF stands for the type family.
  • newInstance() must return whatever type family you are implementing.
• Ensures: is_initial(newInstance)

• Calls this.createNewRep()
  • createNewRep() initializes instance variables.

• Copies instance variable values from this and restores this.

• Iterator allows a special way for sequential access.
• An interface that extends iterator can be iterated over with a FOR-EACH loop.
• The Basics:
  • Iterator has 'hasNext()' returns an appropriate boolean.
  • The 'next()' method returns the next element.

• The mathematical model of a tree consists of a root node and a string of the subtrees.

• Size: total number of nodes |t|
• Height: number of nodes on the longest path from root to leaf ht(t)
• Labels: the set whose elements are the labels of t (no duplicates or ordering) labels(t)

• Tokenizer
  • Separate into tokens (Strings without separators).
• Parser
  • Make a Program object from tokens.
• Code Generator
  • Make code of ints that can be run.

• real-const has four representations.
• The first representation has digit-seq . digit-seq.
  • the spaces separate pieces
  • This representation means a digit-seq + '.' + digit-seq.