#                                                   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 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, a dictionay is a sequence of key-value pairs.  For example,
# a phone book is a dictionary: mapping of names to phone numbers.

# Remember we want to 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
# and done using it?
#
# Well, we will do (1), (2), and (3) by writing an example that mapps 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
# the 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 dictionay and
# and start adding elements.  Here is how you do it.  I am creating a 
# dictionary named 'eng2sp' initialized with an empty dictionary.

eng2sp = {}


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

eng2sp['one'] = 'uno'

# One more with the two-dos pair:

eng2sp['two'] = 'dos'


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

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

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


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

print eng2sp

# 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:

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


# Order of the pairs in a dictionary is not important



# Here is another dictionay:

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


# Deleting an entry (pair) from a dictionary:

del inventory['pears']


print inventory

# Now it contains: {'oranges': 525, 'apples': 430, 'bananas': 312}


# Updating the value of a pair:

inventory['apples'] = 0

print inventory

# Now it contains: {'oranges': 525, 'apples': 0, 'bananas': 312}


# Length of a dictionary

print len(inventory)


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

print eng2sp.keys()
# ['one', 'three', 'two']


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

print eng2sp.values()
# ['uno', 'tres', 'dos']


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

print eng2sp.items()
# [('one','uno'), ('three', 'tres'), ('two', 'dos')]


# Check if a key is contained in a dictionary
print eng2sp.has_key('one')   # True

print eng2sp.has_key('deux')  # False



# 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
# copy.

copy = 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 the first method 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 12.10 of [DEM] for some interesting exercises.