c++: template to work with sorted list of ints and strings

Zenoture
Zenoture used Ask the Experts™
on
So I have finally templated the script, and it works with ints, chars, floats, and doubles, but does not like strings. How would I go about allowing this program to make a sorted list of strings based on the template?

// driver file

#include <iostream>
#include "llSorted.h"

int main()
{
	llSorted<int> templatize;
	
	templatize.init();
}

Open in new window

// header file - llSorted.h

#ifndef LLSORTED_H
#define LLSORTED_H

template <class itemType>
class llSorted
{
private:
	struct node
	{
		itemType data;
		node* next;
		node* prev;
	};
	node *head, *tail, *cur;
	int MAX_SIZE;
	int length;
	itemType temp;
	int index;
	int value;
	int cmd;
	bool found;
	bool inserted;

public:
	llSorted();
	bool isFull();
	bool isEmpty();
	void init();
	void printList();
	void InsertItem();
	void RetrieveItem();
	void DeleteItem();
	void getLength();
	void usrVal(int);
	void validation();
	int exit();

};

#endif

Open in new window

// implementation file - llSorted.cpp

#include <iostream>
#include <cstdlib>
#include <ctime>
#include "llSorted.h"
using std::cout;
using std::cin;
using std::endl;

template <class itemType>
llSorted<itemType>::llSorted()
{
	srand(time(0));

	head = NULL;
	tail = NULL;
	cur = NULL;
	index = 0;
	MAX_SIZE = 11;
	length = rand() % 10 + 1;
	cmd = 0;
	for (int i = 0; i < length; i++)
	{
		if (head == NULL)
		{
			head = new node;
			head->data = rand() % 101;
			head->next = new node;
			head->prev = NULL;
			cur = head->next;
			cur->prev = head;
		}
		else
		{
			cur->data = rand() % 101;
			cur->next = new node;
			cur->next->prev = cur;
			cur = cur->next;
		}
	}
	tail = cur;
	tail->next = head;
	head->prev = tail;

	// sort the list
	if (head != NULL)
	{
		cur = head;
		for (int i = 0; i < length; i++)
		{
			for (int j = 0; j < length; j++)
			{
				if (cur->next != tail)
				{
					if (cur->data > cur->next->data)
					{
						temp = cur->data;
						cur->data = cur->next->data;
						cur->next->data = temp;
					}
				}
				cur = cur->next;
			}
		}
	}
}

template <class itemType>
void llSorted<itemType>::init()
{
	printList();
	cout << "\nAvailable Commands:\n  1. Insert Item\n  2. Retrieve Item\n  3. Delete Item\n  4. List Details\n  9. Select Different Implementation\n  0. Exit\n\nCommand: ";
	while(!(cin >> cmd))
	{
		cout << "Please enter only the number associated with the command\nCommand: ";
		cin.clear();
		cin.ignore(1000, 10);
	}

	switch (cmd)
	{
	case 1:
		InsertItem();
		break;
	case 2:
		RetrieveItem();
		break;
	case 3:
		DeleteItem();
		break;
	case 4:
		getLength();
		break;
	case 9:
		init();
		break;
	case 0:
		exit();
		break;
	default:
		validation();
		break;
	}
}

template <class itemType>
void llSorted<itemType>::printList()
{
	cout << "List: ";
	// memory issue if list is empty
	if (!(isEmpty()))
	{
		cur = head;
		while (cur != tail)
		{
			cout << cur->data;
			if (cur->next != tail)
				cout << ", ";
			cur = cur->next;
		}
	}
}

template <class itemType>
bool llSorted<itemType>::isFull()
{
	return (length == MAX_SIZE);
}

template <class itemType>
bool llSorted<itemType>::isEmpty()
{
	return (length == 0);
}

