|
| 1 | +# Test for utimeq module which implements task queue with support for |
| 2 | +# wraparound time (utime.ticks_ms() style). |
| 3 | +try: |
| 4 | + from utime import ticks_add, ticks_diff |
| 5 | + from utimeq import utimeq |
| 6 | +except ImportError: |
| 7 | + print("SKIP") |
| 8 | + import sys |
| 9 | + sys.exit() |
| 10 | + |
| 11 | +DEBUG = 0 |
| 12 | + |
| 13 | +MAX = ticks_add(0, -1) |
| 14 | +MODULO_HALF = MAX // 2 + 1 |
| 15 | + |
| 16 | +if DEBUG: |
| 17 | + def dprint(*v): |
| 18 | + print(*v) |
| 19 | +else: |
| 20 | + def dprint(*v): |
| 21 | + pass |
| 22 | + |
| 23 | +# Try not to crash on invalid data |
| 24 | +h = utimeq(10) |
| 25 | +try: |
| 26 | + h.push(1) |
| 27 | + assert False |
| 28 | +except TypeError: |
| 29 | + pass |
| 30 | + |
| 31 | +try: |
| 32 | + h.pop(1) |
| 33 | + assert False |
| 34 | +except IndexError: |
| 35 | + pass |
| 36 | + |
| 37 | + |
| 38 | +def pop_all(h): |
| 39 | + l = [] |
| 40 | + while h: |
| 41 | + item = [0, 0, 0] |
| 42 | + h.pop(item) |
| 43 | + #print("!", item) |
| 44 | + l.append(tuple(item)) |
| 45 | + dprint(l) |
| 46 | + return l |
| 47 | + |
| 48 | +def add(h, v): |
| 49 | + h.push(v, 0, 0) |
| 50 | + dprint("-----") |
| 51 | + #h.dump() |
| 52 | + dprint("-----") |
| 53 | + |
| 54 | +h = utimeq(10) |
| 55 | +add(h, 0) |
| 56 | +add(h, MAX) |
| 57 | +add(h, MAX - 1) |
| 58 | +add(h, 101) |
| 59 | +add(h, 100) |
| 60 | +add(h, MAX - 2) |
| 61 | +dprint(h) |
| 62 | +l = pop_all(h) |
| 63 | +for i in range(len(l) - 1): |
| 64 | + diff = ticks_diff(l[i + 1][0], l[i][0]) |
| 65 | + assert diff > 0 |
| 66 | + |
| 67 | +def edge_case(edge, offset): |
| 68 | + h = utimeq(10) |
| 69 | + add(h, ticks_add(0, offset)) |
| 70 | + add(h, ticks_add(edge, offset)) |
| 71 | + dprint(h) |
| 72 | + l = pop_all(h) |
| 73 | + diff = ticks_diff(l[1][0], l[0][0]) |
| 74 | + dprint(diff, diff > 0) |
| 75 | + return diff |
| 76 | + |
| 77 | +dprint("===") |
| 78 | +diff = edge_case(MODULO_HALF - 1, 0) |
| 79 | +assert diff == MODULO_HALF - 1 |
| 80 | +assert edge_case(MODULO_HALF - 1, 100) == diff |
| 81 | +assert edge_case(MODULO_HALF - 1, -100) == diff |
| 82 | + |
| 83 | +# We expect diff to be always positive, per the definition of heappop() which should return |
| 84 | +# the smallest value. |
| 85 | +# This is the edge case where this invariant breaks, due to assymetry of two's-complement |
| 86 | +# range - there's one more negative integer than positive, so heappushing values like below |
| 87 | +# will then make ticks_diff() return the minimum negative value. We could make heappop |
| 88 | +# return them in a different order, but ticks_diff() result would be the same. Conclusion: |
| 89 | +# never add to a heap values where (a - b) == MODULO_HALF (and which are >= MODULO_HALF |
| 90 | +# ticks apart in real time of course). |
| 91 | +dprint("===") |
| 92 | +diff = edge_case(MODULO_HALF, 0) |
| 93 | +assert diff == -MODULO_HALF |
| 94 | +assert edge_case(MODULO_HALF, 100) == diff |
| 95 | +assert edge_case(MODULO_HALF, -100) == diff |
| 96 | + |
| 97 | +dprint("===") |
| 98 | +diff = edge_case(MODULO_HALF + 1, 0) |
| 99 | +assert diff == MODULO_HALF - 1 |
| 100 | +assert edge_case(MODULO_HALF + 1, 100) == diff |
| 101 | +assert edge_case(MODULO_HALF + 1, -100) == diff |
| 102 | + |
| 103 | +print("OK") |
0 commit comments