multi_index_search.py

""" Proof of concept of looking up a matching value based on multiple indexes
by reverse sorting and searching the combinations. O^log n I believe.
"""

from itertools import combinations

class Lookup:
    def __init__(self, name=None):
        self.name = name
        self.index = {}

    def store(self, value, keys):
        key = tuple(sorted(keys.items()))
        self.index[key] = value

    def query(self, keys):
        stack = sorted(keys.items())

        try:
            return self.index[tuple(stack)]
        except KeyError:
            pass

        for i in range(len(stack) - 1, 0, -1):
            for key in combinations(stack, i):
                try:
                    return self.index[tuple(key)]
                except KeyError:
                    pass

        return None

def test_simple():
    l = Lookup()
    l.store("data value 1", {'index1': '123456'})
    l.store("data value 2", {'index1': '123457'})

    assert l.query({"index1": '123456'}) == "data value 1"
    assert l.query({"index1": '123457'}) == "data value 2"
    assert l.query({"index1": '123458'}) is None

def test_partial():
    l = Lookup()
    l.store("data value 1", {'index1': '123456', 'index2': '123'})
    l.store("data value 2", {'index1': '123456'})

    assert l.query({"index1": '123456', 'index2': '123'}) == "data value 1"
    assert l.query({"index1": '123456', 'index2': '123', 'extra': 1}) == "data value 1"

    assert l.query({"index1": '123456'}) == "data value 2"
    assert l.query({"index1": '123456', 'index2': '121'}) == "data value 2"