#include <SDLList.hpp>

Inheritance diagram for SDLList:

Public Member Functions
	SDLList (int size)
	SDLList (const SDLList &copy_from)
	SDLList (const DLList &copy_from)
virtual	~SDLList ()
SDLList &	operator= (const SDLList &)
virtual void	merge_unique (DLList &merge_list, int merge_list_unique)
SetDynamicMemoryAllocation(memoryManager) protected void	insert_link_first (void *new_item)
void	append_link (void *newBody)
void *	extract_link ()
void *	change_item_to (void *newBody)
void	sort_list ()
CubitBoolean	move_to_item_sorted (void *value)
void	insert_item_sorted (void value, void new_item)
void *	move_to_and_remove_item_sorted (void *value)
void	set_sorted_flag (const int sorted_flag)
CubitBoolean	where_is_item_sorted (void *value, int &item_index)
Public Attributes
int(*	compare_order_obj )(void object_1, void object_2)
int(*	compare_order )(void object_1, void object_2)
int(*	compare_equal )(void object_1, void object_2)
Private Member Functions
void	binary_search (int min_location, int max_location, void *item) const
Static Private Attributes
static MemoryManager	memoryManager

Detailed Description

Definition at line 42 of file SDLList.hpp.

Constructor & Destructor Documentation

SDLList::SDLList ( int size )

Definition at line 19 of file SDLList.cpp.

                                : DLList( increment )
{}

SDLList::SDLList ( const SDLList & copy_from )

Definition at line 23 of file SDLList.cpp.

                                    : DLList(from)
{
  listIsSorted = from.listIsSorted;
}

SDLList::SDLList ( const DLList & copy_from )

Definition at line 29 of file SDLList.cpp.

                                   : DLList(from)
{
  listIsSorted = CUBIT_FALSE;
}

SDLList::~SDLList ( ) [virtual]

Definition at line 34 of file SDLList.cpp.

{
}

Member Function Documentation

void SDLList::append_link ( void * newBody ) [inline]

Reimplemented from DLList.

Definition at line 161 of file SDLList.hpp.

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

    if ( itemCount == listLength )
        lengthen_list();

    listArray[itemCount++] = new_item;
}

void SDLList::binary_search	(	int *	min_location,
		int *	max_location,
		void *	item
	)		const `[private]`

Definition at line 143 of file SDLList.cpp.

{
  // sort the list if necessary and initialize binary search parameters
  assert( listIsSorted );

  *min_location = 0;
  *max_location = itemCount - 1;
  int bracket_width = *max_location;
  int compare_location = itemCount >> 1;

    // bracket the location (binary search)

  while(bracket_width > 1)
  {
    if ((*compare_order)(item, listArray[compare_location]))
    {
      *min_location     = compare_location;
      bracket_width     = *max_location - *min_location;
      compare_location += (bracket_width >> 1);
    }
    else
    {
      *max_location     = compare_location;
      bracket_width     = *max_location - *min_location;
      compare_location -= (bracket_width >> 1);
    }
  }

    // if there are duplicate entries in the list, bracket them with min_location
    // and max_location
  while (  *min_location > 0 && (*compare_equal)(item, listArray[*min_location-1]))
    (*min_location)--;

    // (max_location already backets the item)
  
}

void * SDLList::change_item_to ( void * newBody )

Reimplemented from DLList.

Definition at line 77 of file SDLList.cpp.

{
  listIsSorted = CUBIT_FALSE;
  return DLList::change_item_to(new_item);
}

void * SDLList::extract_link ( )

Reimplemented from DLList.

Definition at line 70 of file SDLList.cpp.

{
  listIsSorted = CUBIT_FALSE;
  return DLList::extract_link();
}

void SDLList::insert_item_sorted	(	void *	value,
		void *	new_item
	)

Definition at line 242 of file SDLList.cpp.

{
  assert(new_item != NULL);

  // if entries exist then find insertion index

  if ( itemCount > 0)
  {
    // perform the binary search and set index to the min_location

    int min_location, max_location;
    if (!listIsSorted)
    {
      sort_list();
    }
    binary_search(&min_location, &max_location, value);
    index = min_location;

    // test for special cases (insert first or last)

    if (index == 0)
    {
      // if new_items value < first (ascending) or new_items value > first
      // (descending) then insert as first item (index = -1)

      if (!(*compare_order)(value, listArray[index]))
      {
        index--;
      }
    }
    if (index == (itemCount - 2))
    {
      // if new_items value > last (ascending) or new_items value < last
      // (descending) then insert as last item (index = itemCount - 1)

      if ((*compare_order)(value, listArray[index + 1]))
      {
        index++;
      }
    }
  }

  // insert new_item
  insert_link(new_item);
  listIsSorted = CUBIT_TRUE;
}

