/*
 *
 *  Name:           partitionEntries
 *  Input:          input list of index entries, I
 *                  integer fan value, fan
 *  Output:         output list of index entries, A
 *                  output list of index entries, B
 *  Return:         void
 *  Description:    Separate input list of index entries into two groups.  The 
 *                  method used for partitioning the entries is extremely 
 *                  implementation dependent.  The basic idea is to set-up the 
 *                  two output index entry lists to have minimal bounding 
 *                  index keys which will improve later queries on the index, 
 *                  since fewer branches of the index tree will need to be 
 *                  traversed to satisfy the query command.  However, the 
 *                  method itself is probably the most computationally 
 *                  expensive of the insertion subroutines, because multiple 
 *                  loops through the index entry lists and volume 
 *                  calculations are required for true "minimal" bounding index 
 *                  keys to be determined.  If multiple branch searches is not 
 *                  prohibitive, i.e., a parallel search is possible or query 
 *                  response time is not time consuming relative to an insert 
 *                  operation, then the partition subroutine can use a 
 *                  sub-minimal approach.  In fact, the partition can simply 
 *                  split the input list into two equal groups ignoring the 
 *                  bounding index keys completely.  The effect will be to 
 *                  cause new traversals of the index to descend multiple 
 *                  branches, but this trade-off may be acceptable for a given 
 *                  implementation.
 *
 *                  On entrance, the input list, I, should have at least 
 *                  MINIMUM_FAN_SIZE entries and nor more than 2 * fan entries, 
 *                  and the output lists, A and B, should be empty(NULL).  On 
 *                  exit, the input list, I, is empty(NULL) and the output 
 *                  lists, A and B, have the partitioned entries (both are 
 *                  non-NULL).  Each list is ready for insertion into an 
 *                  IndexNode.
 *  Calls:          errorMessage()
 *                  keyUnion()
 *                  penalty()
 *                  volume()
 *      System:     
 *  Author:         M.L.Rivas
 *
 *  Revision History:
 *  Date    Name            Revision
 *  ------- --------------- ------------------------------
 *  24May99 Matthew Rivas   Created
 *
 *              Copyright 1999, Atlantic Aerospace Electronics Corp.
 */

#include <assert.h>         /* for assert()                   */
#include <stdlib.h>         /* for NULL definition            */
#include "dataManagement.h" /* for primitive type definitions */
#include "errorMessage.h"   /* for errorMessage() definition  */
#include "index.h"          /* for IndexEntry definition      */
#include "indexKey.h"       /* for IndexKey definition        */

/*
 *  Function prototypes
 */
extern Float penalty( IndexEntry A, IndexEntry B );
extern Float volume( IndexKey key );
extern void keyUnion( IndexKey *A, IndexKey *B, IndexKey *U );

