#include <DLList.hpp>

Inheritance diagram for DLList:

Public Member Functions
	DLList (int list_size)
	DLList (const DLList &copy_from)
virtual	~DLList ()
void	step ()
void	step (int n)
void	back ()
void	back (int n)
void	reset ()
void	last ()
void	clean_out ()
void	shrink (int k)
CubitBoolean	is_at_beginning () const
CubitBoolean	is_at_end () const
int	get_index ()
void	set_index (int new_index)
void	compress ()
void	reverse ()
DLList &	operator= (const DLList &)
virtual void	merge_unique (DLList &merge_list, int merge_list_unique=CUBIT_FALSE)
void	intersect (DLList &merge_list)
int	append_unique (void *new_item)
	SetDynamicMemoryAllocation (memoryManager) int operator<(const DLList &list) const
int	operator<= (const DLList &list) const
int	operator> (const DLList &list) const
int	operator>= (const DLList &list) const
int	operator== (const DLList &list) const
int	operator!= (const DLList &list) const
Protected Member Functions
void	insert_link (void *newBody)
void	insert_link_first (void *new_item)
void	append_link (void *newBody)
void *	nullify_link ()
void *	cut_link ()
void *	extract_link ()
CubitBoolean	omit_link (void *)
void *	next_item (int n=1) const
void *	prev_item (int n=1) const
void *	get_item () const
void *	change_item_to (void *newBody)
void *	move_to_and_remove_item (void *item)
void *	get_item_and_step ()
void *	step_and_get_item ()
void *	get_item_and_back ()
CubitBoolean	move_to_item (void *body)
CubitBoolean	move_to_nearby_item (void *body)
int	distance_to_nearby_item (void *body)
CubitBoolean	move_between_items (void body1, void body2)
int	where_is_item (void *item) const
Protected Attributes
void *	nullItem
int	index
Static Private Member Functions
static const char *	type ()
Static Private Attributes
static MemoryManager	memoryManager

Detailed Description

Definition at line 38 of file DLList.hpp.

Constructor & Destructor Documentation

DLList::DLList ( int list_size )

Definition at line 19 of file DLList.cpp.

                              : ArrayBasedContainer( increment )
{
  index      = 0;
  nullItem   = 0;
}

DLList::DLList ( const DLList & copy_from )

Definition at line 26 of file DLList.cpp.

                                 : ArrayBasedContainer ( from )
{
  index = from.index;
  listIsSorted = CUBIT_FALSE;
}

DLList::~DLList ( ) [virtual]

Definition at line 32 of file DLList.cpp.

{
}

Member Function Documentation

void DLList::append_link ( void * newBody ) [inline, protected]

Reimplemented in SDLList.

Definition at line 323 of file DLList.hpp.

{
    assert(new_item != NULL);
    // see if the list must be lengthened

    if ( itemCount == listLength )
        lengthen_list();

    listArray[itemCount++] = new_item;
}

int DLList::append_unique ( void * new_item )

void DLList::back ( ) [inline]

Definition at line 299 of file DLList.hpp.

                              { if (itemCount) index--;
                          if (index < 0) index = itemCount - 1; }

void DLList::back ( int n ) [inline]

Definition at line 302 of file DLList.hpp.

{ step(-n); }

void * DLList::change_item_to ( void * newBody ) [protected]

Reimplemented in SDLList.

Definition at line 503 of file DLList.cpp.

{
  assert(new_item != NULL);
  if ( !itemCount )
    {
      PRINT_WARNING("DLList: Attempted update of empty list\n");
      return NULL;
    }
  void *temp = listArray[index];
    listArray[index] = new_item;
  return temp;
}

void DLList::clean_out ( ) [inline]

Reimplemented from ArrayBasedContainer.

Definition at line 386 of file DLList.hpp.

{
    itemCount = 0;
    index = 0;
}

void DLList::compress ( ) [virtual]

Reimplemented from ArrayBasedContainer.

Definition at line 525 of file DLList.cpp.

{ 
   int j = 0; 
   int i;
   int new_index = index;

   for ( i = 0; i < itemCount; i++ )
      if (listArray[i] != NULL)
      {
         listArray[j++] = listArray[i];
         if (i < index)
            new_index--;
      }
   
   itemCount = j; 
   index = new_index;
   if (index >= itemCount)
      index = 0;
   nullItem = 0;
}

void * DLList::cut_link ( ) [protected]

Definition at line 124 of file DLList.cpp.

{
    if ( !itemCount )
    {
        PRINT_WARNING("Attempted link removal from empty DLList\n");
        return NULL;
    }

    // save the current value

    void *temp = listArray[index];

    // compress memory

    for ( int i = index; i < itemCount-1; i++ )
    {
        listArray[i] = listArray[i+1];
    }

    itemCount--;
    if ( index >= itemCount )
    {
        index = 0;
    }

    return temp;
}

int DLList::distance_to_nearby_item ( void * body ) [protected]

Definition at line 308 of file DLList.cpp.

{
  int old_index = index;
  move_to_nearby_item( body );
  int distance = abs(index - old_index);
  if ( distance > itemCount / 2 )
    distance = itemCount - distance;
  index = old_index;
  return distance;
}

void * DLList::extract_link ( ) [protected]

Reimplemented in SDLList.

Definition at line 163 of file DLList.cpp.

{
    if ( !itemCount ) {
      PRINT_WARNING("Attempted link removal from empty DLList\n");
      return NULL;
    }
    
    // save the current value
    void *temp = listArray[index];
    
    // assign last node to the current index
    listArray[index] = listArray[itemCount - 1];
    
    // decrement itemCount
    itemCount--;
    if ( index == itemCount && index != 0) {
      // The choices here are index at beginning or end.
      // End seems to work better when 'extract' is being used
      // with calls to 'move_to_item'. 
      index--;
    }
    
    return temp;
}

int DLList::get_index ( )

void * DLList::get_item ( ) const [inline, protected]

Definition at line 334 of file DLList.hpp.

{
    if ( !itemCount ) {
        PRINT_WARNING("Attempted get of empty DLList\n");
        return NULL;
    }
    else {
      assert(listArray[index] != NULL);
      return listArray[index];
    }
}

void * DLList::get_item_and_back ( ) [protected]

Definition at line 285 of file DLList.cpp.

{
    if ( !itemCount )
    {
        PRINT_WARNING("Attempted get_and_back from empty DLList\n");
        return NULL;
    }
    void *temp = listArray[index--];
    if (index < 0) index=itemCount-1;
    assert(temp != NULL);
    return temp;
}

void * DLList::get_item_and_step ( ) [inline, protected]

Definition at line 346 of file DLList.hpp.

{
#ifndef GDSJAAR
    if ( !itemCount )
    {
        PRINT_WARNING("Attempted get_and_step from empty DLList\n");
        return NULL;
    }
    else
#endif
    {
        void *temp = listArray[index++];
        if (index == itemCount) index=0;
        assert(temp != NULL);
        return temp;
    }
}

void DLList::insert_link ( void * newBody ) [protected]

Definition at line 37 of file DLList.cpp.

{
  assert(new_item != NULL);
  // see if the list must be lengthened
  if ( itemCount == listLength )
  {
      lengthen_list();
  }
  
  // set new index
  
  if ( itemCount )
  {
      index++;
  }
  else
  {
      index = 0;
  }
  
  // the item must be put in the current index, all higher
  // indexes must be bubbled up one spot
  
  for ( int i = itemCount; i > index; i-- )
  {
      listArray[i] = listArray[i-1];
  }
  
  listArray[index] = new_item;
  itemCount++;
}

void DLList::insert_link_first ( void * new_item ) [protected]

Reimplemented in SDLList.

Definition at line 113 of file DLList.cpp.

{
  // set index to -1 ... index will be set to 0 in insert_link

  index = -1;
  insert_link(new_item);
}

