Source: classlib/include/classlib/listimp.h
|
|
|
|
/***************************************************************************
listimp.h - liste
-------------------
begin : ven dic 7 17:40:01 CET 2001
copyright : (C) 2001 by Nicola De Nisco
email : nicola@winada.it
***************************************************************************/
/***************************************************************************
* *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 2 of the License, or *
* (at your option) any later version. *
* *
***************************************************************************/
#if !defined( __CLASSLIB_LISTIMP_H )
#define __CLASSLIB_LISTIMP_H
#if !defined( __LIMITS_H )
#include
#endif // __LIMITS_H
#if !defined( __CHECKS_H )
#include
#endif // __CHECKS_H
#if !defined( __CLASSLIB_DEFS_H )
#include "classlib/defs.h"
#endif // __CLASSLIB_DEFS_H
#if !defined( __CLASSLIB_MEMMGR_H )
#include "classlib/memmgr.h"
#endif // __CLASSLIB_MEMMGR_H
#if !defined( __CLASSLIB_ALLOCTR_H )
#include "classlib/alloctr.h"
#endif // __CLASSLIB_ALLOCTR_H
#if !defined( __CLASSLIB_VOIDP_H )
#include "classlib/voidp.h"
#endif // __CLASSLIB_VOIDP_H
template class TMListImp;
template class TMListElement;
/**
template class TMListElement
Node for templates TMListImp and TMIListImp
*/
template class TMListBlockInitializer
{
protected:
TMListBlockInitializer();
~TMListBlockInitializer();
static unsigned Count;
};
template
TMListBlockInitializer::TMListBlockInitializer()
{
PRECONDITION( Count != UINT_MAX );
if( Count++ == 0 )
TMListElement::Mgr =
new TMMemBlocks( sizeof(TMListElement), 20 );
}
template
TMListBlockInitializer::~TMListBlockInitializer()
{
PRECONDITION( Count != 0 );
if( --Count == 0 )
{
delete (TMListElement::Mgr);
TMListElement::Mgr = 0;
}
}
template
unsigned TMListBlockInitializer::Count = 0;
template class TMListElement
{
public:
TMListElement( const T& t, TMListElement *p ) :
Data(t)
{
Next = p->Next;
p->Next = this;
}
TMListElement();
TMListElement *Next;
T Data;
private:
friend class TMListBlockInitializer;
static TMMemBlocks *Mgr;
};
template
TMMemBlocks *TMListElement::Mgr = 0;
template
inline TMListElement::TMListElement()
{
Next = 0;
}
template class TMListIteratorImp;
/**
template class TMListImp
Implements a managed list of objects of type T. Assumes that
T has meaningful copy semantics and a default constructor.
*/
template class TMListImp :
private TMListBlockInitializer
{
typedef TMListBlockInitializer Parent;
public:
typedef void (*IterFunc)(T &, void *);
typedef int (*CondFunc)(const T &, void *);
friend class TMListIteratorImp;
TMListImp()
{
InitList();
}
virtual ~TMListImp()
{
Flush();
}
const T& PeekHead() const
{
return Head.Next->Data;
}
int Add( const T& t );
int Detach( const T& t )
{
return DoDetach( t, 0 );
}
int DetachAtHead()
{
return DoDetachAtHead(0);
}
T *Find( const T& t );
void Flush()
{
DoFlush();
}
int IsEmpty() const
{
return ItemsInContainer == 0;
}
int GetItemsInContainer() const
{
return ItemsInContainer;
}
void ForEach( IterFunc iter, void *args );
T *FirstThat( CondFunc cond, void *args ) const;
T *LastThat( CondFunc cond, void *args ) const;
protected:
int DoDetach( const T& t, int del = 0 )
{
return DetachElement(FindDetach(t),del);
}
int DoDetachAtHead( int del = 0 )
{
return DetachElement(&Head,del);
}
void DoFlush( int del = 0 );
TMListElement Head, Tail;
virtual TMListElement *FindDetach( const T& t )
{
return FindPred(t);
}
virtual TMListElement *FindPred( const T& );
int ItemsInContainer;
private:
virtual void RemoveData( TMListElement * )
{
}
void InitList();
int DetachElement( TMListElement *pred, int del = 0 );
};
template void TMListImp::InitList()
{
Head.Next = &Tail;
Tail.Next = &Tail;
ItemsInContainer = 0;
}
template int TMListImp::Add( const T& toAdd )
{
new TMListElement( toAdd, &Head );
ItemsInContainer++;
return 1;
}
template
TMListElement *TMListImp::FindPred( const T& t )
{
Tail.Data = t;
TMListElement *cursor = &Head;
while( !(t == cursor->Next->Data) )
cursor = cursor->Next;
Tail.Data = T();
return cursor;
}
template
int TMListImp::DetachElement( TMListElement *pred,
int del )
{
TMListElement *item = pred->Next;
if( item == &Tail )
return 0;
else
{
pred->Next = pred->Next->Next;
if( del != 0 )
RemoveData( item );
delete item;
ItemsInContainer--;
return 1;
}
}
template T *TMListImp::Find( const T& t )
{
TMListElement *cursor = FindPred(t)->Next;
if( cursor == &Tail )
return 0;
else
return &cursor->Data;
}
template void TMListImp::DoFlush( int del )
{
TMListElement *current = Head.Next;
while( current != &Tail )
{
TMListElement *temp = current;
current = current->Next;
if( del != 0 )
RemoveData( temp );
delete temp;
}
InitList();
}
template
void TMListImp::ForEach( IterFunc iter, void *args )
{
TMListElement *cur = Head.Next;
while( cur->Next != cur )
{
iter( cur->Data, args );
cur = cur->Next;
}
}
template
T *TMListImp::FirstThat( CondFunc cond, void *args ) const
{
TMListElement *cur = Head.Next;
while( cur->Next != cur )
if( cond( cur->Data, args ) != 0 )
return &(cur->Data);
else
cur = cur->Next;
return 0;
}
template
T *TMListImp::LastThat( CondFunc cond, void *args ) const
{
T *res = 0;
TMListElement *cur = Head.Next;
while( cur->Next != cur )
{
if( cond( cur->Data, args ) != 0 )
res = &(cur->Data);
cur = cur->Next;
}
return res;
}
/**
template class TMSListImp
Implements a managed, sorted list of objects of type T. Assumes that
T has meaningful copy semantics, a meaningful < operator, and a
default constructor.
*/
template class TMSListImp :
private TMListImp
{
typedef TMListImp Parent;
public:
friend class TMListIteratorImp;
int Add( const T& t );
typedef void (*IterFunc)(T&, void *);
typedef int (*CondFunc)(const T&, void *);
Parent::PeekHead;
Parent::Detach;
Parent::DetachAtHead;
Parent::Find;
Parent::Flush;
Parent::IsEmpty;
Parent::GetItemsInContainer;
Parent::ForEach;
Parent::FirstThat;
Parent::LastThat;
protected:
Parent::Head;
Parent::Tail;
Parent::ItemsInContainer;
Parent::DoDetach;
Parent::DoDetachAtHead;
Parent::DoFlush;
virtual TMListElement *FindDetach( const T& t );
virtual TMListElement *FindPred( const T& );
};
/**
template class TMListIteratorImp
Implements a list iterator. This iterator works with any direct
managed list. For indirect lists, see TMIListIteratorImp.
*/
template class TMListIteratorImp
{
typedef TMListImp iter1;
typedef TMSListImp iter2;
public:
TMListIteratorImp( const iter1& l )
{
List = &l;
Cur = List->Head.Next;
}
TMListIteratorImp( const iter2& l );
operator int()
{
return Cur != &(List->Tail);
}
const T& Current()
{
PRECONDITION( int(*this) != 0 );
return Cur->Data;
}
const T& operator ++ ( int )
{
PRECONDITION( Cur != &(List->Tail) );
TMListElement *temp = Cur;
Cur = Cur->Next;
return temp->Data;
}
const T& operator ++ ()
{
PRECONDITION( Cur->Next != &(List->Tail) );
Cur = Cur->Next;
return Cur->Data;
}
void Restart()
{
Cur = List->Head.Next;
}
private:
const TMListImp *List;
TMListElement *Cur;
};
/**
template class TListImp
template class TListIteratorImp
Implements a list of objects of type T using TStandardAllocator as
its memory manager. Assumes that T has meaningful copy semantics
and a default constructor.
*/
template class TListImp :
public TMListImp
{
};
/**
template class TListImp
template class TListIteratorImp
Implements a list of objects of type T using TStandardAllocator as
its memory manager. Assumes that T has meaningful copy semantics
and a default constructor.
*/
template class TListIteratorImp :
public TMListIteratorImp
{
public:
TListIteratorImp( const TMListImp& l ) :
TMListIteratorImp( l ) {}
TListIteratorImp( const TMSListImp& l ) :
TMListIteratorImp( l ) {}
};
template class TMSListIteratorImp :
public TMListIteratorImp
{
public:
TMSListIteratorImp( const TMSListImp& l ) :
TMListIteratorImp( l ) {}
};
template int TMSListImp::Add( const T& t )
{
new TMListElement( t, FindPred(t) );
ItemsInContainer++;
return 1;
}
template
TMListElement *TMSListImp::FindDetach( const T& t )
{
TMListElement *res = FindPred(t);
if( res != 0 &&
res->Next->Data == t )
return res;
else
return &Tail;
}
template
TMListElement *TMSListImp::FindPred( const T& t )
{
Tail.Data = t;
TMListElement *cursor = &Head;
while( cursor->Next->Data < t )
cursor = cursor->Next;
return cursor;
}
/**
template class TSListImp
template class TSListIteratorImp
Implements a sorted list of objects of type T using
TStandardAllocator as its memory manager. Assumes that
T has meaningful copy semantics, a meaningful < operator, and a
default constructor.
*/
template class TSListImp :
public TMSListImp
{
};
template class TSListIteratorImp :
public TMSListIteratorImp
{
public:
TSListIteratorImp( const TSListImp& l ) :
TMSListIteratorImp( l ) {}
};
// constructor for TMListIteratorImp
template
TMListIteratorImp::TMListIteratorImp( const TMSListImp& l )
{
List = &l;
Cur = List->Head.Next;
}
/**
template class TMInternalIListImp
Implements a managed list of pointers to objects of type T.
This is implemented through the form of TMListImp specified by List.
Since pointers always have meaningful copy semantics, this class
can handle any type of object.
*/
template class TMInternalIListImp :
public TMListImp
{
typedef TMListImp Parent;
public:
typedef void (*IterFunc)(T&, void *);
typedef int (*CondFunc)(const T&, void *);
T *PeekHead() const
{
return STATIC_CAST(T *,STATIC_CAST(void *,Parent::PeekHead()));
}
int Add( T *t )
{
return Parent::Add( t );
}
int Detach( T *t, int del = 0 )
{
return Parent::DoDetach( t, del );
}
int DetachAtHead( int del = 0 )
{
return Parent::DoDetachAtHead( del );
}
void Flush( int del = 0 )
{
Parent::DoFlush(del);
}
T *Find( const T *t );
void ForEach( IterFunc iter, void * );
T *FirstThat( CondFunc cond, void * ) const;
T *LastThat( CondFunc cond, void * ) const;
protected:
virtual TMListElement *
FindPred( const TVoidPointer& ) = 0;
private:
virtual void RemoveData( TMListElement *block )
{
delete STATIC_CAST(T *,STATIC_CAST(void *,block->Data));
}
};
template
T *TMInternalIListImp::Find( const T *t )
{
TMListElement *cur = Head.Next;
Tail.Data = t;
while( !(*STATIC_CAST(T *,STATIC_CAST(void *,cur->Data)) == *t) )
cur = cur->Next;
Tail.Data = TVoidPointer();
if( cur == &Tail )
return 0;
else
return STATIC_CAST(T *,STATIC_CAST(void *,cur->Data));
}
template
void TMInternalIListImp::ForEach( IterFunc iter,
void *args )
{
TMListElement *cur = Head.Next;
while( cur->Next != cur )
{
iter( *STATIC_CAST(T *,STATIC_CAST(void *,cur->Data)), args );
cur = cur->Next;
}
}
template
T *TMInternalIListImp::FirstThat( CondFunc cond,
void *args ) const
{
TMListElement *cur = Head.Next;
while( cur->Next != cur )
if( cond( *STATIC_CAST(T *,STATIC_CAST(void *,cur->Data)), args ) != 0 )
return STATIC_CAST(T *,STATIC_CAST(void *,cur->Data));
else
cur = cur->Next;
return 0;
}
template
T *TMInternalIListImp::LastThat( CondFunc cond,
void *args ) const
{
T *res = 0;
TMListElement *cur = Head.Next;
while( cur->Next != cur )
{
if( cond( *STATIC_CAST(T *,STATIC_CAST(void *,cur->Data)), args ) != 0 )
res = STATIC_CAST(T *,STATIC_CAST(void *,cur->Data));
cur = cur->Next;
}
return res;
}
/**
template class TMSInternalIListImp
Implements a sorted managed list of pointers to objects of type T.
This is implemented through the form of TMListImp specified by List.
Since pointers always have meaningful copy semantics, this class
can handle any type of object.
*/
template class TMSInternalIListImp :
public TMSListImp
{
typedef TMSListImp Parent;
public:
typedef void (*IterFunc)(T&, void *);
typedef int (*CondFunc)(const T&, void *);
T *PeekHead() const
{
return STATIC_CAST(T *,STATIC_CAST(void *,Parent::PeekHead()));
}
int Add( T *t )
{
return Parent::Add( t );
}
int Detach( T *t, int del = 0 )
{
return Parent::DoDetach( t, del );
}
int DetachAtHead( int del = 0 )
{
return Parent::DoDetachAtHead( del );
}
void Flush( int del = 0 )
{
Parent::DoFlush(del);
}
T *Find( const T *t );
void ForEach( IterFunc iter, void * );
T *FirstThat( CondFunc cond, void * ) const;
T *LastThat( CondFunc cond, void * ) const;
protected:
virtual TMListElement *
FindPred( const TVoidPointer& ) = 0;
private:
virtual void RemoveData( TMListElement *block )
{
delete STATIC_CAST(T *,STATIC_CAST(void *,block->Data));
}
};
template
T *TMSInternalIListImp::Find( const T *t )
{
TMListElement *cur = Head.Next;
Tail.Data = t;
while( !(*STATIC_CAST(T *,STATIC_CAST(void *,cur->Data)) == *t) )
cur = cur->Next;
Tail.Data = TVoidPointer();
if( cur == &Tail )
return 0;
else
return STATIC_CAST(T *,STATIC_CAST(void *,cur->Data));
}
template
void TMSInternalIListImp::ForEach( IterFunc iter,
void *args )
{
TMListElement *cur = Head.Next;
while( cur->Next != cur )
{
iter( *STATIC_CAST(T *,STATIC_CAST(void *,cur->Data)), args );
cur = cur->Next;
}
}
template
T *TMSInternalIListImp::FirstThat( CondFunc cond,
void *args ) const
{
TMListElement *cur = Head.Next;
while( cur->Next != cur )
if( cond( *STATIC_CAST(T *,STATIC_CAST(void *,cur->Data)), args ) != 0 )
return STATIC_CAST(T *,STATIC_CAST(void *,cur->Data));
else
cur = cur->Next;
return 0;
}
template
T *TMSInternalIListImp::LastThat( CondFunc cond,
void *args ) const
{
T *res = 0;
TMListElement *cur = Head.Next;
while( cur->Next != cur )
{
if( cond( *STATIC_CAST(T *,STATIC_CAST(void *,cur->Data)), args ) != 0 )
res = STATIC_CAST(T *,STATIC_CAST(void *,cur->Data));
cur = cur->Next;
}
return res;
}
/**
template class TMIListImp
template class TMIListIteratorImp
Implements a managed list of pointers to objects of type T.
This is implemented through the template TMInternalIListImp. Since
pointers always have meaningful copy semantics, this class
can handle any type of object.
*/
template class TMIListImp :
public TMInternalIListImp
{
typedef TMInternalIListImp Parent;
public:
//friend class TMIListIteratorImp;
friend class Parent;
void Flush( int del = 0 )
{
Parent::DoFlush(del);
}
typedef void (*IterFunc)(T &, void *);
typedef int (*CondFunc)(const T &, void *);
Parent::PeekHead;
Parent::Add;
Parent::Detach;
Parent::DetachAtHead;
Parent::Find;
Parent::IsEmpty;
Parent::GetItemsInContainer;
Parent::ForEach;
Parent::FirstThat;
Parent::LastThat;
protected:
Parent::Head;
Parent::Tail;
Parent::ItemsInContainer;
virtual TMListElement *FindPred( const TVoidPointer& );
};
template class TMIListIteratorImp :
private TMListIteratorImp
{
typedef TMListIteratorImp Parent;
public:
TMIListIteratorImp( const TMIListImp& l ) :
TMListIteratorImp(l) {}
T *Current()
{
return STATIC_CAST(T *,STATIC_CAST(void *,Parent::Current()));
}
T *operator ++ (int)
{
return STATIC_CAST(T *,STATIC_CAST(void *,Parent::operator++(1)));
}
T *operator ++ ()
{
return STATIC_CAST(T *,STATIC_CAST(void *,Parent::operator++()));
}
Parent::Restart;
Parent::operator int;
};
template
TMListElement *
TMIListImp::FindPred( const TVoidPointer& t )
{
Tail.Data = t;
TMListElement *cursor = &Head;
while( !(*STATIC_CAST(T *,STATIC_CAST(void *,t)) ==
*STATIC_CAST(T *,STATIC_CAST(void *,cursor->Next->Data)) ))
cursor = cursor->Next;
Tail.Data = TVoidPointer();
return cursor;
}
/**
template class TIListImp
template class TIListIteratorImp
Implements a list of pointers to objects of type T using
TStandardAllocator as its memory manager. This is implemented
through the template TMInternalIListImp. Since
pointers always have meaningful copy semantics, this class
can handle any type of object.
*/
template class TIListImp :
public TMIListImp
{
};
template class TIListIteratorImp :
public TMIListIteratorImp
{
public:
TIListIteratorImp( const TIListImp& l ) :
TMIListIteratorImp( l ) {}
};
/**
template class TMISListImp
template class TMISListIteratorImp
Implements a managed sorted list of pointers to objects of type T.
This is implemented through the template TInternalIListImp. Since
pointers always have meaningful copy semantics, this class
can handle any type of object.
*/
template class TMISListImp :
private TMSInternalIListImp
{
typedef TMSInternalIListImp Parent;
public:
friend class Parent;
Parent::PeekHead;
Parent::Add;
Parent::Detach;
Parent::DetachAtHead;
Parent::Find;
Parent::Flush;
Parent::IsEmpty;
Parent::GetItemsInContainer;
Parent::ForEach;
Parent::FirstThat;
Parent::LastThat;
protected:
Parent::Head;
Parent::Tail;
Parent::ItemsInContainer;
virtual TMListElement *FindDetach( const TVoidPointer& );
virtual TMListElement *FindPred( const TVoidPointer& );
};
template class TMISListIteratorImp :
private TMListIteratorImp
{
typedef TMListIteratorImp Parent;
public:
TMISListIteratorImp( const TMISListImp& l ) :
TMListIteratorImp(l) {}
T *Current()
{
return STATIC_CAST(T *,STATIC_CAST(void *,Parent::Current()));
}
T *operator ++ (int)
{
return STATIC_CAST(T *,STATIC_CAST(void *,Parent::operator++(1)));
}
T *operator ++ ()
{
return STATIC_CAST(T *,STATIC_CAST(void *,Parent::operator++()));
}
Parent::Restart;
Parent::operator int;
};
template
TMListElement *
TMISListImp::FindDetach( const TVoidPointer& t )
{
TMListElement *res = FindPred(t);
if( res == 0 || res->Next == &Tail )
return &Tail;
else if(
*STATIC_CAST(T *,STATIC_CAST(void *,res->Next->Data)) ==
*STATIC_CAST(T *,STATIC_CAST(void *,t)) )
return res;
else
return &Tail;
}
template
TMListElement *
TMISListImp::FindPred( const TVoidPointer& t )
{
Tail.Data = t;
TMListElement *cursor = &Head;
while( *STATIC_CAST(T *,STATIC_CAST(void *,cursor->Next->Data)) <
*STATIC_CAST(T *,STATIC_CAST(void *,t)) )
cursor = cursor->Next;
Tail.Data = TVoidPointer();
return cursor;
}
/**
template class TISListImp
template class TISListIteratorImp
Implements a sorted list of pointers to objects of type T using
TStandardAllocator as its memory manager.
This is implemented through the template TInternalIListImp. Since
pointers always have meaningful copy semantics, this class
can handle any type of object.
*/
template class TISListImp :
public TMISListImp
{
};
template class TISListIteratorImp :
public TMISListIteratorImp
{
public:
TISListIteratorImp( const TISListImp& l ) :
TMISListIteratorImp( l ) {}
};
#endif // __CLASSLIB_LISTIMP_H
| Generated by: nicola on gulliver.wadahome.it on Sun May 25 13:54:34 2003, using kdoc 2.0a53. |