from unit_tester import test

import time

def search_linear(xs, target):
    """ Find and return the index of target in sequence xs - Linear Search Algorithm"""
    for (i, v) in enumerate(xs):
        if v == target:         # Is referred to as a probe.
            return i
    return -1

def search_binary(xs, target):
    """ Find and return the index of key in sequence xs """
    lb = 0
    ub = len(xs)
    while True:
        if lb == ub:   # If region of interest (ROI) becomes empty
            return -1

        # Next probe should be in the middle of the ROI
        mid_index = (lb + ub) // 2

        # Fetch the item at that position
        item_at_mid = xs[mid_index]

        print("ROI[{0}:{1}](size={2}), probed='{3}', target='{4}'".format(lb, ub, ub-lb, item_at_mid, target))

        # How does the probed item compare to the target?
        if item_at_mid == target:
            return mid_index      # Found it!
        if item_at_mid < target:
            lb = mid_index + 1    # Use upper half of ROI next time
        else:
            ub = mid_index        # Use lower half of ROI next time



def find_unknown_words(vocab, wds):
    """ Return a list of words in wds that do not occur in vocab """
    result = []
    for w in wds:
        # if search_linear(vocab, w) < 0:
        #     result.append(w)
        if search_binary(vocab, w) < 0:
            result.append(w)
    return result


def load_words_from_file(filename):
    """ Read words from filename, return list of words. """
    f = open(filename, "r")
    file_content = f.read()
    f.close()
    wds = file_content.split()
    return wds


def text_to_words(the_text):
    """ return a list of words with all punctuation removed,
        and all in lowercase.
    """

    my_substitutions = the_text.maketrans(
      # If you find any of these
      "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&()*+,-./:;<=>?@[]^_`{|}~'\\",
      # Replace them by these
      "abcdefghijklmnopqrstuvwxyz                                          ")

    # Translate the text now.
    cleaned_text = the_text.translate(my_substitutions)
    wds = cleaned_text.split()
    return wds


def get_words_in_book(filename):
    """ Read a book from filename, and return a list of its words. """
    f = open(filename, "r")
    content = f.read()
    f.close()
    wds = text_to_words(content)
    return wds

bigger_vocab = load_words_from_file("vocab.txt")
book_words = get_words_in_book("alice_in_wonderland.txt")

# t0 = time.clock()
# missing_words = find_unknown_words(bigger_vocab, book_words)
# t1 = time.clock()
# print("There are {0} unknown words.".format(len(missing_words)))
# print("That took {0:.4f} seconds.".format(t1-t0))

search_binary(bigger_vocab, "magic")

bad75fca237ef4a1605f89dcbbd20abbedb5c2f5
<mask token>


def search_linear(xs, target):
    """ Find and return the index of target in sequence xs - Linear Search Algorithm"""
    for i, v in enumerate(xs):
        if v == target:
            return i
    return -1


def search_binary(xs, target):
    """ Find and return the index of key in sequence xs """
    lb = 0
    ub = len(xs)
    while True:
        if lb == ub:
            return -1
        mid_index = (lb + ub) // 2
        item_at_mid = xs[mid_index]
        print("ROI[{0}:{1}](size={2}), probed='{3}', target='{4}'".format(
            lb, ub, ub - lb, item_at_mid, target))
        if item_at_mid == target:
            return mid_index
        if item_at_mid < target:
            lb = mid_index + 1
        else:
            ub = mid_index


<mask token>


def load_words_from_file(filename):
    """ Read words from filename, return list of words. """
    f = open(filename, 'r')
    file_content = f.read()
    f.close()
    wds = file_content.split()
    return wds


<mask token>


def get_words_in_book(filename):
    """ Read a book from filename, and return a list of its words. """
    f = open(filename, 'r')
    content = f.read()
    f.close()
    wds = text_to_words(content)
    return wds


<mask token>

<mask token>


def search_linear(xs, target):
    """ Find and return the index of target in sequence xs - Linear Search Algorithm"""
    for i, v in enumerate(xs):
        if v == target:
            return i
    return -1


def search_binary(xs, target):
    """ Find and return the index of key in sequence xs """
    lb = 0
    ub = len(xs)
    while True:
        if lb == ub:
            return -1
        mid_index = (lb + ub) // 2
        item_at_mid = xs[mid_index]
        print("ROI[{0}:{1}](size={2}), probed='{3}', target='{4}'".format(
            lb, ub, ub - lb, item_at_mid, target))
        if item_at_mid == target:
            return mid_index
        if item_at_mid < target:
            lb = mid_index + 1
        else:
            ub = mid_index


def find_unknown_words(vocab, wds):
    """ Return a list of words in wds that do not occur in vocab """
    result = []
    for w in wds:
        if search_binary(vocab, w) < 0:
            result.append(w)
    return result


def load_words_from_file(filename):
    """ Read words from filename, return list of words. """
    f = open(filename, 'r')
    file_content = f.read()
    f.close()
    wds = file_content.split()
    return wds


<mask token>


def get_words_in_book(filename):
    """ Read a book from filename, and return a list of its words. """
    f = open(filename, 'r')
    content = f.read()
    f.close()
    wds = text_to_words(content)
    return wds


<mask token>

<mask token>


def search_linear(xs, target):
    """ Find and return the index of target in sequence xs - Linear Search Algorithm"""
    for i, v in enumerate(xs):
        if v == target:
            return i
    return -1


def search_binary(xs, target):
    """ Find and return the index of key in sequence xs """
    lb = 0
    ub = len(xs)
    while True:
        if lb == ub:
            return -1
        mid_index = (lb + ub) // 2
        item_at_mid = xs[mid_index]
        print("ROI[{0}:{1}](size={2}), probed='{3}', target='{4}'".format(
            lb, ub, ub - lb, item_at_mid, target))
        if item_at_mid == target:
            return mid_index
        if item_at_mid < target:
            lb = mid_index + 1
        else:
            ub = mid_index


