Coverage for src/P4OO/_OrderedSet.py: 82%

1""" OrderedSet 

2 

3Copied from http://code.activestate.com/recipes/576694/ 

4 

5Created by Raymond Hettinger 

6Licensed under the MIT License 

7 

8Modified by David L. Armstrong to avoid use of 'next' keyword 

9and add indexing support 

10""" 

11 

12import collections.abc 

13 

14KEY, PREV, NEXT = range(3) 

15 

16 

17class OrderedSet(collections.abc.MutableSet): 

18 """ Set that remembers original insertion order. 

19 """ 

20 

21 def __init__(self, iterable=None): 

22 self.end = end = [] 

23 end += [None, end, end] # sentinel node for doubly linked list 

24 self.map = {} # key --> [key, prev, next] 

25 if iterable is not None: 

26 self |= iterable 

27 

28 def __len__(self): 

29 return len(self.map) 

30 

31 def __contains__(self, key): 

32 return key in self.map 

33 

34 def add(self, key): 

35 if key not in self.map: 

36 end = self.end 

37 curr = end[PREV] 

38 curr[NEXT] = end[PREV] = self.map[key] = [key, curr, end] 

39 

40 def discard(self, key): 

41 if key in self.map: 

42 key, prevItem, nextItem = self.map.pop(key) 

43 prevItem[NEXT] = nextItem 

44 nextItem[PREV] = prevItem 

45 

46 # indexing support 

47 def __getitem__(self, key): 

48 if not isinstance(key, int): 

49 raise KeyError(key) 

50 

51 if key >= len(self) or key < (len(self) * -1): 

52 raise KeyError(key) 

53 

54 counter = 0 

55 if key >= 0: 

56 item = self.end 

57 while counter <= key: 

58 item = item[NEXT] 

59 counter += 1 

60 return item[KEY] 

61 item = self.end 

62 while counter > key: # > because 0 is the start, not 1 

63 item = item[PREV] 

64 counter -= 1 

65 return item[KEY] 

66 

67 def __iter__(self): 

68 end = self.end 

69 curr = end[NEXT] 

70 while curr is not end: 

71 yield curr[KEY] 

72 curr = curr[NEXT] 

73 

74 def __reversed__(self): 

75 end = self.end 

76 curr = end[PREV] 

77 while curr is not end: 

78 yield curr[KEY] 

79 curr = curr[PREV] 

80 

81 def pop(self, last=True): 

82 if not self: 

83 raise KeyError('set is empty') 

84 key = next(reversed(self)) if last else next(iter(self)) 

85 self.discard(key) 

86 return key 

87 

88 def __repr__(self): 

89 if not self: 

90 return '%s()' % (self.__class__.__name__,) 

91 return '%s(%r)' % (self.__class__.__name__, list(self)) 

92 

93 def __eq__(self, other): 

94 if isinstance(other, OrderedSet): 

95 return len(self) == len(other) and list(self) == list(other) 

96 return set(self) == set(other) 

97 

98 def __del__(self): 

99 self.clear() # remove circular references