// Purpose.  Need to refactor to sort out "interface vs implementation"

class StackArray {
    private int[] items = new int[12];
    private int   total = -1;
    public void push( int i ) { if ( ! isFull()) items[++total] = i; }
    public boolean isEmpty()  { return total == -1; }
    public boolean isFull()   { return total == 11; }
    public int top() {
        if (isEmpty()) return -1;
        return items[total];
    }
    public int pop() {
        if (isEmpty()) return -1;
        return items[total--];
}   }

class StackList {
    private Node last;
    public void push( int i ) {
        if (last == null)
            last = new Node( i );
        else {
            last.next = new Node( i );
            last.next.prev = last;
            last = last.next;
    }   }
    public boolean isEmpty() { return last == null; }
    public boolean isFull()  { return false; }
    public int top() {
        if (isEmpty()) return -1;
        return last.value;
    }
    public int pop() {
        if (isEmpty()) return -1;
        int ret = last.value;
        last = last.prev;
        return ret;
}   }

class StackFIFO extends StackArray {
    private StackArray temp = new StackArray();
    public int pop() {
        while ( ! isEmpty())
            temp.push( super.pop() );
        int ret =  temp.pop();
        while ( ! temp.isEmpty())
            push( temp.pop() );
        return ret;
}  }

class StackHanoi extends StackArray {
    private int totalRejected = 0;
    public int reportRejected()   { return totalRejected; }
    public void push( int in ) {
        if ( ! isEmpty()  &&  in > top())
            totalRejected++;
        else super.push( in );
}   }

class BridgeDisc {
    public static void main( String[] args ) {
        StackArray[] stacks = { new StackArray(), new StackFIFO(), new StackHanoi() };
        StackList    stack2 = new StackList();
        for (int i=1, num; i < 15; i++) {
            stacks[0].push( i );
            stack2.push( i );
            stacks[1].push( i );
        }
        java.util.Random rn = new java.util.Random();
        for (int i=1, num; i < 15; i++)
            stacks[2].push( rn.nextInt(20) );
        while ( ! stacks[0].isEmpty())
            System.out.print( stacks[0].pop() + "  " );
        System.out.println();
        while ( ! stack2.isEmpty())
            System.out.print( stack2.pop() + "  " );
        System.out.println();
        while ( ! stacks[1].isEmpty())
            System.out.print( stacks[1].pop() + "  " );
        System.out.println();
        while ( ! stacks[2].isEmpty())
            System.out.print( stacks[2].pop() + "  " );
        System.out.println();
        System.out.println( "total rejected is "
            + ((StackHanoi)stacks[2]).reportRejected() );
}   }

// 12  11  10  9  8  7  6  5  4  3  2  1
// 14  13  12  11  10  9  8  7  6  5  4  3  2  1
// 1  2  3  4  5  6  7  8  9  10  11  12
// 0  0  1  12  16  18
// total rejected is 8

class Node {
    public int  value;
    public Node prev, next;
    public Node( int i ) { value = i; }
}



// Purpose.  Bridge design pattern
// 1. Create an implementation/body abstraction
// 2. Derive the separate implementations from the common abstraction
// 3. Create an interface/handle class that "has a" and delegates to the impl
// 4. Embellish the interface class with derived classes if desired

class Stack {
    private StackImpl impl;
    public Stack( String s ) {
        if      (s.equals("array")) impl = new StackArray();
        else if (s.equals("list"))  impl = new StackList();
        else System.out.println( "Stack: unknown parameter" );
    }
    public Stack()                { this( "array" ); }
    public void    push( int in ) { impl.push( in ); }
    public int     pop()          { return impl.pop(); }
    public int     top()          { return impl.top(); }
    public boolean isEmpty()      { return impl.isEmpty(); }
    public boolean isFull()       { return impl.isFull(); }
}

class StackHanoi extends Stack {
    private int totalRejected = 0;
    public StackHanoi()           { super( "array" ); }
    public StackHanoi( String s ) { super( s ); }
    public int reportRejected()   { return totalRejected; }
    public void push( int in ) {
        if ( ! isEmpty()  &&  in > top())
            totalRejected++;
        else super.push( in );
}   }

class StackFIFO extends Stack {
    private StackImpl temp = new StackList();
    public StackFIFO()           { super( "array" ); }
    public StackFIFO( String s ) { super( s ); }
    public int pop() {
        while ( ! isEmpty())
            temp.push( super.pop() );
        int ret =  temp.pop();
        while ( ! temp.isEmpty())
            push( temp.pop() );
        return ret;
}  }

interface StackImpl {
    void    push( int i );
    int     pop();
    int     top();
    boolean isEmpty();
    boolean isFull();
}

