# Micropattern

## Fixed value

The role of a variable is a fixed value if its value is not changed in run-time after initialization.

pii = 3.14                                     # 1
r = input("Enter the radius of a circle: ")    # 2
print "The area of the circle is", pii*r*r     # 3
• r is a fixed value,
• pii is a fixed value, also.

## Stepper

Stepper goes through a succession of values in some systematic way.

multiplier = 1                                # 1
while multiplier <= 10 :                      # 2
print multiplier, "* 3 =", multiplier*3   # 3
multiplier += 1                           # 4
• multiplier is a stepper.

A stepper can also be used, for example, for counting and traversing the indexes of an array.

## Most-recent holder

A variable is a most-recent holder, if its value is the latest gone through value of a certain group or simply the latest input value.

s = 0                                                         # 1
while s <= 0 :                                                # 2
s = input("Enter the length of the side of a square: ")   # 3
print "The area of the square is", s*s                        # 4 
• s is a most-recent holder.

## Most-wanted holder

The value of a most-wanted holder is the "best" or otherwise the most-wanted value out of the values gone through so far. There exists no restrictions for measuring the superiority of the values

smallest = input("Enter a number: ")             # 1
for i in range(9) :                              # 2
number = input("Enter a number: ")           # 3
if number < smallest : smallest = number     # 4
print "The smallest number was", smallest        # 5
• smallest is a most-wanted holder,
• i is a stepper,
• number is a most-recent holder.

## Gatherer

The value of a gatherer accumulates all the values gone through so far.

count = 0                                               # 1
sum = 0                                                 # 2
number = 0                                              # 3
while number != -999 :                                  # 4
number = input("Enter a number, -999 to quit: ")    # 5
if number != -999 :                                 # 6
sum += number                                   # 7
count += 1                                      # 8
if count :                                              # 9
print "The average is", sum / count                 # 10
• sum is a gatherer,
• count is a stepper,
• number is a most-recent holder.

## Follower

A follower always gets the old value of another known variable as its new value.

previous = input("Enter the 1. value: ")                       # 1
current = input("Enter the 2. value: ")                        # 2
biggestDiff = current - previous                               # 3
month = 3                                                      # 4
while month <= 12 :                                            # 5
previous = current                                         # 6
current = input("Enter the " + month + ". value: ")  # 7
if current - previous > biggestDiff :                      # 8
biggestDiff = current - previous                       # 9
month += 1                                                 # 10
print "The biggest difference was", biggestDiff                # 11

• previous is a follower,
• month is a stepper,
• current is a most-recent holder,
• biggestDiff is a most-wanted holder.

Followers are used a lot with linked data structures to point the data element previous to the one in process.

## One-way flag

A one-way flag is a Boolean variable which once changed cannot get its original value anymore.

sum = 0                                                             # 1
neg = 0                                                             # 2
number = 1                                                          # 3
while number :                                                      # 4
number = input("Enter a number, 0 to quit: ")                   # 5
sum += number                                                   # 6
if number < 0 : neg = 1                                         # 7
print "The sum is", sum                                             # 8
if neg : print "There was at least one negative number in inputs"   # 9

• neg is a one-way flag,
• number is a most-recent holder,
• sum is a gatherer.

A one-way flag can also be used, for example, to watch errors occuring in input data so that the program could ask the inputs again.

## Temporary

A variable is a temporary if its value is always needed only for a very short period.

taxRate = 16                                                          # 1
taxfree = 1                                                           # 2
while taxfree :                                                       # 3
taxfree = input("Enter tax-free price (0 to quit): ")             # 4
if taxfree :                                                      # 5
tax = taxfree * taxRate / 100                                 # 6
print "Total price", taxfree+tax, "that includes tax", tax    # 7

• tax is a temporary,
• taxRate is a fixed value,
• taxfee is a most-recent holder.

A temporary is typically used for efficiency reasons (e.g., executing a computation, whose value is needed in several places, only once) or to clarify the program (e.g., computing the result in a variable even though the use of a variable would not be absolutely necessary). A temporary is also often used for swapping two data elements of an organizer.

## Organizer

An organizer is a data structure which is used for reorganizing its elements after initialization.

