Archived

This topic is now archived and is closed to further replies.

kulik

My data container

Recommended Posts

kulik    102
I created my simple List class, it works like a data container, but I am not sure if its universal. If it can handle everything. Or how about memory leaks? I didn''t want to use templates, so I used void* pointers. Please look at the code. Any tips / suggestions welcome even critics :-)
// Header below

// pls note that ffSomething is something!

// like ffBool is like bool

// its because of platform compatibility



class FF List  
{
private:
	ffUint nObjs;
	ffVoid* *objs;

	ffUint curpos; // For GetNext()

public:
	List();
	~List();
	ffBool		Add(ffVoid * newObject);
	ffBool		Remove(ffVoid * object);
	ffVoid		Clear(ffBool freeObjects);
	
	ffVoid*		GetFirst();
	ffVoid*		GetNext();
	ffVoid		GetFirst(ffVoid* out);	// For non-explicit cast

	ffVoid		GetNext(ffVoid* out);	// For non-explicit cast


	ffUint		CountObjects();
	ffBool		Contains(ffVoid* object);
	ffBool		IsEmpty();

	ffVoid		LinkWithList(List* l);			ffVoid		AddFromList(List* l);		
};

// Source code below



List::List()
{
	nObjs = 0;
	objs = new ffVoid*[0];
	curpos=0;
}

List::~List()
{
	Clear(ffFALSE);
}

ffBool		List::Add(ffVoid * newObject)
{
    ffVoid* *t;
	// Lets create a temporary linked list

	t = new ffVoid*[nObjs];
	for (ffUint i=0; i<nObjs; i++)
	{
		t[i]=objs[i];
	}
	delete objs; // delete ours

	nObjs++;
	objs = new ffVoid*[nObjs];
	for (ffUint i=0; i<nObjs-1; i++)
	{
		objs[i]=t[i]; // Link our list again

	}
	delete t; // Delete temp list

	objs[nObjs-1]=newObject;
	return ffTRUE;
}

ffBool		List::Remove(ffVoid * object)
{
	ffVoid* *t;
	// Lets create a temporary linked list

	t = new ffVoid*[nObjs];
	for (ffUint i=0; i<nObjs; i++)
	{
		t[i]=objs[i];
	}
	delete objs; // delete ours

	nObjs--;
	objs = new ffVoid*[nObjs];
	ffUint w=0; // write position

	for (ffUint i=0; i<nObjs+1; i++)
	{
		if (t[i]==object)
		{
			// This is it

		}
		else
		{
			objs[w]=t[i];
			w++;
		}
		objs[i]=t[i]; // Link our list again

	}
	delete t; // Delete temp list	

	return ffTRUE;
}

ffVoid		List::Clear(ffBool freeObjects)
{
	if (nObjs==0)
	{
		return; // Nothing to delete

	}
	if (freeObjects)
	{
		for (ffUint i=0; i<nObjs; i++)
		{
			if (objs[i] != NULL)
			{
				delete objs[i];
			}
		}
	}
	delete objs;
	nObjs=0;
}

ffVoid*		List::GetFirst()
{
	if (nObjs==0)
	{
		return 0;
	}
	curpos = 0;
	return objs[0];
}

ffVoid*		List::GetNext()
{
	curpos++;
	if (curpos>nObjs-1)
	{
		return NULL;
	}
	return objs[curpos];
}

ffVoid		List::GetFirst(ffVoid* out)	// For non-explicit cast

{
	out = GetFirst();
}
ffVoid		List::GetNext(ffVoid* out)	// For non-explicit cast

{
	out = GetNext();
}

ffUint		List::CountObjects()
{
	return nObjs;
}

ffBool		List::Contains(ffVoid* object)
{
	for (ffUint i=0; i<nObjs; i++)
	{
		if (objs[i]==object)
		{
			return ffTRUE; // Yeah fe found it

		}
	}
	return ffFALSE; // Try again :-)


}

ffBool		List::IsEmpty()
{
	if (nObjs==0) return ffTRUE;
	return ffFALSE;
}

