1 # Copyright (C) 2014 Nippon Telegraph and Telephone Corporation.
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
13 # See the License for the specific language governing permissions and
14 # limitations under the License.
18 from sys import intern
21 class CircularListType(object):
22 """Instances of this class represent a specific type of list.
23 Nodes are linked in a circular fashion, using attributes on the
28 ItemList = CircularListType(next_attr='_next',
34 The created list has the following properties:
36 - A node can be inserted O(1) time at the head, tail, or
37 after/before another specified node.
39 - A node can be removed in O(1) time from any list it may be on,
40 without providing a reference to the list.
42 - The current node in an iteration can be deleted safely.
47 """An object that represents a list.
49 This class is not expected to be used directly by clients. Rather, they
50 would use the 'create' method of a CircularListType object to create an
54 # Define the set of valid attributes so as to make the list
57 # We override __getattr__ and __setattr__ so as to store the
58 # the next and previous references on the list head in
59 # _next_slot_ and _prev_slot_ respectively.
60 __slots__ = ["list_type", "head", "_next_slot_",
63 def __init__(self, list_type):
64 self.list_type = list_type
66 # Save memory by using the List object itself as the head.
68 self.list_type.node_init(self.head)
70 def __getattr__(self, name):
71 if(name == self.list_type.next_name):
72 return self._next_slot_
74 if(name == self.list_type.prev_name):
75 return self._prev_slot_
77 raise AttributeError(name)
79 def __setattr__(self, name, value):
80 if(name in CircularListType.List.__slots__):
81 object.__setattr__(self, name, value)
84 if(name == self.list_type.next_name):
85 self._next_slot_ = value
88 if(name == self.list_type.prev_name):
89 self._prev_slot_ = value
92 raise AttributeError(name)
95 return not self.list_type.node_is_on_list(self.head)
98 """Remove all items from the list."""
100 # Make sure that all items are unlinked.
104 def is_on_list(self, node):
105 return self.list_type.node_is_on_list(node)
107 def append(self, node):
108 self.list_type.node_insert_before(self.head, node)
110 def prepend(self, node):
111 self.list_type.node_insert_after(self.head, node)
114 return self.generator()
116 def remove(self, node):
117 """List the given node from the list.
119 Note that this does not verify that the node is on this
120 list. It could even be on a different list.
122 self.list_type.node_unlink(node)
124 self.list_type.node_del_attrs(node)
127 """Remove the first item in the list and return it."""
128 node = self.list_type.node_next(self.head)
129 if(node is self.head):
136 """Enables iteration over the list.
138 The current item can safely be removed from the list during
141 # Keep a pointer to the next node when returning the
142 # current node. This allows the caller to remove the
143 # current node safely.
144 node = self.list_type.node_next(self.head)
145 next = self.list_type.node_next(node)
146 while(node is not self.head):
150 next = self.list_type.node_next(node)
153 # CircularListType methods
156 def __init__(self, next_attr_name=None, prev_attr_name=None):
157 """Initializes this list.
159 next_attr_name: The name of the attribute that holds a reference
160 to the next item in the list.
162 prev_attr_name: the name of the attribute that holds a reference
163 to the previous item in the list.
166 # Keep an interned version of the attribute names. This should
167 # speed up the process of looking up the attributes.
168 self.next_name = intern(next_attr_name)
169 self.prev_name = intern(prev_attr_name)
172 return CircularListType.List(self)
175 """Make a CircularListType instance look like a class by
176 creating a list object.
180 def node_init(self, node):
181 assert(not self.node_is_on_list(node))
183 # Set the node to point to itself as the previous and next
185 self.node_set_next(node, node)
186 self.node_set_prev(node, node)
188 def node_next(self, node):
190 return getattr(node, self.next_name)
191 except AttributeError:
194 def node_set_next(self, node, next):
195 setattr(node, self.next_name, next)
197 def node_prev(self, node):
199 return getattr(node, self.prev_name)
200 except AttributeError:
203 def node_set_prev(self, node, prev):
204 setattr(node, self.prev_name, prev)
206 def node_del_attrs(self, node):
207 """Remove all attributes that are used for putting this node
208 on this type of list.
211 delattr(node, self.next_name)
212 delattr(node, self.prev_name)
213 except AttributeError:
216 def node_is_on_list(self, node):
217 """Returns True if this node is on *some* list.
219 A node is not on any list if it is linked to itself, or if it
220 does not have the next and/prev attributes at all.
222 next = self.node_next(node)
223 if next == node or next is None:
224 assert(self.node_prev(node) is next)
229 def node_insert_after(self, node, new_node):
230 """Insert the new node after node."""
232 assert(not self.node_is_on_list(new_node))
233 assert(node is not new_node)
235 next = self.node_next(node)
236 assert(next is not None)
237 self.node_set_next(node, new_node)
238 self.node_set_prev(new_node, node)
240 self.node_set_next(new_node, next)
241 self.node_set_prev(next, new_node)
243 def node_insert_before(self, node, new_node):
244 """Insert the new node before node."""
246 assert(not self.node_is_on_list(new_node))
247 assert(node is not new_node)
249 prev = self.node_prev(node)
250 assert(prev is not None)
251 self.node_set_prev(node, new_node)
252 self.node_set_next(new_node, node)
254 self.node_set_prev(new_node, prev)
255 self.node_set_next(prev, new_node)
257 def node_unlink(self, node):
259 if not self.node_is_on_list(node):
262 prev = self.node_prev(node)
263 next = self.node_next(node)
265 self.node_set_next(prev, next)
266 self.node_set_prev(next, prev)
268 self.node_set_next(node, node)
269 self.node_set_prev(node, node)