CODEWITHSUNDEEP
clojurefunctional-programmingzipper
erdos
erdos

Reputation: 3538

Clojure zipper to remove all right siblings

I want to write a function for a zipper that removes all right siblings of a node while staying at the same location.

(defn remove-all-rights-1 [loc]
  (if (zip/right loc) 
    (recur (zip/remove (zip/right loc)))
    loc))

The problem here is that remove returns the location that would have preceded the current node in DFS.

Therefore the following example...

(-> (clojure.zip/vector-zip [1 [[2] 3]])
    (zip/down)
    (zip/right)
    (zip/down)
    (remove-all-rights-1)
    (zip/replace :x)
    (zip/root))

...gives [1 [[:x]]] instead of [1 [:x]] because zip/remove jumped to the bottom leaf instead of just going back left.

How should I remove the right siblings without also changing location in the tree? Thanks in advance!

Upvotes: 1

Views: 248

Answers (3)

Alan Thompson
Alan Thompson

Reputation: 29984

This can be easily accomplished with the Tupelo Forest library:

(dotest
  (with-forest (new-forest)
    (let [edn-orig          [1 [[2] 3]]
          root-hid          (add-tree (edn->tree edn-orig))
          hid               (find-hid root-hid [::tf/list ::tf/list])
          subtree-edn-orig  (-> hid hid->tree tree->edn)
          >>                (kids-update hid butlast)
          subtree-edn-final (-> hid hid->tree tree->edn)
          edn-final         (-> root-hid hid->tree tree->edn)]

      (is= subtree-edn-orig      [[2] 3])
      (is= subtree-edn-final     [[2]])
      (is= edn-final          [1 [[2]]]  ))))

The tree created has nodes with :tag values of :tupelo.forest/list at the first & second levels:

  (is= (hid->bush root-hid)
    [{:tag :tupelo.forest/list, :tupelo.forest/index nil}
     [#:tupelo.forest{:value 1, :index 0}]
     [{:tag :tupelo.forest/list, :tupelo.forest/index 1}
      [{:tag :tupelo.forest/list, :tupelo.forest/index 0}
       [#:tupelo.forest{:value 2, :index 0}]]]] )

An HID is a pointer to a tree node, so root-hid points to the root node of the tree and hid points to the subtree [[2] 3]. After we remove the right-most node 3, hid points to the subtree [[2]].

For the child nodes (kids), we use the butlast function to remove the right-most, then convert the data from a forest/tree format back into EDN.

See the README here, and the API docs here. There are also many live code examples here. Also see the Clojure Conj video.

Upvotes: 1

erdos
erdos

Reputation: 3538

Generalizing akond's answer gave the following solution:

(defn remove-all-rights
  "Removes all right siblings. Stays at original location."
  [loc]
  (let [parent-loc (zip/up loc)
        |lefts| (inc (count (zip/lefts loc)))]
    (->> (zip/make-node loc (zip/node parent-loc) (take |lefts| (zip/children parent-loc)))
         (zip/replace parent-loc)
         (zip/down)
         (zip/rightmost))))

The main idea is to construct a copy of the parent node where the collection of children does not contain the right siblings.

Upvotes: 2

akond
akond

Reputation: 16060

(letfn [(kill-right [loc]
            (let [lost   (zip/rights loc)
                  parent (-> loc zip/up zip/node)
                  node   (into (empty parent) (take (- (count parent) (count lost)) parent))]
                (-> loc
                    zip/up
                    (zip/replace node)
                    zip/down
                    zip/rightmost)))]
    (-> (clojure.zip/vector-zip [1 [[2] 3]])
        zip/down
        zip/right
        zip/down
        kill-right
        (zip/replace :x)
        zip/root))

Upvotes: 1

Related Questions