bit_strings_query.py

import numpy as np

#Re-implementation of bisect functions of bisect module to suit the application
def bisect_left(a, x):
    lo = 0
    hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo
            
def bisect_right(a, x):
    lo = 0
    hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid] and not a[mid].startswith(x):
            hi = mid
        else:
            lo = mid + 1
    return lo

#function which accepts an sorted array of bit strings, a query string
#This returns an array containing all indices which share the first h bits of the query
def simpleFunctionBisectReImplemented(sorted_array, item, h):
    left_index = bisect_left(sorted_array, item[:h])
    right_index = bisect_right(sorted_array, item[:h])
    return np.arange(left_index, right_index)


#demonstration

bit_string_list = []
k = 32
min_length = 20
array_length = 100

for i in range(array_length):
    bit_string = ''
    for j in range(np.random.randint(min_length,k+1)):
        bit_string = bit_string + str(np.random.randint(0,2))
    bit_string_list.append(bit_string)

bit_string_list = np.sort(bit_string_list)

#prints the sorted bit string array
print bit_string_list

#creates a query
query = ''
for j in range(np.random.randint(10,20)):
    query = bit_string + str(np.random.randint(0,2))

#prints query
print query

h = 10
#print the result
print simpleFunctionBisectReImplemented(bit_string_list, query, 10)