| 1 | """Various utility functions."""
|
|---|
| 2 | from collections import namedtuple, OrderedDict
|
|---|
| 3 |
|
|---|
| 4 |
|
|---|
| 5 | __unittest = True
|
|---|
| 6 |
|
|---|
| 7 | _MAX_LENGTH = 80
|
|---|
| 8 | def 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 |
|
|---|
| 18 | def strclass(cls):
|
|---|
| 19 | return "%s.%s" % (cls.__module__, cls.__name__)
|
|---|
| 20 |
|
|---|
| 21 | def 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 |
|
|---|
| 62 | def 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 |
|
|---|
| 100 | def _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 |
|
|---|
| 135 | def _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 |
|
|---|
| 142 | def _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
|
|---|
