Extract indices of visible nodes in a tree where only some nodes are expanded

Question

A program that I work on constantly updates and modifies program state containing an arbitrarily deep and wide tree. The data looks something like this.

(defonce state
         (r/atom {:some  "program"
                  :state "here"
                  :tree  [{:topic    "Books"
                           :expanded true
                           :children [{:topic "Titles"}
                                      {:topic    "Authors"
                                       :expanded true
                                       :children [{:topic "Alice"}
                                                  {:topic "Bob"}
                                                  {:topic "Carol"}]}
                                      {:topic "Genres"}]}
                          {:topic    "CDs"
                           :children [{:topic "Genres"}
                                      {:topic "Albums"}
                                      {:topic "Artists"}]}
                          {:topic    "To Do"
                           :expanded true
                           :children [{:topic    "Spouse Birthday"
                                       :expanded nil
                                       :due-date "07/31/2025"
                                       :children [{:topic "Buy Card"}
                                                  {:topic "Buy Jewelry"}
                                                  {:topic "Buy Cake"}]}]}]}))

As the program runs, I need to extract the series of numeric vector indices to reach the visible topics (those that have :children where the :expanded flag is present and "truthy").

Here is a method that works.

;; This flattening function is from an idea presented in response to
;; this question:
;; https://stackoverflow.com/questions/5232350/clojure-semi-flattening-a-nested-sequence
(defn flatten-to-vectors
  [s]
  (mapcat #(if (every? coll? %) (flatten-to-vectors %) (list %)) s))

(defn visible-nodes
  [tree so-far]
  (flatten-to-vectors
    (map-indexed
      (fn [idx ele]
        (let [new-id (conj so-far idx)]
          (if (not (and (:children ele) (:expanded ele)))
            new-id
            (cons new-id (visible-nodes (:children ele) new-id)))))
      tree)))

;; The function can be called like this on the data above.
(println (visible-nodes (:tree @state) []))
;; => ([0] [0 0] [0 1] [0 1 0] [0 1 1] [0 1 2] [0 2] [1] [2] [2 0])

Although this works, it seems like I should be able to generate the correct result without creating nested sequences that require flattening. But I just can't come up with anything.

Any suggestions would be appreciated.

Answer 1

You are right to want to avoid creating the nested structure to begin with. I imagine you read my answer in the question you linked (the second one). As there, here the solution is to use mapcat instead of map. And as I also say in the comments there, while mapcat-indexed does not exist, you can just pass an extra (range) argument to get numbering.

(defn visible-nodes [tree]
  (mapcat (fn [idx ele]
            (for [node (cons []
                         (when (:expanded ele)
                           (visible-nodes (:children ele))))
              (cons idx node))
          (range), tree))

Answer 2

Depending on your final goal, you may be interested in the Tupelo Forest library. Here is a sample of what you can do (data converted to the "tree" format):

(dotest-focus
  (with-forest (new-forest)
    (let [data          {:tag      "program"
                         :state    "here"
                         ::tf/kids [{:topic    "Books"
                                     :expanded true
                                     ::tf/kids [{:topic "Titles" ::tf/kids []}
                                                {:topic    "Authors"
                                                 :expanded true
                                                 ::tf/kids [{:topic "Alice" ::tf/kids []}
                                                            {:topic "Bob" ::tf/kids []}
                                                            {:topic "Carol" ::tf/kids []}]}
                                                {:topic "Genres" ::tf/kids []}]}
                                    {:topic    "CDs"
                                     ::tf/kids [{:topic "Genres" ::tf/kids []}
                                                {:topic "Albums" ::tf/kids []}
                                                {:topic "Artists" ::tf/kids []}]}
                                    {:topic    "To Do"
                                     :expanded true
                                     ::tf/kids [{:topic    "Spouse Birthday"
                                                 :expanded nil
                                                 :due-date "07/31/2025"
                                                 ::tf/kids [{:topic "Buy Card" ::tf/kids []}
                                                            {:topic "Buy Jewelry" ::tf/kids []}
                                                            {:topic "Buy Cake" ::tf/kids []}]}]}]}

processing:

          root-hid      (add-tree data)
          expanded-hids (find-hids root-hid [:** {:expanded true}])
          ]
      (spy-pretty (hid->bush root-hid))
      (doseq [hid expanded-hids]
        (newline)
        (println "-----------------------------------------------------------------------------")
        (spy-pretty :node (hid->node hid))
        (spy-pretty :bush (hid->bush hid)))
      )
    )
  )

with results, overall data in "bush" format:

[{:tag "program", :state "here"}
 [{:topic "Books", :expanded true}
  [{:topic "Titles"}]
  [{:topic "Authors", :expanded true}
   [{:topic "Alice"}]
   [{:topic "Bob"}]
   [{:topic "Carol"}]]
  [{:topic "Genres"}]]
 [{:topic "CDs"}
  [{:topic "Genres"}]
  [{:topic "Albums"}]
  [{:topic "Artists"}]]
 [{:topic "To Do", :expanded true}
  [{:topic "Spouse Birthday", :expanded nil, :due-date "07/31/2025"}
   [{:topic "Buy Card"}]
   [{:topic "Buy Jewelry"}]
   [{:topic "Buy Cake"}]]]]

and the 3 nodes with a truthy value for :expanded as both a raw node or a "bush":

-----------------------------------------------------------------------------
 :node => 
{:tupelo.forest/khids [1001 1005 1006], :topic "Books", :expanded true}

 :bush => 
[{:topic "Books", :expanded true}
 [{:topic "Titles"}]
 [{:topic "Authors", :expanded true}
  [{:topic "Alice"}]
  [{:topic "Bob"}]
  [{:topic "Carol"}]]
 [{:topic "Genres"}]]

-----------------------------------------------------------------------------
 :node => 
{:tupelo.forest/khids [1002 1003 1004],
 :topic "Authors",
 :expanded true}

 :bush => 
[{:topic "Authors", :expanded true}
 [{:topic "Alice"}]
 [{:topic "Bob"}]
 [{:topic "Carol"}]]

-----------------------------------------------------------------------------
 :node => 
{:tupelo.forest/khids [1015], :topic "To Do", :expanded true}

 :bush => 
[{:topic "To Do", :expanded true}
 [{:topic "Spouse Birthday", :expanded nil, :due-date "07/31/2025"}
  [{:topic "Buy Card"}]
  [{:topic "Buy Jewelry"}]
  [{:topic "Buy Cake"}]]]