TypeScript の陥りやすい罠

TypeScript の陥りやすい罠

Oreilly の Effective Typescript を読んだ。説明が簡潔でわかりやすく、章の構成も読みたいところだけ読めば良いようになっており、すらすら読める。対象読者層はある程度 TypeScript を使っており、ひと通りの機能を触ったことがある人だと思う。全くの初心者はまず Handbookを一通り眺めてみることをおすすめする。本書籍はTypeScript本の一冊目として手に取るものではない。

2 年くらい TypeScript を使っているが意外と詳しく知らない動作やうろ覚えだった機能についても書かれており、参考になった。Conditional TypesやUtility Typesについては薄めだったのは残念。

本書を読んだ上で、Handbook で気になる部分を再度読み直したり、TypeScript リポジトリの Issue を読むことで浮かび上がってきた、 TypeScript を使う際に気をつけるべき点、他の静的型言語とは異なる点をいくつかまとめておく。(なので本書に載っていないものもある)

動作確認は TypeScript v4.1.5 で行った。

削除される型

TypeScript の型情報は JavaScript コードには一切残らない。

そのため、型に対してtypeofinstanceofなどの JavaScript 上の値を扱う演算子を使うことはできない。

Playground Link

interface Square {
  width: number;
}

interface Rectangle {
  height: number;
  width: number;
}

function getArea(shape: Square | Rectangle) {
  if (typeof shape === Square) {
    // 'Square' only refers to a type, but is being used as a value here.(2693)
  }
  if (shape instanceof Rectangle) {
    // 'Rectangle' only refers to a type, but is being used as a value here.(2693)
  }
}

上記コードのように Union 型のメンバを判別したい場合は、in演算子を使い、オブジェクトが固有のプロパティを持っているかどうかで判別するか:

Playground Link

interface Square {
  width: number;
}

interface Rectangle {
  height: number;
  width: number;
}

function getArea(shape: Square | Rectangle) {
  if ("height" in shape) {
    shape; // (parameter) shape: Rectangle
  } else {
    shape; // (parameter) shape: Square
  }
}

"タグ"付きの Union として Union のメンバに共通するプロパティをもたせることで判別する。下記の例では、kindプロパティを持たせている。

Playground Link

interface Square {
  kind: "square";
  width: number;
}

interface Rectangle {
  kind: "rectangle";
  height: number;
  width: number;
}

function getArea(shape: Square | Rectangle) {
  if (shape.kind === "square") {
    shape; // (parameter) shape: Square
  } else {
    shape; // (parameter) shape: Rectangle
  }
}

ちなみにclass構文は、同時にinterface型を作成するため、次のコードは正しい:

Playground Link

class Square {
  constructor(public width: number) {
    this.width = width;
  }
}

class Rectangle {
  constructor(public width: number, public height: number) {
    this.width = width;
    this.height = height;
  }
}

function getArea(shape: Square | Rectangle) {
  if (shape instanceof Square) {
    shape; // (parameter) shape: Square
  } else {
    shape; // (parameter) shape: Rectangle
  }
}

keyof Union は never 型

keyofは型にアクセス可能なプロパティのキーを返す。共通のプロパティを持たない型同士の Union であれば、その型にアクセス可能なプロパティキーは存在しないので、neverとなる。

Playground Link

GitHub Issue

interface Person {
  name: string;
}
interface Lifespan {
  birth: Date;
  death?: Date;
}
type UnionKey = keyof (Person | Lifespan); // never
type IntersectionKey = keyof (Person & Lifespan); // "name" | "birth" | "death"

これは以下のコードが型エラーになるのと同じ理由

Playground Link

interface Person {
  name: string;
}
interface Lifespan {
  birth: Date;
  death?: Date;
}

declare const personOrLifespan: Person | Lifespan;
if (personOrLifespan.name) {
  // Property 'name' does not exist on type 'Person | Lifespan'. Property 'name' does not exist on type 'Lifespan'.
}

personOrLifespanの型は、以下の型 ではない

type PersonOrLifespan = {
  name?: string;
  birth?: Date;
  death?: Date;
}

オブジェクトは単一の厳密な型を作成しない

Handbook

Playground Link

interface Person {
  name: string;
  age: number;
  address: string;
}

interface Animal {
  name: string;
  age: number;
}

function callAnimal(animal: Animal) {
  console.log(`${animal.name}`);
}

const person: Person = { name: "John", age: 22, address: "12345" };
callAnimal(person); // Animal型の引数にPerson型のオブジェクトを割り当てることができる

TypeScript のオブジェクトは単一の厳密な型を作成しない。構造的型システムである TypeScript において、オブジェクトの形状の一部分が型の形状と一致すれば、そのオブジェクトは型に割り当てることができると判断される。

上記コードでいえば、name: stringage: number;のプロパティを持つオブジェクトはAnimal型でもあるとみなされる。

"exccess property checking"はオブジェクトリテラルの作成時にしか発生しない

次のコードは、構造的型システムの観点からすれば正しいように思える。animalオブジェクトはAnimal型に必要なすべてのプロパティを持っているし、プロパティの値の型も間違っていない。しかし、TypeScript は型エラーを警告してくれる。

interface Animal {
  name: string;
  age: number;
}

const animal: Animal = {
  name: "John",
  age: 22,
  address: "12345", // Type '{ name: string; age: number; address: string; }' is not assignable to type 'Animal'. Object literal may only specify known properties, and 'address' does not exist in type 'Animal'.
};

これは"exccess property checking"と呼ばれるチェック機能によるもので、オブジェクトリテラルを作成したときのみに動作し、不要なプロパティの存在やプロパティ名をタイプミスしていないか検証してくれる。

以下のコードでは"exccess property checking"は起こらない。

Playground Link

interface Animal {
  name: string;
  age: number;
}

const animal = {
  name: "John",
  age: 22,
  address: "12345",
};

const obj: Animal = animal;

type エイリアスと interface の違い

  • interfaceUnion型を拡張できない。一度typeを経由する必要がある

Playground Link

interface Square {
  width: number;
}

interface Rectangle {
  height: number;
  width: number;
}

type TSquareOrRectangle = Square & Rectangle;

interface IShape extends TSquareOrRectangle {}
  • interfaceでは Named Tuple が表現できない

TypeScript のテストケースを探ったりコミッターに聞いてみたりしたができないっぽい

Handbook

Playground Link

type TLocation = [lat: number, long: number]; // [lat: number, long: number]

interface ILocation extends Array<number> {
  0: number;
  1: number;
  length: 2;
}

const location1: TLocation = [1, 2];
location1[0]; // (property) 0: number (lat)

const location2: ILocation = [1, 2];
location2[0]; // (property) ILocation[0]: number

interfaceは"declaration merging"が可能

interfaceの型宣言を結合する。例えば TypeScript のコンパイラオプションlibes2016を指定すると、"declaration merging"によって既存の型に新しい ECMA のメソッドが追加される。

混乱のもとになるので、巨大なライブラリの製作者でなければ、この機能はあまり使用しなくて良いと思われる。別の名前で個別に型を定義し、拡張することをおすすめする。

Playground Link

interface Rectangle {
  height: number;
}

interface Rectangle {
  width: number;
}

const rectangle: Rectangle = {
  height: 200,
  width: 100,
};

ECMAScript にない言語機能

Enum

Enum は結構癖が強い。通常のenumJavaScript オブジェクトに変換されるのに対して、const enumは TypeScript の型システム上でしか存在しない。

