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