Hashtree

[Licini]

Adding HashTree to compare changes on data structrues. For example:

from compas.datastructures import HashTree

print("\nCOMPARE DICTS:")
tree1 = HashTree.from_dict({"a": {"b": 1, "c": 3}, "d": [1, 2, 3], "e": 2})
tree2 = HashTree.from_dict({"a": {"b": 1, "c": 2}, "d": [1, 2, 3], "f": 2})

tree1.print_hierarchy()
tree2.print_hierarchy()

tree2.print_diff(tree1)

print("\nCOMPARE MESH CHANGE:")

from compas.datastructures import Mesh

mesh = Mesh.from_polyhedron(4)
tree1 = HashTree.from_object(mesh)
mesh.vertex_attribute(0, "x", 1.0)
tree2 = HashTree.from_object(mesh)
tree1.print_hierarchy()
tree2.print_hierarchy()
tree2.print_diff(tree1)

COMPARE DICTS:
└── ROOT @ 4cd56
    ├── .a @ c16fd
    │   ├── .b:1 @ c9b55
    │   └── .c:3 @ 518d4
    ├── .d:[1, 2, 3] @ 9be3a
    └── .e:2 @ 68355
└── ROOT @ fbe39
    ├── .a @ c2022
    │   ├── .b:1 @ c9b55
    │   └── .c:2 @ e3365
    ├── .d:[1, 2, 3] @ 9be3a
    └── .f:2 @ 93861
Added:
{'path': '.f', 'value': 2}
Removed:
{'path': '.e', 'value': 2}
Modified:
{'path': '.a.c', 'old': 3, 'new': 2}

COMPARE MESH CHANGE:
└── ROOT @ 95d3c
    ├── .attributes @ 79a1d
    │   └── .name:Mesh @ 7e7b9
    ├── .dva @ c54cf
    │   ├── .x:0.0 @ 5bc2d
    │   ├── .y:0.0 @ 1704b
    │   └── .z:0.0 @ 6199e
    ├── .dea @ c1cd7
    ├── .dfa @ 977d2
    ├── .vertex @ 631b6
    │   ├── .0 @ 269b3
    │   │   ├── .x:-0.8164965809277261 @ 2a2bf
    │   │   ├── .y:0.0 @ 1704b
    │   │   └── .z:-0.5773502691896258 @ 6244a
    │   ├── .1 @ 70091
    │   │   ├── .x:0.0 @ 5bc2d
    │   │   ├── .y:-0.8164965809277261 @ dcdd6
    │   │   └── .z:0.5773502691896258 @ 2c4c0
    │   ├── .2 @ 71776
    │   │   ├── .x:0.8164965809277261 @ 38e43
    │   │   ├── .y:0.0 @ 1704b
    │   │   └── .z:-0.5773502691896258 @ 6244a
    │   └── .3 @ 9c4f5
    │       ├── .x:0.0 @ 5bc2d
    │       ├── .y:0.8164965809277261 @ 477c9
    │       └── .z:0.5773502691896258 @ 2c4c0
    ├── .face @ 8ed1b
    │   ├── .0:[0, 1, 2] @ 8bb03
    │   ├── .1:[0, 3, 1] @ 15099
    │   ├── .2:[0, 2, 3] @ 96bc4
    │   └── .3:[1, 3, 2] @ d242c
    ├── .facedata @ c21a1
    │   ├── .0 @ a8138
    │   ├── .1 @ 80b33
    │   ├── .2 @ 35d79
    │   └── .3 @ 26f09
    ├── .edgedata @ 9a637
    ├── .max_vertex:3 @ 01770
    └── .max_face:3 @ 77792
└── ROOT @ 0b3b4
    ├── .attributes @ 79a1d
    │   └── .name:Mesh @ 7e7b9
    ├── .dva @ c54cf
    │   ├── .x:0.0 @ 5bc2d
    │   ├── .y:0.0 @ 1704b
    │   └── .z:0.0 @ 6199e
    ├── .dea @ c1cd7
    ├── .dfa @ 977d2
    ├── .vertex @ 24c72
    │   ├── .0 @ bc868
    │   │   ├── .x:1.0 @ 614ef
    │   │   ├── .y:0.0 @ 1704b
    │   │   └── .z:-0.5773502691896258 @ 6244a
    │   ├── .1 @ 70091
    │   │   ├── .x:0.0 @ 5bc2d
    │   │   ├── .y:-0.8164965809277261 @ dcdd6
    │   │   └── .z:0.5773502691896258 @ 2c4c0
    │   ├── .2 @ 71776
    │   │   ├── .x:0.8164965809277261 @ 38e43
    │   │   ├── .y:0.0 @ 1704b
    │   │   └── .z:-0.5773502691896258 @ 6244a
    │   └── .3 @ 9c4f5
    │       ├── .x:0.0 @ 5bc2d
    │       ├── .y:0.8164965809277261 @ 477c9
    │       └── .z:0.5773502691896258 @ 2c4c0
    ├── .face @ 8ed1b
    │   ├── .0:[0, 1, 2] @ 8bb03
    │   ├── .1:[0, 3, 1] @ 15099
    │   ├── .2:[0, 2, 3] @ 96bc4
    │   └── .3:[1, 3, 2] @ d242c
    ├── .facedata @ c21a1
    │   ├── .0 @ a8138
    │   ├── .1 @ 80b33
    │   ├── .2 @ 35d79
    │   └── .3 @ 26f09
    ├── .edgedata @ 9a637
    ├── .max_vertex:3 @ 01770
    └── .max_face:3 @ 77792
Added:
Removed:
Modified:
{'path': '.vertex.0.x', 'old': -0.8164965809277261, 'new': 1.0}

[gonzalocasas]

This is really cool! I didn't have time to review it in detail, and I also don't recall exactly how merkle trees are supposed to work, but it's a nice idea, I will go through it probably early next year!

[Licini]

This is really cool! I didn't have time to review it in detail, and I also don't recall exactly how merkle trees are supposed to work, but it's a nice idea, I will go through it probably early next year!

No hurries! It's just put up there for discussion. Have a great holiday! : )

[tomvanmele]

@Licini any progress here?

[jf---]

@Licini impressive contribution!

[Licini]

@tomvanmele could you take another look? And if adding an example, where should it go? tutorial.basics or tutorial.advanced?

[tomvanmele]

seems to LGTM, but is this meant to be serialisable? __data__ seems missing then...

@Licini ping

[Licini]

@Licini looks good, but would be even better if you add a (minimal) corresponding page in the docs related to this new data structure :)

Hey sorry totally forgot about this one for a while..... Added a tutorial now!

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 83.67347% with 16 lines in your changes missing coverage. Please review.

Project coverage is 60.01%. Comparing base (ea316f9) to head (e887548).

Files	Patch %	Lines
src/compas/datastructures/tree/hashtree.py	83.50%	16 Missing :warning:

Additional details and impacted files

@@            Coverage Diff             @@
##             main    #1238      +/-   ##
==========================================
+ Coverage   59.92%   60.01%   +0.09%     
==========================================
  Files         206      207       +1     
  Lines       22136    22234      +98     
==========================================
+ Hits        13264    13343      +79     
- Misses       8872     8891      +19     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[jf---]

@tomvanmele this is a considerable contribution -- what's holding back from merging?

[tomvanmele]

@jf--- it was merged yesterday

[jf---]

🤦‍♂️