1"""Various utility functions.""" 2from collections import namedtuple, OrderedDict 3 4 5__unittest = True 6 7_MAX_LENGTH = 80 8def safe_repr(obj, short=False): 9 try: 10 result = repr(obj) 11 except Exception: 12 result = object.__repr__(obj) 13 if not short or len(result) < _MAX_LENGTH: 14 return result 15 return result[:_MAX_LENGTH] + ' [truncated]...' 16 17 18def strclass(cls): 19 return "%s.%s" % (cls.__module__, cls.__name__) 20 21def sorted_list_difference(expected, actual): 22 """Finds elements in only one or the other of two, sorted input lists. 23 24 Returns a two-element tuple of lists. The first list contains those 25 elements in the "expected" list but not in the "actual" list, and the 26 second contains those elements in the "actual" list but not in the 27 "expected" list. Duplicate elements in either input list are ignored. 28 """ 29 i = j = 0 30 missing = [] 31 unexpected = [] 32 while True: 33 try: 34 e = expected[i] 35 a = actual[j] 36 if e < a: 37 missing.append(e) 38 i += 1 39 while expected[i] == e: 40 i += 1 41 elif e > a: 42 unexpected.append(a) 43 j += 1 44 while actual[j] == a: 45 j += 1 46 else: 47 i += 1 48 try: 49 while expected[i] == e: 50 i += 1 51 finally: 52 j += 1 53 while actual[j] == a: 54 j += 1 55 except IndexError: 56 missing.extend(expected[i:]) 57 unexpected.extend(actual[j:]) 58 break 59 return missing, unexpected 60 61 62def unorderable_list_difference(expected, actual, ignore_duplicate=False): 63 """Same behavior as sorted_list_difference but 64 for lists of unorderable items (like dicts). 65 66 As it does a linear search per item (remove) it 67 has O(n*n) performance. 68 """ 69 missing = [] 70 unexpected = [] 71 while expected: 72 item = expected.pop() 73 try: 74 actual.remove(item) 75 except ValueError: 76 missing.append(item) 77 if ignore_duplicate: 78 for lst in expected, actual: 79 try: 80 while True: 81 lst.remove(item) 82 except ValueError: 83 pass 84 if ignore_duplicate: 85 while actual: 86 item = actual.pop() 87 unexpected.append(item) 88 try: 89 while True: 90 actual.remove(item) 91 except ValueError: 92 pass 93 return missing, unexpected 94 95 # anything left in actual is unexpected 96 return missing, actual 97 98_Mismatch = namedtuple('Mismatch', 'actual expected value') 99 100def _count_diff_all_purpose(actual, expected): 101 'Returns list of (cnt_act, cnt_exp, elem) triples where the counts differ' 102 # elements need not be hashable 103 s, t = list(actual), list(expected) 104 m, n = len(s), len(t) 105 NULL = object() 106 result = [] 107 for i, elem in enumerate(s): 108 if elem is NULL: 109 continue 110 cnt_s = cnt_t = 0 111 for j in range(i, m): 112 if s[j] == elem: 113 cnt_s += 1 114 s[j] = NULL 115 for j, other_elem in enumerate(t): 116 if other_elem == elem: 117 cnt_t += 1 118 t[j] = NULL 119 if cnt_s != cnt_t: 120 diff = _Mismatch(cnt_s, cnt_t, elem) 121 result.append(diff) 122 123 for i, elem in enumerate(t): 124 if elem is NULL: 125 continue 126 cnt_t = 0 127 for j in range(i, n): 128 if t[j] == elem: 129 cnt_t += 1 130 t[j] = NULL 131 diff = _Mismatch(0, cnt_t, elem) 132 result.append(diff) 133 return result 134 135def _ordered_count(iterable): 136 'Return dict of element counts, in the order they were first seen' 137 c = OrderedDict() 138 for elem in iterable: 139 c[elem] = c.get(elem, 0) + 1 140 return c 141 142def _count_diff_hashable(actual, expected): 143 'Returns list of (cnt_act, cnt_exp, elem) triples where the counts differ' 144 # elements must be hashable 145 s, t = _ordered_count(actual), _ordered_count(expected) 146 result = [] 147 for elem, cnt_s in s.items(): 148 cnt_t = t.get(elem, 0) 149 if cnt_s != cnt_t: 150 diff = _Mismatch(cnt_s, cnt_t, elem) 151 result.append(diff) 152 for elem, cnt_t in t.items(): 153 if elem not in s: 154 diff = _Mismatch(0, cnt_t, elem) 155 result.append(diff) 156 return result 157