Coverage for trimesh/iteration.py: 100%

1from collections import OrderedDict 

2from math import log2 

3from typing import Any 

4 

5from .typed import Callable, Iterable, NDArray, Sequence 

6 

7 

8def reduce_cascade(operation: Callable, items: Sequence | NDArray): 

9 """ 

10 Call an operation function in a cascaded pairwise way against a 

11 flat list of items. 

12 

13 This should produce the same result as `functools.reduce` 

14 if `operation` is commutable like addition or multiplication. 

15 This may be faster for an `operation` that runs with a speed 

16 proportional to its largest input, which mesh booleans appear to. 

17 

18 The union of a large number of small meshes appears to be 

19 "much faster" using this method. 

20 

21 This only differs from `functools.reduce` for commutative `operation` 

22 in that it returns `None` on empty inputs rather than `functools.reduce` 

23 which raises a `TypeError`. 

24 

25 For example on `a b c d e f g` this function would run and return: 

26 a b 

27 c d 

28 e f 

29 ab cd 

30 ef g 

31 abcd efg 

32 -> abcdefg 

33 

34 Where `functools.reduce` would run and return: 

35 a b 

36 ab c 

37 abc d 

38 abcd e 

39 abcde f 

40 abcdef g 

41 -> abcdefg 

42 

43 Parameters 

44 ---------- 

45 operation 

46 The function to call on pairs of items. 

47 items 

48 The flat list of items to apply operation against. 

49 """ 

50 if len(items) == 0: 

51 return None 

52 elif len(items) == 1: 

53 # skip the loop overhead for a single item 

54 return items[0] 

55 elif len(items) == 2: 

56 # skip the loop overhead for a single pair 

57 return operation(items[0], items[1]) 

58 

59 for _ in range(int(1 + log2(len(items)))): 

60 results = [] 

61 

62 # loop over pairs of items. 

63 items_mod = len(items) % 2 

64 for i in range(0, len(items) - items_mod, 2): 

65 results.append(operation(items[i], items[i + 1])) 

66 

67 # if we had a non-even number of items it will have been 

68 # skipped by the loop so append it to our list 

69 if items_mod != 0: 

70 results.append(items[-1]) 

71 

72 items = results 

73 

74 # logic should have reduced to a single item 

75 assert len(results) == 1 

76 

77 return results[0] 

78 

79 

80def chain(*args: Iterable[Any] | Any | None) -> list[Any]: 

81 """ 

82 A less principled version of `list(itertools.chain(*args))` that 

83 accepts non-iterable values, filters `None`, and returns a list 

84 rather than yielding values. 

85 

86 If all passed values are iterables this will return identical 

87 results to `list(itertools.chain(*args))`. 

88 

89 

90 Examples 

91 ---------- 

92 

93 In [1]: list(itertools.chain([1,2], [3])) 

94 Out[1]: [1, 2, 3] 

95 

96 In [2]: trimesh.util.chain([1,2], [3]) 

97 Out[2]: [1, 2, 3] 

98 

99 In [3]: trimesh.util.chain([1,2], [3], 4) 

100 Out[3]: [1, 2, 3, 4] 

101 

102 In [4]: list(itertools.chain([1,2], [3], 4)) 

103 ----> 1 list(itertools.chain([1,2], [3], 4)) 

104 TypeError: 'int' object is not iterable 

105 

106 In [5]: trimesh.util.chain([1,2], None, 3, None, [4], [], [], 5, []) 

107 Out[5]: [1, 2, 3, 4, 5] 

108 

109 

110 Parameters 

111 ----------- 

112 args 

113 Will be individually checked to see if they're iterable 

114 before either being appended or extended to a flat list. 

115 

116 

117 Returns 

118 ---------- 

119 chained 

120 The values in a flat list. 

121 """ 

122 # collect values to a flat list 

123 chained = [] 

124 # extend if it's a sequence, otherwise append 

125 [ 

126 chained.extend(a) 

127 if (hasattr(a, "__iter__") and not isinstance(a, (str, bytes))) 

128 else chained.append(a) 

129 for a in args 

130 if a is not None 

131 ] 

132 return chained 

133 

134 

135class IndexedDict(OrderedDict): 

136 """ 

137 An append-only `OrderedDict` which knows what position a key was inserted at. 

138 

139 Useful anywhere values are referenced by *position* but keyed by content so 

140 duplicates are only stored once: the only other spelling is 

141 `list(d.keys()).index(key)`, which allocates every key and scans it, i.e. 

142 quadratic. Looking up the position of all `n` keys once each: 

143 

144 n list(keys()).index() this class 

145 2000 0.061s 0.00007s 

146 4000 0.262s 0.00012s 

147 8000 1.135s 0.00026s 

148 

149 Removing or reordering a key would shift the position of every key after it, 

150 so `__delitem__`, `pop`, `popitem`, and `move_to_end` raise: the supported 

151 way to remove is `clear` followed by `update`. 

152 

153 Examples 

154 ---------- 

155 

156 In [1]: IndexedDict({"a": 1, "b": 2, "c": 3}).index("c") 

157 Out[1]: 2 

158 """ 

159 

160 # subclasses `OrderedDict` rather than `dict` as it routes `__init__`, `update`, 

161 # `setdefault`, `|=`, and `copy` through `__setitem__`: one place records a position 

162 

163 def __init__(self, *args, **kwargs): 

164 # must exist before `super` starts routing through `__setitem__` 

165 self._position = {} 

166 super().__init__(*args, **kwargs) 

167 

168 def __setitem__(self, key, value): 

169 if key not in self: 

170 self._position[key] = len(self) 

171 super().__setitem__(key, value) 

172 

173 def _forbidden(self, *args, **kwargs): 

174 raise TypeError("`IndexedDict` is append-only: use `clear` and `update`") 

175 

176 # removing or reordering a key shifts the position of every key after it 

177 __delitem__ = pop = popitem = move_to_end = _forbidden 

178 

179 def clear(self) -> None: 

180 super().clear() 

181 self._position.clear() 

182 

183 def index(self, key) -> int: 

184 """ 

185 Which position in insertion order was `key` inserted at. 

186 """ 

187 return self._position[key]