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

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

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

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

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

集合を使う方法

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

<!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 を使って次のように表せます。

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.

このステップ関数を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 （表示）になるので、次のように簡略化できます。

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 は次のようになります。

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

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つ程度のページ番号を得るためにそれだけの計算が必要でしょうか？

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

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に書き起こすと次のようになります。

<!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億ページあってもサクサクです。