Many many bugs

148

Author

September 17, 2004 06:37 AM

Hi everyone ! I was trying to do a little project to show myself what I have learned from programming in C++ up to now. Of course, I couldn't include everything I know from C++ ( I didn't need inheritance nor polymorphism...etc ) but I came up with the idea of doing something that would be a mix between a regular linked list ( Link* next ... ) and std::list but I wrote it in one shot and then compiled so I had a lot of errors! Now I'm almost finished with debugging and I need your help for some bugs that I couldn't find any solution to fix them. Here's the code:

/////////////////////////////////////////////////
// FILE: auto_list.h						   //
// CODER: T i l e x							   //
/////////////////////////////////////////////////

#ifndef _LIST_H_
#define _LIST_H_

#pragma warning(disable: 4018) // warning incompatibility signed/unsigned

#include <iostream>
#include <vector>

typedef unsigned int UINT;

// These values are used to know what type of sort ( greater than or lower than )
// has to be used by the sorting algorithm
const UINT GREATER_THAN = 0;
const UINT LOWER_THAN = 1;

// Display a message if some memory occurs and throw it
class bad_memory_request {
public:
	bad_memory_request(char* errorDescription = "You asked less memory than minimum needed.") {
		std::cout << errorDescription;
	}
};

/* **********************************************
 - class Link
 - it represents a link in a single-linked list
********************************************** */
template<class T>
struct Link {
	T m_Data;
	Link* m_Next;

	Link() {;};
	Link& operator=(Link<T>& copy) {
		m_Data = copy.m_Data;
		return *this;
	}
	Link& operator=(const Link<T>& copy) {
		m_Data = copy.m_Data;
		return *this;
	}

	bool operator==(Link& copy) {
		return (m_Data == copy.m_Data);
	}
};

/* **********************************************
 - class auto_list
 - it a single-linked list
 - it's possible to:
		* add an element at the end of the list
		* add an element at the beginning of the list
		* remove an element at the end of the list
		* remove an element at the beginning of the list
		* remove all elements in the list
		* remove only certain elements in the list
		* sort all elements using 3 sorts ( shell sort, bubble sort and quicksort )
		  using 2 different comparisons ( "greater than" and "lower than" )
	    * eliminate all elements that have the same data and are
		  more than once in the list
	    * retrieve a reference of the first or last occurence of some data
 - supports memory pages
********************************************** */
template<class T>
class auto_list {
protected:
	Link<T>* m_List;
	UINT m_Size, m_Capacity;
public:
	auto_list();
	auto_list(T, UINT nb=1);
	auto_list(const Link<T>);
	auto_list(const Link<T>*);
	auto_list(const auto_list&);
	~auto_list();

	void ReserveMemory(UINT);
	void push_back(T);
	void push_front(T);
	void pop_back();
	void pop_front();
	void clear();
	void erase(UINT start, UINT end);
	void bsort(UINT);				// bubble sort
	void bsort_greater();
	void bsort_lower();
	void qsort(UINT);				// quick sort
	void qsort_greater();
	void qsort_lower();
	void ssort(UINT);				// shell sort
	void ssort_greater();
	void ssort_lower();
	void eliminate_doubles();
	void rearrange();

	Link<T>& first() const;
	Link<T>& last() const;
	Link<T>& find_first(T&) const;
	Link<T>& find_last(T&) const;

	auto_list<T>& operator=(const Link<T>*);
	auto_list<T>& operator=(const auto_list<T>&);
	bool operator==(const Link<T>*) const;
	bool operator!=(const Link<T>*) const;
	Link<T>& operator[](UINT index) const { return m_List[index]; };
	Link<T>*& operator*() { return m_List; };
};

#endif




/////////////////////////////////////////////////
//				IMPLEMENTATION				   //
// Please note that implementation is placed   //
// in the header file because the class uses   //
// templates and "export" isn't standard	   //
/////////////////////////////////////////////////




// Allocate 1 element only to make sure the instance doesn't become a zombie
template<class T>
auto_list<T>::auto_list() : m_Size(0), m_Capacity(1) {
	m_List = new Link<T>[m_Capacity];
}

// Allocate "nb" elements so it's possible to create more than
// 1 instance of the data at a time
template<class T>
auto_list<T>::auto_list(T data, UINT nb=1) {
	m_Size = nb;
	m_Capacity = m_Size * 2;
	m_List = new Link<T>[m_Capacity];
	for(int i = 0;i < nb;++i) {
		m_List.m_Data = data;
		m_List.m_Next = &m_List[i+1];
	}
}

// Copy only 1 link in the list
template<class T>
auto_list<T>::auto_list(const Link<T> element) : m_Size(1), m_Capacity(2) {
	m_List = new Link<T>[m_Size];
	m_List[0] = element;
}

// Copy an array of links into the list
template<class T>
auto_list<T>::auto_list(const Link<T>* list) {
	// FIXME: Find a way to make this constructor work.
}

// Copy constructor, make sure it's possible to assign our 
// object to an object of the same type
template<class T>
auto_list<T>::auto_list(const auto_list& list) {
	m_Size = list.m_Size;
	m_Capacity = list.m_Capacity;
	m_List = new Link<T>[m_Capacity];
	for(int i = 0; i < m_Size; ++i)
		m_List = list.m_List;
}

// Simply delete all allocated memory
template <class T>
auto_list<T>::~auto_list() {
	delete[] m_List;
}

// Reserve memory for "nb" elements in the list
template<class T>
void auto_list<T>::ReserveMemory(UINT nb) {
	if(nb < m_Size)
		throw(bad_memory_request());
	else {
		auto_list copy = *this;
		delete[] m_List;
		m_Capacity = nb;
		m_List = new Link<T>[m_Capacity];
		for(int i = 0; i < m_Size; ++i)
			m_List = copy.m_List;
	}
}

// Push an element at the end of the list
template<class T>
void auto_list<T>::push_back(T data) {
	// Make sure we have more memory than needed
	if(m_Capacity == ++m_Size) {
		// Store the data while we are reallocating memory
		auto_list copy = *this;

		// allocate 2 times more than m_Size memory
		delete[] m_List;
		m_Capacity = m_Size * 2;
		m_List = new Link<T>[m_Capacity];

		// copy back everything
		for(int i = 0; i < m_Size; ++i)
			m_List = copy.m_List;
	}
	// if we have more than 1 link
	if(m_Size > 1)
		// assign the current link as the previous link's next
		m_List[m_Size-2].m_Next = &m_List[m_Size-1];

	// assign the correct values
	m_List[m_Size-1].m_Data = data;
	m_List[m_Size-1].m_Next = NULL;
}

// Push an element at the beginning of the list
template<class T>
void auto_list<T>::push_front(T data) {
	if(m_Capacity == ++m_Size) {
		auto_list copy = *this;
		delete[] m_List;
		m_Capacity = m_Size * 2;
		m_List = new Link<T>[m_Capacity];
		for(int i = 0; i < m_Size; ++i)
			m_List[i+1] = copy.m_List;
	}
	m_List[0].m_Data = data;
	m_List[0].m_Next = &m_List[1];
}

// Remove the last element
template<class T>
void auto_list<T>::pop_back() {
	if(m_Size == 0) {
		throw bad_memory_request();
		return; // FIXME: is that executed ?
	}
	m_List[--m_Size].m_Data = NULL;
	m_List[m_Size-1].m_Next = NULL;
}

// Remove the first element
template<class T>
void auto_list<T>::pop_front() {
	if(m_Size == 0) {
		throw bad_memory_request();
		return; // FIXME: is that executed ?
	}
	m_Size--;
	for(int i = 0; i < m_Size; ++i)
		m_List = m_List[i+1];
	m_List[m_Size].m_Data = NULL;
	m_List[m_Size-1].m_Next = NULL;
}


// Remove all the elements in the list
template<class T>
void auto_list<T>::clear() {
	for(int i = 0; i < m_Size; ++i)
		m_List.m_Data = NULL;
	m_Size = 0;
}

// Remove all elements from "start" to "end"
template<class T>
void auto_list<T>::erase(UINT start, UINT end) {
	if((start > end) && (end >= --m_Size))
		return;
	for(int i = start; i < end; ++i)
		m_List.m_Data = NULL;
	m_Size -= (end - start);
	rearrange();
}

// Find what function to call, greater_than or lower_than
template<class T>
void auto_list<T>::bsort(UINT type) {
	if(type == GREATER_THAN)
		bsort_greater();
	else if(type == LOWER_THAN)
		bsort_lower();
}

// use the greater than algorithm
template<class T>
void auto_list<T>::bsort_greater() {
	for(int i = 0; i < m_Size; ++i) {
		for(int k = 0; k < m_Size; ++k) {
			if(m_List[k].m_Data > m_List.m_Data) {
				Link<T> temp = m_List[k];
				m_List[k] = m_List;
				m_List = temp;
			}
		}
	}
}

template<class T>
void auto_list<T>::bsort_lower() {
	for(int i = 0; i < m_Size; ++i) {
		for(int k = 0; k < m_Size; ++k) {
			if(m_List[k].m_Data < m_List.m_Data) {
				Link<T> temp = m_List[k];
				m_List[k] = m_List;
				m_List = temp;
			}
		}
	}
}

// Find what function to call, greater_than or lower_than
template<class T>
void auto_list<T>::qsort(UINT type) {
	// TODO: Implement me !
}

// use the greater than algorithm
template<class T>
void auto_list<T>::qsort_greater() {
	// TODO: Implement me !
}

template<class T>
void auto_list<T>::qsort_lower() {
	// TODO: Implement me !
}

// Find what function to call, greater_than or lower_than
template<class T>
void auto_list<T>::ssort(UINT type) {
	// TODO: Implement me !
}

// use the greater than algorithm
template<class T>
void auto_list<T>::ssort_greater() {
	// TODO: Implement me !
}

template<class T>
void auto_list<T>::ssort_lower() {
	// TODO: Implement me !
}

// eliminate all elements that are present more than once in the list
template<class T>
void auto_list<T>::eliminate_doubles() {
	if(m_Size > 0) {
		std::vector<T> buffer;
		bool found;
		for(int i = 0; i < m_Size; ++i) {
			found = false;
			for(std::vector<T>::const_iterator j = buffer.begin(); j != buffer.end(); ++j) {
				if(m_List.m_Data == (*j)) {
					m_List.m_Data = 0;
					found = true;
					break;
				}
			}
			if(!found)
				buffer.push_back(m_List.m_Data);
			rearrange();
		}
	}
}

// make sure there are no NULL values between links
template<class T>
void auto_list<T>::rearrange() {
	int null_count = 0;
	for(int i = 0; i < m_Size; ++i) {
		if(m_List.m_Next == NULL) {
			m_List = m_List[i+1];
			if(i > 0)
				m_List[i-1].m_Next = &m_List;
			++null_count;
		}
	}
	m_Size -= null_count;
}

// reference to the first element
template<class T>
Link<T>& auto_list<T>::first() const{
	return m_List[0];
}

// reference to the last element
template<class T>
Link<T>& auto_list<T>::last() const{
	return m_List[m_Size-1];
}

// find the first element that corresponds to "data"
template<class T>
Link<T>& auto_list<T>::find_first(T& data) const{
	for(int i = 0; i < m_Size; ++i)
		if(m_List.m_Data == data)
			return m_List;
	return NULL;
}

// find the last element that corresponds to "data"
template<class T>
Link<T>& auto_list<T>::find_last(T& data) const{
	Link<T> log = NULL;
	for(int i = 0; i < m_Size; ++i)
		if(m_List.m_Data == data)
			log = m_List;
	return log;
}

template<class T>
auto_list<T>& auto_list<T>::operator=(const Link<T>* list) {
	return (m_List = list);
}

template<class T>
auto_list<T>& auto_list<T>::operator=(const auto_list& list) {
	m_Size = list.m_Size;
	m_Capacity = list.m_Capacity;
	if(m_List)
		delete[] m_List;
	m_List = new Link<T>[m_Capacity];
	m_List = list.m_List;
	return *this;
}

template<class T>
bool auto_list<T>::operator==(const Link<T>* list) const{
	for(int i = 0; i < m_iSize; ++i)
		if(list == m_List)
			return true;
	return false;
}

template<class T>
bool auto_list<T>::operator!=(const Link<T>* list) const{
	for(int i = 0; i < m_iSize; ++i)
		if(list != m_List)
			return true;
	return false;
}

Ok sorry I know it's pretty big to put on a forum. 1st known bug: the function rearrange() seems not to do its job correcly. It's supposed to take every Link that has been removed, moved or anything else that is not active anymore and put it at the back of the active elements so that if you have 5 elements and the pop_front(), you won't see 0 being the first value of the list. 2nd known bug: I can't go through the list like a regular linked list. If I use the following code, the program outputs '1' and the it crashes...

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

int main(void) {
	auto_list<int> myList;
	myList.push_back(1);
	myList.push_back(2);
	myList.push_back(2);
	myList.push_back(4);
	myList.eliminate_doubles();
	Link<int>* ptr = &myList[0];
	while(ptr != NULL) {
		std::cout << ptr->m_Data;
		ptr = ptr->m_Next;
	}
	return 0;
}

Well I think that pretty much sums it for now. PS: I know that my the code sucks bad but I'm getting better Thank you guys/girls [Edited by - White Scorpion on September 17, 2004 3:38:47 PM]

darookie

1,441

September 17, 2004 06:47 AM

Quote:Original post by White Scorpion
[...] but I wrote it in one shot and then compiled so I had a lot of errors!

And what did you learn from that?
Never write such a bunch of code in one shot!

I didn't look at all of the code (and I suppose very few people will) but I'll check it and get back when I'm finished (or someone else spots the bug [wink]) because it looks quite interesting.
There are some design issues (e.g. seperating algorithms from data structure like STL does) but it's a good exercise indeed.

White Scorpion

148

Author

September 17, 2004 06:49 AM

I took the exercise from "The C++ Language" by Bjarne Stroustrup and I modified it a bit to make it more challenging. Originally it had only to be a linked list that would auto-deallocate memory but now it's something nearly usefull lol
As for the bugs well I'm working on them but I didn't find anything interesting yet.

White Scorpion

148

Author

September 17, 2004 06:53 AM

PS: If anyone wanted to know, I just fixed find_last() here's the code to it.

// find the last element that corresponds to "data"template<class T>Link<T>& auto_list<T>::find_last(T& data) const{	int last = -1;	for(int i = 0; i < m_Size; ++i)		if(m_List.m_Data == data)			last = i;	return (last == -1) ? NULL : m_List[last];}

darookie

1,441

September 17, 2004 07:02 AM

Well I still didn't look at all the code, but you have some serious bugs that are very obvious.

Your push_back() method does weird things.
After resizing, all your m_Next pointers will be screwed up,
because you copy them from a temporary list on stack without
resetting the m_Next pointers of each element.

You should completely re-design your class (sorry to say that but your approach seems to yield so many issues that it would be easier to rewrite some core functionality).

Some hints:

You use an array to store list elements. So far so good.
But to avoid pointer issues (as with resizing) you should
store indices into that array instead of pointers in your
m_Next members or the Link template.

Keep a free-list for unused indices - this will manage inserts
and gets rid of re-arranging. A free-list is a stack of
indices and very simple to use. You just push any unused indices onto that stack (e.g. on resizing) and pop one when you need a free element. If the stack is empty you need to resize.

I hope you get the idea (if not it's my fault - I'm not so good in explaining such things[rolleyes]),
Pat.

grekster

640

September 17, 2004 07:02 AM

When you post code can you use the [ source ] tags :)

Quote:Original post by BosskIn Soviet Russia, you STFU WITH THOSE LAME JOKES!

Drag0n

186

September 17, 2004 07:15 AM

Uh...I didn't look over all your code, but in rearrange() you might have a bug:

for(int i = 0; i < m_Size; ++i) {	//...		m_List = m_List[i+1];	//...}

Of course, I don't know whether you eliminate the case of having a null pointer at the last element, but if not, this will sooner or later generate an access violation... :)

I like your code, btw. Very readable. I'll go and look for more bugs now... ;)

Cheers,
Drag0n

-----------------------------"Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to build bigger and better idiots. So far, the universe is winning..." -- Rich Cook"...nobody ever accused English pronounciation and spelling of being logical." -- Bjarne Stroustrup"...the war on terror is going badly because, if you where to compare it to WWII, it's like America being attacked by Japan, and responding by invading Brazil." -- Michalson

White Scorpion

148

Author

September 17, 2004 03:50 PM

Well I'm fixing some of the bugs you guys told me but I will keep the same badly-coded structure. Next project I'll code ( probably a simple game ) I will ask help on how to build the structure because it seems to be my 1st biggest problem.

Many many bugs

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Many many bugs

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines