#                                                   dictionaries.py

# All of the compound data types we have studied so far---strings, lists,
# and tuples---are sequence types, which use integers as indices to access
# the values that are contained in them.  If you try to use any other
# type as an index, you get an error. 
#
# A dictionary is also a compound data type.  It is Python's built-in 'mapping'
# type.  It maps keys, which can be any immutable type, to values, which
# can be any type, just like the values of a list or tuple.
#
# Abstractly and conceptually, a dictionary is a sequence of key-value pairs.
# For example, a phone book is a dictionary: name-number pairs, i.e., 
# mapping of names to phone numbers.

# Remember we should know how to (1) create a new instance of this type,
# (2) do a write access, (3) do a read access, and (4) destroy it when
# you are done using it?
#
# Well, we will do (1), (2), and (3) by writing an example that maps English
# words to Spanish equivalents.  For this dictionary, the indices are strings.
# As usual we won't worry about destroying one since it will be done 
# automatically by the Python system when you stop using the data structure
# that you created.  It is called garbage collection.  We are talking about
# destroying the entire dictionary instance itself, not an entry in the
# dictionary.  For individual entries, we will be able to remove a value from
# a dictionary which will then be destroyed by the language system if it
# is not shared by some other data structure.
#
# One way to create a dictionary is to start with an empty dictionary and
# start adding elements, i.e., pairs.  Here is how you do it.  I am creating
# a dictionary named 'e2s' (English to Spanish) initialized with an empty
# dictionary.

e2s = {}


# This is how you put a key-value pair, i.e., 'one' as the key and 'uno' as
# the value of the pair:

e2s['one'] = 'uno'

# One more with the two-dos pair:

e2s['two'] = 'dos'


# This is how you retrieve the value associated with a key:

e2s['one']        # Just to do a read access

print e2s['one']  # If you want it to be printed on the screen


# This will display the contents of the entire dictionary so far:

print e2s

# The elements of a dictionary appear in a comma-separated list as you can
# see in the printed result above - you ARE using an interpreter to execute
# these lines, aren't you?
#
# Each entry (pair) contains an index and a value separated by a colon. 
# In a dictionary, the indices are called keys, so the elements are
# called key-value pairs.  Dictionaries are also called association
# lists, the original term used in the Lisp programming language for the
# same concept.


# You can create one dictionary with some initial pairs explicitly like this:

e2s = {'one': 'uno', 'two': 'dos', 'three': 'tres'}


# Order of the pairs in a dictionary is not important


# You can use a list of tuples to initialize a new dictionary:

t = [('a', 0), ('b', 1), ('c', 2)]
d = dict(t)
print d        # {'a': 0, 'b': 1, 'c': 1}


# Combining dict and zip yields a concise way to create a dictionary:

d = dict(zip('abc', range(3)))
print d        # {'a': 0, 'c': 2, 'b': 1}


# Here is another dictionary:

inventory = {'apples': 430, 'bananas': 312, 'oranges': 525, 'pears': 217}

print "\nShould print {'apples': 430, 'bananas': 312, 'oranges': 525, 'pears': 217}"

print inventory

# Deleting an entry (pair) from a dictionary:

del inventory['pears']

print "\nShould print {'apples': 430, 'bananas': 312, 'oranges': 525}"
print inventory


# Updating the value of a pair:

inventory['apples'] = inventory['apples'] + 10

print "\nShould print {'apples': 440, 'bananas': 312, 'oranges': 525}"
print inventory


# Updating the value of a pair once more:

inventory['oranges'] = 0

print "\nShould print {'apples': 440, 'bananas': 312, 'oranges': 0}"
print inventory


# Note: index (key) must be unique in a dictionary, i.e., no two keys
#       can be identical although values do not need to be unique.
#       This is like a function in math!



# Length of a dictionary

print "\nShould print 3"
print len(inventory)


# Retrieve all the keys in a dictionary into a list:

print "\nShould print ['one', 'three', 'two']"
print e2s.keys()