void partitionEntries( IndexEntry *I,   /*  input entry list to partition */
                       Int fan,         /*  fan or order of index         */
                       IndexEntry **A,  /*  1st group partitioned entries */
                       IndexEntry **B ) /*  2nd group partitioned entries */
{   /* beginning of partitionEntries()  */
    IndexEntry *entry1;        /* looping entry to find first entry of groups */
    IndexEntry *entry2;        /* looping entry to find first entry of groups */
    IndexEntry *currentEntry;  /* looping entry for input list                */
    IndexEntry *previousEntry; /* looping entry for input list                */
    IndexEntry *tempA;         /* temp entry to find first entry of group A   */
    IndexEntry *tempB;         /* temp entry to find first entry of group B   */
    IndexKey    unionAB;       /* union of first entries of group A and B     */
    Float       volumeAB;      /* volume of first entries of group A and B    */
    Int         sizeOfGroupA;  /* current size of group A                     */
    Int         sizeOfGroupB;  /* current size of group B                     */

    static Char name[] = "partitionEntries";

    assert( I && I->next );     /*  need at least two entries to partition  */
    assert( MINIMUM_FAN_SIZE > 1 );
    assert( fan >= MINIMUM_FAN_SIZE );

    /*
     *  Find "worst" combination of all entries in I.  The worst combination is 
     *  the one which produces the largest bounding index key, i.e., the 
     *  largest hyper-cube volume.  The two entries which form the worst combo 
     *  will be the first entries into the two groups, A and B.  The method 
     *  used to find the worst combo is straight forward enumeration of all 
     *  possible combinations.  Note that only forward combinations are 
     *  necessary since the volume( union( A, B ) ) is the same as the 
     *  volume( union( B, A ) ).  The first candidate pair for the worst case 
     *  are chosen as the first and second entries of the input list, I.
     */
    *A       = I;
    *B       = I->next;
    keyUnion( &(*A)->key, &(*B)->key, &unionAB );
    volumeAB = volume( unionAB );

    /*
     *  A double loop through the input list, I, is used to find all 
     *  combinations.
     */
    for ( entry1 = I; entry1 != NULL; entry1 = entry1->next ) {
        for ( entry2 = entry1->next; entry2 != NULL; entry2 = entry2->next ) {
            IndexKey    tempKey;
            Float       tempVolume;
            
            /*
             *  If this combination produces a worse penalty, then replace old 
             *  candidates with new pair.
             */
            keyUnion( &entry1->key, &entry2->key, &tempKey );
            tempVolume = volume( tempKey );

            if ( tempVolume > volumeAB ) {
               *A       = entry1;
               *B       = entry2;
               unionAB  = tempKey;
               volumeAB = tempVolume;
            }   /*  end of if ( tempVolume > volumeAB )   */
        }   /*  end of loop for entry2  */
    }   /* end of loop for entry1   */

    /*
     *  The entry pointers, A and B, now point to the first entries of the 
     *  two groups which are forming during the partition. Remove them from the 
     *  input list, I. Set the size of each group to one for the initial 
     *  entries.  The entries of I which correspond to A and B are 
     *  found by comparing pointer values.
     */
    currentEntry  = I;      /*  current entry  (starts at beginning of I)   */
    previousEntry = NULL;   /*  previous entry (NULL for first entry)       */
    while ( currentEntry != NULL ) {
        if ( currentEntry == *A || currentEntry == *B ) {
            /*
             *  Found A or B in list as currentEntry. Remove current entry from 
             *  list, checking for special case where current entry is the head 
             *  of list, i.e., no previous entry.
             */
            if ( previousEntry == NULL ) {
                /*
                 *  No previous pointer means that the current entry is the 
                 *  head of the list.  Removing the entry means updating I and 
                 *  reseting the values for currentEntry and previousEntry.
                 */
                I             = currentEntry->next;
                currentEntry  = I;
                previousEntry = NULL;
            }   /*  end of if ( previousEntry == NULL )    */
            else {
                /*
                 *  Remove current entry by setting previous entry's pointer to 
                 *  skip the current.
                 */
                previousEntry->next = currentEntry->next;
                
                /*
                 *  Setup entries for next loop. Since an entry was removed 
                 *  from the list, the previous entry, previousEntry, does not 
                 *  change.
                 */
                currentEntry = previousEntry->next;
            }   /*  end of else */           
        }   /*  end of if ( currentEntry == A || currentEntry == B )    */
        else {
            /*
             *  Did not find either A or B, so just set up for next loop
             */
            previousEntry = currentEntry;
            currentEntry  = currentEntry->next;
        }   /*  end of else */
    }   /* end of loop for currentEntry   */

    /*
     *  Finish up by fixing the next pointers for both A and B to NULL since 
     *  their the first and only entries in the lists, and setting the size of 
     *  each group to one.
     */
    (*A)->next   = NULL;
    (*B)->next   = NULL;
    sizeOfGroupA = 1;
    sizeOfGroupB = 1;

    /*
     *  The first entries of groups A and B are now assigned and removed from 
     *  the input list, I.  The "volume" for A and B is the "worst" possible 
     *  for all combinations of the entries of I.
     *
     *  Assign all remaining entries of I to each group based on penalty.  The 
     *  current implementation finds the penalty of the entry with the first 
     *  entries into the group, i.e., A or B.  Other methods are possible, 
     *  including using the penalty of the current group rather than the first 
     *  entry into that group.
     */
    tempA = *A;
    tempB = *B;
    while ( I != NULL ) {
        /*
         *  If neither group is full, add according to penalty
         */
        if ( sizeOfGroupA < fan && sizeOfGroupB < fan ) {
            if ( penalty( **A, *I ) < penalty( **B, *I ) ) {
                /*
                 *  Place current entry into group A, incrementing counter
                 */
                tempA->next = I;            /*  add current entry to group A  */
                I           = I->next;      /*  increment current entry       */
                tempA       = tempA->next;  /*  increment group A ptr         */
                tempA->next = NULL;         /*  remove new entry from group I */

                sizeOfGroupA++;
            }   /*  end of if ( penalty( I, A ) < penalty( I, B ) ) */
            else {
                /*
                 *  Place current entry into group B, incrementing counter
                 */
                tempB->next = I;            /*  add current entry to group B  */
                I           = I->next;      /*  increment current entry       */
                tempB       = tempB->next;  /*  increment group B ptr         */
                tempB->next = NULL;         /*  remove new entry from group I */

                sizeOfGroupB++;
            }   /*  end of else */
        }   /*  end of if ( sizeOfGroupA < fan && sizeOfGroupB < fan )  */
        /*
         *  If group A is full and there is room on group B, then add entry to 
         *  group B
         */
        else if ( sizeOfGroupA >= fan && sizeOfGroupB < fan ) {
            /*
             *  Place entry into group B, incrementing counter
             */
            tempB->next = I;            /*  add current entry to group B  */
            I           = I->next;      /*  increment current entry       */
            tempB       = tempB->next;  /*  increment group B ptr         */
            tempB->next = NULL;         /*  remove new entry from group I */
            
            sizeOfGroupB++;
        }   /*  end of if ( sizeOfGroupA >= fan )   */
        /*
         *  If group B is full and there is room on group A, then add entry to 
         *  group A
         */
        else if ( sizeOfGroupB >= fan && sizeOfGroupA < fan ) {
            /*
             *  Place current entry into group A, incrementing counter
             */
            tempA->next = I;            /*  add current entry to group A  */
            I           = I->next;      /*  increment current entry       */
            tempA       = tempA->next;  /*  increment group A ptr         */
            tempA->next = NULL;         /*  remove new entry from group I */

            sizeOfGroupA++;
        }   /*  end of if ( sizeOfGroupB >= fan )   */
        else {
            /*
             *  Special(error) case when both groups are full and no where to 
             *  place entry.  Simply ignore entry and try to continue.
             */
            I = I->next;
            
            errorMessage( "too many entries to partition", REPLACE );
            errorMessage( name, PREPEND );
            
        }
    }   /* end of loop for currentEntry   */
    
    return;
}   /*  end paritionEntries()   */