egui_dock icon indicating copy to clipboard operation
egui_dock copied to clipboard

Replace binary tree to allow more that two splits per node

Open LennysLounge opened this issue 6 months ago • 7 comments

Related to #147

Replaces the internal binary tree with a tree that allows a arbitrary amount of splits per node.

LennysLounge avatar Dec 30 '23 18:12 LennysLounge

@Adanos020 In this first step i wanted to only remove any dependencies the code might have on the binary tree. As a result of this, most methods on NodeIndex are not really possible and have been move into the tree itself.

The Tree still behaves like a binary tree but the layout of the nodes in the Vec is free. This should make it easier to implement the actual feature later.

LennysLounge avatar Dec 30 '23 18:12 LennysLounge

@LennysLounge Hey, thanks for giving it a stab. I noticed that sometimes when you drag a tab out of a window surface and dock it somewhere else, the application panics on window_surface.rs, line 77. Turns out that it in the statement above, focused_leaf() returns an Empty node.

Since we're not operating on a binary tree anymore, maybe we should phase out Node::Empty completely, which should also fix this panic. Does that sound right?

Adanos020 avatar Jan 07 '24 14:01 Adanos020

Yes, Node::Empty only exists to fill out the empty spaces in the binary tree. No binary tree, no need for empty nodes. I was hesitant to do it at first since i wanted to keep these changes as small as possible. However, removing Node::Empty has to happen at some point anyway and it makes the code easier to understand if we remove it now.

That Bug you mentioned bother me though. I encountered a similar bug at the same place before and thought i had fixed it. Apparently not. And i cant replicate it from your description either. If i remove Node::Empty i might end up fixing the bug too but that doesnt sound very robust if you know what i mean. If you have some reliable way to replicated it i can take a look to fix it.

LennysLounge avatar Jan 07 '24 21:01 LennysLounge

I think replacing the underlying data structure is already a very radical change, so going all in and removing Node::Empty makes sense. In 0.x releases we're free to make breaking changes like this without violating SemVer. :slightly_smiling_face:

As for the bug, I found very a consistent reproduction:

  1. Run the simple example
  2. Pull any tab A out into a window
  3. Pull any other tab B and dock it in the previously created window, to the right of A
  4. Pull A out of the window and dock it anywhere in the main view
  5. Observe the application panicking

Adanos020 avatar Jan 07 '24 21:01 Adanos020

Found the bug and fixed it. There was a special case when removing a node where a sibling node was moved. If that sibling node was focused, the focus was now on a stale node and could cause the panic. The focus is now correctly updated.

LennysLounge avatar Jan 08 '24 18:01 LennysLounge

I successfuly removed Node::Empty. However that highlights a new issue. previously the Tree::iter and Tree::iter_mut methods simply iterated over the nodes vector with the empty nodes. Now there is no way to see that a node has been removed from the tree and you are looking at stale data.

I briefly tried to replace the iterator with one that only iterates over valid nodes in breadth first order but hit a blocker with the mutable iterator. I dont really know how to continue with that problem.

LennysLounge avatar Jan 08 '24 18:01 LennysLounge

I see, I can take a look if there's a way to solve this.

Adanos020 avatar Jan 08 '24 18:01 Adanos020