//**************************************

//INCLUDE files for :David Nugent's link

// ed list container classes

//**************************************

// +++Date last modified: 05-Jul-1997

////////////////////////////////////////

////////////////////////

// MODULE

// list.hpp

// CREATED

// davidn 03 Dec 1994 23:34

// David L. Nugent

// This class implementation is donated

// to the public domain

// DESCRIPTION

// Classes supporting linked list contai

// ners

// CLASSES/TYPES

// class node

//Represents a single link in a doubly l

// inked list

// class list

//Base class which handles all of the li

// nked list management

// class iter

//Base class for handling iteration thro

// ugh a linked list

// class Node

//Template class used for containment of

// an arbitrary type T

// class List

//Linked list class which is used to get

// /store/remove nodes

//from a linked list containing data

// class Iter

//Used for iteration of a List

// SYNOPSIS

// These classes allow any arbitrary typ

// e to be contained in a

// type-safe linked list. All of the com

// mon code for list

// management itself is contained in a c

// ommon set of classes:

// node, list and iter. Template classes

// derived from these

// allow inline access to the underlying

// base classes via a

// type-safe front-end.

////////////////////////////////////////

////////////////////////

#if !defined( _list_h )

#define _list_h

class list;

// Generic 'node' class

class node

{

friend class iter;

public:

node( list * L =0, node * prv =0, node * nxt =0 )

: mylist( 0 ), Prev( 0 ), Next( 0 )

{ link( L, prv, nxt ); }

virtual ~node( void )

{ unlink( ); }

void link( list * L, node * prv, node * nxt );

void unlink( );

node * prevNode( void ) const

{ return Prev; }

node * nextNode( void ) const

{ return Next; }

private:

list * mylist;

node * Prev, * Next;

};

// template node frontend

template

class Node : public node

{

public:

Node( T data, list * L =0, node * prv =0, node * nxt =0 )

: node( L, prv, nxt ), Data( data ) {}

Node * next( void ) const

{ return (Node *)nextNode(); }

Node * prev( void ) const

{ return (Node *)prevNode(); }

T & ref2data( void ) const

{ return ( T & )Data; }

T * ptr2data( void ) const

{ return ( T * )&Data; }

T data( void ) const

{ return Data; }

private:

T Data;

};

// Generic 'list' class

class list

{

friend class node;

public:

list( void )

: First( 0 ), Last( 0 ), nodes( 0 ) {}

virtual ~list( void )

{ purge(); }

void purge( void );

long items( void ) const

{ return nodes; }

void addatstart( node * n )

{ n->link( this, 0, First ); }

void addatend( node * n )

{ n->link( this, Last, 0 ); }

void addafter( node * n, node * prv )

{ n->link( this, prv, 0 ); }

void addbefore( node * n, node * nxt )

{ n->link( this, 0, nxt ); }

node * firstNode( void ) const

{ return First; }

node * lastNode( void ) const

{ return Last; }

protected:

node * First, * Last;

long nodes;

};

// Container class List

template

class List : public list

{

public:

List( void ) : list() {}

Node * add( T data, Node * prv =0, Node * nxt =0 )

{ return new Node( data, this, prv, nxt ); }

Node * first( void ) const

{ return (Node *)First; }

Node * last( void ) const

{ return (Node *)Last; }

};

enum trOp

{

FIRST, LAST, PREV, NEXT, CURR

};

#define TR_OK 0

#define TR_EMPTY -2

#define TR_NOMORE -3

class iter

{

public:

iter( list & L )

: mylist( L ), nptr( 0 ) {}

iter( iter const & I )

: mylist( I.mylist ), nptr( I.nptr ) {}

iter & operator=( iter const & I )

{ if ( &I.mylist == &mylist ) nptr = I.nptr; return *this; }

void reset( void )

{ nptr = 0; }

int traverse( trOp op );

int current( void )

{ return traverse( CURR ); }

int first( void )

{ return traverse( FIRST ); }

int last ( void )

{ return traverse( LAST ); }

int prev( void )

{ return traverse( PREV ); }

int next( void )

{ return traverse( NEXT ); }

protected:

list & mylist;

node * nptr;

};

// Iterator

template

class Iter : public iter

