cgma
SDLList Class Reference

#include <SDLList.hpp>

Inheritance diagram for SDLList:
DLList ArrayBasedContainer

List of all members.

Public Member Functions

 SDLList (int size)
 SDLList (const SDLList &copy_from)
 SDLList (const DLList &copy_from)
virtual ~SDLList ()
SDLListoperator= (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.

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.

Reimplemented from DLList.

Definition at line 70 of file SDLList.cpp.

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.

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;
}

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;
}

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.

Reimplemented from DLList.

Definition at line 152 of file SDLList.hpp.


The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines