Hi,
in the past I always appreciated your help and hope that you also can help
me this time. I've spent many many hours but still can't solve the
problem by myself and you are my last hope.
I've a program which is using self-written double-linked lists as a data
structure. The template list consists of list elements and the list itself
linking the list elements.
Here is the header file list.h:
template <class ELEMENT>
class ListElem
{
friend class List<ELEMENT>;
ELEMENT* content;
ListElem<ELEMENT>* nextelem, *prevelem; ListElem(ELEMENT* c);
};
template <class ELEMENT>
class List
{
ListElem<ELEMENT>* firstelem;
ListElem<ELEMENT>* lastelem;
ListElem<ELEMENT>* forward; // Internal forward iterator one //
element beyond
ListElem<ELEMENT>* backward; // Internal backward
//iterator one element beyond
int length;
ListElem<ELEMENT>*> *keymap; void createKeymap();
public:
List();
void Delete(ELEMENT* x);
ELEMENTTYPE* First();
void Append(ELEMENTTYPE* x);
ELEMENTTYPE* Succ(ELEMENTTYPE* x);
};
And the source file:
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include "list.h"
using namespace std;
#define ISEMPTY ((bool)!firstelem)
template <class ELEMENT>
ListElem<ELEMENT>::ListElem(ELEMENT* c) {
content = c;
nextelem = prevelem = NULL;
}
template <class ELEMENT>List<ELEMENT>::List()
:keymap(NULL)
{
firstelem = NULL;
lastelem = NULL;
forward = NULL;
backward = NULL;
length = 0;
}
template <class ELEMENT>
void List<ELEMENT>::Delete(ELEMENT* x) {
if (!keymap)
{
if (!firstelem) return;
if (firstelem->content==x)
{
ListElem<ELEMENT> *n=firstelem->nextelem;
if (n) n->prevelem=NULL;
else lastelem=NULL;
deleteElem(firstelem);
firstelem=n;
return;
}
if (lastelem->content==x)
{
ListElem<ELEMENT> *p=lastelem->prevelem; p->nextelem=NULL;
deleteElem(lastelem);
lastelem=p;
return;
}
// Otherwise create mapping and search for the requested element:
createKeymap();
}
typename multimap<ELEMENTTYPE*, ListElem<ELEMENTTYPE>*>::iterator
it(keymap->find(x));
if (it!=keymap->end())
{
ListElem<ELEMENT> *e=(*it).second;
if (e->nextelem) e->nextelem->prevelem=e->prevelem; else
lastelem=e->prevelem;
if (e->prevelem) e->prevelem->nextelem=e->nextelem; else
firstelem=e->nextelem;
deleteElem(e);
keymap->erase(it);
if (!length)
{
delete keymap;
keymap=NULL;
}
}
}
template <class ELEMENT>
ELEMENT* List<ELEMENT>::First()
{
if (ISEMPTY) return NULL;
forward=firstelem->nextelem;
return firstelem->content;
}
template <class ELEMENT>
ELEMENT* List<ELEMENT>::Succ(ELEMENT* x) {
if (ISEMPTY) return NULL;
if (!keymap) createKeymap();
typename multimap<ELEMENT*, ListElem<ELEMENT>*>::iterator
it(keymap->find(x));
if (it!=keymap->end())
{
ListElem<ELEMENT> *e=(*it).second;
if (e->nextelem)
{
forward=e->nextelem->nextelem;
return e->nextelem->content;
}
}
forward=NULL;
return NULL;
}
#define APPEND(e) { \
if (ISEMPTY) \
{ firstelem = e; \
lastelem = e; \
} \
else \
{ lastelem->nextelem = e; \
e->prevelem=lastelem;\
lastelem = e; \
} \
length++; }
template <class ELEMENT>
void List<ELEMENT>::Append(ELEMENT* x) {
ListElem<ELEMENT> *e=new ListElem<ELEMENT>(x); APPEND(e); if (keymap)
keymap->insert(pair<ELEMENT* const,
ListElem<ELEMENT>*>(x, e));
}
------------------
The code is probably not good style and it's quite a hassle to handle all
the pointers.
My idea was to replace the self-written class by an STL class. First, I
wanted to keep the pointers and not replace it by references since I
didn't want to change all the programs using this list. I also wanted to
keep the function names in ordner not to change the other programs. When
the lists are running I slowly wanted to remove the list class and use
direct STL statements in the code. However, my wrapper class with an STL
list which should replace the self-written class doesn't work properly. A
test program using my new list is telling me that the information stored
in the list is not what it should be. (The test program is using "diff"
with some known correct results...)
Here is my wrapper class which should replace the above posted list:
template <class ELEMENT>
class List
{
list<ELEMENT*>* mylist;
public:
List();
void Delete(ELEMENT* x);
ELEMENT* First();
ELEMENT* Succ(ELEMENT* x);
void Append(ELEMENT* x);
};
And the source code:
#include <cstdio>
#include <cstdlib>
#include <list>
#include <algorithm>
#include <iostream>
#include "graph.h"
using namespace std;
template <class ELEMENT>
List<ELEMENT>::List()
{
mylist = new list<ELEMENT*>;
}
template <class ELEMENT>
void List<ELEMENT>::Delete(ELEMENT* x) {
typename list<ELEMENT*>::iterator it = find(mylist->begin(),
mylist->end(), x);
if (it != mylist->end())
mylist->erase(it);
}
template <class ELEMENT>
ELEMENT* Liste<ELEMENT>::First()
{
if (mylist->empty()) return NULL;
return *(mylist->begin());
}
template <class ELEMENT>
ELEMENT* Liste<ELEMENT>::Succ(ELEMENT* x)
{
if (mylist->empty()) return NULL;
typename list<ELEMENTTYPE2*>::iterator it = find(mylist->begin(),
mylist->end(), x);
if (it != mylist->end())
{
return *(++(it));
}
else
{
current = NULL;
return NULL;
}
}
void Liste<ELEMENT>::Append(ELEMENT* x)
{
mylist->push_back(x);
}
I would really appreciate your help. I spent days with this class
but can't find the error. Maybe you can find why there's a
difference with the stored values in the self-written list and my
STL list.
Sorry, for so many lines of code, but I'm really stuck and this
prevents me of going one with my work.
I also appreciate any comments on how to improve my code.
PLEASE HELP ME ;)
Thank you very much.
Chris