template <class itemType>
void llSorted<itemType>::InsertItem()
{
	// Check to see if the list is full
	if(isFull())
	{
		cout << "List is Full!\n" << endl;
		init();
	}
	// List is not full, ask user for value and insert sorted
	else
	{
		usrVal(0);
		// if list is empty, just insert it right after head
		if (isEmpty())
		{
			length++;
			cur->data = value;
			cur->next = NULL;
			tail = cur->next;
			cout << endl;
			init();
		}
		else
		{
			// Traverse the list til next is > the value
			cur = head->next;
			inserted = false;
			while (cur != tail)
			{
				if (value > cur->data)
				{
					cur = cur->next;
				}
				else
				{
					cur = new node;
					cur->data = value;
					inserted = true;
					length++;
					break;
				}
			}
			if (!inserted)
			{
				cur = new node;
				cur->data = value;
				cur->next = NULL;
				tail = cur->next;
				length++;
			}
			cout << endl;
			init();
		}
	}
}

template <class itemType>
void llSorted<itemType>::RetrieveItem()
{
	// Check to see if the list is empty
	if(isEmpty())
	{
		cout << "List is empty!\n" << endl;
		init();
	}
	// List is not empty, ask user for value to find
	else
	{
		usrVal(1);
		// Traverse the list until tail is hit
		cur = head;
		index = 0;
		while (cur != tail)
		{
			if (cur->data == value)
			{
				found++;
				cout << "  Found! Properties of '" << cur->data << "':" << endl;
				cout << "  Address:\t\t\t" << &cur->data << endl;
				cout << "  Index:\t\t\t" << index << endl;
				if (cur->next != tail)
					cout << "  Next Address & Value:\t\t" << &cur->next << " = " << cur->next->data << endl;
				cur = cur->next;
			}
			else
				cur = cur->next;
			index++;
		}
		if(!found)
			cout << "Value does not exist!\n";
		cout << endl;
		init();
	}
}

template <class itemType>
void llSorted<itemType>::DeleteItem()
{
	// Check if list is empty
	if (isEmpty())
	{
		cout << "List is empty!" << endl;
		init();
	}
	// List is not empty, ask user for value and "delete" item
	else
	{
		usrVal(2);
		// traverse the list until you find the value
		cur = head;
		while(cur->next != tail)
		{
			// check if cur->next contains the value
			if(cur->next->data == value)
			{
				found++;
				length--;
				cur->next = cur->next->next;
			}
			else
				cur = cur->next;
		}
		if(!(found))
			cout << "Value does not exist!\n" << endl;
		cout << endl;
		init();
	}
}

template <class itemType>
void llSorted<itemType>::getLength()
{
	// offset by -1 due to NULL head
	cout << "Maximum number of items list can hold:\t" << MAX_SIZE - 1 << endl;
	cout << "Currently stored items:\t\t\t" << length - 1 << endl;
	cout << "Last selected index:\t\t\t";
	if (index == 0)
		cout << "None" << endl;
	else
		cout << index - 1 << endl;
	cout << endl;
	init();
}

template <class itemType>
void llSorted<itemType>::usrVal(int val)
{
	cout << "What integer would you like to ";
	if (val == 0)
		cout << "insert? ";
	else if (val == 1)
		cout << "retrieve? ";
	else
		cout << "delete? ";
	while (!(cin >> value))
	{
		cout << "Please enter only integer digits: ";
		cin.clear();
		cin.ignore(1000, 10);
	}
	// reset found to 0
	found = 0;
}

template <class itemType>
void llSorted<itemType>::validation()
{
	cout << "Invalid Command. Please try again.\n" << endl;
	init();
}

template <class itemType>
int llSorted<itemType>::exit()
{
	cout << "Good bye.";
	return 0;
}

template class llSorted<int>;
template class llSorted<char>;
template class llSorted<float>;
//template class llSorted<std::string>;

Open in new window

Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
In .cpp line 154:
cur->data = value;

Looks like a type mismatch.
But what potential problem do you see where it "works" for, say, double?

Author

Commented:
Constructor also has to be re-written since comparison of strings and integers are completely different. How would I go about making a special set of instructions only if the type is string?
Become a Microsoft Certified Solutions Expert

This course teaches how to install and configure Windows Server 2012 R2.  It is the first step on your path to becoming a Microsoft Certified Solutions Expert (MCSE).

Author

Commented:
For double and float, if the value is int, then it'll truncate, so that needs to be changed to itemType as well (which I did). Also, at initialization of the list, all items in the list will be integers since rand() is of int type, but what if I typecast? Will it make a difference?
When creating a template, the purpose is to provide a stable product that does not have to be modified for every data type being used. If you didn't write a linked list, but were, instead, a user, then you would not expect the linked list product to initialize data for you (especially not randomly). If you wanted to put random data in the list (say for number types), then you might do that in your test driver, and then insert the nodes from the driver into the list.

Getting a string from a rand() is a matter of mapping random numbers to chars. For example, 0..25 could be 'A'-'Z'; 26 could be 'a', etc.

For things, like rand(), that may make no sense for string (or other data types), then you should think about making a template function to specialize the class template. I'll be back tonight. Others can certainly continue assisting in the meantime.

In the constructor is:
// sort the list
I guess this is what you mean by "since comparison of strings and integers are completely different"
You can specify here what exactly the sort order should be, and we can help make it work. But, again, when I think of a constructor for a linked list, my immediate thought is that the list is empty (unless you define constructors that allow externally created data to be included as arguments).

Take a look at the this list's api and see whether you would like to pattern your design after some of their approaches.
     http://www.cplusplus.com/reference/stl/list/



You have made too many assumptions about the type itemType in your code. It's seemingly hard coded to work with ints, yet you expect it to be able to take any data type you throw at it including strings?


head->data = rand() % 101 ; // assigning an int to type itemType ?
cur->data = rand() % 101; // assigning an int to type itemType ?
cur->data = value; // assigning an int to type itemType ?

For example:
std::string data = 3; // this is not valid c++

trinitrotolueneDirector - Software Engineering

Commented:
zenoture :  any specific reason why you do not want to use STL? looks to me you are re-inventing the wheel here. If its for academic purposes this should be fine but for production level code it pays to use a library which has been tested over time

Author

Commented:
@trinitrotoluene

Not allowed to use STL. This is an academic exercise to show the usage of templates and understand how they work.

@davesgonebananas

I understand what are are saying, and I made it clear in my previous posts that I know ints and strings will need to handled differently. My question now is if there is a way to use templates with a conditional statement. For example, if the template is of type int, run the regular code the way it is as it will work for ints, chars, floats and doubles. If the the template is of type string, run a special case string function to do the same basic concept.

@phoffric

I was actually thinking the same thing. Maybe it would be best if I moved the list generation and sorting into a separate function which does what it is supposed to do based on the type. Again, since STLs are not allowed, I can take concepts of STL but I can't actually use the STL itself.

So now that the question is clear, how would I go about truly making this sorted circular 2-way linked list work for any datatype provided? If I do special cases for each type, I might as well just write a function for each one separately... So where do I go from here?
>> a way to use templates with a conditional statement
Here is some pseudo-code that represents what you are asking (section 35.7):
    http://www.parashift.com/c++-faq-lite/templates.html#faq-35.7
Read up to section 35.9

>> (1) how would I go about truly making this sorted circular 2-way linked list work
>> (2) for any data type provided?
Given that doing (1) requires some care and (2) working with templates can be tricky (as you have seen), I recommend that (1) be done first. That is design your api for, say, an int, choosing methods, say, based on existing STL methods. That would be a C++ design question if you need assistance.

Then implement your design.  If you need assistance, then that would be a C++ coding question.

Then, convert your working implementation to a template as you have done in your OP with the understanding that string will still need some work. Post this result here, and we try to help you with problems.

Just wondering.. What is the deadline for completion? Do you have to hand in intermediate steps (e.g., design, implementation, conversion to template, get string to work)? Depending upon the deadline, your time available, and your desire to learn new things, we can advise accordingly, so as not to get yourself too deep. Do you need to be able to include an arbitrary data type (e.g., your own class definition)?

Author

Commented:
>>Just wondering.. What is the deadline for completion? Do you have to hand in intermediate steps >>(e.g., design, implementation, conversion to template, get string to work)? Depending upon the >>deadline, your time available, and your desire to learn new things, we can advise accordingly, so as >>not to get yourself too deep. Do you need to be able to include an arbitrary data type (e.g., your own >>class definition)?

Was actually due yesterday (10/21) but my professor is lenient and would rather have good, working, "beautiful" code rather than something hacked together. I actually enjoy learning about the intricacies of the code, as I used to be a PHP developer a while ago (not knowing basic programming skills), but now have a much better understanding of everything due to these exercises, so I always try to milk it as much as I can. As for the steps, it needs to be turned in like a complete program, no steps, and only the following datatypes:
int, char, float, double, and string
Anything else is optional. There is no extra credit for going above and beyond the requirements, but the deeper understanding of what's going on is more worth it to me.

Author

Commented:
Hoping to complete this by Sunday night however, as there are other exercises being assigned, and I don't want to fall too much behind.
You need to get rid of all the int specific code out of your generic class because it simply doesn't belong there.  Your generic class should contain only a working linked list.  You should put int specific/test code in a separate harness class.  If you feel the test code needs to be in the template'd class, you can create a template specialisation for .
// template specialisation for int type.
template <>
class llSorted<int> {

... int specific stuff goes in this class

}

Open in new window

>> "beautiful" code rather than something hacked together
Then can you get an extra extension. Before "beautiful" code can be created, I think you need a better design (doesn't have to be beautiful, but at least adequate from a user's perspective as well as a designer's). I think two Sundays from now will give you the time. If you ask multiple short questions that are somewhat independent of each other, then you will get more parallel processing from multiple experts to keep you going 24x7. We should just focus on string, and forget the user defined classes until after you meet your deadline.

Could you explain exactly the problem you are facing with the string? What behavior are you getting that you do not like? What behavior do you expect?

If this Sunday is the absolute deadline, let us know what you want to do in light of our comments from me, davesgoneba…, and trinitrotoluene.
I would take everything a step back and try to clean your list from code that does not belong there (like said a couple of times before).
Once you have done that, those problems with int/double/strings incompatibilities will go away, since the remaining code will be generalized.

So lets look at the member-functions of your list:

  isFull -> makes no sense, a list has an open capactiy by definition

Then there are a lot of utility functions, that dont belong to a general list.
The basic operations on a list are those:


  void Init();
  void Deinit();
  bool IsEmpty() const;
  void InsertItem(const itemType &item);
  void DeleteItem(const itemType &item);
  bool FindItem(const itemType &item) const;
  void getLength();  -> wrong name, better: GetItemCount()


Start to implement those functions cleanly, make sure they work as expected and remove all the rest.
Use always the same style for your function names, either capital letters on the beginning or not.

Your professor will be more happy with less stuff that is working and clean than lots of cluttered code of funny things that dont work and dont belong into the list.

Focus on the basics first, make them work, if time is left then move to the higher level.

ike
I agree that taking a step back is valuable. I'd recommend trying to use method names in the STL list link provided earlier. In that way you are getting used to nomenclature that you will need to know later.

Author

Commented:
Ok, the code was modified using typeid to execute different code based on the type. It works for chars, floats, ints, and doubles, but once the last line (template class llSorted<std::string>;) is uncommented, the errors start to roll in. At this point all I want is to be able to use the code I have with as minimal change as possible to work with strings. With the typeid's in place, it shouldn't really care if bool operations are happening since that code will not be executed as a string.

I don't mind doing template specialization for stings, but doesn't defeat the purpose of a function that can handle any datatype? Why would someone template a function if it just has to be re-written all over again for a different datatype?

Errors:
1>------ Build started: Project: Templetized sorted 2-way circular linked list, Configuration: Debug Win32 ------
1>  stdafx.cpp
1>  llSorted.cpp
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(40): warning C4244: '=' : conversion from 'int' to 'float', possible loss of data
1>          f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(20) : while compiling class template member function 'void llSorted<itemType>::genList(void)'
1>          with
1>          [
1>              itemType=float
1>          ]
1>          f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(368) : see reference to class template instantiation 'llSorted<itemType>' being compiled
1>          with
1>          [
1>              itemType=float
1>          ]
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(46): warning C4244: '=' : conversion from 'int' to 'float', possible loss of data
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(11): error C2593: 'operator =' is ambiguous
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\xstring(772): could be 'std::basic_string<_Elem,_Traits,_Ax> &std::basic_string<_Elem,_Traits,_Ax>::operator =(_Elem)'
1>          with
1>          [
1>              _Elem=char,
1>              _Traits=std::char_traits<char>,
1>              _Ax=std::allocator<char>
1>          ]
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\xstring(767): or       'std::basic_string<_Elem,_Traits,_Ax> &std::basic_string<_Elem,_Traits,_Ax>::operator =(const _Elem *)'
1>          with
1>          [
1>              _Elem=char,
1>              _Traits=std::char_traits<char>,
1>              _Ax=std::allocator<char>
1>          ]
1>          while trying to match the argument list '(std::string, int)'
1>          f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(5) : while compiling class template member function 'llSorted<itemType>::llSorted(void)'
1>          with
1>          [
1>              itemType=std::string
1>          ]
1>          f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(370) : see reference to class template instantiation 'llSorted<itemType>' being compiled
1>          with
1>          [
1>              itemType=std::string
1>          ]
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(26): error C2593: 'operator =' is ambiguous
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\xstring(772): could be 'std::basic_string<_Elem,_Traits,_Ax> &std::basic_string<_Elem,_Traits,_Ax>::operator =(_Elem)'
1>          with
1>          [
1>              _Elem=char,
1>              _Traits=std::char_traits<char>,
1>              _Ax=std::allocator<char>
1>          ]
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\xstring(767): or       'std::basic_string<_Elem,_Traits,_Ax> &std::basic_string<_Elem,_Traits,_Ax>::operator =(const _Elem *)'
1>          with
1>          [
1>              _Elem=char,
1>              _Traits=std::char_traits<char>,
1>              _Ax=std::allocator<char>
1>          ]
1>          while trying to match the argument list '(std::string, int)'
1>          f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(20) : while compiling class template member function 'void llSorted<itemType>::genList(void)'
1>          with
1>          [
1>              itemType=std::string
1>          ]
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem *)' : could not deduce template argument for 'const _Elem *' from 'int'
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\string(243) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const _Elem *,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const _Elem *' from 'std::string'
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\string(233) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'int'
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\string(223) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::string'
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1356) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::string'
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1356) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::string'
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1356) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::string'
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1179) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::string'
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1179) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::string'
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1179) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'std::string'
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\utility(318) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'std::string'
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\utility(318) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'std::string'
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\utility(318) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2676: binary '<' : 'std::string' does not define this operator or a conversion to a type acceptable to the predefined operator
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): fatal error C1903: unable to recover from previous error(s); stopping compilation
1>  Generating Code...
1>  Skipping... (no relevant changes detected)
1>  Lab7.cpp
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

