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]