linlist.h

X-tree的C++源码

#ifndef __LINLIST
#define __LINLIST

#include <stdio.h>

////////////////////////////////////////////////////////////////////////
// LinList  (SLink)
////////////////////////////////////////////////////////////////////////

template <class DATA> 
struct SLink 
{
    DATA *d;                    // Zeiger auf Element-Daten
    SLink<DATA> *next;          // Zeiger auf naechstes Element
    SLink<DATA> *prev;          // Zeiger auf vorhergehendes Element

    SLink();
    ~SLink();
};

template <class DATA> 
SLink<DATA>::SLink()
{
    d = NULL;
    next = prev = NULL;
}

template <class DATA> 
SLink<DATA>::~SLink()
{
    delete d;
}

////////////////////////////////////////////////////////////////////////
// LinList
////////////////////////////////////////////////////////////////////////

template <class DATA> 
class LinList
{
protected:
    SLink<DATA> *first;         // Rootzeiger des Datenbestands
    SLink<DATA> *last;          // Zeiger auf letztes Element
    int anz;                    // Anzahl der belegten Elemente in der Liste
    SLink<DATA> *akt;           // zeigt auf aktuelles Element
    int akt_index;              // Index des zuletzt mit get geholten Elements
public:
    LinList();
    virtual ~LinList();
    int get_num()               // gibt Anzahl der im Index belegten Elements
        { return anz; }         // zurueck
    
    void check();               // ueberprueft Konsistenz der Liste

    void insert(DATA *f);       // haengt ein Element vorne an die Liste an
    bool erase();               // loescht aktuelles Element aus der Liste

    DATA * get(int i);          // liefert i-tes Element
    DATA * get_first();         // liefert erstes Element im Index
    DATA * get_last();          // liefert erstes Element im Index
    DATA * get_next();          // liefert naechstes Element im Index
    DATA * get_prev();          // liefert vorhergehendes Element im Index
};


template <class DATA> 
LinList<DATA>::LinList()
{
    anz = 0;
    akt_index = -1;
    akt = first = last = NULL;
}

template <class DATA> 
LinList<DATA>::~LinList()
{
    SLink<DATA> *hf;

    // Elemente freigeben
    akt = first;
    while (akt != NULL)
    {
	hf = akt->next;
	delete akt;
	akt = hf;
    }
}

template <class DATA> 
void LinList<DATA>::insert(DATA *f)
{
    SLink<DATA> *sd;

    // neuen Rahmen erzeugen
    sd = new SLink<DATA>;
    sd->d = f;

    // Zeiger umbiegen
    sd->next = first;
    sd->prev = NULL;
    if (first != NULL)
	first->prev = sd;

    // first, last und anz berichtigen
    anz++;
    first = sd;
    if (last == NULL)
	last = sd;

    // Position ist undefiniert
    akt = NULL;
    akt_index = -1;
}

template <class DATA> 
bool LinList<DATA>::erase()
{
    SLink<DATA> *n_akt;

    // Liste leer oder akt nicht definiert?
    if (akt)
    {
	// Element ist erstes Element
	if (akt == first)
	{
	    // Element ist einziges Element
	    if (akt == last)
	    {
		akt_index = -1;
		first = last = NULL;
		n_akt = NULL;
	    }
	    else
	    {
		// Element ist erstes Element, aber nicht leztes
		(akt->next)->prev = NULL;
		first = akt->next;
		n_akt = first;
		akt_index = 0;
	    }
	}
	else
	{
	    // Element ist letztes Element
	    if (akt == last)
	    {
		(akt->prev)->next = NULL;
		last = akt->prev;
		n_akt = NULL;
		akt_index = -1;
	    }
	    else
	    // Element ist mitten in der Liste
	    {
		(akt->next)->prev = akt->prev;
		(akt->prev)->next = akt->next;
		n_akt = akt->next;
		akt_index++;
	    }
	}

	// Speicher freigeben
	delete akt;

	// aktuelles Element setzen
	akt = n_akt;

	// anz berichtigen
	anz--;
	return TRUE;
    }
    return FALSE;
}

template <class DATA> 
DATA* LinList<DATA>::get(int i)
// liefert das i-te Element in der Liste
{
    bool ahead;   // wenn ahead TRUE ist, wird in next-Richtung gesucht
    int j;

    // liegt das i-te Element ueberhaupt in der Liste?
    if (i >= anz)
	return NULL;

    // ist die Liste schon auf das i-te Element positioniert?
    if (i == akt_index)
	return akt->d;

    // hat eine Positionierung der Liste stattgefunden?
    if (akt_index == -1)
    {
	// i liegt naeher an first, als an last
	if (i < (anz / 2))
	{
	    akt = first;
	    akt_index = 0;
	    ahead = TRUE;
	}
	else
	{
	    akt = last;
	    akt_index = anz - 1;
	    ahead = FALSE;
	}
    }
    else
    {
	// die gewuenschte Position liegt vor der aktuellen
	if (i < akt_index)
	{
	    // liegt i naeher an first, als an akt_index?
	    if ((akt_index - i) > i)
	    {
		akt = first;
		akt_index = 0;
		ahead = TRUE;
	    }
	    else
		ahead = FALSE;
	}
	else
	{
	    // liegt i naeher an last, als an akt_index?
	    if ((i - akt_index) > ((anz-1) - i))
	    {
		akt = last;
		akt_index = anz - 1;
		ahead = FALSE;
	    }
	    else
		ahead = TRUE;
	}
    }


    // gesuchter Index liegt in next - Richtung  
    if (ahead)
    {
	for (j = akt_index; j < i; j++)
	{
	    if (!akt)
		error("LinList::get: List seems to be inkonsistent", TRUE);
	    akt = akt->next;
	}
    }
    else
    {
	for (j = akt_index; j > i; j--)
	{
	    if (!akt)
		error("LinList::get: List seems to be inkonsistent", TRUE);
	    akt = akt->prev;
	}
    }

    akt_index = i;
    return akt->d;
}

template <class DATA> 
DATA* LinList<DATA>::get_first()
{
    akt = first;

    if (akt != NULL)
    {
	akt_index = 0;
	return akt->d;
    }
    else
	return NULL;
}

template <class DATA> 
DATA* LinList<DATA>::get_last()
{
    akt = last;

    if (akt != NULL)
    {
	akt_index = anz - 1;
	return akt->d;
    }
    else
	return NULL;
}

template <class DATA> 
DATA* LinList<DATA>::get_next()
{
    akt = akt->next;

    if (akt != NULL)
    {
	akt_index++;
	return akt->d;
    }
    else
    {
	akt_index = -1;
	return NULL;
    }
}

template <class DATA> 
DATA* LinList<DATA>::get_prev()
{
    akt = akt->prev;

    if (akt != NULL)
    {
	akt_index--;
	return akt->d;
    }
    else
    {
	akt_index = -1;
	return NULL;
    }
}

template <class DATA> 
void LinList<DATA>::check()
{
    SLink<DATA> *f, *old_f;
    int myanz;
    char buffer[255];

    old_f = first;
    // Liste muss ganz leer sein
    if (old_f == NULL)
    {
	if (last != NULL)
	    error("LinList::check: first == NULL, last != NULL", FALSE);
	if (anz != 0)
	    error("LinList::check: first == NULL, anz != 0", FALSE);
	return;
    }

    myanz = 1;
    if (old_f->prev != NULL)
    {
	error("LinList::check: Listenkopf.prev ungleich NULL", FALSE);
	return;
    }

    for (f = old_f->next; f != NULL; f = f->next)
    {
	if (f->prev != old_f)
	{
	    error("LinList::check: Rueckwaertsverkettung fehlerhaft", FALSE);
            return;
        }
	if (old_f->next != f)
	{
	    error("LinList::check: Vorwaertsverkettung fehlerhaft", FALSE);
            return;
        }
	old_f = f;

	myanz ++;
	if (myanz > anz)
	{
	    sprintf(buffer, "LinList::check: anz (%d != %d) passt nicht", myanz, anz);
	    error(buffer, FALSE);
	    return;
	}
    }

    if (old_f->next != NULL)
    {
	error("LinList::check: Listenende.next ungleich NULL", FALSE);
	return;
    }

    if (last != old_f)
    {
	error("LinList::check: last ungleich Listenende", FALSE);
	return;
    }

    if (myanz != anz)
    {
	sprintf(buffer, "LinList::check: anz (%d != %d) passt nicht", myanz, anz);
	error(buffer, FALSE);
    }
}


////////////////////////////////////////////////////////////////////////
// SortedLinList
////////////////////////////////////////////////////////////////////////

template <class DATA> 
class SortedLinList : public LinList<DATA>
{
    bool increasing;
public:
    SortedLinList();

    void set_sorting(bool _increasing); // wenn increasing gleich TRUE, wird 
                                // aufsteigend einsortiert
                                // DIESE FUNKTION MUSS VOR DEM ERSTEN EINFUEGEN 
                                // GERUFEN WERDEN !!!!!!!!!!!
    void insert(DATA *f);       // fuegt ein Element durch direktes Einfuegen ein

    void sort(bool _increasing);// sortiert die Liste