ql33

// Chp. 30 Lab 3
// Lab 3 involves manipulating a queue data structure

// no data structures may be used except for stacks and queues

// Queue methods that you are allowed to use are listed below:
// public boolean add (E x),  public E remove(),  public E peek(),  public boolean isEmpty()

// Stack methods that you are allowed to use are listed below:
// public boolean push (E x),  public E pop(),  public E peek(),  public boolean isEmpty()


import java.util.*;

public class QueueLab3
{
    public static void main(String args[])
    {
        System.out.println("Java3016.java\n\n");

        // default constructor
        QueueManipulate <Integer> aQueue = new QueueManipulate <Integer>();

        Queue<Integer> queue2 = new LinkedList<Integer>();
        queue2.add(1); queue2.add(3); queue2.add(5);

        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);
        System.out.println(queue);


        // overloaded constructor
        QueueManipulate <Integer> myQueue = new QueueManipulate <Integer> (queue);
        System.out.println("overloaded constructor"); myQueue.display(); System.out.println();


        // copy constructor
        QueueManipulate <Integer> ourQueue = new QueueManipulate <Integer> (myQueue);
        System.out.println("\ncopy constructor\n");
        System.out.println(ourQueue); ourQueue.display();
        System.out.println("\n" + myQueue); myQueue.display();
        queue = new LinkedList<Integer>();
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);

        // removeFirst
        System.out.println("\n\nremoveFirst\n");
        myQueue = new QueueManipulate <Integer> (queue);
        myQueue.removeFirst(6); myQueue.removeFirst(2); myQueue.display();
        queue = new LinkedList<Integer>();
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);

        // removeAll
        System.out.println("\n\nremoveAll\n");
        myQueue = new QueueManipulate <Integer> (queue);
        myQueue.removeAll(2); myQueue.removeAll(4); myQueue.display();
        queue = new LinkedList<Integer>();
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);

        // reverse
        System.out.println("\n\nreverse\n");
        myQueue = new QueueManipulate <Integer> (queue);
        myQueue.reverse(); myQueue.display();
        queue = new LinkedList<Integer>();
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);

        // clone
        System.out.println("\n\nclone\n");
        myQueue = new QueueManipulate <Integer> (queue);
        aQueue = new QueueManipulate <Integer> (queue2);
        System.out.println(aQueue); aQueue.display(); System.out.println();
        System.out.println(myQueue); myQueue.display(); System.out.println();
        myQueue.clone(aQueue); System.out.println(aQueue); aQueue.display();
        System.out.println(); System.out.println(myQueue); myQueue.display();
        queue = new LinkedList<Integer>();
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);
        queue2 = new LinkedList<Integer>();
        queue2.add(1); queue2.add(3); queue2.add(5);

        // append
        System.out.println("\n\nappend\n");
        myQueue = new QueueManipulate <Integer> (queue);
        aQueue = new QueueManipulate <Integer> (queue2);
        System.out.println(aQueue); aQueue.display(); System.out.println();
        System.out.println(myQueue); myQueue.display(); System.out.println();
        myQueue.append(aQueue); System.out.println(aQueue); aQueue.display();
        System.out.println(); System.out.println(myQueue); myQueue.display();
        queue = new LinkedList<Integer>();
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);
        queue2 = new LinkedList<Integer>();
        queue2.add(1); queue2.add(3); queue2.add(5);

        // replace
        System.out.println("\n\nreplace\n");
        myQueue = new QueueManipulate <Integer> (queue);
        System.out.println(); System.out.println(myQueue);
        myQueue.display();System.out.println(); myQueue.replace(2,4);
        System.out.println(myQueue); myQueue.display();
        queue = new LinkedList<Integer>();
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);

        // moveToFront
        System.out.println("\n\nmoveToFront\n");
        myQueue = new QueueManipulate <Integer> (queue);
        System.out.println(); System.out.println(myQueue);
        myQueue.display(); System.out.println();    myQueue.moveToFront(4);
        System.out.println(myQueue); myQueue.display();
        queue = new LinkedList<Integer>();
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);

        // moveToBack
        System.out.println("\n\nmoveToBack\n");
        myQueue = new QueueManipulate <Integer> (queue);
        System.out.println(); System.out.println(myQueue);
        myQueue.display();System.out.println(); myQueue.moveToBack(2);
        System.out.println(myQueue); myQueue.display();
        queue = new LinkedList<Integer>();
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);

        // insertItem
        System.out.println("\n\ninsertItem\n");
        myQueue = new QueueManipulate <Integer> (queue);
        System.out.println(); System.out.println(myQueue);
        myQueue.display();System.out.println();
        myQueue.insertItem(4,3); System.out.println(myQueue); myQueue.display();
        queue = new LinkedList<Integer>();
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);


        /*
        aQueue = new QueueManipulate <Integer> (queue2);
        System.out.println("\n\nremovefirst\n");
        System.out.println(aQueue.removeFirst(5));
        System.out.println(aQueue.removeFirst(6));
        queue2 = new LinkedList<Integer>();
        queue2.add(1); queue2.add(3); queue2.add(5);

        aQueue = new QueueManipulate <Integer> (queue2);
        System.out.println("\n\nremoveAll\n");
        System.out.println(aQueue.removeAll(5));
        System.out.println(aQueue.removeAll(6));
        queue2 = new LinkedList<Integer>();
        queue2.add(1); queue2.add(3); queue2.add(5);

        myQueue = new QueueManipulate <Integer> (queue);
        System.out.println("\n\nreplace\n");
        System.out.println(myQueue.replace(5,4));
        System.out.println(myQueue.replace(6,5));
        queue = new LinkedList<Integer>();
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);

        aQueue = new QueueManipulate <Integer> (queue2);
        System.out.println("\n\nmoveToFront\n");
        System.out.println(aQueue.moveToFront(5));
        System.out.println(aQueue.moveToFront(6));
        queue2 = new LinkedList<Integer>();
        queue2.add(1); queue2.add(3); queue2.add(5);

        aQueue = new QueueManipulate <Integer> (queue2);
        System.out.println("\n\nmoveToBack\n");
        System.out.println(aQueue.moveToBack(2));
        System.out.println(aQueue.moveToBack(5));
        queue2 = new LinkedList<Integer>();
        queue2.add(1); queue2.add(3); queue2.add(5);

        myQueue = new QueueManipulate <Integer> (queue);
        System.out.println("\n\ninsert\n");
        System.out.println(myQueue.insertItem(5,4));
        System.out.println(myQueue.insertItem(6,5));
        queue = new LinkedList<Integer>();
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);
        queue.add(2); queue.add(4); queue.add(6);
        */

        System.out.println("\n\n");
    }
}

