Homework 7 - Computer Architecture I - ShanghaiTech University

Goals

In this assignment, you can finally code in C++ again. Topics covered are:

Template Metaprogramming.
Iterator.
Function object.
A better understanding of the STL containers.

Setup

Download the following files: doubll2d.hpp and Makefile.

Overview

Your task is to implement a 2D doubly linked list in C++ using templates. doubll2d.hpp declares all the classes needed. Some of the methods are left for you to define. For templates, the program that is using them has to always include the implementation as well, because we cannot generate and link to a .o file because the code depends on the template parameter. To keep the code clean it is one convention to still only declare the classes and functions in a .hpp file while its implementation goes into a *-impl.hpp file which is included at the end of the .hpp file.

Implementation Details

Finish the implementation of the class and methods in doubll2d-impl.hpp. And you should obey the following rules:

No standard libraries are allowed to use. Specifically, no #include statements are allowed to appear in doubll2d-impl.hpp.
We assume type T has default constructor and destructor, and it is both copy constructible and assignable.
The number of comments should be at least 25% of the non-blank lines. The TA's will check by hand if those comments are valid, meaningful and in English - failure to comply may lead to a score of 0 for this HW. You can use this Python script, which is the same as that on Autolab, to check your comments.

List node

Similar to HW2, a list node has four pointers to its left, right, up and down adjacent nodes. list node is implemented in doubll2d.hpp for you.

Iterator

You need to finish the implementation of list_row_elem_iter<T>, list_col_elem_iter<T>, list_row_iter<T>, list_col_iter<T>.

`list_row_elem_iter<T>`

This iterator represents an element in some row. You should overload the following operators:

*: dereference operator.
->: pointer operator.
==, !=: comparison operator.
++, --: self increment and decrement operator. Here, operator++ represents the next right element, while operator-- represents the last left element in this row.

`list_col_elem_iter<T>`

This iterator represents an element in some column. You should overload the following operators:

*: dereference operator.
->: pointer operator.
==, !=: comparison operator.
++, --: self increment and decrement operator. Here, operator++ represents the element below, while operator-- represents the element above in this column.

`list_row_iter<T>`

This iterator represents a row in a 2D doubly linked list. You should implement the following methods.

Method: list_row_elem_iter<T> begin(): Returns the iterator of the leftmost element in this row.
Method: list_row_elem_iter<T> end(): Returns the iterator next to the rightmost element in this row.
Method: reverse_iter<list_row_elem_iter> rbegin(): Returns the reverse iterator of the rightmost element in this row.
Method: reverse_iter<list_row_elem_iter> rend(): Returns the reverse iterator before the leftmost element in this row.

You should also overload the following operators:

*: dereference operator.
->: pointer operator.
==, !=: comparison operator.
++, --: self increment and decrement operator. Here, operator++ represents the row below, while operator-- represents the row above.

`list_col_iter<T>`

This iterator represents a column in a 2D doubly linked list. You should implement the following methods.

Method: list_col_elem_iter<T> begin(): Returns the iterator of the top element in this column.
Method: list_col_elem_iter<T> end(): Returns the iterator below the bottom element in this column.
Method: reverse_iter<list_col_elem_iter> rbegin(): Returns the reverse iterator of the bottom element in this column.
Method: reverse_iter<list_col_elem_iter> rend(): Returns the reverse iterator above the top element in this column.

You should also overload the following operators:

*: dereference operator.
->: pointer operator.
==, !=: comparison operator.
++, --: self increment and decrement operator. Here, operator++ represents the right column, while operator-- represents the left column.

2D Doubly Linked List

Finally, implement the 2D doubly linked list. Implement the following methods:

Method: list_row_iter row_begin(): Returns an iterator to the first (top) row in this list.
Method: list_row_iter row_end(): Returns an iterator below the last (bottom) row in this list.
Method: reverse_iter<list_row_iter> row_rbegin(): Returns a reverse iterator to the last (bottom) row in this list.
Method: reverse_iter<list_row_iter> row_rend(): Returns a reverse iterator above the first (top) row in this list.
Method: list_col_iter col_begin(): Returns an iterator to the first (leftmost) column in this list.
Method: list_col_iter col_end(): Returns an iterator after the last (rightmost) column in this list.
Method: reverse_iter<list_col_iter> col_rbegin(): Returns a reverse iterator to the last (rightmost) column in this list.
Method: reverse_iter<list_col_iter> col_rend(): Returns a reverse iterator before the first (leftmost) column in this list.
Method: list_row_iter insert_row(list_row_iter cursor, input_iter begin, input_iter end ): Insert a new row in the list below the row referenced by cursor. The data stores from input_iter begin to end.; When the length of data is shorter than it should be, you should fill the rest part by default value of T.; When the length of data is longer than it should be, you should make use of the dim_col items from begin and ignore the extra elements.; If the list is empty, you should insert the whole data from begin to end.; If the list is empty and begin equals to end, do nothing and return row_end().; If the cursor equals to row_end() operator, insert the data above the origin first row.; Return the iter of the row inserted.
Method: list_col_iter insert_col(list_col_iter cursor, input_iter begin, input_iter end ): Insert a new column in the list after the column referenced by cursor. The data stores from input_iter begin to end.; When the length of data is shorter than it should be, you should fill the rest part by default value of T.; When the length of data is longer than it should be, you should make use of the dim_col items from begin and ignore the extra elements.; If the list is empty, you should insert the whole data from begin to end.; If the list is empty and begin equals to end, do nothing and return col_end().; If the cursor equals to col_end() operator, insert the data before the origin first column.; Return the iter of the column inserted.
Method: list_row_iter delete_row(list_row_iter cursor ): Delete the row where the given cursor reference to and returns the row_iter above the given cursor.; If the first row is deleted, then return the row_iter below the given cursor.; If the deleted row is the only row in the list, return row_end().; If the cursor is row_end() operator, do nothing and return row_end() operator.; If the last row in list is deleted, the size of list should be set to 0*0.
Method: list_col_iter delete_col(list_col_iter cursor ): Delete the column where the given cursor reference to and returns the col_iter left to the given cursor.; If the first column is deleted, then return the col_iter right to the given cursor.; If the deleted column is the only column in the list, return col_end.; If the cursor is col_end() operator, do nothing and return col_end() operator.; If the last column in list is deleted, the size of list should be set to 0*0.
Method: void clear(): Clear all the nodes in this list.
Method: R reduce(std::function<R(R, const T &)> fn, R init ): This reduce() implementation takes a reducer function and an initial value for the accumulator.; For each iterable item, the reducer is called, passing it the accumulator and the current list element.; The return value is assigned to the accumulator. When it's finished applying the reducer to all of the values in the list, the accumulated value is returned.

Hints

You can refer to the GNU C++ Library's implementation. In GNU/Linux, the header file for std::list is placed at /usr/include/c++/<GCC version>/.
Because the compiler will not generate any code if the templates are not used, so it won't complain about errors exist in methods you do not use. It is strongly suggested that you test all your methods before submission. One easy approach is to specialize your templates and compile it.

Submission

Submit doubll2d-impl.hpp to Autolab.