Playground Link

enum FlavorEnum {
  VANILLA = 1,
  CHOCOLATE = 2,
  STRAWBERRY = 99,
}

let flavorEnum = FlavorEnum.CHOCOLATE;
FlavorEnum[0]; // <- indexでアクセスできてしまう

const enum FlavorConstEnum {
  VANILLA = 1,
  CHOCOLATE = 2,
  STRAWBERRY = 99,
}

let flavorConstEnum = FlavorConstEnum.CHOCOLATE;
FlavorConstEnum[0]; // A const enum member can only be accessed using a string literal.(2476)

文字列を割り当てる(string enum)こともできるが、これは構造的型システムの TypeScript の中でも特殊なふるまいになる。構造的型システムからすれば下記のflavorは文字列リテラル型の"strawberry"を受け入れても良さそうだが、型エラーが発生する:

Playground Link

enum FlavorEnum {
  VANILLA = "vanilla",
  CHOCOLATE = "chocolate",
  STRAWBERRY = "strawberry",
}

let flavor = FlavorEnum.CHOCOLATE;
flavor = "strawberry"; // Type '"strawberry"' is not assignable to type 'FlavorEnum'.(2322)

下記画像のように Enum のメンバにコメントを付けたい、とかでなければ文字列リテラルの Union を使ったほうが良い:

image

Playground Link

type FlavorUnion = "vanilla" | "chocolate" | "strawberry";

let flavor: FlavorUnion = "vanilla";

TypeScript のソースコードを読んでみると、ビットによるフラグ管理に Enum が使われていることが分かる。おそらくはこのために Enum が導入されたのだろう。

ビット演算子を使うと複数のメンバを持つメンバがかなり書きやすい。

Playground Link

// ビット演算時、数値は32ビットの整数値に変換される
const enum Flavor {
  /** 1 (32ビットの整数値: 0000 0000 0000 0000 0000 0000 0000 0001) */
  VANILLA = 1 << 0,
  /** 2 (32ビットの整数値: 0000 0000 0000 0000 0000 0000 0000 0010) */
  CHOCOLATE = 1 << 1,
  /** 4 (32ビットの整数値: 0000 0000 0000 0000 0000 0000 0000 0100) */
  STRAWBERRY = 1 << 2,
  /** 7 (32ビットの整数値: 0000 0000 0000 0000 0000 0000 0000 0111) */
  All = VANILLA | CHOCOLATE | STRAWBERRY,
}

function order(flavor: Flavor) {
  if (flavor & Flavor.VANILLA) {
    throw new Error("VANILLA is out of stock!");
  }
}

let chocolate = Flavor.CHOCOLATE;
order(chocolate);

let all = Flavor.All;
order(all); // Error: VANILLA is out of stock!

let vanilla = Flavor.VANILLA;
order(vanilla); // Error: VANILLA is out of stock!

コンパイルされた JS コードにも全く無駄がない。ソースコードの圧縮にも一役買っているようだ:

"use strict";
function order(flavor) {
    if (flavor & 1 /* VANILLA */) {
        throw new Error("VANILLA is out of stock!");
    }
}
let chocolate = 2 /* CHOCOLATE */;
order(chocolate);
let all = 7 /* All */;
order(all); // Error: VANILLA is out of stock!
let vanilla = 1 /* VANILLA */;
order(vanilla); // Error: VANILLA is out of stock!

複雑なEnumを持たない通常のアプリ規模では必要ないテクニックだが、置き換えができないケースもあることは知っておくべきだろう。

Decorator

experimentalDecoratorsオプションを指定すれば TypeScript でも Decorator は使用できるが、避けるべき。TC39でも仕様は定まっていない。加えて TypeScript で使用できる Decorator の実装は 2014 年の提案のものであり、将来的に実装に破壊的変更が入る可能性が高い。

Angular や NestJS では当たり前のように Decorator を使っているが、対応に追われそうだ。

type-widening

TypeScript の型の推論はとても賢く、いちいち型注釈を付けなくても型が付くという安心を得られる。しかしそれゆえに、混乱を引き起こすケースがある。

次のケースでは、alice変数は文字列リテラル型である"Alice"ではなく、文字列型として推論されるため型エラーが発生する。

Playground Link

type Name = "Alice" | "Bob";

declare function setName(name: Name): void;

setName("Alice");

let alice = "Alice"; // let alice: string
setName(alice); // Argument of type 'string' is not assignable to parameter of type 'Name'.(2345)

これを解消するには、型注釈を使う、あるいはconstにより文字列リテラル型として変数を宣言する:

Playground Link

type Name = "Alice" | "Bob";

declare function setName(name: Name): void;

let alice: Name = "Alice";
setName(alice);

const bob = "Bob";
setName(bob);

type-narrowing

Handbook

control flow analysisのおかげで、型チェッカーが変数の処理を追ってくれるので、型制限を維持したまま、変数に「その時点でもっともあり得る型」が割り当てられる。

Playground Link

function foo(x: string | number | boolean): number | boolean {
  if (typeof x === "string") {
    x; // (parameter) x: string
    x = 1;
    x; // (parameter) x: number
    // x = {}; // ← xはもともと string | number | boolean のUnion型なので、オブジェクトは代入できない Type '{}' is not assignable to type 'string | number | boolean'.
  }
  return x; // (parameter) x: number | boolean
}

ただしunknownに対しては、うまく動作しない。否定型(Negated Type)が導入されればやりようはありそうな気がする。

GitHub Issue

Playground Link

function foo(x: unknown): unknown {
  if (x == null) {
    x; // (parameter) x: unknown (実際は null | undefined)
    x = 1;
    x; // (parameter) x: unknown (実際は数値)
  } else if (isObject(x)) {
    x; // (parameter) x: object | null (実際はオブジェクト)
    x = 2;
    x; // (parameter) x: unknown
  }
  return x; // (parameter) x: unknown
}

function isObject(x: unknown): x is object {
  return typeof x === "object";
}

JavaScript のスーパーセットであるということ

動作するあらゆる JavaScript は、(型エラーが発生するかどうかに関わらず)TypeScript コンパイラを通しても JavaScript に変換され、変わらず動作する。

TypeScript の原理原則として、JavaScript のランタイム動作を決して変更しないというものがある。また一部型システムにおいてもその動作を尊重している。

例えば、以下のコードは TypeScript として正しい。JavaScript では文字列と数値を加算演算子でつなぐと、数値は文字列に型強制される。

TypeScript はこのふるまいを尊重するため型チェッカーはエラーを発生させない。

const x = "1" + 1; // "11"
const y = 1 + "1"; // "11"

しかし、TypeScript はどこかで線引をする。以下のコードは JavaScript の構文的に正しく、ランタイムエラーを発生させないが、TypeScript の型チェッカーは警告を表示する。

const x = 1 + []; // Operator '+' cannot be applied to types 'number' and 'never[]'.(2365)
// JavaScriptでは、結果は 1
const y = 1 + null; // Object is possibly 'null'.(2531)
// JavaScriptでは、結果は 1

線引するポイントは、こうしたコードをプログラマが意図的に書いているかよりもバグの可能性が高いと思われるかどうかだろう。具体的には、配列やnullを数値に加算するコードはプログラマが意図しないもの(バグ)であると TypeScript のコミッターが判断しているのだと思う。

TSをブラウザで実行するためのChrome拡張作った

ブラウザ上でTypeScriptをお手軽に試したいと思ったので作りました

