def range_code(low,high):
    """ Generate a range code for the inclusive span [low,high].
        low, high must be integer. """

    if low > high:
        #Empty set
        return None

    bits = 0
    while high >= (1<<bits):
        bits += 1
    result = 0
    for i in xrange(bits-1,-1,-1):
        low_bit = (low>>i)&1
        high_bit = (high>>i)&1
        if low_bit != high_bit: break
        result += (low_bit+1) * (3**i)
    return result 

def range_queryset(point):
    """ Generate a list of range codes that will guarantee
        finding all intervals that include point """

    bits = 0
    while point >= (1<<bits):
        bits += 1
        
    results = [0]
    for i in xrange(bits-1,-1,-1):
        bit = (point>>i)&1
        results.append(results[-1] + (bit+1) * (3**i))
    return results


if __name__ == '__main__':
    import sqlite3, random, time
    
    conn = sqlite3.connect(':memory:')
    
    c = conn.cursor()
    
    c.execute(r'create table foobar (low,high,range_code)')
    
    # Index range codes
    # Try commenting this out, observe slowdown!
    c.execute(r'create index foobar_range_code_high_low on foobar(range_code,high,low)')
    
    # Give the brute force method all the help it can get
    c.execute(r'create index foobar_high_low on foobar(high,low)')
    
    print 'Generate some data'
    for i in xrange(1000000):
        a = random.randrange(1<<30)
        b = a+random.randrange(1<<20)
        code = range_code(a,b)
        c.execute('insert into foobar(low,high,range_code) values (?, ?, ?)', 
                  (a,b,code)) 
    
    conn.commit()
    
    print
    print 'Check that it really does use the range code'

    point = 12345
    queryset = ','.join(str(item) for item in range_queryset(point))
    c.execute("""explain query plan select low,high from foobar 
                 where range_code in (%s) 
                 and low <= ? and high >= ?""" % queryset,
                 (point,point))
    print
    print 'Query with range code:'
    for item in c:
        print item
    
    c.execute("""explain query plan select low,high from foobar 
                 where low <= ? and high >= ?""",
                 (point,point))
    print
    print 'Query without range code:'
    for item in c:
        print item

    print
    print 'Run queries'

    points = [ random.randrange(1<<30) for i in xrange(100) ]
    
    code_time = 0.0
    codeless_time = 0.0
    for point in points:
        t1 = time.time()
        queryset = ','.join(str(item) for item in range_queryset(point))
        #spank me
        c.execute("""select low,high from foobar 
                     where range_code in (%s) 
                     and low <= ? and high >= ?""" % queryset,
                     (point,point))
        items1 = c.fetchall()
        t2 = time.time()
        
        code_time += t2-t1
        
        t1 = time.time()
        c.execute("""select low,high from foobar 
                     where low <= ? and high >= ?""",
                     (point,point))
        items2 = c.fetchall()
        t2 = time.time()
        
        items1.sort()
        items2.sort()
        assert items1 == items2
        
        codeless_time += t2-t1

    print 'With range codes:   ', code_time, 'sec'    
    print 'Without range codes:', codeless_time, 'sec'    
    
    c.close()
    conn.commit()