# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # COMP6714-Project 1
#
# ### Submission Deadline for the Project is 23:59:59 PM, on **25 Sep, 2017** 
#
# This ipython notebook illustrates the requirements for **COMP6714 Project-1**.
#
# ## Instructions:
# 1. You need to implement your code in **`submission.py`** file, provided along with this notebook.
# 2. For all questions, your codes in the file **`submission.py`** need to output your results according to corresponding format specified in **`Proj1-spec.ipynb`**.
# 3. We will not consider any output printed out on the screen. All results should be returned in appropriate data structures return by corresponding functions.
# 4. This Project is not designed to be a full-fledged software program, so we will not evaluate it deliberately using any invalid inputs.
# 5. You are **not allowed** to change the names of the functions to be submitted in **`submission.py`**. 
# 6. If you choose to skip a question, leave the corresponding function body in the file **submission.py** as it is (i.e., keep the **`pass`** line), otherwise it will affect your marks for other questions.
# 7. You are allowed to add other functions and import modules (which you may have to in this project), but you are **not allowed to define global variables**, i.e., **only functions are allowed** in **`submission.py`**. Also be careful not to import unnecessary modules, as it may lead to unexpected errors.
# 8. You are allowed to submit as many times as you want before the deadline, but **ONLY the latest version will be kept and marked**.
# 9. For your convenience, we will process your codes submitted before the **Deadline** using a sample dataset, you should not consider these results as your final grades.
# 10. For **Final Grades** we will be using a different dataset, so your final scores may vary.

# # Question 0: An example (0 point)
#
# We illustrate the steps for completing the **project** notebook and prepare **`submission.py`** by solving the `Question 0`. In this example question, you are required to implement a function that takes two integer arguments `a` and `b`, and output their sum.
#
# You will be provided with the definition of the function, as given below:

def add(a, b): # do not change the heading of the function
    pass # **replace** this line with your code


# **Step 1**: You need to put your implementation in the function body like below **(you should remove the `pass` line from the function body)**:

def add(a, b): # do not change the heading of the function
    return a + b


# **Step 2**: you need to paste your code to **`submission.py`**, which originally contains only function definitions. We have added this function in **`submission.py`** as a sample solution to **Question 0** for your reference.

# Here is the demonstration of our testing environment, which explains how we will evaluate your submission. 

# +
import submission

result = submission.add(5,3)
print(result)


# -

# As you can see, all you need to/have to do is to implement the function; do not print anything out from your own implementation. (c.f., Instruction-#3)
# <br />
# <br />
# <br />
# <br />
# <br />
#

# # Question 1: List Intersection using Galloping Search (35 point)
#
# You need to implement a function named: **`gallop_to`** using the galloping search algorithm. 
#
# #### Specifications:
# We will test your implementation of **`gallop_to`** using a seperate function **`intersection_galloping`**, which is already provided to you in this notebook.
#
# Input of the **`intersection_galloping`** function consists of two objects of the **`InvertedList`** class, initiated with sorted list of integers, e.g.,
#
# `a = InvertedList([2, 4, 6, 8, 10, 12, 14, 16, 18])`
#
# `b = InvertedList([1, 2, 4, 8, 16, 32])`
#
#
# **`intersection_galloping(a, b)`** calls the function: **`gallop_to`** by passing, an InvertedList object to traverse, and an integer **value** that we need to gallop to. 
#
# In addition to galloping, each run of **`gallop_to`** will also return an integer **count** representing the number of times you assess a value (under the current pointer) in the InvertedList object passed to the **`gallop_to`** function. 
#
# Final output of **`intersection_galloping`** will be a list of integers, and a count representing the sum of all the **count** variables returned by the **`gallop_to`** function.
#
#
# #### Example:
#
# #### (i) `intersection_galloping(a, b)`
#  ##### (a) input:
#
# `a = InvertedList([2, 4, 6, 8, 10, 12, 14, 16, 18])`
#
# `b = InvertedList([1, 2, 4, 8, 16, 32])`
#  
#  ##### (b) output:
#  
# ([2, 4, 8, 16], 17)
#
# #### (ii) `gallop_to(a, 8)`
#  ##### (a) input: 
#
# `a = InvertedList([2, 4, 6, 8, 10, 12, 14, 16, 18])`
#
# `val = 8`
#
# In the above example, for `InvertedList object a` with current `cursor position = 2`, corresponding to `current value = 6`, `gallop_to(a, 8)` will return a **count = 2**, which corresponds to the sum of 1st peek at `cursor position = 2, value = 6`, and a 2nd peek at `cursor position = 4, value = 10`, after we doubled the interval.
#
#  ##### (b) output:
#  
#  `2`
#  
# ** Note:** In `gallop_to`, you are only allowed to update **count**, for the elements of **InvertedList** that you checked as: <br>
# * smaller than **val** (*i.e.,* elements< **val**), and 
# * the first element that is greater than or equal to the **val** (*i.e.,* element >= **val**).
#

# ## The InvertedList class
#
# To facilitate the implementation of `Question 1`, we provide this `InvertedList` class which encapsulates all the important *operations* needed to be performed on an inverted list. 

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            



