dag_sort.C

Go to the documentation of this file.

// dag_sort.C
//
// 2/11/98 WAH:  Broke away from Scheduler package; minor patching up.

/* Comparsion routines for sorting */

/***************** BEGIN *****************/

#if defined (_STL_SORTING_)
// Dummy method, to test the use of compare functions
static int CompareNodeIds( BigListElement NodeOne, BigListElement NodeTwo )
{
   int rc;

   derr( ">> dag::CompareNodeIds\n" );
   rc = NodeOne.GetOp()->GetOpId() > NodeTwo.GetOp()->GetOpId();
   derr( "   Op 1-" << NodeOne.GetOp()->GetOpId() << ", Op 2-"
         << NodeTwo.GetOp()->GetOpId() << "\n" );
   derr( "<< dag::CompareNodeIds\n" );
   return rc;
}

static int CompareNodeHeights( BigListElement NodeOne, BigListElement NodeTwo )
{ return NodeOne.GetHeight() > NodeTwo.GetHeight(); }

static int CompareNodeValues( BigListElement NodeOne, BigListElement NodeTwo )
{ return NodeOne.Value > NodeTwo.Value; }

#else

static int CompareNodeIds( BigListElement *NodeOne, BigListElement *NodeTwo )
{
   int rc;

   derr( ">> dag::CompareNodeIds\n" );
   rc = NodeOne->GetOp()->GetOpId() > NodeTwo->GetOp()->GetOpId();
   derr( "   Op 1-" << NodeOne->GetOp()->GetOpId() << ", Op 2-"
         << NodeTwo->GetOp()->GetOpId() << "\n" );
   derr( "<< dag::CompareNodeIds\n" );
   return rc;
}

static int CompareNodeHeights( BigListElement *NodeOne,
                               BigListElement *NodeTwo )
{ return NodeOne->GetHeight() > NodeTwo->GetHeight(); }

static int CompareNodeValues( BigListElement *NodeOne,
                              BigListElement *NodeTwo )
{ return NodeOne->Value > NodeTwo->Value; }

#endif



// SetVectorPtrs
void dag::SetVectorPtrs( vector < SmallListElement > *List )
{
   int i, index, size, OpId;


   derr( ">> SetVectorPtrs\n" );
   size = List->size();
   for ( i = 0; i < size; i++ ) {

      SmallListElement *small_element = &(*List)[i];

      OpId = small_element->GetOp()->GetOpId();
      derr( "   Find Op " << OpId << "..." );
#if defined (_STL_LIST_USED_)
      index = FindOpInList( &Vector, OpId );
#else if defined (_STL_VECTOR_USED_)
      index = FindOpInList( &MasterList, OpId );
#endif
      derr( "found at index " << index << "\n" );
#if defined (_STL_LIST_USED_)
      small_element->SetDagEntry( &(Vector[ index ]) );
#else if defined (_STL_VECTOR_USED_)
      small_element->SetDagEntry( &(MasterList[ index ]) );
#endif
      derr( "   Entry ptr set "
            << small_element->GetDagEntry()->GetOp()->GetOpId() << "\n" );
   }
   derr( "<< SetVectorPtrs\n" );
}


// SetSublistPtrs:
void dag::SetSublistPtrs( VectorList *V )
{
   VectorList::iterator VectorFront, VectorBack;


   // Reset the ptrs from the SmallListElement lists into the MainList
   derr( ">> SetSubListPtrs\n" );
   for ( VectorFront = V->begin(), VectorBack = V->end();
         VectorFront != VectorBack; VectorFront++ ) {
      derr( "   Op " << (*VectorFront).GetOp()->GetOpId()
            << ", Set Predecessor Ptrs\n" );
      SetVectorPtrs( (*VectorFront).Predecessors );
      derr( "   Set Successor Ptrs\n" );
      SetVectorPtrs( (*VectorFront).Successors );
   }
   derr( "<< SetSubListPtrs\n" );
}


// CopyListToVector: Since the current STL version doesn't support passing
//    an arbitrary sort function to a list, the list has to be copied to a
//    vector, which is then sorted
void dag::CopyListToVector( MainList::iterator ListFront,
                            MainList::iterator ListBack )
{
   VectorList::iterator VectorFront, VectorBack;
   BigListElement Element;


   FunctionName = "CopyListToVector() w/iterators";
   derr( ">> CopyListToVector w/iterators\n" );
   for ( ; ListFront != ListBack; ListFront++ ) {

      BigListElement *Element1;

      Element1 = new BigListElement( *ListFront );
#if defined (_STL_LIST_USED_)
      Vector.push_back( *Element1 );
#endif
#if defined (_DAG_DEBUG_)
      Element1->PrintElement();
#endif
   }
   derr( "<< CopyListToVector w/iterators\n" );
}

