Search  

---

C:/temp/src/j2k/DataType/Link/SList.cpp

Go to the documentation of this file.

// SList.cpp - Class implementation for a Single-Linked list node with freelist

#ifndef __J2K__SList_CPP__
#define __J2K__SList_CPP__

#include <j2k/DataType/Link/SList.hpp>

/////////////////////////////////////////////////////////////////////////////
/// WARNING:  curr->next  is the OFFICIAL current element !               ///
/// This is to avoid prev(), when adding or removing elements !           ///
/////////////////////////////////////////////////////////////////////////////

inline SList::SList()                     // Constructor -- Ignore sz
 : nbElements( 0 ), pos( 0 )
{
  head = tail = curr = new SLink();       // Create header node (NULL, NULL)
}

SList::~SList()                           // Destructor
{
  while( head != NULL )                   // Return links to freelist storage
  {
    curr = head;
    head = head->next;
    delete curr;
  }
}

void SList::clear()                       // Remove all Elems from list
{
  while( head->next != NULL )             // Return links to free store
  {
    curr       = head->next;              //   (keep header node)
    head->next = curr->next;
    delete curr;
  }

  curr = tail = head;                     // Reinitialize
  pos  = 0;
  nbElements = 0;
}

void SList::setFirst()                    // Set curr to first position
{
  curr = head; 
  pos  = 0;
}

// Insert Elem at current position
void SList::insert( Elem item ) 
{
  assert( curr != NULL );                     // Must be pointing to list Elem
  curr->next = new SLink( item, curr->next );

  if ( tail == curr )                         // Appended new Elem
  {
    tail = curr->next;
  }

  nbElements++;
}

inline void SList::append( Elem  item )       // Insert Elem at tail
{
  curr = tail = tail->next = new SLink( item, NULL );
  nbElements++;
  pos++;
}

inline void SList::enqueue( Elem item ) 
{
  append( item );
}

inline Elem  SList::dequeue()                 // Dequeue Elem from head
{
  curr = head;
  return remove();
}

Elem  SList::remove()                     // Remove/return Elem
{
  assert( isInList() );                   // Must be valid position
  Elem   temp  = curr->next->element;     // Remember value
  SLink* ltemp = curr->next;              // Remember link node
  curr->next   = ltemp->next;             // Remove from list
  if (tail == ltemp) tail = curr;         // Removed last: set tail
  delete ltemp;                           // Send link to free store

  nbElements--;
  return temp;                            // Return value removed
}

inline void SList::next()                 // Move curr to next position
{
  if (curr != NULL) 
  {
    curr = curr->next;
    pos++;
  }
}

// VERY COSTLY ROUTINE ( If you use it alot use DList instead of SList )
void SList::prev()                        // Move curr to previous position
{
  SLink* temp = head;
  if ((curr == NULL) || (curr == head))   // No previous Elem
  {
    curr = NULL;
    return;                               // So, just return
  }

  while( ( temp != NULL ) && ( temp->next != curr ) ) 
  {
    temp = temp->next;
  }

  curr = temp;
  pos--;
}

long SList::size() const 
{
  return nbElements;
}

long SList::getPos() const 
{
  return pos;
}


ULONG SList::length() const          // Return current length of list
{
  register ULONG cnt = 0;
  SLink* temp = head->next;

  for ( ; temp != NULL; temp = temp->next )
  {
     cnt++;                        // Count the number of Elems
  }

  return cnt;
}

void SList::setPos( ULONG p )     // Set curr to specified position
{
  curr = head;
  register ULONG i = 0;
  pos = 0;

  for( ; ( curr != NULL ) && ( i < p ); i++, pos++ )
  {
    curr = curr->next;
  }
}

void SList::setValue( Elem val )    // Set current Elem's value
{
  assert( isInList() ); 
  curr->next->element = val; 
}

Elem SList::currValue() const       // Return value of current Elem
{
  assert( isInList() ); 
  return curr->next->element; 
}

Elem SList::getValue() const        // Return value of current Elem
{
  assert( isInList() ); 
  return curr->next->element; 
}

inline BOOL SList::isInList() const   // TRUE if curr is within list
{
  return ( (curr != NULL)  &&  (curr->next != NULL) );
}

// This is ok?
long SList::find( Elem  item )            // Find value
{
  assert( !isEmpty() ); 

  SLink* temp = curr;
  ULONG  counter = 0;

  if ( curr == head  ||  curr == NULL ) 
  {
    curr = head->next;
    pos = 0;
  }

  for ( ; isInList(); curr = curr->next, pos++ ) 
  {
    if ( curr->element == item ) 
    {
      return pos;
    }
  }

  curr = temp;
  return -1;                              // Not found
}

inline BOOL SList::isEmpty() const        // Return TRUE if list is empty
{
  return ( head->next == NULL || nbElements < 1 );
}


void SList::display() 
{
  if ( curr == head )  return;   // Empty List
  
  SLink* temp = curr;
  curr = head->next;

  printf( "===========================================\n" );

  while ( curr != NULL )             // Stop if we reach the end
  {
    printf( "%d \t", curr->element );

    if ( curr->next == NULL ) 
    {
      printf( "NULL \n" );
    } 
    else 
    {
      printf( "%d \n", curr->next->element );
    }
  
    curr = curr->next;
  }

  printf( "===========================================\n" );

  curr = temp;
}

#endif // End of SList.cpp

---