前回の振り返り
前回は、Compositeパターンを導入し、Heading Role、LeafHeading、SectionHeadingの3つの構成要素でツリー構造を表現できるようにしました。しかし、ツリー構造は手動で構築していました。
今回は、パーサーを実装して、見出しの配列から自動的にツリー構造を構築します。
今回のゴール
HeadingExtractorで抽出した見出しの配列（フラット）を受け取り、SectionHeadingとLeafHeadingのツリー構造を自動的に構築するTOCParserクラスを作成します。
ツリー構築のアルゴリズム
見出しの配列をツリー構造に変換するには、スタックを使ったアルゴリズムが有効です。
基本的なアイデア
- スタックに「現在の親候補」となる見出しを積んでいく
- 新しい見出しが来たら、スタックから「自分より浅いレベルの見出し」を探す
- その見出しの子として追加する
- 自分もスタックに積む（次の見出しの親候補になる）
具体例
以下の見出しを処理する流れを見てみましょう：
1
2
3
4
| H1: はじめに
H2: 第1章
H3: セクション1.1
H2: 第2章
|
| ステップ | 処理する見出し | スタックの状態 | アクション |
|---|
| 1 | H1: はじめに | [H1] | ルートとしてスタックに積む |
| 2 | H2: 第1章 | [H1, H2] | H1の子として追加、スタックに積む |
| 3 | H3: セクション1.1 | [H1, H2, H3] | H2の子として追加、スタックに積む |
| 4 | H2: 第2章 | [H1, H2] | H3, (前のH2)をポップ、H1の子として追加 |
TOCParserクラスの実装
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| package TOCParser;
use v5.36;
use Moo;
use SectionHeading;
use LeafHeading;
has 'headings' => (
is => 'ro',
required => 1,
);
has 'root' => (
is => 'lazy',
builder => '_build_root',
);
sub _build_root ($self) {
# 仮想ルート（レベル0）を作成
my $root = SectionHeading->new(
level => 0,
text => 'ROOT',
);
my @stack = ($root);
for my $h ($self->headings->@*) {
my $level = $h->{level};
my $text = $h->{text};
# スタックから、自分より浅いレベルの見出しを探す
while (@stack > 1 && $stack[-1]->level >= $level) {
pop @stack;
}
# 親を取得
my $parent = $stack[-1];
# 新しい見出しを作成（常にSectionHeadingとして作成）
my $new_heading = SectionHeading->new(
level => $level,
text => $text,
);
# 親の子として追加
$parent->add_child($new_heading);
# スタックに積む
push @stack, $new_heading;
}
return $root;
}
sub render ($self) {
my @lines;
for my $child ($self->root->children->@*) {
push @lines, $child->render;
}
return join("\n", @lines);
}
1;
|
コードの解説
仮想ルート
1
2
3
4
| my $root = SectionHeading->new(
level => 0,
text => 'ROOT',
);
|
レベル0の「仮想ルート」を作成します。これにより、複数のH1があっても統一的に扱えます。
スタック操作
1
2
3
| while (@stack > 1 && $stack[-1]->level >= $level) {
pop @stack;
}
|
現在の見出しより深いまたは同レベルの見出しをスタックからポップします。条件@stack > 1は、仮想ルートを残すためです。
$stack[-1]: スタックの最後の要素（Perl では負のインデックスで末尾から参照）pop @stack: スタックから要素を取り除く
親への追加
1
2
3
| my $parent = $stack[-1];
$parent->add_child($new_heading);
push @stack, $new_heading;
|
スタックの先頭（残った中で最も深い）が親。子として追加し、自分もスタックに積む。
レンダリング
1
2
3
4
5
6
7
| sub render ($self) {
my @lines;
for my $child ($self->root->children->@*) {
push @lines, $child->render;
}
return join("\n", @lines);
}
|
仮想ルートの子要素（実際のH1見出し）をレンダリングします。
使用例
これまでに作成したクラスを組み合わせます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #!/usr/bin/env perl
use v5.36;
use lib '.';
use MarkdownReader;
use HeadingExtractor;
use TOCParser;
my $reader = MarkdownReader->new(
filepath => 'sample.md',
);
my $extractor = HeadingExtractor->new(
lines => $reader->lines,
);
my $parser = TOCParser->new(
headings => $extractor->headings,
);
say "目次:";
say $parser->render;
|
実行結果
1
2
3
4
5
| 目次:
- はじめに
- 第1章
- セクション1.1
- 第2章
|
自動的にツリー構造が構築され、正しい階層でレンダリングされました！
エッジケースへの対応
レベルがスキップされるケース
H2を飛ばしてH3が来た場合でも、アルゴリズムは正しく動作します。H3はH1の直接の子として追加されます。
複数のH1
1
2
3
4
| # 第1部
## 章1
# 第2部
## 章2
|
仮想ルート（レベル0）があるため、複数のH1も正しく処理できます。
関連：Iteratorパターンとのツリー走査
ツリー構造の走査（トラバース）は、Iteratorパターンとも関連します：
Compositeパターンはツリー構築、Iteratorパターンはツリー走査を担当します。
完成コード
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| package TOCParser;
use v5.36;
use Moo;
use SectionHeading;
use LeafHeading;
has 'headings' => (
is => 'ro',
required => 1,
);
has 'root' => (
is => 'lazy',
builder => '_build_root',
);
sub _build_root ($self) {
my $root = SectionHeading->new(
level => 0,
text => 'ROOT',
);
my @stack = ($root);
for my $h ($self->headings->@*) {
my $level = $h->{level};
my $text = $h->{text};
while (@stack > 1 && $stack[-1]->level >= $level) {
pop @stack;
}
my $parent = $stack[-1];
my $new_heading = SectionHeading->new(
level => $level,
text => $text,
);
$parent->add_child($new_heading);
push @stack, $new_heading;
}
return $root;
}
sub render ($self) {
my @lines;
for my $child ($self->root->children->@*) {
push @lines, $child->render;
}
return join("\n", @lines);
}
1;
|
まとめ
今回は、スタックベースのアルゴリズムで、見出しの配列からツリー構造を自動構築するTOCParserクラスを実装しました。
学んだこと：
- スタックを使った親子関係の追跡
- 仮想ルート（レベル0）による複数ルート要素の統一的扱い
- Compositeパターンと組み合わせた自動的なツリー構築
- 条件分岐に頼らないアルゴリズム設計
次回は、同じツリー構造からHTML形式やJSON形式など、複数のフォーマットで目次を出力する機能を実装します。
