ライブラリなしでページネーションを実装する

一般的にページネーションはライブラリやフレームワークの標準機能を利用して実装するため、アルゴリズムを意識することは少ないと思います。
本稿ではページネーションをライブラリやフレームワークを使わずに独自実装する方法を紹介します。

今回実装するページネーションは次のようなものです。

![pagination](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/72814/bb4345c3-4113-87e8-3740-309c3b750c3a.gif)

全ページを表示するのではなく、開いているページに合わせて特定のページが省略されて表示されます。

当初、[集合を使う方法](#集合を使う方法)がエレガントに思えたのですが、計算効率の悪さが気になりました。
そこで、[計算量を最適化した方法](#計算量を最適化した方法)を加筆しました。
結果的にこちらの方が可読性も計算効率も高くなりました。
導出過程を飛ばして結論を先に知りたい方は[計算量を最適化した方法](#計算量を最適化した方法)からご覧ください。

## 集合を使う方法

先にソースコード全体を載せます。

```html
<!DOCTYPE html>
<html>
  <head>
    <style>
      #pagination li {
        float: left;
        list-style: none;
        border: 1px solid #CCC;
        border-left: none;
        text-align: center;
        padding: 5px;
        width: 20px;
      }
      #pagination li:first-child {
        border-left: 1px solid #CCC;
        border-radius: 5px 0 0 5px;
      }
      #pagination li:last-child {
        border-radius: 0 5px 5px 0;
      }
      #pagination a {
        color: #00e;
        text-decoration: none;
      }
    </style>
  </head>
  <body>
    <ul id="pagination"></ul>
    <script>
      function step(x, c, n) {
        return (
          x === 1 ||
          x === n ||
          (c <= 4 && x <= 5) ||
          (c > 4 && c <= n - 4 && (c - 1 <= x && x <= c + 1)) ||
          (c > n - 4 && x >= n - 4)
        );
      }

      function compress(x, i, pages) {
        return i === 0 || pages[i - 1] !== x;
      }

      // 合計ページ数
      const total = 10;

      // URLパラメーター
      const params = new URLSearchParams(location.search);

      // 現在のページをURLパラメーターから取得
      const currentPage = Number(params.get('page') || 1);

      const pages = [];
      for (let i = 0; i < total; i++) {
        const x = i + 1;
        pages.push(x * step(x, currentPage, total));
      }

      const elm = document.getElementById('pagination');
      elm.innerHTML = pages
        .filter(compress)
        .map((num) => {
          if (num === currentPage) {
            // 現在のページ
            return `<li>${num}</li>`;
          }
          if (num) {
            return `<li><a href="?page=${num}">${num}</a></li>`;
          }
          // numが0のとき
          return '<li>...</li>';
        })
        .join('');
    </script>
  </body>
</html>
```

省略される非表示のページを 0 、現在のページを *c* 、最後のページを *n* とすると、ページの集合 *P* はステップ関数 *u* を使って次のように表せます。

```math
P = \{ u(x)\ x\ |\ x \in N,\ 1 \le x \le n \} \\
c \le 4\ のとき \\
u(x) = \left\{
\begin{array}{ll}
1 & (x \le 4\ または\ x = n) \\
0 & (4 \lt x \lt n)
\end{array}
\right. \\
4 \lt c \le n - 4\ のとき \\
u(x) = \left\{
\begin{array}{ll}
1 & (x = 1\ または\ c - 1 \le x \le c + 1 \ または\ x = n) \\
0 & (1 \lt x \lt c - 1\ または\ c + 1 \lt x \lt n)
\end{array}
\right. \\
n - 4 < c\ のとき \\
u(x) = \left\{
\begin{array}{ll}
1 & (x = 1\ または\ n - 4 \le x) \\
0 & (1 \lt x \lt n - 4)
\end{array}
\right.
```

![map](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/72814/5822b2ec-acb7-8cca-af89-f8956526af12.png)

このステップ関数をJavaScriptに書き直すと、

```javascript
function step(x, c, n) {
  return (
    (c <= 4 && (x <= 4 || x === n)) ||
    (c > 4 && c <= n - 4 && (x === 1 || (c - 1 <= x && x <= c + 1) || x === n)) ||
    (c > n - 4 && (x === 1 || x >= n - 4))
  );
}
```

となります。

さらに `x === 1` のときと、 `x === n` のときは必ず `true` （表示）になるので、次のように簡略化できます。

```javascript
function step(x, c, n) {
  return (
    x === 1 ||
    x === n ||
    (c <= 4 && x <= 4) ||
    (c > 4 && c <= n - 4 && (c - 1 <= x && x <= c + 1)) ||
    (c > n - 4 && x >= n - 4)
  );
}
```

このステップ関数と `x` を掛け合わせることで得られる集合 *P* は次のようになります。

![pages](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/72814/b4840032-9792-5d64-964c-ff4d40a943dc.png)

連続した0を圧縮して1つにまとめるために、次のようにcompress関数を定義します。

```javascript
function compress(x, i, pages) {
  return i === 0 || pages[i - 1] !== x;
}
```

*P* ( i - 1 ) が *P* ( i ) と異なるとき `true` を返し、同じとき `false` を返します。
このcompress関数で *P* をフィルタリングして、描画処理を入れれば完成です。

1度のループで効率よく書くこともできますが、可読性を考えてあえて分割しました。

## 計算量を最適化した方法

さて、合計ページ数が100個程度なら前述の方法で問題になりませんが、1万ページならどうでしょう？
今のPCなら大丈夫？
じゃあ、1億ページなら？

次に考える必要があるのが計算量です。
前述の方法では全探索になってしまうため、ループをまとめても計算量がO(n)になります。
しかし、よく見てください、5つ程度のページ番号を得るためにそれだけの計算が必要でしょうか？

![pagination](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/72814/bb4345c3-4113-87e8-3740-309c3b750c3a.gif)

1と10と現在のページ周辺以外必要ないはずです。
具体的には、

```math
c < 5 のとき、P = \{ 1, 2, 3, 4, 5, 0, n \} \\
c > n - 4 のとき、P = \{ 1, 0, n - 4, n - 3, n - 2, n - 1, n \} \\
5 \le c \le n - 4 のとき、P = \{ 1, 0, c - 1, c, c + 1, 0, n \}
```

です。

これを改めてJavaScriptに書き起こすと次のようになります。

```html
<!DOCTYPE html>
<html>
  <head>
    <style>
      #pagination li {
        float: left;
        list-style: none;
        border: 1px solid #CCC;
        border-left: none;
        text-align: center;
        padding: 5px;
        width: 20px;
      }
      #pagination li:first-child {
        border-left: 1px solid #CCC;
        border-radius: 5px 0 0 5px;
      }
      #pagination li:last-child {
        border-radius: 0 5px 5px 0;
      }
      #pagination a {
        color: #00e;
        text-decoration: none;
      }
    </style>
  </head>
  <body>
    <ul id="pagination"></ul>
    <script>
      function pages(c, n) {
        if (c < 5) {
          return [1, 2, 3, 4, 5, 0, n];
        }
        if (c > n - 4) {
          return [1, 0, n - 4, n - 3, n - 2, n - 1, n];
        }
        return [1, 0, c - 1, c, c + 1, 0, n];
      }

      // 合計ページ数
      const total = 10;

      // URLパラメーター
      const params = new URLSearchParams(location.search);

      // 現在のページをURLパラメーターから取得
      const currentPage = Number(params.get('page') || 1);

      const elm = document.getElementById('pagination');
      elm.innerHTML = pages(currentPage, total)
        .map((num) => {
          if (num === currentPage) {
            // 現在のページ
            return `<li>${num}</li>`;
          }
          if (num) {
            return `<li><a href="?page=${num}">${num}</a></li>`;
          }
          // numが0のとき
          return '<li>...</li>';
        })
        .join('');
    </script>
  </body>
</html>
```

これなら1億ページあってもサクサクです。