🔒 Locked

double circular linked list problem

Started by chrka Feb 17, 2007 at 11:33 AM 8 replies 1k views

Original Post

Feb 17, 2007 at 11:33 AM


#include <iostream>
#include <fstream>
#include <string>
#include <stdlib.h>




template<class TYPE> class TDoubleLinkedList;
template<class TYPE> class TDoubleLinkedListMember;
template<class TYPE> class TDoubleLinkedListItterator;



template<class TYPE>
class TDoubleLinkedListMember
{
	template<class TYPE>
	friend class TDoubleLinkedList;
	template<class TYPE>
	friend class TDoubleLinkedListItterator;

	TDoubleLinkedList<TYPE> *m_pList;
	TYPE *m_pPrevMember;
	TYPE *m_pNextMember;

public:
	TDoubleLinkedListMember()
	: m_pList(NULL), m_pPrevMember(NULL), m_pNextMember(NULL)
	{}

	~TDoubleLinkedListMember()
	{
		if(m_pList)
			m_pList->Unlink(this);
	}
};









template<class TYPE>
class TDoubleLinkedListItterator
{
	template<class TYPE>
	friend class TDoubleLinkedList;

	TDoubleLinkedList<TYPE> *m_pList;
	TYPE *m_pCurrentMember;
	
	TDoubleLinkedListItterator(TDoubleLinkedList<TYPE> *_pList)
	: m_pList(_pList), m_pCurrentMember(_pList->m_pFirstMember)
	{}

public:
	TYPE* operator ->() { return m_pCurrentMember; }
	operator TYPE*() { return m_pCurrentMember; }
	TYPE* operator++() { m_pCurrentMember = m_pCurrentMember->m_pNextMember; return m_pCurrentMember; }
	TYPE* operator--() { m_pCurrentMember = m_pCurrentMember->m_pPrevMember; return m_pCurrentMember; }
	
	
	void Rewind()
	{
		m_pCurrentMember = m_pList->m_pFirstMember;
	}

	int Valid()
	{	
		
		return m_pCurrentMember->m_pNextMember
				!=m_pList->m_pFirstMember;
	}
};












template<class TYPE>
class TDoubleLinkedList
{
	template<class TYPE>
	friend class TDoubleLinkedListItterator;

	TYPE *m_pFirstMember;
	TYPE *m_pLastMember;
	int m_size;
public:

	TDoubleLinkedList()
	:m_pFirstMember(NULL), m_pLastMember(NULL), m_size(0)
	{}

	int Size()
	{
		return m_size;
	}

	// Lägger till i början av listan
	void Add(TYPE *_pObject)
	{
		LinkLast(_pObject);
		m_size++;

	}


	void LinkLast(TYPE *_pObject)
	{
		if(!_pObject) 
			return;
		
		
		if(m_pFirstMember)
		{
			m_pLastMember->m_pNextMember = _pObject;
			_pObject->m_pPrevMember = m_pLastMember;

			m_pLastMember = _pObject;
			_pObject->m_pNextMember = m_pFirstMember;

			m_pFirstMember->m_pPrevMember = m_pLastMember;
			

		}
		else // ingen nod
		{
			m_pLastMember = _pObject;
			m_pFirstMember = _pObject;



			// Ny nod, därför cirkulär med sig själv.
			_pObject->m_pNextMember = _pObject;
			_pObject->m_pPrevMember = _pObject;
		}


		_pObject->m_pList = this;

	}






	
	void Unlink(TDoubleLinkedListMember<TYPE> *_pObject)
	{
		if(!_pObject)
			return;

		if(!_pObject->m_pList) 
			return;


		if(_pObject->m_pPrevMember)
			_pObject->m_pPrevMember->m_pNextMember = _pObject->m_pNextMember;
		else
			m_pFirstMember = _pObject->m_pNextMember;

		if(_pObject->m_pNextMember)
			_pObject->m_pNextMember->m_pPrevMember = _pObject->m_pPrevMember;



		_pObject->m_pList = NULL;
		_pObject->m_pPrevMember = NULL;
		_pObject->m_pNextMember = NULL;
	}




	
	void DeleteAll()
	{
		while(m_pFirstMember)
			delete m_pFirstMember;
	}

	
	void Swap(TYPE *_pObject1, TYPE *_pObject2)
	{	
		if(!_pObject1 || !_pObject2 || _pObject1 == _pObject2)
			return;

		// Swapa pekare så det underlättar.
		if(_pObject1->m_pPrevMember == _pObject2)
		{
			TYPE *pTempPtr = _pObject1;
			_pObject1 = _pObject2;
			_pObject2 = pTempPtr;
		}

		// byt next och prev pekarna
		if(_pObject1->m_pNextMember == _pObject2)
		{

			TYPE *pTempPtr = _pObject1->m_pPrevMember;
			_pObject1->m_pPrevMember = _pObject2;
			_pObject1->m_pNextMember = _pObject2->m_pNextMember;
			_pObject2->m_pNextMember = _pObject1;
			_pObject2->m_pPrevMember = pTempPtr;
		}
		else
		{

			TYPE *pTempPtr = _pObject2->m_pNextMember;
			_pObject2->m_pNextMember = _pObject1->m_pNextMember;
			_pObject1->m_pNextMember = pTempPtr;

			pTempPtr = _pObject2->m_pPrevMember;
			_pObject2->m_pPrevMember = _pObject1->m_pPrevMember;
			_pObject1->m_pPrevMember = pTempPtr;
		}

		
		if(_pObject1->m_pPrevMember)
			_pObject1->m_pPrevMember->m_pNextMember = _pObject1;
		else
			m_pFirstMember = _pObject1;

		if(_pObject1->m_pNextMember) _pObject1->m_pNextMember->m_pPrevMember = _pObject1;
		
		if(_pObject2->m_pPrevMember)
			_pObject2->m_pPrevMember->m_pNextMember = _pObject2;
		else
			m_pFirstMember = _pObject2;

        if(_pObject2->m_pNextMember) _pObject2->m_pNextMember->m_pPrevMember = _pObject2;
	}

	
	
	TDoubleLinkedListItterator<TYPE> GetItterator() { return TDoubleLinkedListItterator<TYPE>(this); }



	
	void BubbleSort(int (*_pfnCompare)(TYPE*,TYPE*), int Order=1)
	{
		if(Order != -1 && Order != 1) // check for correct order parameter
			return;

		int Done = 0;
		while(!Done)
		{
			Done = 1;

			for(CIntStorageIttr Ittr = g_List.GetItterator(); Ittr->m_pNextMember; ++Ittr)
			{
				if(_pfnCompare(Ittr, Ittr->m_pNextMember) == Order)
				{
					Swap(Ittr, Ittr->m_pNextMember);
					Done = 0;
				}
			}
		}
	}
};









class CIntStorage : public TDoubleLinkedListMember<CIntStorage>
{
public:
	int m_Value;
	CIntStorage(int _Value)
		:m_Value(_Value)
	{}

	static int NormalCompare(CIntStorage *_pObject1, CIntStorage *_pObject2)
	{
		if(_pObject1->m_Value < _pObject2->m_Value)
			return 1;

		if(_pObject1->m_Value > _pObject2->m_Value)
			return -1;

		return 0;
	}
};


typedef TDoubleLinkedListItterator<CIntStorage> CIntStorageIttr;

int main()
{
	TDoubleLinkedList<CIntStorage> list;
	for(int i = 1; i < 6; i++)
		list.Add(new CIntStorage(rand()));



	for(CIntStorageIttr Ittr = list.GetItterator(); Ittr.Valid(); ++Ittr)
		printf(">> %d\n", Ittr->m_Value);

	list.BubbleSort(CIntStorage::NormalCompare);
	CIntStorageIttr Ittr = list.GetItterator();
	for(int i=0; i<list.Size(); i++)
	{
		std::cout << Ittr->m_Value << std::endl;
		++Ittr;
	}




}

Okey. The first problem is the Valid function. I use it to check if I should stop when I itterate through the list. Just want to go from the first node to the last one. But I just get from the first node to the one BEFORE the last node. So if there is 3 nodes, i will just get 2 nodes. The second problem is the BubbleSort algorithm. I have no ide why it doesn't work, I have tryed to just doing a for-loop and a fixed size of what it will sort. But it can't sort anything more then 3 nodes correctly. Please help me, it feels like I have tried forever.

Zahlman

Feb 17, 2007 at 1:27 PM

Quote:
Original post by chrka
Please help me, it feels like I have tried forever.

Is there some reason std::list doesn't suit your needs?

All you should need to do is make an iterator adapter along the following lines (warning: completely off the top of my head):

// BTW, for longer source snippets you should use the 'source' tags like this insteadtemplate <typename Iterator, typename Container>class CircularIterator {  Iterator i;  Container* c;  CircularIterator(const Iterator& i, const Container& c) : i(i), c(&c) {}  CircularIterator& operator++() {    if (++i == c.end()) { i = c.begin(); }    return *this;  }  CircularIterator operator++(int) {    Iterator j = i;    ++i;    return CircularIterator(j, *c);  }  typename Iterator::value_type operator*() { return *i; }};

BTW, "iterator" is spelled as such, with only one t in each spot :) (Also, the interface for your iterator is completely wrong; the standard interface with operator++, etc. is expected in order to be able to make it interact with the standard library).

Now you can still use the list's .sort() member function to sort the contents.

All of that said, I suspect you're doing very strange things in the client code that will be using this container. Why would you try to sort a *circular* container? What does that even *mean*? (Hint: What is the element after the "last" element? How does it compare to the element "before" it? Is that consistent with the ordering rule for the rest of the container? For that matter, what does "last element" mean for a circular container?)

chrka

Feb 18, 2007 at 2:19 AM

The reason for not using std::list is because I want tro try to make it myself :)

Hmm, could you exaplain your code? Don't understand it fully out.
And mayby an example to?

And your hint, yes I realise that it is a strange thing to sort a circular list.
And what is after the "last" node. I did think about that but was asking if someone did know a way to sort it anyway ;D

thanks

TheTroll

Feb 18, 2007 at 3:10 AM

The reason he is trying to "make it himself" is becuase it is homework. Come on how many of us have made our own linked list after STL outside of class?

theTroll

chrka

Feb 18, 2007 at 3:16 AM

Quote:
Original post by TheTroll
The reason he is trying to "make it himself" is becuase it is homework. Come on how many of us have made our own linked list after STL outside of class?

theTroll

Yes it's true, it is for a class in school. But that was just a singel linked circular list, nothing more (this is actually a ada-course with a little c++ part in it). But I wanted to do more, so I actually can learn something.
And try to learn things isn't bad, right?

ToohrVyk

Feb 18, 2007 at 3:27 AM

Quote:
Original post by chrka
Hmm, could you exaplain your code? Don't understand it fully out.
And mayby an example to?

He has created an iterator wrapper around the iterator of an existing container type. For instance:

typedef CircularIterator<std::list<int>::iterator,std::list<int> > intIterator;std::list<int> intList;intIterator it(intList.begin(),intList);for(int i  = 0; i < 2*intList.size(); ++i, ++it){  std::cout << *it << " ";}

The above would traverse intList two times, as if it were a circular linked list. I have to admit, that's not necessarily an useful thing to have, but it works.

Quote:
And what is after the "last" node. I did think about that but was asking if someone did know a way to sort it anyway ;D

Since the usual definition of "sorted" (that, when traversing the container, each element is smaller than the next) is meaningless for a circular container, you'll have to explain what you mean by "sort".

chrka

Feb 18, 2007 at 3:42 AM

Quote:
Original post by ToohrVyk
Quote:
Original post by chrka
Hmm, could you exaplain your code? Don't understand it fully out.
And mayby an example to?

He has created an iterator wrapper around the iterator of an existing container type. For instance:

*** Source Snippet Removed ***

The above would traverse intList two times, as if it were a circular linked list. I have to admit, that's not necessarily an useful thing to have, but it works.

Quote:
And what is after the "last" node. I did think about that but was asking if someone did know a way to sort it anyway ;D

Since the usual definition of "sorted" (that, when traversing the container, each element is smaller than the next) is meaningless for a circular container, you'll have to explain what you mean by "sort".

Ah yes, sorry for forgetting to explained what I meant by sort.
If I put in the values "1 3 6 5 4 2", I want it to be sorted to "1 2 3 4 5 6" even though it is a circular list.

I have a m_pFirstMember and a m_pLastMember, so I know where the "start" and "end" is. But can't get it to sort =\

ToohrVyk

Feb 18, 2007 at 3:47 AM

Quote:

If I put in the values "1 3 6 5 4 2", I want it to be sorted to "1 2 3 4 5 6" even though it is a circular list.

So, you want to shuffle the values so that there is only one place where a value is greater than the next?

chrka

Feb 18, 2007 at 3:55 AM

Quote:
Original post by ToohrVyk
Quote:

If I put in the values "1 3 6 5 4 2", I want it to be sorted to "1 2 3 4 5 6" even though it is a circular list.

So, you want to shuffle the values so that there is only one place where a value is greater than the next?

Exactly!

Update:

After playing and some modifing of Zahlman's code I have one more problem.

This code works perfectly

	std::list<int> intList;	intList.push_back(1);	intList.push_back(2);	intList.push_back(3);	CircularIterator<std::list<int>::iterator,std::list<int> >		it(intList.begin(),intList);	for(unsigned int i  = 0; i < 2*intList.size(); ++i, ++it)	{	  std::cout << *it << " ";	}

But I would like to know what the ::iterator variable is?
I want to know because I want to be able to do

	TDoubleLinkedList<CIntStorage> list;	for(int i = 1; i < 3; i++)		list.Add(new CIntStorage(rand()));	  CircularIterator<TDoubleLinkedList<CIntStorage>::GetIterator()                                             ,TDoubleLinkedList<CIntStorage> >		itrr(list.begin(),list);

This doesn't work because I have no iterator variable (?) in my class.
Any ide on how I can fix that? is it just an Integer that counts up or what?

Update 2:
I think I have figured out how to implement a iterator so it will look like the stl sample TheTroll gave me.

But you are free to post code that will fix the iterator too. Hopefully better then mine :P

[Edited by - chrka on February 18, 2007 4:55:36 AM]

Sneftel

Feb 18, 2007 at 10:12 AM

Please don't double-post on these forums.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.