Merge pull request #70 from aphitorite/614

MusicTheorist · web-flow · commit 3631533153df · 2020-06-20T00:00:21.000-04:00
Refactor Tree Sort
diff --git a/src/sorts/TreeSort.java b/src/sorts/TreeSort.java
@@ -6,13 +6,12 @@
 import utils.Reads;
 import utils.Writes;
 
-//TODO: Code's an absolute mess. Refactor it at some point.
 final public class TreeSort extends Sort {
     public TreeSort(Delays delayOps, Highlights markOps, Reads readOps, Writes writeOps) {
         super(delayOps, markOps, readOps, writeOps);
         
         this.setSortPromptID("Tree");
-        this.setRunAllID("Tree Sort");
+        this.setRunAllID("Tree Sort (Unbalanced)");
         this.setReportSortID("Treesort");
         this.setCategory("Insertion Sorts");
         this.isComparisonBased(true);
@@ -24,122 +23,73 @@ public TreeSort(Delays delayOps, Highlights markOps, Reads readOps, Writes write
     }
     
     // Code retrieved from https://www.geeksforgeeks.org/tree-sort/
-    
-    // Java program to  
-    // implement Tree Sort 
-    final class TreeSorter  
-    { 
-
-        // Class containing left and 
-        // right child of current  
-        // node and key value 
-        final class Node  
-        { 
-            int key; 
-            Node left, right; 
-
-            public Node(int item)  
-            { 
-                key = item; 
-                left = right = null; 
-            } 
-        } 
-
-        // Root of BST 
-        Node root; 
-
-        //Index for final result
-        int index;
-        
-        //Field to store current length
-        int length;
-        
-        // Constructor 
-        TreeSorter()  
-        {  
-            root = null;  
-        } 
+	
+	final private class Node { 
+		int key; 
+		Node left, right; 
 
-        //Method has to be inside TreeSort to access Node class directly
-        public Node treeWrite(Node element, int at) {
-            Node node = new Node(0);
-            
-            if(at < length) Highlights.markArray(1, at - 1);
-            
-            Writes.changeTempWrites(1);
-            
-            Writes.startLap();
-            
-            node = element;
-            
-            Writes.stopLap();
-            
-            Delays.sleep(0.25);
-            
-            return node;
-        }
-        
-        // This method mainly 
-        // calls insertRec() 
-        void insert(int key) 
-        { 
-            this.root = treeWrite(insertRec(root, key, 1), 1);
-        } 
+		public Node(int item) { 
+			key = item; 
+			left = right = null; 
+		} 
+	} 
+	
+	private Node root; 
+	private int index, length;
 
-        /* A recursive function to  
-     insert a new key in BST */
-        Node insertRec(Node root, int key, int depth)  
-        { 
+	private Node treeWrite(Node element, int at) {
+		Node node = new Node(0);
+		
+		if(at > 0 && at < this.length) Highlights.markArray(1, at - 1);
+		Writes.changeTempWrites(1);
+		Writes.startLap();
+		node = element;
+		Writes.stopLap();
+		
+		Delays.sleep(0.25);
+		
+		return node;
+	}
 
-            /* If the tree is empty, 
-         return a new node */
-            if (root == null)  
-            { 
-                root = treeWrite(new Node(key), 1);
-                return root; 
-            } 
+	private void insert(int key) {
+		this.root = this.treeWrite(insertRec(this.root, key, 1), 1);
+	} 
+	
+	private Node insertRec(Node root, int key, int depth) { 
+		if (root == null) { 
+			root = treeWrite(new Node(key), 1);
+			return root; 
+		} 
 
-            /* Otherwise, recur 
-         down the tree */
-            if (Reads.compare(key, root.key) == -1) 
-                root.left = treeWrite(insertRec(root.left, key, depth * 2), depth * 2); 
-            else if (Reads.compare(key, root.key) == 1) 
-                root.right = treeWrite(insertRec(root.right, key, (depth * 2) + 1), (depth * 2) + 1); 
+		if (Reads.compare(key, root.key) == -1) 
+			root.left  = treeWrite(insertRec(root.left, key, depth * 2), depth * 2); 
+		else if (Reads.compare(key, root.key) == 1) 
+			root.right = treeWrite(insertRec(root.right, key, (depth * 2) + 1), (depth * 2) + 1); 
 
-            /* return the root */
-            return root; 
-        } 
+		return root; 
+	} 
 
-        // A function to do  
-        // inorder traversal of BST 
-        void inorderRec(Node root, int[] array)  
-        { 
-            if (root != null)  
-            { 
-                inorderRec(root.left, array); 
-                Writes.write(array, this.index++, root.key, 1, true, false); 
-                inorderRec(root.right, array); 
-            } 
-        } 
+	private void traverseRec(Node root, int[] array) { 
+		if (root != null) { 
+			this.traverseRec(root.left, array); 
+			Writes.write(array, this.index++, root.key, 1, true, false); 
+			this.traverseRec(root.right, array); 
+		} 
+	} 
 
-        void treeins(int arr[], int length) 
-        { 
-            for(int i = 0; i < length; i++) 
-            {
-                Highlights.markArray(2, i);
-                insert(arr[i]); 
-            } 
-            Highlights.clearMark(2);
-        } 
-
-    }
+	private void treeIns(int arr[]) {
+		for(int i = 0; i < this.length; i++) {
+			Highlights.markArray(2, i);
+			this.insert(arr[i]);
+		} 
+		Highlights.clearMark(2);
+	}
 
     @Override
     public void runSort(int[] array, int currentLength, int bucketCount) {
-        TreeSorter tree = new TreeSorter();
-        tree.length = currentLength;
-        tree.treeins(array, tree.length); 
-        tree.index = 0;
-        tree.inorderRec(tree.root, array); 
+        this.length = currentLength;
+        this.treeIns(array); 
+        this.index = 0;
+        this.traverseRec(this.root, array); 
     }
 }
