Software Design
Spring 2008

For today you should have:

1) read Chapter 11

2) worked on Homework 4


For Monday you should:

1) read Chapter 12

2) work on Homework 4

3) prepare for a quiz


Dictionary methods
------------------

See the attached documentation.

As always, when you are using a new method, test it out
in isolation before you design a program around it!

A few highlights:

1) In addition to keys(), values() and items(), there
   are also iterkeys(), itervalues() and iteritems().

   The difference is that the first three make a new list;
   the second three make an iterator object that traverses
   the dictionary.

   So the latter is a little more efficient, but it if
   you modify the dictionary, it breaks the iterator.

2) items() returns a list of tuples.  You can loop through it:

   for t in d.items():
       k, v = t            # tuple assignment

   Or you can cut out the middle man:

   for k, v in d.items():
       # loopity

3) We have already seen get(), which takes an optional second argument:

   d.get(k, 0)      # return 0 if k is not in d

   There is also setdefault, which is similar, but different.
   Here's a common example:

   d.setdefault(k, []).append(x)

   If k is not in d, setdefault creates a new empty list,
   adds it to the dictionary, and returns a reference to it.


Dictionaries and Uniqueness
---------------------------

A natural use of dictionaries is to check uniqueness.
Here is an example from an old quiz:

Write a function named has_duplicates that takes a list
as a parameter and that returns True if there is any object
that appears more than once in the list, and False otherwise.


# simple version using only things in the book
def has_duplicates(t):
    d = {}
    for x in t:
        if d.has_key(x):
            return True
        d[x] = "the value doesn't matter"
    return False


# a version that uses the id function to deal with
# non-hashable keys and the in operator 
def has_duplicates2(t):
    d = {}
    for x in t:
        y = id(x)
        if y in d:
            return True
        d[y] = None
    return False


# a version that uses the set type
def has_duplicates3(t):
    d = set()
    for x in t:
        y = id(x)
        if y in d:
            return True
        d.add(y)
    return False

# test all three versions
for test in [has_duplicates, has_duplicates2, has_duplicates3]:

    t = range(10) + list(string.lowercase)
    print test(t)

    t.append('a')
    print test(t)



Homework 3 Solutions
--------------------

What was the ultra-secret point of Homework 3?

1) design by assembly

"How to think" provides a subset of the string operations, but they
are sufficient for the homework; the task is to arrange them into a
solution.

Sometimes that just means problem recognition:

def has_no_e(word):
    return 'e' not in word

def is_palindrome2(word):
    back = word[::-1]
    return back == word

Other times some assembly is required:

def is_abecedarian(word):
    for i in range(len(word)-1):
        if word[i] >= word[i+1]:      # strict version: no doubles
            return False
    return True


2) our first design pattern, search!

Many problems reduce to traversal+search.

    for x in collection:        # traversal
        if condition(x):        # check a condition 
            return True         # found it!
    return False                # didn't find it.

But sometimes it takes some rearranging to adapt this
pattern to a given problem.

a) in avoids, we reverse the sense of the return value

b) in uses_only, we reverse the sense of the condition

c) in uses_all, we traverse the required letters rather than
   the word


3) An opportunity for recursion:

def is_palindrome(word):
    if len(word) < 2: return True
    if word[0] != word[-1]: return False
    middle = word[1:-1]
    return is_palindrome(middle)


4) another example of interface design

A big, complicated function is almost always a sign that
there is an opportunity for abstraction.

Imagine that you had to present your program at a code review.
How would you convince a reader that it is correct?

See rotate_word in sd_hw03_soln.py

A function whose name begins with _ is "internal".


4) a first look at Gui layout (see Rotate.py)