void SDLList::insert_link_first ( void * new_item )

Reimplemented from DLList.

Definition at line 54 of file SDLList.cpp.

{
  DLList::insert_link_first(new_item);
  listIsSorted = CUBIT_FALSE;
}

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

Reimplemented from DLList.

Definition at line 47 of file SDLList.cpp.

{
  DLList::merge_unique(merge_list, merge_list_unique);
  listIsSorted = CUBIT_FALSE;
}

void * SDLList::move_to_and_remove_item_sorted ( void * value )

Definition at line 293 of file SDLList.cpp.

{
  if (move_to_item_sorted(value))
    return cut_link();
  else
    return (void*) NULL;
}

CubitBoolean SDLList::move_to_item_sorted ( void * value )

Definition at line 183 of file SDLList.cpp.

{
  int item_index;
  CubitBoolean item_exists = where_is_item_sorted( value, item_index );
  index = item_index; // always
  return item_exists;
}

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

Definition at line 302 of file SDLList.cpp.

{
  if (this != &from) {
    DLList::operator=(from);
  }
  return *this;
}

void SDLList::set_sorted_flag ( const int sorted_flag ) [inline]

Definition at line 172 of file SDLList.hpp.

{
    listIsSorted = sorted_flag;
}

void SDLList::sort_list ( )

Definition at line 87 of file SDLList.cpp.

{
  listIsSorted = CUBIT_TRUE;
  if (itemCount > 1)
  {
    int mid = (itemCount >> 1) + 1;
    int ir = itemCount;
    void* temp_element = NULL;

    while(CUBIT_TRUE)
    {
      if (mid > 1)
      {
    mid--;
    temp_element = listArray[mid - 1];
      }
      else
      {
    ir--;
    temp_element = listArray[ir];
    listArray[ir] = listArray[0];
    if (ir == 1)
    {
      listArray[0] = temp_element;
      return;
    }
      }

      int i = mid;
      int j = mid + mid;

      while (j <= ir)
      {
    if (j < ir)
    {
       if ((*compare_order_obj)(listArray[j], listArray[j - 1])) j++;
    }
    if ((*compare_order_obj)(listArray[j - 1], temp_element))
    {
      listArray[i - 1] = listArray[j - 1];
      i = j;
      j += j;
    }
    else
    {
      j = ir + 1;
    }
      }

      listArray[i - 1] = temp_element;
    }
  }
}

CubitBoolean SDLList::where_is_item_sorted	(	void *	value,
		int &	item_index
	)

Definition at line 196 of file SDLList.cpp.

{
  // if entries exist then find insertion index

  if ( 0 == itemCount ) {
    insert_index = 0;
    return CUBIT_FALSE;
  }
  
  if (!listIsSorted)
  {
    sort_list();
  }

  // perform the binary search
  
  int min_location, max_location;
  binary_search(&min_location, &max_location, value);
  
  // if item occupies a place in the list then min_location and/or
  // max_location specifies the location ... otherwise item was not found
  
  if ((*compare_equal)(value, listArray[min_location]))
    {
      insert_index = min_location;
      return CUBIT_TRUE;
    }
  else if ((*compare_equal)(value, listArray[max_location]))
    {
      insert_index = max_location;
      return CUBIT_TRUE;
    }  
  // else not found, 
  insert_index = min_location;
  // is it beyond the end?
  if (itemCount == max_location ) {
    if ((*compare_order)(value, listArray[max_location]))
      insert_index = itemCount;
  }
  return CUBIT_FALSE;
}

Member Data Documentation

int(* SDLList::compare_equal)(void *object_1, void *object_2)

Definition at line 133 of file SDLList.hpp.

int(* SDLList::compare_order)(void *object_1, void *object_2)

Definition at line 132 of file SDLList.hpp.

int(* SDLList::compare_order_obj)(void *object_1, void *object_2)

Definition at line 131 of file SDLList.hpp.

MemoryManager SDLList::memoryManager [static, private]

Reimplemented from DLList.

Definition at line 152 of file SDLList.hpp.

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

Public Member Functions

Public Attributes

Private Member Functions

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation