1. Create all the required data structures along with the implementation of each of the following methods for all classes. You are required to demonstrate the working of the each of the following methods by invoking them from a main program.
2. Read the redirected input and create all the data structures.
3. Demonstrate the working of the classes with two different data types: integer and character strings.
4. Document your project thoroughly as the examples in the textbook. This includes but not limited to header comments for all classes/methods, explanatory comments for each section of code, meaningful variable and method names, and consistent indentation.
To search for books and articles in a library computer system one uses keywords in combination with Boolean operators such as 'and' and or. For example, if you are going to search for articles and books dealing with uses of nanotechnology in bridge construction, the query would be nanotechnology and bridge construction. In order to retrieve the books and articles properly, every document is represented using a set of keywords. In the computer system, for each document apart from title, author(s), data of publication, publisher, and other bibliographic information, a set of keywords that represent the content of the document is stored.
An Inverted List data structure is where for each keyword we store a set of document numbers that contain the keyword. For example, for the keyword carbon fiber we will have the following:
bridge construction 887, 117, 665, 900
carbon fiber 887, 1098, 654, 665, 117
The documents numbered 887, 1098, 654, 665, and 117 will contain the keyword carbon fiber and the keyword bridge construction is found in documents numbered 887, 117, 665 and 900.
The Boolean queries are processed as illustrated in the following example. To obtain the documents containing the keywords bridge construction and carbon fiber we perform a set intersection operation and get the documents 887, 117, and 665. The Boolean query bridge construction or carbon fiber will result in a set union operation and the documents for this query are 887, 1098, 654, 665, and 900.
In this project we are going the create classes and methods that will lead us to the inverted list data structure.
A Cell is a linked list node and can contain any data (in this project we will assume that they are all integers). A Cell Node contains a value (a data type) and a pointer to a Cell. The Master Cell contains an array of Cell Nodes.
The input file contains an unknown number of lines of input. Each line contains an integer (we will call it info) and followed by an integer (call it noItems- number of items). Following this integer, there will be several integers (the number of them equal to noItems). For example, let us say that the input line is as follows:
106 5 1200 1800 300 4999 5000
106 is the info, noItems is 5 and the 5 integers are 1200, 1800, 300, 4999, and 5000. When you read the line, you will create a CellNode object store the value 106 in its _info field. You will create a linked list with the 5 values and store the pointer to the first element of the linked list created in the field _myCell of the CellNode object. The CellNode object that was created is stored in the first element of the vector _myCellNodes of the MasterCell object created in the main program. Here is a set of input lines:
106, 5 1200 1800 300 4999 5000
90, 3 30 1000 80
200, 3 20 10 40 90
50, 2 41 31
60, 3 88 75 26
65, 1 51
The data structure is pictorially depicted below: see image.
Below is a second set of input lines:
Operating Systems, 5 1200 1800 300 4999 5000
Compiler construction, 3 30 1000 80
Database Management systems, 3 20 10 40 90
Java programs for beginners, 2 41 31
Statistics introduction, 3 88 75 26
Algorithms analysis, 1 51
The data structure is pictorially depicted below: see image.
After reading all the input and creating appropriate objects, you have to demonstrate the working of all the methods in each of the classes.
You are required to implement the following class structures along with the implementation of the methods associated with each of them.
template < class DT>
class Cell {
protected:
DT* _value;
Cell< DT>* _right;
public:
//All required methods
};
template < class DT1, class DT2>
class CellNode {
protected:
DT1* _info;
Cell< DT2>* _myCell;
public:
//All required methods
};
template < class DT1, class DT2>
class MasterCell {
protected:
CellNode< DT1,DT2>* _myCellNodes;
public:
//All required methods
};