🌲

Compositeパターンを使ってTOC(目次)を生成する

2022/02/28に公開

はじめに

下記の構成で記事を書きます。

  • Compositeパターンの説明
  • パターンを使ったTOC生成の実装

本文中のコードはtypescriptですが、オブジェクト指向の言語に触れたことがあれば雰囲気で読めると思います。
TOCはtable of contentsの略です。

Compositeパターンの説明

まずはCompositeパターンの説明をば。。。

Compositeパターンは、構造に関するパターンに分類され、木構造を扱うのに長けています。

オブジェクト指向における再利用のためのデザインパターン(改訂版)p.175より

◉目的
部分ー全体階層を表現するために、オブジェクトを木構造に組み立てる。(後略)

部分ー全体階層という言葉がややこしいですが、部分が階層的に連なって最終的に1つの塊となる構造っていうイメージでいます。
Compositeパターンの例をググると、ディレクトリ構造を表現するのにCompositeパターン使っているのをよく見かけます。

Compositeパターンの構造はこんな感じになります!

composite-class
composite-object

後者の図を見るとオブジェクトを木構造に組み立てているのがわかりやすいと思います。

  • Component: CompositeとLeafに共通なインターフェイスを定義する。
  • Composite: 子オブジェクトを持つComponentの実装。子Composite、子Leafを保持し、これらを呼び出す。
  • Leaf: Componentの直接的な実装。Compositeの末端。
  • Client: 一番上の階層にいるCompositeを操作して、Composite内のオブジェクトを操作する。Componentインターフェイスを通じてComposite内のオブジェクトを操作する。

実装はこんな感じになります!

interface Component {
  operation(): void;
}

class Composite implements Component {
  children: Component[]  = [];
  operation(): void {
    this.children.forEach(child => child.operation());
  }
}

class Leaf implements Component {
  operation(): void {
    // do something.
  }
}

で、Compositeパターンには、透過性を優先した設計と、型安全性を優先した設計の2種類の設計があります!
提示したコードは子オブジェクトを管理する方法がないですよね、children: Component[]に子供を出し入れするメソッドがないですよね、これをどうするかで分かれます。

透過性を優先した設計

composite-transparent

Componentに子供を管理するメソッドを定義します。
CompositeもLeafにも子供管理の実装をすることになります。

interface Component {
  operation(): void;
  add(child: Component);
}

class Composite implements Component {
  children: Component[]  = [];
  operation(): void {
    this.children.forEach(child => child.operation());
  }
  add(child: Component) {
    this.children.push(child);
  }
}

class Leaf implements Component {
  operation(): void {
    // do something.
  }
  add(child: Component) { throw new Error("Not Supported Operation."); }
}

Leafは子供を管理しないので、例外を投げるようにします。
子供管理オペレーションをComponentインターフェイスを通じて行える、実装クラスに関係なく透過的に扱える、というのがポイントです。

function doSomething(): void {
  let component: Component = new Composite();
  // Componentインターフェイスを通じて子供を管理できる。
  component.add(new Composite()); 
  component.add(new Leaf());
  component.operation();
}

型安全性を優先した設計

composite-type-safety

Compositeクラスにのみ子供を管理するメソッドを定義します。

interface Component {
  operation(): void;
}

class Composite implements Component {
  children: Component[]  = [];
  operation(): void {
    this.children.forEach(child => child.operation());
  }
  add(child: Component) {
    this.children.push(child);
  }
}

class Leaf implements Component {
  operation(): void {
    // do something.
  }
}

間違えてLeafに対してadd()を呼び出す実装をしたらコンパイル時にエラーが発生するので、安全性が得られます。
実行時にエラーが出て、そこではじめて実装が間違えていることを知る、のではなくその前に知ることができますね。

function doSomething(): void {
  // Compositeクラスを通じてのみ子供管理できる。
  let composite: Composite = new Composite();
  composite.add(new Composite()); 
  composite.add(new Leaf());
  composite.operation();
}

function compileError(): void {
  let leaf: Leaf = new Leaf();
  // ↓ Property 'add' does not exist on type 'Leaf'.ts(2339) って怒られる。
  leaf.add(new Leaf()); 
}

Compositeパターンの説明はこれで終わりにして、パターンを使った実装に入ります。

パターンを使ったTOC生成の実装

TOC生成にCompositeパターン適用できる?

そもそもパターンつかえるのか?TOC(目次)ってどんな感じの構造になってる?っていうのをみていきます。
いくつかのサービスのTOCを見て回りましたが、こんなHTMLがあったら

<h1 id="h1-1">h1-1</h1>
<p>foobar<p>
<h2 id="h2-1">h2-1</h2>
<p>foobar<p>
<h3 id="h3-1">h3-1</h3>
<p>foobar<p>
<h1 id="h1-2">h1-2</h1>
<p>foobar<p>

こんな感じのTOCになります。

<!-- ulはolの場合もある。Zennはol -->
<ul>
  <li><a href="#h1-1">h1-1</a>
    <ul>
      <li><a href="#h2-1">h2-1</a>
        <ul>
          <li><a href="#h3-1">h3-1</a></li>
        </ul>
      </li>
    </ul>
  </li>
  <li><a href="#h1-2">h1-2</a></li>
</ul>

図にしてみるとこうなります。

toc-tree

木構造ですね。Compositeパターンが適用できそうです。
こんなに書かなくても、そういえばそもそもHTMLって木構造だよなぁとか、ひととおり書いてから思いました。木生える🌲

wikipediaより

HTMLは木構造(入子構造)のマークアップ言語であり、形式言語である。

実装

ふたつのフェーズに分けて実装します。

  • 共通的な操作の実装。これまで例示してきたコードのoperation()にあたる。
  • Composite内の構造を管理する操作の実装。これまで例示してきたコードのadd(child)にあたる。

共通操作の実装

TOCのHTMLを生成するのが共通操作になります。
先ほどTOCの構造を図示しましたが、ul, li, aをパターンに当てはめるとそれぞれ、

  • ul -> Composite
  • li -> Composite
  • a -> Leaf

になります。
HTMLを生成する際に、ul, liは内部に子オブジェクトを持ち、この子達の処理を呼び出します。
aは子オブジェクトを持たないので純粋にHTMLを生成します。

interface Component {
  toHtml(): HTMLElement;
}
class Composite implements Component {
  private items: Component[];
  private tag: string;

  // tagにはul or liを渡す
  constructor(tag:string) {
    this.items = [];
    this.tag = tag;
  }
  
  toHtml(): HTMLElement {
    // ul または li を作って、子供オブジェクトのHTML生成結果をappendChild()する。
    let node = document.createElement(this.tag);
    this.items.forEach(item => {
      node.appendChild(item.toHtml());
    })
    return node; 
  }
}
class Leaf implements Component {
  private fragment: string;
  private text: string;
  
  constructor(fragment: string, text: string) {
    this.fragment = fragment;
    this.text = text;
  }
  
  toHtml(): HTMLElement {
    let a = document.createElement('a');
    a.href = '#' + this.fragment;
    a.innerHTML = this.text;
    return a;
  }
}
  • Compositeが内部に持っている子供達items: Toc[]の処理を呼び出している
  • Leafがただただ<a>タグを生成している

ということを見ていただければと思います。

これであとは構造を組み立てて、toHtml()を呼び出せばTOCを作ることができます。
では、組み立てられるように、Composite内の構造を管理する操作の実装を追加します。

Composite内の構造を管理する操作の実装

実装する前に、TOCの構造をもう少し深く理解したいので先ほど図示したものに落書きします。

toc-tree-rakukagi

それぞれの部分において、ulを最上層のノードとして、その下にli,aがくっついてますね。

h1タグへのリンクは、h1タグのリンクを管理するulに、追加する。
h2タグへのリンクは、h2タグのリンクを管理するulに、追加する。
h2タグのリンクを管理するulは、その直前のliに追加する。
h3タグへのリンクは、h3タグのリンクを管理するulに、追加する。
(・・・繰り返し・・・)
といった具合でやれば組み立てられそうです。

子供を追加するメソッドをComposite達に実装します。

interface Component {
  toHtml(): HTMLElement;
  add(item: Component): void; // ★追加
}
class Composite implements Component {
  private items: Component[];
  ...
  add(item: Component): void {
    this.items.push(item);
  }
}
class Leaf implements Component {
  ...
  add(item: Component): void {
    throw new Error("Not supported operation.");
  }
}

先ほど図示&説明した内容で組み立てます。。。

function createToc(): void {
  let rootNode = new Composite('ul');
  let lih1 = new Composite('li');
  lih1.add(new Leaf('h1-1', 'h1-1'));
  rootNode.add(lih1);

  let ulh2 = new Composite('ul');
  let lih2 = new Composite('li');
  lih2.add(new Leaf('h2-1', 'h2-1'))
  ulh2.add(lih2);
  lih1.add(ulh2);

  let ulh3 = new Composite('ul');
  let lih3 = new Composite('li');
  lih3.add(new Leaf('h3-1', 'h3-1'));
  ulh3.add(lih3);
  lih2.add(ulh3);

  let lih1twice = new Composite('li');
  lih1twice.add(new Leaf('h1-2','h1-2'));
  rootNode.add(lih1twice);

  // 一番上の階層のCompositeの操作を呼び出す。
  console.log(rootNode.toHtml().outerHTML);
}

下記の内容がコンソール出力されます(整形済み)。
期待通りの内容です。

<ul>
  <li><a href="#h1-1">h1-1</a>
    <ul>
      <li><a href="#h2-1">h2-1</a>
        <ul>
          <li><a href="#h3-1">h3-1</a></li>
        </ul>
      </li>
    </ul>
  </li>
  <li><a href="#h1-2">h1-2</a></li>
</ul>

TOCを生成するライブラリの紹介

Compositeパターンを使ってTOCを生成するAngularのライブラリを作ったので紹介します。
共通操作の実装は大体一緒ですが、構造を組み立てるとこの実装が違います。TOC生成対象の文書からheadingタグを抜き出して、先頭のタグから順に処理して木構造を組み立てています。

https://www.npmjs.com/package/ngx-toc
https://github.com/HiromasaNojima/ngx-toc/tree/main/projects/ngx-toc/src/lib

参考

GitHubで編集を提案

Discussion