void DLList::intersect ( DLList & merge_list )

CubitBoolean DLList::is_at_beginning ( ) const [inline]

Definition at line 308 of file DLList.hpp.

{if (!index) return CUBIT_TRUE;
 else return CUBIT_FALSE;}

CubitBoolean DLList::is_at_end ( ) const [inline]

Definition at line 312 of file DLList.hpp.

{
  if (itemCount == 0 || index == itemCount-1)
    return CUBIT_TRUE;
  else
    return CUBIT_FALSE;
}

void DLList::last ( ) [inline]

Definition at line 306 of file DLList.hpp.

{ if (itemCount) index = itemCount - 1; }

void DLList::merge_unique	(	DLList &	merge_list,
		int	merge_list_unique = `CUBIT_FALSE`
	)		`[virtual]`

Reimplemented in SDLList.

Definition at line 71 of file DLList.cpp.

{
   // MJP Note:
   // This procedure could be much more efficient if sorted lists
   // are used. However, I need this procedure at this time to merge
   // DLLists that already exist. These were not created as sorted
   // lists (SDLLists) and it would be painful to convert them to
   // SDLLists. It would be a lot easier if one could simply sort 
   // a DLList based on the numeric values of its items.
   
   // Save the current index of the merge_list
   int current_index = merge_list.index;
   int old_size = size();   
   int i, j, check_index;
   void* new_item = NULL;   

   for (i = 0; i < merge_list.size(); i++)
   {
      // Get the item from the merge_list and insert it into "this"
      // list if it doesn't already exist there.
      new_item = merge_list.get_item_and_step();
      check_index = merge_list_unique ? old_size : size();
      
      for ( j = 0; j < check_index; j++ )
      {
        if ( listArray[j] == new_item )
        {
          check_index = -1;
          break;
        }
      }
      
      if ( check_index != -1 )
        append_link(new_item);
   }
   
   // Restore the original index of the merge_list
   merge_list.index = current_index;
}

CubitBoolean DLList::move_between_items	(	void *	body1,
		void *	body2
	)		`[protected]`

Definition at line 436 of file DLList.cpp.

{
  
  assert(item1 != NULL && item2 != NULL);
  if ( !itemCount )
      return CUBIT_FALSE;
  
  for ( int i = 0; i < itemCount; i++ )
    {
      if ( listArray[i] == item1 )
        {
      //dance around looking for item2
      if ( i+1 < itemCount ) {
        if ( listArray[i+1] == item2 ) {
          index = i+1;
          return CUBIT_TRUE;
        }
      }
      if ( i > 0 ) {
        if ( listArray[i-1] == item2 ) {
          index = i;
          return CUBIT_TRUE;
        }
      }
      if ( ( i+1 == itemCount && listArray[0] == item2 ) 
           || ( i == 0 && listArray[itemCount-1] == item2 ) )
        {
          index = 0;
          return CUBIT_TRUE;
        }
    }
    }
  return CUBIT_FALSE;
}

void * DLList::move_to_and_remove_item ( void * item ) [protected]

Definition at line 300 of file DLList.cpp.

{
  if (move_to_item(item))
    return cut_link();
  else
    return (void*) NULL;
}

CubitBoolean DLList::move_to_item ( void * body ) [protected]

Definition at line 379 of file DLList.cpp.

{
  int item_position = where_is_item( item );
  if ( item_position >= 0 ) {
    index = item_position;
    return CUBIT_TRUE;
  }
  return CUBIT_FALSE;
}

CubitBoolean DLList::move_to_nearby_item ( void * body ) [protected]

Definition at line 320 of file DLList.cpp.

