Okay. I added the patch with a few changes. Essentially you had made some methods protected when they were previously private. I changed them back to private.
I also readded a few constructors that were in the last version (the ones that took a boolean indicating whether it was a maximum or minimum heap). This was mainly to minimize the change in interface between the two versions. I also added you as an author tag. Anyways could you download it from CVS and make sure I didn't stuff anything up ? ;) Unfortunately we don't have a unit test for the PriorityHeap and we really should have one. On Thu, 8 Nov 2001 11:58, Chad Stansbury wrote: > 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" <[EMAIL PROTECTED]> > 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]> -- Cheers, Pete --------------------------------------------------- "It is easy to dodge our responsibilities, but we cannot dodge the consequences of dodging our responsibilities." -Josiah Stamp --------------------------------------------------- -- To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
