search

geocaml / ocaml-rtree

A pure OCaml implementation of R-Trees
BSD 3-Clause "New" or "Revised" License
26 stars 7 forks source link

Depth function #22

Closed harshey1103 closed 1 year ago

harshey1103 commented 1 year ago

Initial implementation of depth function. The function returns 0 for an empty tree and 1 for a tree whose root is a leaf.

patricoferris commented 1 year ago

Just as an additional thing, your depth' function isn't tail-recursive. I'm totally fine with this but it might be a nice exercise to see if you can make it tail-recursive. Some extra info on that: https://www.cs.cornell.edu/courses/cs3110/2014fa/recitations/5/rec05.html

harshey1103 commented 1 year ago

Hi @patricoferris, I looked into the test directory but I am not able to figure out how to write a test for the depth function. There aren't any tests for the Rtree module. :'(

patricoferris commented 1 year ago

Yes the tests are a little disorganised, apologies! There are tests of the Rtree module though. For example

https://github.com/geocaml/ocaml-rtree/blob/ee12c378658e28dd66d7d69066f6719164c67f02/test/basic.ml#L88-L120

Here we test the OMT loader for an instantiation of the Rtree module using rectangles and lines. This should help write a test to check the depth function :))

harshey1103 commented 1 year ago

I tried to make the function tail recursive and have written the tests can you please have a look @patricoferris @AryanGodara .

patricoferris commented 1 year ago

The changes are looking good to me. Our CI system seems a bit broken, so I've opened an issue for them: https://github.com/ocurrent/solver-service/issues/74. I ran this locally and I'm happing with the changes, thank you @harshey1103 :))

patricoferris commented 1 year ago

One thing I would add is that the depth function is not quite tail-recursive here (the function call is not in the tail position) but that's okay, I think something else might break before we get depths that cause us trouble... I think