# Retrieve all the values in a dictionary into a list:

print "\nShould print ['uno', 'tres', 'dos']"
print e2s.values()



# Retrieve all the pairs in a dictionary into a list:

print "\nShould print [('one','uno'), ('three', 'tres'), ('two', 'dos')]"
print e2s.items()



# Check if a key is contained in a dictionary

print "\nShould print True"
print e2s.has_key('one')

print "\nShould print False"
print e2s.has_key('deux')


# If you want to iterate through the pairs
# and add 10 to each
for key in inventory.keys():
   inventory[key] = inventory[key] + 10

print "\nShould print [450, 322, 10]"
print inventory.values()


# If you want to iterate through the pairs
# and add 10 to each this way this time
for key in e2s.keys():
   e2s[key] = e2s[key] + str(10)

print "\nShould print ['uno10', 'dos10', 'tres10']"
print e2s.values()


# Combining items, tuple assignment, and for, you get the idiom for
# traversing the keys and values of a dictionary:

for key, val in e2s.items():
    print val, key

# The output of this loop is:
#
#    tres10 three
#    dos10 two
#    uno10 one

# It is common to use tuples as keys in dictionaries (primarily because you
# can't use lists).  For example, pbook (a phone book dictionary) might map
# from last-name, first-name pairs to phone numbers.

first = 'john'
last = 'doe'
number = 9096070410
pbook = {}
pbook[last,first] = number

pbook['jones','amy'] = 2133223333

# The expression in the brackets is a tuple.  We could use tuple assignment
# to traverse this pbook.

for last, first in pbook:
    print first, last, pbook[last,first]

# This loop traverses the keys in pbook, which are tuples.  It assigns the
# elements of each tuple to last and first, then prints the name and
# corresponding phone number.

#======================================
# Using an alias vs. a copy

opposites = {'up': 'down', 'right': 'wrong', 'true': 'false'}

# This assignment creates an alias where both names reference the same
# identical dictionary object.

alias = opposites


# This 'copy' command creates a distinct copy of the original.  There are 
# two copies now with different names: one called opposites and another 
# called cp.

cp = opposites.copy()


# See Section 10.4 of [DEM] if you want to use sparse matrices in Python.
#
# Chances are you will want to learn how to deal with matrices in general
# in NumPy/SciPy rather than in Python.  We will know more about it when
# we learn NumPy/SciPy.



#======================================
# Exercise 1:
#
# We can write a function that counts the number of occurrences of a
# letter in a string.  Or, a more general version of this problem
# would be to form a histogram of the letters in the string, that
# is, how many times each letter appears.
#
# Such a histogram might be useful for compressing a text file.  Because
# different letters appear with different frequencies, we can compress a
# file by using shorter codes for common letters and longer codes for 
# letters that appear less frequently. 
#
# Dictionaries provide an elegant way to generate a histogram.  Here is a
# simple program that would do that:
#
#   >>> letter_counts = {}
#   >>> for letter in "Mississippi":
#   ...   letter_counts[letter] = letter_counts.get(letter, 0) + 1
#   ...
#   >>> letter_counts
#   {'M': 1, 's': 4, 'p': 2, 'i': 4}
#
# We start with an empty dictionary.  For each letter in the string, we find
# the current count (possibly zero) and increment it.  At the end, the 
# dictionary contains pairs of letters and their frequencies. 
#
# It might be more appealing to display the histogram in alphabetical order.
# We can do that with the items and sort methods: 
#
#   >>> letter_items = letter_counts.items()
#   >>> letter_items.sort()
#   >>> print letter_items
#   [('M', 1), ('i', 4), ('p', 2), ('s', 4)]
#
# You have seen the items method before, but sort is one of the first methods
# you have encountered that applies to lists.  There are several other list 
# methods, including append, extend, and reverse.  Consult the Python 
# documentation for details on these methods and some additional ones.


# Exercise 2:
#
# See Section 11.10 of [Downey] for some interesting exercises.