I have checked in the version of TreeList that I had been working on (tidied up from your original code). The F�delung code looks interesting, so should probably replace the checked in code. Also, I think that it might be possible to have TreeList subclass AbstractLinkedList, which would be nice.
Stephen ----- Original Message ----- From: "J�rg Schm�cker" <[EMAIL PROTECTED]> > Stephen, > > I have added a fast implementation for iterator() and listIterator() using a > thing called "F�delung" in German. Please copy the Apache license into the > files. > > Thanks, > > Joerg > > -----Original Message----- > From: Stephen Colebourne [mailto:[EMAIL PROTECTED] > Sent: Wednesday, May 05, 2004 1:46 AM > To: J�rg Schm�cker > Cc: Jakarta Commons Developers List > Subject: Re: [collections] TreeList > > > The default iterator is picked up from AbstractList. For each next() it uses > get(index) on the list to retrieve the element. As you might imagine, > ArrayList can easily beat this with a dedicated implementation going > straight to the array. > > The two possible solutions are to have each node in the tree refer to its > parent, or to have the iterator dynamically use an ArrayStack to build up > the parent structure as it navigates it. I favour the latter if possible. > > Stephen > > ----- Original Message ----- > From: "J�rg Schm�cker" <[EMAIL PROTECTED]> > > Can you tell me how the iterator is implemented? Currently, I have not > > implemented such forward/backward linking to improve iteration > performance. > > > > Regards, > > > > Joerg > > > > -----Original Message----- > > From: Stephen Colebourne [mailto:[EMAIL PROTECTED] > > Sent: Monday, May 03, 2004 4:00 PM > > To: Jakarta Commons Developers List > > Cc: J�rg Schm�cker > > Subject: Re: [collections] TreeList > > > > > > Thanks. Forwarded to commons-dev for reference. > > > > I will be checking the class in shortly. It does need a proper iterator > > implementation, as the default is slow. This can be added later though. > > > > Stephen > > > > ----- Original Message ----- > > From: "J�rg Schm�cker" <[EMAIL PROTECTED]> > > > Sorry for the hassle. I am very happy to contribute the code. Next > time > > I > > > will contribute with the standard Apache licence. > > > > > > I am hoping that I'll have the time to finish the tree-based class to > > > implement a ordered subset of a set witht the same order and fast > > insertion. > > > That was the original reason I started implementing it as a tree. The > idea > > > that it will be much faster came to me only during the development. > Don't > > > know if it is a standard algorithm, but I did not copy it anywhere. > > > AVL-Trees should not be a problem. > > > > > > Regards, > > > > > > Joerg > > > > > > -----Original Message----- > > > From: Stephen Colebourne [mailto:[EMAIL PROTECTED] > > > Sent: Sunday, May 02, 2004 11:34 AM > > > To: J�rg Schm�cker > > > Subject: Re: [collections] TreeList > > > > > > > > > You're essentially stating that you haven't blatently ripped the code > off > > > from somewhere else (except standard computer science algorithm books). > > Also > > > that, if it was written for a company, that the company doesn't claim > any > > > ownership. > > > > > > IANAL, but my understanding is that legally you are donating a COPY of > > your > > > code to Apache that will then be OWNED by Apache. Both you and Apache > can > > > then do as they please with the code - in Apache's case release it with > > > commons collections. > > > > > > Effectively, you are saying that you COULD sign > > > http://www.apache.org/licenses/#clas without having to go through the > > hassle > > > of doing so. > > > > > > BTW, I am only having to mail you this because you didn't submit your > > > original code with an Apache licence. If you had, I would have taken > that > > as > > > the sign of donation! > > > > > > Stephen > > > > > > ----- Original Message ----- > > > From: "J�rg Schm�cker" <[EMAIL PROTECTED]> > > > > Stephen, > > > > > > > > Could you give me a reason, why I should not be in the position to > > donate > > > > the class? I don't think there is one but I just want to make sure. > > > > > > > > Joerg > > > > > > > > -----Original Message----- > > > > From: Stephen Colebourne [mailto:[EMAIL PROTECTED] > > > > Sent: Saturday, May 01, 2004 11:57 PM > > > > To: [EMAIL PROTECTED] > > > > Cc: Jakarta Commons Developers List > > > > Subject: [collections] TreeList > > > > > > > > > > > > Joerg, > > > > I have been looking at integrating your tree based list into commons > > > > collections. Can you confirm that you are in a position to donate the > > > class > > > > to Apache please? A reply to confirm this will allow its inclusion. > > > > > > > > Stephen > --------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
