Hello,

Is it possible to iterate through all items in a TAvgLvlTree? I couldn't find an easy method for doing that.

thanks,

Hello, 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

Mattias

You might also find the following useful:

Tree.FindLowest
Tree.FindHighest
Tree.FindSuccessor(Node)
Tree.FindPrecessor(Node)

Mattias

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?

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? What is your opinion -- did it work well for you?
In particular, I am interested in the memory management issues -- how is enumerator instance freed in your example?

Finally, do you feel the need for the remaining extension proposal -- namely, getting the index from enumerator?

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.

Finally, do you feel the need for the remaining extension proposal -- namely, getting the index from enumerator?

An index is hardly needed for an AVL tree.

Mattias

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

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.

Ouch. This is exactly what enumerators are were designed to avoid. Maybe convert TLazAccessibleObject to expect enumerable instead?

And don't forget to invalidate the index on any node operation
(*change/add/remove)

But I would try to avoid that.

If you need that, synedi has an AVL tree which can be used (abused) to keep track of the position/index. It will need minor modifications, as it currently stores the data, as difference to the previous node, rather than absolute value

Alexander Klenin wrote

Ouch. This is exactly what enumerators are were designed to avoid. Maybe convert TLazAccessibleObject to expect enumerable instead?

Could you be more specific as to what type you are talking about and would it look like a routine in TLazAccessibleObject which offers the iteration functionality?

Can I add a routine to access the AvgLvlTree as an array?

No.

A tree in general has no first or 0 element.

If you want to iterate through all nodes, use an enumerator or the findlowest+findsuccessor.

If you want a hybrid of array and avl tree use a differential tree. Martin has implemented a specific one. Maybe a descendant of TAvgLvlTree can be implemented as a generic one.

That's one specific use case.
For other examples how avl trees can be used see the hundreds of places in the IDE.

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

Keep the last node. It can be found in O(logn).
Why use an integer to refer to an element?

Mattias

Mattias Gaertner wrote

Why use an integer to refer to an element?

Backwards compatibility. I have multiple libraries which offer an interface to an internal list and I designed all to offer array-access because this is convenient and is how TFPList works. I don't want to break backwards compatibility, so if this can't be added to the AVL tree I will need multiple copies of the AVL tree 2 array code.

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

Mattias Gaertner wrote

I implemented a TIndexedAVLTree.

Great! thanks a lot =)

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.