github.com

コードスニペットを選択して拡張のメニューを押すと、そのコードを貼り付けたTS playgroundが開く

image

拡張のアイコンをクリックすると、TSが実行できるポップアップが開くのでGitHubで見かけたコードとかのちょっとした型の確認とかに使う

image

ストアに登録はしてないのでインストールには手間がかかる。

  1. リリースページからdist.zipファイルをダウンロードして解凍する
  2. ブラウザのアドレスバーに"chrome://extensions"と打ち込み、拡張機能ページを開く
  3. 「パッケージ化されていない拡張機能を読み込む」をクリックして解答したフォルダを選択する

TypeScriptでもジェネリクスをインスタンス化したい

C# だとジェネリクスの型パラメータは実行時にも利用できる

using System;  

var factory = new Factory();
factory.LogType<Car>(); // Car

class Car
{
  string color = "red";
}

public class Factory
{   
    public void LogType<T>() {
      Console.WriteLine(typeof(T).Name);
    }
}

TypeScriptによる型はコンパイル時にはすべて取り除かれるため、実行時には利用できない。(typeofで型は取り出せない。)そのためメソッドの引数から推論させ、それを利用する

class Car {
  color = "red";
}

class Factory {
    logType<T>(type: (new () => T)): void {
        console.log(JSON.stringify(new type()))
    }
}

let factory = new Factory();
factory.logType(Car); // "{"color":"red"}" 

TypeScriptは構造的型付けなので、型は構造で表現される。いわゆるダックタイピング

構造的型付けは、一見して直感には反するかもしれない。例えば以下のコードはエラーにならない。CarクラスはEmptyクラスのプロパティをすべて持っているとみなされるため

class Empty {}

class Car {
  color = 'red';
}

let empty: Empty = {};
empty = new Car()

10分で作るSvelteマークダウンエディタ

10分で作るSvelteマークダウンエディタ

参考:

Build a Svelte JS App: Magic Framework (Svelte 3 Tutorial) - Snipcart

Svelteとは

これを見るとSvelteが何なのかだいたい分かる https://youtu.be/AdNJ3fydeao

これを読むとなぜSvelteを作ろうとしたかだいたい分かる https://svelte.dev/blog/virtual-dom-is-pure-overhead

マークダウンエディタを作る

プロジェクトセットアップ

まず雛形を作る:

npx degit sveltejs/template svelte-markdown-editor
cd svelte-markdown-editor && npm i

マークダウンをパースするライブラリを入れる

markedをインストールする:

npm i marked

ローカル開発する

必要なライブラリがインストールされていれば、次のコマンドでrollupが実行される:

npm run dev

App.svelte (1)

App.svelte<script>タグで囲まれた部分を次のように編集する:

<script>
    export let source;
</script>

export let source;で、App.svelteコンポーネントで使用するプロパティを定義している。これにより、親コンポーネントからsource propを渡すことができるようになる。

main.js

main.jsでは、App.svelteコンポーネントをどのように描画するかを設定している。App.svelteは、source propを受け取るので、次のように設定できる:

import App from './App.svelte';

const app = new App({
    target: document.body,
    props: {
        source: '# New document'
    }
});

export default app;

Editor.svelte

テキストエリアを持つ、Editor.svelteを作成する。まずファイルを作成し、次のように編集する:

<script>
    export let source;
</script>

<div class="markdown-editor__left-panel">
    <textarea bind:value={source} class="markdown-editor__source"></textarea>
</div>


<style>
    .markdown-editor__left-panel {
        width: 50%;
        border: solid 1px black;
        height: 90vh;
    }

    .markdown-editor__source {
        border: none;
        width: 100%;
        height: 100%;
    }

    .markdown-editor__source:focus {
        outline: none;
    }
</style>

以下の部分で、bind:valueを使ってsource propが、このテキストエリアの値と"バインド"していることをSvelteに伝える。これにより、親コンポーネントに"テキストエリアの値"(=source prop)が更新したことを伝えられるようになる。

<textarea bind:value={source} class="markdown-editor__source"></textarea>

スタイル(style)に関しては、コンパイルされたファイルを見ると、コンポーネントごとに.svelte-zafbdqのようなハッシュが与えられており、コンポーネントにスコープが閉じられている。

Preview.svelte (1)

マークダウンの入力を受け取り、HTMLとして出力するPreview.svelteを作成する。ファイルを作成して、次のように編集する:

<script>
    import marked from 'marked';
    export let source;
    let markdown = marked(source);
</script>

<div class="markdown-editor__right-panel">
    <div class="markdown-editor__output">{markdown}</div>
</div>

<style>
    .markdown-editor__right-panel {
        width: 50%;
        border: solid 1px black;
        height: 90vh;
        overflow: auto;
    }

    .markdown-editor__output {
        width: 100%;
        padding: 0 2em;
    }
</style>

App.svelte (2)

作成したコンポーネントApp.svelteでひとまとめにする:

<script>
    import Editor from './Editor.svelte'
    import Preview from './Preview.svelte'
    export let source;
</script>

<header class="header">
    <h1 class="header-title">Svelte powered markdown editor</h1>
</header>

<div class="markdown-editor">
    <Editor bind:source={source} />
    <Preview source={source} />
</div>

<style>
    .header {
        height: 10vh;
        display: flex;
        align-items: center;
        justify-content: center;
    }

    .header-title {
        margin: 0;
    }

    .markdown-editor {
        width: 100%;
        display: flex;
        align-items:flex-start;
        justify-content: space-evenly;
    }
</style>

作成したコンポーネントは、そのままインポートし、使用できる。その際、通常のHTMLタグと区別するため、必ず大文字で始める。

import Editor from './Editor.svelte'
import Preview from './Preview.svelte'

Editorのテキストエリアの値とsourceはバインドするので、次のようにする: <Editor bind:source={source} />

一方、Previewではsourceは更新されないため、バインドする必要はない。

この状態で、ブラウザを開いてみると、2点バグが確認できるはず。

  1. PreviewでHTMLが正しくレンダリングできていない
  2. テキストエリアの値を変更しても、Previewの値が更新されない

f:id:uraway:20210114124320p:plain

Preview.svelte (2)

1つ目のバグを解消するには、次のようにSvelteが用意した特別なタグである@htmlタグを変数の前に付けることで、markdownのHTMLを直接描画させる。

<div class="markdown-editor__output">{@html markdown}</div>

2つ目のバグは、markdownの値が、sourceが更新されても再計算されていないことによる。

下記では、JavaScriptの標準構文であるラベル付き文を使って、markdown変数が"再計算される値"であることをSvelteに伝える[^1]。ReactのuseEffect内でstateを変更するふるまいに近いが、deps(依存)を自由に決めることはできない。

これにより、source propが更新された時に、markdown変数も再計算されるようになる。

$: markdown = marked(source);

もし、次のように通常通り変数を設定してしまうと、markdownは再計算されず、DOMは更新されない。

let markdown = marked(source);
^1

コンパイルされたコード(下記)を見ると、ダーティーチェックしているだけで、ラベル付き文は使われていないっぽい。構文的にエラーを出さないようにするハック?

$$self.$$.update = () => {
    if ($$self.$$.dirty & /*source*/ 2) {
         $$invalidate(0, markdown = marked(source));
    }
};

TypeScriptで実装するデータ構造

TypeScriptで実装するデータ構造

GitHub - uraway/data-structures.ts at master

TOC

LinkedList

