bitmap_pattern_matcher.py

def getMatch(bitmapQ, bitmapT):
    """
    if bitmapT exist in bitmapQ
    Return the coordinates of the match 
    or therewise return None
    """
    n = len(bitmapQ)
    m = len(bitmapQ[0])

    if len(bitmapT) > n or len(bitmapT[0]) > m:
        return None

    def match(r , c):
        # Check borders
        for i in range(len(bitmapT)):
            for j in range(len(bitmapT[0])):
                if r+i >= n or c+j >= m or bitmapT[i][j] != bitmapQ[r+i][c+j]: # start the search at (r,c)
                    return False
        return True
    
    for i in range(n):
        for j in range(m):
            if match(i, j) == True:
                return (i, j)
    
    return None

# testings
if __name__ == "__main__":
    matrix_ = [[1,1,1,0,0],
               [1,1,0,0,0],
               [0,1,0,1,1],
               [0,0,1,1,1]]

    bit_map_1 = [[1,1],
                 [1,1]]

    bit_map_2 = [[0,0],
                 [1,1]]

    bit_map_3 = [[1,0],
                 [0,0],
                 [1,1]]

    print("mask: {}".format(getMatch(matrix_, bit_map_1)))
    print("mask2: {}".format(getMatch(matrix_, bit_map_2)))
    print("mask3: {}".format(getMatch(matrix_, bit_map_3)))