ffVoid		List::LinkWithList(List* l)		// NOTE: nothing is copyed, its just linked

{
	Clear(ffFALSE);
	ffVoid* item = l->GetFirst();
	while (item != NULL)
	{
		Add(item);
		item = l->GetNext();
	}
}

ffVoid		List::AddFromList(List* l)		// NOTE: nothing is copyed, its just linked

{
	ffVoid* item = l->GetFirst();
	while (item != NULL)
	{
		Add(item);
		item = l->GetNext();
	}
}
Do you think this is universal?? I tried it with a lot of classes, structs, floats, integers,... but I am not sure if it can handle everything. Thx

Share this post


Link to post
Share on other sites
snk_kid    1312
Just a couple of questions

First do you need to write a list? is it for learning?

If it isn't then your will be better off using STL containers.
If it is why didn't you wont to use templates?

How are you implementing your list? with singlely/doublely linked list? Can you show us your declaration of ffUint?

I would declare a list using doublely linked list something like this:



template<class T>
struct list_node {

list_node* predessor, successor;
T element;

};

template<class T>
class list {
public:
list();
list(const list<T>&);
const list<T>& operator=(const list<T>&);

bool is_empty() const;

bool add(const T&);
bool remove(const T&);
void clear();

~list();
private:
list_node<T>* _head;
};



[edited by - snk_kid on May 25, 2004 5:01:34 AM]

Share this post


Link to post
Share on other sites
kulik    102
Its for learning, also I only use classes / procs that I fully understand - its not very funny to debug STL :-)

I am implementing this to a DLL. Its double-linked. Its a dynamically alocated list of pointers that are pointing to something.


typedef unsigned int ffUint;

Share this post


Link to post
Share on other sites
snk_kid    1312
Debugging STL? in theory you shouldn''t ever need to debug a standard libaray if its been implemented correctly, thats the whole point of a standard libaray there meant to be robust and efficent but your learning so its totally fine to make your own, see how it works.

From looking at your code a bit more closely, you don''t need to typedef a bool, its already portable unless your trying to use ints for booleans but still.

It doesn''t look like a normal linked list implementation to me, it looks like your using an array as your implementation which you can do. From your code its hard to tell what your trying to do it looks kind of whacky no offense. Also using void pointers isn''t very type safe and because this is in C++ not C it will get frowned upon.

With linked lists you should start off by making a node type that holds a pointer to its succesor maybe also to it''s predessor and the element to hold. Also if it really is a doublely linked list you wouldn''t need an extra variable that keeps track of the last inserted node as the the head of the list has a link to the front and back. If you implement it like the way i showed previously your code will become more simpler than that and more natural of DLL.

Share this post


Link to post
Share on other sites
kulik    102
Thx

You think that VC++ 6 STL is implemented correctly :-D



[edited by - kulik on May 25, 2004 6:09:21 AM]

Share this post


Link to post
Share on other sites
snk_kid    1312
quote:
Original post by kulik
Thx

You think that VC++ 6 STL is implemented correctly :-D



[edited by - kulik on May 25, 2004 6:09:21 AM]


VC++ 6 is messed up when it comes to C++ standard compliancey is pretty pathetic, i think there imp of STL is also messed up. You can get service packs that will fix most of the issues, the lastest service pack is sp 6 which i think will sort out the STL libs, if not then you can download and use STLport''s imp of STL and use that instead. Didn''t mean to discourage you, its good that your trying to learn i think you should try and do your own version have some sort of reference on data structures & algorithms to help you out

Share this post


Link to post
Share on other sites
snk_kid    1312
i''ve written an example list implementation using a doublely linked list for you to see the workings and how its more simpler than you had it before, just ask if anything don''t make sense:

dll.h:

#ifndef _DOUBLE_LINKED_LIST_
#define _DOUBLE_LINKED_LIST_

#include <new>

