Coverage for /usr/lib/python3/dist-packages/sympy/core/sorting.py: 77%

1from collections import defaultdict 

2 

3from .sympify import sympify, SympifyError 

4from sympy.utilities.iterables import iterable, uniq 

5 

6 

7__all__ = ['default_sort_key', 'ordered'] 

8 

9 

10def default_sort_key(item, order=None): 

11 """Return a key that can be used for sorting. 

12 

13 The key has the structure: 

14 

15 (class_key, (len(args), args), exponent.sort_key(), coefficient) 

16 

17 This key is supplied by the sort_key routine of Basic objects when 

18 ``item`` is a Basic object or an object (other than a string) that 

19 sympifies to a Basic object. Otherwise, this function produces the 

20 key. 

21 

22 The ``order`` argument is passed along to the sort_key routine and is 

23 used to determine how the terms *within* an expression are ordered. 

24 (See examples below) ``order`` options are: 'lex', 'grlex', 'grevlex', 

25 and reversed values of the same (e.g. 'rev-lex'). The default order 

26 value is None (which translates to 'lex'). 

27 

28 Examples 

29 ======== 

30 

31 >>> from sympy import S, I, default_sort_key, sin, cos, sqrt 

32 >>> from sympy.core.function import UndefinedFunction 

33 >>> from sympy.abc import x 

34 

35 The following are equivalent ways of getting the key for an object: 

36 

37 >>> x.sort_key() == default_sort_key(x) 

38 True 

39 

40 Here are some examples of the key that is produced: 

41 

42 >>> default_sort_key(UndefinedFunction('f')) 

43 ((0, 0, 'UndefinedFunction'), (1, ('f',)), ((1, 0, 'Number'), 

44 (0, ()), (), 1), 1) 

45 >>> default_sort_key('1') 

46 ((0, 0, 'str'), (1, ('1',)), ((1, 0, 'Number'), (0, ()), (), 1), 1) 

47 >>> default_sort_key(S.One) 

48 ((1, 0, 'Number'), (0, ()), (), 1) 

49 >>> default_sort_key(2) 

50 ((1, 0, 'Number'), (0, ()), (), 2) 

51 

52 While sort_key is a method only defined for SymPy objects, 

53 default_sort_key will accept anything as an argument so it is 

54 more robust as a sorting key. For the following, using key= 

55 lambda i: i.sort_key() would fail because 2 does not have a sort_key 

56 method; that's why default_sort_key is used. Note, that it also 

57 handles sympification of non-string items likes ints: 

58 

59 >>> a = [2, I, -I] 

60 >>> sorted(a, key=default_sort_key) 

61 [2, -I, I] 

62 

63 The returned key can be used anywhere that a key can be specified for 

64 a function, e.g. sort, min, max, etc...: 

65 

66 >>> a.sort(key=default_sort_key); a[0] 

67 2 

68 >>> min(a, key=default_sort_key) 

69 2 

70 

71 Notes 

72 ===== 

73 

74 The key returned is useful for getting items into a canonical order 

75 that will be the same across platforms. It is not directly useful for 

76 sorting lists of expressions: 

77 

78 >>> a, b = x, 1/x 

79 

80 Since ``a`` has only 1 term, its value of sort_key is unaffected by 

81 ``order``: 

82 

83 >>> a.sort_key() == a.sort_key('rev-lex') 

84 True 

85 

86 If ``a`` and ``b`` are combined then the key will differ because there 

87 are terms that can be ordered: 

88 

89 >>> eq = a + b 

90 >>> eq.sort_key() == eq.sort_key('rev-lex') 

91 False 

92 >>> eq.as_ordered_terms() 

93 [x, 1/x] 

94 >>> eq.as_ordered_terms('rev-lex') 

95 [1/x, x] 

96 

97 But since the keys for each of these terms are independent of ``order``'s 

98 value, they do not sort differently when they appear separately in a list: 

99 

100 >>> sorted(eq.args, key=default_sort_key) 

101 [1/x, x] 

102 >>> sorted(eq.args, key=lambda i: default_sort_key(i, order='rev-lex')) 

103 [1/x, x] 

104 

105 The order of terms obtained when using these keys is the order that would 

106 be obtained if those terms were *factors* in a product. 

107 

108 Although it is useful for quickly putting expressions in canonical order, 

109 it does not sort expressions based on their complexity defined by the 

110 number of operations, power of variables and others: 

111 

112 >>> sorted([sin(x)*cos(x), sin(x)], key=default_sort_key) 

113 [sin(x)*cos(x), sin(x)] 

114 >>> sorted([x, x**2, sqrt(x), x**3], key=default_sort_key) 

115 [sqrt(x), x, x**2, x**3] 

116 

117 See Also 

118 ======== 

119 

120 ordered, sympy.core.expr.Expr.as_ordered_factors, sympy.core.expr.Expr.as_ordered_terms 

121 

122 """ 

123 from .basic import Basic 

124 from .singleton import S 

125 

126 if isinstance(item, Basic): 

127 return item.sort_key(order=order) 

128 

129 if iterable(item, exclude=str): 

130 if isinstance(item, dict): 

131 args = item.items() 

132 unordered = True 

133 elif isinstance(item, set): 

134 args = item 

135 unordered = True 

136 else: 

137 # e.g. tuple, list 

138 args = list(item) 

139 unordered = False 

140 

141 args = [default_sort_key(arg, order=order) for arg in args] 

142 

143 if unordered: 

144 # e.g. dict, set 

145 args = sorted(args) 

146 

147 cls_index, args = 10, (len(args), tuple(args)) 

148 else: 

149 if not isinstance(item, str): 

150 try: 

151 item = sympify(item, strict=True) 

152 except SympifyError: 

153 # e.g. lambda x: x 

154 pass 

155 else: 

156 if isinstance(item, Basic): 

157 # e.g int -> Integer 

158 return default_sort_key(item) 

159 # e.g. UndefinedFunction 

160 

161 # e.g. str 

162 cls_index, args = 0, (1, (str(item),)) 

163 

164 return (cls_index, 0, item.__class__.__name__ 

165 ), args, S.One.sort_key(), S.One 

166 

167 

168def _node_count(e): 

169 # this not only counts nodes, it affirms that the 

170 # args are Basic (i.e. have an args property). If 

171 # some object has a non-Basic arg, it needs to be 

172 # fixed since it is intended that all Basic args 

173 # are of Basic type (though this is not easy to enforce). 

174 if e.is_Float: 

175 return 0.5 

176 return 1 + sum(map(_node_count, e.args)) 

177 

178 

179def _nodes(e): 

180 """ 

181 A helper for ordered() which returns the node count of ``e`` which 

182 for Basic objects is the number of Basic nodes in the expression tree 

183 but for other objects is 1 (unless the object is an iterable or dict 

184 for which the sum of nodes is returned). 

185 """ 

186 from .basic import Basic 

187 from .function import Derivative 

188 

189 if isinstance(e, Basic): 

190 if isinstance(e, Derivative): 

191 return _nodes(e.expr) + sum(i[1] if i[1].is_Number else 

192 _nodes(i[1]) for i in e.variable_count) 

193 return _node_count(e) 

194 elif iterable(e): 

195 return 1 + sum(_nodes(ei) for ei in e) 

196 elif isinstance(e, dict): 

197 return 1 + sum(_nodes(k) + _nodes(v) for k, v in e.items()) 

198 else: 

199 return 1 

200 

201 

202def ordered(seq, keys=None, default=True, warn=False): 