# You need to implement your code below, and copy this code in the file **`submission.py`**

# +
def gallop_to(a, val):# do not change the heading of the function
    def binary_search(start, end, a, val):
        while start < end:
            if a.peek((start + end) // 2) < val:
                start = max(start + 1, (start + end) // 2)
            elif a.peek((start + end) // 2) > val:
                end = min((start + end) // 2, end - 1)
            else:
                end = (start + end) // 2
                break
        a.cur = end
        return
    a.cur = 1  
    count = 0
    while(a.elem() and a.elem() < val):
        count += 1
        a.cur *= 2
    binary_search(a.cur // 2, min(a.cur, len(a.data)) , a, val)   

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


# -

def binary_search(start, end, a, val):
        count = 0
        while start < end:
            count += 1
            if a.peek((start + end) // 2) < val:
                start = max(start + 1, (start + end) // 2)
            elif a.peek((start + end) // 2) > val:
                end = min((start + end) // 2, end - 1)
            else:
                break
        a.cur = end
        return count
a = InvertedList([1,2,3,4,5,6, 7])
print(binary_search(0, 7, a, 4))


# ## Intersection Algorithm using `gallop_to()`
#
# After implementing the `gallop_to()` function, you will be using Intersection Algorithm, *i.e.*, `intersection_galloping` to test your results.
#
# In this function, we initialize a variable named: **count** to store the total number of times you peek a value in InvertedList passed to the `gallop_to()` function.
#
# You will observe, the galloping search algorithm quickly skip over the list to reposition the cursor.

# +
#import submission

def intersection_galloping(a, b):
    # just in case these lists have been traversed.
    a.reset()
    b.reset()
    count = 0

    ret = []
    while not a.eol() and not b.eol():
        if a.elem() == b.elem():
            ret.append(a.elem())
            a.next()  # Note that here you are only allowed to move the cursor of one InvertedList Object. 
        else:
            if a.elem() < b.elem():
                count = count + gallop_to(a,b.elem())
            else:
                count = count + gallop_to(b,a.elem())
    # end_while
    return ret, count


# -

import random
cc = 100
n = 10000
while cc > 0:
    cc -= 1
    a = InvertedList( sorted([random.randint(1, 1000000) for _ in range(n)]))
    b = InvertedList( sorted([random.randint(1, 1000000) for _ in range(n)]))
    print( intersection_galloping(a, b))

# After implementation of the `gallop_to` function, you can test your implementation here. It should result an output ([2, 4, 8, 16], 17)

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


# # Question 2: Logarithmic Merge (35 point)
#
# In this question, we simulate the implementation of (binary) Logarithmic_Merge for Index Merging, given in **L4-slides (36-37)**.
# You are required to implement the Logarithmic Megre function: **`Logarithmic_merge(index, cut_off, buffer_size)`**.
#
# The function takes 3 parameters as input,i.e., *(i)* **index**, *(ii)* **cut_off**, and *(iii)* **buffer_size**.
# 1. First parameter, **index**, represents the live streaming index, we simulate the **index** using a list of unordered integers.
# 2. Second parameter, **cut_off**, is the cut_off point for the streaming **index**, it is illustrated in the example below.
# 3. Third parameter, **buffer_size**, represents the maximum size of your memory buffer. When **index** is **greater than or equal** to the **buffer_size**, we write down the **index** in a file.
#
# ##### Note: You are not supposed to actually write down your index in the file, you will be simulating the index writing part by adding the index to a list.
#
# #### Example for cut_off:
# index = [15, 46, 19, 93, 73, 64, 33, 80, 73, 26, 22, **-77-**, 27, .....]
#
# Assume that you have access to live-streaming data, which is being populated in your list named: **index**. The parameter, **cut_off** defines a threshold for the **index**. For-example, **cut_off = 12** will restrict the function:**`Logarithmic_merge(index, cut_off, buffer_size)`** to use **top 12** values, i.e., it will only consider values upto and including the value **77**. 
#
# #### Specifications:
# Your inputs will be the *(i)* **index**, i.e., unsorted list of integers, *(ii)* **cut_off**, *i.e.,* the cut-off point, and *(iii)* **buffer_size**, *i.e.,* the maximum size of index that can be kept in memory. 
#
# Your output should be a list of sub-lists, where each sub-list stores intermediate result of logarithmic merge. First sub-list will store the value for Z0, the second sub-list will store the value of L0, and the subsequent sub-lists will store values for L1, L2, L3 and so on...
# ##### Note: Don't remove empty sub-lists from your final result. It will effect your evaluation.
#
# #### Example:
#
#  ##### input: (index, cut_off, buffer_size), e.g., ([15, 46, 19, 93, 73, 64, 33, 80, 73, 26, 22, 77, 27], 10, 3)
#  
#  ##### output: List of sub-lists storing all the intermediate results, and the final result, e.g., [[26], [33, 73, 80], [15, 19, 46, 64, 73, 93]].
#  
# **Note**:<br>
# 1. Z0 should be added at the start of the final list, followed by L0, L1, L3, and so on... <br>
# 2. In the example output, Z0 = [26], L0 = [33, 73, 80], L1 = [15, 19, 46, 64, 73, 93] <br>
# 3. **index** within a sub-list should be sorted. <br>

# You need to implement your code below, and copy this code in the file **`submission.py`**

def Logarithmic_merge(index, cut_off, buffer_size): # do not change the function heading
    disk = [[]]
    memory = []

    def merge(i, sub_list, disk):
        if len(disk) == i + 1:
            disk.append([])
        disk[i+1].append(sorted(sub_list[0] + sub_list[1]))
        disk[i] = []
        if len(disk[i+1]) > 1:
            merge(i+1, disk[i+1], disk)
            
    def merge_disk(disk):
        if len(disk[0]) > 1:
            merge(0, disk[0], disk)
    
    
    for i in index[:cut_off]:
        print("memory", memory, "disk:",disk)
        memory.append(i)

        if len(memory) >= buffer_size:
            disk[0].append(sorted(memory))
            merge_disk(disk)
            memory = []
    
    disk = [[memory]] + disk
    ret = []
    for i in disk:
        if i:
            ret += i
        else:
            ret.append(i)
    return ret        

# After implementation of **`Logarithmic_merge`**, you can test your implementation here. You should see the following output:
#
# [[26], [33, 73, 80], [15, 19, 46, 64, 73, 93]]

# +
import random
#import submission

random.seed(1999)
n = 14
index = [random.randint(1, 100) for _ in range(n)]
print(index)
result = Logarithmic_merge(index, 13, 3) #cut_off = 10, initial buffer_size = 3
print(result) # expect to see a list of lists
# -

# # Question 3: Decoders for Gamma, Delta, and Rice codes (30 point)
#
# In this part you will implement decoders for Gamma, Delta, and Rice codes.
#
# #### Specifications:
# For Gamma, and Delta decoders, your input will be a string of bits (0s or 1s) without any space. Your output for Gamma, and Delta decoders should be a list of integers. 
# For Rice decoder, input constitutes of the *(i)* code, i.e., a string of bits (0s or 1s) without any space, and *(ii)* an integer representing the value of b. Here b = 2^k. Output of Rice decoder should be a list of integers.
#
# ##### Note, for Rice Decoder, in contrast to the information provided in (L5, slide57), we assume the input of the decoder is comig from q = [x]/b, and r = (x) - (q.b). 
#
# #### (i) Examples for Gamma and Delta:
#
#  ##### (a) input: (String x), e.g., ("1111111100000000011111111000001001")
#  
#  ##### (b) output: list of numbers, e.g., [256, 265]
#  
# #### (ii) Example for Rice Decoder:
#  ##### (a) input: (String x , int b) e.g., ("11110101111011",4)
#  
#  ##### (b) output: list of numbers, e.g., [18, 19]

i = [[]]
print(i[0])


# You need to implement your code below, and copy this code in the file **`submission.py`**

def decode_gamma(inputs):# do not change the function heading
    all_digits = []
    while(inputs):
        k_d, remain = inputs.split("0", 1)
        k_r = remain[:len(k_d)]
        inputs = remain[len(k_d):]
        all_digits.append(2**len(k_d) + int(k_r, 2))   
    return all_digits



# After implementation of **`decode_gamma`**, you can test your implementation here. You should see the following output [256, 265]

#import submission
inputs = "100002"
result = decode_gamma(inputs)
print(result)


# You need to implement your code below, and copy this code in the file **`submission.py`**

def decode_delta(inputs):# do not change the function heading
    if(inputs == "0"):
        return [1]
    import math
    all_digits = []
    while inputs:
        if(inputs == "0"):
            inputs = input[1:]
            all_digits.append(1)
            continue
        k_dd, remain = inputs.split("0", 1)
        k_dr = remain[:len(k_dd)]
        k_r_remain = remain[len(k_dd):]

        
        k_d = 2**(2**len(k_dd)-1+ int(k_dr, 2))
        k_r = k_r_remain[:int(math.log2(k_d))]

        inputs = k_r_remain[int(math.log2(k_d)):]
        all_digits.append(k_d + int(k_r, 2))
    
    return all_digits

# After implementation of **`decode_delta`**, you can test your implementation here. You should see the following output: [256, 265]

#import submission
inputs = "111001011111111110000"
result = decode_delta(inputs)
print(result)


# You need to implement your code below, and copy this code in the file **`submission.py`**

def decode_rice(inputs, b):# do not change the function heading
    import math
    all_digits = []
    sb = int(math.log2(b))
    while(inputs):
        q, remain = inputs.split("0", 1)
        offset = remain[:sb]
        inputs = remain[sb:]
        print(q, 2**(len(q)), offset)
        print(b)
        all_digits.append(b * len(q) + int(offset, 2))
    return all_digits


# After implementation of **`decode_rice`**, you can test your implementation here. you should see the following output: [18, 19]

#import submission
inputs = "11110010"
b = 10
result = decode_rice(inputs, b)
print(result)



StarcoderdataJupyterScriptsDedupFiltered