pythonでの連結リストの実装

linkedlist.py

# -*- coding: utf-8 -*-
'''tes
連結リスト
----------

Pythonでは__(アンダースコア2つ)で囲まれたメソッドを、特殊メソッドと呼ぶ。特殊メソッドを決められた仕様に沿って実装することで、様々なポリモーフィズムの恩恵を得ることができる。 例えば、__iter__特殊メソッドを実装したクラスのインスタンスはfor文の中で用いることができるようになる。

以下の手順で **MyLinkedList** クラスを実装せよ。

#.  __reversed__()とMyReverseIterator以外を実装し連結リストを完成させよ

#. ::

        MyLinkedList.__reversed__()
        MyReverseIterator

   を実装し、両方向リストを完成させよ。逆方向のリンクはNode.prevという名前
   のインスタンス変数で保持すること。

テストも実行すること::

    $ python linkedlist.py
    $ python test.py
'''

import pdb, copy
from collections import Iterator, Sequence, MutableSequence


class MyLinkedList(MutableSequence):

    def __init__(self):
        'コンストラクタ'
        self.head = None
        self.last = None
        self.node = None

    def __contains__(self, value):
        for iterator in self:
            if iterator.value == value:
                return "True"



        '''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):

        return MyIterator(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 sorted(self):
        if self.head == None:
            raise IndexError
        pdb.set_trace()
        self.node = self.head
        answer = List()
        while self.node:
            answer.append(self.node.value)
            self.node = self.node.next
        return answer
        

    def __len__(self):
        if self.head == None:
            return 0
        
        self.node = self.head
        if self.node.next == None:
            return 1
        length = 1
        while self.node.next:
                length += 1
                self.node = self.node.next
        return length

       
        '''len関数で呼ばれる特殊メソッド

        ::

            >>> l = MyLinkedList()
            >>> len(l)
            0
            >>> l.append(1)
            >>> len(l)
            1
            >>> l.append(2)
            >>> len(l)
            2

        '''

    def __getitem__(self, key):
        if type(key) != int:
            raise TypeError
        if key < -len(self):
            raise IndexError
        if key >= len(self):
            raise IndexError

        if self.head == None:
            raise IndexError
        if key == -1:
            result = self.last.value
        elif key == 0:
            result = self.head.value

        elif key < -1:
            for i in range(- key):
                result = self.node.value
                self.node = self.node.prev

        else:
            self.node = self.head
            for i in range(key + 1):
                result = self.node.value
                self.node = self.node.next
                


        #pdb.set_trace()
        return result


        '''インデックス記法で呼ばれる特殊メソッド

        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

        '''

    def __setitem__(self, key, value):
        if type(key) != int:
            raise IndexError
        if key < -len(self):
            raise IndexError
        if key >= len(self):
            raise IndexError
        self.node = self.head
        for i in range(key):
            self.node = self.node.next
            
        self.node.value = value
        self.node = value
        return self.node



        '''インデックス記法を用いた代入文で呼ばれる特殊メソッド

        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):
        if type(key) != int:
            raise IndexError
        if key < -len(self):
            raise IndexError
        if key >= len(self):
            raise IndexError
        if self.head == None:
            raise IndexError
        self.node = self.head

        #pdb.set_trace()
        for i in range(key):
            self.node = self.node.next
        if self.node.prev == None:
            self.head = self.node.next
            self.head.prev = None
        elif self.node.next == None:
            self.last = self.last.prev
            self.last.next = None
        else:
            self.node.prev.next = self.node.next
            #pdb.set_trace()
            self.node = None




        '''インデックス記法を用いて削除を行う

        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):
        if self.last == None:
            self.head = Node(value)
            self.last = Node(value)

        elif self.head.next == None:
            #pdb.set_trace()
            self.node = self.head
            self.node.next = Node(value)
            self.last = self.node.next
            self.head.next = self.node.next
            self.last.prev = self.node
        else:
            self.node = self.last
            self.node.next = Node(value)
            self.last = self.node.next
        return self


        '''+=オペランドで呼ばれる特殊メソッド

        collections.MutableSequence基底クラスのMixinメソッド

        戻り値が代入される。::

            >>> l = MyLinkedList()
            >>> l += 1
            >>> l[0]
            1
            >>> l += 2
            >>> l[1]
            2

        '''
        pass

    def __reversed__(self):
        return MyReverseIterator(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 reverse(self):
        import copy
        mirror = copy.deepcopy(self)
        mirror.node = mirror.head
        self.node = self.last

        while self.node != None:
            #pdb.set_trace()
            mirror.node.value = copy.deepcopy(self.node.value)
            mirror.node = mirror.node.next
            self.node = self.node.prev

        
        self.node = self.head
        mirror.node = mirror.head
        while self.node != None:
            #pdb.set_trace()
            self.node.value = copy.deepcopy(mirror.node.value)
            self.node = self.node.next
            mirror.node = mirror.node.next


        '''自分自身の順番を逆にする

        collections.MutableSequence基底クラスのMixinメソッド
        破壊的メソッドであることに注意。また、このメソッド自体は値を返さない。::

            >>> l = MyLinkedList()
            >>> l.append(1)
            >>> l.append(2)
            >>> l.reverse()
            >>> l.pop()
            1
            >>> l.pop()
            2

        '''
        pass

    def index(self, value):
        #pdb.set_trace()
        self.node = self.head
        for i in self:
            if self.node.value == value:
                return self.node
            self.node = self.node.next
        '''``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):
        self.node = self.head
        i = 0
        if key == 0:
            next_of_next = self.node
            self.head = Node(value)
            self.head.next = next_of_next
            self.head.next.prev = self.first
        else:

            for i in range(key - 1):
                self.node = self.node.next
                i += 1
            next_of_next = self.node.next
            self.node.next = Node(value)
            self.node.next.prev = self.node
            self.node = self.node.next
            self.node.next = next_of_next

        
        '''リストへの挿入

        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):
        #pdb.set_trace()
        count = 0
        self.node = self.head
        for i in self:
            if self.node.value == value:
                count += 1
            self.node = self.node.next
        return count
        '''要素の数え上げ

        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):
        flag = False
        import pdb
        #pdb.set_trace()
        self.node = self.head
        while self.node != None:
            if self.node.value == value:
                if self.node.prev != None and self.node.next != None:
                    self.node.prev.next = self.node.next
                    self.node.next.prev = self.node.prev
                elif self.node.prev == None:
                    self.node.next.prev = None
                    self.head = self.node.next
                elif self.node.next == None:
                    self.node.prev.next = None
                    self.last = self.node.prev
                flag = True
            self.node = self.node.next

        if flag != True:
            raise ValueError

        
        '''要素の削除

        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):
        from collections import Iterable
        if isinstance(seq, Iterable) != True:
            raise IndexError
        else:
            #pdb.set_trace()
            self.node = self.last
            for i in seq:
                self.node.next = Node(i)
                self.node = self.node.next
                self.last = self.node
        '''要素の拡張

        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

    def pop(self):
        if self.last == None:
            raise IndexError
        elif self.head.next == None:
            answer = self.last.value
            self.last = None
            return answer
        else:
            answer = self.last.value
            self.last = self.last.prev
            self.last.next = None
            return answer
        '''リストの末尾から値を一つ取り出す

        collections.MutableSequence基底クラスのMixinメソッド::

            >>> l = MyLinkedList()
            >>> l.append(1)
            >>> l.pop()
            1

        空のリストに対して読んだ場合、IndexError例外を発生させなければならない::

            >>> l.pop()
            Traceback (most recent call last):
                ...
            IndexError

        '''

    def append(self, value):
        import pdb
        if self.head == None:
            #pdb.set_trace()
            self.head = Node(value)
            self.last = self.head
            
        elif self.head.next == None:
            self.last.next = Node(value)
            self.last = self.last.next
            self.last.prev = self.head
            self.head.next = self.last    
        else:
            self.last.next = Node(value)
            slp = self.last
            self.last = self.last.next
            #pdb.set_trace()
            self.last.prev = slp
        '''リストの末尾に``value''を加える

        collections.MutableSequence基底クラスのMixinメソッド

            >>> l = MyLinkedList()
            >>> l.append(1)
            >>> l.append(2)

        '''



class MyIterator(Iterator):
    '''MyLinkedListインスタンスに対するイテレータ'''
    def __init__(self, node):
        self.node = node.head
        
    def next(self):
        if self.node == None:
            raise StopIteration
        result = self.node
        self.node = self.node.next
        return result


        '''イテレータプロトコル

        collections.Iterator基底クラスの抽象メソッド

        最後まできた場合はStopIteration例外を発生させなければならない。
        詳しくはMyLinkedList.__iter__特殊メソッドのコメント参照
        '''

    # python3から__next__特殊メソッドに変更された
    __next__ = next


class MyReverseIterator(Iterator):
    '''MyLinkedListインスタンスに対する逆方向のイテレータ'''
    def __init__(self, node):
        self.node = node.last

    def next(self):
        if self.node == None:
            raise StopIteration
        result = self.node
        self.node = self.node.prev
        return result
        '''イテレータプロトコル

        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 pdb
    import doctest
    doctest.testmod()
    l = MyLinkedList()

    for i in range(10):
        l.append(i)
    for i in range(-9, 0):
        #pdb.set_trace()
        print l[i]