On Wednesday 29 October 2008 20:18, Sam wrote: > > > On Wed, Oct 29, 2008 at 10:18 PM, <[EMAIL PROTECTED]> wrote: > > > Author: xor > > > Date: 2008-10-29 14:18:43 +0000 (Wed, 29 Oct 2008) New > > Revision: 23170 > > > > > > Modified: > > > trunk/plugins/FMSPlugin/WoT/FMSMessageManagerWoT.java > > > Log: > > > Implementation. Toad, please make the > > UpdatableSortedLinkedList use generics and take a Comparator maybe. > > > > You may use java.util.TreeSet / SortedSet. > > > > UpdatableSortedLinkedList contain some ugly hack, impossible > > to generify without interface change. > > > > TreeSet: "This implementation provides guaranteed log(n) time cost > for the basic operations (add, remove and contains)."
Trees can be reasonably fast in practice due to locality (caching) issues ... granted, red-black trees have a very low fanout so are probably quite slow ... > > - Therefore it only contains a sorted tree, not a hashtable, and is > not suitable for this purpose. > We need really quick checking whether a message exists so we need > a hashtable. Further, the messages will usually be displayed sorted > by their date, so a sorted list is also needed. > > If anyone wants to clean up the UpdatableSortedLinkedList, feel free > to do so :) I will do it after I'm finished with FMS but not right now. > > By the way: A sorted linked list should be quiet fast for insertions > of new messages because usually old messages are downloaded before > new ones. So deep walks into the list will probably not happen often.
pgp9JLMMOgGLw.pgp
Description: PGP signature
_______________________________________________ Devl mailing list [email protected] http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
