| Efficient tree or TreeItem navigation [message #454095] |
Sun, 17 April 2005 03:13  |
Eclipse User |
|
|
|
Originally posted by: doug-list.threepenny.net
Given a TreeItem from a tree (e.g. after calling getSelection()), is
there an efficient way to find the next item in the tree?
The only method I can see is to call getParent().getItems() and walk the
array to find the index of the current item and then return the next in
the array.
That'll work--but horribly slow, as in O(n) for something which I think
should be O(1). Does SWT support something faster or do I have to roll
my own solution to this?
Doug
|
|
|
|
| Re: Efficient tree or TreeItem navigation [message #454168 is a reply to message #454160] |
Mon, 18 April 2005 17:31  |
| Eclipse User |
|
|
|
Originally posted by: bob.objfac.com
Yes, but does TreeItem.indexOf(TreeItem) walk the children array?
If you really care about the speed (probably the only cases where you
should are ones you can't fix; the linear search is built into TreeItem)
you could keep a HashMap nextItem of TreeItem->TreeItem. This would be
constant time, linear storage. You would of course need to maintain the
nextItem table in synch with inserts/deletes. Insert is easy; to make
delete constant time you'd need a previous link of some sort. Then you'd
have a bug or two to fix...
Bob Foster
Grant Gayed wrote:
> Hi Doug,
>
> There is not api for this, so you'll need to compute it. Note that API
> TreeItem.indexOf(TreeItem) was added to the 3.1 stream recently, which gets
> you out of walking the parent item's array of children.
>
> Grant
>
> "Doug Pearson" <doug-list@threepenny.net> wrote in message
> news:d3skn7$fgb$1@news.eclipse.org...
>
>>Given a TreeItem from a tree (e.g. after calling getSelection()), is
>>there an efficient way to find the next item in the tree?
>>
>>The only method I can see is to call getParent().getItems() and walk the
>>array to find the index of the current item and then return the next in
>>the array.
>>
>>That'll work--but horribly slow, as in O(n) for something which I think
>>should be O(1). Does SWT support something faster or do I have to roll
>>my own solution to this?
>>
>>Doug
>>
>
>
>
|
|
|
| Re: Efficient tree or TreeItem navigation [message #454169 is a reply to message #454168] |
Mon, 18 April 2005 17:52 |
| Eclipse User |
|
|
|
Originally posted by: doug-list.threepenny.net
Bob & Grant,
Thanks for the comments. What Bob suggests is basically what I went
with (I used setData("prev") and "next" to link the nodes of the tree
together as they're created).
It's good to know they're adding something to the API to help with this
in the future because what I'm doing is definitely clumsy and
potentially prone.
Anyway, thanks for confirming that there's no way to avoid what I'm
doing right now.
Doug
Bob Foster wrote:
> Yes, but does TreeItem.indexOf(TreeItem) walk the children array?
>
> If you really care about the speed (probably the only cases where you
> should are ones you can't fix; the linear search is built into TreeItem)
> you could keep a HashMap nextItem of TreeItem->TreeItem. This would be
> constant time, linear storage. You would of course need to maintain the
> nextItem table in synch with inserts/deletes. Insert is easy; to make
> delete constant time you'd need a previous link of some sort. Then you'd
> have a bug or two to fix...
>
> Bob Foster
>
> Grant Gayed wrote:
>
>> Hi Doug,
>>
>> There is not api for this, so you'll need to compute it. Note that API
>> TreeItem.indexOf(TreeItem) was added to the 3.1 stream recently, which
>> gets
>> you out of walking the parent item's array of children.
>>
>> Grant
>>
>> "Doug Pearson" <doug-list@threepenny.net> wrote in message
>> news:d3skn7$fgb$1@news.eclipse.org...
>>
>>> Given a TreeItem from a tree (e.g. after calling getSelection()), is
>>> there an efficient way to find the next item in the tree?
>>>
>>> The only method I can see is to call getParent().getItems() and walk the
>>> array to find the index of the current item and then return the next in
>>> the array.
>>>
>>> That'll work--but horribly slow, as in O(n) for something which I think
>>> should be O(1). Does SWT support something faster or do I have to roll
>>> my own solution to this?
>>>
>>> Doug
>>>
>>
>>
>>
|
|
|
Powered by
FUDForum. Page generated in 0.03074 seconds
] 
Search
Help
Register
Login
Home