class QueueManipulate<E>
{

    private Queue <E> myQueue;

    // default constructor - instantiates myQueue, myQueue should be empty after this constructor call
    public QueueManipulate()
    {
        myQueue=new LinkedList<E>();
    }



    // overloaded constructor - recieves parameter queue(a queue of type E), instantiates myQueue, and
    // copies all data items from parameter queue(front to back) into myQueue(front to back)
    public QueueManipulate(Queue <E> queue)
    {
        Queue<E> temp=new LinkedList<E>();
        myQueue=new LinkedList<E>();
        while(!queue.isEmpty())
        {
            myQueue.add(queue.peek());
            temp.add(queue.remove());
        }
        while(!temp.isEmpty())
        {
            queue.add(temp.remove());
        }

    }



    // copy constructor - recieves parameter queueManipObj(a QueueManipulate object), instantiates myQueue(of the curent oject in scope), and
    // copies all data items from myQueue(of parameter queueManipObj, front to back) into myQueue(of the curent oject in scope, front to back)
    // all data items in myQueue(of the parameter queueManipObj) should not be affected and remain in the same order
    public QueueManipulate(QueueManipulate queueManipObj)
    {
        myQueue=new LinkedList<E>();
        queueManipObj.clone(this);
    }



    // displays all data items in myQueue, front to back (each item on a seperate line) while preserving the order of data items in myQueue
    public void display()
    {
            Queue<E> temp=new LinkedList<E>();

          while(!myQueue.isEmpty())
          {
            E temp2=myQueue.remove();
            temp.add(temp2);
          }

          while(!temp.isEmpty())
          {
            E temp2=temp.remove();
            System.out.println(temp2);
            myQueue.add(temp2);
          }
    }



    // receives parameter target(of type E), removes the first occurrence of target from myQueue and leaves the remaining data items in myQueue intact
    // returns true if target found, returns false if target not found
    public boolean removeFirst(E target)
    {
        Queue<E> temp=new LinkedList<E>();
        int k=0;
        while(!myQueue.isEmpty())
          {
            if(target.equals(myQueue.peek()) && k==0)
            {
            k=1;
            myQueue.remove();
            }
            else
                temp.add(myQueue.remove());
          }
        while(!temp.isEmpty())
        {
            myQueue.add(temp.remove());
        }

        return k==1;
    }



    // receives parameter target(of type E), removes all occurrences of target from myQueue and leaves the remaining data items in myQueue intact
    // returns true if target(s) found, returns false if target(s) not found
    public boolean removeAll(E target)
    {
        Queue<E> temp=new LinkedList<E>();
        int k=0;
        while(!myQueue.isEmpty())
          {
            if(target.equals(myQueue.peek()) )
            {
            k=1;
            myQueue.remove();
            }
            else
                temp.add(myQueue.remove());
          }
        while(!temp.isEmpty())
        {
            myQueue.add(temp.remove());
        }

        return k==1;
    }



    // reverses the the data items in myQueue (ie.  1 2 3 4   shold now be   4 3 2 1)
    public void reverse()
    {
        Stack<E> stack= new Stack<E>();
        while(!myQueue.isEmpty())
        {
            stack.push(myQueue.remove());
        }

        while(!stack.isEmpty())
        {
            myQueue.add(stack.pop());
        }
    }



