Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Naming change for NodeIndex #208

Open
Tracked by #194 ...
plafer opened this issue Oct 30, 2023 · 2 comments
Open
Tracked by #194 ...

Naming change for NodeIndex #208

plafer opened this issue Oct 30, 2023 · 2 comments
Milestone

Comments

@plafer
Copy link
Contributor

plafer commented Oct 30, 2023

I find the naming around NodeIndex confusing (i.e. "index", "depth" and "value"). Currently, every time I encounter a NodeIndex, I have to remind myself e.g. what value is, which is distracting.

I can currently think of 2 alternatives for renaming.

Reusing matrix terminology

We could reuse matrix terminology, so the renaming would look like:

  • NodeIndex -> NodeCoordinate or NodeCoord
  • depth -> i
  • value -> j

I'm not really against keeping NodeIndex, although I typically think of "indices" as being 1-dimensional, and "coordinates" as being 2D+.

Changing only value

A less important change would only change value.

  • NodeIndex -> NodeCoordinate, NodeCoord or NodeIndex
  • depth -> depth
  • value -> width

depth makes it clear that the "y coordinate" starts from the top, and width tries to capture "x coordinate" (from how we usually use "width" with a rectangle).

The depth/width terminology is probably more descriptive, so I would personally go in that direction.

@hackaugusto
Copy link
Contributor

hackaugusto commented Nov 1, 2023

I personally find the matrix terminology harder to understand.

I have been using the following terminology:

  • depth: 0-indexed depth, from top to bottom (useful to describe a walk from the root)
  • level: 0-indexed level, from bottom to top (useful to describe MMR, because the level is consistent after tree merges, whereas depth is not)
    • note: this is the opposite of what I see in the literature. level is usually from top to bottom, but since the codebase already used the term depth I used this meaning. We could use something else, like layer.
  • position: 0-index leaf position, from left-to-right

Besides the NodeIndex we also have the InOrderIndex, and the Mmr structure would benefit from a PostOrderIndex (currently this logic is burried inside the Mmr, the code would be more readable if isolated). These indexes are named after the walk they perform. In the literature the NodeIndex performs a level order traversal, so perhaps it would be best to call it LevelOrderIndex

I also find it confusing that our code doesn't have an enum to determine the orientation of a tree walk when checking bits. Something like enum Orientation { Left, Right } would make the tree traversal more readable in some places.

To summarize the above, I think we should:

  • Add a PostOrderIndex
  • Rename NodeIndex to LevelOrderIndex
  • Use position instead of pos / value for the leaf position
  • Rename level to layer
  • Add an Orientation enum to clarify the code

@bobbinth
Copy link
Contributor

bobbinth commented Nov 1, 2023

For NodeIndex specifically, to me also the new terminology does not seems like an improvement. But I agree that naming can be improved.

I don't see an issue with the depth name, but agree with @hackaugusto that we should probably rename value to position. Then, current NodeIndex is a combination of depth, which specifies the layer (or level) and position, which specifies the location of the node in that layer.

I think other changes that @hackaugusto mentioned should go into a different issue.

@bobbinth bobbinth added this to the v0.8 milestone Jan 5, 2024
@bobbinth bobbinth modified the milestones: v0.8, v0.9 Feb 13, 2024
@bobbinth bobbinth modified the milestones: v0.9, v0.10.0 Mar 24, 2024
@bobbinth bobbinth modified the milestones: v0.10.0, v0.11.0 Oct 18, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
Status: No status
Development

No branches or pull requests

3 participants