Generic Linked List: need help...

Thanks a lot Anon Poster! You really helped out a lot, and that node inheritance example is EXACTLY what I need, thank you sooo much

You can inheritate your base list class. That''ll make cleaner code.

.lick

quote:

---

Original post by Pipo DeClown
You can inheritate your base list class. That''ll make cleaner code.

---

Hey thanks for the advice, but why would I need to derive from my List class? I fully understand the need to derive from a Node class, but deriving from the list class?!?! (I don''t get it) How would it help? Maybe someone could give a little example...

Bump!

Could someone please explain the need to inherit from a list class as Pipo has said...

[edited by - chacha8 on July 21, 2003 9:34:35 AM]

You want a list implementation? here''s on in C! hehe yes it''s mine, and yes, I know, it''s beautiful!

typedef struct sList
{
void *pvData;
struct slist *pNext;
} tList;

tList;

// Loops through the passed in list List, starting at 0 using Index, 

//returning the type Type and Assigning it to Variable

#define LOOP_LIST(Index, Variable, Type, List)  for (Index = 0;	(Variable = (Type *)GetNthElement(List, Index)) != NULL; Index++)


/**********************************************************
*
*	CreateNode()
*
*	Takes the pointer for the data, and the size of the data
* 	and returns a pointer to list.
*
***********************************************************/
tList *CreateNode(void *pvNewData, int Size)
{
	tList *pList;

	// make room for List...

	pList = (tList *)malloc(sizeof(tList));

	// then make room for Data (using size passed in)

	pList->pvData = (void *)malloc(Size);
	pList->Next = NULL;

	// then copy the data passed in into List data

	memcpy(pList->pvData, pvNewData, Size);

	return (pList);
}

/**********************************************************
*
*	AddToList()
*
* 	Adds the passed in List Ptr to the passed in list and returns
*	the result.
*
***********************************************************/
tList *AddToList(tList *pList, tList *pNode)
{
	tList *TempPtr;

	// if the list is empty, make node New Head

	if (pList == NULL)
	{
		pList = pNode;
	}
	else
	{		
		TempPtr = pList;

		// go to end of list and...

		while(TempPtr->Next != NULL)
		{
			TempPtr = TempPtr->Next;
		}

		// put our node at end of list

		TempPtr->Next = pNode;
	}

	return (pList);
}

/**********************************************************
*
*	GetNthElement()
*
* 	Returns the Nth data element given in the passed in list
*
***********************************************************/
void *GetNthElement(tList *pList, ULONG ulElement)
{
	register tList *pTemp = pList;
	register ULONG ulIndex;

	// loop through until we''re at end, or we''re at the one we want

	for (ulIndex = 0; (pTemp != NULL) && (ulIndex < ulElement); ulIndex++)
	{
		pTemp = pTemp->Next;
	}

	if (pTemp == NULL)
		return (NULL);
	else
		return (pTemp->pvData);
}


/**********************************************************
*
*	RemoveElement()
*
*   Remove an Element from a linked list
*
***********************************************************/
tList *RemoveElement(tList *pList, void *pvRemove)
{
	tList *pTemp = pList;
	tList *pTemp2;

	if (pList == NULL)
		return (NULL);
	
	// if the 1st node is the one we want, move Head to Next, and remove it

	if (pTemp->pvData == pvRemove)
	{
		pList = pList->Next;		
		free(pTemp->pvData);
		free(pTemp);
	}
	else
	{
		// while we''re not at end of list, and we haven''t found our node, go to next

		while((pTemp->Next != NULL) && (pTemp->Next->pvData != pvRemove))
		{
			pTemp = pTemp->Next;
		}

		// if we didn''t find it, return NULL

		if (pTemp->Next == NULL)
			return (NULL);

		// otherwise, mark the Next node (node to be deleted), make Next

		// point to Next''s Next, and remove old Next (the one we Marked (pTemp2))

		pTemp2 = pTemp->Next;
		pTemp->Next = pTemp->Next->Next;
		free(pTemp2->pvData);
		free(pTemp2);
	}

	return (pList);
}

/**********************************************************
*
*	FreeList()
*
*   Frees all the memory from the list
*
***********************************************************/
void FreeList(tList *pListToFree)
{
	void *pvFree;

	if (pListToFree == NULL)
		return;

	// go through each element, removing the head of the list until empty

	while(pvFree = GetNthElement(pListToFree, 0))
	{
		pListToFree = RemoveElement(pListToFree, pvFree);
	}

}
    

You don''t "need" to inherit a linked list class.

However, a list class that also has some functions for drawing Is-A linked list class. That pretty much tells me that inheritance is the way to go.

Slight nit pick- You said you inherit your node class. Actually, you don''t (and you didn''t in your code). You just USE a node class in your linked list class. Apples and oranges FYI.

Also, you might consider encapsulating your node class inside your linked list class (since its the only thing thats gonna use it, and use it internally too). Theres no need for it to be in global scope. It wouldnt need to be a templated node class/struct then either.

To sum up.
Make an all purpose list class (or use std::list)
Derive specialized lists classes (for drawing or whatever from the all purpose one, if it Is-A linked list).

I.E

template <class Object>
class list; // all purpose list class can be std::list


template <class Object>
class drawing_list : public list<Object> // can easily be std::list

{
public:
// rest of drawing_lists members (ctors etc)


void draw_all (void) { ... }
void draw (int index) { ... }
};

I was bored, but had some fun writing this

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <functional>


namespace drawlist
{

template <class Object>
class list : private std::list<Object>
{
private:
	typedef std::list<Object> list_type;
public:
	typedef list_type::allocator_type allocator_type;  
	using list_type::iterator;			using list_type::const_iterator; 
	using list_type::const_reference;	using list_type::const_reverse_iterator; 
	using list_type::reverse_iterator; 	using list_type::difference_type;
	using list_type::max_size;			using list_type::reference;
	using list_type::value_type;		using list_type::assign;
	using list_type::back;				using list_type::begin; 
	using list_type::clear;				using list_type::empty; 
	using list_type::end;				using list_type::erase; 
	using list_type::front;				using list_type::get_allocator; 
	using list_type::insert;			using list_type::merge; 
	using list_type::pop_back;			using list_type::pop_front; 
	using list_type::push_back;			using list_type::push_front; 
	using list_type::rbegin;			using list_type::remove; 
	using list_type::remove_if;			using list_type::rend; 
	using list_type::resize;			using list_type::reverse; 
	using list_type::size;				using list_type::size_type; 
	using list_type::sort;				using list_type::splice; 
	using list_type::swap;				using list_type::unique;

	explicit list () : std::list<Object>(){}
	explicit list(size_t num, const Object& val = Object())
		: std::list<Object>(num,val)
	{}
	explicit list(const drawlist::list<Object>& ob)
		: std::list<Object>(ob)
	{}

	template <class iter>
	explicit list (iter start, iter end)
	{
		insert (begin(), start, end); // cool beans

	}
	~list ()
	{
		// does not need to do anything 	

	}
	void draw (const iterator& p)
	{
		p->draw();
	}
	void checked_draw (const iterator& p)
	{
		if (p != end())
			p->draw();
	}
	void draw (iterator start, iterator end) // by value

	{
		for (;start != end; start++)
			draw(start);
	}
};
} // end namespace drawlist


class Asteriod
{
public:
	Asteriod (int x_axis = 0, int y_axis = 0) : x_(x_axis), y_(y_axis)	{}
	void draw (void)	
	{
		std::cout << "Drawing Asteriod! *("
			<< x_ << '','' << y_ << '')''<< std::endl; 	
	}
	int get_x (void) const { return x_; }
	int get_y (void) const { return y_; }

	friend bool operator == (const Asteriod&, const Asteriod&);
	friend bool operator != (const Asteriod& rhs1, const Asteriod& rhs2);
private:
	int x_, y_;
};
bool operator == (const Asteriod& rhs1, const Asteriod& rhs2)
{
	if (rhs1.get_x() == rhs2.get_x() && rhs1.get_y() == rhs2.get_y())
		return true;
	return false;
}

bool operator != (const Asteriod& rhs1, const Asteriod& rhs2) {	return !(rhs1 == rhs2);}



int main ()
{
	std::vector<Asteriod> b;
	b.push_back(Asteriod(1, 3));
	b.push_back(Asteriod(3, 32));
	b.push_back(Asteriod(45,3));
	b.push_back(Asteriod(142, 49));

	drawlist::list<Asteriod> a(b.begin(),b.end());
	// we see lists constructor in action taking a iterator range from a vector =]

	// something not possible in VC 6 with original STL implementaion.

	// kinda cool. making use of member templates in dervived class

	// Underneath the interface the shotty implemention is still there however *g*


	// find a specific asteriod

	drawlist::list<Asteriod>::iterator p = std::find (a.begin(), a.end(), Asteriod(3,32));

	a.checked_draw(p); // draw it if its valid

	a.draw (p); // just draw it.. who cares if its invalid :)


	std::cout << std::endl;
	a.draw(a.begin(), a.end()); // Draw them all using the full range

		
	return 0;
};

I used private inheritance because std::list doesnt have virtual draw functions or a virtual destructor. It stops anyone from trying to use it polymorphically which might happen in public inheritance.
The using stuff is to make all the memmbers public just like public inheritance does because it has a Is-A relationship.

Why would i bother doing all that? I dunno!

On a final inspection. This was pretty much all worthless.

We could have just defined two templated draw functions in global scope that take generic iterators. We can then use them on all applicable containers with applicaple types.

Such as

template <class iter>
void draw(iter p)
{
	p->draw ();
}

template <class iter>
void draw (iter start, iter end)
{
	for (;start != end; start++)
		draw(start);
}

Anyway, hope i cleared some stuff up and gave you an idea or two.

Ok, well I''ve now completed my list class so everything is fine, and thanks anyway guys.

And to Amnesty:

quote:

---

You said you inherit your node class. Actually, you don''t (and you didn''t in your code)

---

Yes, when I wrote my code in the first post, I hadn''t actually inherited from the Node class, because that''s what my initial question was about...but now I''ve finished it with the inheritance so I''ve no problem now. Just wanted to say, because you made me look a fool. (as if I didn''t know what inheritance was, ahh that''s an insult! ).