反序列化广度优先树

Question

我需要按如下方式使用四叉树：

           p
         /| |\ 
        / | | \    
       /  | |  \
      p   w b   p
    /| |\     /| |\   
   / | | \   / | | \
  b  w w  b w  b w  b

但它们已使用广度优先顺序序列化为字符串，因此之前的树将具有以下表示形式：

ppwbpbwwbwbwb

我正在尝试将这样的字符串转换为嵌套向量结构：

[ [ b w w b ] w b [ w b w b] ]

但有时以下代码无法正常工作：

(defn read-quad-tree [pattern]
  (loop [r                    []
         [s & rs :as stack]   []
         [p & rp :as pending] (reverse pattern)]
    (cond (nil? pending)  (first r)
          (= (count r) 4) (recur [] (conj stack (reverse r)) pending)
          (= p \p)        (recur (conj r s) rs rp)
          :else           (recur (conj r p) stack rp))))

已编辑以添加复杂示例：

另一个（失败的）例子。下一棵树：

                    |
         +------+-------+------+
         |      |       |      |
         |      w       w      |
         |                     |
   +---+---+---+         +---+---+---+
   |   |   |   |         |   |   |   | 
   |   w   w   |         |   w   w   |
   |           |         |           |
+-+-+-+     +-+-+-+   +-+-+-+     +-+-+-+
| | | |     | | | |   | | | |     | | | |
b b b b     w w w w   b b w w     b w b w

将被序列化为：

ppwwppwwppwwpbbbbwwwwbbwwbwbw

目标是获得以下结构：

[ [ [ b b b b ] w w [ w w w w ] ] w w [ [ b b w w ] w w [ b w b w ] ] ]

但是我的代码给出了不同的（错误的）结构。

Answer 1

您的代码存在一些表示列表而不是（预期的）向量的名称。

这已经可以从函数的 return 值中看出，它是一个列表。

查看代码的这些部分：

(loop   ...
        [s & rs :as stack]
        ...
        (recur (conj r s) rs rp)

高亮的[s & rs :as stack]会得到stack向量，将第一个元素命名为s，其余元素命名为list(!)rs。由于 rs 是一个列表，它会在某个时候像那样传递给 stack（通过最后一个 recur），然后也是一个列表，而不是一个向量。然后，下一次 r 有 4 个元素时，(conj stack ... 将不会追加 r，而是添加前缀，因为这是conj 应用于列表时。引用自 docs:

;; notice that conjoining to a vector is done at the end

;; notice conjoining to a list is done at the beginning

这当然会破坏预期的算法，并解释您得到的错误结果。

即使 r 是向量，(reverse r) 也会出现类似的问题。

您可以修复它，例如，通过在您希望列表作为向量传递的位置应用 (into [] ...)。我看到两个地方需要这样做：

(defn read-quad-tree [pattern]
  (loop [r                    []
         [s & rs :as stack]   []
         [p & rp :as pending] (reverse pattern)]
    (cond (nil? pending)  (first r)
          (= (count r) 4) (recur [] (conj stack (into [] (reverse r))) pending)
          (= p \p)        (recur (conj r s) (into [] rs) rp)
          :else           (recur (conj r p) stack rp))))

pending不需要修复，因为它永远不会“感染”列表类型的其他名称。

当更正后的代码这样调用时：

(println (read-quad-tree "ppwwppwwppwwpbbbbwwwwbbwwbwbw"))

它将输出：

[[[b b b b] w w [w w w w]] w w [[b b w w] w w [b w b w]]]

在查找问题时，我还添加了一些对（无效）有效模式的检查，您可能会感兴趣。扩展代码如下：

(defn read-quad-tree [pattern]
    (loop   [r                   []
            [s & rs :as stack]   []
            [p & rp :as pending] (reverse pattern)]
        (cond
            (nil? pending)
                (if (or (seq stack) (not= (count r) 1))
                    {:error "Too few 'p'"}
                    {:tree (first r)})
            (= (count r) 4)
                (recur [] (conj stack (into [] (reverse r))) pending)
            (= p \p) 
                (if (empty? s)
                    {:error (format "'p' at %s lacks %d children" (count pending) (- 4 (count r)))}
                    (recur (conj r s) (into [] rs) rp))
            :else
                (recur (conj r p) stack rp))))

如果一切顺利，它将 return 带有 tree 键的地图，或者如果 error 键模式不完整。

反序列化广度优先树

Deserialize breadth-first trees

algorithm

tree

clojure