{
      // empty list
  if (itemCount == 0) 
    return CUBIT_FALSE;
  
  // Search current item first...
  void **ptr_up = &(listArray[index]);
  if (*ptr_up == item) 
    return CUBIT_TRUE;

  int i_up, i_down;
  i_up = i_down = index;
  void **ptr_down = ptr_up;
  while (1) 
  {
      // check forward in the list
      // increment
    if ( ++i_up < itemCount )
      ptr_up++;
    else
    {
      i_up = 0;
      ptr_up = listArray;
    }
      // check
    if ( *ptr_up == item )
    {
      index = i_up;
      return CUBIT_TRUE;
    }
    if ( i_up == i_down )
    {
      return CUBIT_FALSE;
    }
    
      // check backward in the list
      // increment
    if ( --i_down >= 0 )
      ptr_down--;
    else
    {
      i_down = itemCount-1;
      ptr_down = &(listArray[i_down]);
    }
      // check
    if ( *ptr_down == item )
    {
      index = i_down;
      return CUBIT_TRUE;
    }
    if ( i_up == i_down )
    {
      return CUBIT_FALSE;
    }
    
  }
}

void * DLList::next_item ( int n = 1 ) const [inline, protected]

Definition at line 364 of file DLList.hpp.

{
    if ( !itemCount )
    {
        PRINT_WARNING("Attempted next of empty DLList\n");
        return NULL;
    }
    else
    {
        // return the proper index
        // beware of negative n leading to negative new_index
        int new_index = index+n;
    while (new_index < 0)
      new_index += itemCount;

    new_index = new_index%itemCount;

        assert(listArray[new_index] != NULL);
        return listArray[new_index];
    }
}

void * DLList::nullify_link ( ) [protected]

Definition at line 235 of file DLList.cpp.

{
    if ( !itemCount )
    {
        PRINT_WARNING("Attempted link nullify from empty DLList\n");
        return NULL;
    }

    // save the current value
      nullItem = listArray[index];
      listArray[index] = 0;
    return nullItem;
}

CubitBoolean DLList::omit_link ( void * oldObjPtr ) [protected]

Definition at line 195 of file DLList.cpp.

{
    int scan_index;
    int squeeze_index = 0;
    CubitBoolean found = CUBIT_FALSE;
    for(scan_index = 0; scan_index < itemCount; ++scan_index)
    {
        if(listArray[scan_index] == oldObjPtr)
        {
            found = CUBIT_TRUE;
            if(index == scan_index) index = squeeze_index - 1;
        }
        else 
        {
            if(scan_index != squeeze_index)
            {
                listArray[squeeze_index] = listArray[scan_index];
                if(index == scan_index) index = squeeze_index;
            }
            ++squeeze_index;
        }
    }

    if(found)
    {
        itemCount = squeeze_index;
//+//   If the first item was deleted and index pointed to it, make an
//+//   adjustment here. If itemCount is zero, don't assign -1 again.
        if (index < 0)
      index = (itemCount) ? (itemCount - 1) : 0 ;
    if (index >= itemCount)
      index = (itemCount) ? (itemCount - 1) : 0 ;
    }

    return found;
}

int DLList::operator!= ( const DLList & list ) const

Definition at line 595 of file DLList.cpp.

{
    return (itemCount != list.itemCount) || !(list >= *this);
}

int DLList::operator<= ( const DLList & list ) const

Definition at line 574 of file DLList.cpp.

{
    return list >= *this;
}

DLList & DLList::operator= ( const DLList & from )

Definition at line 516 of file DLList.cpp.

{
  if (this != &from) {
    ArrayBasedContainer::operator=(from);
    index = from.index;
  }
  return *this;
}

int DLList::operator== ( const DLList & list ) const

Definition at line 590 of file DLList.cpp.

{
    return (itemCount == list.itemCount) && (list >= *this);
}

int DLList::operator> ( const DLList & list ) const

Definition at line 569 of file DLList.cpp.

{
    return (itemCount > list.itemCount) && (*this >= list);
}

int DLList::operator>= ( const DLList & list ) const

Definition at line 579 of file DLList.cpp.

{
    if( itemCount < list.itemCount ) return 0;
    
    DLList temp_list = list;
    for( int i = 0; i < itemCount; i++ )
        if( temp_list.move_to_item( listArray[i] ) ) temp_list.extract_link();
    
    return temp_list.itemCount == 0;  
}

void * DLList::prev_item ( int n = 1 ) const [protected]

Definition at line 249 of file DLList.cpp.

{
    if ( !itemCount )
    {
        PRINT_WARNING("Attempted prev of empty DLList\n");
        return NULL;
    }

    // return the proper index
    // beware of negative n
    int new_index = index - n;

    while (new_index < 0)
      new_index += itemCount;
    // beware of negative n leading to new_index >itemCount
    new_index = new_index%itemCount;

    assert(listArray[new_index] != NULL);
    return listArray[new_index];
}

void DLList::reset ( ) [inline]

Definition at line 304 of file DLList.hpp.

{ index = 0; }

void DLList::reverse ( )

Definition at line 546 of file DLList.cpp.

{
  int front = 0; 
  int tail  = itemCount-1;
  void *temp;
  
  while (front < tail) {
    temp             = listArray[front];
    listArray[front] = listArray[tail];
    listArray[tail]  = temp;
    tail--;
    front++;
  }
}

void DLList::set_index ( int new_index )

DLList::SetDynamicMemoryAllocation ( memoryManager ) const

void DLList::shrink ( int k )

Reimplemented from ArrayBasedContainer.

void DLList::step ( ) [inline]

Definition at line 283 of file DLList.hpp.

                              { if (itemCount) index++; 
                                  if (index >= itemCount) index = 0;}

void DLList::step ( int n ) [inline]

Definition at line 286 of file DLList.hpp.

                               {
  if (itemCount) {
    index += n;
    if (index < 0)   {
      index = itemCount - (-index)%itemCount;
    }
    if (index >= itemCount) {
      index %= itemCount;
    }
  }
}

void * DLList::step_and_get_item ( ) [protected]

Definition at line 270 of file DLList.cpp.

{
    if ( !itemCount )
    {
        PRINT_WARNING("Attempted step_and_get from empty DLList\n");
        return NULL;
    }

    if (++index == itemCount)
      index=0;
    void *temp = listArray[index];
    assert(temp != NULL);
    return temp;
}

static const char* DLList::type ( ) [inline, static, private]

Definition at line 274 of file DLList.hpp.

{ return "DLList"; }

int DLList::where_is_item ( void * item ) const [protected]

Definition at line 389 of file DLList.cpp.

{
  // test for null input item
  assert(item != NULL);

  if (itemCount == 0) return -1;
  
  // loop through list searching for item ...
  // if found set index and return true

  // Search current item first...
  void **ptr = &(listArray[index]);
  if (*ptr == item) return index;

  // Now, search from current index to end of array
  int i;
  for (i=index+1; i < itemCount; i++) {
    ptr++;
    if ( *ptr == item) {
        // check if move_to_nearby would have been better
        //if ( i - index > 1000 )
        // PRINT_INFO(" Found, i = %d, index = %d, itemCount = %d.\n",
        //           i, index, itemCount);
      return i;
    }
  }
  
  // Now search from beginning of array to index...
  ptr = listArray;
  for (i = 0; i < index; i++) {
    if (*ptr == item) {
        // check if move_to_nearby would have been better
        // if ( i + itemCount - index > 1000 )
        // PRINT_INFO(" Found, i = %d, index = %d, itemCount = %d.\n",
        //           i, index, itemCount);
      return i;
    }
    ptr++;
  }
  
  // item is not in array, return false
  return -1;
}

Member Data Documentation

int DLList::index [protected]

Definition at line 267 of file DLList.hpp.

MemoryManager DLList::memoryManager [static, private]

Reimplemented in SDLList.

Definition at line 277 of file DLList.hpp.

void* DLList::nullItem [protected]

Definition at line 253 of file DLList.hpp.

The documentation for this class was generated from the following files:

Public Member Functions

Protected Member Functions

Protected Attributes

Static Private Member Functions

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation