import java.util.*;

/**
 * Card Deck data structure
 * 
 * Special-purpose doubly-linked list for manipulating a deck of cards.
 * Allows swapping single cards and ranges of cards in constant time.
 * Also keeps track of the jokers and their positions for special purposes.
 * 
 * Copyright (c) 2007 William R. Fraser
 * All rights reserved.
 *
 * @author William R. Fraser <wfraser@cs.uic.edu>
 * @version 2007.04.05
 */
public class CardDeck
{
    private Card   head;           // pointer to the first card
    private Card   tail;           // pointer to the last card
    private Card   firstJoker;     // pointer to the first joker
    private Card   secondJoker;    // pointer to the second joker
    private int    firstJokerPos;  // position of the first joker
    private int    secondJokerPos; // position of the  joker
	
    // useful constants
    public static final int DECKSIZE            = 28;
    public static final int FIRSTJOKER          = 27;
    public static final int SECONDJOKER         = 28;
	
    /**
     * Construct the deck of cards from a string of DECKSIZE integers separated
     * by at least one space.
     * 
     * @param s
     */
    public CardDeck(String s)
    {
        Scanner scan = new Scanner(s);
        scan.useDelimiter("[ ]+");
        
        head = null;
        tail = null;
		
        for (int i = 0; i < DECKSIZE; i++) {
            if (!scan.hasNextInt())
                throw new IllegalArgumentException("There must be " + DECKSIZE
                        + " cards.");
			
            int value = scan.nextInt();
            
            if (value < 1 || value > DECKSIZE)
                throw new IllegalArgumentException("Card with value " + i
                        + " is out of range.");
			
            Card c = new Card(value, tail, null);
            
            if (i != 0) {
                tail.setNext(c);
            } else {
                head = c;
            }
                
            tail = c;
            			
            switch (value) {
            case FIRSTJOKER:
                firstJoker = tail;
                firstJokerPos = i;
                break;
            case SECONDJOKER:
                secondJoker = tail;
                secondJokerPos = i;
                break;
            }
        }
    }

    /**
     * Construct the deck of cards from an array of integers in the range 0 to
     * DECKSIZE.
     * 
     * @param ints
     */
    public CardDeck(int[] ints)
    {
        if (ints.length != DECKSIZE)
            throw new IllegalArgumentException("There must be " + DECKSIZE
                    + " cards.");
		
        head = null;
        tail = null;
        
        for (int i = 0; i < DECKSIZE; i++) {
            if (i < 1 || i > DECKSIZE)
                throw new IllegalArgumentException("Card " + i
                        + " is out of range.");
            
            Card c = new Card(ints[i], tail, null);
            
            if (i != 0) {
                tail.setNext(c);
            } else {
                head = c;
            }
            
            tail = c;
            			
            switch (ints[i]) {
            case FIRSTJOKER:
                firstJoker = tail;
                firstJokerPos = i;
                break;
            case SECONDJOKER:
                secondJoker = tail;
                secondJokerPos = i;
                break;
            }
        }
    }
    
    /**
     * Convert the deck into an array of integers in the range 0 to DECKSIZE.
     * The integers represent the card values.
     * 
     * @return
     */
    public int[] toArray()
    {
        int[] retval = new int[DECKSIZE];
        Card c = head;
        for (int i = 0; i < DECKSIZE; i++) {
            retval[i] = c.getDatum();
            c = c.getNext();
        }
        return retval;
    }
    
    /**
     * Make a string of the form "[1, 2, 3, 4, ..., 28]" representing the deck.
     */
    public String toString()
    {
        Formatter f = new Formatter();
        int[] arr = toArray();
        
        f.format("[");
        for (int i = 0; i < DECKSIZE - 1; i++) {
            f.format("%d, ", arr[i]);
        }
        f.format("%d]", arr[DECKSIZE - 1]);
        
        return f.toString();
    }
	
    /**
     * Perform a Count Cut. That is, take the range of cards starting from the
     * head up to the card at the position of the value of the bottom card,
     * and move it to just above the bottom card.
     * 
     * Runs in O(n) time.
     */
    public void countCut()
    {		
        if (tail == firstJoker || tail == secondJoker)
            return; // do nothing
		
        int endPos = tail.getDatum() - 1;
        Card end = getCardAt(endPos);		// O(n) time
		
        /*
         * find whether there are jokers in this range
         */
		
        boolean firstJokerInRange;
        boolean secondJokerInRange;
        firstJokerInRange = secondJokerInRange = false;
        
        Card c = head;
        while (c != end.getNext()) {		// O(n) time
            if (c.getDatum() == FIRSTJOKER) {
                firstJokerPos += DECKSIZE - endPos - 2;
                firstJokerInRange = true;
            } else if (c.getDatum() == SECONDJOKER) {
                secondJokerPos += DECKSIZE - endPos - 2;
                secondJokerInRange = true;
            }
            c = c.getNext();
        }
		
        Card next = end.getNext();
		
        head.setPrev(tail.getPrev());
        tail.getPrev().setNext(head);
        end.setNext(tail);
        tail.setPrev(end);
        next.setPrev(null);
        head = next;
        
        if (!firstJokerInRange)
            firstJokerPos -= endPos + 1;
        if (!secondJokerInRange)
            secondJokerPos -= endPos + 1;
    }
	
    /**
     * Swap the 27 joker with the card after it, or the head if it is already
     * the last card in the deck.
     * 
     * Runs in O(1) time.
     */
    public void firstJokerSwapNext()
    {
        if (firstJoker == tail) {
            Card prev = firstJoker.getPrev();
            prev.setNext(null);
            tail = prev;
            head.setPrev(firstJoker);
            firstJoker.setNext(head);
            firstJoker.setPrev(null);
            head = firstJoker;
            firstJokerPos = 0;
            secondJokerPos++; // everything gets shifted down by one
        } else {
            Card prev = firstJoker.getPrev();
            Card next = firstJoker.getNext();
            
            if (next == secondJoker) {
                secondJokerPos--;
            }
            
            if (firstJoker != head) {
                prev.setNext(next);
            } else {
                head = next;
            }
            
            next.setPrev(prev);
            
            firstJoker.setNext(next.getNext());
            if (next != tail) {
                next.getNext().setPrev(firstJoker);
            } else {
                tail = firstJoker;
            }

            next.setNext(firstJoker);
            firstJoker.setPrev(next);
            firstJokerPos++;
        }
    }
    
    /**
     * Move the 28 joker down in the deck twice.
     * 
     * Runs in O(1) time.
     */
    public void secondJokerSwapNextTwice()
    {
        for (int i = 0; i < 2; i++) {
            if (secondJoker == tail) {
                if (head == firstJoker) {
                    firstJokerPos = 27;
                }
                
                Card prev = secondJoker.getPrev();
                
                prev.setNext(head);
                head.setPrev(prev);
                
                secondJoker.setNext(head.getNext());
                head.getNext().setPrev(secondJoker);
                
                secondJoker.setPrev(null);
                head.setNext(null);
                
                tail = head;
                head = secondJoker;
                secondJokerPos = 0;
            } else {
                Card prev = secondJoker.getPrev();
                Card next = secondJoker.getNext();
                
                if (next == firstJoker) {
                    firstJokerPos--;
                }
                
                if (secondJoker != head) {
                    prev.setNext(next);
                } else {
                    head = next;
                }
                
                next.setPrev(prev);

                secondJoker.setNext(next.getNext());
                if (next != tail) {
                    next.getNext().setPrev(secondJoker);
                } else {
                    tail = secondJoker;
                }
                    
                next.setNext(secondJoker);
                secondJoker.setPrev(next);
                secondJokerPos++;
            }
        }
    }
        
    /**
     * Perform a Triple Cut. That is, take the range starting at the head and
     * ending with the card before the topmost joker, and swap it with the range
     * starting with the card after the bottommost joker and ending with the
     * tail.
     * 
     * Runs in O(1) time.
     */
    public void tripleCut()
    {
        Card topJoker, bottomJoker;
        
        if (firstJokerPos < secondJokerPos) {
            topJoker = firstJoker;
            bottomJoker = secondJoker;
        } else {
            topJoker = secondJoker;
            bottomJoker = firstJoker;
        }
        
        if (topJoker == head && bottomJoker == tail) {
            return; // do nothing
        } else if (topJoker == head) {
            Card b = bottomJoker.getNext();
            topJoker.setPrev(tail);
            tail.setNext(topJoker);
            bottomJoker.setNext(null);
            tail = bottomJoker;
            b.setPrev(null);
            head = b;
        } else if (bottomJoker == tail) {
            Card a = topJoker.getPrev();
            bottomJoker.setNext(head);
            head.setPrev(bottomJoker);
            topJoker.setPrev(null);
            head = topJoker;
            a.setNext(null);
            tail = a;
        } else {
            Card a = topJoker.getPrev();
            Card b = bottomJoker.getNext();
            
            topJoker.setPrev(tail);
            tail.setNext(topJoker);
            bottomJoker.setNext(head);
            head.setPrev(bottomJoker);
            
            head = b;
            tail = a;
            
            tail.setNext(null);
            head.setPrev(null);
        }
        
        int temp = secondJokerPos;
        secondJokerPos = DECKSIZE - firstJokerPos - 1;
        firstJokerPos = DECKSIZE - temp - 1;
    }
	
    /**
     * Make sure the deck data structure makes sense.
     * 
     * @return
     */
    public String sanityCheck()
    {
        StringBuffer badness = new StringBuffer();
        
        if (head.getPrev() != null)
            badness.append("Head has a card before it!\n");
        if (tail.getNext() != null)
            badness.append("Tail has a card after it!\n");
        if (getCardAt(firstJokerPos) != firstJoker)
            badness.append("First joker isn't where it was expected!\n");
        if (getCardAt(secondJokerPos) != secondJoker)
            badness.append("Second joker isn't where it was expected!\n");
        if (firstJokerPos == DECKSIZE - 1 && tail != firstJoker)
            badness.append("First joker is listed at the end, but is not "
                    + "tail!\n");
        if (firstJokerPos == 0 && head != firstJoker)
            badness.append("First joker is listed at the start, but is not "
                    + "head!\n");
        if (secondJokerPos == DECKSIZE - 1 && tail != secondJoker)
            badness.append("Second joker is listed at the end, but is not "
                    + "tail!\n");
        if (secondJokerPos == 0 && head != secondJoker)
            badness.append("Second joker is listed at the start, but is not "
                    + "head!\n");
		
        HashSet<Card> cards = new HashSet<Card>();
        boolean circRef = false;
        Card c = head;
        while (c != null) {
            
            if (c != head && c.getPrev() == null)
                badness.append("A card in the middle has no previous!\n");
            else
                if (c != head && c.getPrev().getNext() != c)
                    badness.append("A card in the middle's previous doesn't "
                            + "refer ahead to it!\n");
            if (c != tail && c.getNext() == null)
                badness.append("A card in the middle has no next!\n");
            else
                if (c != tail && c.getNext().getPrev() != c)
                    badness.append("A card in the middle's next doesn't refer "
                            + "back to it!\n");
            
            if (c.getNext() == c)
                badness.append("A card lists itself as next!\n");
            if (c.getPrev() == c)
                badness.append("A card lists itself as previous!\n");
            
            if (!cards.add(c)) {
                badness.append("Deck has a circular reference!\n");
                circRef = true;
                break;
            }
            
            c = c.getNext();
        }
        
        // if there was a circular reference, this will always be short, so skip
        if (!circRef && cards.size() != DECKSIZE)
            badness.append("Deck has a hole! Couldn't find " + DECKSIZE
                    + " cards!\n");
        
        return badness.toString();
    }
    
    /**
     * Get the index of the Card given.
     * 
     * Runs in O(n) time.
     * 
     * @param c Card to find
     * @return index of card in deck
     */
    public int getIndex(Card c)
    {        
        int i = 0;
        while (c != head) {
            c = c.getPrev();
            i++;
        }
        return i;
    }
    
    /**
     * Get the card at the specified index.
     * 
     * Runs in O(n) time.
     * 
     * @param index Index of card in deck to find
     * @return Card at given index
     */
    public Card getCardAt(int index)
    {
        if (index >= DECKSIZE || index < 0)
            throw new ArrayIndexOutOfBoundsException("Can't get card " + index
                    + " from a " + DECKSIZE + "-card deck!");
        
        Card c = head;
        for (int i = 0; i < index; i++) {
            c = c.getNext();
        }
        
        return c;
    }
    
    /**
     * Return the first joker (27).
     * @return
     */
    public Card getFirstJoker()
    {
        return firstJoker;
    }
    
    /**
     * Return the position of the first joker.
     * @return
     */
    public int getFirstJokerPos()
    {
    	return firstJokerPos;
    }
    
    /**
     * Return the second joker (28).
     * @return
     */
    public Card getSecondJoker()
    {
        return secondJoker;
    }
    
    /**
     * Return the position of the second joker.
     * @return
     */
    public int getSecondJokerPos()
    {
    	return secondJokerPos;
    }
    
    /**
     * Return the card at the top of the deck.
     * @return
     */
    public Card getHead()
    {
        return head;
    }
    
    /**
     * Return the card at the bottom of the deck.
     * @return
     */
    public Card getTail()
    {
        return tail;
    }
    
}