def find_unknown_words(vocab, wds):
    """ Return a list of words in wds that do not occur in vocab """
    result = []
    for w in wds:
        if search_binary(vocab, w) < 0:
            result.append(w)
    return result


def load_words_from_file(filename):
    """ Read words from filename, return list of words. """
    f = open(filename, 'r')
    file_content = f.read()
    f.close()
    wds = file_content.split()
    return wds


def text_to_words(the_text):
    """ return a list of words with all punctuation removed,
        and all in lowercase.
    """
    my_substitutions = the_text.maketrans(
        'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!"#$%&()*+,-./:;<=>?@[]^_`{|}~\'\\'
        ,
        'abcdefghijklmnopqrstuvwxyz                                          ')
    cleaned_text = the_text.translate(my_substitutions)
    wds = cleaned_text.split()
    return wds


def get_words_in_book(filename):
    """ Read a book from filename, and return a list of its words. """
    f = open(filename, 'r')
    content = f.read()
    f.close()
    wds = text_to_words(content)
    return wds


<mask token>

from unit_tester import test
import time


def search_linear(xs, target):
    """ Find and return the index of target in sequence xs - Linear Search Algorithm"""
    for i, v in enumerate(xs):
        if v == target:
            return i
    return -1


def search_binary(xs, target):
    """ Find and return the index of key in sequence xs """
    lb = 0
    ub = len(xs)
    while True:
        if lb == ub:
            return -1
        mid_index = (lb + ub) // 2
        item_at_mid = xs[mid_index]
        print("ROI[{0}:{1}](size={2}), probed='{3}', target='{4}'".format(
            lb, ub, ub - lb, item_at_mid, target))
        if item_at_mid == target:
            return mid_index
        if item_at_mid < target:
            lb = mid_index + 1
        else:
            ub = mid_index


def find_unknown_words(vocab, wds):
    """ Return a list of words in wds that do not occur in vocab """
    result = []
    for w in wds:
        if search_binary(vocab, w) < 0:
            result.append(w)
    return result


def load_words_from_file(filename):
    """ Read words from filename, return list of words. """
    f = open(filename, 'r')
    file_content = f.read()
    f.close()
    wds = file_content.split()
    return wds


def text_to_words(the_text):
    """ return a list of words with all punctuation removed,
        and all in lowercase.
    """
    my_substitutions = the_text.maketrans(
        'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!"#$%&()*+,-./:;<=>?@[]^_`{|}~\'\\'
        ,
        'abcdefghijklmnopqrstuvwxyz                                          ')
    cleaned_text = the_text.translate(my_substitutions)
    wds = cleaned_text.split()
    return wds


def get_words_in_book(filename):
    """ Read a book from filename, and return a list of its words. """
    f = open(filename, 'r')
    content = f.read()
    f.close()
    wds = text_to_words(content)
    return wds


bigger_vocab = load_words_from_file('vocab.txt')
book_words = get_words_in_book('alice_in_wonderland.txt')
search_binary(bigger_vocab, 'magic')

from unit_tester import test

import time

def search_linear(xs, target):
    """ Find and return the index of target in sequence xs - Linear Search Algorithm"""
    for (i, v) in enumerate(xs):
        if v == target:         # Is referred to as a probe.
            return i
    return -1

def search_binary(xs, target):
    """ Find and return the index of key in sequence xs """
    lb = 0
    ub = len(xs)
    while True:
        if lb == ub:   # If region of interest (ROI) becomes empty
            return -1

        # Next probe should be in the middle of the ROI
        mid_index = (lb + ub) // 2

        # Fetch the item at that position
        item_at_mid = xs[mid_index]

        print("ROI[{0}:{1}](size={2}), probed='{3}', target='{4}'".format(lb, ub, ub-lb, item_at_mid, target))

        # How does the probed item compare to the target?
        if item_at_mid == target:
            return mid_index      # Found it!
        if item_at_mid < target:
            lb = mid_index + 1    # Use upper half of ROI next time
        else:
            ub = mid_index        # Use lower half of ROI next time



def find_unknown_words(vocab, wds):
    """ Return a list of words in wds that do not occur in vocab """
    result = []
    for w in wds:
        # if search_linear(vocab, w) < 0:
        #     result.append(w)
        if search_binary(vocab, w) < 0:
            result.append(w)
    return result


def load_words_from_file(filename):
    """ Read words from filename, return list of words. """
    f = open(filename, "r")
    file_content = f.read()
    f.close()
    wds = file_content.split()
    return wds


def text_to_words(the_text):
    """ return a list of words with all punctuation removed,
        and all in lowercase.
    """

    my_substitutions = the_text.maketrans(
      # If you find any of these
      "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&()*+,-./:;<=>?@[]^_`{|}~'\\",
      # Replace them by these
      "abcdefghijklmnopqrstuvwxyz                                          ")

    # Translate the text now.
    cleaned_text = the_text.translate(my_substitutions)
    wds = cleaned_text.split()
    return wds


def get_words_in_book(filename):
    """ Read a book from filename, and return a list of its words. """
    f = open(filename, "r")
    content = f.read()
    f.close()
    wds = text_to_words(content)
    return wds

bigger_vocab = load_words_from_file("vocab.txt")
book_words = get_words_in_book("alice_in_wonderland.txt")

# t0 = time.clock()
# missing_words = find_unknown_words(bigger_vocab, book_words)
# t1 = time.clock()
# print("There are {0} unknown words.".format(len(missing_words)))
# print("That took {0:.4f} seconds.".format(t1-t0))

search_binary(bigger_vocab, "magic")
