Apfelmus, Thanks for the reply.
From your description (without reading the code ;))
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).
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. An outward radial path will only expand the tree linearly, not quadratically, in size.
Put differently, using Data.Tree.Zipper.parent on B will move you to C, not to A.
The parent of C is either A or B, depending on the path that created it, but parent teleports you in O(1). Walking from A to B only involves: (bX,bY) = (-3,0) (aX,aY) = (-2,0) (bR,bK) = (|bX| + |bY|, bR - bX) = (3,6) -- left halfplane (aR,aK) = (|aX| + |aY|, aR - aX) = (2,4) -- left halfplane deltaR = bR - aR = 1 maybe (insertDownFirst (newNode rk) z) (moveAround rk) $ firstChild z When firstChild fails, insertDownFirst and we're done! All operations are O(1). When firstChild succeeds, moveAround queries each of the defined nodes -- but not any of the undefined nodes! -- at that radius. There is at most one defined node with Nothing value to ensure a path from the origin to every node (where path is not contiguous in X,Y, or K, only in R!) The diagram you describe can be created with: Prelude> :l GridZipper *GridZipper> let f &&& g = \x -> (f x, g x) *GridZipper> let f >>> g = g . f *GridZipper> const (newGrid :: Grid String) >>> fromTree
west >>> west >>> setValue (Just "A: X=-2,Y=0,R=2,K=4") west >>> setValue (Just "B: X=-3,Y=0,R=3,K=6") east >>> east >>> east east >>> east >>> setValue (Just "C: X= 2,Y=0,R=2,K=0") assocList >>> show >>> putStrLn $ ()
-- The tree is this: [(XY (-2) 0,"A: X=-2,Y=0,R=2,K=4"), (XY (-3) 0,"B: X=-3,Y=0,R=3,K=6"), (XY 2 0,"C: X= 2,Y=0,R=2,K=0")] -- Zipper starts at origin: Loc {tree = Node {rootLabel = GridLabel (RK 0 0) Nothing, subForest = []}, lefts = [], rights = [], parents = []} -- Zipper after walking to A and setting value: Loc {tree = Node {rootLabel = GridLabel (RK 2 4) (Just "A: X=-2,Y=0,R=2,K=4"), subForest = []}, lefts = [], rights = [], parents = [([],GridLabel (RK 1 2) Nothing,[]) ,([],GridLabel (RK 0 0) Nothing,[])]} -- Zipper after walking to B and setting value: Loc {tree = Node {rootLabel = GridLabel (RK 3 6) (Just "B: X=-3,Y=0,R=3,K=6"), subForest = []}, lefts = [], rights = [], parents = [([],GridLabel (RK 2 4) (Just "A: X=-2,Y=0,R=2,K=4"), []),([],GridLabel (RK 1 2) Nothing,[]) ,([],GridLabel (RK 0 0) Nothing,[])]} -- Zipper where it left off at C: (Loc {tree = Node {rootLabel = GridLabel (RK 2 0) (Just "C: X=2,Y=0,R=2,K=0"), subForest = []}, lefts = [], rights = [], parents = [([Node {rootLabel = GridLabel (RK 1 2) Nothing, subForest = [Node {rootLabel = GridLabel (RK 2 4) (Just "A: X=-2,Y=0,R=2,K=4"), subForest = [Node {rootLabel = GridLabel (RK 3 6) (Just "B: X=-3,Y=0,R=3,K=6"), subForest = []}]}]}], GridLabel (RK 1 0) Nothing,[]), ([],GridLabel (RK 0 0) Nothing,[])]}, -- Zipper at origin Loc {tree = Node {rootLabel = GridLabel (RK 0 0) Nothing, subForest = [Node {rootLabel = GridLabel (RK 1 2) Nothing, subForest = [Node {rootLabel = GridLabel (RK 2 4) (Just "A: X=-2,Y=0,R=2,K=4"), subForest = [Node {rootLabel = GridLabel (RK 3 6) (Just "B: X=-3,Y=0,R=3,K=6"), subForest = [] } ]} ]}, Node {rootLabel = GridLabel (RK 1 0) Nothing, subForest = [Node {rootLabel = GridLabel (RK 2 0) (Just "C: X=2,Y=0,R=2,K=0"), subForest = [] }] }]}, lefts = [], rights = [], parents = []}) Apfelmus, Heinrich wrote:
Dan Weston wrote:
For the 2D grid zipper above, moving around is O(1) but update is O(log n). This is acceptable; also because I'm quite confident that a zipper for a 2D grid with everything O(1) does not exist. I can prove that for a special case and should probably write it down at some point. Really? My solution (rose tree zipper where tree depth is manhattan distance from origin and forest width is nodes around concentric diamonds, see http://permalink.gmane.org/gmane.comp.lang.haskell.cafe/49948) was designed specifically to be amortized constant for everything for paths that do not specifically move helically around the origin. The complexity of lookup is O(d) where d is the number of defined nodes at a given radius. Until the grid gets pretty dense, d grows very slowly for most sane paths.
Have I missed something?
From your description (without reading the code ;)), I gather that your tree looks something like this?
-+- / \ -+ -+- +- / / \ \ -+ -+ -+- +- +- / / / \ \ \ -+ -+ -+ -+- +- +- +- / / / / \ \ \ \ + B A + +--+--C--+--+-- ... \ \ \ \ / / / / -+ -+ -+ -+- +- +- +- \ \ \ / / / -+ -+ -+- +- +- \ \ / / -+ -+- +- \ / -+-
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).
Put differently, using Data.Tree.Zipper.parent on B will move you to C, not to A.
I mean, O(d) may be fine for you, but it's not O(1) for everything as advertised. :)
Regards, H. Apfelmus
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe