Advanced Programming I Code Review for Programming Assignment 3

Advanced Programming I Lecture Notes

14 March 2006 • Assignment 3 Code Review

Outline

The problem.
Some solutions.
Testing
Results
Coding observations.

The Problem

Build a concordance generator.

A Big Idea

The data are page numbers and words.
A concordance views the data from two directions:
1. Words on a page.
2. Pages with a word.
Any data structures allow two views on the data?
- A matrix.

A Concordance Matrix

A boolean matrix indexed by word and page.
m[w][p] is true iff word w appears on page p.

Matrix Slices

A concordance deals with whole rows and columns.
Call these boolean vectors matrix slices.

Slice Manipulations

The and of boolean vectors results in common elements.
- m[any][*] & m[nail][*]
  - All pages containing "any" and "nail".
- m[*][3] & m[*][102]
  - All words appearing on pages 3 and 102.

The Concordance Matrix ADT

add_page(page p) - add the words from p to the matrix.
```
while inf >> p
  m.add_page(p)
```
get_slice(query q) - return a slice that's the and of all the query elements.
```
while cin >> q
  cout << m.get_slice(q)
```
Other operations as needed.

Matrix ADT Implementations

Use a boolean matrix.
- Fast and space efficient.
- But,
  - Not easily dynamic.
  - Not every word appears on every page.
    - A large number of false elements.
Use a sparse-matrix representation.

Sparse Matrices

a sparse matrix

Which Is Better?

Look to the data for an answer.
- The Wealth of Nations has 380,000 words on 616 pages, 670 words per page.
- A boolean matrix requires 380,000×616 ∼ 8 mbytes.
- A sparse matrix requires 670×616 ∼ 413,000 elements.
At 16 bytes/element it's a toss-up.

Which Is Better?

Look to the operations for an answer.
- Adding entries is easier for boolean matrices.
- Changing size is easier for sparse matrices.
- Indexing is faster for boolean matrices once the words have been mapped.
- Slicing is slightly easier for boolean matrices.
What is the name of this section?
- Use sparse matrices.

The Other ADTs

Pages
- Straightforward
Slices
- Either a boolean vector or a linked list.
  - Boolean vectors work well.
Queries
- Almost the same as pages.

Dualities

A query can be for words or page numbers.
A slice can be along a row or a column.
Both are different but mostly the same.
- It's simplest to treat them as the same.
```
query q
while cin >> q
  cout << m.get_slice(q)
```
How?

Type Tagging

Slices and queries can maintain type tags.

class query
  enum q_type { words, pages }
  q_type t
  string * words
  int * pages

This is clumsy and generally considered bad programming practice.
- We'll consider better approaches (subtype polymorphism) later in the semester.

Test Cases

Empty and garbage test cases.
No-argument test "./concord".

Cat and multi test cases.

PAGE 1
cat

PAGE 1
cat blue emerald
PAGE 2
cat red  diamond
PAGE 3
dog blue diamond

Smith and big test cases.

Big Test Cases

A +1000-page text.
- The C++ Programming Language, Bjarne Stroustrup, 1997, 1020 pages.
- Infinite Jest, David Wallace, 1996, 1079 pages.
A +1000-character word.

Test Results

	Tests
	1	2	3	4	5	6	7
1
2
3
4
5

Coding Observations

Comments
STL containers.
Know Your Tools.
Check array accesses.
Program defensively.
Obey the Rule of Three.

Comment Your Code

Every function should have a comment.
The comment should describe
- The inputs, including any globals.
- The outputs, including any globals.
- The relation between inputs and outputs.
- Error conditions, including exceptions thrown.
Keep your functions (and so your comments) simple.

Good Comment Characteristics

Good comments should answer two questions:
1. What does this procedure do?
2. How do I call this procedure?
Good comments do not tell me how the function works.
- Although they may contain asymptotic behavior estimates.

Example Comments

Bad


bool searchPage(
  string a[], List * word, int y, int page)

So so.


/* STORE THE FIRST QUERY PAGE'S UNIQUE WORDS */

int store_words(string* pt, int count, int in)

Good


bool List::first(ListElementType & elem);

  // Precondition: true.
  // Postcondition: if this list is empty, elem is undefined, 
  //   otherwise elem is a reference to the first item.
  // Returns: true if and only if elem is defined.

No STL Containers

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <stdlib.h>

Iterators and algorithms are o.k., but no containers.
- The rest of the C++ standard library is o.k. too.

Know Your Tools.

int main(int argc char * argv[]) { ... }

What is argc?
- argc (the argument count): an int whose value is the number of strings on the command line ~~when the command to execute the binary executable of the program given~~ (Nyhoff, page 122).
- argc is one past the last legal value in argv (me).
argv[argc] is never valid (off-by-1 error).

Know Your Tools..


int main (int argc,char *argv[])
  ifstream myfile(argv[1])

int main(int argc, char *argv[])
  string infile(argv[1])
  ifstream fin
  fin.open(infile.c_str())

int main (int argc, char ** argv)
  if (argc == 1) { cerr << emsg; exit(0) }
  string filename = argv[1]

int main(int argc, char** argv)
  if (argc != 2) cout << emsg
  ifstream infile(argv[1])

Check Array Accesses

What's wrong with this code?


int * arrayInt = new int[QueryPages.Size()]
int cnt = 1
do 
  cnt++
  second  =  Text[arrayInt[cnt]]
while cnt < QueryPages.Size()

It is the programmers responsibility to make sure every array access is valid.
- C++ is not going to help you.

Pointer Errors Are Nasty

$ ./concord smith.txt
? 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Segmentation fault (core dumped)

$ ./concord smith.txt
? 2 3 4 5 6 7 8 9 10 11 12 13 14
and as be it not of that the
? 2 3 4 5 6 7 8 9 10 11 12 13 14 15
and as be it not of that the
?

Program Defensively

This is bad programming because it doesn't check its own limits.

int answer[1000]
int pagefound = 0
answer[pagefound] = i
pagefound++

Better, but what's with the magic numbers?
```
char buf[256]
memset(buf, '\0', 256)
line.copy(buf, 256)
```
- This code still has a nasty error.

Obey The Rule of Three

Every class with pointers must define a destructor, a copy constructor and an assignment operator.

You should recoil from classes like this:


class List {
  public:
    List();
    void insert(const ListElementType &)
    bool first(ListElementType &)
    bool next(ListElementType &)
  private:
    Node * link
  }

Obeying The Rule of Three

But professor, I don't need the rule of three.

I have three replies:
1. How do you know?
2. Maybe not now, but how about later?
3. Wrong

Back up your assertion.


class List {
  public:
    List();
    void insert(Element &)
    bool first(Element &)
    bool next(Element &)
  private:
    Node * link
    List(const List &)
   ~List()
    List & operator=(List)
  }

This page last modified on 16 March 2006.
This work is covered by a
Creative Commons License.