リングバッファを作る - リクエスト URL をためておく仕組み (BloggerGlass)

「Back」ボタンを実装するためには、戻るべき画面を記録しておかなければならない。現状の画面遷移だけなら 1 つ前の画面を覚えておけば十分なはずだが、将来のことも考えて、画面遷移の履歴を保持するための仕組みを作ってみることにした。

履歴保存用クラス

実体はリクエスト URL (文字列)を保存しておくためのリスト(Ruby で言うなら配列)に過ぎない。ただし、「前の画面に戻る」ための履歴だから、最後に登録した URL を最初に取り出すことになる。つまり、LIFO (Last In First Out)と呼ばれるデータ構造になる。別の呼び方にスタックというのもある。

スタックなら、操作のためのインタフェースは以下のようになる。

スタックの操作

名称	機能
is_empty	空かどうかを返す
push	データを 1 つ追加する
pop	最後に追加したデータを取り出す(取り出しされたデータはスタックから削除する)
peek	最後に追加したデータを見る(取り出さない)

最低限必要なのは push と pop で、他はあると便利なものだ。

また、この履歴保存用クラスは、スタックであると同時にリングバッファでもある。これは平たく言えば、バッファが一杯になったとき、古いデータが新しいデータで上書きされていくデータ構造だ。

リングバッファにしたかったのには理由がある。直前の画面に戻るための履歴なのだから、バッファが一杯になったからと言って履歴が保存できなくなるのは困る。一方で、古い履歴よりも新しい履歴の方が重要だ。そういう意味で、新しいデータを常に保存することができる(その代わり古いデータは消えていく)リングバッファは最適だと言える。

	class RequestHistory(object):
	def __init__(self, size=10):
	self.size = size
	self.modulus = self.size + 1
	self.history = [''] * (self.modulus)
	self.base = 0
	self.top = 1
	def is_empty(self):
	return self.base == self.decrement(self.top)
	def peek(self):
	if self.is_empty():
	return None
	else:
	return self.history[self.decrement(self.top)]
	def push(self, request):
	self.history[self.top] = request
	if self.top == self.base:
	self.base = self.increment(self.base)
	self.top = self.increment(self.top)
	def pop(self):
	index = self.decrement(self.top)
	if self.is_empty():
	return None
	self.top = index
	return self.history[self.top]
	def export_history(self):
	h = []
	i = self.increment(self.base)
	while i != self.top:
	h.append(self.history[i])
	i = self.increment(i)
	h.append(self.history[i])
	return h
	def import_history(self, history):
	for request in history:
	self.push(request)
	def increment(self, number):
	return (number + 1) % self.modulus
	def decrement(self, number):
	return (number - 1) % self.modulus

view raw request_history.py hosted with ❤ by GitHub

export_history と import_history は、履歴をセッションデータとしてデータストアに収めるときに使用する(ことになるはず)。

単体テスト

RequestHistory クラスは、以下のような単体テストを書きながら、そしてテストしながら実装した。50 行足らずの短いプログラムだと言うのに意外に難しかった。何度「これで良い(はず)！」と思ってからテストに失敗したことか。こういう一般的なプログラムを書くときは、本当にテストが役に立つ。

(tests/util_test.py より)
import unittest

import pathconf
# target module 
import util

class RequestHistoryTest(unittest.TestCase):
    def setUp(self):
        self.history = util.RequestHistory()

    def test_is_empty(self):
        """empty?(EMPTY) == True"""
        self.assert_(self.history.is_empty())

    def test_peek(self):
        """peek(push(EMPTY, A)) == A,
        then pop() also returns A
        """
        self.history.push('/1')
        self.assertEqual(self.history.peek(), '/1')
        self.assertEqual(self.history.pop(), '/1')

    def test_pop_against_empty(self):
        """pop(EMPTY) == None"""
        self.assertEqual(self.history.pop(), None)

    def test_push_1_pop_1(self):
        """pop(push(EMPTY, A)) == A"""
        self.history.push('/')
        self.assertEqual(self.history.pop(), '/')

    def test_push_2_pop_2(self):
        """pop(push(push(EMPTY, A), B)) == B
        pop(pop(push(push(EMPTY, A), B))) == A
        """
        self.history.push('/')
        self.history.push('/foo')
        self.assertEqual(self.history.pop(), '/foo')
        self.assertEqual(self.history.pop(), '/')

    def test_push_10_pop_10(self):
        """H = push(push(...(push(EMPTY, 0), 1), ...), 9)
        then, pop(pop(...(pop(H))...)) = 0
        """
        for i in range(10):
            self.history.push("/%d" % i)
        for i in reverse_range(10):
            self.assertEqual(self.history.pop(), ("/%d" % i))

    def test_push_11_pop_10(self):
        """H = push(push(...(push(EMPTY, 0), 1), ...), 10)
        then, pop(pop(...(pop(H))...)) = 1
        """
        for i in range(11):
            self.history.push("/%d" % i)
        r = reverse_range(11)
        r.pop()
        for i in r:
            self.assertEqual(self.history.pop(), ("/%d" % i))

    def test_export_history(self):
        for i in range(10):
            self.history.push("/%d" % i)
        h = self.history.export_history()
        for i in range(10):
            self.assertEqual(h[i], ("/%d" % i))

    def test_import_history(self):
        h = []
        for i in range(10):
            h.append("/%d" % i)
        self.history.import_history(h)
        r = range(10)

    def test_pickle(self):
        """Make sure that it can be pickled in and out."""
        for i in range(10):
            self.history.push("/%d" % i)
        pickled = pickle.dumps(self.history)
        history = pickle.loads(pickled)

        for i in reverse_range(10):
            self.assertEqual(history.pop(), ("/%d" % i))

def reverse_range(n):
    r = range(n)
    r.reverse()
    return r

def suite():
    return unittest.TestSuite((
            unittest.makeSuite(RequestHistoryTest, 'test'),
            ))

if __name__ == '__main__':
    unittest.TextTestRunner().run(suite())

関連リンク

• リングバッファ (Wikipedia:ja)
• 構造としてのFIFO(リングバッファ) (Super Technique 講座)

関連記事

• GAE アプリ用に PyUnit を使って単体テストを書く