Free2Code
The majority of forums are now only available as archives, which means posting/editing is disabled.

The Anything and Everything forum is still open.
 
Time: 2014-09-16, 03:25am
Sorted Queue using array of ListNodes [Question]
Subject: Sorted Queue using array of ListNodes [Question]  ·  Posted: 2004-12-06, 01:30am
Rank: ? (1)
Member #: 22787
So I need to make this queue. The enqueue method finds the right place to add the node and the dequeue method just takes the node off of the front. I'm having problems setting it up, though. This is my code at the moment:
Code:
  1. public class RPQueue implements RPQueueInterface
  2. {
  3.     private Memory queue;        // Array that holds queue elements
  4.     private int capacity;        // size of the array (capacity of the queue)
  5.     private int numItems = 0;    // number of items on the queue
  6.     private int front = 0;       // location of the front of the queue
  7.     final byte DECREASING = 0;   // used to determine current order of queue
  8.     final byte INCREASING = 1;   // used to determine current order of queue
  9.     
  10.     /**
  11.      * ListNode creates variables for use in storing information in nodes.
  12.      *
  13.      * @author Dale, Joyce, Weems & Christopher Yount
  14.      * @version 11/9/04
  15.     */
  16.     protected class ListNode
  17.     // Used to hold references to list nodes for the linked list implementation
  18.     {
  19.         protected Comparable info;   // used to store the info in a list node
  20.         protected int next;          // used as a reference to the next node in the array
  21.     }
  22.     
  23.     /**
  24.      * Creates an array data structure of ListNodes.
  25.      *
  26.      * @author Christopher Yount
  27.      * @version 11/22/04
  28.      */
  29.     protected class Memory
  30.     {
  31.         ListNode array[];
  32.         protected ListNode list;          // reference to first node in list
  33.         protected ListNode free;          // reference to first node in free list
  34.         protected int currentPos = 0;     // Current position for iteration
  35.         
  36.         // Constructors
  37.         public Memory()
  38.         {
  39.             array = new ListNode[100];
  40.             capacity = 100;
  41.             for (int i = 0; i < capacity - 2; i++)
  42.             {
  43.                 array[i] = null;
  44.                 array[i].next = i + 1;
  45.             }
  46.             array[capacity - 1] = null;
  47.             array[capacity - 1].next = -1;
  48.             
  49.             list = null;
  50.             free = array[0];
  51.         }
  52.         
  53.         public Memory(int maxSize)
  54.         {
  55.             array = new ListNode[maxSize];
  56.             capacity = maxSize;
  57.             for (int i = 0; i < capacity - 2; i++)
  58.             {
  59.                 array[i] = null;
  60.                 array[i].next = i + 1;
  61.             }
  62.             array[capacity - 1] = null;
  63.             array[capacity - 1].next = -1;
  64.             
  65.             list = null;
  66.             free = array[0];
  67.         }
  68.         
  69.         /**
  70.          * This method returns the address of the next linked-list node or -1 if the array
  71.          * is full
  72.          *
  73.          * @return     an int holding the value of the next linked-list node or -1
  74.          */
  75.         public int allocate()
  76.         // Effect:         Returns the address of the next linked-list node
  77.         //                 or -1 if there is no space left.
  78.         // Postconditions: if (isFull), -1 is returned, otherwise, return the address
  79.         //                 of the next linked-list node
  80.         {
  81.             int allocated = 0;
  82.             
  83.             if (numItems != 0)
  84.             {
  85.                 if (currentPos == capacity - 1)
  86.                     allocated = -1;
  87.                 else if (numItems > 1)
  88.                     allocated = array[currentPos].next;
  89.             }
  90.             
  91.             return allocated;
  92.         }
  93.         
  94.         /**
  95.          * This method reinserts the node with address "cell" back into the free list or
  96.          * raises an assert exception if "cell" is outside the proper range.
  97.          *
  98.          * @param  y   an int referencing an address
  99.          */
  100.         public void deallocate (int cell)
  101.         {
  102.             assert (cell > capacity - 1):
  103.                    "Cell is outside of the proper range.";
  104.             
  105.             array[cell].next = free.next;
  106.             free = array[cell];
  107.             
  108.         }
  109.     }
  110.     
  111.     // Constructors
  112.     public RPQueue()
  113.     {
  114.         queue = new Memory();
  115.     }
  116.     
  117.     public RPQueue(int maxSize)
  118.     {
  119.         queue = new Memory(maxSize);
  120.     }
  121.    
  122.     /**
  123.      * This method determines whether or not the queue is empty.
  124.      *
  125.      * @return     a boolean value containing the result of isEmpty == true
  126.      */
  127.     public boolean isEmpty()
  128.     // Effect:         Determines whether this priority queue is empty.
  129.     // Postcondition:  Return value = (this priority queue is empty)
  130.     {
  131.         boolean emptyQueue = false;
  132.         
  133.         if (numItems == 0)
  134.         {
  135.             emptyQueue = true;
  136.         }
  137.         
  138.         return emptyQueue;
  139.     }
  140.     
  141.     /**
  142.      * This method determines whether or not the queue is full.
  143.      *
  144.      * @return     a boolean value containing the result of isFull == true
  145.      */
  146.     public boolean isFull()
  147.     // Effect:         Determines whether this priority queue is full.
  148.     // Postcondition:  Return value = (priority queue is full)
  149.     {
  150.         boolean fullQueue = false;
  151.         
  152.         if (queue.allocate() == -1)
  153.             fullQueue = true;
  154.             
  155.         return fullQueue;
  156.     }
  157.     
  158.     /**
  159.      * This method adds an item onto the queue, in its sorted place.
  160.      *
  161.      * @param  y   an object of type Comparable
  162.      */
  163.     public void enqueue(Comparable item)
  164.     // Effect:         Adds item to this priority queue.
  165.     // Postcondition:  If (this priority queue is full)
  166.     //                   an unchecked exception that communicates &acirc;enqueue
  167.     //                   on priority queue full&acirc; is thrown
  168.     //                 Else
  169.     //                   item is in this priority queue.
  170.     {
  171.         assert (!isFull()):
  172.                "Queue is full. Please dequeue before attempting to enqueue.";
  173.         
  174.         ListNode newNode = new ListNode();    // reference to node being inserted
  175.         ListNode prevLoc = new ListNode();    // trailing reference
  176.         ListNode location = new ListNode();   // traveling reference
  177.         int spaceHolder = 0;
  178.         boolean moreToSearch;
  179.         
  180.         location = queue.list;
  181.         prevLoc = null;
  182.         moreToSearch = (location != null);
  183.         
  184.         // Find insertion point.
  185.         while (moreToSearch)
  186.         {
  187.             if (item.compareTo(location.info) > 0)   // list element is larger than item
  188.                 moreToSearch = false;
  189.             
  190.             else
  191.             {
  192.                 prevLoc = location;
  193.                 queue.currentPos = location.next;
  194.                 location = queue.array[queue.currentPos];
  195.                 moreToSearch = (location.info != null);
  196.             }
  197.         }
  198.         
  199.         // Prepare node for insertion.
  200.         newNode.info = item;
  201.         // Insert node into list.
  202.         if (prevLoc == null)   // Insert as first
  203.         {
  204.             newNode.next = queue.currentPos;
  205.             queue.list = newNode;
  206.         }
  207.         else
  208.         {
  209.             newNode.next = prevLoc.next;
  210.             queue.array[prevLoc.next] = newNode;
  211.         }
  212.         
  213.         numItems++;
  214.     }
  215.     
  216.     /**
  217.      * This method removes an element from front of the queue and returns a reference
  218.      * to it.
  219.      *
  220.      * @return     a reference to the removed element
  221.      */
  222.     public Comparable dequeue()
  223.     // Effect:         Removes element with highest priority from this
  224.     //                   priority queue and returns a reference to it
  225.     // Postconditions: If (this priority queue is empty)
  226.     //                   an error message is produced
  227.     //                 Else
  228.     //                   Highest priority element has been removed.
  229.     //                   Return value = (reference to the removed element)
  230.     {
  231.         Comparable reference;
  232.         int newFront;
  233.         
  234.         assert (numItems != 0):
  235.                "You cannot dequeue from an empty queue.";
  236.                
  237.         reference = queue.array[front].info;
  238.         newFront = queue.array[front].next;
  239.         queue.deallocate(front);
  240.         front = newFront;
  241.         numItems--;
  242.         
  243.         return reference;
  244.         
  245.     }
  246.     /**
  247.      * This method reverses the order of the list, resulting in a list sorted in an
  248.      * increasing or decreasing manner.
  249.      *
  250.      */    
  251.     public void Reverse()
  252.     // Effect:         Reverses the order of the sorted list
  253.     // Postconditions: The list is now sorted in either ascending or descending order
  254.     {
  255.         byte order = 0;
  256.         
  257.         if (queue.array[0].info.compareTo(queue.array[queue.array[0].next].info) > 0)
  258.         {
  259.             order = DECREASING;
  260.         }
  261.         else
  262.         {
  263.             order = INCREASING;
  264.         }
  265.         
  266.         if (order == DECREASING)
  267.         {
  268.             
  269.         }
  270.         
  271.         else
  272.         {
  273.             
  274.         }
  275.     }
  276.     
  277.     public String displayQueue()
  278.     {
  279.         int i = 0;
  280.         String queueContents = "";
  281.         for (i = 0; i < numItems; i++)
  282.         {
  283.             queueContents = queueContents + queue.array[i] + " ";
  284.         }
  285.         
  286.         return queueContents;
  287.     }
  288. }


I'm getting null pointer exceptions where I define the Memory arrays. What am I doing wrong? Also, I need to be able to reverse the order of the queue. I feel like I should be able to do this recursively. Am I correct? How would I go about doing this? Thank you.

 
  Reply to this ·  Post link ·  Top

Pages: 1

Please login or register to post a reply.