class StackArray implements StackImpl {
    private int[] items = new int[12];
    private int   total = -1;
    public void push( int i ) { if ( ! isFull()) items[++total] = i; }
    public boolean isEmpty()  { return total == -1; }
    public boolean isFull()   { return total == 11; }
    public int top() {
        if (isEmpty()) return -1;
        return items[total];
    }
    public int pop() {
        if (isEmpty()) return -1;
        return items[total--];
}   }

class StackList implements StackImpl {
    private Node last;
    public void push( int i ) {
        if (last == null)
            last = new Node( i );
        else {
            last.next = new Node( i );
            last.next.prev = last;
            last = last.next;
    }   }
    public boolean isEmpty() { return last == null; }
    public boolean isFull()  { return false; }
    public int top() {
        if (isEmpty()) return -1;
        return last.value;
    }
    public int pop() {
        if (isEmpty()) return -1;
        int ret = last.value;
        last = last.prev;
        return ret;
}   }

class BridgeDisc {
    public static void main( String[] args ) {
        Stack[] stacks = { new Stack( "array" ), new Stack( "list" ),
            new StackFIFO(), new StackHanoi() };
        for (int i=1, num; i < 15; i++)
            for (int j=0; j < 3; j++)
                stacks[j].push( i );
        java.util.Random rn = new java.util.Random();
        for (int i=1, num; i < 15; i++)
            stacks[3].push( rn.nextInt(20) );
        for (int i=0, num; i < stacks.length; i++) {
            while ( ! stacks[i].isEmpty())
                System.out.print( stacks[i].pop() + "  " );
            System.out.println();
        }
        System.out.println( "total rejected is "
            + ((StackHanoi)stacks[3]).reportRejected() );
}   }

// 12  11  10  9  8  7  6  5  4  3  2  1
// 14  13  12  11  10  9  8  7  6  5  4  3  2  1
// 1  2  3  4  5  6  7  8  9  10  11  12
// 0  0  1  12  16  18
// total rejected is 8

class Node {
    public int  value;
    public Node prev, next;
    public Node( int i ) { value = i; }
}



// Purpose.  Bridge design pattern
// 1. Create an implementation/body base class
// 2. Derive the separate implementations from the common abstraction
// 3. Create an interface/wrapper class that "hasa" and delegates to the impl
// 4. Embellish the interface class with derived classes if desired

class Stack {                  // 3. Create an interface/wrapper class that
   protected StackImp imp;     //    "hasa" implementation object and delegates
   public Stack( String s ) {  //    all requsts to it
      if (s.equals("java")) imp = new StackJava();
      else                  imp = new StackMine(); }
   public Stack()                { this( "java" ); }
   public void    push( int in ) { imp.push( new Integer(in) ); }
   public int     pop()          { return ((Integer)imp.pop()).intValue(); }
   public boolean isEmpty()      { return imp.empty(); }
}

class StackHanoi extends Stack {   // 4. Embellish the interface class with
   private int totalRejected = 0;  //     derived classes if desired
   public StackHanoi()           { super( "java" ); }
   public StackHanoi( String s ) { super( s ); }
   public int reportRejected()   { return totalRejected; }
   public void push( int in ) {
      if ( ! imp.empty()  &&  in > ((Integer)imp.peek()).intValue())
         totalRejected++;
      else imp.push( new Integer(in) );
}  }

interface StackImp {           // 1. Create an implementation/body base class
   Object  push( Object o );   Object  peek();
   boolean empty();            Object  pop(); }

class StackJava extends java.util.Stack implements StackImp { }

class StackMine implements StackImp {        // 2. Derive the separate impl's
   private Object[] items = new Object[20];  //    from the common abstraction
   private int      total = -1;
   public Object push( Object o ) { return items[++total] = o; }
   public Object peek()           { return items[total]; } 
   public Object pop()            { return items[total--]; }
   public boolean empty()         { return total == -1; }
}

class BridgeDemo {
   public static void main( String[] args ) {
      Stack[] stacks = { new Stack("java"), new Stack("mine"), 
         new StackHanoi("java"), new StackHanoi("mine") };
      for (int i=0, num; i < 20; i++) {
         num = (int) (Math.random() * 1000) % 40;
         for (int j=0; j < stacks.length; j++) stacks[j].push( num );
      }
      for (int i=0, num; i < stacks.length; i++) {
         while ( ! stacks[i].isEmpty())
            System.out.print( stacks[i].pop() + "  " );
         System.out.println();
      }
      System.out.println( "total rejected is "
         + ((StackHanoi)stacks[3]).reportRejected() );
}  }

// 30  3  6  10  0  14  23  39  2  5  30  20  13  31  9  4  30  11  15  36
// 30  3  6  10  0  14  23  39  2  5  30  20  13  31  9  4  30  11  15  36
// 0  2  4  11  15  36
// 0  2  4  11  15  36
// total rejected is 14