Sign in Join

Live chat for Free Pascal, Lazarus, Delphi and every Pascal programmer.

Mailing lists / fpc-devel / 2012-03

Re: How to iterate through a TAvgLvlTree

4 messages · 4 people · –

Reply by email Subscribe to this list Your subscription

Read-only archive. Use j and k to move between messages.

Alexander Klenin
Mattias Gaertner wrote 32 lines
On Fri, 16 Mar 2012 20:47:15 +1100 Alexander Klenin wrote: > On Fri, Mar 16, 2012 at 19:36, Mattias Gaertner > wrote: > >> Is it possible to iterate through all items in a TAvgLvlTree? I > >> couldn't find an easy method for doing that. > > > > for Node in Tree do > > By the way, I think you are using TAvgLvlTree rather often, > so did you ever wanted another traversal order besides the default one? Of course. > You replaced my proposal of extending the for..in loop on the wiki > by an example implementing it using the current syntax. > > So, I am interested -- did you actually use you implementation? Yes. > What is your opinion -- did it work well for you? Yes. > In particular, I am interested in the memory management issues -- > how is enumerator instance freed in your example? If you mean the fpc enumerators: They are freed by compiler magic after the loop.

So perhaps this fact should be added to the manual? http://www.freepascal.org/docs-html/ref/refsu50.html

Alexander S. Klenin

Reply by email

Felipe Monteiro de Carvalho
to Alexander Klenin

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.

Felipe Monteiro de Carvalho

Reply by email

Marc Weustink
to Felipe Monteiro de Carvalho
Felipe Monteiro de Carvalho wrote 15 lines
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.

Lazarus has a TMap implementations where a AvgLvlTree is used for looking up items and has a own AvgLvlTreeItem which is a double linked list so items can be iterated.
Tree.FindSuccessor(Node)/Tree.FindPrecessor(Node) can cause a lot of nodes traveled.

Marc

Non-ordened access ofcourse would be slow because it would require a loop till the index is found.

Reply by email

Mattias Gaertner
to Marc Weustink

Marc Weustink hat am 22. März 2012 um 10:31
geschrieben:

Show quoted text 22 lines
Felipe Monteiro de Carvalho 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. Lazarus has a TMap implementations where a AvgLvlTree is used for looking up items and has a own AvgLvlTreeItem which is a double linked list so items can be iterated. Tree.FindSuccessor(Node)/Tree.FindPrecessor(Node) can cause a lot of nodes traveled.

True. But practically it hardly matters due to the AVL feature of the tree.

Half of the time it will travel 1 node.
1/4 of the time it travels 2 nodes.
1/8 it travels 3 nodes.
1/16 it travels 4 nodes.
...

That means in a tree with 1 million nodes there is exactly one case where it travels 20 nodes, two cases where it travels 19 nodes, ... and 500.000 nodes where it travels 1 node.

On average it travels 2 nodes.

Iterating an AVL tree needs 2*n steps.

Show quoted text 6 lines
Marc > > Non-ordened access ofcourse would be slow because it would require a > loop till the index is found.

This is where TIndexedAVLTree is better. It needs at most log(n).

Mattias

Reply by email