LinkedListは、各要素が次の要素を参照を持っているシーケンスなデータ構造です。配列と似た形でデータを保存しますが、インデックスによるアクセスは苦手で、時間計算量は配列がO(1)であるのに対して、LinkedListは最悪O(n)です。

仕様

  • push(value) - O(1): データを追加する
  • pop() - O(1): 最後に追加されたデータを削除する
  • find(index) - O(n): indexの要素を検索する
  • findBy(callback) - O(n): 要素を検索する
  • insertAt(index) - O(n): indexに要素を追加
  • removeFrom(index) - O(n): indexの要素を削除

実装

export class LinkedListNode<T> {
  value: T;
  nextNode: LinkedListNode<T> | null;

  constructor(value: T, next = null) {
    this.value = value;
    this.nextNode = next;
  }
}

export class LinkedList<T> {
  headNode: LinkedListNode<T> | null = null;
  tailNode: LinkedListNode<T> | null = null;
  length = 0;

  constructor(values: T[]) {
    values.forEach((value) => this.push(value));
  }

  // 要素を最後尾に追加
  // O(1)
  push(value: T): LinkedListNode<T> {
    const newNode = new LinkedListNode<T>(value);

    // LinkedListがemptyの場合
    if (!this.headNode || !this.tailNode) {
      this.headNode = newNode;
      this.tailNode = newNode;
    } else {
      this.tailNode.nextNode = newNode;
      this.tailNode = newNode;
    }
    this.length += 1;
    return newNode;
  }

  // 最後尾の要素を削除
  // O(n)
  pop(): LinkedListNode<T> | null {
    const deletedNode = this.tailNode;
    // LinkedListがemptyの場合
    if (this.headNode && this.tailNode) {
      let curentNode = this.headNode;
      while (curentNode !== null) {
        if (curentNode.nextNode) {
          curentNode = curentNode.nextNode;
        } else {
          curentNode == null;
        }
      }
      this.tailNode = curentNode;
      this.length -= 1;
    }

    return deletedNode;
  }

  // indexの要素を検索
  // O(n)
  find(index: number): LinkedListNode<T> | null {
    let currentIndex = 0;
    let currentNode = this.headNode;

    if (index > this.length) {
      throw new Error(`Node index(${index}) does not exist in the list.`);
    }

    while (currentIndex < index) {
      if (currentNode?.nextNode) {
        currentIndex += 1;
        currentNode = currentNode?.nextNode;
      }
    }

    return currentNode;
  }

  // 要素を検索
  // O(n)
  findBy(
    callback: (currentNode: LinkedListNode<T>) => boolean
  ): LinkedListNode<T> | null {
    let currentNode = this.headNode;

    while (currentNode !== null) {
      if (callback(currentNode)) {
        return currentNode;
      }

      if (currentNode?.nextNode) {
        currentNode = currentNode?.nextNode;
      }
    }

    return null;
  }

  // indexに要素を追加
  // O(n)
  insertAt(value: T, index: number): LinkedList<T> {
    if (index > this.length) {
      throw new Error(`Node index(${index}) does not exist in the list.`);
    }

    const newNode = new LinkedListNode(value);
    let currentIndex = 0;
    let currentNode = this.headNode;
    let prevNode = null;

    if (index === 0) {
      newNode.nextNode = this.headNode;
      this.headNode = newNode;
      this.length += 1;
      return this;
    }

    while (currentIndex < index) {
      if (currentNode?.nextNode) {
        currentIndex += 1;
        prevNode = currentNode;
        currentNode = currentNode?.nextNode;
      }
    }

    if (prevNode) {
      newNode.nextNode = currentNode;
      prevNode.nextNode = newNode;
    }

    this.length += 1;
    return this;
  }

  // indexの要素を削除
  // O(n)
  removeFrom(index: number): LinkedList<T> {
    if (index > this.length) {
      throw new Error(`Node index(${index}) does not exist in the list.`);
    }

    let currentIndex = 0;
    let currentNode = this.headNode;
    let prevNode = null;

    if (index === 0 && currentNode?.nextNode) {
      this.headNode = currentNode?.nextNode;
      this.length -= 1;
      return this;
    }

    while (currentIndex < index) {
      if (currentNode?.nextNode) {
        currentIndex += 1;
        prevNode = currentNode;
        currentNode = currentNode?.nextNode;
      }
    }

    if (prevNode?.nextNode && currentNode) {
      prevNode.nextNode = currentNode.nextNode;
    }

    this.length -= 1;
    return this;
  }

  // 値をリストする
  values(): T[] {
    const array = [];
    let currentNode = this.headNode;
    while (currentNode !== null) {
      array.push(currentNode.value);
      currentNode = currentNode.nextNode;
    }

    return array;
  }

  // イテレーター
  *[Symbol.iterator](): Generator {
    let currentNode = this.headNode;
    while (currentNode !== null) {
      currentNode = currentNode.nextNode;
      yield currentNode;
    }
  }
}

const list = new LinkedList([1, 2, 3]);
console.log(list.push(1)); // 1
console.log(list.values()); // [1, 2, 3, 1]
console.log(list.insertAt(10, 1).values()); // [1, 10, 2, 3, 1]
console.log(list.length); // 4
console.log(list.removeFrom(4).values()); // [ 1, 10, 2, 3 ]
console.log(list.find(2)?.value); // 2
console.log(list.find(10)?.value); // Error: Node index(10) does not exist in the list.

Stack

Stackは、LIFO(Last In First Out)のデータ構造です。データを'A','B','C'という順番に入れた場合、'C','B','A'といった順番で取り除くことができます。LinkedListの応用で実装できます。

仕様

  • push(value) - O(1): データを追加する
  • pop() - O(1): 最後に追加されたデータを削除する
  • peek() - O(1): 最後に追加されたデータを返す

実装

export class StackNode<T> {
  value: T;
  nextNode: StackNode<T> | null;

  constructor(value: T, next = null) {
    this.value = value;
    this.nextNode = next;
  }
}

export class Stack<T> {
  headNode: StackNode<T> | null = null;
  length = 0;

  constructor(values: T[]) {
    values.forEach((value) => this.push(value));
  }

  // データを追加する
  // O(1)
  push(value: T): StackNode<T> {
    const newNode = new StackNode(value);
    newNode.nextNode = this.headNode;
    this.headNode = newNode;
    this.length += 1;

    return newNode;
  }

  // 最後に追加されたデータを削除する
  // O(1)
  pop(): StackNode<T> | null {
    const deletedNode = this.headNode;
    if (this.headNode) {
      this.headNode = this.headNode.nextNode;
      this.length -= 1;
    }

    return deletedNode;
  }

  // 最後に追加されたデータを返す
  // O(1)
  peek(): StackNode<T> | null {
    return this.headNode;
  }

  values(): T[] {
    const array = [];
    let currentNode = this.headNode;
    while (currentNode !== null) {
      array.push(currentNode.value);
      currentNode = currentNode.nextNode;
    }

    return array;
  }

  *[Symbol.iterator](): Generator {
    let currentNode = this.headNode;
    while (currentNode !== null) {
      currentNode = currentNode.nextNode;
      yield currentNode;
    }
  }
}

const stack = new Stack([1, 2, 3]);
console.log(stack.push(4).value); // 4
console.log(stack.values()); // [ 4, 3, 2, 1 ]
console.log(stack.pop()?.value); // 4
console.log(stack.pop()?.value); // 3
console.log(stack.peek()?.value); // 2