characters = []                                             # 1
letter = "a"                                                # 2
while letter != "x" :                                       # 3
letter = raw_input("Enter a letter, x to quit: ")       # 4
if letter != "x" : characters = characters + [letter]   # 5
print characters                                            # 6
length = len(characters)                                    # 7
if length :                                                 # 8
i = 0                                                   # 9
while i < length/2 :                                    # 10
tmp = characters[i]                                 # 11
characters[i] = characters[length-1-i]              # 12
characters[length-1-i] = tmp                        # 13
i += 1                                              # 14
print characters                                            # 15
• characters is an organizer,
• letter is a most-recent holder,
• length is a fixed value,
• i is a stepper,
• tmp is a temporary.

An organizer can be used for sorting or for some other reorganization.

## Container

Container is a data structure where elements can be added and removed.

stack = []                                                 # 1
command = "x"                                              # 2
while command != "q":                                      # 3
command = raw_input("Enter command: ")                 # 4
if command == "n":                                     # 5
stack = stack + [raw_input("Enter element: ")]     # 6
elif command == "r" and len(stack) > 0 :               # 7
print stack[len(stack)-1], "removed."              # 8
del stack[len(stack)-1]                            # 9
• stack is a container,
• command is a most-recent holder.

## Walker

Walker traverses a data structure.

class Node:                                            # 1
def __init__(self, data=None, next=None):            # 2
self.data = data                                   # 3
self.next  = next                                  # 4
head = Node()                                          # 5
command = "x"                                          # 6
while command != "q" :                                 # 7
command = raw_input("Enter command: ")             # 8
if command == "n":                                 # 9
p = head                                       # 10
while p.next : p = p.next                      # 11
t = Node(raw_input("Enter element: "))         # 12
p.next = t                                     # 13
elif command == "p" :                              # 14
p = head.next                                   # 15
while p :                                      # 16
print p.data                               # 17
p = p.next                                 # 18
• p is a walker,
• head is a fixed value,
• t is a temporary,
• command is a most-recent holder,
• data is a fixed value,
• next is a fixed value.

## Linear search

You are working with a collection or stream of objects. How do you find an object that meets a specific condition?

Construct a Process All Items loop (see later on), but provide a way to exit the loop early should you find your target sooner.

for (i = 0; i < students.size(); i++)
break;

// process student[i], who has an A

If it is possible that you will not find your target, be sure to do a Guarded Linear Search (see next slide).

## Guarded linear search

You are doing a Linear Search.

How do you handle the possibility that no target may be found?

Follow the loop with an Alternative Action that treats the "not found" situation as a special case.

for (i = 0; i < students.size(); i++)
if ( student[i].grade().isAnA() )
break;

if (i < students.size())              // found it!
// process student[i], who has an A
else
// handle the exception

## Process all items

You are writing code that manipulates a collection.

The collection might be an array, a bag, a hashtable, a stream, or a file. You want to process all of the items in an identical manner.

There are two kinds of process-all-items loops:

• a definite loop that uses indexing, and
• an iterating loop when an iterating interface is used.

## Definite process all items

You are writing a Process All Items loop for an indexable collection, the number of items in the collection can be determined in constant time and indexing is constant time.

for(int k=0; k < v.size(); k++) {
process v[k]
}

## Iterator process all items

You are writing a Process All Items loop for a collection that uses an iterator interface or when constant time indexing of the collection is not possible.

For instance, in Java...

Hashtable table = new Hashtable();
// code to put values in table

Enumeration e = table.keys();
while (e.hasMoreElements()) {
process(table.get(e.nextElement()));
}

...or in C++...

Node * ptr = first;
while (ptr != NULL) {
process(ptr->info);
ptr = ptr->next;
}

## Loop and a half

You are writing a Process All Items loop. How do you structure the loop when the number of items in the collection isn't known in advance and the items are provided one-at-a-time?

Typical approach: use a sentinel.

read value
while (value != sentinel)
process value
read value

This leads to duplicate code for the read/get and makes the loop body harder to understand since it turns a read-and-process loop into a process-and-read loop.

Solution: while-true loop with a break in the loop body.

while (true)
if (value == sentinel) break;
process value

## Polling loop

You are writing a program that asks the user to enter a data value. How do you poll until the user enters a valid data item?

Many languages provide a do...while... construct that allows direct testing of a value after entry:

do {
cout << "Enter a grade between 0 and 100, inclusive: ";
} while (grade < 0 || grade > 100)
• same prompt on all requests, so the user may be confused by the repetition;
• the test is negative, which requires students to use De Morgan's laws to write the condition

Instead, you could follow the data entry with an explicit validation loop:

cout << "Enter a grade between 0 and 100, inclusive: ";

while (grade < 0 || grade > 100) {
cout << "Sorry!  That is an illegal value." << endl;
cout << "Enter a grade between 0 and 100, inclusive: ";
}

But still...

• replicated code,
• logically negated test.

Solution: add a loop and a half:

while (1) {
cout << "Enter a grade between 0 and 100, inclusive: ";

if (grade >= 0 && grade <= 100) break;

cout << "Sorry!  That is an illegal value." << endl;
}

## One loop for linear structures

How do you write code that processes data stored in a linear structure, such as an array, list, or file?

• A problem may seem to call for multiple loops to match intuition, but the data is stored sequentially
• Therefore, use the structure of the data to guide the solution: one loop for sequential data.
• For instance: removing duplicated elements from a sorted array. At first you may think of writing nested loops: an outer loop to process all items and an inner loop to search past duplicated items.
• The nested loop approach will make updating the indexing variable difficult.

Solution: use only a process all items loop.

void removedups(vector & a, int & n) {
// precondition: a <= a <= ... <= a[n - 1]
// postcondition: all duplicates removed from a,
//                n = # elements in a
int k;
int uniqueCount = 1;

// invariant: no duplicates in a .. a[uniqueCount-1]

for(k=1; k < n; k++) {
if (a[k] != a[uniqueCount-1]) {
a[uniqueCount] = a[k];
uniqueCount++;
}
}
n = uniqueCount;
}

# Some exercises

## Exercise 1

For each of the following snippets, try to assign to each variable a role.

### E1.1

public class Dog {
String name;
int age;
public Dog (String n) {
name = n;
age = 0;
}
public void birthday () {
age++;
}
}


### E1.2

public class ReversableString {
private char[] characters;
public ReversableString (String s) { characters = s.toCharArray(); }
public String get() { return new String(characters); }
public void reverse() {
int length = characters.length;
char tmp;
for (int i = 0; i < length/2; i++) {
tmp = characters[i];
characters[i] = characters[length-i-1];
characters[length-i-1] = tmp;
}
}
}


### E1.3

public class BankAccount {
private String accountNumber;
private float interest, balance=0;
public BankAccount (String nr, float percent) {
accountNumber = nr;
interest = percent;
}
public String getAccountNumber  ()        { return accountNumber; }
public float  getBalance        ()        { return balance; }
public float  getInterest       ()        { return interest; }
public void   setInterest (float pc)      { interest = pc; }
public void   transaction (float amount)  { balance += amount; }
}


### E1.4

public class Thermometer {
private int reading=-999, previous=-999, coldest=-999;
private boolean frozen=false;
public Thermometer () { }
public int  getReading () { return reading; }
public void setReading (int r) {
if (r < coldest) coldest = r;
if (r < 0) frozen = true;
}
public int     getPrevious () {return previous; }
public int     getColdest  () {return coldest; }
public boolean getFrozen   () {return frozen; }
}


### E1.5

public class Stack {
private int contents;
private Stack next;
public Stack() { this.next = null; }
public void add (int element) {
Stack node;
node = new Stack();
node.contents = element;
node.next = this.next;
this.next = node;
}
public int remove () {
int removed = 0;
if (this.next != null) {
removed = this.next.contents;
this.next = this.next.next;
}
return removed;
}
public int size () {
int size = 0;
Stack p = this.next;
while (p != null) {
size++;
p = p.next;
}
return size;
}
}
class StackTest {
Stack myStack = new Stack();
...
}


### E1.6

public class Item {
float taxfreePrice, priceWithTax;
public Item (float price) {
taxfreePrice = price;
}
public float setTax (float taxRate) {
float tax;
tax = taxRate * taxfreePrice / 100;
priceWithTax = taxfreePrice + tax;
return tax;
}
}


## Exercise 2

For each of the considered loop patterns, find out

• a typical, very simple instance, and
• a less evident instance.

### For instance...

Consider the case of linear search:

• An obvious instance is that of searching within a simple data structure linearly organized, such as when trying to find a vowel in a string s:
for c in s:
if is_vowel(c):
break

# process c
• A more elaborate case is that concerning data structures which, although not naturally organized in a linear fashion, may be accessed through the iterator pattern, such as the dictionary d in the following example:
for k in d:
if k.isdigit():
break