We help IT Professionals succeed at work.

Deep copy a queue without changing the existing queue?

tyweed420
tyweed420 asked
on
9,183 Views
Last Modified: 2012-06-22
I'm trying to get the clone method to completly copy the queue so that any further modifications on the existing queue after issuing the clone() will not effect the copy. However , i'm scratching my head as to how you get a deep copy of an existing queue without modifying the existing queue?

see because you need to get all the data so you need to somehow step through the entire queue  and add it to the copy. but by doing so you need to dequeue the queue whuich removes the item from the original queue changing it. If someone can help me deep copy this proirityqueue i'd apprecciate it!

        public Object clone()
        {
                  PriorityQueue answer = null;

             try
             {
                  answer = (PriorityQueue) super.clone();

             }
             catch (CloneNotSupportedException ignore)
           {
                                //This will never happen because this class is Clonable
                   return null;  //Never get here
           }
          
             //step through queue somehow to get the data values but this would change the existing queue yes?
                      while(!queue.isEmpty() )
                     { //i have no idea how to get a deep copy of a queue?
                            answer.enqueue(dequeue(queue) );
                    }
                
                  return answer;
            }


-----------------Class Priority Queue------------------------------------


    import java.util.TreeSet;

   public class PriorityQueue {
        /**
         * the queue is implemented by a TreeSet because it includes a sort algorithm !
         */
        private TreeSet queue;

        /**
         *
         */
        public PriorityQueue() {
            queue = new TreeSet();
        }

        /**
         * Remove all the elements of the queue
         */
        public void clear() {
            queue.clear();
        }

        /**
         *
         * @return true if the queue is empty
         */
        public boolean isEmpty() {
            if (queue.isEmpty()) {
                return true;
            }
            else {
                return false;
            }
        }

        /**
         *
         * @return int the number of elements in the queue
         */
        public int getSize() {
            return queue.size();
        }

        /**
         *
         * @param element any object !
         * @param priority should be >= 0
         */
        public void insert(Vertex element, int priority) {
            if (element == null) {
                throw new IllegalArgumentException("element must be not null");
            }
            if (priority < 0) {
                throw new IllegalArgumentException("Illegal distance: " + priority);
            }
            QueueElement queueElement = new QueueElement(element, priority);
            queue.add(queueElement);
        }

        public Object clone()
        {
                  PriorityQueue answer = null;

             try
             {
                  answer = (PriorityQueue) super.clone();

             }
             catch (CloneNotSupportedException ignore)
           {
                                //This will never happen because this class is Clonable
                   return null;  //Never get here
           }
          
          
                
                  return answer;
            }


        public Vertex getShortest()
        {
                    if (!isEmpty())
                       {
                                  QueueElement queueElement = (QueueElement) queue.first();
                                  Vertex element = queueElement.element;
                                  //queue.remove(queueElement);
                             return element;
                                     }
                                     else
                                     return null;
            }

        /**
         *
         * @return Object the element in the queue which has the lowest priority. Also removes it from the queue.
         */
        public Vertex dequeueLowestPriorityElement() {
            if (!isEmpty())
            {
                QueueElement queueElement = (QueueElement) queue.first();
                Vertex element = queueElement.element;
                queue.remove(queueElement);
                return element;
            }
            else {
                return null;
            }
        }

        /**
         *
         * <p>Title: graphs</p>
         * <p>Description: element of the Queue. It contains an object and his priority.
         *  Implements Compartable to be used by the TreeSet. </p>
         * <p>Copyright: Copyright (c) 2002</p>
         * <p>Company: </p>
         * @author Jean-Michel Garnier
         * @version 1.0
         */
        class QueueElement implements Comparable {

            /**
             * any object
             */
            public Vertex element;

            /**
             * Priority. Must be >= 0
             */
            public int priority;

            /**
             *
             * @param element
             * @param priority
             */
            public QueueElement(Vertex element, int priority)
            {
                this.element = element;
                this.priority = priority;
            }

            /**
             * Implementation of compareTo
             * @param o
             * @return int a negative integer, zero, or a positive
             *    integer as the priority of this object is less than, equal to, or
             * greater than the specified object.
             * @author Modified by Olivier Daroux
             */
            public int compareTo(Object o) {
                QueueElement ps = (QueueElement) o;
                int priorityOther = ps.priority;
                if (this.priority == priorityOther) {
                    if ( this.element.equals(ps.element) ) {
                        return 0;
                    } else {
                        return -1;
                    }
                }
                else {
                    if (this.priority < priorityOther) {
                        return -1;
                    }
                    else {
                        return 1;
                    }
                }
            }

        } // End Class QueueElement

    } // End Class PriorityQueue

---------------------------------------------------
Comment
Watch Question

This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
I'v had to do some tinkering with your code to get it to get close to compile. However, one error below i do not know how to fix? any ideas?

----------------------------------ERROR----------------------
C:\Documents and Settings\Steven  Labarbera\Desktop\cs146\hw4\PriorityQueue.java:67: clone() has protected access in java.lang.Object
                     answer.queue.add( ( (QueueElement) it.next() ).clone() );
                                       ^
1 error

Tool completed with exit code 1


---------------------------------------------------------------

these are the changes does this look ok the changes i'v made?

   public Object clone()
          {
                 PriorityQueue answer = new PriorityQueue();

                 for(Iterator it = queue.iterator();it.hasNext();) {
                     answer.queue.add( ( (QueueElement) it.next() ).clone() );
                  }
                  return answer;
            }
CERTIFIED EXPERT
Top Expert 2016

Commented:
http://java.sun.com/j2se/1.5.0/docs/api/java/util/PriorityQueue.html

Has a ctor that will produce a clone by the looks
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION