Objectives:

Design and implementation of data structures for a given Abstract Data Type.

Practice with linked lists

Coming up with a design which meets given runtime specifications.

Summary: you are given the specifications for an Abstract Data Type as a pure C++ virtual class along with runtime requirements. Your job: design and implement a class called GridWorld which meets the requirements.

The World: The world is kind of boring. It is an RxC grid (rows and columns). Each entry on the grid is called a district and is referred to by its row r and column c where r{0..R-1} and c{0..C-1}. Well sometimes refer to such a district as Dr,c.

The People: Then there are the people; each person is uniquely identified by an integer ID (like a social security number). Person IDs start at zero. Each living person resides in one (and only one) of the districts.

Day Zero: When a world is created, just two things determine its initial configuration:

R: the number of rows

C: the number of columns

Operations: once a world is created, there are various operations that can be performed. These operations are laid out in the table starting on the next page.

C++ Stuff: you have been given a file GWInterface.h which specifies a C++ "pure abstract class" called GWInterface. This class essentially specifies the ADT or interface: it provides no function implementations or specify any data members. It does specify the functions that must be included in any sub-class that claims to implement.

The Operations:

The table below lists each operation that must be supported including runtime and behavioral requirements.

Operation: Creation of a new world.

Corresponding Constructor:

GridWorld(unsigned nrows, unsigned ncols)

Description: initializes a world to have the dimensions specified by the parameters and zero population.

Operation: Creating a new person

Corresponding Member Function:

bool birth(int row, int col, int &id);

Description: by calling this function we are asking for a new person to be created and to place that person in district (row, col).

If the given row/col corresponds to a valid district, this function does the following:

creates a new person

assigns a unique integer ID to the person and

places that person in district (row, col).

communicates the assigned ID to the caller via the reference parameter id.

Returns true (for "success").

If parameters row/col do not refer to a valid district in the world, no person is created and false is returned.

Runtime requirement:

O(1). There is a caveat here: this bound will be technically amortized because you will be allowed to reallocate an array as more people are created. To achieve the amortized O(1) behavior, your resizing operation should yield an array twice as large as the previous capacity.

Rules For Assigning IDs (IMPORTANT): There are two scenarios here:

First Priority - Recycling a previously used ID: if there is one or more ID that was previously used for a person (who is now dead), you must use such an ID for the person being created. If there are multiple such IDs, you must assign the ID which has been "retired"/unused for the longest time (maybe this helps prevent fraud?)

If case-1 does not apply (no IDs to recycle): you must assign the smallest unused integer to the person being created.

Operation: "killing" an existing person

Corresponding Member Function:

bool death(int id);

Description: if alive, person represented by id is removed from its current district and the entire world. Data structures updated accordingly.

returns: true if operation succeeds; false if fails (no such living person).

Runtime requirement: O(1)

Tip: think about the ID assignment policy for the birth function; how might it affect your implementation of the death function?

Operation: moving/relocating a person to a target district

Description: if given person is alive, and specified target-row

and column are valid, person is moved to specified district and

data structures updated accordingly.

return: indicates success/failure

runtime: O(1)

comment/note: the specified person becomes the 'newest' member

of target district (least seniority) -- see requirements of members().

This is true even if the target district happens to be the same as

the person's current district (basically resets their seniority).

bool move(int personID, int targetRow, int targetCol);

Operation: querying for the current population of the entire world.

Corresponding Member function:

int population()const;

Description: simply returns the total number of (living) people in the entire world/grid.

Runtime: O(1)

Operation: querying for the current population of a specific district.

Corresponding Member function:

int population(int row, int col)const;

Description: simply returns the total number of (living) people in district specified by (row,col). If row/col does not correspond to a valid district, zero is returned.

runtime: O(1)

Operation: determine the district where a particular person lives.

Corresponding Member Function:

bool whereis(int personID, int &row, int &col)const;

Description: if personID represents a currently living person, the row and column where that person currently lives is reported via reference parameters row and col and true is returned.

If personID does not correspond to a currently living person, false is returned.

Runtime: O(1)

Operation: exporting the current members of a particular district.

Corresponding Member Function:

std::vector * members(int row, int col)const;

Description: creates and populates an integer vector with a snapshot of the current residents of district specified by (row, col). The vector is returned as a pointer.

If there is no such district (row,col), a vector is still created returned, but it is empty.

Requirement: the members of the district must be ordered in descending order of seniority: The person who has lived in the district the longest must be first and so-on.

Runtime: O(Nr,c) where Nr,c is the population of the district in question.

Tip: Think about the the ordering requirement above and how functions birth, death and move impact this rule.

Operations: queries for dimensions of world.

Corresponding Member Functions:

int num_rows()const;

int num_cols()const;

Description: Pretty self-explanatory - just returns the number of row (or columns) in the world. (Note that once a world is created, the dimensions are fixed).

Runtime: O(1)

Comment: these should be one-liners.

Operation: deallocating a world and doing associated cleanup.

Corresponding Destructor:

~GridWorld()

Description: deallocates all dynamically allocated objects associated with the world -- typical destructor stuff.