Program Help v.Link Lists

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

  1. Macbeth

    Macbeth That's illogical... OT Supporter

    Joined:
    Mar 1, 2005
    Messages:
    18,408
    Likes Received:
    0
    Location:
    Under your bed.
    Essentially I'm having some difficulties attempting to do my assignment. Right now, from the output of the program (the driver includes a debugging code) I don't seem to be getting the correct results.

    Essentially its a card game program, and right now I'm just trying to add cards to a hand (group) using a link list. Unfortunately, the output keeps saying stuff like:

    Code:
    !! Before DEUCE of CLUBS we have null when it should be ACE of SPADES
    IJKL
    !! Before DEUCE of CLUBS we have null when it should be ACE of SPADES
    
    !! Before SIX of HEARTS we have null when it should be DEUCE of CLUBS
    I have no idea why it is getting a null before a new card is added. I still can't see any problems, then again its taken me this long to grasp the whole blah.next.prev.fuckthisshit etc. Code for checking (bold & italic is the code I am doing for the assignment):

    Code:
    package edu.uwm.cs351;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.List;
    
    /**
     * Traditional playing cards.
     * @author boyland
     */
    public class Card {
        public enum Suit { CLUB, DIAMOND, HEART, SPADE };
        public enum Rank {
            ACE(1), DEUCE(2), THREE(3), FOUR(4), FIVE(5), SIX(6), SEVEN(7), EIGHT(8), NINE(9), TEN(10),
            JACK(11), QUEEN(12), KING(13);
    
            private final int rank;
            private Rank(int r) {
                rank = r;
            }
    
            public int asInt() {
                return rank;
            }
        }
    
        private final Suit suit;
        private final Rank rank;
        private Card prev, next;
        private Group group;
    
        public Card(Rank r, Suit s) {
            rank = r;
            suit = s;
        }
    
        // getters for all fields:
    
        public Suit getSuit() {
            return suit;
        }
    
        public Rank getRank() {
            return rank;
        }
    
        public Card getPrevious() {
            return prev;
        }
    
        public Card getNext() {
            return next;
        }
    
        public Group getGroup() {
            return group;
        }
    
        // no setters!
    
        @Override
        public String toString() {
            return rank + " of " + suit + "S";
        }
    
    
        public static class Group {
            private Card first, last;
            private int size;
    
            public Group() {
                first = last = null;
                size = 0;
            }
    
            public Card getFirst() { return first; }
            public Card getLast() { return last; }
    
            private boolean report(String s) {
                System.err.println("Invariant error: " + s);
                return false;
            }
         [B]  [I] private boolean _wellFormed() {
                // As before, we provide the code to check for cycles:
                if (first != null) {
                    // We do not permit cycles in the list.
                    Card cycle = first.next;
                    for (Card c = first; c != null; c = c.next) {
                        if (c == cycle) return report("cycle detected!");
                        if (cycle== null) break;
                        cycle = cycle.next;
                        if (cycle == null) break;
                        cycle = cycle.next;
                    }
                }
                // Then check the other aspects of the invariant:
                // TODO
                // Explain and implement the invariant
                return true;
            }
    
            /**
             * Return true if there are no cards,
             * that is, if and only if getFirst() == null
             */
            public boolean isEmpty() {
                if (getFirst() == null) return true;
                return false; // TODO
            }
    
            /**
             * Return the number of cards in this pile. O(1)
             */
            public int count() {
                return size; // TODO
            }
    
            /**
             * Add a card to the end of this pile/hand.
             [email protected] The card must not belong to any group before.
             [email protected] The card will belong this this pile/hand afterwards.
             * NO LOOPS!
             */
            public void add(Card c) {
                if (first == null) {
                    first = c;
                    last = c;
                    size++;
                }
                else if (first.next == null) {
                    first.next = c;
                    last = first.next;
                    size++;
                }
                else {
                    last.next = c;
                    last = last.next;
                    size++;
                }
            }
            /**
             * Remove the first card and return it.
             [email protected] !isEmpty()
             [email protected] returned card will not belong to any group afterwards.
             [email protected] IllegalStateException if group empty
             * NO LOOPS!
             */
            public Card draw() {
                Card drawCard = first;
                first = first.next;
                drawCard.group = null;
                size--;
                return drawCard;
                //else throw new IllegalStateException();
            }
    
            /**
             * Remove the given card from this group.
             [email protected] The card being removed must belong to this group.
             [email protected] The card will not below to any group afterwards.
             [email protected] IllegalArgumentException if the card does not belong 
             *to this group.
             * NO LOOPS!
             */
            public void remove(Card c) {
                if (c.group.first == first && c.group.last == last) {
                    c.prev.next = c.next;
                    c.next = null;
                    c.prev = null;
                }
                else throw new IllegalArgumentException();
            }
    
            /**
             * Sort the cards using the given comparison.
             * Sorting is done using insertion sort, starting at the beginning.
             * For each card (after the first), determine where to insert
             * it in the sorted cards to its left.  Insertion sort, if done correctly,
             * is one of the most efficient on already sorted lists.
             * Thus adding at the end and then sorting is efficient: O(n).
             [email protected] the same cards belong to this group afterwards.
             [email protected] no two adjacent cards are in the WRONG order, that is,
             * cmp.compare(c,c.next) is never positive.
             */
            public void sort(Comparator<Card> cmp) {
                // TODO
                // Make sure to test invariant before and after
                // You may find it helpful to use "remove" (but watch about size!)
            }[/I]     
    [/B]      
            /**
             * Randomize the order of the cards in this group.
             * This is very different from the [email protected] #sort(Comparator)} method
             * because <ol>
             * <li> we decant the cards into an array list;
             * <li> we use a library function to do the work;
             * </ol>
             * The implementation of [email protected] #sort(Comparator)} should
             * have neither of those characteristics.
             */
            public void shuffle() {
                List<Card> cards = new ArrayList<Card>();
                while (!isEmpty()) {
                    cards.add(draw());
                }
                Collections.shuffle(cards);
                for (Card c: cards) {
                    add(c);
                }
            }
        }
    
        /** Create and return a fresh pack of cards.
         * A "static" method is a class method.  It is invoked using
         * the class, not an instance.
         * @return a fresh pack of 52 cards
         */
        public static Group newDeck() {
            Group g = new Group();
            for (Suit s : Suit.values()) {
                for (Rank r : Rank.values()) {
                    Card c = new Card(r,s);
                    g.add(c);
                }
            }
            return g;
        }
    }
    
     
  2. ge0

    ge0 New Member

    Joined:
    Oct 31, 2005
    Messages:
    8,398
    Likes Received:
    0
    Location:
    JERSEY
    I didn't read through the entire code, but skimming through your comments, there are some functions that could be useful functions for the linkedlist container such as:

    .add(Object o); - adds something to the list, you can also pass an index here
    .addFirst(Object o); - adds it to the beginning of the list
    .addLast(Object o); - adds it to the end
    .removeFirst(Object o); - removes the first element and returns it
    .removeLast(Object o); - removes the last and returns it
    .contains(Object o); - returns a true or false if the object is in the list and where its at;

    //etc

    I would also use a Collections.sort(list)
     

Share This Page