連結リストを実装しながら特殊メソッドを勉強する例題を作った
Pythonでは__(アンダースコア二つ)で囲まれたメソッドは特殊メソッドと呼ばれ、これらを決められたルールに沿って実装することで、様々な機能を持たせることができます。例えば、__iter__特殊メソッドを決められたルール(Pythonではイテレータプロトコルと呼ばれる)に沿って実装することで、for文を使って要素の一つ一つを順番に取り出すことができるようになります。ちょうどJavaでIterableインタフェースをimplementすることでfor-each文で呼び出せるようになるのと同じです。
今回の問題では
- __iter__
- __contains__
- __len__
- __getitem__
- __setitem__
- __delitem__
- __iadd__
- __reversed__
などの特殊メソッドに加え、collectionsモジュールに含まれているMutableSequence基底クラスの抽象メソッドである
- append
- pop
- insert
- index
- count
- reverse
- extend
- remove
などのメソッドの実装も行います。実装例はそのうち公開します。
参考: データモデル — Python 2.7ja1 documentation
今回は連結リストを実装しながら特殊メソッドの使い方を勉強するための練習問題を作ってみました。doctestが付属しているので、以下のコードをlinkedlist.pyという名前で保存し
$ python linkedlist.py
とすることによって、テストすることが可能です。
連結リストがどんなものか分からない人は→http://ja.wikipedia.org/wiki/連結リスト
# -*- coding: utf-8 -*- ''' 課題１ MyLinkedList.__init__() MyLinkedList.append() MyLinkedList.pop() MyIterator を実装せよ。 課題２ MyLinkedList.__iter__() MyLinkedList.__contains__() MyLinkedList.__getitem__() MyLinkedList.__len__() を実装し、MyLinkedListをSequenceから継承するように変更せよ。 また、IterableやSequenceを要求される箇所にMyLinkedListのインスタンスを渡し 動くか確認せよ。 課題３ MyLinkedList.insert() MyLinkedList.__setitem__() MyLinkedList.__delitem__() を実装し、MyLinkedListをMutableSequenceから継承するように変更せよ。 課題４ MyLinkedList.__iadd__() MyLinkedList.index() MyLinkedList.count() MyLinkedList.reverse() MyLinkedList.extend() MyLinkedList.remove() を実装し、片方向リストを完成させよ 課題５ MyLinkedList.__reversed__() MyReverseIterator を実装し、両方向リストを完成させよ。逆方向のリンクはNode.prevという名前 のインスタンス変数で保持すること。 ''' from collections import Iterator, Sequence, MutableSequence class MyLinkedList(object): # Sequence): # MutableSequence): def __contains__(self, value): '''inステートメントで呼ばれる特殊メソッド collections.Sequence基底クラスのMixinメソッド inステートメントで呼ばれる。value in self の結果をTrueかFalseで返す >>> l = MyLinkedList() >>> l.append(1) >>> 1 in l # l.__contains__(1) に等しい True >>> 2 in l False ''' pass def __iter__(self): '''iter関数で呼ばれる特殊メソッド collections.Sequence基底クラスのMixinメソッド イテレータデザインパターンにおけるイテレータオブジェクトを返す。Python においては、主にfor文で用いられる。 for a in b: do(a) は次のコードと等しい。 iterator = iter(b) # = b.__iter__() try: while True: a = next(iterator) # = iterator.next() do(a) except StopIteration: pass (余談) Python3からはnext組み込み関数で呼ばれるのが、nextメソッドから __next__特殊メソッドに変更されました。 >>> l = MyLinkedList() >>> l.append(1) >>> iterator = iter(l) >>> isinstance(iterator, MyIterator) True >>> next(iterator) 1 iteratorオブジェクトは最後まできたらStopIteration例外を発生させなければ ならない。 >>> item = next(iterator) Traceback (most recent call last): ... StopIteration __iter__特殊メソッドを実装することでfor文で使うことができるようになる。 >>> l.append(2) >>> for i in l: ... print i ... 1 2 ''' pass def __len__(self): '''len関数で呼ばれる特殊メソッド >>> l = MyLinkedList() >>> len(l) 0 >>> l.append(1) >>> len(l) 1 >>> l.append(2) >>> len(l) 2 ''' pass def __getitem__(self, key): '''インデックス記法で呼ばれる特殊メソッド collections.Sequence基底クラスの抽象メソッド 配列のようなインデックス記法を用いた場合に呼び出され、``key''番目の要素 の値を返す。 >>> l = MyLinkedList() >>> l.append(1) >>> l[0] # l.__getitem__(0) 1 設定されていないインデックスにアクセスされた場合はIndexError例外を発生 させなければならない。 >>> l[2] Traceback (most recent call last): ... IndexError ``key''が数字以外だった場合TypeError例外を発生させなければならない >>> l['string'] Traceback (most recent call last): ... TypeError ``key''の値は-len(self) <= key < len(self)でなければならず、範囲外の 場合はIndexError例外を発生させなければならない。 >>> l.append(2) >>> l[-2] 1 >>> l[2] Traceback (most recent call last): ... IndexError >>> l[-3] Traceback (most recent call last): ... IndexError ''' pass def __setitem__(self, key, value): '''インデックス記法を用いた代入文で呼ばれる特殊メソッド collections.MutableSequence基底クラスの抽象メソッド ``key''番目の値を``value''に置き換える。 >>> l = MyLinkedList() >>> l.append(1) # [1] >>> l[0] = 2 # [2] >>> l[0] 2 設定されていないインデックスに対して代入を行おうとした場合はIndexError 例外を発生させなければならない。 >>> l[1] = 2 Traceback (most recent call last): ... IndexError ``key''が数字以外だった場合TypeError例外を発生させなければならない >>> l['string'] = 2 Traceback (most recent call last): ... TypeError ``key''の値は-len(self) <= key < len(self)でなければならず、範囲外の 場合はIndexError例外を発生させなければならない。 >>> l.append(2) # [2, 2] >>> l[-2] = 3 # [3, 2] >>> l[0] 3 >>> l[2] Traceback (most recent call last): ... IndexError >>> l[-3] Traceback (most recent call last): ... IndexError ''' pass def __delitem__(self, key): '''インデックス記法を用いて削除を行う collections.MutableSequence基底クラスの抽象メソッド delステートメントで``key''番目の値を削除する >>> l = MyLinkedList() >>> l.append(1) >>> l.append(2) >>> l[0] 1 >>> del l[0] >>> l[0] 2 設定されていないインデックスの削除を行おうとした場合はIndexErrorを発生 させなければならない。 >>> del l[1] Traceback (most recent call last): ... IndexError ``key''が数字以外だった場合TypeError例外を発生させなければならない >>> del l['string'] Traceback (most recent call last): ... TypeError ``key''の値は-len(self) <= key < len(self)でなければならず、範囲外の 場合はIndexError例外を発生させなければならない。 >>> del l[-1] >>> l[0] Traceback (most recent call last): ... IndexError ''' pass def __iadd__(self, value): '''+=オペランドで呼ばれる特殊メソッド collections.MutableSequence基底クラスのMixinメソッド 戻り値が代入される >>> l = MyLinkedList() >>> l += 1 >>> l[0] 1 >>> l += 2 >>> l[1] 2 ''' pass def __reversed__(self): '''reversed組み込み関数で呼ばれる特殊メソッド collections.Sequence基底クラスのMixinメソッド 逆方向にたどるためのイテレータオブジェクトを返す。 >>> l = MyLinkedList() >>> l.append(1) >>> l.append(2) >>> iterator = reversed(l) >>> isinstance(iterator, MyReverseIterator) True >>> next(iterator) 2 >>> next(iterator) 1 最後まできたらStopIteration例外を発生させなければならない >>> next(iterator) Traceback (most recent call last): ... StopIteration for文で用いることも可能 >>> for i in reversed(l): ... print i ... 2 1 ''' pass def append(self, value): '''リストの末尾に``value''を加える collections.MutableSequence基底クラスのMixinメソッド >>> l = MyLinkedList() >>> l.append(1) >>> l.append(2) ''' pass def pop(self): '''リストの末尾から値を一つ取り出す collections.MutableSequence基底クラスのMixinメソッド >>> l = MyLinkedList() >>> l.append(1) >>> l.pop() 1 空のリストに対して読んだ場合、IndexError例外を発生させなければならない >>> l.pop() Traceback (most recent call last): ... IndexError ''' pass def reverse(self): '''自分自身の順番を逆にする collections.MutableSequence基底クラスのMixinメソッド 破壊的メソッドであることに注意。また、このメソッド自体は値を返さない。 >>> l = MyLinkedList() >>> l.append(1) >>> l.append(2) >>> l.reverse() >>> l.pop() 1 >>> l.pop() 2 ''' pass def index(self, value): '''``value''が最初に現れるインデックスを返す collections.Sequence基底クラスのMixinメソッド >>> l = MyLinkedList() >>> l.append(1) >>> l.append(2) >>> l.append(1) >>> l.index(1) 0 >>> l.index(2) 1 ``value''が存在しない場合はValueError例外を発生させなければならない。 >>> l.index(3) Traceback (most recent call last): ... ValueError ''' pass def insert(self, key, value): '''リストへの挿入 collections.MutableSequence基底クラスの抽象メソッド ``key''番目に``value''を挿入する。 >>> l = MyLinkedList() >>> l.append(1) # [1] >>> l.insert(0, 2) # [2, 1] >>> l.insert(1, 3) # [2, 3, 1] >>> l.insert(-1, 4) # [2, 3, 4, 1] >>> l.insert(-3, 6) # [2, 6, 3, 4, 1] >>> l.insert(-5, 5) # [5, 2, 6, 3, 4, 1] >>> l.pop() 1 >>> l.pop() 4 >>> l.pop() 3 ``key``が大きすぎるもしくは小さすぎる場合は端に挿入される。例外は発生 しない。 >>> l.append(1) # [5, 2, 6, 1] >>> l.insert(100, 2) # [5, 2, 6, 1, 2] >>> l.pop() 2 >>> l.insert(-100, 0) # [0, 5, 2, 6, 1] >>> l.pop() 1 >>> l.pop() 6 >>> l.pop() 2 >>> l.pop() 5 >>> l.pop() 0 ''' pass def count(self, value): '''要素の数え上げ collections.Sequence基底クラスのMixinメソッド ``value''と値が等しいオブジェクトが含まれる数を返す。 >>> l = MyLinkedList() >>> l.append(1) >>> l.append(2) >>> l.append(1) >>> l.count(1) 2 >>> l.count(3) 0 同一のオブジェクトである必要はない >>> 1 is 1.0 # ヒント1 False >>> 1 == 1.0 # ヒント2 True >>> l.count(1.0) 2 ''' pass def remove(self, value): '''要素の削除 collections.MutableSequence基底クラスのMixinメソッド ``value''と値が等しいオブジェクトの内、最もインデックスの小さいものを 削除する >>> l = MyLinkedList() >>> l.append(1) >>> l.append(2) >>> l.append(1) >>> l.append(2) >>> l.remove(2) >>> l.pop() 2 >>> l.pop() 1 >>> l.pop() 1 >>> l.pop() Traceback (most recent call last): ... IndexError 存在しない値が指定された場合はValueError例外を発生させなければならない >>> l.remove(2) Traceback (most recent call last): ... ValueError ''' pass def extend(self, seq): '''要素の拡張 collections.MutableSequence基底クラスのMixinメソッド ``seq''を末尾に追加する。``seq''はiterableなオブジェクトでなければなら ない。 >>> l = MyLinkedList() >>> l.extend([1,2,3]) >>> l.pop() 3 >>> l.pop() 2 >>> l.pop() 1 iterableかどうかは次のようにして知ることができる >>> from collections import Iterable >>> isinstance([], Iterable) True >>> isinstance((), Iterable) True >>> isinstance({}, Iterable) True >>> isinstance(1, Iterable) False >>> isinstance('', Iterable) # 文字列はiterable True >>> 'string'[1] 't' ''' pass class MyIterator(Iterator): '''MyLinkedListインスタンスに対するイテレータ''' def next(self): '''イテレータプロトコル collections.Iterator基底クラスの抽象メソッド 最後まできた場合はStopIteration例外を発生させなければならない。 詳しくはMyLinkedList.__iter__特殊メソッドのコメント参照 ''' pass # python3から__next__特殊メソッドに変更された __next__ = next class MyReverseIterator(Iterator): '''MyLinkedListインスタンスに対する逆方向のイテレータ''' def next(self): '''イテレータプロトコル collections.Iterator基底クラスの抽象メソッド 最後まできた場合はStopIteration例外を発生させなければならない。 詳しくはMyLinkedList.__reversed__特殊メソッドのコメント参照 ''' pass # python3から__next__特殊メソッドに変更された __next__ = next class Node(object): '''ノード''' def __init__(self, value): self.value = value self.next = None self.prev = None def __repr__(self): 'printステートメントなどで呼ばれる' return repr(self.value) if __name__ == '__main__': import doctest doctest.testmod()
