def reverse_lookup()

in multiset_codec/msbst.py [0:0]

• 18 lines of code
• 6 McCabe index (conditional complexity)

def reverse_lookup(multiset, idx):
    '''
    Looks up the cumulative (start) and frequency (freq) counts,
    as well as the symbol x, at index idx.
    '''
    size, y, left, right = multiset or (0, (), (), ())
    assert 0 <= idx < size
    y_start = left[0] if left else 0
    y_freq = size - y_start - (right[0] if right else 0)
    if idx < y_start:
        (start, freq), x = reverse_lookup(left, idx)
    elif idx >= y_start + y_freq:
        size_not_right = size - right[0]
        (start, freq), x = reverse_lookup(right, idx - size_not_right)
        start = start + size_not_right
    else:
        x, start, freq = y, y_start, y_freq
    return (start, freq), x