Question

JAVA:

* You may not add any fields to the node or list classes.
* You may not add any methods to the node class.
* Do not change any 'Utility' methods that I have included.
* You may NOT use any arrays or other Java classes

set * Change the value at the specified index * the location can be specified by a positive or negative number. * zero or positive value is interpreted as an offset from the left (first) * a negative value is interpreted as an offset from the right, with -1 meaning last index values outside the valid range should not change the list * The function returns true if the set was successful, false if the index is invalid * In the examples below the list is delimited by { } the value on the left would be 'first' the value on the right would be 'last' Examples: { 1 2 3 4 5 6 }.set(1, 9) --> { 1 9 3 4 5 6 } { 1 2 3 4 5 6 }.set(5, 9) { 1 2 3 4 5 9 } * { 1 2 3 4 5 6 }.set(8, 9) --> { 1 2 3 4 5 6 } * { 1 2 3 4 5 6 }.set(-1, 9) { 1 2 3 4 5 9 } { 1 2 3 4 5 6 }.set(-4, 9) { 1 2 9 4 5 6 } * { 1 2 3 4 5 6 }.set(-11, 9) --> { 1 2 3 4 5 6 } wowwww uuuuuu public boolean set(int index, double value) { return false; // ToDo 1 fix this

~ Testing purposes ~

public class DSIList {
   Node first,last;        // three instance variables
   int N;                   // maintain the size of the list

   static class Node { // Note the useful Node constructor
       public Node(double item, Node prev, Node next) { this.item = item; this.prev = prev; this.next = next; }
       public double item;
       public Node next;     // the next node       - to the right
       public Node prev;     // the previous node   - to the left
   }

   // constructors
   public DSIList () {   // an empty list
       first = last = null;
       N = 0;
   };    
   public DSIList (double item) { // a list with one item
       first = last = new Node(item,null,null);
       N = 1;
   };

   public boolean isEmpty () { return N == 0; }
   public int size ()        { return N; }

   public static void setTests() {
       DSIList d1;
       d1 = new DSIList ("9");                       // Initial list -> 99
       d1.set (0,3);                                // change list item 0 to 3
       check ("set #1", d1, "[ 3 ]");               // answer. list -> 3

       d1 = new DSIList ("2 3");                   // Initial list -> 2 3
       d1.set (1,9);                               // change list item 1 to 9
       check ("set #2", d1, "[ 2 9 ]");           // answer. list -> 2 9
      
       d1 = new DSIList ("0 1 2 3 4 5 6 7 8");                  
       d1.set (1,9);                              
       check ("set #3", d1, "[ 0 9 2 3 4 5 6 7 8 ]");          
      
       d1 = new DSIList ("0 1 2 3 4 5 6 7 8");                  
       d1.set (10,9);                              
       check ("set #4", d1, "[ 0 1 2 3 4 5 6 7 8 ]");
      
       d1 = new DSIList ("9");                  
       d1.set (-1,3);                              
       check ("set #5", d1, "[ 3 ]");  
      
       d1 = new DSIList ("2 3");                  
       d1.set (-2,9);                              
       check ("set #6", d1, "[ 9 3 ]");
      
       d1 = new DSIList ("0 1 2 3 4 5 6 7 8 ");                  
       d1.set (-4,9);                              
       check ("set #7", d1, "[ 0 1 2 3 4 9 6 7 8 ]");  
      
       d1 = new DSIList ("0 1 2 3 4 5 6 7 8 ");                  
       d1.set (-9,9);                              
       check ("set #8", d1, "[ 9 1 2 3 4 5 6 7 8 ]");
      
       d1 = new DSIList ("0 1 2 3 4 5 6 7 8 ");                  
       d1.set (-10,9);                              
       check ("set #8", d1, "[ 0 1 2 3 4 5 6 7 8 ]");
      
       StdOut.println ("Finished set tests");
   }

/************************************* Utility routines   *****************************************/
   public DSIList (String s) {

       String[] nums = s.split (" ");
       double fitem = Double.parseDouble (nums[nums.length-1]);
       DSIList t = new DSIList(fitem);
       first = t.first;
       last=t.last;
       N=1;
       for (int i = nums.length-2; i >= 0; i--) {
           try {
               insertBefore (Double.parseDouble (nums[i]),0);          
           } catch (NumberFormatException e) {   }
       }
   }

   public Node find( double item) {
       for ( Node tmp = first; tmp != null; tmp = tmp.next )
           if ( tmp.item == item)
               return tmp;
       return null;
   }
   public String toString () {
       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 ();
   }

   static void showError (String message) {
       Trace.draw ();
       StdOut.println (message);
       //throw new Error (); // stops execution
   }
   public static void checkInvariants (String message, DSIList that) {
       int N = that.N;
       DSIList.Node left = that.first;
       DSIList.Node right = that.last;

       if (N < 0) throw new Error ();
       if (N == 0) {
           if (left != null || right != null) {
               showError (String.format ("%s: Expected first,last == null.", message));
           }
       } else {
           if (left == null || right == null) {
               showError (String.format ("%s: Expected first,last != null.", message));
           }
       }
       if (N > 0) {
           DSIList.Node prev = null;
           DSIList.Node current = left;
           for (int i = 0; i < N; i++) {
               if (current == null) {
                   showError (String.format ("%s: Expected %d next nodes, but got less.", message, N));
               }
               if (current.prev != prev) {
                   showError (String.format ("%s: Broken prev link.", message));
               }
               prev = current;
               current = current.next;
           }
           if (current != null) {
               showError (String.format ("%s: Expected %d next nodes, but got more.", message, N));
           }
           DSIList.Node next = null;
           current = right;
           for (int i = 0; i < N; i++) {
               if (current == null) {
                   showError (String.format ("%s: Expected %d prev nodes, but got less.", message, N));
               }
               if (current.next != next) {
                   showError (String.format ("%s: Broken next link.", message));
               }
               next = current;
               current = current.prev;
           }
           if (current != null) {
               showError (String.format ("%s: Expected %d prev nodes, but got more.", message, N));
           }
       }
   }
   private static void check (String message, DSIList actual, String expected) {
       checkInvariants (message, actual);
       if (expected != null) {
           if (!expected.equals (actual.toString ())) {
               showError (message + " Expected \"" + expected + "\", got \"" + actual + "\"");
           }
       }
   }
   private static void check (String message, DSIList actual, String expected, double dActual, double dExpected) {
       if (dExpected != dActual) {
           showError (message + " Expected \"" + dExpected + "\", got \"" + dActual + "\"");
       }
       check (message, actual, expected);
   }

}

Answer 1

/**
   * Change the value at the specified index
   * the location can be specified by a positive or negative number
   * zero or positive value is interpreted as an offset from the left (first)
   * a negative value is interpreted as an offset from the right, with -1 meaning last
   * index values outside the valid range should not change the list
   * The function returns true if the set was successful, false if the index is invalid
   *
   *
   * @param index, int index of node to update
   * @param value, double value to be updated
   *
   */
   public boolean set(int index, double value)
   {
       // if index is zero or positive , offset is interpreted from the left
       if(index >= 0)
       {
           // if index is valid
           if(index >=0 && index < size())
           {
               int idx = 0; // start index = 0
               Node curr = first; // set curr to first node of list
               // loop to get the node whose value is to be updated starting from left
               while(idx < index)
               {
                   curr = curr.next;
                   idx++;
               }
                 
               curr.item = value; // set the item of curr to value
                 
               return true; // update successful
           }else
               return false; // update unsuccessful
       }
       else // if index is negative, offset is interpreted from the right
       {
           // if index is valid
           if((index >= -1*size()) && (index <= -1))
           {
               int idx = -1; // start index = -1
               Node curr = last; // set curr to last
               // loop to get the node whose value is to be updated starting from right
               while(idx > 1*index)
               {
                   curr = curr.prev;
                   idx--;
               }
                 
               curr.item = value; // update the curr item to value
               return true; // update successful
           }else
               return false; // update unsuccessful
       }
   }
//end of set method