home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / snip9707.zip / LIST.HPP < prev    next >
C/C++ Source or Header  |  1997-07-05  |  7KB  |  257 lines
  1. // +++Date last modified: 05-Jul-1997
  2.  
  3. ////////////////////////////////////////////////////////////////
  4. // MODULE
  5. //  list.hpp
  6. // CREATED
  7. //  davidn  03 Dec 1994  23:34
  8. //  David L. Nugent
  9. //  This class implementation is donated to the public domain
  10. // DESCRIPTION
  11. //  Classes supporting linked list containers
  12. // CLASSES/TYPES
  13. //  class node
  14. //    Represents a single link in a doubly linked list
  15. //  class list
  16. //    Base class which handles all of the linked list management
  17. //  class iter
  18. //    Base class for handling iteration through a linked list
  19. //  class Node<T>
  20. //    Template class used for containment of an arbitrary type T
  21. //  class List<T>
  22. //    Linked list class which is used to get/store/remove nodes
  23. //    from a linked list containing data
  24. //  class Iter<T>
  25. //    Used for iteration of a List<T>
  26. // SYNOPSIS
  27. //  These classes allow any arbitrary type to be contained in a
  28. //  type-safe linked list. All of the common code for list
  29. //  management itself is contained in a common set of classes:
  30. //  node, list and iter. Template classes derived from these
  31. //  allow inline access to the underlying base classes via a
  32. //  type-safe front-end.
  33. ////////////////////////////////////////////////////////////////
  34.  
  35. #if !defined( _list_h )
  36. #define _list_h
  37.  
  38. class list;
  39.  
  40.     // Generic 'node' class
  41.  
  42. class node
  43. {
  44.     friend class iter;
  45.   public:
  46.     node( list * L =0, node * prv =0, node * nxt =0 )
  47.       : mylist( 0 ), Prev( 0 ), Next( 0 )
  48.     { link( L, prv, nxt ); }
  49.     virtual ~node( void )
  50.     { unlink( ); }
  51.     void link( list * L, node * prv, node * nxt );
  52.     void unlink( );
  53.     node * prevNode( void ) const
  54.     { return Prev; }
  55.     node * nextNode( void ) const
  56.     { return Next; }
  57.   private:
  58.     list * mylist;
  59.     node * Prev, * Next;
  60. };
  61.  
  62.     // template node frontend
  63.  
  64. template<class T>
  65. class Node : public node
  66. {
  67.   public:
  68.     Node( T data, list * L =0, node * prv =0, node * nxt =0 )
  69.       : node( L, prv, nxt ), Data( data ) {}
  70.     Node<T> * next( void ) const
  71.     { return (Node<T> *)nextNode(); }
  72.     Node<T> * prev( void ) const
  73.     { return (Node<T> *)prevNode(); }
  74.     T & ref2data( void ) const
  75.     { return ( T & )Data; }
  76.     T * ptr2data( void ) const
  77.     { return ( T * )&Data; }
  78.     T data( void ) const
  79.     { return Data; }
  80.   private:
  81.     T Data;
  82. };
  83.  
  84.     // Generic 'list' class
  85.  
  86. class list
  87. {
  88.     friend class node;
  89.   public:
  90.     list( void )
  91.       : First( 0 ), Last( 0 ), nodes( 0 ) {}
  92.     virtual ~list( void )
  93.     { purge(); }
  94.     void purge( void );
  95.     long items( void ) const
  96.     { return nodes; }
  97.     void addatstart( node * n )
  98.     { n->link( this, 0, First ); }
  99.     void addatend( node * n )
  100.     { n->link( this, Last, 0 ); }
  101.     void addafter( node * n, node * prv )
  102.     { n->link( this, prv, 0 ); }
  103.     void addbefore( node * n, node * nxt )
  104.     { n->link( this, 0, nxt ); }
  105.     node * firstNode( void ) const
  106.     { return First; }
  107.     node * lastNode( void ) const
  108.     { return Last; }
  109.   protected:
  110.     node * First, * Last;
  111.     long nodes;
  112. };
  113.  
  114.     // Container class List<T>
  115.  
  116. template<class T>
  117. class List : public list
  118. {
  119.   public:
  120.     List( void ) : list() {}
  121.     Node<T> * add( T data, Node<T> * prv =0, Node<T> * nxt =0 )
  122.     { return new Node<T>( data, this, prv, nxt ); }
  123.     Node<T> * first( void ) const
  124.     { return (Node<T> *)First; }
  125.     Node<T> * last( void ) const
  126.     { return (Node<T> *)Last; }
  127. };
  128.  
  129. enum trOp
  130. {
  131.   FIRST, LAST, PREV, NEXT, CURR
  132. };
  133.  
  134. #define TR_OK     0
  135. #define TR_EMPTY  -2
  136. #define TR_NOMORE -3
  137.  
  138. class iter
  139. {
  140.   public:
  141.     iter( list & L )
  142.       : mylist( L ), nptr( 0 ) {}
  143.     iter( iter const & I )
  144.       : mylist( I.mylist ), nptr( I.nptr ) {}
  145.     iter & operator=( iter const & I )
  146.     { if ( &I.mylist == &mylist ) nptr = I.nptr; return *this; }
  147.     void reset( void )
  148.     { nptr = 0; }
  149.     int traverse( trOp op );
  150.     int current( void )
  151.     { return traverse( CURR ); }
  152.     int first( void )
  153.     { return traverse( FIRST ); }
  154.     int last ( void )
  155.     { return traverse( LAST );  }
  156.     int prev( void )
  157.     { return traverse( PREV );  }
  158.     int next( void )
  159.     { return traverse( NEXT );  }
  160.   protected:
  161.     list & mylist;
  162.     node * nptr;
  163. };
  164.  
  165.     // Iterator
  166.  
  167. template<class T>
  168. class Iter : public iter
  169. {
  170.   public:
  171.     typedef int (*comparator)( const &T, const T&);
  172.  
  173.     Iter( List<T> & L )
  174.       : iter( L ) {}
  175.     Iter( Iter<T> const & I )
  176.       : iter( I ) {}
  177.     Iter<T> & operator=( Iter<T> const & I )
  178.     { iter::operator=( I ); return *this;  }
  179.     List<T> & myList( void ) const
  180.     { return ( List<T> & )mylist; }
  181.     Node<T> * atNode( void ) const
  182.     { return ( Node<T> * )nptr; }
  183.     T & ref2data( void ) const
  184.     { return atNode()->ref2data(); }
  185.     T * ptr2data( void ) const
  186.     { return atNode()->ptr2data(); }
  187.     T data( void ) const
  188.     { return atNode()->data(); }
  189.     void addFirst( T data )
  190.     { myList().addatstart( new Node<T>( data ) ); }
  191.     void addLast( T data )
  192.     { myList().addatend( new Node<T>( data ) ); }
  193.     void addAfter( T data )
  194.     { myList().addafter( new Node<T>( data ), nptr ); }
  195.     void addBefore( T data )
  196.     { myList().addbefore( new Node<T>( data ), nptr ); }
  197.     void add( T data, trOp op );
  198.     trOp locate( T & data, comparator compare );
  199.     int addsorted( T data, comparator compare, int adddupe =0 );
  200. };
  201.  
  202. template<class T> void Iter<T>::add( T data, trOp op )
  203. {
  204.   switch( op )
  205.   {
  206.   case FIRST:           addFirst( data );    break;
  207.   case LAST:            addLast( data );     break;
  208.   case PREV:            addBefore( data );   break;
  209.   case CURR: case NEXT: addAfter( data );    break;
  210.   }
  211. }
  212.  
  213. template<class T>
  214. trOp
  215. Iter<T>::locate( T & data, comparator compare )
  216. {
  217.   register trOp rc;
  218.   register Node<T> * n = myList().first();
  219.  
  220.   if ( n == 0 )   // Add to start of empty list
  221.     rc = FIRST;
  222.   else
  223.   {
  224.     rc = LAST;
  225.     while ( rc == LAST && n != 0 )
  226.     {
  227.       int r = compare( data, n->ref2data() );
  228.       if ( r == 0 )       // Found an exact match
  229.         rc = CURR;
  230.       else if ( r < 0 )   // We've gone past it
  231.         rc = PREV;
  232.       else
  233.         n = n->next();
  234.     }
  235.   }
  236.  
  237.   nptr = n;
  238.   return rc;
  239.  
  240. }
  241.  
  242. template<class T>
  243. int
  244. Iter<T>::addsorted( T data, comparator compare, int adddupe )
  245. {
  246.   trOp r;
  247.  
  248.   if ((( r  = locate( data, compare )) != CURR ) || adddupe )
  249.   {
  250.     add( data, r );
  251.     return 1;
  252.   }
  253.   return 0;
  254. }
  255.  
  256. #endif    // _list_h
  257.