Attached are the files that I have patched to allow the priority queue, synchronized priority queue, and binary heap to accept Objects rather than Comparables. Note that these patches do not retain backwards compatibility. You will find that the following major implementation changes were made:
1. All references to Comparable have been changed to Object 2. I have substituted a Comparator for the isMinHeap parameter. The BinaryHeap now has two constants - MAX_COMPARATOR and MIN_COMPARATOR. These comparators assume that the elements stored in the heap implement the Comparable interface. If you don't specify a comparator in the constructor, it defaults to MIN_COMPARATOR, thereby yielding a min heap. If you want a max heap, you specify MAX_COMPARATOR in the constructor. You can also specify a custom comparator if you don't want to rely on the content's natural ordering. 3. I have consolidated the separate percolateDown/Up Min and Max heap methods. Instead there is now just a single percolateDownHeap and percolateUpHeap method that utilizes the comparator to determine the ordering. 4. I have made 2 performance related changes: 4a. I have removed a redundant divide and multiply statement in the while loop for the two percolate methods. This resulted in a 4% speed increase. 4b. I have changed 'hole * 2' and 'hole / 2' to 'hold << 1' and 'hold >> 1', respectively. I would have thought the java compiler would perform this optimization for me, but alas, jdk 1.3.1 does not appear to do so. Anyhow, this seems to increase the speed of the insert operation by a non-trivial amount. Unfortunately, the new implementation degrades the pop performance somewhat. I have seen about a 9% performance hit when inserting and popping 2,000,000 random Integers into the heap (14,971 ms for the old implementation vs. 16,414 ms using the new implementation). This performance degradation can be attributed to the additional method call and cast involved with using a Comparator rather than directly invoking the element's compareTo method. All performance measurements were recording on a 1.4 GHz P4 running jdk1.3.1_01 on Win2K. ----- Original Message ----- From: "Peter Donald" <[EMAIL PROTECTED]> To: "Avalon Developers List" <avalon-dev@jakarta.apache.org> Sent: Wednesday, November 07, 2001 7:49 AM Subject: Re: [Excalibur] PriorityQueue & BinaryHeap proposal > On Thu, 8 Nov 2001 01:04, Chad Stansbury wrote: > > Okay - here's the problem. The current BinaryHeap interface expects a > > Comparable for it's public interface. In order to maintain backwards > > compatibility I must either: > > > > 1. Add new public methods to the BinaryHeap class (e.g., insertObject, > > peekObject, popObject) and change the insert, peek, and pop methods to > > invoke these new methods, or > > 2. I can create a new BinaryObjectHeap class and have the BinaryHeap class > > act as a wrapper class. > > > > I am also wondering how I would modify the PriorityQueue interface w/o > > breaking backwards compatibility... > > > > Any suggestions would be appreciated. > > I am not sure we need to maintain 100% backwards compatability in this case. > peek() and pop() methods in al cases that I use them and have seen them used > will actually need to be cast to something else anyways. Retrieving a > Comparable from heap is rarely the aim and come to think of it I think it was > probably a mistake to return Comparables rather than Objects ;) > > For insert there will need to be backwards compatability because people will > use that to pass in comparables. However you should be ab;le to get backwards > compatability with this by just checking the type passed in (if Comparable do > X, else do Y) and converting parameter to Object. > > -- > Cheers, > > Pete > > -------------------------------------------------------------- > "Science is like sex: sometimes something useful comes out, > but that is not the reason we are doing it" -- Richard Feynman > -------------------------------------------------------------- > > -- > To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> > For additional commands, e-mail: <mailto:[EMAIL PROTECTED]> >
BinaryHeap.java
Description: Binary data
PriorityQueue.java
Description: Binary data
SynchronizedPriorityQueue.java
Description: Binary data
-- To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
