def interval_size_code(low,high):
    """ Round the size of the interval down to the nearest
        power of two. """
    
    size = high-low
    approx_size = 1
    while approx_size*2 < size: approx_size *= 2 
    return approx_size


def interval_query(maximum_size,table):
    """ Construct a query to retrieve intervals intersecting the
        interval [:lower,:upper). """

    queries = [ ]
    size = 1
    while size <= maximum_size:
        queries.append(
            'select * from %s where size = %d and low < :upper and :lower-%d < low' % (table,size,size)) 
        queries.append(
            'select * from %s where size = %d and high < :upper+%d and :lower < high' 
            ' and not (low < :upper and :lower-%d < low)'% (table,size,size,size)) 
        size *= 2
    return ' union all '.join(queries)


if __name__ == '__main__':
    import sqlite3, random, time
    
    conn = sqlite3.connect(':memory:')
    
    c = conn.cursor()
    
    c.execute(r'create table foobar (low,high,size)')
    
    # Index range codes
    # Try commenting this out, observe slowdown!
    c.execute(r'create index foobar_size_low on foobar(size,low)')
    c.execute(r'create index foobar_size_high on foobar(size,high)')
    
    # 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,1<<20)
        size = interval_size_code(a,b)
        c.execute('insert into foobar(low,high,size) values (?, ?, ?)', 
                  (a,b,size)) 
    
    conn.commit()
    
    print
    print 'Check that it really does use the range code'

    print
    print 'Query with size code:'
    point = 12345
    query = interval_query(1<<30,'foobar')
    c.execute('explain query plan %s' % query,
                 {'lower':point,'upper':point+1})
    for item in c:
        print item

    
    print
    print 'Query without size code:'
    c.execute("""explain query plan select low,high from foobar 
                 where low <= ? and high > ?""",
                 (point,point))
    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()
        query = interval_query(1<<30,'foobar')
        c.execute("""select low,high from (%s) 
                     """ % query,
                     {'lower':point,'upper':point+1})
        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()
        
        codeless_time += t2-t1
        
        items1.sort()
        items2.sort()
        assert items1 == items2

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