Tree with parent pointers VS zippers

[stefnotch]

I think zippers are neater, see also https://blog.yaakov.online/red-green-trees/

[stefnotch]

82c2345 still has the Tree with parent pointers design

[stefnotch]

Zippers are nice so far

[stefnotch]

See also #20 and readme

[stefnotch]

Everyone uses zippers or red-green trees

[stefnotch]

Neato, we could have constant time comparisons for zipper equality (given non-pathological trees)
Though a simple very nested fraction gives us an exponential growth of the number so that's not so cool in the worst case. We can survive like 32 nested fractions.

// get a unique value for a given zipper
current = this
zipperValue = this.indexInParent + 1; // 0 equals end, so we pretend there's an unreachable child at the far left
while(this.parent != null) {
  current = this.parent
  zipperValue = zipperValue * (current.length+1) + current.indexInParent
}
return zipperValue; // wait wtf is that a unique encoding?


// turn the value back into a zipper
fromZipperValue(zipperValue, root) {
  current = root
  while(zipperValue > 0) {
    index = (zipperValue mod (current.length+1)) - 1;
    zipperValue = floor(zipperValue / (current.length+1))
    current = current.children[index]
  }
}

There's a smarter way of doing it, see #30

[stefnotch]

Now I'm thinking about redesigning this in Rust.
API comes first, and the internal structure should be an implementation detail. I want the zippers to be the public API.

[stefnotch]

https://michaeldadams.org/papers/scrap_your_zippers/

[stefnotch]

Having parent references (including the zipper or red-green node types) is much easier when you have a homogeneous tree. Then you don't have to deal with cases like "this table cell node can only have a table as its parent". (See also #21 (comment) )

As such, not giving a table some funny "table-row" and "table-cell-elements" makes it easier to deal with.
Similarly, rows can have any child they want. So the Row<T> design gets dropped.