## define the function p() that outputs debugging messages if DEBUG flag is True. 

#DEBUG = True
DEBUG = False

def p(msg):
    if DEBUG:
        print(".. {}".format(msg)) 

"""
Explanation: List intersection algorithms
In this notebook, you can experiment with two algorithms (the naive one and the one using galloping search) to perform list intersection, which is an essential operator in supporting conjunction keyword queries.
End of explanation
"""


from pprint import pprint
from bisect import *

## You may find many similarity between this class and the file operation (in C/Java). 
class InvertedList:
    def __init__(self, l):
        self.data = l[:] # make a copy
        self.cur = 0     # the cursor 

    def get_list(self):
        return self.data
 
    def eol(self):
        # we use cur == len(list) to indicate EOL
        return False if self.cur < len(self.data) else True
    
    def next(self, val = 1):
        # does not allow cur to be out-of-range, but use len(list) to indicate EOL
        self.cur = min(self.cur + val, len(self.data)) 
            
    def elem(self):
        if self.eol():
            return None
        else: 
            return self.data[self.cur]

    def peek(self, pos):
        # look at the element under the current cursor, but does not advance the cursor. 
        if pos < len(self.data):
            return self.data[pos]
        else:
            return None
        
    def reset(self):
        self.cur = 0
    
    def dump(self):
        print("* {} : {} (cur = {})".format(self.data[:self.cur], self.data[self.cur:], self.cur))
        
    def skip_to(self, val):
        ##!! This is a naive and inefficient implementation. 
        ##!! Once you have implemented gallop_to(), you can just call it here instead.
        # move the cursor to the first element no smaller than `val`

        while not self.eol() and self.elem() < val:
            self.next()               
            
    def gallop_to(self, val):
        ##!! Not implemented yet. 
        pass

                        





"""
Explanation: The InvertedList class
We implement this class which encapsulates all the important operations one can perform on an inverted list.
End of explanation
"""


a = InvertedList([2, 4, 6, 8, 10, 12, 14, 16, 18])
b = InvertedList([1, 2, 4, 8, 16, 32])

while not a.eol():
    e = a.elem()
    a.next()
    print(e)

a.dump()

"""
Explanation: Test the class
End of explanation
"""


def test_gallop(l, val):
    print("=> gallop_to({})".format(val))
    l.reset()
    l.gallop_to(val)
    l.dump()

test_a = [val - 1 for val in a.get_list()]
test_a.append(a.get_list()[-1] + 100)

DEBUG = False # to show the overview
a.dump()
for t_a in test_a:
    test_gallop(a, t_a)

DEBUG = True # to show the details. Your detailed debugging info may vary. 
test_gallop(a, test_a[-2])

"""
Explanation: If you have implemented the gallop_to() correctly, you should pass the following test. You may change the call to skip_to() for now to see how it should work.
End of explanation
"""


def intersection_naive(a, b):
    # just in case these lists have been traversed.
    a.reset()
    b.reset()
    
    ret = []
    while not a.eol() and not b.eol():
        if a.elem() < b.elem():
            p("move a")
            a.next()
        elif a.elem() > b.elem():
            p("move b")
            b.next()
        else:
            p("found one")
            ret.append(a.elem())
            a.next()
            b.next()
    return ret
        

"""
Explanation: As you can see above, the galloping search algorithm quickly skip over the list to reposition the cursor. In the additional note, it is proved that its complexity is $O(\log x)$, where $x$ is the difference between the correct cursor position and the initial cursor position. 
The Naive Intersection Algorithm
End of explanation
"""


intersection_naive(a, b)

"""
Explanation: Test
End of explanation
"""


def intersection_galloping(a, b):
    # just in case these lists have been traversed.
    a.reset()
    b.reset()
    
    ret = []
    while not a.eol() and not b.eol():
        if a.elem() == b.elem():
            p("found one")
            ret.append(a.elem())
            a.next()
        else:
            if a.elem() < b.elem():
                a.gallop_to(b.elem())
            else:
                b.gallop_to(a.elem())
    # end_while
    return ret
        

intersection_galloping(a, b)

"""
Explanation: Intersection Algorithm using gallop_to()
Here, we call gallop_to explicitly to show some detailed info if you have it implemented correctly. You can change the calls to skip_to in a more general setting.
End of explanation
"""


