import datetime
class Array:
def __init__(self, size=256):
"""
:param size: the size of container
"""
self._size = size
self._items = [None]*size
self.length=0
def __getitem__(self, index):
return self._items[index]
def __setitem__(self, key, value):
self._items[key] = value
self.length+=1
def __len__(self):
return self.length
def clear(self, value=None):
for index in self._items:
self._items[index] = value
self.length=0
def __iter__(self):
for i in self._items:
yield i
class Node:
def __init__(self, value=None, next=None, prev=None, create_time=None):
"""
:param value:value
:param next: next node
:param prev: prev node
:param create_time: create time
"""
self.value, self.next, self.prev, self.create_time = value, next, prev, create_time
class Bag:
def __init__(self, maxsize=None,array_atribut_size=256,del_time=60):
"""
:param maxsize: the size of container
:param array_atribut_size:the history message is array_atribut*2
:param del_time: if now time - create time >del_time(s) del node
"""
self.del_time=del_time
self.array_atribut_size=array_atribut_size
self.array=[Array(array_atribut_size),Array(array_atribut_size),Array(array_atribut_size)]
self._root = Node()
self._root.next = self._root
self._root.prev = self._root
self._maxsize = maxsize
self._tailnode = self._root
self._headnode = self._root
self._length = 0
self.array_tail=0
self.array_tail_tail=0
def __len__(self):
"""
:return: the length of Bag()
"""
self.remove_by_time()
return self._length
def remove_by_time(self):
curnode = self._root
lis = []
while True:
curnode = curnode.next
if curnode == self._root:
break
if datetime.datetime.now() - curnode.create_time > datetime.timedelta(seconds=self.del_time):
lis.append(curnode.value)
for i in lis:
self.remove(i)
def append(self, value):
if self._maxsize is not None and self._length >= self._maxsize:
raise Exception("Full")
node=Node(value=value, create_time=datetime.datetime.now())
if self._tailnode == self._root:
self._root.next = node
node.prev = self._root
self._headnode = node
else:
node.prev = self._tailnode
self._tailnode.next = node
self._tailnode = node
self._root.prev = node
node.next = self._root
if self.array_tail_tail == self.array[self.array_tail]._size:
if self.array_tail==0:
self.array_tail=1
if self.array[2][0] is not None:
self.array[0], self.array[1], self.array[2] = Array(self.array_atribut_size), self.array[0],self.array[1]
self.array_tail=0
elif self.array_tail==1:
self.array_tail=0
self.array[0],self.array[1],self.array[2]=Array(self.array_atribut_size),self.array[0],self.array[1]
self.array_tail_tail = 0
self.array[self.array_tail][self.array_tail_tail] = value
self.array_tail_tail += 1
self._length += 1
def appendleft(self, value):
"""
:param value: value
:return: None
"""
if self._maxsize is not None and self._length >= self._maxsize:
raise Exception("Full")
node = Node(value=value, create_time=datetime.datetime.now())
if self._tailnode == self._root:
self._root.prev = node
node.next = self._root
self._tailnode = node
else:
node.next = self._headnode
self._headnode.prev = node
self._headnode = node
self._root.next = node
node.prev = self._root
if self.array_tail_tail == self.array[self.array_tail]._size:
if self.array_tail==0:
self.array_tail=1
if self.array[2][0] is not None:
self.array[0], self.array[1], self.array[2] = Array(self.array_atribut_size), self.array[0],self.array[1]
self.array_tail=0
elif self.array_tail==1:
self.array_tail=0
self.array[0],self.array[1],self.array[2]=Array(self.array_atribut_size),self.array[0],self.array[1]
self.array_tail_tail = 0
self.array[self.array_tail][self.array_tail_tail] = value
self.array_tail_tail += 1
self._length += 1
def iter_node(self):
curnode = self._root
while True:
curnode = curnode.next
if curnode == self._root:
break
yield curnode
def __iter__(self):
self.remove_by_time()
for i in self.iter_node():
yield i.value
def show_history(self):
"""
show the history message (2*self.array_atribut_size)
:return:
"""
if self.array[2][0] is None:
for a in self.array[0]:
if a == None:
continue
yield a
for b in self.array[1]:
if b == None:
continue
yield b
else:
num2=0
for b in self.array[1]:
if b == None:
continue
num2+=1
if num2<=len(self.array[0]):
continue
yield b
for c in self.array[2]:
if c == None:
continue
yield c
for a in self.array[0]:
if a == None:
continue
yield a
def remove(self, value):
"""
:param value: the value of any node(first_create)
:return: if value is True:value else:-1
"""
for i in self.iter_node():
if i.value == value:
if i == self._headnode:
self._headnode = i.next
if i == self._tailnode:
self._tailnode = i.prev
i.next.prev, i.prev.next = i.prev, i.next
self._length -= 1
return i
return -1
原文：https://www.cnblogs.com/xuxingping/p/10946319.html