Dan Weston wrote: > > I hope the code is better than my description! :) The structure is more > like > > Nothing(RK 0 _) > Nothing(RK 1 _) > A(RK 2 4) > B(RK 3 6) > C(RK 2 0) > >> The root of the tree is the center and you can descend on the right. >> But with this structure, walking from A to B is O(d) = O(n) >> (where d is the distance from the origin, >> n the side length of the grid) instead of O(1). > > No. The tree is [[Node]], where the outer list has one element for each > radius that has an occupied node and each inner list has the number of > nodes at the given radius. > > You descend the spine of the outer list radially in O(deltaR) time, > which for incremental moves is O(1). > > Then you search for an existing inner list element in O(nk(r)), which > stays fairly constant for reasonable paths (basically, the width of a > path swath).
Ah, so you're using a sparse representation for grids. That's a good idea! Unfortunately, it doesn't help when the grid is a full rectangle, i.e. when nk(r) becomes proportional to r. The (most likely unattainable) goal I had in mind is to create a zipper for the full grid that supports O(1) operations. >> I mean, O(d) may be fine for you, but it's not O(1) for everything as >> advertised. :) > > d is not the distance from the origin, it is nk(r), the number of nodes > at a given radius: d(2) = 2, d(3) = 1. Oh, right. > An outward radial path will only expand the tree linearly, not > quadratically, in size. Well, that's still linear in the side length of a full grid. Directly using Data.Map (Integer,Integer) a would improve that to a logarithm. Of course, your structure can be enhanced by using a Data.Map instead of a linked list for each ring à la [Data.Map Integer a] This will give O(log nk(r)) movements, but that's still not constant time. Regards, H. Apfelmus _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe