/usr/share/sumo/tools/net/OrderedMultiSet.py is in sumo-tools 0.15.0~dfsg-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | #!/usr/bin/env python
"""
@file netdiff.py
@author Jakob Erdmann
@date 2011-10-04
@version $Id: OrderedMultiSet.py 11571 2011-12-01 09:06:35Z bieker $
multi set with insertion-order iteration
based on OrderedSet by Raymond Hettinger (c) , MIT-License
[http://code.activestate.com/recipes/576694/]
SUMO, Simulation of Urban MObility; see http://sumo.sourceforge.net/
Copyright (C) 2011 DLR (http://www.dlr.de/) and contributors
All rights reserved
"""
import collections
KEY, PREV, NEXT = range(3)
class OrderedMultiSet(collections.MutableSet):
def __init__(self, iterable=None):
self.end = end = []
end += [None, end, end] # sentinel node for doubly linked list
self.map = collections.defaultdict(collections.deque) # key --> [(key, prev1, next1), (key, prev2, next2), ...]
self.size = 0
if iterable is not None:
self |= iterable
def __len__(self):
return self.size
def __contains__(self, key):
return key in self.map
def add(self, key):
self.size += 1
end = self.end
curr = end[PREV]
new = [key, curr, end]
curr[NEXT] = end[PREV] = new
self.map[key].append(new)
def discard(self, key):
if key in self.map:
self.size -= 1
deque = self.map[key]
key, prev, next = deque.popleft()
prev[NEXT] = next
next[PREV] = prev
if len(deque) == 0:
self.map.pop(key)
def __iter__(self):
end = self.end
curr = end[NEXT]
while curr is not end:
yield curr[KEY]
curr = curr[NEXT]
def __reversed__(self):
end = self.end
curr = end[PREV]
while curr is not end:
yield curr[KEY]
curr = curr[PREV]
def pop(self, last=True):
if not self:
raise KeyError('set is empty')
key = next(reversed(self)) if last else next(iter(self))
self.discard(key)
return key
def __repr__(self):
if not self:
return '%s()' % (self.__class__.__name__,)
return '%s(%r)' % (self.__class__.__name__, list(self))
def __eq__(self, other):
if isinstance(other, self.__class__):
return len(self) == len(other) and list(self) == list(other)
return set(self) == set(other)
def __del__(self):
self.clear() # remove circular references
def __sub__(self, other):
result = self.__class__()
for x in self:
result.add(x)
for x in other:
result.discard(x)
return result
def __or__(self, other):
result = self.__class__()
for x in self:
result.add(x)
for x in other:
result.add(x)
return result
|