{

public:

typedef int (*comparator)( const &T, const T&);

Iter( List & L )

: iter( L ) {}

Iter( Iter const & I )

: iter( I ) {}

Iter & operator=( Iter const & I )

{ iter::operator=( I ); return *this; }

List & myList( void ) const

{ return ( List & )mylist; }

Node * atNode( void ) const

{ return ( Node * )nptr; }

T & ref2data( void ) const

{ return atNode()->ref2data(); }

T * ptr2data( void ) const

{ return atNode()->ptr2data(); }

T data( void ) const

{ return atNode()->data(); }

void addFirst( T data )

{ myList().addatstart( new Node( data ) ); }

void addLast( T data )

{ myList().addatend( new Node( data ) ); }

void addAfter( T data )

{ myList().addafter( new Node( data ), nptr ); }

void addBefore( T data )

{ myList().addbefore( new Node( data ), nptr ); }

void add( T data, trOp op );

trOp locate( T & data, comparator compare );

int addsorted( T data, comparator compare, int adddupe =0 );

};

template void Iter::add( T data, trOp op )

{

switch( op )

{

case FIRST:addFirst( data );break;

case LAST:addLast( data ); break;

case PREV:addBefore( data );break;

case CURR: case NEXT: addAfter( data );break;

}

template

trOp

Iter::locate( T & data, comparator compare )

{

if ( n == 0 )// Add to start of empty list

rc = FIRST;

else

{

rc = LAST;

while ( rc == LAST && n != 0 )

{

int r = compare( data, n->ref2data() );

if ( r == 0 )// Found an exact match

rc = CURR;

else if ( r < 0 )// We've gone past it

rc = PREV;

else

n = n->next();

}

nptr = n;

return rc;

}

template

int

Iter::addsorted( T data, comparator compare, int adddupe )

{

trOp r;

if ((( r = locate( data, compare )) != CURR ) || adddupe )

{

add( data, r );

return 1;

}

return 0;

}

#endif// _list_h

code:

Can't Copy and Paste this?

Click here for a copy-and-paste friendly version of this code!

Terms of Agreement:

By using this code, you agree to the following terms...

1) You may use this code in your own programs (and may compile it into a program and distribute it in compiled format for langauges that allow it) freely and with no charge.

2) You MAY NOT redistribute this code (for example to a web site) without written permission from the original author. Failure to do so is a violation of copyright laws.

3) You may link to this code from another website, but ONLY if it is not wrapped in a frame.

4) You will abide by any additional copyright restrictions which the author may have placed in the code or code's description.

//**************************************

// Name: David Nugent's linked list cont

// ainer classes

// Description:Implementation of class n

// ode, list & iterator

// By: Bob Stout (republished under Open

// Content License)

//This code is copyrighted and has// limited warranties.Please see http://

// www.1CPlusPlusStreet.com/xq/ASP/txtCodeI

// d.707/lngWId.3/qx/vb/scripts/ShowCode.ht

// m//for details.//**************************************

// +++Date last modified: 05-Jul-1997

////////////////////////////////////////

/////////////////////

// MODULE

// list.cpp

// CREATED

// davidn 03 Dec 1994 23:59

// David L. Nugent

// This class implementation is donated

// to the public domain

// DESCRIPTION

// Implementation of class node, list &

// iter

// FUNCTIONS

// node::unlink()

//Destroys linkage from a list and remov

// es it from a

//linked list

// node::link()

//Links a node into a linked list

// list::purge()

//Removes all linked list entries

// iter::traverse()

//Provides full traversal functions for

// nodes in a

//linked list

////////////////////////////////////////

/////////////////////

// Implementation of class list & friend

// s

#include "list.hpp"

void

node::unlink()

{

if ( mylist )

{

// Unlink from previous

if ( Prev )

Prev->Next = Next;

else

mylist->First = Next;

// Unlink from next

if ( Next )

Next->Prev = Prev;

else

mylist->Last = Prev;

mylist->nodes--;

mylist = 0;

Prev = Next = 0;

}

void

node::link( list * L, node * prv, node * nxt )

{

// If currently linked, then unlink it

if ( mylist )

unlink();

// Link it to the list

if ( L )

{

mylist = L;

// Add after previous

if ( prv )

{

Prev = prv;

Next = prv->Next;

}

// Add before next

else if ( nxt )

{

Next = nxt;

Prev = nxt->Prev;

}

// Else just add to end

else

{

Next = 0;

Prev = L->Last;

}

if ( Prev )

Prev->Next = this;

else

L->First = this;

if ( Next )

Next->Prev = this;

else

L->Last = this;

mylist->nodes++;

}

void

list::purge( void )

{

while ( First )

delete First;

}

int

iter::traverse( trOp op )

{

if ( mylist.firstNode() == 0 )

return TR_EMPTY;

switch ( op )

{

case NEXT:

if ( nptr )

{

nptr = nptr->Next;

break;

}

case FIRST:

nptr = mylist.firstNode();

break;

case PREV:

if ( nptr )

{

nptr = nptr->Prev;

break;

}

case LAST:

nptr = mylist.lastNode();

break;

case CURR:

break;

}

return ( nptr ) ? TR_OK : TR_NOMORE;

}