List

// list.cc
// Jesse B. Dooley
// 28 May 1996

// template double linked list class

// The following overloaded operators are
// assumed for the L data type.
// <  less than
// >  greater than
// == equals
// << output stream
// >> input stream
// =  assignment

// list.cc

#ifndef LIST_CC
#define LIST_CC

#include <iostream.h>  // UNIX

// prototype class
template <class L> class list;
// prototype input function

template <class L> istream& operator >> (istream&, list<L>&);
// prototype output function

template <class L> ostream& operator << (ostream&, list<L>& );

template<class L> class list {

   struct listnode {
      L ListData;
      listnode *next, *previous;
   };

   listnode *first, *current, *last;

   unsigned long m_ulPopulation;

friend istream& operator >> (istream &IS , list<L> &A);

friend ostream& operator << (ostream &OS , list<L>& A );


int crown( L d )
{
    listnode *newnode = new listnode;

    if (newnode == NULL)
        return 0;

    newnode->next = first;
    newnode->previous = NULL;
    newnode->ListData = d;

    if (first != NULL)
        first->previous = newnode;

    if (last == NULL)
        last = newnode;

    current = first = newnode;

    m_ulPopulation++;

    return 1;
}

          
int cuttail()
{
    if (last == NULL)
        return 0;
            
    current = last->previous;
    current->next = NULL;
    delete last;
    last = current;
    getfirst();
    m_ulPopulation--;

    return 1;
}


int decapitate()
{
    if (first == NULL)
        return 0;

    getfirst();

    first = current->next;

    if (first != NULL)
        first->previous = NULL;

    if (last == current)
        last = NULL;

    delete current;
    getfirst();

    m_ulPopulation--;

    return 1;
}


void getfirst ()
{
    current = first;
}


void getlast ()
{
    current = last;
}


int getnext ()
{
    if (current)
    {
        current = current->next;
        return 1;
    }
    return 0;
}


int getprevious ()
{
    if (current->previous)
    {
        current = current->previous;
        return 1;
    }
    return 0;
}


int gut()
{
    if ((current->next == NULL) || (current->previous == NULL))
        return 0;

    current->previous->next = current->next;
    
    current->next->previous = current->previous;

    delete current;

    getfirst();

    m_ulPopulation--;

    return 1;
}


int offEOL ()
{
    return (current == NULL);
} // offEOL


int pintogut( L &d )
{
    listnode *newnode = new listnode;

    if (newnode == NULL)
        return 0;

    newnode->ListData = d;
    newnode->next = current->next;
    newnode->previous = current;

    current->next->previous = newnode;
    current->next = newnode;

   m_ulPopulation++;

    return 1;
}


int pintotail( L &d )
{
    listnode *newnode = new listnode;
    if (newnode == NULL)
        return 0;

    newnode->next = NULL;
    newnode->previous = last;
    newnode->ListData = d;

    last->next = newnode;
    last = newnode;

    m_ulPopulation++;

    return 1;
}


public:

list()
// first = current = last = 0, m_population = 0
{
   first = current = last = NULL;
   m_ulPopulation = 0;
}

list( const list<L> &P )
// copy list P to list *this
{
  if (P.first)  {
    first = new listnode;
    first->ListData = P.first->ListData;
    first->next = NULL;
    first->previous = NULL;
    current = first;
    listnode *currL = P.first->next;
    while (currL)  {
      current->next = new listnode;
      current->previous = current;
      current = current->next;
      current->ListData = currL->ListData;
      current->next = NULL;
      currL = currL->next;
    }
    last = current;
  }
  else
    first = current = last = NULL;
    m_ulPopulation = P.m_ulPopulation;
}


~list()
// deletes and frees list nodes from first to last
{
   while (first)
   {
      listnode *ptr = first;
      first = first ->next;
      delete ptr;
   }
   first = last = current = NULL;
}


list<L> operator = ( const list<L> &P )
{
     if( P.first )
     {
         erase();
         first = new listnode;
         first->ListData = P.first->ListData;
         first->next = NULL;
         first->previous = NULL;
         current = first;
         listnode *currL = P.first->next;
         while( currL )
         {
                current->next = new listnode;
                current->previous = current;
                current = current->next;
                current->ListData = currL->ListData;
                current->next = NULL;
                currL = currL->next;
        }
        last = current;
     }
     else
     {
         first = current = last = NULL;
     }
     m_ulPopulation = P.m_ulPopulation;

     return *this;
} // =


int operator += ( list<L> &d)
{
    d.getfirst();
    unsigned long lhold_population = d.census();
    while ( !d.offEOL() )
    {
        if ( *this += d.current->ListData )
        {
            lhold_population--;
        }
        else
            return 0;
        d.getnext();
    }
   return (lhold_population == 0);
}


int operator += ( L d)
{
   if ( !locate( d ) )
   {
      if( current && current->ListData < d)
      {
            return pintogut( d );
      }
      else if ( current == first )
      {
          return crown( d );
      }
      else
      {
         if ( offEOL() )
            return pintotail( d );
         else
            return pintogut( d );
      }
   }
   return 0;
}


int operator -= ( list<L> &D )
{
    D.getfirst();
    int hold_population = D.census();

    while ( !D.offEOL() )
    {
           if( *this -= D.current->ListData)
           {
               hold_population--;
           }
           D.getnext();
    }
    return (hold_population == 0);
}


int operator -= ( L d )
{
    if (locate( d ))
    {
       if (current == first)
               return decapitate();
       else if (current == last)
                   return cuttail();
       else
               return gut();
    }
    return 0;
}


int operator==( list<L>& list2 )
{
  unsigned long i_list1census = census();
  unsigned long i_list2census = list2.census();
  
  if (i_list1census != i_list2census)
      return 0;

  while( i_list1census >= 0 )
  {
        L Temp1;
        L Temp2;
        returncurrent(Temp1);
        list2.returncurrent(Temp2);
        if (Temp2 != Temp1)
           return 0;
        getnext();
        list2.getnext();
  }      
  return 1;
}


int AddToList( L d)
{
   locate( d );
   if( current && current->ListData < d)
   {
        return pintogut( d );
   }
   else if ( current == first )
   {
      return crown( d );
   }
   else
   {
      if ( offEOL() )
         return pintotail( d );
      else
         return pintogut( d );
   }
   return 0;
}


unsigned long census()
{
    return m_ulPopulation;
}


void erase()
{
    while (current)
    {
         decapitate();
    }
}


int isempty ()
{
    return (first == NULL);
}

int locate( const L &K )
{
    int i_ReturnCount = 0;
    getfirst();
    if ( !isempty() )
    {
      while ( !offEOL() )
      {
            i_ReturnCount++;
            if ( current->ListData == K )
               return i_ReturnCount;
            if ( current->ListData > K )
            {
                getprevious();
                return 0;
            }
               getnext();
      }
    }
    return 0;
} // locate


int locatenum( const L &K )
{
    int i_ReturnCount = 0;
    listnode *p_Temp = NULL;
    getfirst();
    if ( !isempty() )
    {
      while ( !offEOL() )
      {
            if ( current->ListData == K )
            {
               i_ReturnCount++;
               p_Temp = current;
            }
             getnext();
      }
    }
    current = p_Temp;
    return i_ReturnCount;
} // locatenum


L* returncurrent ()
{
    if (current != NULL)
    {
        return &current->ListData;
    }
    return NULL;
}


int returncurrent ( L &d )
{
    if (current != NULL)
    {
        d = current->ListData;
        return 1;
    }
    return 0;
}


L* returnfirst ( )
{
    return &first->ListData;
}


int returnfirst ( L &d )
{
    if (first != NULL)
    {
        d = first->ListData;
        return 1;
    }
    return 0;
}


L* returnlast ( )
{
    if (last != NULL)
    {
       return &last->ListData;
    }
    return NULL;
}


int returnlast ( L &d )
{
    if (last != NULL)
    {
        d = last->ListData;
        return 1;
    }
    return 0;
}
};

template <class L> istream& operator >> (istream &IS , list<L> &A)
{
   if( IS )
   {
       L D;
       IS >> D;
       A += D;
   }
    return IS;
}

template <class L> ostream& operator << (ostream &OS , list<L>& A )
{
    A.getfirst();
    while ( !A.offEOL() )
    {
          OS << A.returncurrent();
          A.getnext();
    }
    return OS;
} 
#endif // LIST_CC

Internal Links

Parent Article: Programming Portfolio