CS 202 Spring XXXXXXXXXXAssignment 8
Linked Lists
Overview
Oh no, someone has left a pile of ga
age around and we’re the only ones who can sort it. This may not
sound like the most enticing job, but hey, someone’s gotta do it.
In this assignment, you will be given a "ga
age" text file containing a piece of data on each line. However,
the type of each datum is a
itrary. That is, on any line, you could receive any piece of ga
age, here being
any primitive type. Any line could contain an int, a double, a bool, a char, or a string. As an example from
the provided ga
age file:
j
t
3.0000
57
true
man
1
Contains two chars, a double, an int, a bool, and then a string. It is possible that each of these lines could
e interpreted as several different data types, so we will need to establish a precedence for the types. Each
line will be given the following priority with regards to types: int > char > double > bool > string,
where int has the highest priority and string has the lowest priority. This means something like 3 will be
treated as an int first, rather than a double, char, or string, which might all also make sense.
To organize these various pieces of trash, we will place them into a big ga
age pile and then sort our way
through it. This will involve reading the data, determining the type, and then placing it into our pile. The
pile will be represented here as a series of doubly linked nodes, with each node containing a single piece of
ga
age. After throwing everything into the pile, we will sort all of the ga
age first by its type, and then
y the standard sorting implementation for that type. See the Sample Output section for an example of
how the sorting will look.
Global Helper Functions
Below is a list of global helpers independent of any classes. Aside from these, please also be aware of the
preprocessor definitions at the top of dataProcessing.h which can be used. These are described by the
functions in which they are relevant. You have to implement one of the functions, which is in red.
• bool isInteger(string s) - Tells whether a given string can be interpreted as an integers. Returns
true if so, false if not.
• bool isChar(string s) - Tells whether a given string can be interpreted as an integers.
• bool isDouble(string s) - Tells whether a given string can be interpreted as an integers.
• bool isBool(string s) - Tells whether a given string can be interpreted as an integers.
• stob(string s) - Converts the given string to a boolean value. Assumes the string is either "true" o
"false", else gives an e
or.
• unsigned int getDataType(string ga
age) - This function takes in a string and determines what
kind of data the string is. Using all the "is" functions above, check the string to see if any are true. If
it is an integer, return INT. Next, check for char and return CHAR if true. The next checks are fo
ool and then for double. If none of the checks return true, return STRING.
2
UML Diagrams
dataElementBase
- dataType : ushort
- next : dataElementBase*
- prev : dataElementBase*
+ dataElementBase(ushort)
+ dataElementBase(const dataElementBase&)
+ operator=(const dataElementBase&) : void
+ virtual ~dataElementBase()
+ virtual *getData() = 0 : void
+ virtual printElement(ostream&) const = 0 : void
+ getNext() const : dataElementBase*
+ getPrev() const : dataElementBase*
+ getDataType() const : ushort
+ link(dataElementBase*) : void
+ compare(dataElementBase*) : short
+ static getNewDataElement(uint, string) : dataElementBase*
+ static deepCopyDataElement(dataElementBase*) : dataElementBase*
+ static swap(dataElementBase*, dataElementBase*) : void
dataElement
- data : t
+ dataElement(ushort, t)
+ getData() void*
+ printElement(ostream&)
t
ga
agePile
- head : dataElementBase*
- tail : dataElementBase*
- size : uint
+ ga
agePile()
+ ga
agePile(const ga
agePile&)
+ ~ga
agePile()
+ operator =(const ga
agePile&) : void
+ addItem(string) : void
+ clearGa
agePile() : void
+ sort() : void
+ operator[] (uint) : dataElementBase*
Important Classes and Functions
Below is a list of functions and variables that are important for this assignment. Variables are in green,
functions that you will need to write are in red, functions implemented for you already are in
3
lue, and functions that are abstract that will be implemented later are in magenta.
dataElementBase
This class serves as an abstract base for our dataElement class. A dataElementBase can be thought of
as similar to a doubly linked node, just with a few extra functions added in. These will be linked togethe
later in our ga
agePile class to form a full pile, with each node holding a single piece of ga
age of some
a
itrary type along with pointers to the next and previous node. Since this acts as the base class for all
variations of dataElement, we will use pointers of this type to point to any single dataElement, regardless
of the actual type of data it holds.
• unsigned short dataType - An enumeration-esque variable that stores an integer representing the
type this object is storing. Use this to do easy checking on the contents of a node. Use the preprocesso
definitions at the top of the dataProcess.h when using this variable. This should be limited to INT,
CHAR, DOUBLE, BOOL, and STRING.
• dataElementBase* next - Points to the next dataElementBase object that comes after this one
in our pile. If nothing is after it, this will be nullptr.
• dataElementBase* prev - Points to the previous dataElementBase object that comes before this
one in our pile. If nothing is before it, this will be nullptr.
• dataElementBase(unsigned short dt) - A constructor to initialize a
and new item for the linked
list. The parameter dt is the data type that the item will be {INT, CHAR, DOUBLE, BOOL, o
STRING}. Note that this class is abstract, so this constructor will only be called for objects of the
derived class. The actual data value that will be stored is initialized in the derived class constructor.
The derived class constructor must specify a call to this one.
• dataElementBase(const dataElementBase& copy) - This constructor will initialize the this
object to be a copy of the parameter object. The dataType is the only thing that should be copied. Do
not copy the next and prev pointers, as this will link the new item into the original list (seen below).
The green item is the new copy of the second element in the original list (in blue). The problem here
is that the original list doesn’t know that the new item is linked in, therefore, we cannot expect this
list to properly deallocate. Because of this problem, we will treat the copy constructor as a method to
create a new item with the same dataType that will be linked in a completely different list. So, just
initialize next and prev to be nullptr.
• void link(dataElementBase* node) - This function is used to link a node into the pile. The
parameter node to be linked will always be linked to the right of this dataElementBase object. That
is, it will always be linked through the this->next pointer. Assign the parameter node to the next
pointer. The node parameter has a prev pointer that needs to be linked as well. This should only be
done if node is not nullptr.
• unsigned short getDataType() const - Simple getter for the dataType variable.
• virtual void* getData() = 0 - This will grab the data being stored in our node. This act as a gette
for the dataElement class, but will return the data generically as a void*.
4
• virtual void printElement(ostream& out) = 0 - This will print the data stored in the node to
the given stream. We will implement this later in the dataElement class.
• virtual ~dataElementBase() - This destructor has to exist in order to properly deallocate dataEle-
ments that contains objects of a class.
• short compare(dataElementBase* deb) - Tells how two dataElementBase compare to one an-
other by comparing this to the other object, deb, passed. Returns an enumeration-esque short intege
on the status of the comparison defined by preprocessor directives at the top of dataProcessing.h. Can
eturn LESSTHAN, GREATERTHAN, or EQUAL. This will compare the two objects based first on
their type, followed by comparing the actual contents if the types match. The priority can be seen in
the other preprocessor directives or earlier in the Overview section.
• void operator =(const dataElementBase& copy) - = overload that makes a deep copy of the
given dataElementBase object to this one. Should copy only the dataType of the other over to this
one. Similar to the copy constructor, we do not want to link the this object into the list that the
data is being copied from, therefore, leave the next and prev pointers as they are or just set them to
a default of nullptr.
• dataElementBase* getNext() const - Getter for the next member.
• dataElementBase* getPrev() const - Getter for the prev member.
• static dataElementBase* getNewDataElement(unsigned short dataType, string data) -
This is where the code can get kind of funky. The job of this function is to return a reference to a
and new data element for a linked list. The dataType parameter is the type of data being stored and
the data parameter is the data to be stored. The pointer that is returned will contain a value given
y new. An example of this can be seen below, in which we return a reference to a new data element
that is of dataType type:
1 return new dataElementBase(dataType);
Unfortunately, this does not work because we cannot instantiate an abstract class. Actually, a reference
to a derived class object must be returned. Note here that derived class objects are of template type,
thus they need to be allocated appropriately. For example, if the data type of our data element is INT,
the code may look like:
1 return new dataElement
( dataType , stoi(data));
The "?" is where the data parameter will go, though it will need to be converted to the proper datatype.
You have access to stoi(), stod(), and a helper function called stob() (for bools). This function should
use the given dataType to figure out the type, construct a dataElement object of the co
esponding
type as seen above, and then set its data field after converting it using the appropriate conversion
function.
• static dataElementBase* deepCopyDataElement(dataElementBase *deb) - This function
operators similar to the one above. The only difference is the parameter, in which a deep copy of the
parameter must be made. So, a reference to a derived object allocated with new is required. The main
problem is getting the data being stored in the parameter. The