Grids

#include "grid.h"

For 2-D organizations, e.g., board games like chess
Good for board games, matrices, images, city maps, etc.
must specify element type in <> brackets (called a template parameter or a type parameter)

//constructing a Grid
Grid<int> matrix(3, 4);
matrix[0][0] = 75;
....

//constructing a Grid
Grid<int> matrix = {
  {75, 61, 83, 71},
  {94, 89, 98, 100},
  {63, 54, 51, 49},
};

Pictorially, the matrix looks like:

row/col  0   1   2   3
 0      75  61  83  71
 1      94  89  98 100
 2      63  54  51  49

Grid members

Member function name	Description
`Grid<type> name(r, c);` or `Grid<type> name;`	create grid with given number of rows/columns; empty 0x0 grid if omitted.
`g[r][c]` or `g.get(r, c)`	returns value at given row/col.
`g.fill(value)`	set every cell to store the given value.
`g.inBounds(r, c)`	returns true if given position is in the grid.
`g.numCols()` or `g.width()`	returns number of columns.
`g.numRows()` or `g.height()`	returns number of rows.
`g.resize(nRows, nCols)`	resizes grid to new size, discarding old contents.
`g[r][c] = value` or `g.set(r, c, value)`	stores value at given row/col.
`g.toString()`	returns a string representation of the grid such as `"{{1, 3}, {-8, 2}, {-3, -4}, {4, 7}}"`.
`cout << g`	prints, e.g., `"{{1, 3}, {-8, 2}, {-3, -4}, {4, 7}}"`.

Looping over a grid

Row-major order

for (int r = 0; i < grid.numRows(); r++) {
  for (int c = 0; c < grid.numCols(); c++) {
    //do something with grid[r][c]
  }

Using for-each loop (also row-major order)

for (int value : grid) {
  //do something with value (don't have access to row/col number)
}

Column-major order

for (int c = 0; c < grid.numCols(); c++) {
  for (int r = 0; i < grid.numRows(); r++) {
    //do something with grid[r][c]
  }

Show an example grid and show the difference between row-major and column-major orders.

Grid as a parameter

When a grid is passed by value, C++ makes a copy of its contents. Copying is slow, you should pass by reference with &. If the code won't modify the grid, also pass it as const.

Which one is best?

int computeSum(Grid<int> g) { ...}
int computeSum(Grid<int> &g) { ...}
int computeSum(const Grid<int> g) { ...}
int computeSum(const Grid<int> &g) { ...} : Best

Which one is best?

int invert(Grid<double> g) { ...} : will not work
int invert(Grid<double> &g) { ...} : Best
int invert(const Grid<double> g) { ...} : will not work
int invert(const Grid<double> &g) { ...} : will not work

Exercise: Write a function knightCanMove that accepts a grid and two row/column pairs (r1, c1), (r2, c2) as parameters, and returns true if there is a knight at chess board square (r1, c1) that can legally move to empty square (r2, c2).

Recall that a knight makes an "L" shaped move, going 2 squares in one direction and 1 square in the other.
knightCanMove(board, 1, 2, 2, 4) returns true.

bool knightCanMove(Grid<string> const &board, int r1, int c1, int r2, int c2)
{
  if (!board.inBounds(r1, c1) || !board.inBounds(r2, c2)) { 
    return false; 
  } 
  if (board[r1][c1] != "knight" || board[r2][c2] != "") { 
    return false; 
  } 
  int dr = abs(r1 - r2); 
  int dc = abs(c1 - c2); 
  if (!((dr == 1 && dc == 2) || (dr == 2 && dc == 1))) { 
    return false; 
  } 
  return true; 
}

Another solution:

bool knightCanMove(Grid& board, int r1, int c1, int r2, int c2) { 
    int dr = abs(r1 - r2), dc = abs(c1 - c2); 
    return board.inBounds(r1, c1) && board.inBounds(r2, c2) 
            && board[r1][c1] == "knight" && board[r2][c2] == "" 
            && ((dr == 1 && dc == 2) || (dr == 2 && dc == 1)); 
}

Grids as return values

Write two versions of addFive() method that adds 5 to each element of the grid: in the first version, the input grid itself is modified; in the second version, a new output grid is returned as a return value.

String Streams

#include

An istringstream lets you "tokenize" a string.

istringstream input("abc def 123 456");
string first, last, phone;
int age;
input >> first >> last; //first = "abc", last = "def", removes whitespace
input >> phone;  //phone = "123"
input >> age;  //age = 123

Another example: read all tokens from a string

istringstream input2("abc def 123 456 hello world");
string word;
while (input2 >> word) {
  cout << word << endl; //abc\ndef\n123\n456\n...
}

String streams are similar to I/O streams. e.g., cin>>word behaves similarly to input2>>word. The difference is that in the first case the input is read from the console (e.g., keyboard); in the second case the input is read from a string (stringstream).

An ostringstream lets you write output into a string buffer. Use the str member function to extract the string that was built.

int age = 42, iq = 95;
ostringstream output;
output << "abc's age is " << age << endl;
output << " and his IQ is " << iq << "!" << endl;
string result = output.str(); //this construct allowed us to convert integers and newline characters into strings. result = "abc's age is 42\nand his IQ is 95!\n"

Some subtle things about input streams, e.g., cin

Can use the getline function (notice small l) for getting a line of input from the console input stream.

cout << "What is your name? ";
string name;
getline(cin, name); //breaks on newline characters
cout << "Hi " << name << endl;

But, do not mix >> and getline on the same input stream! Not recommended and will give unexpected results.

cout << "How old are you? "; 
int age; 
cin >> age;  //user input: 17\n
cout << "And what's your name? "; 
string name; 
getline(cin, name);  //user input: abc\n
cout << "Wow, " << name << " is " << age << "!" << endl;

Output of the above program:

How old are you: 17
And what's your name: abc
Wow,  is 17!

Notice that the name was not read correctly because of mixing of >> and getline on the same input stream.

Advice for this course: always use Stanford getXxx methods to read from cin.

Exercise: write a function string_stats that prints statistics about the data in a string (passed an argument).

string s = "Hello I am really enjoying COL100.\nWhat a wonderful course this is.\nI am glad that I chose IIT Delhi\n\nI am sure this will help me in future\n";
string_stats(s);

For this string, the function should print the following output:

Line 1: 34 chars, 6 words
Line 2: 32 chars, 5 words
Line 3: 32 chars, 8 words
Line 4: 0 chars, 0 words
Line 5: 37 chars, 9 words
longest = 37 chars, average = 27.0 chars

Solution

/* Prints length/count statistics about data in the given file. */ 
void inputStats2(string filename) { 
    ifstream input; 
    input.open(filename); 
    int lineCount = 0, longest = 0, totalChars = 0; 
    string line; 
    while (getline(input, line)) { 
        lineCount++; 
        totalChars += line.length(); 
        if (longest < line.length()) {
          longest = line.length(); 
        }
        int wordCount = countWords(line);   // on next slide 
        cout << "Line " << lineCount << ": " << line.length() 
             << " chars, " << wordCount << "words" << endl; 
    } 
    double average = (double) totalChars / lineCount; 
    cout << longest = " << longest 
         << ", average = " << average << endl; 
}

And here is the definition of countWords:

/* Returns the number of words in the given string. */ 
int countWords(string line) { 
    istringstream words(line); 
    int wordCount = 0; 
    string word; 
    while (words >> word) { 
        wordCount++; 
    } 
    return wordCount; 
}