On Fri, 16 Mar 2012 11:36:08 +0100 Felipe Monteiro de Carvalho <[email protected]> wrote:
> Can I add a routine to access the AvgLvlTree as an array? To make it a > better substitute to TFPList in objects which offer an indirect > interface to the internal list, such as TLazAccessibleObject. > > My idea is defining: > Index zero = Tree.FindLowest > Indez Count-1= Tree.FindHighest > > On each access store the last accessed node and if the next call wants > a node index=oldindex+1 or -1 then just use: > > Tree.FindSuccessor(Node) > Tree.FindPrecessor(Node) > > Because almost always I use the array access only to iterate in a loop. > > Non-ordened access ofcourse would be slow because it would require a > loop till the index is found. I implemented a TIndexedAVLTree. This allows log(n) access to items via the position. For example to get the fourth node: Node:=Tree[3]; It has the above caching mechanism to speed up common queries. So, running with a "for i:=0 to Tree.Count-1 do" needs O(n). Otherwise it is a normal AVL tree, so insertion, deletion and finding takes O(log(n)). I also added a second enumerator to TAvgLvlTree to run from highest to lowest and I removed the nodememmanager making it is easier to use with threads. Mattias -- _______________________________________________ Lazarus mailing list [email protected] http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
