On Thu, Oct 30, 2008 at 8:22 AM, Daniel Cheng <[EMAIL PROTECTED]> wrote: > On Thu, Oct 30, 2008 at 4:18 AM, Sam <[EMAIL PROTECTED]> 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)." >> >> - Therefore it only contains a sorted tree, not a hashtable, and is >> not suitable for this purpose. > > I means this one: > private UpdatableSortedLinkedList<FMSBoard> mBoardsSorted = new > UpdateableSortedLinkedList<FMSBoard>(); > > This is just a sorted list, not a hashtable. > Were you talking about some other code?
And we have java.util.TreeMap too. Red-Black tree may be less optimal, but I really *hate* the idea of using DoublyLinkedList and its friends. It is a ugly hack for quick iteration of list in the early days, and can be replaced LinkList using ListIternator in most cases. - The performance benefit is marginal. - Custom code like these make casual contributor less likely. - The class was created in 2005 era, and I can still find bugs in recent months. Keep it out from the new code if you can. IF you REALLY HAVE to use it, PLEASE add a junit test for all new method you created. >> 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. > > Just keep a list and hash table. > UpdatableSortedLinkedList have worse case O(n) add / remove time. > >> 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. > > I tried to do this, but it need touching some client code. > It's not a good idea to do so before db4o merge. > >> 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. > _______________________________________________ Devl mailing list [email protected] http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
