CSC300 / CSC402: Example [1/6] Previous pageContentsNext page

Suppose I have a sorted linked list of doubles.

Let's write an insert method.

file:PlaygroundInsert.java [source]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package algs13;
import java.text.DecimalFormat;
import stdlib.*;
public class PlaygroundInsert {
  private Node first;
  static class Node { 
    public double item; 
    public Node next; 
    public Node (double item, Node next) { this.item = item; this.next = next; }
  }
  public void insert (double item) {  
    // TODO
  }

  public static void main (String[] args) {
    //Trace.showObjectIdsRedundantly(true);
    Trace.showBuiltInObjects(true);
    Trace.drawStepsOfMethod ("insert");
    Trace.drawStepsOfMethod ("insertH");
    Trace.run ();
    testInsert ("[ 11 21 31 41 51 ]", "11 21 41 51", 31);
    //PlaygroundInsert list = of ("11 21 41 51"); 
    //list.insert(31);
    Trace.draw ();
    StdOut.println ("Finished tests");
  }
  
  public static void main1 (String[] args) {
    testInsert ("[ 11 21 31 41 51 ]", "11 21 41 51", 31);
    testInsert ("[ 11 21 31 41 51 ]", "11 31 41 51", 21);
    testInsert ("[ 11 21 31 41 51 ]", "11 21 31 51", 41);
    testInsert ("[ 11 21 31 41 51 ]", "11 21 31 41", 51);
    testInsert ("[ 11 ]", "", 11);
    testInsert ("[ 11 21 31 41 51 ]", "21 31 41 51", 11);
    StdOut.println ("Finished tests");
  }
  
  /* ToString method to print */
  public String toString () { 
    // Use DecimalFormat #.### rather than String.format 0.3f to leave off trailing zeroes
    DecimalFormat format = new DecimalFormat ("#.###");
    StringBuilder result = new StringBuilder ("[ ");
    for (Node x = first; x != null; x = x.next) {
      result.append (format.format (x.item));
      result.append (" ");
    }
    result.append ("]");
    return result.toString ();
  }

  /* Method to create lists */
  public static PlaygroundInsert from(String s) {
    PlaygroundInsert result = new PlaygroundInsert ();
    if ("".equals (s)) return result;
    
    Node first = null;
    String[] nums = s.split (" ");
    for (int i = nums.length-1; i >= 0; i--) {
      try { 
        double num = Double.parseDouble (nums[i]); 
        first = new Node (num, first);      
      } catch (NumberFormatException e) {
        throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i]));
      }
    }
    result.first = first;
    return result;
  }

  private static void testInsert (String expected, String list, double item) {
    PlaygroundInsert aList = PlaygroundInsert.from (list); 
    aList.insert (item);
    String actual = aList.toString ();
    if (! expected.equals (actual)) {
      StdOut.format ("Failed [%s].insert(%f): Expecting (%s) Actual (%s)\n", list, item, expected, actual);
    }
  }
}

Previous pageContentsNext page