183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh"""Various utility functions.""" 283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehfrom collections import namedtuple, OrderedDict 383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh__unittest = True 683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh_MAX_LENGTH = 80 883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehdef safe_repr(obj, short=False): 983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh try: 1083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh result = repr(obj) 1183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh except Exception: 1283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh result = object.__repr__(obj) 1383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if not short or len(result) < _MAX_LENGTH: 1483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return result 1583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return result[:_MAX_LENGTH] + ' [truncated]...' 1683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 1783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 1883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehdef strclass(cls): 1983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return "%s.%s" % (cls.__module__, cls.__name__) 2083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 2183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehdef sorted_list_difference(expected, actual): 2283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Finds elements in only one or the other of two, sorted input lists. 2383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 2483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh Returns a two-element tuple of lists. The first list contains those 2583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh elements in the "expected" list but not in the "actual" list, and the 2683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh second contains those elements in the "actual" list but not in the 2783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh "expected" list. Duplicate elements in either input list are ignored. 2883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """ 2983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh i = j = 0 3083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh missing = [] 3183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh unexpected = [] 3283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh while True: 3383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh try: 3483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh e = expected[i] 3583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh a = actual[j] 3683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if e < a: 3783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh missing.append(e) 3883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh i += 1 3983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh while expected[i] == e: 4083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh i += 1 4183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh elif e > a: 4283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh unexpected.append(a) 4383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh j += 1 4483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh while actual[j] == a: 4583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh j += 1 4683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh else: 4783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh i += 1 4883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh try: 4983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh while expected[i] == e: 5083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh i += 1 5183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh finally: 5283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh j += 1 5383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh while actual[j] == a: 5483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh j += 1 5583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh except IndexError: 5683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh missing.extend(expected[i:]) 5783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh unexpected.extend(actual[j:]) 5883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh break 5983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return missing, unexpected 6083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 6183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 6283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehdef unorderable_list_difference(expected, actual, ignore_duplicate=False): 6383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Same behavior as sorted_list_difference but 6483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for lists of unorderable items (like dicts). 6583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 6683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh As it does a linear search per item (remove) it 6783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh has O(n*n) performance. 6883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """ 6983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh missing = [] 7083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh unexpected = [] 7183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh while expected: 7283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh item = expected.pop() 7383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh try: 7483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh actual.remove(item) 7583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh except ValueError: 7683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh missing.append(item) 7783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if ignore_duplicate: 7883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for lst in expected, actual: 7983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh try: 8083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh while True: 8183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh lst.remove(item) 8283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh except ValueError: 8383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh pass 8483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if ignore_duplicate: 8583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh while actual: 8683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh item = actual.pop() 8783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh unexpected.append(item) 8883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh try: 8983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh while True: 9083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh actual.remove(item) 9183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh except ValueError: 9283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh pass 9383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return missing, unexpected 9483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 9583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # anything left in actual is unexpected 9683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return missing, actual 9783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 9883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh_Mismatch = namedtuple('Mismatch', 'actual expected value') 9983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 10083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehdef _count_diff_all_purpose(actual, expected): 10183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 'Returns list of (cnt_act, cnt_exp, elem) triples where the counts differ' 10283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # elements need not be hashable 10383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh s, t = list(actual), list(expected) 10483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh m, n = len(s), len(t) 10583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh NULL = object() 10683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh result = [] 10783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for i, elem in enumerate(s): 10883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if elem is NULL: 10983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh continue 11083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh cnt_s = cnt_t = 0 11183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for j in range(i, m): 11283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if s[j] == elem: 11383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh cnt_s += 1 11483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh s[j] = NULL 11583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for j, other_elem in enumerate(t): 11683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if other_elem == elem: 11783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh cnt_t += 1 11883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh t[j] = NULL 11983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if cnt_s != cnt_t: 12083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh diff = _Mismatch(cnt_s, cnt_t, elem) 12183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh result.append(diff) 12283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 12383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for i, elem in enumerate(t): 12483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if elem is NULL: 12583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh continue 12683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh cnt_t = 0 12783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for j in range(i, n): 12883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if t[j] == elem: 12983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh cnt_t += 1 13083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh t[j] = NULL 13183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh diff = _Mismatch(0, cnt_t, elem) 13283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh result.append(diff) 13383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return result 13483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 13583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehdef _ordered_count(iterable): 13683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 'Return dict of element counts, in the order they were first seen' 13783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh c = OrderedDict() 13883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for elem in iterable: 13983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh c[elem] = c.get(elem, 0) + 1 14083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return c 14183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 14283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehdef _count_diff_hashable(actual, expected): 14383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 'Returns list of (cnt_act, cnt_exp, elem) triples where the counts differ' 14483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # elements must be hashable 14583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh s, t = _ordered_count(actual), _ordered_count(expected) 14683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh result = [] 14783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for elem, cnt_s in s.items(): 14883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh cnt_t = t.get(elem, 0) 14983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if cnt_s != cnt_t: 15083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh diff = _Mismatch(cnt_s, cnt_t, elem) 15183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh result.append(diff) 15283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for elem, cnt_t in t.items(): 15383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if elem not in s: 15483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh diff = _Mismatch(0, cnt_t, elem) 15583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh result.append(diff) 15683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return result 157