Queue

Queueは、FIFO(First In First Out)のデータ構造です。データを'A','B','C'という順番に入れた場合、'A','B','C'といった順番で取り除くことができます。LinkedListの応用で実装できます。

仕様

  • enqueue(value) - O(1): データを追加する
  • dequeue() - O(1): 最も古いデータを削除する
  • peek() - O(1): 最も古いデータを返す
export class QueueNode<T> {
  value: T;
  nextNode: QueueNode<T> | null;

  constructor(value: T, next = null) {
    this.value = value;
    this.nextNode = next;
  }
}

export class Queue<T> {
  headNode: QueueNode<T> | null = null;
  tailNode: QueueNode<T> | null = null;
  length = 0;

  constructor(values: T[]) {
    values.forEach((value) => this.enqueue(value));
  }

  // データを追加する
  // O(1)
  enqueue(value: T): QueueNode<T> {
    const newNode = new QueueNode(value);
    if (!this.headNode) {
      this.headNode = newNode;
    }

    if (!this.tailNode) {
      this.tailNode = newNode;
    } else {
      this.tailNode.nextNode = newNode;
      this.tailNode = newNode;
    }
    this.length += 1;

    return newNode;
  }

  // 最初に追加されたデータを削除する
  // O(1)
  dequeue(): QueueNode<T> | null {
    const deletedNode = this.headNode;
    if (this.headNode) {
      this.headNode = this.headNode.nextNode;
      this.length -= 1;
    }

    return deletedNode;
  }

  // 最初に追加されたデータを返す
  // O(1)
  peek(): QueueNode<T> | null {
    return this.headNode;
  }

  values(): T[] {
    const array = [];
    let currentNode = this.headNode;
    while (currentNode !== null) {
      array.push(currentNode.value);
      currentNode = currentNode.nextNode;
    }

    return array;
  }

  *[Symbol.iterator](): Generator {
    let currentNode = this.headNode;
    while (currentNode !== null) {
      currentNode = currentNode.nextNode;
      yield currentNode;
    }
  }
}


const queue = new Queue([1, 2, 3]);
console.log(queue.enqueue(4).value); // 4
console.log(queue.values()); // [ 1, 2, 3, 4 ]
console.log(queue.dequeue()?.value); // 1
console.log(queue.dequeue()?.value); // 2
console.log(queue.peek()?.value); // 3

HashTable

HashTableは、Objectと同じくキーバリューペアでデータを保存します。キーのハッシュ値をインデックスとして、テーブル内にデータを保存します。データを検索する場合は、検索キーをハッシュし、配列にアクセスします。

JavaScriptでは、Object/Mapで事足りるはずなので、自分で実装する必要はありません。

仕様

  • hash(key): キーのハッシュ関数
  • set(key, value) - O(1): 値をハッシュキーで保存する
  • get(key) - O(1): キーから値を取得する

実装

export class HashTable {
  size: number;
  table: Array<unknown>;

  constructor(size: number) {
    this.size = size;
    this.table = [];
  }

  // キーのハッシュ関数
  hash(key: string): number {
    let id = 0;
    for (let i = 0; i < key.length; i++) {
      // キーの各文字列のUnicode値*100
      id += key.charCodeAt(i) * 100;
    }
    // this.sizeの範囲に収める
    return id % this.size;
  }

  // 値をハッシュキーで保存する
  // O(1)
  set(key: string, value: unknown): void {
    const id = this.hash(key);
    this.table[id] = value;
  }

  // 値をハッシュキーから検索して取得する
  // O(1)
  get(key: string): unknown {
    const id = this.hash(key);
    const value = this.table[id];

    return value;
  }
}

const hashTable = new HashTable(100);
hashTable.set('A', 'a');
hashTable.set('B', 'b');
// ハッシュ関数が不完全またはHashTableのサイズが小さい場合、異なるキーから同一のインデックスが生成されることがある
console.log(hashTable.hash('A')); // 0
console.log(hashTable.hash('B')); // 0

// 不正
console.log(hashTable.get('A')); // b
console.log(hashTable.get('B')); // b

ハッシュ関数が不完全またはHashTableのサイズが小さい場合、異なるキーから同一のインデックスが生成されることがあります。これを「衝突」と呼び、解決する方法の一つに、連鎖法があります。

実装には、コンストラクタで定義するtableに、LinkedListを使用します。ハッシュ値が衝突した場合、同一インデックスのLinkedListにデータをpushします。

import { LinkedList, LinkedListNode } from './list';

export class HashTableWithLinkedList {
  size: number;
  table: LinkedList<{ key: string; value: unknown }>[];

  constructor(size: number) {
    this.size = size;
    this.table = Array({ length: size }).map(() => new LinkedList([]));
  }

  // キーのハッシュ関数
  hash(key: string): number {
    let id = 0;
    for (let i = 0; i < key.length; i++) {
      // キーの各文字列のUnicode値*100
      id += key.charCodeAt(i) * 100;
    }
    // this.sizeの範囲に収める
    return id % this.size;
  }

  // 値をハッシュキーで保存する
  // O(1)
  set(key: string, value: unknown): void {
    const id = this.hash(key);
    const linkedList = this.table[id];
    linkedList.push({ value, key });
  }

  // 値をハッシュキーから検索して取得する
  // O(1)
  get(key: string): LinkedListNode<{ key: string; value: unknown }> | null {
    const id = this.hash(key);
    const linkedList = this.table[id];

    return linkedList.findBy((currentNode) => currentNode.value.key === key);
  }
}

const hashTableWithLinkedList = new HashTableWithLinkedList(100);
hashTableWithLinkedList.set('A', 'a');
hashTableWithLinkedList.set('B', 'b');
// キーのハッシュ値は同じ(衝突)
console.log(hashTableWithLinkedList.hash('A')); // 0
console.log(hashTableWithLinkedList.hash('B')); // 0
// 上書きされることはない
console.log(hashTableWithLinkedList.get('A')?.value); // { value: 'a', key: 'A' }
console.log(hashTableWithLinkedList.get('B')?.value); // { value: 'b', key: 'B' }

Tree

Treeは、階層性があるデータを表すのに適したデータ構造です。それぞれのNodeは、自身のデータとほかのNodeへの参照(親子関係)を持ちます。

仕様

Node

  • value: 値
  • parent: 親Nodeへの参照
  • children[]: 子Nodeへの参照

Tree

  • root: ルートNode(親Nodeを持たないNode)への参照
  • traverseWithDepthFirst(): 深さ優先探索(親Nodeから子Nodeへの走査を優先する)
  • traverseWithBreadthFirst(): 幅優先探索(深さが同じNodeの走査を優先する)
  • find(callback, traversal): Nodeを指定した探索方法で検索する
  • add(value, parentValue, traversal): parentValueを指定した探索方法で検索し、その子Nodeとしてvalueを追加する
  • remove(value, parentValue, traversal): parentValueを指定した探索方法で検索し、その子Nodeにvalueがあれば削除する
traverseWithDepthFirst

深さ優先探索では、以下のようなTree構造があった場合走査順は、G -> E -> C -> D -> A -> B -> F とします。

    G
   / \
  E   F
 / \ 
C   D
   / \
  A   B

単純な再帰呼び出しで実装することができます。

traverseWithBreadthFirst

幅優先探索では、以下のようなTree構造があった場合走査順は、G -> E -> F -> C -> D -> A -> B とします。

    G
   / \
  E   F
 / \ 
C   D
   / \
  A   B

子Nodeをキュー(Queue)に登録しておき、現在のNodeを探索したあとで、キューに登録されたNodeを探索することで実装することができます。

実装

import { Queue } from './queue';

export class Node<T> {
  value: T;
  parent: Node<T> | null;
  children: Node<T>[];

  constructor(value: T) {
    this.value = value;
    this.parent = null;
    this.children = [];
  }
}

type Traversal<T> =
  | Tree<T>['traverseWithBreadthFirst']
  | Tree<T>['traverseWithDepthFirst'];

export class Tree<T> {
  root: Node<T>;

  constructor(value: T) {
    this.root = new Node(value);
  }

  // 深さ優先走査
  // O(n)
  traverseWithDepthFirst(callback: (node: Node<T>) => void): void {
    const traverse = (node: Node<T>) => {
      for (let i = 0; i < node.children.length; i++) {
        traverse(node.children[i]);
      }

      callback(node);
    };

    traverse(this.root);
  }

  // 幅優先走査
  // O(n)
  traverseWithBreadthFirst(callback: (node: Node<T>) => void): void {
    const queue = new Queue([this.root]);
    let currentTree = queue.dequeue()?.value;

    while (currentTree) {
      for (let i = 0, length = currentTree.children.length; i < length; i++) {
        queue.enqueue(currentTree.children[i]);
      }

      callback(currentTree);
      currentTree = queue.dequeue()?.value;
    }
  }

  // 指定した値のNodeを検索する
  // O(n)
  find(callback: (node: Node<T>) => void, traversal: Traversal<T>): void {
    traversal.call(this, callback);
  }

  // 指定した値のNodeに新しいNodeを追加する
  // O(n)
  add(value: T, parentValue: T, traversal: Traversal<T>): Node<T> {
    let parentNode = null;
    const newNode = new Node(value);
    this.find((node) => {
      if (node.value === parentValue) {
        parentNode = node;
        parentNode.children.push(newNode);
        newNode.parent = parentNode;
      }
    }, traversal);

    if (!parentNode) {
      throw new Error('Cannot add node to a non-existence parent.');
    }

    return newNode;
  }

  // 指定した親Nodeから指定した値のNodeを削除する
  // O(n)
  remove(value: T, parentValue: T, traversal: Traversal<T>): Node<T> | null {
    let deletedNode: Node<T> | null = null;
    this.find((node) => {
      if (node.value === parentValue) {
        const deletedNodeIndex = node.children.findIndex(
          (node) => node.value === value
        );
        if (!deletedNode) {
          throw new Error('Node to remove does not exist.');
        }
        deletedNode = node.children[deletedNodeIndex];
        node.children.splice(deletedNodeIndex, 1);
      }
    }, traversal);

    return deletedNode;
  }
}

/**
 *     G
 *    / \
 *   E   F
 *  / \
 * C   D
 *    / \
 *   A   B
 */
const tree = new Tree('G');
tree.add('E', 'G', tree.traverseWithBreadthFirst);
tree.add('F', 'G', tree.traverseWithBreadthFirst);
tree.add('C', 'E', tree.traverseWithBreadthFirst);
tree.add('D', 'E', tree.traverseWithBreadthFirst);
tree.add('A', 'D', tree.traverseWithBreadthFirst);
tree.add('B', 'D', tree.traverseWithBreadthFirst);

Heap

Heapとは、子要素は親要素より常に大きいか等しい(または常に小さいか等しい)という制約を持つバイナリーツリー(ノードが持つ子要素が最大2である)構造のことです。ヒープメモリと混同しないように注意が必要です。

ここでは、MinHeap(子要素は親要素より常に小さい)を実装します。

仕様

  • getMin() - O(1): 最小値を返す
  • insert(value) - O(log n): 要素を追加する
  • remove(value) - O(log n): 要素を削除する

add

MinHeapにおいて、Nodeを追加するプロセスを図解してみます。Heapは配列としても表現できます:

1.Node(10)を追加する

Node(10)をルートとして追加します
10

[10]

2.Node(49)を追加する

バイナリーツリーでは、ある要素に新しい要素を追加する際左から追加します
   10
  /
49

[10, 49]

3.Node(26)を追加する

   10
  /  \
49   26

[10, 49, 26]

4.1.Node(13)を追加する

一時的に、Node(49)の子要素として追加します
     10
    /  \
  49   26
 /
13

[10, 49, 26, 13]

配列において、Node(13)のインデックスがn-1であるとき、その親のNode(49)のインデックスはMath.floor((n-1)/2)と表すことができます。

4.2.Node(13)を正しい場所に移動する

13 < 49 なので、Node(13)とNode(49)の場所をスワップします。10 < 13 なのでこれ以上入れ替えません。
     10
    /  \
  13   26
 /
49

[10, 13, 26, 49]

次に、時間計算量を考えます。上記(4)では、要素の入れ替えのためにルートの片側の親要素すべてと比較しました。したがって、時間計算量はMinHeapの高さhです。

MinHeapの要素数と、高さ(h)は次のような関係にあります。

heapの要素数 h
1 1
2 2
3 2
4 3
5 3
6 3
7 3
8 3
9 4
<= [tex: 2k]  k
 \displaystyle
\begin{aligned}
n &\leqq 2^k \\
k &\leqq log_2 n
\end{aligned}

よって時間計算量は、 O(\log n)となります。

remove

次の概念図におけるMinHeapから、特定のNodeを削除するプロセスを見てみましょう:

      10
    /    \
  13      26
 /  \    /  \
33  40  51   69    

[10, 13, 26, 33, 40, 51, 69]

1.1.Node(10)を削除する

最も右(the last Node)を一時的にNode(10)のあった場所に据えます
      69
    /    \
  13      26
 /  \    /
33  40  51

[69, 13, 26, 33, 40, 51]

1.2.Node(69)を正しい場所に移動します

13 < 69 なので、Node(13)とNode(69)の場所をスワップします 
      13
    /    \
  69      26
 /  \    /
33  40  51

[13, 69, 26, 33, 40, 51]

1.3.さらに、Node(69)を正しい場所に移動します

33 < 69 なので、Node(33)とNode(69)の場所をスワップします 
      13
    /    \
  33      26
 /  \    /
69  40  51

[13, 33, 26, 69, 40, 51]

次に、時間計算量を考えます。最も入れ替えのコストが重い場合(最小の要素を削除する場合)を考えてみましょう。addと同じように、MinHeapの高さに比例します。

よって時間計算量は、 O(\log n)となります。

実装

export class MinHeap {
  heap: Array<number>;

  constructor() {
    this.heap = [];
  }

  swap(currentIndex: number, targetIndex: number): void {
    const tmp = this.heap[targetIndex];
    this.heap[targetIndex] = this.heap[currentIndex];
    this.heap[currentIndex] = tmp;
  }

  add(value: number): void {
    // heap arrayの最後尾に要素を追加
    this.heap.push(value);

    const currentIndex = this.heap.length - 1;
    this.heapifyUp(currentIndex);
  }

  remove(value: number): void {
    if (this.heap.length < 1) return;

    for (let index = 0; index < this.heap.length; index++) {
      if (this.heap[index] !== value) continue;

      // 配列の最後尾の要素を削除する
      const lastItem = this.heap.pop() as number;

      // 削除する要素が配列の最後尾ならここで終了
      if (index === this.heap.length - 1) break;

      this.heap[index] = lastItem;
      this.heapifyUp(index);
      this.heapifyDown(index);
    }
  }

