#619 Made TreeView stable

Merged, abandoned or rejected pull requests are moved here to clear the main Pull Requests forum.
User avatar
DeepSOIC
Veteran
Posts: 7896
Joined: Fri Aug 29, 2014 12:45 am
Location: used to be Saint-Petersburg, Russia

Re: #619 Made TreeView stable

Post by DeepSOIC »

Just having some fun :P
chicken-egg-tree.png
chicken-egg-tree.png (116.4 KiB) Viewed 2747 times
User avatar
DeepSOIC
Veteran
Posts: 7896
Joined: Fri Aug 29, 2014 12:45 am
Location: used to be Saint-Petersburg, Russia

Re: #619 Made TreeView stable

Post by DeepSOIC »

realthunder wrote:The cyclic check only happens when a free item (i.e. an item at document root) is newly claimed, which already has children. The check needs to visit all its children. That's the only case requiring a check.
Maybe it can be made faster by going the other way around? i.e. when adding an object as child of something, and withdrawing it from root, look up the ultimate parent of something and check if it is the child being added? This way, the performance penalty is proportional to depth of tree, which isn't going to be too big anyway?
User avatar
DeepSOIC
Veteran
Posts: 7896
Joined: Fri Aug 29, 2014 12:45 am
Location: used to be Saint-Petersburg, Russia

Re: #619 Made TreeView stable

Post by DeepSOIC »

realthunder wrote:The cyclic check only happens when a free item (i.e. an item at document root) is newly claimed, which already has children. The check needs to visit all its children. That's the only case requiring a check. We'd be creating new items (without children obviously) for all other cases. So, I think the performance impact should be limited.
So as far as I understand, it's pretty rare, so can be ignored.
realthunder
Veteran
Posts: 2190
Joined: Tue Jan 03, 2017 10:55 am

Re: #619 Made TreeView stable

Post by realthunder »

:lol:
DeepSOIC wrote:Maybe it can be made faster by going the other way around? i.e. when adding an object as child of something, and withdrawing it from root, look up the ultimate parent of something and check if it is the child being added? This way, the performance penalty is proportional to depth of tree, which isn't going to be too big anyway?
I doubt there is any shortcut. When reparenting the root item, you'll never know what's in its children until a full visit.

The performance impact will only kick in when it needs to visit large number of children and find it's actually fine, or only find the cycle at the near end. I'd expect it may have impact on loading large document. Not sure though, if the parent children relationship is saved and not inferred during loading, and loaded in order of parent first, then it should be fine too. But, even if it is the worst, that it has to visit each children recursively (that's factorial n! maybe?), the checking time won't be significant comparing to restoring actually geometry data.

So yeah, I guess it should be fine.
Try Assembly3 with my custom build of FreeCAD at here.
And if you'd like to show your support, you can donate through patreon, liberapay, or paypal
User avatar
DeepSOIC
Veteran
Posts: 7896
Joined: Fri Aug 29, 2014 12:45 am
Location: used to be Saint-Petersburg, Russia

Re: #619 Made TreeView stable

Post by DeepSOIC »

realthunder wrote:visit each children recursively (that's factorial n! maybe?)
n! !?? If so, it's awful, since factorial of just 13 is already over 1G. And a factorial of 20 will take about 100 years to traverse.
realthunder
Veteran
Posts: 2190
Joined: Tue Jan 03, 2017 10:55 am

Re: #619 Made TreeView stable

Post by realthunder »

DeepSOIC wrote:
realthunder wrote:visit each children recursively (that's factorial n! maybe?)
n! !?? If so, it's awful, since factorial of just 13 is already over 1G. And a factorial of 20 will take about 100 years to traverse.
Oops, I mean 1+2+3..+n, not multiple, n(n+1)/2. This is the case where all child items are loaded before its parent.
Try Assembly3 with my custom build of FreeCAD at here.
And if you'd like to show your support, you can donate through patreon, liberapay, or paypal
User avatar
DeepSOIC
Veteran
Posts: 7896
Joined: Fri Aug 29, 2014 12:45 am
Location: used to be Saint-Petersburg, Russia

Re: #619 Made TreeView stable

Post by DeepSOIC »

realthunder wrote:Oops, I mean 1+2+3..+n, not multiple, n(n+1)/2.
Haha, that's just O(n^2), which is a heaven of a difference compared to the factorial :lol: .

I just gave it compound->explode->compound->... torture again, and with tree potentially expandable to about 4 gigaleaves, I had no noticeable slowdown.
User avatar
bernd
Veteran
Posts: 12849
Joined: Sun Sep 08, 2013 8:07 pm
Location: Zürich, Switzerland
Contact:

Re: #619 Made TreeView stable

Post by bernd »

Just tested the branch on Debian Jessie and played a bit. Wow thats cool. The objects in TreeView do no longer jump around :D :D
User avatar
NormandC
Veteran
Posts: 18587
Joined: Sat Feb 06, 2010 9:52 pm
Location: Québec, Canada

Re: #619 Made TreeView stable

Post by NormandC »

Hello,

Would you please have a look at this topic and tell me if I'm making wrong assumptions? In which case I apologize. :oops:

Re: Odd behaviour with Part Design Boolean/Part Fusion operations https://forum.freecadweb.org/viewtopic. ... 46#p168246

tl;dr: bringing an inactive Body into an active one using a Boolean operation feature seems to create a second instance of the "imported" Body. IMO this is not desired, and I don't remember seeing this behaviour before. I thought this might be a side effect of the treeview changes, but I am not a developer.

As for the two other issues I mention, I doubt they are related.

I'll try to compile FreeCAD from a prior commit to test...

Thanks!
User avatar
DeepSOIC
Veteran
Posts: 7896
Joined: Fri Aug 29, 2014 12:45 am
Location: used to be Saint-Petersburg, Russia

Re: #619 Made TreeView stable

Post by DeepSOIC »

NormandC wrote:tl;dr: bringing an inactive Body into an active one using a Boolean operation feature seems to create a second instance of the "imported" Body. IMO this is not desired,
This is desired IMO, because visibility of body used for boolean operation does not depend on visibility of the body that contains the Boolean operation. But according to code, Part shouldn't claim the used body as child anymore, so there is likely a bug somewhere.
Post Reply