GitHub ActionsでdotfileのCIを回す
以前の記事で、neovimで使うpythonの環境を自動構築するシェルスクリプトを書きましたが、neovim以外でも似たようなことを行うスクリプト群を作成しました。しかし、作ったはいいもののはたしてこれがうまくいくのかということに確証が持てなかったので当然テストしてみたいとなるのですが、実機はもちろん仮想マシン立ててやるのもめんどくさかったので、GitHub Actionsを使ってCIを回してみることにしました。
コード全体は以下にあります。
GitHub Actionsとは
GitHubが提供しているCI実行環境。無料でも多分ある程度までは使える高性能なCI環境です。
ワークフローという単位で定義し、その中に複数のジョブが実行されるというCIツールとしては一般的な構成かと思います。
ジョブは自分で定義したり、マーケットプレイスでプリセットを探すこともできるので、自由度もかなり高いです。
詳細なドキュメントはこちら
initスクリプトの構成
initスクリプト群はMakeコマンドにより起動され、下のように大きく分けて２つの処理を行っています。
#dotfiles/init/linux/Makefile
init:
./install.sh
link:
./link.sh
nvim-package-update:
./python/update.sh
インストールスクリプト
１つめはインストールです。エントリーポイントはdotfiles/init/linux/install.shで、前述のneovimやzsh、dockerなど使うであろうもののインストール処理を行います。
#dotfiles/init/linux/install.sh #!/bin/sh -xeu sudo apt-get update #zshのインストールと設定 ./zsh.sh #英字キーボード用の設定 sudo apt-get -y install fcitx fcitx-mozc #dockerのインストール ./docker.sh #neovimのインストールと設定 ./nvim.sh #python周り ./python/pyenv.sh #albert ./albert.sh #latex ./latex.sh #リンク作成 ./link.sh
上のようにインストールするものごとに細分化したスクリプトファイルに置くことで、可読性・保守性を向上させ、後述する単独テストを可能にしています。
リンク作成スクリプト
２つめはシンボリックリンク作成です。エントリーポイントはdotfiles/init/linux/link.shで、dotfileに入っている設定ファイルを有効化するためにシンボリックリンクをホームディレクトリに作成しています。
#dotfiles/init/linux/link.sh #!/bin/bash -xeu rm -f ~/.gdbinit ln -s ~/dotfiles/gdb/gdbinit ~/.gdbinit rm -f ~/.gitconfig ln -s ~/dotfiles/git/gitconfig ~/.gitconfig rm -f ~/.latexmkrc ln -s ~/dotfiles/latex/latexmkrc ~/.latexmkrc rm -f ~/.tmux.conf ln -s ~/dotfiles/tmux/tmux.conf ~/.tmux.conf rm -f ~/.config/nvim ln -s ~/dotfiles/nvim ~/.config/nvim rm -f ~/.zshrc ln -s ~/dotfiles/zsh/zshrc ~/.zshrc
現在あるリンクを消した上で新しいリンクを張り直します。(install.shの中でもこのスクリプトは読み込まれているのはちょっと設計ミスかも。分けるか少し検討中。)
CI
スクリプト群を解説したところで、本題のCIに入っていきたいと思います。
ワークフローの定義には、.github/workflows以下のymlファイルを使用します。
今回は、init/linux以下に変更が入ったときと、ワークフロー定義が変わったときにテストしてほしいので以下のように書きます。
#.github/workflows/init-test.yml
name: "init script test"
on:
push:
paths:
- '.github/workflows/init-test.yml'
- 'init/linux/**'
#この後にジョブの定義が続く...
jobs:
nameでワークフローの名前を定義、on.push.pathsを指定することでこれらのファイルに変更が入ったpushで発火してくれます。
push以外にも、pull requestなど様々な条件で発火でき、詳細は公式ドキュメントを参照してください。
全体テスト
全体テストのジョブは、全体を通して実行してみてエラーが出なければ良いだけなので非常にシンプルです。
#.github/workflows/init-test.yml jobs: init-test: runs-on: ubuntu-latest steps: - uses: actions/checkout@v2 - name: init working-directory: ./init/linux run: make init - name: link working-directory: ./init/linux run: make link
init-testジョブはruns-onで指定したマシンで実行され、stepsで定義されたステップを実行します。
ベースとして使うactionsはcheckoutのみを行うactions/checkout@v2を使用します。
また、それぞれのステップで実行するコマンドをrunで定義します。ここでは上に挙げたMakefileを叩くだけです。
単体テスト
全体テストだけでもいいのですが、今後インストールスクリプトが大きくなってくると、どこでエラーが起こっているのかなどを把握する必要が出てきます。そのため、それぞれのスクリプトごとに単独でテストするジョブも定義していきます。
行うことはそれぞれのスクリプトファイルを単体で実行するだけですが、これを独立して行うためにジョブを大量に作るのは賢くありません。このようなニーズに応えるために、GitHub Actionsにはmatrixという仕組みがあります。
これは、簡単にいうとリスト内の要素を独立に実行してくれるfor文のようなものです。ここではそれぞれのスクリプトファイルを独立に実行したいので以下のように書きます。
#.github/workflows/init-test.yml jobs: unit-test: runs-on: ubuntu-latest strategy: #これをtrueとしてしまうと、どれか一つエラーになると全部強制終了してしまう fail-fast: false #scriptをキーとして、リスト内の要素が値となるジョブが独立して実行される matrix: script: ["./albert.sh", "./docker.sh","./latex.sh","./nvim.sh","./zsh.sh","./python/pyenv.sh"] steps: - uses: actions/checkout@v2 - name: unit-test of ${{matrix.script}} working-directory: ./init/linux run: ${{matrix.script}} #init-testが下に続く...
matrixの中に、スクリプトファイル名を値とするリストを定義することで以下のように、独立したジョブが複数実行されます。
matrixを使えば、異なるosでテストしたりすることもできます。
注意点
シェルスクリプトがエラーを起こしたときにきちんと終了するように、シェバンには -euをつけましょう。
#!/bin/bash -xeu
これを忘れるとエラーを起こしているのにも関わらず、見た目上は成功しているようになってしまいます。
また、-xもつけると、どのコマンドが実行されたのかわかりやすくなります。
おまけ READMEへのバッジ
よく下のようなテスト結果を示すバッジがREADMEについているところを見たことがあるかもしれません。これはREADMEに以下を埋め込むことで可能です。
pythonでneovimのdenite拡張を作る
neovimにはリモートプラグインというneovim本体とは別のプロセスで動くプラグインがあります。リモートプラグインは、msgpack-rpcという仕様でneovim本体と通信し、通信部分はすべてライブラリがやってくれるので、簡単にプラグインを書くことができ、この記事では内部でリモートプラグインを利用しているdeniteの拡張を作っていきたいと思います。
コード全体は以下にあります。
deniteとは
deniteは、「何か」を集めて一覧で表示し、それに対して「ある動作」を行うことを統一的に行えるプラグインです。例えば現在のディレクトリ以下のファイルを表示し即座にジャンプしたり、ディレクトリ以下に対してgrepした結果を表示してジャンプしたりすることができます。
これらの機能は標準で用意されているものですが、「何か」や「ある動作」に対応するものは自分で定義することもできるため、deniteの機能を拡張することができます。
この「何か」はdenite内ではsource、「ある動作」はkindと呼ばれます。
つまり、deniteの拡張を作るというのはsourceとkindを作ることだと言えます。
この記事では、以下gifのように、競プロなどでよく使うコードスニペットを即座に貼り付けるdenite拡張を書いていきたいと思います。
ディレクトリ構成
コードは {neovimのランタイムパス}/rplugin/python3/denite/source 以下に配置してください。
開発時には、
開発ディレクトリ
|-rplugin
|-python3
|-denite
|-source
| |-clipy.py
|
|-kind
|-clipy.py
のようなディレクトリ構成にして、
:set runtimepath+=開発ディレクトリ :UpdateRemotePlugin
とすれば手元で実行できます。
またリリースする際には、このディレクトリをgithubなどで管理していれば使っているプラグイン管理プラグインなどでリポジトリ名を指定してください。
sourceの作成
簡単な例
前述のように、sourceはどのようなリソースを集めるのかを定義します。
deniteの公式ドキュメントにも書いてありますが、sourceは.base内のBaseクラスを継承したSourceクラスを作ることで定義できます。
このクラスに必要なメソッドはinitとgether_candidatesのみであるので、(何もしませんが)最低限実装したクラスを以下に示します。
from .base import Base class Source(Base): def __init__(self, vim): super().__init__(vim) self.name = 'clipy' self.kind = 'clipy' def gather_candidates(self,context): return [{'word':'candidate1'},{'word':'candidate2'}]
この例では、deniteの候補にcandidate1とcandidate2が表示されたと思います。
このようにsourceの定義では、オブジェクトのリストを返すgather_candidates関数を定義します。 また、オブジェクトは以下のようなフィールドを持ちます。
| フィールド名 | 説明 |
|---|---|
| word | 実際に表示され、検索対象に含まれる文字列 |
| abbr | これが指定されていると、wordではなくこちらの文字列が表示されるが検索はされない |
また、これ以外にも、フィールドは自分で指定できます。
実際に作ったsource
完成したclipyのsourceを以下に示します。
クリックして表示
from .base import Base
import glob
import os
import re
CLIPY_HIGHLIGHT_SYNTAX = [
{'name':'Title','link':'Statement','re':r'.\+\%(:\)\@='},
{'name':'Description','link':'Comment','re':r'\%(:\)\@<=.\+'},
]
class Source(Base):
def __init__(self, vim):
super().__init__(vim)
self.name = 'clipy'
self.kind = 'clipy'
def on_init(self,context):
context['__bufnr'] = str(self.vim.call('bufnr','%'))
context['__filetype'] = str(self.vim.command_output('echo &filetype'))
def gather_candidates(self,context):
candidates = []
clipy_root = self.vim.vars['clipy_root']
clipy_filetype = self.vim.vars['clipy_filetype'].get(context['__filetype'],[])
for filetype in clipy_filetype:
files = glob.glob("{}/**/*.{}".format(clipy_root,filetype),recursive = True)
for file in files:
candidates.extend(self._extract(file))
return candidates
def _extract(self,filename):
entries = []
extracted = []
with open(filename) as f:
lines = f.readlines()
line_count = 1
for line in lines:
match = re.search(r'<denite-clipy>(.*)</denite-clipy>',line)
if match:
entries.append({'body':match.groups()[0],'line':line_count})
line_count = line_count + 1
for i,entry in enumerate(entries):
if i != len(entries) - 1:
body = entry['body']
line_start = entries[i]['line']
line_end = entries[i+1]['line'] -2
extracted.append({'word':body,'__line':"{}:{}".format(line_start,line_end),'action__path':filename})
else:
body = entry['body']
line_start = entries[i]['line']
extracted.append({'word':body,'__line':"{}:{}".format(line_start,len(lines)),'action__path':filename})
return extracted
def highlight(self):
for syn in CLIPY_HIGHLIGHT_SYNTAX:
self.vim.command(
'syntax match {0}_{1} /{2}/ contained containedin={0}'.format(self.syntax_name, syn['name'], syn['re']))
self.vim.command(
'highlight default link {}_{} {}'.format(self.syntax_name, syn['name'], syn['link']))
gather_candidatesでは、g:clipy_rootで指定されたディレクトリ以下のリストg:clipy_filetype内のファイルタイプにマッチするファイルから、
<denite-clipy>スニペット名:説明</denite-clipy>
というタグに挟まれた文字列を取得します。この文字列はwordフィールドに配置され、構文ハイライトされて候補として表示されます。
また、kindでスニペットとして挿入するために、前後のタグの位置から挿入すべき行範囲を取得しています。
例えば、下のようなファイルに対しては以下のようなオブジェクトを返します。
#file.txt <denite-clipy>hoge:hoge</denite-clipy> hogehoge <denite-clipy>fuga:fuga</denite-clipy> fugafuga
[
{'word':'hoge:hoge','__line':"2:3",'action__path':'file.txt'},
{'word':'fuga:fuga','__line':"5:5",'action__path':'file.txt'}
]
行番号が0始まりになっている理由はkindでのputコマンドの仕様がそうだからです。
リモートプラグインからneovimの機能にアクセスするには、self.vimに用意されているapi群を利用します。詳細は ここ を参照してください。(ただし、self.vim.varsなどはドキュメントに書いてないのでソースから調べる必要がありそうです。)
kindの作成
実際に作ったkind
kindは選ばれた候補に対して何を行うのかを定義します。
kindもsourceと同様に、ベースクラスを継承してやる必要があります。
必要なものは_init_とnameであり、それに加えてactionを定義していきます。
kindの方は複雑でないので完成したものを解説していきます。
from denite.base.kind import Base class Kind(Base): def __init__(self, vim): super().__init__(vim) self.name = 'clipy' self.default_action = 'paste' def action_paste(self,context): targets = context['targets'] filename = targets[0]['action__path'] line = targets[0]['__line'] self.vim.feedkeys(":put =readfile('{}')[{}]\n".format(filename,line))
sourceのkindで指定したものをnameに指定することでこのkindで処理を行うことができます。
選択された候補の情報は、context.targetsにリストとして入っています。
今回やるべきはファイル名と行の範囲から貼り付けるという処理なのでputコマンドにreadfileのスライスを食わせることで実現できます。
まとめ
以上で説明したもの以外にも、非同期で候補を集める処理なども書くことができ、汎用性に優れた拡張が書けそうです。
また、リモートプラグインはmsgpack-rpcを使えれば、どんな言語でもneovimの拡張を書くことができる可能性を秘めているのでこれからも調べていきたいと思います。
Neovimのpython環境を一発で自動構築する
私はメインのエディタとしてneovimを使っていますが、一部のプラグイン(deopleteなど)にはpython環境が必要なことがあります。
しかし、pythonのバージョンは使うマシンや環境によって異なるため、同時に複数のマシンで環境を揃えたり、新しいマシンを導入した際に環境構築がめんどくさかったりします。今回はpython仮想環境を用いることで、コマンド一発でneovimのpython環境を構築する方法を紹介します。
私はツールの設定ファイルや環境構築スクリプトをgithubで管理しているので、全体を見たい方は下のリポジトリをご覧ください。
pyenvとvirtualenv
pythonのバージョン管理というとまず思い浮かぶのがpyenvだと思います。
pyenvは使うバージョンを記したversionファイル(globalなら~/.pyenv/version)に応じて実際に呼び出すpython実行ファイルを切り替えます。このことによって、下のように簡単なコマンドでシステム全体や特定のディレクトリ以下で使うバージョンを切り替えることができます。
$ python --version Python 3.8.1 $ pyenv global 2.7.15 $ python --version Python 2.7.15
しかし、neovimは設定ファイルに書かれたパスを参照してpythonを実行しているに過ぎず、このやり方では少し都合がよろしくないです。
この問題を解決するのがvirtualenvです。これは、ディレクトリの中にpythonの実行環境を閉じ込めたもので、使う実行ファイル、ライブラリを完全に固定することができます。
virtualenvを用いたpython環境の作成
neovimの使うpython環境は2系と3系の２つがあり、それぞれの仮想環境を用意していきます。前提として、python2とpython3をpyenvを用いて切り替えることのできる状態にしてあるものとします。(pyenvの導入方法は後述します)
#python3環境を~/nvim-python3ディレクトリに構築 $ pyenv global 3.8.1 $ virtualenv -p python3 ~/nvim-python3 #python2環境を~/nvim-python2ディレクトリに構築 $ pyenv global 2.7.15 $ virtualenv -p python ~/nvim-python2
このコマンドによって~ディレクトリ以下に２つのディレクトリができました。このディレクトリ内にあるactivateファイルをsourceすることでpythonコマンドがその仮想環境内のpythonコマンドを指すようになります。もとのpythonコマンドを参照するようにするためにはdeactivateコマンドを実行します。
$ which python /home/denjo/.pyenv/shims/python #一時的に仮想環境のpythonを使う $ source ~/nvim-python3/bin/activate $ which python /home/denjo/nvim-python3/bin/python #deactivateコマンドでもとに戻る $ deactivate $ which python /home/denjo/.pyenv/shims/python
仮想環境内にneovimに必要なパッケージをインストールするには仮想環境のpythonを有効にした状態でpipを用いてインストールしてください。
$ source ~/nvim-python3/bin/activate
$ pip install pynvim
$ deactivate
同様にpython2用の仮想環境を構築してください。
neovimで使うpythonのパスを設定する
neovimの設定ファイル内に以下のコードを書いてください
let g:python3_host_prog = expand('~/nvim-python3/bin/python3') let g:python_host_prog = expand('~/nvim-python2/bin/python2')
この状態でneovimのcheckhealthを実行すると以下のように正しく仮想環境内のpythonを見てくれていることが解ると思います。
## Python 2 provider (optional) - INFO: pyenv: Path: /home/denjo/.pyenv/libexec/pyenv - INFO: pyenv: Root: /home/denjo/.pyenv - INFO: Using: g:python_host_prog = "/home/denjo/nvim-python2/bin/python2" - INFO: Executable: /home/denjo/nvim-python2/bin/python2 - INFO: Python version: 2.7.15 - INFO: pynvim version: 0.4.1 - OK: Latest pynvim is installed. ## Python 3 provider (optional) - INFO: pyenv: Path: /home/denjo/.pyenv/libexec/pyenv - INFO: pyenv: Root: /home/denjo/.pyenv - INFO: Using: g:python3_host_prog = "/home/denjo/nvim-python3/bin/python3" - INFO: Executable: /home/denjo/nvim-python3/bin/python3 - INFO: Python version: 3.8.1 - INFO: pynvim version: 0.4.1 - OK: Latest pynvim is installed.
環境自動構築
以上を踏まえて、仮想環境の構築をコマンド一発で行ってくれるようにしてみます。
ここでは以下のことを行うシェルスクリプトを用いて自動構築していきます。
- pyenvの導入
- pyenvでpythonをインストール
- 仮想環境を構築
- 使うライブラリのインストール
pyenvの導入
pyenvの導入はリポジトリをクローンすることで行います。
git clone git://github.com/yyuu/pyenv.git ~/.pyenv
このままでは使えないので、使っているシェルの設定ファイルに(bashrc,zshrcなど)以下を書き込んでください。
export PYENV_ROOT="$HOME/.pyenv" export PATH="$PYENV_ROOT/bin:$PATH" eval "$(pyenv init -)"
私はzshrcもリポジトリで管理しているのでcloneしてくれば既に書き込みは終了しています。
pyenvでpythonをインストール
pyenv install 3.8.1 pyenv install 2.7.15
使うライブラリのインストール
仮想環境は前述のように行ったものとします。 pipはrオプションで、インストールしたいライブラリ一覧を記したファイルを読み取ってインストールしてくれます。
このファイルは手動で書いてもいいですし、既存のpipでインストールしたパッケージを複製したい場合はpip freezeコマンドでこのファイルを生成してくれます。
$ pip freeze > requirement.txt $ cat requirement.txt pynvim==0.4.1
#一覧ファイルを使ってインストール pip install -r requirement.txt
結果として、自動構築スクリプトは以下のようになります。
#!/bin/bash #install pyenv git clone git://github.com/yyuu/pyenv.git ~/.pyenv #install 2 and 3 pyenv install 3.8.1 pyenv install 2.7.15 #make virtualenv pyenv global 3.8.1 pip install virtualenv virtualenv -p python3 ~/nvim-python3 pyenv global 2.7.15 virtualenv -p python ~/nvim-python2 pyenv global system #install requirement source ~/nvim-python3/bin/activate pip install -r ~/dotfiles/init/linux/python/nvim-python3-requirements.txt deactivate source ~/nvim-python2/bin/activate pip install -r ~/dotfiles/init/linux/python/nvim-python2-requirements.txt deactivate
このようなスクリプトを一回作ってしまえばどんな環境でも使いまわせるので非常に楽です。
C++による平衡二分木(AVL木)の実装
前の記事でも書きましたが、趣味で下のgif画像のような平衡二分木(AVL木)を実装したので、それについての解説を書いていこうと思います。
コード全体は以下のレポジトリにあります。
二分木について
二分木とは、何らかの大小関係が定まっており、データに重複がないデータの保持に使われるデータ構造です。
定義としては、
- あるノードに着目すると、そのノードは左ノードと右ノードを持つ。(持たないことも可能)
- あるノードに着目すると、そのノードのデータは左ノードのデータよりも大きく、右ノードのデータより小さい。
です。具体的には下図のような木構造になります。
二分木の検索
二分木の検索は、上に述べた定義を使って行い、以下のような疑似コードになります。
注目ノード = 根ノード while(注目ノード != null){ if(注目ノード.データ == 検索するデータ){ return 検索成功 } if(検索するデータ < 注目ノード.データ){ 注目ノード = 注目ノード.左ノード }else{ 注目ノード = 注目ノード.右ノード } } return 検索失敗
このコードでは、根ノードからデータの大小に応じて左右のノードに注目していき、もし注目しているノードのデータが検索したデータと一致していたら検索成功、そうでないなら検索継続としています。そして、それ以上検索することができなかったら検索失敗とします。
二分木の挿入
二分木の挿入は、「そのノードがあるとしたらどの位置にあるのか」ということに着目して行い、以下のような疑似コードになります。
//searchParentは、引数のデータを持つノードがあると仮定し、そのノードの親ノードを返す。今は既にあるノードが挿入されることはないとします。 親ノード = searchParent(挿入するデータ) if(挿入するデータ < 親ノード.データ){ //newNodeは、引数のデータを持つノードを作って返す。 親ノード.左ノード = newNode(挿入するデータ) }else{ 親ノード.右ノード = newNode(挿入するデータ) }
二分木の削除
二分木の削除は、削除されるノードに部分木がある可能性があり、削除した後にそれらを適切に接続しないといけないので検索・挿入よりは複雑になります。
削除されるノードに左部分木がない場合
以下のように削除されるノードを右部分木で置き換えます。
削除されるノードに左部分木がある場合
以下のように削除されるノードのデータを、削除されるノードの左部分木の中で最大なノードのデータに置き換え、そのノードを削除します
以上をまとめると、以下のような疑似コードになります。
//searchNode関数は引数のデータを持つノードを返します。今は削除するデータがないことは考えません 削除されるノード = searchNode(削除するデータ) if(削除するノード.左ノード == ない){ //replace関数は第一引数で指定されたノードを第二引数で指定されたノードで置き換えます replace(削除するノード,削除するノード.右ノード) //delete関数は引数で指定されたノードを削除します delete(削除するノード) }else{ //leftMax関数は引数で指定されたノードの左部分木の中で最大なノードを返します。 左最大ノード = leftMax(削除するノード) 削除されるノード.データ = 左最大ノード.データ delete(左最大ノード) }
二分木の弱点
二分木はデータの検索、挿入、削除をlognオーダーで行うことができますが、この定義のまま実装すると、下のようなケースのときに最悪nオーダーになってしまいます。
- 単調増加するデータが挿入されたとき
- 0,1,-1,2,-2...とデータが挿入されたとき
以上のケースはどれも、あるノードの左右の部分木に偏りが生じてしまうことで起こります。
このようなケースでも性能を保つための工夫を施した実装が平衡二分木の一つであるAVL木です。
AVL木について
木の高さと偏りについて
この記事では部分木の高さを、
- その部分木の根ノードの左右の部分木の高さの最大値+1
- 左右の部分木がない場合、ない方の高さは0とする。
と定義します。
また、部分木の偏りを、
- その部分木の左右の部分木の高さの差(左が大きい時を正)
と定義します。
具体的には以下のようになります。
AVL木の定義
AVL木は以下のように定義されます。
- 木の中のどの部分木に着目しても、その部分木の偏りは -1,0,1のどれかである。
つまり、左のような二分木はAVL木でなく、右のような部分木はAVL木であるということです。
挿入、削除をしてもそれぞれのステップの最後にはAVL木になっている必要があるので、それぞれの操作の際には偏りを直す操作が必要になることがわかると思います。
回転
偏りを直すための操作の基本となるのが回転操作です。回転操作は、前後で二分木であることは維持しつつも、木の形を変える操作で、以下の4つが挙げられます。
左回転、右回転
以下の画像で、右向きの矢印が右回転、左向きの矢印が左回転です。
疑似コードは以下のようになります。
//右回転 bノード = aノード.左ノード Y = aノード.左ノード.右ノード 回転後のルート = bノード aノード.左ノード = Y if (Y != nullNode) { Y.親ノード = aノード } bノード.右ノード = aノード //Replace関数はaノードをルートとする部分木をbノードをルートとする部分木に置き換える Replace(aノード,bノード) aノード.親ノード = bノード return 回転後のルート
//左回転 aノード = bノード.右ノード Y = bノード.右ノード.左ノード 回転後のルート = aノード bノード.左ノード = Y if (Y != nullNode) { Y.親ノード = bノード } aノード.左ノード = bノード Replace(bノード,aノード) bノード.親ノード = aノード return 回転後のルート
左右二重回転
以下の画像が左右二重回転です。bノードに対して左回転を行った後、aノードに対して右回転を行います。
疑似コードは以下のようになります。
//左回転を行う関数 RotateL(aノード.左ノード) return RotateR(aノード)
右左二重回転
以下の画像が右左二重回転です。bノードに対して右回転を行った後、aノードに対して左回転を行います。
疑似コードは以下のようになります。
//右回転を行う関数 RotateL(aノード.右ノード) return RotateL(aノード)
平衡処理
AVL木の条件を常に満たすために、挿入・削除の度に以上の回転操作を使って、二分木の偏りをなくしていきます。 偏りが生じるケースはいくつかに分類され、そのそれぞれで行う回転操作が異なります。
挿入
左部分木の方から挿入された場合と、右部分木の方から挿入された場合では左右対称になっただけなので、ここでは左部分木の方から挿入された場合を考えます。
また、以下では注目するノードをu、uの左の子をv、vの右の子をwとします。
uの偏りが0になるとき
uをルートとする部分木の高さは挿入の前後で変わらないので、それ以上上のノードで平衡処理をする必要はないので、平衡処理を終了します。
uの偏りが1になるとき
uをルートとする部分木の高さは挿入の前後で1増えます。この部分木はAVL木の条件を満たしてはいますが、高さが増えたことにより、上の木でAVLでなくなる可能性があるので注目ノードをuの親ノードにして平衡処理を続けます。
uの偏りが2になるとき
vをルートとする部分木はAVL木であるため、vの偏りは-1,0,1のどれかですが、もし挿入後の偏りが0であったとすると、挿入によってvをルートとする部分木の高さは変わらず、uの偏りが2とならないため、この場合は除かれます。
よって、vの偏りが-1になったときと、1になったときに場合分けして考えます。
vの偏りが1になるとき
下図のAに挿入されたとき、条件より、B,Cはともに高さhです。右回転をして平衡処理をすると、全体として高さは変わらないので平衡処理を終了します。
vの偏りが-1になるとき
wの偏りによって以下の3つにわけられます。
wの偏りが1になるとき
下図のBに挿入されたとき、条件より、A,B,Dは高さh+1,Cは高さhです。左右回転をして平衡処理をすると、全体として高さは変わらないので平衡処理を終了します。
wの偏りが0になるとき
挿入されるノードがwのとき、左右回転をして平衡処理をすると、全体として高さは変わらないので平衡処理を終了します。
wの偏りが-1になるとき
下図のCに挿入されたとき、条件より、A,C,Dは高さh+1,Bは高さhです。左右回転をして平衡処理をすると、全体として高さは変わらないので平衡処理を終了します。
このように、vの偏りが-1のときは、結局左右回転をするので、uの偏りが2のときは二通りの処理になります。
削除
削除するとき上述のような方法で行えば、必ず削除されるのは葉ノードとなります。 また、削除をするということは、「削除した側の高さが1減る」、つまり「削除していない側の高さが1増える」ことであるので、挿入のときとは全く逆の操作をすればいいことになります。
以上をまとめると、挿入時の平衡処理の疑似コードは以下のようになります。
注目ノード = 挿入されたノード while (注目ノード.親ノード != nullNode) { 親ノード = 注目ノード.親ノード 親の高さ = 親ノード.高さ //左部分木に挿入されたとき if (親ノード.左ノード == 注目ノード) { //bias関数は引数ノードの偏りを返す if (bias(親ノード) == 2) { //Rotate系は回転して高さを更新し、回転後の部分木のルートノードを返す 親ノード = bias(親ノード.左ノード) >= 0 ? RotateR(親ノード) : RotateLR(親ノード) }else { //modHeight関数は引数ノードの高さを更新する modHeight(親ノード) } //右部分木に挿入されたとき }else { if (bias(親ノード) == -2) { 親ノード = bias(親ノード.右ノード) <= 0 ? RotateL(親ノード) : RotateRL(親ノード) }else { modHeight(親ノード) } } //挿入前後で部分木の高さが変わらないなら平衡処理終了 if (親の高さ == 親ノード.高さ) { break } //親ノードに注目して平衡処理を続ける 注目ノード = 親ノード }
また、削除時の疑似コードは以下のようになります。
//削除されるのは必ず葉ノード 注目ノード = 削除されたノードの親 while (注目ノード.親ノード != nullNode) { 親ノード = 注目ノード.親ノード 親の高さ = 親ノード.高さ //右部分木で削除されたとき if (親ノード.右ノード == 注目ノード) { //bias関数は引数ノードの偏りを返す if (bias(親ノード) == 2) { //Rotate系は回転して高さを更新し、回転後の部分木のルートノードを返す 親ノード = bias(親ノード.左ノード) >= 0 ? RotateR(親ノード) : RotateLR(親ノード) }else { //modHeight関数は引数ノードの高さを更新する modHeight(親ノード) } //左部分木で削除されたとき }else { if (bias(親ノード) == -2) { 親ノード = bias(親ノード.右ノード) <= 0 ? RotateL(親ノード) : RotateRL(親ノード) }else { modHeight(親ノード) } } //削除前後で部分木の高さが変わらないなら平衡処理終了 if (親の高さ == 親ノード.高さ) { break } //親ノードに注目して平衡処理を続ける 注目ノード = 親ノード }
このように挿入と削除はほとんど同じですが、「左部分木での挿入時の操作」=「右部分木での削除時の操作」(逆も然り)というところだけが違います。
実装
以上を踏まえると、以下のような実装となります。デストラクタにstd::queueを使っている以外は、全くライブラリを使っておらず、一から実装しきることができました。
工夫として、葉ノードの子をnullNodeという番兵ノードとしたことが挙げられます。このことにより、
- nullNodeは高さ0としているので、高さ・偏りの計算時にnullチェックをする必要がない
- Replaceした結果nullNodeになるときでも統一的に書ける
など好都合であるため、このようにしています。
二分木のGIFアニメーションを生成する
趣味で平衡二分木を作ったのですが、（この解説記事ももうすぐ上げます）記事を書くにあたり、下のようなgifアニメなどによる説明があると分かりやすいと思い、それを自動生成するスクリプトを書きました。
適当な実装
本当に適当なgif画像を生成するだけなら、フレームごとの画像をgifにするだけ（ブラウザとかコマンドとか）です。
しかし、このままだと、ルートノードの位置がフレームごとにずれてしまったり、そもそも見切れて下のような見にくいgifとなってしまいます。
これを防ぐためには、すべての画像でルートノードの位置を統一してやる必要があり、今回のスクリプトではこの処理もしています。
それでは具体的な方法を解説していきます。
仕組み
以下にスクリプトのコードを置いておきます。
dot言語による二分木静止画像の生成
まずは以下のような二分木の静止画像を取得することが必要ですが、dotコマンドというGraphvizパッケージのコマンドを使って生成します。
これは、二分木を全探索しつつ、dot言語のフォーマットを出力するコードを書くことでできます。
詳しくは私のAVL木のコード（下のリンク）や、他の方の記事を参照するなりしてください。（二分木の記事の中にもしかしたら書くかも）
ルートノードのずれを補正する
ルートノードがずれていないように見えるためには、すべてのフレームでルートノードの座標が一定になっている必要があります。 また、座標が一定でも、画像のサイズが異なればずれているように見えてしまいます。
そのため、
- すべての画像のキャンバスサイズを一番大きい画像のサイズに揃える
- すべてのフレーム画像に対して枠からはみ出たりしないようなルートノードの固定位置を検出
- すべてのフレーム画像のルートノードが固定位置に固定されるように平行移動
という処理が必要です。
1.画像サイズを揃える
ここでは画像サイズが最大となる画像に揃えるので、まずはそのサイズを探す以下のようなpythonスクリプトを書きます。
#biggest_size.py #coding:utf-8 from PIL import Image import os maxW = 0 maxH = 0 filelist = os.listdir(".") for f in filelist: _,aug = os.path.splitext(f) if aug == ".png": im = Image.open(f) rgb_im = im.convert('RGB') size = rgb_im.size if size[0] > maxW: maxW = size[0] if size[1] > maxH: maxH = size[1] print("{},{}".format(maxW,maxH))
カレントディレクトリからpngファイルを探し、Imageパッケージにより画像サイズを取得して最大値を更新して最後に出力しています。
こうして得られた最大サイズに各画像のキャンバスサイズを拡大していきます。
MAX=`python3 ./biggest_size.py` MAXWIDTH=`echo ${MAX} | sed -e 's/,.*//'` MAXHEIGHT=`echo ${MAX} | sed -e 's/.*,//'` for file in *.png do FILE=${file%.*}.bmp convert ${file} $FILE convert $FILE -gravity west -background white -extent ${MAXWIDTH}x${MAXHEIGHT} $FILE done
拡大に使っているconvertコマンドは ImageMagickパッケージをインストールすると勝手についてきます。 このコマンドのextentオプションにより、画像の拡大ではなくキャンバスサイズの拡大をしてくれます。
2.枠からはみ出ないような固定位置を検出
枠からはみ出ないような固定位置とは、「左端ノードからルートノードまでのx座標の差が最も大きい画像のルートノードの座標」となり、具体的には以下の図の青点のような座標を指します。
このようにすれば確かに左方向にははみ出す画像が無いことは保証されるけど、右方向に関してはどうだろうと思う方もいるかもしれません。
本当はそこも処理しなければなりませんが、今回はAVL木であるのでそこまで問題ではないと考えました。もしそれを任意のケースで保証するなら、ずらすことによるはみ出し分を前項と同じようにキャンバスサイズの拡大をすればいいだけです。
以下のpythonスクリプトで画像の画素値を上から下に見ていくことでルートノード、左から右に見ていくことで左端ノードの座標を検出します。
#calc_offset.py #coding:utf-8 from PIL import Image import sys import os def searchRoot(rgb_im,size): for h in range(size[1]): for w in range(size[0]): r,g,b = rgb_im.getpixel((w,h)) if r==0 and g==0 and b==0: return w,h def searchLeft(rgb_im,size): for w in range(size[0]): for h in range(size[1]): r,g,b = rgb_im.getpixel((w,h)) if r==0 and g==0 and b==0: return w,h maxOffset = 0 ret_w=0 ret_h=0 filelist = os.listdir(".") for f in filelist: _,aug = os.path.splitext(f) if aug == ".png": im = Image.open(f) rgb_im = im.convert('RGB') size = rgb_im.size w,h = searchLeft(rgb_im,size) root_w,root_h = searchRoot(rgb_im,size) if root_w - w > maxOffset: ret_w = root_w ret_h = root_h maxOffset = root_w - w print("{},{}".format(ret_w,ret_h))
3.画像を平行移動
2で取得したオフセットをもとに以下のように各画像をずらしていきます。
OFFSET_W=`python3 ./calc_offset.py` for file in *.bmp do ROOT=`python3 ./search_root.py ${file}` convert ${file} -distort Affine "${ROOT} ${OFFSET_W}" ${file} done
convertコマンドのAffine変換を使い、それぞれのルートノードの位置が固定点になるように平行移動していきます。
gifにする
最後にconvertコマンドですべての画像をつなげたgifにします。
convert -delay 50 -loop 0 *.bmp anim.gif