  // 対象の要素と親要素を比較してスワップ
  heapifyUp(index: number): void {
    let currentIndex = index - 1;
    const parentIndex = Math.floor((currentIndex - 1) / 2);

    while (
      currentIndex > 1 &&
      this.heap[parentIndex] > this.heap[currentIndex]
    ) {
      this.swap(currentIndex, parentIndex);
      currentIndex = parentIndex;
    }
  }

  // 対象の要素と子要素を比較してスワップ
  heapifyDown(index: number): void {
    let currentIndex = index;
    const currentValue = this.heap[index];

    while (true) {
      let indexToSwap = null;
      const rightChildIndex = (currentIndex + 1) * 2;
      const leftChildIndex = rightChildIndex - 1;
      const rightChild = this.heap[rightChildIndex];
      const leftChild = this.heap[leftChildIndex];

      // rightChildが存在する場合:
      if (rightChild) {
        if (rightChild < currentValue) {
          indexToSwap = rightChildIndex;
        }
      }

      // leftChildが存在する場合:
      if (leftChild) {
        if (leftChild < (indexToSwap === null ? currentValue : rightChild)) {
          indexToSwap = leftChildIndex;
        }
      }

      if (indexToSwap === null) break;

      // スワップ
      this.swap(currentIndex, indexToSwap);
      currentIndex = indexToSwap;
    }
  }
}

Trie

Trie)とは、ノードには自身に対応するプレフィックスがあるツリー構造。詳しくはwiki参照。

例えば、to/tea/tenが端NodeであるTrie構造は次のようになります。

     null
    /  
   t     
 /   \    
to    te
     /   \
    tea  ten    

仕様

  • insert - O(m): 単語を追加する。計算量は文字列の長さm
  • findWords(prefix) - O(m): prefixに続く単語を検索する。計算量は最短でも文字列の長さm

実装

export class TrieNode {
  value: string;
  children: { [x: string]: TrieNode };
  isWord: boolean;

  constructor(value: string, isWord: boolean) {
    this.value = value;
    // オブジェクトにTrieNodeを保存する
    this.children = {};
    this.isWord = isWord;
  }

  addChild(value: string, isWord: boolean): TrieNode {
    this.children[value] = new TrieNode(value, isWord);
    return this.children[value];
  }

  removeChild(value: string): void {
    delete this.children[value];
  }

  // 自身とその子ノードにおいて、単語となる文字列を返す
  getWords(): string[] {
    const results: string[] = [];

    if (this.isWord) results.push(this.value);

    Object.values(this.children).forEach((child) => {
      const words = child.getWords();
      words.forEach((word) => results.push(word));
    });

    return results;
  }
}

export class Trie {
  root: TrieNode;

  constructor() {
    this.root = new TrieNode('', false);
  }

  // 単語を追加する
  insert(word: string): void {
    let currentNode = this.root;

    const characters = Array.from(word);

    let value = '';
    characters.forEach((chr, i) => {
      const isWord = i === characters.length - 1;
      value += chr;
      if (currentNode.children[value]) {
        currentNode = currentNode.children[value];
      } else {
        currentNode = currentNode.addChild(value, isWord);
      }
    });
  }

  // 単語を検索する
  findWords(prefix: string): string[] {
    let currentNode = this.root;
    const results: string[] = [];

    const characters = Array.from(prefix);

    let value = '';
    characters.forEach((chr, i) => {
      value += chr;
      const child = currentNode.children[value];

      if (i === characters.length - 1) {
        child.getWords().forEach((word) => {
          results.push(word);
        });
      }

      currentNode = child;
    });

    return results;
  }
}

BinarySearchTree

「左の子孫の値 ≤ 親 ≤ 右の子孫の値」という制約を持つバイナリツリー。

実装

  • insert - O(log n): 要素を追加する
  • find - O(log n): 要素を検索する

時間計算量は、ツリーの高さがkであるとき、ノード数はk^2より小さいことから、

 \displaystyle
\begin{aligned}
n &\leqq 2^k \\
k &\leqq log_2 n
\end{aligned}

よって時間計算等は O(log n)

仕様

export class BinarySearchTreeNode {
  value: number;
  right: null | BinarySearchTreeNode;
  left: null | BinarySearchTreeNode;

  constructor(value: number) {
    this.value = value;
    this.right = null;
    this.left = null;
  }

  insert(value: number): void {
    if (value === this.value) {
      return;
    }

    if (value < this.value) {
      if (this.left) {
        this.left.insert(value);
      } else {
        const newNode = new BinarySearchTreeNode(value);
        this.left = newNode;
      }
    }

    if (this.value < value) {
      if (this.right) {
        return this.right.insert(value);
      } else {
        const newNode = new BinarySearchTreeNode(value);
        this.right = newNode;
      }
    }
  }

  find(value: number): BinarySearchTreeNode | null {
    if (value === this.value) {
      return this;
    }

    if (value < this.value && this.left) {
      return this.left.find(value);
    }

    if (this.value < value && this.right) {
      return this.right.find(value);
    }

    return null;
  }
}

export class BinarySearchTree {
  root: BinarySearchTreeNode;

  constructor(value: number) {
    this.root = new BinarySearchTreeNode(value);
  }

  // 要素を追加する
  // O(log n)
  insert(value: number): void {
    return this.root.insert(value);
  }

  // 要素を検索する
  // O(log n)
  find(value: number): BinarySearchTreeNode | null {
    return this.root.find(value);
  }
}

Graph

ノード(Vertex)の集合とエッジ(Edge)の集合によるデータ構造です。ノード同士がどのようにエッジによって結ばれるのかの関係を表現します。ベイジアンネットワークやニューラルネットワークの元になるデータ構造です。

   4  -  5  -  1
 /  \      \  /
6     3  -  2

仕様

  • traverseWithDepthFirst(): 深さ優先探索(開始Vertexから次のVertexへの走査を優先する)
  • traverseWithBreadthFirst(): 幅優先探索(開始Vertexから深さが同じVertexの走査を優先する)

traverseWithDepthFirst

スタックを使って、深さ優先探索を実装します。擬似コードは次のようになります。

function traverseWithDepthFirst
  スタック、結果配列、走査済みマップを初期化
  開始Vertexをスタックと走査済みマップに追加
  while スタックが空でない間:
    currentVertexをスタックから取り出す
    currentVertexを結果配列に保存
    adjacencyListからcurrentVertexにつながっているVertexを取り出し、
    各Vertexが走査済みではないなら、走査済みマップとスタックに追加

  return 結果配列

開始Vertexを4とすると、

  1. 4につながるVertexをスタックと走査済みマップに追加 Stack(3, 5, 6) Visited(4, 3, 5, 6) Result(4)
  2. スタックをpopし、6を取り出す。6につながる未走査Vertexはないので次へ Stack(3, 5) Visited(4, 3, 5, 6) Result(4, 6)
  3. スタックをpopし、5を取り出す。5につながる未走査Vertexをスタックと走査済みマップに追加 Stack(3, 1, 2) Visited(4, 3, 5, 6, 1, 2) Result(4, 6, 5)
  4. スタックをpopし、2を取り出す。1につながる未操作Vertexはないので次へ Stack(3, 1) Visited(4, 3, 5, 6, 1, 2) Result(4, 6, 5, 2)
  5. 以後繰り返し

traverseWithBreadthFirst

キューを使って、深さ優先探索を実装します。擬似コードは次のようになります。

function traverseWithBreadthFirst
  キュー、結果配列、走査済みマップを初期化
  開始Vertexをキューと走査済みマップに追加
  while キューが空でない間:
    currentVertexをキューから取り出す
    currentVertexを結果配列に保存
    adjacencyListからcurrentVertexにつながっているVertexを取り出し、
    各Vertexが走査済みではないなら、走査済みマップとキューに追加

  return 結果配列

開始Vertexを4とすると、

  1. キューに3, 5, 6を追加 Queue(3, 5, 6) Result(4, 3, 5, 6)
  2. キューから3を取り出す。3につながる未走査Vertex(2)をキューと走査済みマップに追加。 Queue(5, 6, 2) Result(4, 3, 5, 6, 2)
  3. キューから5を取り出す。5につながる未走査Vertex(1)をキューと走査済みマップに追加。 Queue(6, 2, 1) Result(4, 3, 5, 6, 2, 1)
  4. キューから6を取り出す。6につながる未走査Vertexはない
  5. 以後繰り返し

実装

import { Queue } from './queue';
import { Stack } from './stack';

export class Graph {
  adjacencyList: { [x: string]: string[] };

  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex: string): void {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  addEdge(source: string, destination: string): void {
    if (!this.adjacencyList[source]) {
      this.addVertex(source);
    }
    if (!this.adjacencyList[destination]) {
      this.addVertex(destination);
    }
    this.adjacencyList[source].push(destination);
    this.adjacencyList[destination].push(source);
  }

  removeEdge(source: string, destination: string): void {
    this.adjacencyList[source] = this.adjacencyList[source].filter(
      (vertex) => vertex !== destination
    );
    this.adjacencyList[destination] = this.adjacencyList[destination].filter(
      (vertex) => vertex !== source
    );
  }

  removeVertex(vertex: string): void {
    while (this.adjacencyList[vertex]) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      if (adjacentVertex) {
        this.removeEdge(vertex, adjacentVertex);
      }
    }
    delete this.adjacencyList[vertex];
  }

  // 深さ優先探索
  traverseWithDepthFirst(start: string): string[] {
    const stack = new Stack([start]);
    const result = [];
    const visited: { [x: string]: boolean } = {};
    visited[start] = true;
    let currentVertex;

    while (stack.length) {
      currentVertex = stack.pop()?.value;
      if (!currentVertex) continue;

      result.push(currentVertex);

      this.adjacencyList[currentVertex].forEach((neighbor) => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          stack.push(neighbor);
        }
      });
    }
    return result;
  }

  // 幅優先探索
  traverseWithBreadthFirst(start: string): string[] {
    const queue = new Queue([start]);
    const result = [];
    const visited: { [x: string]: boolean } = {};
    visited[start] = true;
    let currentVertex;

    while (queue.length) {
      currentVertex = queue.dequeue()?.value;
      if (!currentVertex) continue;

      result.push(currentVertex);
      this.adjacencyList[currentVertex].forEach((neighbor) => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.enqueue(neighbor);
        }
      });
    }

    return result;
  }
}

//    4  -  5  -  1
//  /  \      \  /
// 6     3  -  2
const graph = new Graph();
['1', '2', '3', '4', '5', '6'].forEach((vertex) => {
  graph.addVertex(vertex);
});
[
  ['1', '2'],
  ['1', '5'],
  ['2', '5'],
  ['2', '3'],
  ['3', '4'],
  ['4', '5'],
  ['4', '6'],
].forEach(([source, target]) => {
  graph.addEdge(source, target);
});

console.log(graph);
// Graph {
//   adjacencyList: {
//     '1': [ '2', '5' ],
//     '2': [ '1', '5', '3' ],
//     '3': [ '2', '4' ],
//     '4': [ '3', '5', '6' ],
//     '5': [ '1', '2', '4' ],
//     '6': [ '4' ]
//   }
// }

// 深さ優先探索
console.log(graph.traverseWithDepthFirst('4')); // [ '4', '6', '5', '2', '1', '3' ]
// 幅優先探索
console.log(graph.traverseWithBreadthFirst('4')); // [ '4', '3', '5', '6', '2', '1' ]

参考

Next.js API Route: ファイルをサーブする

Next.js API Route: ファイルをサーブする

環境:

  • next: v10.0.1

参考:

getStaticProps

通常、静的ファイルをNext.js上で読み込みたい場合、getStaticPropsを使う。これはサーバーサイドで呼び出されるので、fsなどが使える。

// This function gets called at build time on server-side.
// It won't be called on client-side, so you can even do
// direct database queries. See the "Technical details" section.
export async function getStaticProps() {
  const postsDirectory = path.join(process.cwd(), 'posts')
  const filenames = fs.readdirSync(postsDirectory)

  const posts = filenames.map((filename) => {
    const filePath = path.join(postsDirectory, filename)
    const fileContents = fs.readFileSync(filePath, 'utf8')

    // Generally you would parse/transform the contents
    // For example you can transform markdown to HTML here

    return {
      filename,
      content: fileContents,
    }
  })
  // By returning { props: posts }, the Blog component
  // will receive `posts` as a prop at build time
  return {
    props: {
      posts,
    },
  }
}

ただしgetInitialPropsとコンフリクトするため、このメソッドと同時に使用したい場合は、API Routeからファイルをサーブする方法を模索することになる。

API Routeからファイルをサーブする

相対パスpath.resolveを使えば、ローカルでもVercel上でも動作する。

import { NextApiRequest, NextApiResponse } from "next";
import fs from "fs";
import path from "path";

export default (req: NextApiRequest, res: NextApiResponse): void => {
  res.statusCode = 200;

  const postsDirectory = path.resolve('./public', 'posts')
  const filenames = fs.readdirSync(postsDirectory)

  const posts = filenames.map((filename) => {
    const filePath = path.resolve(postsDirectory, filename)
    const fileContents = fs.readFileSync(filePath, 'utf8')

    return {
      filename,
      content: fileContents,
    }
  })

  res.json({ posts });
};

最初Issueを探っててこれを見つけたがVercel上では動かなかった。バージョンが古くて本番環境のパスが変わったりしたんだろうか

挿入ソートのアルゴリズム

挿入ソートのアルゴリズム

与えられた配列をソートする際、挿入ソートを用いるとする。

与えられた配列を、ソート済みの配列(長さは1)と未ソートの配列に分割する。未ソートの配列の中から一つ選び、ソート済みの配列に挿入する。挿入された値と、隣り合う要素同士を比較し、インデックスを入れ替えながら配列を並び替えていく。

アルゴリズム実装 O(n2)

TypeScript

export function insertionSort(array: number[]) {
    for (let i = 0; i < array.length; i++) {
        let j = i;

        while (j > 0 && array[j] < array[j - 1]) {
            const tmp = array[j];
            array[j] = array[j - 1];
            array[j - 1] = tmp;
            j -= 1;
        }
    }
    return array;
}

Rust

fn insertion_sort(array: &mut Vec<i32>) {
    for i in 0..array.len() {
        let mut j = i;

        while j > 0 && array[j] < array[j - 1] {
            let tmp = array[j];
            array[j] = array[j - 1];
            array[j - 1] = tmp;
            j -= 1;
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn it_works() {
        let mut vec = vec![-96, 11, 0, 45, -2];
        insertion_sort(&mut vec);
        assert_eq!(vec, &[-96, -2, 0, 11, 45]);
    }
}