001package algs13; 002 003import stdlib.StdOut; 004 005import java.text.DecimalFormat; 006 007public class MyListMutator { 008 private Node first; 009 static class Node { 010 public Node (double item, Node next) { this.item = item; this.next = next; } 011 public double item; 012 public Node next; 013 } 014 015 public void insert1(double item) { 016 Node x = first; 017 while(x.next != null && x.next.item < item) { 018 x = x.next; 019 } 020 x.next = new Node(item, x.next); 021 } 022 023 public void insert2(double item) { 024 if(first == null || first.item >= item) { 025 first = new Node(item, first); 026 return; 027 } 028 Node x = first; 029 if(x.next == null || x.next.item >= item) { 030 x.next = new Node(item, x.next); 031 } 032 } 033 034 public void insert3(double item) { 035 if(first == null || first.item >= item) { 036 new Node(item, first); 037 } 038 else { 039 Node x = first; 040 while(x.next != null && x.next.item <= item) { 041 x = x.next; 042 } 043 x.next = new Node(item, x.next); 044 } 045 } 046 047 public void insert4(double item) { 048 if(first == null || first.item >= item) { 049 first = new Node(item, first); 050 } 051 else { 052 Node x = first; 053 while(x.next != null && x.next.item < item) { 054 x = x.next; 055 } 056 new Node(item, x.next); 057 } 058 } 059 060 public void insert5(double item) { 061 Node x = first; 062 while(x != null && x.item < item) { 063 x = x.next; 064 } 065 if(x != null) { 066 x.next = new Node(item, x); 067 } 068 } 069 070 public void insert6(double item) { 071 Node x = first; 072 while(x != null && x.next.item < item) { 073 x = x.next; 074 } 075 if(x != null) { 076 new Node(item, x.next); 077 } 078 } 079 080 public void insert7(double item) { 081 Node x = first; 082 while(x != null && x.next.item <= item) { 083 x = x.next; 084 } 085 if(x != null) { 086 x.next = new Node(item, x.next); 087 } 088 } 089 090 public void insert(double item) { 091 insert1(item); 092 // insert2(item); 093 // insert3(item); 094 // insert4(item); 095 // insert5(item); 096 // insert6(item); 097 //insert7(item); 098 } 099 100 /* ToString method to print */ 101 public String toString () { 102 // Use DecimalFormat #.### rather than String.format 0.3f to leave off trailing zeroes 103 DecimalFormat format = new DecimalFormat ("#.###"); 104 StringBuilder result = new StringBuilder ("[ "); 105 for (Node x = first; x != null; x = x.next) { 106 result.append (format.format (x.item)); 107 result.append (" "); 108 } 109 result.append ("]"); 110 return result.toString (); 111 } 112 /* Method to create lists */ 113 public static MyListMutator from(String s) { 114 MyListMutator result = new MyListMutator(); 115 if ("".equals (s)) return result; 116 117 Node first = null; 118 String[] nums = s.split (" "); 119 for (int i = nums.length-1; i >= 0; i--) { 120 try { 121 double num = Double.parseDouble (nums[i]); 122 first = new Node (num, first); 123 } catch (NumberFormatException e) { 124 throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i])); 125 } 126 } 127 result.first = first; 128 return result; 129 } 130 131 private static void testInsert (String expected, String list, double item) { 132 MyListMutator aList = MyListMutator.from (list); 133 aList.insert (item); 134 String actual = aList.toString (); 135 if (! expected.equals (actual)) { 136 StdOut.format ("Failed [%s].insert(%f): Expecting (%s) Actual (%s)\n", list, item, expected, actual); 137 } 138 } 139 public static void main(String[] args) { 140 testInsert ("[ 11 21 31 41 51 ]", "11 21 41 51", 31); 141 testInsert ("[ 11 21 31 41 51 ]", "11 31 41 51", 21); 142 testInsert ("[ 11 21 31 41 51 ]", "11 21 31 51", 41); 143 testInsert ("[ 11 21 31 41 51 ]", "11 21 31 41", 51); 144 testInsert ("[ 11 ]", "", 11); 145 testInsert ("[ 11 21 31 41 51 ]", "21 31 41 51", 11); 146 StdOut.println ("Finished tests"); 147 } 148}