"""
HW 1: More Finger Exercises

Instructions:
Fill out each method. Examples are given for each method. Do not
use any external libraries except for unittest if you are doing
the extra credit. 

Note that no examples are given this time! It's up to you 
to test your own code.

Submission:
Upload your filled-out more_finger_exercises.py to Canvas.
"""

# First, we'll see the power of comprehensions in Python. 
# All of these should be done in a single line of code.

def sort_dict(d):
    '''
    Sort a dictionary by its values. Return a list of tuples (key, value).
    Do this in a single line.
    '''
    pass

def extract_and_apply(l, p, f):
    '''
    Implement the function below in a single line:

        def extract_and_apply(l, p, f):
            result = []
            for x in l:
                if p(x):
                    result.append(f(x))
            return result

    where l is a list, 
    p is a predicate (a function that returns a boolean),
    and f is a function.

    Do this in a single line.
    '''
    pass

def dict_filter(items, key):
    '''
    Given a list of items, use the extract_and_apply function to filter
    for only the items that are dictionaries and extract the element in
    those dictionaries indexed by the key given. 
    Do this in a single line.
    '''
    pass

def name_filter(names, lastname):
    '''
    Given a list of names (strings) in the format '<firstname> <lastname>', 
    use the extract_and_apply function to return a list of first names
    with the given last name. 
    Do this in a single line.
    '''
    pass


# Now, we'll see how we can use generators in Python to represent 
# sequences that are infinite!

def generate_fibonacci():
    '''
    Create a generator that yields the Fibonacci sequence.
    '''
    pass

def generate_palindromes(n):
    '''
    Create a generator that yields palindromes starting from the given n. 
    You may assume that n is positive and an integer.
    '''
    pass

def generate_look_and_say():
    '''
    Create a generator that yields the "Look and Say" sequence.
    1, 11, 21, 1211, 111221, 312211, ...
    (If you don't know this, it's a fun puzzle!)

    https://en.wikipedia.org/wiki/Look-and-say_sequence
    '''
    pass

'''
Now, we're going to implement a binary search tree. But we're going 
to do so in a way that makes it behave like a native Python object!
For reference: https://en.wikipedia.org/wiki/Binary_search_tree
or chapters 6 & 7 of https://www.cis.upenn.edu/~cis120/current/files/1200notes.pdf

The goal is to be able to do the following types of "native" 
actions on a BSTree t by leveraging magic methods:

1. Check if an element exists in the tree

if elem in t:
    ...

2. Iterate over the sorted elements of the tree

for elem in t:
    ...

3. Print out the tree nicely

print(t)

For our tree, we will only need to implement insertion, not deletion. 
'''
class BSTree:
    
    def __init__(self):
        '''
        Constructor should return an empty BSTree.
        '''
        pass

    def __contains__(self, element):
        '''
        Determine if element is in the tree. Should return True if so,
        and False otherwise. This magic method allows us to use the syntax

        >>> element in t

        You should iterate through the BST, do not instantiate a list.
        '''
        pass
    
    def __iter__(self):
        '''
        Return a generator (that means yield!) of the elements 
        visited in an in-order traversal:
        https://en.wikipedia.org/wiki/Tree_traversal

        Note that for a binary search tree, in-order traversal results in
        the sorted order of the elements.

        This will allow us to traverse the BSTree nicely like:
        
        >>> for elem in t:
        >>>    ...

        and even cast it like
        
        list(t)
        '''
        pass

    def __str__(self):
        '''
        Return a string representation of the tree as (left, elem, right)
        where elem is the element stored at the root, and left and right
        are the string representations of the left and right subtrees
        (which are in the same format). Empty trees should be represented 
        as a hyphen.

        For example, if we had a BSTree like:
                7
              /  \
             3   9
            / \
           1  5

        the string representation would be

        "(((-, 1, -), 3, (-, 5, -)), 7, (-, 9, -))"
        '''
        pass

    def insert(self, element):
        '''
        Insert the given element into the tree. If the element is equal to
        an element already in the tree, raise an exception with the message:
        'Cannot insert duplicate element!'
        '''
        pass


class Node(object):
    '''
    A node of the BSTree. 
    Should contain a value, left subtree, and right subtree.
    You may find it useful to define some additional methods here.
    '''
    pass


'''
EXTRA CREDIT:
Add a class to test your BSTree using unittest. Have at least one test for every method, e.g.

def test_contains(self):
    ...
def test_str(self):
    ...
etc

You can invoke your tests by adding this to the bottom of your homework file
and running the file in your terminal with `python more_finger_exercises.py`

if __name__ == '__main__':
    unittest.main()
'''