FIFO Minheap Priority Queue

Well, it's been a while.  Nice to be back :D

I've been working this code for a couple days... and it's been giving me some problems.  I originally thought it was working because my input file was small.  But, as the input was more numerous the problem showed itself.  

Here's a break down of what my code is suppose to do:

1. Except data from an input.txt file.
2. Sort according to minheap.
3. Queue according to priority, then by value.
4. Print to output.txt in FIFO order.

What my code actually does:

1. Except data from an input.txt file.
2. Sort according to minheap.
3. Queue according to priority, but only not by value.
4. Prints to output.txt in a strange order (prints the first queued, then starts at the last up).

Please refer to: http://www2.hawaii.edu/~fklam/Java/output.txt

What you are looking at is the output.  I've hardcoded the input for testing purposes:

DG1  aa1  1
DG2  bb2  1
DG3  cc3  1
DG4  dd4  1
               ^ represents priority (1 is the highest, 10 is the smallest), DG_ and _ _# are just Strings.

Each aa, bb, cc, dd will loop 100 times before jumping to the next letter.  

My problem is instead of this output (the one I want):

DG1  aa1  1
DG2  aa2  1
DG3  aa3  1
...
DG1  bb1  1
DG2  bb2  1
DG3  bb3  1
...
DG1  cc1  1
DG2  cc2  1
DG3  cc3  1
...
DG1  dd1  1
DG2  dd2  1
DG3  dd3  1
...

It prints (something slightly off):

DG1  aa1 1  <----- prints correctly
DG100  dd100 1   v----- here down is exact reverse of what I want.
DG99  dd99 1
DG98  dd98 1
...
DG100  cc100 1
DG99  cc99 1
DG98  cc98 1  
...
DG100  bb100 1
DG99  bb99 1
DG98  bb98 1  
...
DG100  aa100 1
DG99  aa99 1
DG98  aa98 1  
...

It prints the first aa1, then it prints the rest in exact reverse order!  Can't figure out what's wrong.  Am I dequeuing it in reverse?  

Other important codes:

1. http://www2.hawaii.edu/~fklam/Java/Output.java
2. http://www2.hawaii.edu/~fklam/Java/PriorityQueue.java
3. http://www2.hawaii.edu/~fklam/Java/DataGram.java

Thank you!!

-luna621 =^^=



luna621Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

objectsCommented:
welcome back :)

need to see ypur code
0
luna621Author Commented:
I was trying some testing, but that didn't work:

    private void minHeapify(int i) {
        int l = 2*i;
        int r = (2*i)+1;
        int smallest = -1;

        if ((priorityQ[i]==l) && (priorityQ[i]==r)) {
            if((priorityQ[l] < priorityQ[i]) && (l <= elemNum)) {
                smallest = l;
            } // end if
            else {
                smallest = i;
            } // end else
            if ((priorityQ[r] < priorityQ[smallest]) && (r <= elemNum)) {
                smallest = r;
            } // end if
            if (i != smallest) {
                swap(priorityQ[i], priorityQ[smallest]);
                minHeapify(smallest);
            } // end if
        } // end if
        else {
            if((priorityQ[l] < priorityQ[i]) && (l <= elemNum)) {
                smallest = l;
            } // end if
            else {
                smallest = i;
            } // end else
            if ((priorityQ[r] < priorityQ[smallest]) && (r <= elemNum)) {
                smallest = r;
            } // end if
            if (i != smallest) {
                swap(priorityQ[i], priorityQ[smallest]);
                minHeapify(smallest);
            } // end if
        } // end else
    } // END minHeapify


    private void goDown() {
        int count;
      for(count = (elemNum/2); count > 0; count--) {
          minHeapify(count);
        }
    }
0
Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

luna621Author Commented:
Okay, scrap that idea above...

I went through the code again.  I believe it heapifies correctly, but the problem is it doesn't keep track of the order of the elements that are being added.  Maybe that explains the reverse order??
0
luna621Author Commented:
Alrighty, more thinking...

