| OLD | NEW |
|---|
| (Empty) |
| 1 # Copyright (C) 2011 Google Inc. All rights reserved. | |
| 2 # | |
| 3 # Redistribution and use in source and binary forms, with or without | |
| 4 # modification, are permitted provided that the following conditions are | |
| 5 # met: | |
| 6 # | |
| 7 # * Redistributions of source code must retain the above copyright | |
| 8 # notice, this list of conditions and the following disclaimer. | |
| 9 # * Redistributions in binary form must reproduce the above | |
| 10 # copyright notice, this list of conditions and the following disclaimer | |
| 11 # in the documentation and/or other materials provided with the | |
| 12 # distribution. | |
| 13 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
| 14 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
| 15 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
| 16 # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
| 17 # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
| 18 # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
| 19 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
| 20 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
| 21 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
| 22 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
| 23 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
| 24 | |
| 25 | |
| 26 class Node(): | |
| 27 def __init__(self, key, value): | |
| 28 self.key = key | |
| 29 self.value = value | |
| 30 self.prev = None | |
| 31 self.next = None | |
| 32 | |
| 33 | |
| 34 class LRUCache(): | |
| 35 """An implementation of Least Recently Used (LRU) Cache.""" | |
| 36 | |
| 37 def __init__(self, capacity): | |
| 38 """Initializes a lru cache with the given capacity. | |
| 39 | |
| 40 Args: | |
| 41 capacity: The capacity of the cache. | |
| 42 """ | |
| 43 assert capacity > 0, "capacity (%s) must be greater than zero." % capaci
ty | |
| 44 self._first = None | |
| 45 self._last = None | |
| 46 self._dict = {} | |
| 47 self._capacity = capacity | |
| 48 | |
| 49 def __setitem__(self, key, value): | |
| 50 if key in self._dict: | |
| 51 self.__delitem__(key) | |
| 52 if not self._first: | |
| 53 self._one_node(key, value) | |
| 54 return | |
| 55 if len(self._dict) >= self._capacity: | |
| 56 del self._dict[self._last.key] | |
| 57 if self._capacity == 1: | |
| 58 self._one_node(key, value) | |
| 59 return | |
| 60 self._last = self._last.next | |
| 61 self._last.prev = None | |
| 62 node = Node(key, value) | |
| 63 node.prev = self._first | |
| 64 self._first.next = node | |
| 65 self._first = node | |
| 66 self._dict[key] = node | |
| 67 | |
| 68 def _one_node(self, key, value): | |
| 69 node = Node(key, value) | |
| 70 self._dict[key] = node | |
| 71 self._first = node | |
| 72 self._last = node | |
| 73 | |
| 74 def __getitem__(self, key): | |
| 75 if not self._first: | |
| 76 raise KeyError(str(key)) | |
| 77 if self._first.key == key: | |
| 78 return self._first.value | |
| 79 | |
| 80 if self._last.key == key: | |
| 81 next_last = self._last.next | |
| 82 next_last.prev = None | |
| 83 next_first = self._last | |
| 84 next_first.prev = self._first | |
| 85 next_first.next = None | |
| 86 self._first.next = next_first | |
| 87 self._first = next_first | |
| 88 self._last = next_last | |
| 89 return self._first.value | |
| 90 | |
| 91 node = self._dict[key] | |
| 92 node.next.prev = node.prev | |
| 93 node.prev.next = node.next | |
| 94 node.prev = self._first | |
| 95 node.next = None | |
| 96 self._first.next = node | |
| 97 self._first = node | |
| 98 return self._first.value | |
| 99 | |
| 100 def __delitem__(self, key): | |
| 101 node = self._dict[key] | |
| 102 del self._dict[key] | |
| 103 if self._first is self._last: | |
| 104 self._last = None | |
| 105 self._first = None | |
| 106 return | |
| 107 if self._first is node: | |
| 108 self._first = node.prev | |
| 109 self._first.next = None | |
| 110 return | |
| 111 if self._last is node: | |
| 112 self._last = node.next | |
| 113 self._last.prev = None | |
| 114 return | |
| 115 node.next.prev = node.prev | |
| 116 node.prev.next = node.next | |
| 117 | |
| 118 def __len__(self): | |
| 119 return len(self._dict) | |
| 120 | |
| 121 def __contains__(self, key): | |
| 122 return key in self._dict | |
| 123 | |
| 124 def __iter__(self): | |
| 125 return iter(self._dict) | |
| 126 | |
| 127 def items(self): | |
| 128 return [(key, node.value) for key, node in self._dict.items()] | |
| 129 | |
| 130 def values(self): | |
| 131 return [node.value for node in self._dict.values()] | |
| 132 | |
| 133 def keys(self): | |
| 134 return self._dict.keys() | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 479633002:
Remove several unneeded modules from webkitpy.common. (Closed)
Base URL: svn://svn.chromium.org/blink/trunk