More Java fun... v.Immakillmyself

Discussion in 'OT Technology' started by Macbeth, Mar 17, 2010.

  1. Macbeth

    Macbeth That's illogical... OT Supporter

    Joined:
    Mar 1, 2005
    Messages:
    18,408
    Likes Received:
    0
    Location:
    Under your bed.
    So currently I'm working on a project where I make a generic doubly linked linked list with a dummy node (it's also cyclic). The driver is set up to test for errors in the code I have to write, and right now the problem is that the driver is attempting to iterate to the next node at the end of the iterators list, and because of that it is throwing the exception I have for when that happens. As far as I know, this shouldn't occur, and it should continue to run normally.

    I figured at first it was a problem with removing nodes using the iterator, so I attempted to fix that, and it still happens. I'm shit out of ideas for how to go about this, so any help at all would be appreciated. Just remember this is only a second year course (maybe even first year if you passed the appropriate tests, which I didn't), so a lot of the concepts are still pretty "basic".

    Driver code:
    Code:
    import java.util.Collection;
    import java.util.Iterator;
    import java.util.NoSuchElementException;
    
    import edu.uwm.cs351.DoublyLinkedList;
    
    
    public class Driver {
    
        private static int passed;
        private static int failed;
        
        /**
         * @param args
         */
        public static void main(String[] args) {
            try {
              testList();
              
            } catch (Exception e) {
                ++failed;
                e.printStackTrace();
            }
            System.out.println("Passed " + passed + " tests.");
            System.out.println("Failed " + failed + " test" + (failed == 1? "." : "s."));
        }
    
        private static void testList()
        {
            Collection<String> l = new DoublyLinkedList<String>();
            String p1 = "Apple";
            String p2 = "Bread";
            String p3 = "Cheese";
    
            test(l,"empty");
    
            try {
                l.iterator().next();
                test(false,"empty list iterator has next");
            } catch (NoSuchElementException e) {
                test(true,"");
            } catch (RuntimeException e) {
                test(false,"wrong exception: " + e);
            }
    
            l.add(p1);
            test(l.iterator().next(),p1,"{p1}.first");
            test(l,"{p1}",p1);
    
            Iterator<String> it = l.iterator();
            it.next(); // result discarded
    
            try {
                it.next();
                test(false,"advanced too far");
            } catch (NoSuchElementException e) {
                test(true,"");
            } catch (RuntimeException e) {
                test(false,"wrong exception: " + e);
            }
    
            it = l.iterator();
            test(it.next(),p1,"again {p1}.first");
    
            it.remove();
            test(l,"again empty");
    
          l.add(p2);
          test(l.iterator().next(),p2,"{p2}.first");
          test(l,"{p2}",p2);
          
          l.clear();
          test(l,"cleared");
          
          l.add(p1);
          l.add(p2);
          it = l.iterator();
          test(it.next(),p1,"{p1,p2}.first");
          test(l,"{p1,p2}",p1,p2);
    
          test(it.next(),p2,"{p1,p2}.second");
    
          test(!it.hasNext(),"{p1,p2} should have nothing at end");
          l.add(p3);
          test(l,"{p1,p2,p3}",p1,p2,p3);
          
          it = l.iterator();
          it.next(); // ignored
          test(it.next(),p2,"{p1,p2,p3}.second");
          
          it.remove();
          test(l,"after removing middle",p1,p3);
          
          l.add(p2);
          test(l,"re-adding p2",p1,p3,p2);
          
          it = l.iterator();
          it.next();
          it.next();
          it.next();
          it.remove();
          test(l,"after removing p2 again",p1,p3);
          test(!it.hasNext(),"should not have remaining element after remove()");
          
          it = l.iterator();
          try {
              it.remove();
              test(false,"remove() called before next()");
          } catch (IllegalStateException e) {
              test(true,"");
          } catch (RuntimeException e) {
              test(false,"wrong exception " + e);
          }
          
          it = l.iterator();
          it.next();
          it.remove();
          
          test(l,"after removing first",p3);
          test(it.hasNext(),"should have remaining element after remove()");
          try {
              it.remove();
              test(false,"remove() called after already removed");
          } catch (IllegalStateException e) {
              test(true,"");
          } catch (RuntimeException e) {
              test(false,"wrong exception " + e);
          }
      
          it = l.iterator();
          it.next();
          it.remove();
          test(!it.hasNext(),"should not have remaining element after remove()");
          test(l,"last element removed");
        }
        
        private static void test(Collection<String> l, String name, String... parts)
        {
            test(l.size(),parts.length,name + ".size()");
            Iterator<String> it = l.iterator();
            int i=0;
            while (it.hasNext() && i < parts.length) {
                test(it.next(),parts[i],name + "[" + i + "]");
                ++i;
            }
            test(!it.hasNext(),name + " too long");
            test(!(i < parts.length),name + " too short");
        }
    
        private static void test(String x, String expected, String name) {
            if (x.equals(expected)) ++passed;
            else {
                ++failed;
                System.out.println("\n!!! Failed test: " + name + ".  Expected \"" + expected + "\", but got \"" + x + "\"\n");
            }
        }
    
        private static void test(int x, int expected, String name) {
            if (x == expected) ++passed;
            else {
                ++failed;
                System.out.println("\n!!! Failed test: " + name + ".  Expected " + expected + ", but got " + x + "\n");
            }
        }
        private static void test(boolean b, String problem) {
            if (b) {
                ++passed;
            } else {
                ++failed;
                System.out.println("\n!!! Failed test: " + problem);
            }
        }
    }
    
    My Code
    Code:
    package edu.uwm.cs351;
    
    import java.util.AbstractCollection;
    import java.util.Collection;
    import java.util.Iterator;
    import java.util.NoSuchElementException;
    
    /**
     * A doubly-linked list implementation of the Java Collection interface
     * We use [email protected] java.util.AbstractCollection} to implement most methods.
     * You should override [email protected] #clear()} for efficiency, and [email protected] #add(Object)}
     * for functionality.  You will also be required to override the abstract methods
     * [email protected] #size()} and [email protected] #iterator()}.  All these methods should be declared
     * "@Override".
     * <p>
     * The data structure is a doubly-linked list with one dummy node.
     * It should be cyclicly linked without any null pointers.
     * The code should have very few special cases.
     * The class should define a private [email protected] #_wellFormed()} method
     * and perform assertion checks in each method.
     * It is not necessary that you implement <i>fail-fast</i> semantics
     * for the iterator.
     * @param <T>
     */
    public class DoublyLinkedList<T> extends AbstractCollection<T> implements Collection<T> {
    
        // Declare private static Node data class
        // Declare data members and invariant
        // Declare methods to implement interface
        private boolean report(String error) {
            System.out.println("Invariant error found: " + error);
            return false;
        }
    
        private boolean _wellFormed() {
            /* *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  * *
             * The data structure is a doubly-linked list with one dummy node.
             * It should be cyclicly linked without any null pointers.
             * The code should have very few special cases.
             * The class should define a private [email protected] #_wellFormed()} method
             * and perform assertion checks in each method.
             * It is not necessary that you implement <i>fail-fast</i> semantics
             * for the iterator.
             * *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  */
            for (Node<T> p = dummy.next; p != dummy; p = p.next) {
                if (p == null) {
                    return report("Null found in list");
                }
            }
    
            Node<T> fast = dummy;
            for (Node<T> p = dummy.prev; fast != dummy.prev && fast != null && 
            fast.next != dummy.prev && fast.next != null; p = p.next) {
                if (p == fast) return report("list is cyclic in the wrong way");
                fast = fast.next.next;
            }
            return true;
        }
    
        private static class Node<T> {
            private T data;
            private Node<T> next;
            private Node<T> prev;
    
            public Node(T element, Node<T> p, Node<T> n) {
                data = element;
                next = n;
                prev = p;
            }
    
        } // end of Node class
    
        Node<T> dummy = new Node<T>(null, null, null);
        private Node<T> cursor;
    
        public DoublyLinkedList() {
            cursor = dummy;
            dummy.next = dummy;
            dummy.prev = dummy;
            assert _wellFormed();
        }
    
        @Override
        public void clear() {
            assert _wellFormed();
    
            dummy.next = dummy;
            dummy.prev = dummy;
            cursor = dummy;
    
    
            assert _wellFormed();
        }
    
        @Override
        public boolean add(T element) {
            assert _wellFormed();
    
            cursor.next = new Node<T>(element, cursor, dummy);
            cursor = cursor.next;
            dummy.prev = cursor;
    
            // assert _wellFormed();
            return true;
        }
    
        // You need a nested (not static) class to implement the iterator:
        private class MyIterator implements Iterator<T> {
    
            Node<T> cur = dummy;
            boolean removed = false;
            
            @Override
            public boolean hasNext() {
                return cur.next != dummy;
            }
    
            @Override
            public T next() {
                if (!hasNext())
                    throw new NoSuchElementException("...");
                else {
                    removed = true;
                    Node<T> temp = cur.next;
                    cur = cur.next;
                    return temp.data;
                }
            }
    
            @Override
            public void remove() {
                if (removed) {
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
                cur = cur.prev;
                removed = false;
                }
                else throw new IllegalStateException();
                assert _wellFormed();
            }
            // Declare fields and methods.
            // No need to give invariant.
            // Optional: check for concurrent modification exception
        }
    
    
        @Override
        public Iterator<T> iterator() {
            return new MyIterator();
        }
    
    
        @Override
        public int size() {
            int size = 0;
            for (Node<T> p = dummy.next; p != dummy; p = p.next) {
                size++;
            }
            return size;
        }
    }
    
     
  2. CodeX

    CodeX Guest

    God what a mess, java makes me cry...

    anyway since no one has responded yet I'll look at it sometime today or tomorrow.
     
    Last edited by a moderator: Mar 18, 2010
  3. SIGirl

    SIGirl Super Duper Moderator Super Moderator

    Joined:
    Nov 1, 2001
    Messages:
    22,677
    Likes Received:
    1,371
    Location:
    Austin, TX
    :werd: There's so much going on. Just put breakpoints in and debug. At least you'll see where the issue starts and hopefully be able to figure out why. I'll look at it if I have more time this weekend.
     
    Narc likes this.

Share This Page