# Recall, a list is a sequence of values; each value has an *index*.

#             0           1           2          3
animals = ['ferret', 'alligator', 'anteater', 'skunk']

# We can also think of this as a *mapping* or *association* from indices to values.
#
#  0 --> 'ferret'
#  1 --> 'alligator'
#  2 --> 'anteater'
#  3 --> 'skunk'

# A dictionary generalizes this to be able to use any values we want as "indices" (*keys*).
# For example, associating animals to exhibit ID codes:

# 'A2' --> 'ferret'
# 'QQ9' --> 'alligator'
# 'Z3' --> 'anteater'
# 'F' --> 'skunk'

# One way to create a dictionary with explicit keys and values:

zoo = {'A2': 'ferret', 'QQ9': 'alligator', 'Z3': 'anteater', 'F': 'skunk'}

# We can look up the value associated with a particular key using the same syntax
# we use to look up an index in a list:

a = zoo['Z3']   # look up the value associated with 'Z3' (== 'anteater')

# We can modify the value associated with a key:

zoo['Z3'] = 'tiger'

# We can also add new keys and values this way:

zoo['R19'] = 'anteater'

# Note each key can only occur once, but there can be multiple keys with the same value:

zoo['T12'] = 'anteater'


### Example: frequency count function

# Return a frequency count of a string, i.e. a dictionary whose keys are characters and associated values are
# how many times each character occurred.
#
# e.g.
#   frequency_count('apple') = {'a': 1, 'p': 2, 'l': 1, 'e': 1}

def frequency_count(s: str) -> dict[str, int]:   # dict[str, int] means keys are str, values are int.
    counts: dict[str, int] = {}   # start off with an empty dictionary

    # Loop through each character c of the string s
    for c in s:
        if c not in counts:
            counts[c] = 0

        counts[c] += 1

        # OR:
        # if c not in counts:
        #     counts[c] = 1
        # else:
        #     counts[c] += 1

    return counts

# Let's generalize to return *normalized* frequencies, i.e. a occurs 20% of the time, etc.
#   frequency('apple') = {'a': 0.2, 'p': 0.4, 'l': 0.2, 'e': 0.2}

# We will do this by writing a function to normalize a dictionary of counts. But first,
# we need a function to add up all the values in a dictionary (to find out what we should
# divide by).

# Add up all the values in the given dictionary.
# e.g.   dict_sum({'a': 1, 'p': 2, 'l': 1, 'e': 1}) == 5.
def dict_sum(counts: dict[str, int]) -> int:
    sum = 0
    for k in counts:   # a for loop on a dictionary will loop through all the keys.
        sum += counts[k]
    return sum

def dict_sum2(counts: dict[str, int]) -> int:
    sum = 0
    for n in counts.values():   #   <some dict>.values() returns a list of all the values
        sum += n                #   .keys() gives a list of keys
    return sum

def normalize(counts: dict[str, int]) -> dict[str, float]:
    # (1) call dict_sum to find out the total
    total = dict_sum(counts)
    # (2) create a new empty dictionary to hold the normalized frequencies
    freq_dict: dict[str, float] = {}
    # (3) loop through counts, put each key in the new dict with a normalized value (divide by total)
    for k in counts:
        freq_dict[k] = counts[k] / total

    # (4) return the new dict
    return freq_dict

# Given a list of words, return a dictionary organizing them by length:
#   each key k is associated with a list of all words of length k.
#
# e.g.
#   words_by_length(['house', 'mouse', 'hi'])
#     == {2: ['hi'], 5: ['house', 'mouse']}
def words_by_length(words: list[str]) -> dict[int, list[str]]:
    words_of_length: dict[int, list[str]] = {}
    for word in words:
        n = len(word)
        if not (n in words_of_length):
            words_of_length[n] = []

        words_of_length[n].append(word)

    return words_of_length