203 """Return an iterator of the seq where keys are used to break ties in 

204 a conservative fashion: if, after applying a key, there are no ties 

205 then no other keys will be computed. 

206 

207 Two default keys will be applied if 1) keys are not provided or 2) the 

208 given keys do not resolve all ties (but only if ``default`` is True). The 

209 two keys are ``_nodes`` (which places smaller expressions before large) and 

210 ``default_sort_key`` which (if the ``sort_key`` for an object is defined 

211 properly) should resolve any ties. 

212 

213 If ``warn`` is True then an error will be raised if there were no 

214 keys remaining to break ties. This can be used if it was expected that 

215 there should be no ties between items that are not identical. 

216 

217 Examples 

218 ======== 

219 

220 >>> from sympy import ordered, count_ops 

221 >>> from sympy.abc import x, y 

222 

223 The count_ops is not sufficient to break ties in this list and the first 

224 two items appear in their original order (i.e. the sorting is stable): 

225 

226 >>> list(ordered([y + 2, x + 2, x**2 + y + 3], 

227 ... count_ops, default=False, warn=False)) 

228 ... 

229 [y + 2, x + 2, x**2 + y + 3] 

230 

231 The default_sort_key allows the tie to be broken: 

232 

233 >>> list(ordered([y + 2, x + 2, x**2 + y + 3])) 

234 ... 

235 [x + 2, y + 2, x**2 + y + 3] 

236 

237 Here, sequences are sorted by length, then sum: 

238 

239 >>> seq, keys = [[[1, 2, 1], [0, 3, 1], [1, 1, 3], [2], [1]], [ 

240 ... lambda x: len(x), 

241 ... lambda x: sum(x)]] 

242 ... 

243 >>> list(ordered(seq, keys, default=False, warn=False)) 

244 [[1], [2], [1, 2, 1], [0, 3, 1], [1, 1, 3]] 

245 

246 If ``warn`` is True, an error will be raised if there were not 

247 enough keys to break ties: 

248 

249 >>> list(ordered(seq, keys, default=False, warn=True)) 

250 Traceback (most recent call last): 

251 ... 

252 ValueError: not enough keys to break ties 

253 

254 

255 Notes 

256 ===== 

257 

258 The decorated sort is one of the fastest ways to sort a sequence for 

259 which special item comparison is desired: the sequence is decorated, 

260 sorted on the basis of the decoration (e.g. making all letters lower 

261 case) and then undecorated. If one wants to break ties for items that 

262 have the same decorated value, a second key can be used. But if the 

263 second key is expensive to compute then it is inefficient to decorate 

264 all items with both keys: only those items having identical first key 

265 values need to be decorated. This function applies keys successively 

266 only when needed to break ties. By yielding an iterator, use of the 

267 tie-breaker is delayed as long as possible. 

268 

269 This function is best used in cases when use of the first key is 

270 expected to be a good hashing function; if there are no unique hashes 

271 from application of a key, then that key should not have been used. The 

272 exception, however, is that even if there are many collisions, if the 

273 first group is small and one does not need to process all items in the 

274 list then time will not be wasted sorting what one was not interested 

275 in. For example, if one were looking for the minimum in a list and 

276 there were several criteria used to define the sort order, then this 

277 function would be good at returning that quickly if the first group 

278 of candidates is small relative to the number of items being processed. 

279 

280 """ 

281 

282 d = defaultdict(list) 

283 if keys: 

284 if isinstance(keys, (list, tuple)): 

285 keys = list(keys) 

286 f = keys.pop(0) 

287 else: 

288 f = keys 

289 keys = [] 

290 for a in seq: 

291 d[f(a)].append(a) 

292 else: 

293 if not default: 

294 raise ValueError('if default=False then keys must be provided') 

295 d[None].extend(seq) 

296 

297 for k, value in sorted(d.items()): 

298 if len(value) > 1: 

299 if keys: 

300 value = ordered(value, keys, default, warn) 

301 elif default: 

302 value = ordered(value, (_nodes, default_sort_key,), 

303 default=False, warn=warn) 

304 elif warn: 

305 u = list(uniq(value)) 

306 if len(u) > 1: 

307 raise ValueError( 

308 'not enough keys to break ties: %s' % u) 

309 yield from value