I think I need to add something to the compareTo method that looks at both the priority as well as the header.  Help?
0
luna621Author Commented:
Simple example:

Want to insert: 3a, 2b, 1a, 2a, 1b, 1c, 2c into heap (where the number represents the priority -- 1 is the highest, and
                                                                           the letter represents a key value or "order").

Want the output from the priority queue to look like: 1a, 1b, 1c, 2a, 2b, 2c, 3a.

Question: Do I store in the minheap by order first, then sort by priority in the queue?
0
luna621Author Commented:
Hmm... it sorts the priorities correctly.  But, when the priorities are the same it doesn't sort by the order the element came in - no FIFO.
0
objectsCommented:
what does your compareTo() method look like?
0
luna621Author Commented:
Located in DataGram.java:

    public int compareTo(Object obj) {
        try {
            DataGram data = (DataGram)obj;
            if ( header < data.getHeader() && priority < data.getPriority() )
                return -1;
            else if ( header > data.getHeader() && priority > data.getPriority() )
                return 1;
            else if ( priority == data.getPriority() )
                return 1;
            else if ( priority > data.getPriority() )
                return -1;
             else
                 return 0;
        } // END try

        catch (ClassCastException ex) {
            return 0;
        } // END catch

    } // END compareTo


    public int comparePriority(Object obj) {
      try {
          DataGram data = (DataGram)obj;
          if ( priority < data.getPriority() )
            return -1;
          else if ( priority > data.getPriority() )
            return 1;
            else
             return 0;
      } // END try
      catch (ClassCastException ex) {
            return 0;
      } // END catch
    } // END comparePriority

    public int compareHeader(Object obj) {  
        try {
            DataGram data = (DataGram)obj;
            if ( header < data.getHeader() )
                return -1;
            else if ( header > data.getHeader() )
                return 1;
             else
                 return 0;
        } // END try
        catch (ClassCastException ex) {
            return 0;
        } // END catch
    } // END compareHeader

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

I have renamed the goDown method to minHeapify -- but since I did that, it's causing an index out of bounds error.  

These are the current codes: won't run --> no output.txt

1. http://www2.hawaii.edu/~fklam/Java/Output.java
2. http://www2.hawaii.edu/~fklam/Java/PriorityQueue.java
3. http://www2.hawaii.edu/~fklam/Java/DataGram.java



These are the original codes: runs, but sorts in a strange order --> output.txt to verfiy

1. http://www2.hawaii.edu/~fklam/Java/Output.java
2. http://www2.hawaii.edu/~fklam/Java/TestMHPQ.java
3. http://www2.hawaii.edu/~fklam/Java/DataGram.java
4. http://www2.hawaii.edu/~fklam/Java/output.txt
0
objectsCommented:
your compare should be something like:

public int compareTo(Object obj) {
   Datagram d = (Datagram) o;
   if (priority==d.priority) {
      return header - d.header;
   }
   return priority - d.priority;
}

     
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
luna621Author Commented:
Okay, let me try that...
0
luna621Author Commented:
Oh!!  It works!!  But I don't understand what your compareTo method does.  If the priorities were equal, it returns the header - the current header, else priority - current priority.  Could you explain the logic behind that?  Thank you!!!
0
objectsCommented:
compareTo() only needs to return a +ve value if greater than, and -ve if less than.
priority - d.priority will be =ve if priority is greater than d.priority etc.

the headers only need to be compared if the priorities are equal, if the priorities are not equal then u only need to compare priorities
0
luna621Author Commented:
ve??
0
luna621Author Commented:
Oh, do you mean and value greater than 0, and value less than 0 and equal 0 if they are equal?
0
objectsCommented:
+ve == positive
-ve == negative

sorry for the shorthand :)
0
luna621Author Commented:
Ah ha!  I see now.  Thank you very much for your help!  I'm glad it was just that one portion of my code that needed fixing.  You're a lifesaver!!! :D
0
objectsCommented:
Glad I could help :)
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.