Move To Front

"""1.3.40 Move-to-front.
Read in a sequence of characters from standard input and
maintain the characters in a linked list with no duplicates. When you read in a
previously unseen character, insert it at the front of the list.
When you read in a duplicate character, delete it from the list and reinsert it
at the beginning. Name your program MoveToFront: it implements the well-known
move-to-front strategy, which is useful for caching, data compression, and many
other applications where items that have been recently accessed are more likely
to be reaccessed.
"""
import unittest
import collections


class MoveToFrontIterator(collections.Iterator):

    def __init__(self, first):
        self._head = first

    def __iter__(self):
        return self

    def __next__(self):
        if not self.has_next(): raise StopIteration
        item = self._head._item
        self._head = self._head._next
        return item

    def has_next(self):
        return self._head != None


class MoveToFront:

    class DataNode:

        def __init__(self, item):
            self._item = item
            self._prev = None
            self._next = None

    def __init__(self):
        self._head = None
        self._size = 0

    def __iter__(self):
        return MoveToFrontIterator(self._head)

    def __node_exists(self, item):
        head = self._head
        while head and head._item != item:
            head = head._next
        return head

    def __update_linkedlist(self, node, exists):
        if exists:
            if node._next and node._prev:
                # 当前结点是链表的头结点和尾节点之间
                node._next._prev = node._prev
            node._prev._next = node._next
            node._next = self._head
            self._head._prev = node
            node._prev = None
            self._head = node
            return
        else:
            node._next = self._head
            if self._head:
                self._head._prev = node
            self._head = node

    def insert(self, item):
        node = self.__node_exists(item)
        if node:
            # 存在该结点
            if node != self._head:
                # 不是链表的首结点
                self.__update_linkedlist(node, True)
            else:
                # 是链表的首结点
                return
        else:
            # 不存在该结点,新插入一个新结点到链表头部
            new_node = self.DataNode(item)
            # 更新链表 while循环 有问题的,while条件怎么都为True
            self.__update_linkedlist(new_node, False)
            self._size += 1

    def size(self):
        return self._size

    def is_empty(self):
        return self._size == 0


class TestMoveToFront(unittest.TestCase):

    @staticmethod
    def create_linkedlist():
        return MoveToFront()

    def test_insert(self):

        # test empty
        head = self.create_linkedlist()
        array = []
        for num in array:
            head.insert(num)

        self.assertEqual(len(array), head.size())
        self.assertEqual(0, head.size())
        self.assertEqual(True, head.is_empty())

        # test insert
        head = self.create_linkedlist()
        array = [1, 2, 3, 2, 7, 8, 10, 9, 12, 11, 8, 6, 6]
        for num in array:
            head.insert(num)

        result = [6, 8, 11, 12, 9, 10, 7, 2, 3, 1]
        self.assertEqual(result, list(head))
        self.assertEqual(len(result), head.size())
        self.assertEqual(False, head.is_empty())

        # test insert
        head = self.create_linkedlist()
        array = [1, 2, 2, 8, 8, 6, 6]
        for num in array:
            head.insert(num)

        result = [6, 8, 2, 1]
        self.assertEqual(result, list(head))
        self.assertEqual(len(result), head.size())
        self.assertEqual(False, head.is_empty())


if __name__ == "__main__":
    unittest.main()

-- EOF --