#if 1
// CopyVectorToVector:
void dag::CopyVectorToVector( VectorList *v1, VectorList *v2 )
{
   VectorList::iterator VectorFront, VectorBack;


   FunctionName = "CopyVectorToVector()";
   derr( ">> CopyVectorToVector\n" );
   v2->reserve( v1->size() );
   for ( VectorFront = v1->begin(), VectorBack = v1->end();
         VectorFront != VectorBack; VectorFront++ ) {

      BigListElement *Element1;

      Element1 = new BigListElement( *VectorFront );
      v2->push_back( *Element1 );
   }

   // Reset the ptrs from the SmallListElement lists into the MainList
   SetSublistPtrs( v2 );
   derr( "<< CopyVectorToVector\n" );
}
#endif


#if defined (_STL_LIST_USED_)
// CopyListToVector: Since the current STL version doesn't support passing
//    an arbitrary sort function to a list, the list has to be copied to a
//    vector, which is then sorted
void dag::CopyListToVector()
{
   MainList::iterator ListFront, ListBack;
   VectorList::iterator VectorFront, VectorBack;
   BigListElement Element;


   FunctionName = "CopyListToVector()()";
   derr( ">> CopyListToVector\n" );

   // Assume that new insertions into the list will expand the vector
   // by no more than 100%.
   Vector.reserve( 2 * MasterList.size() );
   for ( ListFront = MasterList.begin(), ListBack = MasterList.end();
         ListFront != ListBack; ListFront++ ) {

      BigListElement *Element1;

      Element1 = new BigListElement( *ListFront );
      // cerr << "** Copy constructing Op " << (*ListFront).GetOp()->GetOpId()
      //      << "\n";
      Vector.push_back( *Element1 );
   }

   // Reset the ptrs from the SmallListElement lists into the MainList
   SetSublistPtrs( &Vector );
   derr( ">> About to DestructBigList\n" );
   DestructBigList( &MasterList );
   derr( "<< Done w/DestructBigList\n" );
   VectorActive = 1;
   derr( "<< CopyListToVector\n" );
}
#endif


// BubbleSort
void dag::BubbleSort( vector < BigListElement >::iterator Begin,
                      vector < BigListElement >::iterator End,
                      int (*Compare)( BigListElement *, BigListElement * ) )
{
   int i;
   BigListElement *Element, Element1;
   vector < BigListElement >::iterator Front, Back, SubFront, SubBack, Max;


   derr( ">> BubbleSort\n" );
   FunctionName = "BubbleSort() w/iterators";

   // Until all nodes are examined, continue
   for ( i = 0, Front = Begin, Back = End; Front != Back; Front++, i++ ) {

      // Set the current list element as the maximum element
      Max = Front;

      // Compare all elements from this one down to the end
      // Keep an iterator to the largest one found
      for ( SubFront = Front; SubFront != Back; SubFront++ ) {
         if ( Compare( &(*SubFront), &(*Max) ) == 1 )
            Max = SubFront;
      }
      derr( "   ** New Max: Op " << (*Max).GetOp()->GetOpId() << "\n" );

      // Place the new max element into the n-th place in the list. If
      // the max element is the same as before the list was examined,
      // there is no need for the copy.
      if ( Max != Front ) {
         derr( "   Swapping Ops " << (*Max).GetOp()->GetOpId()
               << " and " << (*Front).GetOp()->GetOpId() << "\n" );
         Element = new BigListElement( *Max );
//       delete Max;
         *Max = *Front;
         *Front = *Element;
      }
   }
   derr( "<< BubbleSort\n" );
}


// BubbleSort
void dag::BubbleSort( int (*Compare)( BigListElement *, BigListElement * ) )
{
   int i, size;
   BigListElement *Element, Element1;
   vector < BigListElement >::iterator Front, Back, SubFront, SubBack, Max;


   derr( ">> BubbleSort\n" );
   FunctionName = "BubbleSort() w/ptrs";

   // Until all nodes are examined, continue
#if defined (_STL_LIST_USED_)
   for ( size = Vector.size(), i = 0, Front = Vector.begin(),
         Back = Vector.end(); Front != Back; Front++, i++ ) {
#else if defined (_STL_VECTOR_USED_)
   for ( size = MasterList.size(), i = 0, Front = MasterList.begin(),
         Back = MasterList.end(); Front != Back; Front++, i++ ) {
#endif

      // Set the current list element as the maximum element
      Max = Front;

      // Compare all elements from this one down to the end
      // Keep an iterator to the largest one found
      for ( SubFront = Front; SubFront != Back; SubFront++ ) {
         if ( Compare( &(*SubFront), &(*Max) ) == 1 )
            Max = SubFront;
      }
      derr( "   ** New Max: Op " << (*Max).GetOp()->GetOpId() << "\n" );

      // Place the new max element into the n-th place in the list. If
      // the max element is the same as before the list was examined,
      // there is no need for the copy.
      if ( Max != Front ) {
         derr( "   Swapping Ops " << (*Max).GetOp()->GetOpId()
               << " and " << (*Front).GetOp()->GetOpId() << "\n" );
         Element = new BigListElement( *Max );
//       delete Max;
#if defined (_STL_LIST_USED_)
         *Max = Vector[ i ];
         Vector[ i ] = *Element;
#else if defined (_STL_VECTOR_USED_)
         *Max = MasterList[ i ];
         MasterList[ i ] = *Element;
#endif
      }
   }
   derr( "<< BubbleSort\n" );
}


// SortByOpId: sorts the MasterList by the Op Id of each node
void dag::SortByOpId()
{
   vector < BigListElement >::iterator Front, Back;


   derr( ">> SortByOpId\n" );
#if defined (_STL_LIST_USED_)
#if defined (_STL_SORTING_)
   stable_sort( Vector.begin(), Vector.end(), CompareNodeIds );
#else
   BubbleSort( Vector.begin(), Vector.end(), CompareNodeIds );

   // Reset the ptrs from the SmallListElement lists into the MainList
   SetSublistPtrs( &Vector );
#endif
#else if defined (_STL_VECTOR_USED_)
#if defined (_STL_SORTING_)
   sort( MasterList.begin(), MasterList.end(), CompareNodeIds );
#else
   BubbleSort( MasterList.begin(), MasterList.end(), CompareNodeIds );

   // Reset the ptrs from the SmallListElement lists into the MainList
   SetSublistPtrs( &MasterList );
#endif
#endif

   // Sort the sub-lists
#if defined (_STL_LIST_USED_)
   for ( Front = Vector.begin(), Back = Vector.end(); Front != Back;
         Front++ ) {
#else if defined (_STL_VECTOR_USED_)
   for ( Front = MasterList.begin(), Back = MasterList.end(); Front != Back;
         Front++ ) {
#endif
      (*Front).SortSuccessorsByOpId();
      (*Front).SortPredecessorsByOpId();
   }

   derr( "<< SortByOpId\n" );
}


// SortByHeight: sorts the MasterList by the height of each node
void dag::SortByHeight()
{
   vector < BigListElement >::iterator Front, Back;


   derr( ">> SortByHeight\n" );
#if defined (_STL_LIST_USED_)
#if defined (_STL_SORTING_)
   stable_sort( Vector.begin(), Vector.end(), CompareNodeHeights );
#else
   BubbleSort( Vector.begin(), Vector.end(), CompareNodeHeights );

   // Reset the ptrs from the SmallListElement lists into the MainList
   SetSublistPtrs( &Vector );
#endif
#else if defined (_STL_VECTOR_USED_)
#if defined (_STL_SORTING_)
   sort( MasterList.begin(), MasterList.end(), CompareNodeHeights );
#else
   BubbleSort( MasterList.begin(), MasterList.end(), CompareNodeHeights );

   // Reset the ptrs from the SmallListElement lists into the MainList
   SetSublistPtrs( &MasterList );
#endif
#endif

   // Sort the sub-lists
#if defined (_STL_LIST_USED_)
   for ( Front = Vector.begin(), Back = Vector.end(); Front != Back;
         Front++ ) {
      (*Front).SortSuccessorsByHeight();
      (*Front).SortPredecessorsByHeight();
   }
#else if defined (_STL_VECTOR_USED_)
   for ( Front = MasterList.begin(), Back = MasterList.end(); Front != Back;
         Front++ ) {
      (*Front).SortSuccessorsByHeight();
      (*Front).SortPredecessorsByHeight();
   }
#endif

   derr( "<< SortByHeight\n" );
}


// SortByValue: sorts the MasterList by the Value field of each node
void dag::SortByValue()
{
   vector < BigListElement >::iterator Front, Back;


   derr( ">> SortByValue\n" );
#if defined (_STL_LIST_USED_)
#if defined (_STL_SORTING_)
   sort( Vector.begin(), Vector.end(), CompareNodeValues );
#else
   BubbleSort( Vector.begin(), Vector.end(), CompareNodeValues );

   // Reset the ptrs from the SmallListElement lists into the MainList
   SetSublistPtrs( &Vector );
#endif
#else if defined (_STL_VECTOR_USED_)
#if defined (_STL_SORTING_)
   sort( MasterList.begin(), MasterList.end(), CompareNodeValues );
#else
   BubbleSort( MasterList.begin(), MasterList.end(), CompareNodeValues );

   // Reset the ptrs from the SmallListElement lists into the MainList
   SetSublistPtrs( &MasterList );
#endif
#endif

   // Sort the sub-lists
#if defined (_STL_LIST_USED_)
   for ( Front = Vector.begin(), Back = Vector.end(); Front != Back;
         Front++ ) {
#else if defined (_STL_VECTOR_USED_)
   for ( Front = MasterList.begin(), Back = MasterList.end(); Front != Back;
         Front++ ) {
#endif
      (*Front).SortSuccessorsByValue();
      (*Front).SortPredecessorsByValue();
   }
   derr( "<< SortByValue\n" );
}

/****************** END ******************/

---