#include "stdafx.h"

template <class itemType>
llSorted<itemType>::llSorted()
{
	srand((unsigned int)time(0));

	head = NULL;
	tail = NULL;
	cur = NULL;
	temp = NULL;
	MAX_SIZE = 10 + 1;
	length = rand() % 10 + 1;
	cmd = 0;
	genList();
}

template <class itemType>
void llSorted<itemType>::genList()
{
	for (int i = 0; i < length; i++)
	{
		if (head == NULL)
		{
			head = new node;
			head->data = NULL;
			head->next = new node;
			head->prev = NULL;
			cur = head->next;
			cur->prev = head;
		}
		else
		{
			if (typeid(itemType) != typeid(std::string))
			{
				// if itemType is char, generate new number between A - z
				if (typeid(itemType) == typeid(char))
				{
					while (temp < 65)
						temp = rand() % 123;
					cur->data = temp;
					temp = 0;
				}
				// if itemType is anything but char, just generate a random int
				else
					cur->data = rand() % 101;
				// if this is the last item on the list, set it to head
				if (i == (length-1))
				{
					cur->next = head;
					head->prev = cur;
				}
				else
				{
					cur->next = new node;
					cur->next->prev = cur;
					cur = cur->next;
				}
			}
			else
			{
				// if IS string
			}
		}
	}
	sortList();
}

template <class itemType>
void llSorted<itemType>::sortList()
{
	if (!isEmpty())
	{
		if (typeid(itemType) != typeid(std::string))
		{
			cur = head->next;
			for (int i = 0; i < length; i++)
			{
				for (int j = 0; j < length; j++)
				{
					if (cur->prev->data > cur->data)
					{
						temp = cur->data;
						cur->data = cur->prev->data;
						cur->prev->data = temp;
						cur->prev->next = cur;
					}

					if (cur->next != head)
					{
						cur = cur->next;
					}
					else
						break;
				}
				cur = head->next;
			}
		}
		else
		{
			// if IS string
		}
	}
}

template <class itemType>
void llSorted<itemType>::init()
{
	printList();
	cout << "\nAvailable Commands:\n  1. Insert Item\n  2. Retrieve Item\n  3. Delete Item\n  4. List Details\n  9. Select Different Implementation\n  0. Exit\n\nCommand: ";
	while(!(cin >> cmd))
	{
		cout << "Please enter only the number associated with the command\nCommand: ";
		cin.clear();
		cin.ignore(1000, 10);
	}

	switch (cmd)
	{
	case 1:
		InsertItem();
		break;
	case 2:
		RetrieveItem();
		break;
	case 3:
		DeleteItem();
		break;
	case 4:
		getLength();
		break;
	case 9:
		init();
		break;
	case 0:
		exit();
		break;
	default:
		validation();
		break;
	}
}

template <class itemType>
void llSorted<itemType>::printList()
{
	cout << "List: ";
	// memory issue if list is empty
	if (!(isEmpty()))
	{
		cur = head->next;
		while (cur != head)
		{
			cout << cur->data;
			if (cur->next != head)
				cout << ", ";
			cur = cur->next;
		}
	}
}

template <class itemType>
bool llSorted<itemType>::isFull()
{
	return (length == MAX_SIZE);
}

template <class itemType>
bool llSorted<itemType>::isEmpty()
{
	return (length == 1);
}

template <class itemType>
void llSorted<itemType>::InsertItem()
{
	// Check to see if the list is full
	if(isFull())
	{
		cout << "List is Full!\n" << endl;
		init();
	}
	// List is not full, ask user for value and insert sorted
	else
	{
		usrVal(0);
		// if list is empty, just insert it right after head
		if (isEmpty())
		{
			length++;
			head->next = new node;
			cur = head->next;
			cur->data = value;
			cur->prev = head;
			cur->next = head;
			head->prev = cur;
			cout << endl;
			init();
		}
		else
		{
			if (typeid(itemType) != typeid(std::string))
			{
				// Traverse the list til next is > the value
				cur = head->next;
				inserted = false;
				while (cur != head)
				{
					if (value > cur->data)
					{
						cur = cur->next;
					}
					else
					{
						tempNode = new node;
						tempNode->data = value;
						tempNode->next = cur;
						tempNode->prev = cur->prev;
						cur->prev->next = tempNode;
						cur->prev = tempNode;
						inserted = true;
						length++;
						break;
					}
				}
				if (!inserted)
				{
					tempNode = new node;
					tempNode->data = value;
					tempNode->next = head;
					tempNode->prev = head->prev;
					head->prev->next = tempNode;
					head->prev = tempNode;
					length++;
				}
				cout << endl;
				init();
			}
			else
			{
				// if IS string
			}
		}
	}
}

template <class itemType>
void llSorted<itemType>::RetrieveItem()
{
	// Check to see if the list is empty
	if(isEmpty())
	{
		cout << "List is empty!\n" << endl;
		init();
	}
	// List is not empty, ask user for value to find
	else
	{
		usrVal(1);
		// Traverse the list until tail is hit
		cur = head->next;
		while (cur != head)
		{
			if (cur->data == value)
			{
				found++;
				cout << "  Found! Properties of '" << cur->data << "':" << endl;
				cout << "  Address:\t\t\t" << &cur->data << endl;
				cout << "  Prev Address & Value:\t\t" << &cur->prev << " = " << cur->prev->data << endl;
				cout << "  Next Address & Value:\t\t" << &cur->next << " = " << cur->next->data << endl;
				cur = cur->next;
			}
			else
				cur = cur->next;
		}
		if(!found)
			cout << "Value does not exist!\n";
		cout << endl;
		init();
	}
}

template <class itemType>
void llSorted<itemType>::DeleteItem()
{
	// Check if list is empty
	if (isEmpty())
	{
		cout << "List is empty!" << endl;
		init();
	}
	// List is not empty, ask user for value and delete item
	else
	{
		usrVal(2);
		// traverse the list until you find the value
		cur = head->next;
		while(cur != head)
		{
			// check if cur->next contains the value
			if(cur->data == value)
			{
				found++;
				length--;
				cur->prev->next = cur->next;
				cur->next->prev = cur->prev;
				tempNode = cur;
				cur = cur->next;
				delete tempNode;
				break;
			}
			else
				cur = cur->next;
		}
		if(!(found))
			cout << "Value does not exist!\n" << endl;
		cout << endl;
		init();
	}
}

template <class itemType>
void llSorted<itemType>::getLength()
{
	// offset by -1 due to NULL head
	cout << "Maximum number of items list can hold:\t" << MAX_SIZE - 1 << endl;
	cout << "Currently stored items:\t\t\t" << length - 1 << endl;
	cout << endl;
	init();
}

template <class itemType>
void llSorted<itemType>::usrVal(int val)
{
	cout << "What " << typeid(itemType).name() << " would you like to ";
	if (val == 0)
		cout << "insert? ";
	else if (val == 1)
		cout << "retrieve? ";
	else
		cout << "delete? ";
	while (!(cin >> value))
	{
		cout << "Please enter only integer digits: ";
		cin.clear();
		cin.ignore(1000, 10);
	}
	// reset found to 0
	found = 0;
}

template <class itemType>
void llSorted<itemType>::validation()
{
	cout << "Invalid Command. Please try again.\n" << endl;
	init();
}

template <class itemType>
int llSorted<itemType>::exit()
{
	cout << "Good bye.";
	return 0;
}

template class llSorted<int>;
template class llSorted<char>;
template class llSorted<float>;
template class llSorted<double>;
template class llSorted<std::string>;

Open in new window

Looks like your header has changed. What is it?

Try to avoid RTTI if other approaches are available.
Using typeid within the template bodies as a switch statement on the type (using if-else if-else) is difficult.

It would be nice if you responded to the various comments made for general improvement. If you wish to ignore a suggestion, at least explain why so we'll be on the same page. (Or, we may even be able to turn your explanation into a better design.)

======
Lines 37-39:
   if (typeid(itemType) == typeid(char))
   {
        while (temp < 65)
Line 370:
   template class llSorted<std::string>;
======
temp is of type itemType which in line 370, you are asking for a string.
So line 39 is asking: if the string value in temp is less than 65, then...
Is that what you intended?

In http:#33955382 I provided a link showing funky non-C++ code using a switch statement to handle different types in a template. To repeat:

    http://www.parashift.com/c++-faq-lite/templates.html#faq-35.7
             *** Read up to section 35.9 ***

You also ask:
>> (1) how would I go about truly making this sorted circular 2-way linked list work
>> (2) for any data type provided?

IMO, this project question should be broken up into smaller chunks with each issue delved with separately. It will be easier to follow the threads if you do this. For starters, I suggest that you try to implement the ideas presented in templates.html#faq-35.7 through 35.9 as your own mini project. If you run into problems, post what you have in a new question.

If you still need help with sorted circular 2-way linked lists, I suggest you post a non-template solution in a new question, and indicate the problems you are having.

I noticed that init() calls init(). Why do you want to do that? And if cmd results in another function called, then that function calls init(), which in turn calls init. I suspect that there is a cleaner design.

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial