Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Eclipse Projects » Standard Widget Toolkit (SWT) » Efficient tree or TreeItem navigation
Efficient tree or TreeItem navigation [message #454095] Sun, 17 April 2005 03:13 Go to next message
Eclipse UserFriend
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 #454160 is a reply to message #454095] Mon, 18 April 2005 13:59 Go to previous messageGo to next message
Grant Gayed is currently offline Grant GayedFriend
Messages: 2150
Registered: July 2009
Senior Member
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 #454168 is a reply to message #454160] Mon, 18 April 2005 17:31 Go to previous messageGo to next message
Eclipse UserFriend
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 Go to previous message
Eclipse UserFriend
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
>>>
>>
>>
>>
Previous Topic:How can I disable some TabItems in a TabFolder?
Next Topic:prevent Exit Event from Text
Goto Forum:
  


Current Time: Thu Mar 04 01:49:27 GMT 2021

Powered by FUDForum. Page generated in 0.03512 seconds
.:: Contact :: Home ::.

Powered by: FUDforum 3.0.2.
Copyright ©2001-2010 FUDforum Bulletin Board Software

Back to the top