template<class T>
struct list_node {

typedef list_node<T>* list_node_ptr;
typedef const list_node<T>* const_list_node_ptr;

list_node(const T& elem = T(), list_node_ptr pre = 0, list_node_ptr suc = 0): element(elem), pred(pre), succ(suc) {}

list_node_ptr pred, succ;
T element;
};

template<class T>
class list {
public:
typedef unsigned int size_type;

list(): _head(0), _size(0) {}

list(list<T>& l): _head(0), _size(l._size) {
list_node<T>* curr = l.front();
while(curr != 0) {
this->add_back(curr->element);
curr = curr->succ;
}
}

const list<T>& operator=(const list<T>& l) {

this->clear();

_size = l.size();

list_node<T>* curr = l.front();

while(curr != 0) {
this->add_back(curr->element);
curr = curr->succ;
}
return *this;
}

const bool is_empty() const { return (_size == 0); }

const bool add_front(const T& new_elem) {
try {
list_node<T>* curr = new list_node<T>(new_elem);

++_size;

if(_head == 0) {
_head = new list_node<T>();
_head->succ = _head->pred = curr; //front & back point to the first node

} else {
curr->succ = _head->succ;
_head->succ = curr;
}
return true;
} catch(std::bad_alloc&) {
return false;
}
}

const bool add_back(const T& new_elem) {
try {
list_node<T>* curr = new list_node<T>(new_elem);

++_size;

if(_head == 0) {
_head = new list_node<T>();
_head->succ = _head->pred = curr; //front & back point to the first node

} else {
_head->pred->succ = curr;
curr->pred = _head->pred;
_head->pred = curr;
}

return true;
} catch(std::bad_alloc&) {
return false;
}
}

const bool remove(const T& old_elem) {
if(_head != 0) {
list_node<T>* curr = _head->succ;

while(curr != 0) {
if(curr->element == old_elem) {
curr->pred->succ = curr->succ;
curr->succ->pred = curr->pred;
delete curr;

--_size;

return true;
} else {
curr = curr->succ;
}
}
return false;
} else
return false;
}

const bool contains(const T& key) const {
if(_head != 0) {
list_node<T>* curr = _head->succ;

while(curr != 0) {
if(curr->element == key) {
return true;
} else {
curr = curr->succ;
}
}
return false;
} else
return false;
}

const size_type size() const { return _size; }

typename list_node<T>::const_list_node_ptr& front() const {
return _head->succ;
}

typename list_node<T>::list_node_ptr& front() {
return _head->succ;
}

typename list_node<T>::const_list_node_ptr& back() const {
return _head->pred;
}

typename list_node<T>::list_node_ptr& back() {
return _head->pred;
}

void clear() {
if(_head != 0) {
list_node<T>* curr = _head->succ;

while(curr != 0) {
if(curr->pred != 0)
delete curr->pred;
--_size;
curr = curr->succ;
}

if(curr != 0)
delete curr;

delete _head;
_head = 0;
}
}

~list() {
clear();
}

private:
size_type _size;
list_node<T>* _head;
};
#endif



and driver program:

#include "dll.h"
#include <cstdlib>
#include <iostream>

template<class T>
void print_list(list<T>&);

int main() {

list<int> my_list;

my_list.add_back(10);
my_list.add_back(33);
my_list.add_back(43);

my_list.remove(33);

print_list(my_list);

std::cout << my_list.size() << std::endl;

my_list.clear();

std::cout << my_list.size() << std::endl;

my_list.add_back(33);
my_list.add_front(44);
my_list.add_front(55);
my_list.add_back(99);

print_list(my_list);

list<int> my_other_list(my_list);

list<int> my_other_list2 = my_other_list;

print_list(my_other_list);
print_list(my_other_list2);

std::cout << std::boolalpha << my_other_list2.contains(99) << std::endl;

std::system("pause");
return EXIT_SUCCESS;
}

template<class T>
void print_list(list<T>& my_list) {
std::cout << ''\n'';

for(list_node<int>* itr = my_list.front();
itr != 0;
itr = itr->succ)
std::cout << itr->element << ''\n'';
}

Share this post


Link to post
Share on other sites