解释：最近因为 某些不可预期也不可回避的原因 我不仅仅咸鱼，而且还忘记了很多希望能讲的事情...
部分原因也是『讲』开始不够了，好了... 接下来 部分回归正轨

公告表示此为 Telegram 机器人对特地消息排版模式的误封锁
此时误会已经解除，对 WeVoice 管理员之前的误解表示抱歉

#未公告
占用一下 News 的空间来声明一下昨天 @duangsuse 被无故封锁一事。
此封锁操作由 TGCN-ADNK 机器人错误发起，项目组反馈如上。当事人没有任何违背群规行为。

🤔 这时候我还有一点在想 ADNK 是啥子的缩写

为什么会觉得自己变蠢了：

1. 我本来就不够聪明，相对于我想做的事情而言
2. 我缺少练习，最近也缺少动力（即便事情越来越多，但对慵懒的我来说，事情越多我越推，少一点我反而干了）
3. 三天打鱼两天晒网（至少最近是如此）的模式是不利于发展的
4. 最近的需求提升太剧烈了，具体表现：
a. 我比以往更重视编程实践和（非易失）状态化编程了，这样就不得不谈数据的表示方式（序列化）和一堆问题，我还要接触 C++ 的 iterator, fstream, map, string 什么的东西
以及，Maven, Gradle 等构建工具的语法和 Make 有很大差别，而且多数插件配置繁多
以及，越来越多开发者开始学习 Kotlin Common / Multiplatform / C / C# 了，我怕是跟不上，何况他们的插件也有一大堆配置和 properties
b. 我开始看网络编程了，虽然都是应用层的，而且表示全是 HTTP，最重要的是我同时考虑前端的问题，单页路由好像没有去了解，有时候设计我不会的 layout 就会出问题，Android 应用的标准开发模式也不熟悉
最重要的是，我对 box layout 不了解...
c. 击键不熟悉、创建项目变少、看见大佬的项目和 production ready / 技术高超的软件变多，导致信心丢失严重
d. 我的『分析』更频繁了，而且全都是不会写出来的那种
da. 比如，我看到 zuobiao.me 的调查表都会思考其分页调查实现方式，状态数据传递方式
我会考虑给予一个 [Int], 如何统计出各元素出现的数目，而且最重要的是我不会只想一种方法（比如上面的问题，我基于过程式给出了直接对每项统计输出/array 的做法、基于函数式 map & count、基于算法使用 Map 结构）
甚至对同样的方法我都要想多种范式的（过程式、函数式、多范式封装方式），这占用了大量的脑力和零碎时间
偶尔还会考虑相关的 API 封装方式（比如上例，数据『座标』图的绘制接口，而且还得翻找之前的经验，又得等半天）
db. 比如，知道自己是被 CNBLR 的 ADNK bot 封禁以后，我得考虑类似的 bot 是如何实现（事件模型），需要何种作用域下的何种状态
哪怕是『黑名单和白名单模式，怎么实现』这个问题我都得想一分钟，最后找到如下程序：

       def acceptable(item):
         if use_whitelist: return item in acceptables
         else: return item not in acceptables

       not = lambda p: lambda x: not p(x)
       elem = lambda x, set: x in set
       notElem = not(elem)
       def acceptable1(item):
         judge = elem if use_whitelist else notElem
         return judge(item, acceptables)

这还没完，我得继续找下去（实际上因为很久没看书，我的直觉下降了很多，连这个 def acceptable 定义的类型签名我都想了一会）...
我找到的很多程序都只是一个（不一定是最好的）版本而已，本身还可以有很多方式写出等价的程序

            def acceptable2(item):
               accept = item in acceptables
               if not use_blacklist: accept = not accept
               return accept

我甚至回忆起了 Scheme (准确的说是 Racket... R6RS 好像没有 Map 吧？)...

       (define (count words)
         (set! counts (make-hash))
         (for-each words (lambda (w)
            (hash-update counts w (+ (hash-ref counts w) 1) 0) )))

dc. 有时候我得看一些不那么直白的代码，得想『还能怎么做』，比如之前重构的 FontMod... （和其作者交流了好久，快把 @YuutaW 刷屏了，跑）
想不明白的问题多了自然觉得自己菜了....

下面来说一下这个基于 DOM 的 Heading tree 解析程序的问题 #JS #Algorithm
你将学会如何在不使用显式递归的情况下，只用栈数据结构该如何解析提取嵌套结构

一个明显的好处是这么做快一些：在构造部分子树时，不需要判断 N 次基线条件
此外，这样无须使用 iterator 来跨子程序传递流（扫描）状态
一个坏处是：程序没有那么优雅好看了

接下来讲的实现方式包含三种：

1. 标准方式 — Iterator
a. 把 iterator 的 position 放在递归参数里
b. plain iterator
2. “普通”方式 — 无限 subsequence
我就不写了... 其实很多人这么写的时候也是递归地构造结构，而且对这个问题这么做尤其莫名其妙
3. 优化方式 — foreach 状态机 + 两个显式栈
其中一个栈是用于保存 Heading 深度的，一个栈是保存结果的，只不过碰巧也可以用栈的方式实现

const _1to6 = '1,2,3,4,5,6'.split(',');
function parseHeadingTree(root) {
const isHeading = e => (nm => nm.length > 1 && nm[0] === 'H' && nm[1] in _1to6)(e.tagName);
const headingDepth = e => Number.parseInt(e.tagName[1]); // why not regex?
const peek = (xs) => xs[xs.length -1];
/**/let resultstk = [[]], depthstk = [1]; // 2 stack
for (let elem of root.children) {
if (!isHeading(elem)) continue;
let depth = headingDepth(elem);
let lastdept = peek(depthstk);
if (depth > lastdept) {
depthstk.push(depth);
let subtree = [];
peek(resultstk).push(subtree);
resultstk.push(subtree); }
else if (depth < lastdept) {
depthstk.pop();
resultstk.pop(); }
peek(resultstk).push(elem);
}
return resultstk;
}

发实现走人（慵懒

... 我还打算一遍过的，没想到我对栈组织的还好，对结果的断言没预料到.... 我想想

不过也很快了，程序总共只修改了两次就可以勉强按照预期运行，而且两次
1. 我的一个注释写成了 /*/
2. 我测试的时候给的 document.body 没有 heading

const _1to6 = '1,2,3,4,5,6'.split(',');
const isHeading = e => (nm => nm.length > 1 && nm[0] === 'H' && nm[1] in _1to6)(e.tagName);
const headingDepth = e => Number.parseInt(e.tagName[1]); // why not regex?
const peek = (xs) => xs[xs.length -1];
function parseHeadingTree(root) {
let resultstk = [[]], depthstk = [1];
for (let elem of root.children) {
if (!isHeading(elem)) continue;
let depth = headingDepth(elem);
let lastdept = peek(depthstk), leaf = peek(resultstk);
if (depth > lastdept) {
depthstk.push(depth);
let subtree = [];
leaf.push(subtree);
resultstk.push(subtree); continue; }
else if (depth < lastdept) {
depthstk.pop(); resultstk.pop(); }
leaf.push(elem);
}
return resultstk;
} 争取一下，模拟执行发现一个 bug...
其实我没有主意到 leaf （本身是一个 expression，而不是 value）在过程中发生了更新（if (depth < lastdept) { resultstk.pop(); }）
看来 JS 里没法解决了... 哦不我用箭头函数

至于剩下的问题，就是『栈上重复的引用』
返回前加一个 pop 即可解决

我日，这反 修复失败...

function parseHeadingTree(root) {
const topItem2Stk = (xs) => { let top = xs.pop(); xs.push([top]); };
const deepest = (xs) => { let xx; for (xx = xs; xx.length >0 && xx[0] instanceof Array; xx = xx[0]); return xx; };
let resultstk = [[]], depthstk = [1];
for (let elem of root.children) {
if (!isHeading(elem)) continue;
let depth = headingDepth(elem);
let lastdept = peek(depthstk), leaf = () => peek(resultstk);
if (depth > lastdept) {
depthstk.push(depth);
let subtree = [];
topItem2Stk(resultstk);
leaf().push(subtree);
resultstk.push(subtree); }
else if (depth < lastdept) {
depthstk.pop(); resultstk.pop(); }
leaf().push(elem);
}
let layer = peek(resultstk);
while (layer instanceof Array &&
(layer.length === 0 ||
headingDepth(deepest(layer)) !== 1) ) {
resultstk.pop();
layer = peek(resultstk); } // for top <h1>
return resultstk;
}

为什么一定要 pop 到 <h1>？因为普通情况：

<h1/>
  <h2/>

此时栈顶依然是 h2 的子节点，除非它后面跟了个 h1 使得它被关掉
length == 0 的是不合法的情况，每层至少得有一个 <hn>
len=0 说明它是在读取一个 subtree

沃日，还是不行，策略用错了 这哪里是颗树啊，只有一层...

（拿命继续分析） h4 的时候栈顶为 4
遇到 3 则 depth > lastdept。应该弹出 h4 的栈，所以 h4 实际上没有孙子
h3 遇到 h3 放一起，但我不想这样

我想：h4 遇到 h5 的时候应该接纳 h5... h5 是 h4 的孙子才对
所以就要 deep 放... 得看下一项 是否开启一个 subtree 怎么办呢

const topItem2Stk(xs) => { let top = xs.pop(); xs.push([top]); };
if (depth > lastdept) {
depthstk.push(depth);
let subtree = [];
topItem2Stk(resultstack);
leaf().push(subtree);
resultstk.push(subtree); } 肮脏的做法：若是有的话，我再改回来不就好了！（

const _1to6 = '1,2,3,4,5,6'.split(',');
const isHeading = e => (nm => nm.length > 1 && nm[0] === 'H' && nm[1] in _1to6)(e.tagName);
const headingDepth = e => Number.parseInt(e.tagName[1]); // why not regex?
const peek = (xs) => xs[xs.length -1];
const topItem2Stk = (xs) => { let top = xs.pop(); return (top instanceof Array? top : [top]); };
const deepest = (xs) => { let xx; for (xx = xs; xx.length >0 && xx[0] instanceof Array; xx = xx[0]); return xx; };

function parseHeadingTree(root) {
let resultstk = [[]], depthstk = [1];
function deduceToLevelBase(lev) {
while (peek(depthstk) >= lev) { depthstk.pop(); resultstk.pop(); } }
for (let elem of root.children) {
if (!isHeading(elem)) continue;
let depth = headingDepth(elem);
let lastdept = peek(depthstk), leaf = () => peek(resultstk);
if (depth > lastdept) {
depthstk.push(depth); let parent;
leaf().push(parent = topItem2Stk(leaf()));
let subtree = []; parent.push(subtree);
resultstk.push(subtree); }
else if (depth < lastdept) {
depthstk.pop();
resultstk.pop();
deduceToLevelBase(depth); }
leaf().push(elem);
}
let layer = peek(resultstk);
while (layer instanceof Array &&
(layer.length === 0 ||
headingDepth(deepest(layer)[0]) !== 1) ) {
resultstk.pop();
layer = peek(resultstk); } // for top <h1>
return resultstk;
}

勉强能用的版本，有点小问题

我有点想放弃了，看起来 bug 根本不应该出现

就此算了，可见显式栈的解析器只会更加复杂，难以手写，而不会简单半分
此时已经是凌晨两点了，是我的积累不够而已，就是做不到。 #Algorithm

之前写的那个是堆出来的，我根本就不知道它是基于什么原理....（虽然的确是我自己写的） 输入数据的内涵结构稍微有点变化就会炸，改一点也可能要炸。

虽然我不打算继续了，现在还是说一下这是怎么工作的吧。

上面的 parseHeadingTree 是一个接受 DOM 节点的 ToC （Table of Contents）解析器，它解析目标节点下的所有 h1-h6 heading，来构造一个 header 树

就像这样：

h1
h1
  h2
    h3
  h2
    h5
    h5

[h1
  [h1 [
    [h2 [h3]]
    [h2 [h5 h5]]]]

有两种节点
+ 当前层节点 <h1-h6>
+ 子树节点 [<h1-h6> [...]]

它的解析规则很简单
a. 有一个栈用于记录当前嵌套 heading 的层次, 初始化为 [1]
b. 有一个栈用于放置 <h1-h6> 的嵌套解析状态, 初始化为 [ [] ]
+ 每次要添加元素的时候，都加到 peek(resultstk) 里，因为它代表当前层正在架构的数据对象
e.g.

h1 [[h1]]
h1 [[h1 h1]]
  h2 [a [h1 [h1 a=[h2]]]] 

然后，如果遇到一个 h1 (h1 < h2) 就停止构建 <h2> 的 children，然后把 h1 加到当前层上
h1

[[h1 [h1 a=[h2]] h1]]

这个结论对所有『递归』层都是有效的，也就是说这里的 h2 后面再跟 h3 h4 都是一样的
否则，如果它是最后一个呢？在 for 后面有个 while 就是解决这个问题的，它把所有正在读取还未结束的层给 pop 掉，保证结果单一

+ 如果当前深度增加了，则将上一个标签转换为 stack，加入自己这一层并且进入

  let parent;
      leaf().push(parent = topItem2Stk(leaf()));
      let subtree = []; parent.push(subtree);

resultstk.push(subtree); 当然它还不够健壮，因为如果第一个就是 <h2> 而不是 h1 的话，topItem 就不存在了... 我写个特殊标签吧
+ 如果当前深度不变，什么都不做
+ 如果当前深度减小了，弹出当前深度、弹出一次结果栈（当前构造）
你也可以理解为给构造动态加 ] 闭括号，就是通过弹出栈的方式
最后，把标签送进当前构造的子树里面去，这就实现了无限深度的铺平构造
可是还有一片小乌云。

比方说

h1
  h2
      h5
    h4

我们一般认为 h5 h4 都是 h2 的元素，可是因为上面规则的幼稚性， h5 是 h2 的元素，h4 却不是（h4.depth < h5.depth）
准确的说，一般递归扫描的时候也是『遇到第一个 depth > currentdept 的时候停下』，可我们的这个 context 是基于显式栈的
我想到的方法是（也是递归的时候栈的一种情况）每次 (h4.depth < h5.depth) 的时候，不断 deduce 栈，直到 (h4.depth >= layer.depth) （找到第一个基层）

h1 [h1
  h2 [h1 [h2
      h5 [h1 [h2 [h5
    h4

a. ]](关闭的是 h2 的栈... 不是 h5 的)
b. {- 找到第一个开括号 [h2 -}
] [h4]]

我也是才知道，其实我之前写的也没解决这个问题.... 看起来倒是进步了