    // recieves parameter queueManipObj(a QueueManipulate object), copies all data items from myQueue(of the curent oject in scope, front to back)
    // into myQueue(of parameter queueManipObj, front to back)
    // this is a clone method not an append method  ***  myQueue of parameter queueManipObj should be empty before you copy data items
    // all data items in myQueue(of the curent object in scope) should not be affected and remain in the same order
    public void clone(QueueManipulate queueManipObj)
    {
            Queue<E> queue = new LinkedList<E>();

            while(!myQueue.isEmpty())
            {
                queue.add(myQueue.peek());
                queueManipObj.getQueue().add(myQueue.remove());
            }

            while(!queue.isEmpty())
            {
                myQueue.add(queue.remove());
            }

    }



    // recieves parameter queueManipObj(a QueueManipulate object), copies all data items from myQueue(of parameter queueManipObj, front to back)
    // to the back of myQueue(of the curent oject in scope)
    // this is an append method not a copy constructor or clone method  ***  do not remove any data items in myQueue of (of the curent oject in scope)
    // all data items in myQueue(of the parameter queueManipObj) should not be affected and remain in the same order
    public void append(QueueManipulate queueManipObj)
    {
        Queue<E> queue = new LinkedList<E>();

        while(!queueManipObj.getQueue().isEmpty())
        {
            queue.add(myQueue.peek());
             myQueue.add((E) queueManipObj.getQueue().remove());
        }

        while(!queue.isEmpty())
        {
            queueManipObj.getQueue().add(queue.remove());
        }
    }



    // receives parameters target and newValue(both of type E), replaces ALL occurrences of target, contained in myQueue, with parameter newValue
    // all other data items in myQueue should not be affected and remain in the same order
    // return the amount of data items that were replaced
    public int replace(E target, E newValue )
    {
        Queue<E> temp=new LinkedList<E>();
        int k=0;
        while(!myQueue.isEmpty())
          {
            if(target.equals(myQueue.peek()) )
            {
            k=1;
            myQueue.remove();
            temp.add(newValue);
            }
            else
                temp.add(myQueue.remove());
          }
        while(!temp.isEmpty())
        {
            myQueue.add(temp.remove());
        }



        return -999;
    }



    // receives parameter target(of type E), searches myQueue for target, if target is found, return true and,
    // move ALL occurrences of target to the front of myQueue (there may be one, more than one, or no occurrence of target)
    // if target not found return false
    // all other data items in myQueue should not be affected and remain in the same order
    public boolean moveToFront(E target)
    {
        Queue<E> temp=new LinkedList<E>();
        boolean TF=false;
        Queue<E> tempnon=new LinkedList<E>();

        while(!myQueue.isEmpty())
          {
            if(myQueue.peek().equals(target))
                temp.add(myQueue.remove());
            else
                tempnon.add(myQueue.remove());
            while(!temp.isEmpty())
            {
                myQueue.add(temp.remove());
                TF=true;
            }
            while(!tempnon.isEmpty())
            {
                myQueue.add(tempnon.remove());
            }

          }
        return TF;
    }



    // receives parameter target(of type E), searches myQueue for target, if target is found, return true and,
    // move ALL occurrences of target to the back of myQueue (there may be one, more than one, or no occurrence of target)
    // if target not found return false
    // all other data items in myQueue should not be affected and remain in the same order
    public boolean moveToBack(E target)
    {

        Queue<E> temp=new LinkedList<E>();
        boolean TF=false;
        Queue<E> tempnon=new LinkedList<E>();

        while(!myQueue.isEmpty())
          {
            if(myQueue.peek().equals(target))
                temp.add(myQueue.remove());
            else
                tempnon.add(myQueue.remove());
            while(!tempnon.isEmpty())
            {
                myQueue.add(tempnon.remove());

            }
            while(!temp.isEmpty())
            {
                myQueue.add(temp.remove());
                TF=true;
            }

          }
        return TF;
    }



    // receives parameters target and newValue(both of type E), searches myQueue for target, if target is found, return true and
    // insert the parameter newValue immediately BEFORE ALL occurrences of target(there may be one, more than one, or no occurrence of target)
    // if target not found return false
    // all other data items in myQueue should not be affected and remain in the same order
    public boolean insertItem(E target, E newValue)
    {
        Queue<E> temp=new LinkedList<E>();
        int k=0;
        while(!myQueue.isEmpty())
          {
            if(target.equals(myQueue.peek()) )
            {
            k=1;
            temp.add(newValue);
            temp.add(myQueue.remove());

            }
            else
                temp.add(myQueue.remove());
          }
        while(!temp.isEmpty())
        {
            myQueue.add(temp.remove());
        }



        return k==1;


    }

    public Queue getQueue()
    {
        return myQueue;
    }


}