----------------------------------------------------------------------

QUESTION 1 (10 marks):

What does the following program output?

#include <iostream>
using namespace std;

class A {
public:
	A(int i) : i(i) {
		cout << "Constructor: " << i << endl;
	}
	A(const A &o) : i(o.i) {
		cout << "Copy constructor: " << i << endl;
	}
	A& operator=(const A &o) {
		cout << "Assignment operator: " << o.i << "->" << i << endl;
		i = o.i;
		return *this;
	}
	~A() {
		cout << "Destructor: " << i << endl;
	}
private:
	int i;
};

A a(10);

A test(const A &a, A b, A *c) {
	return *c;
}

int main() {
	A b = a;
	a = b;
	test(1, b, &b);
}


ANSWER:

Constructor: 10
Copy constructor: 10
Assignment operator: 10->10
Copy constructor: 10
Constructor: 1
Copy constructor: 10
Destructor: 10
Destructor: 10
Destructor: 1
Destructor: 10
Destructor: 10


----------------------------------------------------------------------

QUESTION 2 (10 marks):

(a) What operations are required from a Front Insertion Sequence?
    Give an example of a Front Insertion Sequence from the C++ STL.
(b) What type of iterators do Front Insertion Sequences support?
(c) What are the operations that can be performed on a Bidirectional Iterator?


ANSWER:

(a) The operations specifically required by a Front Insertion Sequence are
    push_front() and pop_front(). In addition, Front Insertion Sequences
	require constant time to insert and access the front element. An
	example is the list class.
(b) Front Insertion Sequences support Forward Iterators, the same type of
    iterators as the general Sequence abstraction.
(c) Bidirectional iterators support increment (++), decrement (--),
    dereferencing for read and write, non-alternating dereference and
	increment, Assignable and Equality Comparable.


----------------------------------------------------------------------

QUESTION 3 (15 marks):

You are required to write a program in C++ to perform the following:

	The program is to keep track of student's marks for a course.
	The program shall allow the user to enter new students, as well
	as new assignments. The user must also be able to enter a mark for
	a specific student and assignment. The user shall also be able
	to retrieve the marks of a particular students, or all the students
	that recieved a particular mark.

	The program must also print out a list of final marks for all the
	students. The final mark is simply the sum of all the assignment
	marks.

Which containers from the STL would you use? Explain what you would use them
for and why you choose those particular containers.


ANSWER:

I would use a multimap with students as the keys and assignment marks as the
values. I would use a second multimap with assignment marks as the keys and
students as the values.

When the user entered a student and their mark I would insert the data into
both multimaps - inserting into multimaps is fast so that will be OK.

When the user asks for the marks of a particular student I would retrieve them
from the first multimap, this will be fast since multimaps are designed to
have fast lookups.

When the user asks which students recieves a certain mark I would retrieve
them from the second multimap, this will be fast since multimaps are designed to
have fast lookups.

Outputing the final marks is simply a matter of iterating through the first
multimap and keeping track of the total mark for each student possibly using
a map<student,mark>. 

multimaps were chosen because they have fast lookup based on key and fast
insertions.


----------------------------------------------------------------------

QUESTION 4 (5 marks):

Modify the following linked list of integers class to be a linked list
template.

struct Node {
	int value;
	Node *next;
};

class List {
public: 
	List();
	List(const List&);

	List& operator=(const List&);

	~List();

	int length() const;
	void insert_at_front(int value);
	bool insert_after_current(int value);
	void advance_current();
	int get_current_value() const;

private:
	Node *head;
	Node *current;
};


ANSWER:

template <typename T>
struct Node {
	T value;
	Node<T> *next;
};

template <typename T>
class List {
public:
	List();
	List(const List&);

	List& operator=(const List&);

	~List();

	int length() const;
	void insert_at_front(T value);
	bool insert_after_current(T value);
	void advance_current();
	T get_current_value() const;

private:
	Node<T> *head;
	Node<T> *current;
};



----------------------------------------------------------------------

QUESTION 5 (10 marks):

The following code is meant to read integers from cin and output the integers
it read in sorted order with duplicates removed. Why doesn't it work?
How would you fix it? What containers/algorithms could be used to make 
the program simpler?

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <iterator>

int main() {
	std::vector<int> v;
	std::copy(std::istream_iterator<int>(cin), std::istream_iterator<int>(), std::back_inserter(v));
	std::unique(v.begin(), v.end());
	std::sort(v.begin(), v.end());
	std::copy(v.begin(), v.end(), std::ostream_iterator<int>(cout, "\n"));
}


ANSWER:

There are two reasons the code doesn't work. The first is that the
unique() algorithm only removes adjacent identical entries, and thus
requires the range to be sorted to remove all duplicates. Thus the
unique() and sort() calls are in the wrong order and should be swapped.
The second problem is that unique() doesn't actually remove the elements
from the range, it merely reorders them and returns a new end iterator.

To fix these problems the lines

	std::unique(v.begin(), v.end());
	std::sort(v.begin(), v.end());

are changed to

	std::sort(v.begin(), v.end());
	v.erase(std::unique(v.begin(), v.end()), v.end());

The act of erasing the elements from the vector could also be avoided by
simply using the result of unique() in the call to copy(), like this:

	std::sort(v.begin(), v.end());
	std::copy(v.begin(), std::unique(v.begin(), v.end()), std::ostream_iterator<int>(cout, "\n"));

We make the program simpler by storing the ints in a set. The set will
automatically store each int only once (since it's a Unique Associative
Container) and will store them in sorted order (since it's a Sorted
Associative Container). The entire process now looks like this:

#include <iostream>
#include <set>
#include <algorithm>
#include <functional>
#include <iterator>

int main() {
	std::set<int> v;
	std::copy(std::istream_iterator<int>(cin), std::istream_iterator<int>(), std::inserter(v, v.begin()));
	std::copy(v.begin(), v.end(), std::ostream_iterator<int>(cout, "\n"));
}


----------------------------------------------------------------------

QUESTION 6 (10 marks):

Consider a program with the following specification:

The program reads from standard input. The first line contains a single
integer. The remaining lines are output from the grep command, that is,
they have the form:

<filename>: <line of text>

The program should output each "line of text" (ie. the text after the ':'
character) and add it to the file called "<filename>.log". At most n lines
should be output, where n is the integer read from the first line.

For example, the input

3
test.cc: A test program
main.cc: The main program
test.cc: Revised the test program
sample.cc: Some sample code

causes the lines:

A test program
Revised the test program

to be added to the file test.cc.log, and the line

The main program

to be added to the file main.cc.log.

Implement this program in C++ or Bourne/bash shell. If you have source
code in more than one file, clearly indicate the filename above its
contents in your answer.


ANSWER:

A C++ solution is:

#include <iostream>
#include <fstream>
#include <string>

int main() {
	int max;

	cin >> max;

	int i = 0;
	string filename;
	while ((i < max) && (cin >> filename)) {
		char ch;
		string text;
		cin >> ch;
		getline(cin, text);
		text = ch + text;
		filename = filename.substr(0, filename.length()-1);
		filename += ".log";
		ofstream out(filename.c_str(), ios::app);
		out << text << endl;
		i++;
	}
}


and a Bourne shell solution is:

#!/bin/sh

read max
i=0
while read outfile text; do
	outfile=`basename $outfile :`
	echo "$text" >> ${outfile}.log
	i=`expr $i + 1`
	if [ $i -ge $max ]; then
		break
	fi
done


----------------------------------------------------------------------