Getting Into a Club Program

////////////////////////////////////////////////////////////////////////////////
///  
///  \file defaultfilename
///  \brief 
///  
///  <br>Author(s): Nicholas Guthrie
///  <br>Created: 2011-04-18
///  <br>Email: defaultemail
///  <br>Web: http://nickguthrie.com
///  <br>Title: Getting int a Club (Heaps)
///  <br>Course: 
///  <br> Class #: 
///  <br>Section #: 
///  
///  THIS SOFTWARE IS PROVIDED BY THE NICHOLAS GUTHRIE''AS IS'' AND ANY EXPRESS
///  OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
///  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
///  NO EVENT SHALL UCF BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
///  EXEMPLARY,OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
///  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
///  OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
///  WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
///  OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
///  ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
///  
////////////////////////////////////////////////////////////////////////////////
///////////////////////////
//   Debugging #defines  //
///////////////////////////
#define _CRT_SECURE_NO_WARNINGS   // stops MSDN warnings
#define DEBUG                     // debug mode for better testing

///////////////////////////
//  Globals & Constants  //
///////////////////////////
#define MAXPEOPLE 500             // max people that can be in a line

///////////////////////////
//   Library Includes    //
///////////////////////////
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

///////////////////////////
//  Struct Declarations  //
///////////////////////////
typedef struct {
  int time;
  int hour;
  int min;
  char modifier[3];
} Time;

struct BST{
  char name[29];		///< first name of person
  Time *enter;
  Time *exit;
  int time_in_line;
  int time_in_club;		///< min spent in the club
  int priority;
  struct BST *left;
  struct BST *right;
};

typedef struct {
  struct BST ** heaparray;
  int capacity;
  int size;
}Heap;


///////////////////////////
//  Function Prototypes  //
///////////////////////////
// Print
int  Print_Error(char * error_message);
void Print_Summary(struct BST *node);
void Print_Person_Summary(struct BST *person);
void Print_Person(struct BST *person);
void Print_Heap(Heap *h);
void Print_BST(struct BST *node);
void File_Print_Summary(struct BST *node, FILE *output);

// Main Functions
void PeopleEnterLine(struct BST *AllPeople, Heap *WaitingList, int time);
void PeopleEnterClub(Heap *OutsideClub, Heap *InsideClub, int current_time);
void PeopleLeaveClub(Heap * InsideClub, int current_time);
void IncramentTime(Heap *h, Heap *InsideClub, int current_time);

// Time
Time *InitTime(int hour, int min, char modifier&#91;3&#93;);
Time *InitEmptyTime();
int ConvertToMinutes(int hour, int minutes, char *modifier);
int BST_Min_Enter_Time(struct BST * tree, int time);
int BST_Max_Exit_Time(struct BST * tree, int time);

// Heap
Heap *InitHeap(int size);
void Heap_Swap(Heap *h, int index1, int index2);
int Heap_Maximum(int a, int indexa, int b, int indexb);
void Free_Heap(Heap *h);
//--outside
struct BST * Heap_Outside_Pop(Heap *h);
void Heap_Outside_Insert(Heap *h, struct BST *person);
void Heap_Outside_PercolateDown(Heap *h, int index);
void Heap_Outside_PercolateUp(Heap *h, int index);
//--inside
void Heap_Inside_Pop(Heap *h);
void Heap_Inside_Insert(Heap *h, struct BST *person);
void Heap_Inside_PercolateDown(Heap *h, int index);
void Heap_Inside_PercolateUp(Heap *h, int index);

// BST
struct BST *InitBST();
void Free_BST(struct BST * tree);
struct BST* BST_FindName(struct BST *current_ptr, char name&#91;29&#93;);
struct BST * BST_Insert(struct BST *root, struct BST *element);



///////////////////////////
//        Main           //
///////////////////////////
int main()
{
  /////////////////////
  //   Variables     //
  /////////////////////
  FILE *input, *output; //input & output files

  // Data Storage

  // Input Collection
  int num_clubs, num_events, club_capacity, current_time;
  char time&#91;3&#93;;
  int hour, min, priority;
  char modifier&#91;3&#93;; //AM or PM
  char name&#91;29&#93;;
  char mode; //E = enter, L = leaving

  // Other
  int i, j; //navigation variablges


  /////////////////////
  // Initializations //
  /////////////////////
  input = fopen("club.in", "r");
  output = fopen("club.out", "w");
  if(input == NULL || output == NULL)
    return Print_Error("File not found.");

  /////////////////////
  //   Read Input    //
  /////////////////////
  // FOR all clubs
  fscanf(input, "%d\n", &num_clubs);
  if(num_clubs < 0)
    Print_Error("The number of clubs must be greater than 0.");
  for(i = 0; i<num_clubs; i++)
    {
              struct BST *AllPeople = NULL;
	      struct BST *NewBST = NULL;

      fprintf(output, "Club #%d:\n\n", i+1);
      fscanf(input, "%d%d\n", &num_events, &club_capacity);
      AllPeople = NULL;
      NewBST = NULL;
      
      // FOR all events
      for(j = 0; j<num_events; j++)
	{
	  // Initialize the Outside Heap.
	  fgets(time, 3, input); 
	  hour = atoi(time);     //convert string time to int time
	  fgetc(input); 
	  fgets(time, 3, input);
	  min = atoi(time);
	  fscanf(input, "%s%s%s", modifier, &mode, name);

	  // The person is entering
	  if(mode == 'E')
	    {
	      fscanf(input, "%d\n", &priority);
	      NewBST = InitBST();
	      strcpy(NewBST->name, name);
	      NewBST->priority = priority;
	      NewBST->enter = InitTime(hour, min, modifier);
	      AllPeople = BST_Insert(AllPeople, NewBST);
	    }
	  // The person is leaving
	  else if (mode == 'L')
	    {
	      fscanf(input, "\n");
	      NewBST = BST_FindName(AllPeople, name);
	      NewBST->exit = InitTime(hour, min, modifier);
	    }
	  else
	    return Print_Error("Invalid Enter/Leave Mode:");
	}//END Events

  Heap * WaitList = InitHeap(MAXPEOPLE);
  Heap * InsideClub = InitHeap(club_capacity);

  //WaitList = InitHeap(MAXPEOPLE);
  //InsideClub = InitHeap(club_capacity);
      
      int tmin = BST_Min_Enter_Time(AllPeople, 48*60);
      int tmax = tmin + 20*60;
      tmin--;
      tmax++;

     for(current_time = tmin; current_time < tmax; current_time++)
	{
	  printf("CURRENT TIME = %d\n", current_time);
	  printf("---------- INSIDE ---------- ");
	  Print_Heap(InsideClub);
	  printf("---------- OUTSIDE ---------- ");
	  Print_Heap(WaitList);


	  PeopleLeaveClub(InsideClub, current_time);
	  PeopleEnterLine(AllPeople, WaitList, current_time);
	  PeopleEnterClub(WaitList, InsideClub, current_time);
	  IncramentTime(WaitList, InsideClub, current_time);

	}
     File_Print_Summary(AllPeople,output);
     Free_BST(AllPeople);
      Free_BST(NewBST);
      Free_Heap(WaitList);
      Free_Heap(InsideClub);
      fprintf(output, "\n");
    }//END Clubs
  fclose(input);
  fclose(output);
}//END Main


//////////////////////////////
// Function Implamentations //
//////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/// GENERAL
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
///
///  \brief Prints an error message.
///  \param error_message The error message to print.
///  \return 0, so the program can be exited.
///  
////////////////////////////////////////////////////////////////////////////////
int Print_Error(char * error_message){
  printf("  ERROR: %s Press any key to exit program.\n", error_message);
  getchar(); // wait for user input
  return 0;
}

////////////////////////////////////////////////////////////////////////////////
///  
///  \brief (for debugging) Prints list of people in heap
///  \param HeapStruct *h Pointer to a valid HeapStruct to print.
///  \return void
///  
////////////////////////////////////////////////////////////////////////////////
void Print_Heap(Heap *h)
{
  int i; //navigation variable
  if(h->size > 0)
    {
      printf("  ____ Print Heap ____\n");
      printf("| #  | P | Name  | Enter | Exit |\n");
      printf("|----|---|-------|-------|------|\n");
      
      for (i=1; i <= h->size; i++)
	printf("| %.2d | %d | %.4s\t | %d  | %d | %d\n", i, h->heaparray[i]->priority,
	       h->heaparray[i]->name ,h->heaparray[i]->enter->time,
	       h->heaparray[i]->exit->time, h->heaparray[i]->time_in_club);
    }
}

////////////////////////////////////////////////////////////////////////////////
///
///  \brief Prints all members of a BST in alphabetical order.
///  \param node Root of BST to print.
///  \return void
/// 
////////////////////////////////////////////////////////////////////////////////
void Print_BST(struct BST *node)
{
  if(node != NULL){
    if(node->right !=NULL)
      Print_BST(node->right);
    Print_Person(node);
    if(node->left !=NULL)
      Print_BST(node->left);
  }
}


////////////////////////////////////////////////////////////////////////////////
///
///  \brief Prints all people alphabetically & summary of their data.
///  \param node Root of BST to print.
///  \return void
/// 
////////////////////////////////////////////////////////////////////////////////
void Print_Summary(struct BST *node)
{
  if(node != NULL)
    {
    if(node->right !=NULL)
      Print_Summary(node->right);
    Print_Person_Summary(node);
    if(node->left !=NULL)
      Print_Summary(node->left);
  }
}

void Print_Person_Summary(struct BST *person)
{
    printf("%s waited %d minutes and ", person->name, person->time_in_line);
    if(person->time_in_club > 0)
      printf("stayed in the club for %d minutes.\n", person->time_in_club);
    else
      printf("and never got into the club.\n");
}




void File_Print_Summary(struct BST *node, FILE *output)
{
  if(node != NULL)
    {
      if(node->right !=NULL)
	File_Print_Summary(node->right, output);
      
    fprintf(output, "%s waited %d minutes and ", node->name, node->time_in_line);
    if(node->time_in_club > 0)
      fprintf(output, "stayed in the club for %d minutes.\n", node->time_in_club);
    else
      fprintf(output, "and never got into the club.\n");

    if(node->left !=NULL)
      File_Print_Summary(node->left, output);
  }
}




void Print_Person(struct BST *person)
{
  printf(" __ Print Person __\n");
  printf(" Name.......%s\n", person->name);
  printf(" Enter......%d:%d %s = %d minutes\n", person->enter->hour,
	 person->enter->min, person->enter->modifier, person->enter->time);
  printf(" Exit.......%d:%d %s = %d minutes\n", person->exit->hour,
	 person->exit->min, person->exit->modifier, person->exit->time);
  printf(" In Club....%d minutes\n", person->time_in_club);
  printf(" In Line....%d minutes\n", person->time_in_line);
  printf(" Priority:..%d\n", person->priority);
  printf("\n");
}



////////////////////////////////////////////////////////////////////////////////
/// MAIN FUNCTIONS
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Adds one minute to the waiting time of all people
///  \param HeapStruct *h Pointer to a valid HeapStruct with people in it.
///  \return void
///  
////////////////////////////////////////////////////////////////////////////////
void IncramentTime(Heap *h, Heap *InsideClub, int current_time)
{
  int i;
  for(i = 1; i<=h->size; i++)
    if(h->heaparray[i]->exit->time > current_time)
      h->heaparray[i]->time_in_line = h->heaparray[i]->time_in_line +1;
  for(i = 1; i<=InsideClub->size; i++){
    InsideClub->heaparray[i]->time_in_club =
      InsideClub->heaparray[i]->time_in_club +1;
    printf("%s = %d\n", InsideClub->heaparray[i]->name, InsideClub->heaparray[i]->time_in_club);


  }
}

////////////////////////////////////////////////////////////////////////////////
///
///  \brief Searches a BST for people who want to enter the line.
///
////////////////////////////////////////////////////////////////////////////////
void PeopleEnterLine(struct BST *AllPeople, Heap *WaitingList, int time)
{
  // if right is available, go right
  if(AllPeople->right != NULL)
    PeopleEnterLine(AllPeople->right, WaitingList, time);
  // if time == then this is the alphabetically first person to add
  if(AllPeople->enter->time == time)
    Heap_Outside_Insert(WaitingList, AllPeople);

  if(AllPeople->left != NULL)
    PeopleEnterLine(AllPeople->left, WaitingList, time);
}

void PeopleEnterClub(Heap *WaitList, Heap *InsideClub, int current_time)
{
  //repeat while there is room inside the club and room outside the club
  while(InsideClub->size < InsideClub->capacity && WaitList->size > 0)
    {
      if(WaitList->heaparray[1]->exit->time <= current_time)
	Heap_Outside_Pop(WaitList);
      else
	Heap_Inside_Insert(InsideClub, Heap_Outside_Pop(WaitList));
    }
}

void PeopleLeaveClub(Heap * InsideClub, int current_time)
{
  while(InsideClub->size > 0 && InsideClub->heaparray[1]->exit->time == current_time)
    
    {
      Heap_Inside_Pop(InsideClub);      
    }

}







////////////////////////////////////////////////////////////////////////////////
/// TIME
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Initializes all members of an empty struct Time properly.
///  \return Pointer to a properly initialized struct Time.
///  
////////////////////////////////////////////////////////////////////////////////
Time *InitTime(int hour, int min, char modifier[3])
{
  Time *clock = (Time*)(malloc(sizeof(Time)));
  clock->time = ConvertToMinutes(hour, min, modifier);
  clock->hour = hour;
  clock->min = min;
  strcpy(clock->modifier,modifier);
  return clock;
}

////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Initializes all members of an empty struct Time properly.
///  \return Pointer to a properly initialized struct Time.
///  
////////////////////////////////////////////////////////////////////////////////
Time *InitEmptyTime()
{
  Time *clock = (Time*)(malloc(sizeof(Time)));
  clock->time = -1;
  clock->hour = -1;
  clock->min = -1;
  strcpy(clock->modifier,"NN");
  return clock;
}


////////////////////////////////////////////////////////////////////////////////
///
///  \brief Converts hour and minutes to the minutes past midnight.
///  \param hour The hour of the time (not military time)(0 <= hour <= 12)
///  \param minutes The minutes of the time.
///  \param modifier AM or PM.
///  \return The # of minutes that have passed in the day so far.
///
////////////////////////////////////////////////////////////////////////////////
int ConvertToMinutes(int hour, int minutes, char *modifier)
{
  // if hour is PM add 12
  if(strcmp(modifier, "PM") == 0)
    return (12+hour)*60+minutes;

  // since the "value" of morning (midnight = 0) should actually be > 11:59PM
  else
    {
      if(hour == 12)
	return(24)*60+minutes;
      else
	return(24+hour)*60+minutes;
    }

}














////////////////////////////////////////////////////////////////////////////////
/// HEAP
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Initializes an empty heap with a capacity of SIZE.
///  \param int size Max size of heap to initialize.
///  \return Pointer to a valid HeapStruct.
///  
////////////////////////////////////////////////////////////////////////////////
Heap* InitHeap(int max_size)
{
  Heap* list;
    
  // allocate space for the heap and set the size for an empty heap.
  list = (Heap*)(malloc(sizeof(Heap)));
  list->capacity = max_size;
  list->heaparray = (struct BST**)malloc(sizeof(struct BST)*(max_size+1));
  list->size = 0;
  return list;
}



void Free_Heap(Heap *h) {
     free(h->heaparray);     
     free(h);
}




////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Inserts a value into a heap.
///  \param HeapStruct Pointer to a valid HeapStruct to insert the value in.
///  \param value Value to insert into the HeapStruct.
///  \return void
///  
////////////////////////////////////////////////////////////////////////////////
void Heap_Outside_Insert(Heap *h, struct BST *person)
{
  struct BST** temp;
  //struct BST** throwaway;
  int i; //navigation variable

  
  //DEBUG - Capacity of heap should not grow.  
  // Our array is full, we need to allocate some new space!
  /*if (h->size == h->capacity)
    {
      // We will double the size of the structure.
      h->capacity *= 2; 
      
      // Allocate new space for an array.
      temp = (struct BST**)malloc(sizeof(struct BST)*h->capacity+1); 
      
      // Copy all the items over.
      for (i=1; i<=h->capacity; i++)
	temp[i] = h->heaparray[i];
            
      // Move the pointer and free the old memory.
      throwaway = h->heaparray;
      h->heaparray = temp;
      free(throwaway);
      }*/
      
  // Adjust all the necessary components of h, and then move the inserted
  // item into its appropriate location.  
  h->size = h->size +1;
  //     h->size++;
  h->heaparray[h->size] = person; //DEBUG not sure if this is correct
  Heap_Outside_PercolateUp(h, h->size);
}

////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Percolates up on a heap on a node.
///  \param HeapStruct Pointer to a valid HeapStruct to percolate up on.
///  \param index Node to percolate down from.
///  \return void
///  
////////////////////////////////////////////////////////////////////////////////
void Heap_Outside_PercolateUp(Heap *h, int index)

  
{


  // Can only percolate up if the node isn't the root.
  if (index > 1)
    {
      // See if our current node is bigger in value than its parent.        
      if (h->heaparray[index/2]->priority < h->heaparray[index]->priority)
	{
	  // Move our node up one level.
	  Heap_Swap(h, index, index/2);
	  // See if it needs to be done again.
	  Heap_Outside_PercolateUp(h, index/2);
	}
    }
}

////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Percolates down a heap on a node.
///  \param HeapStruct Pointer to a valid HeapStruct to percolate down on.
///  \param index Node to percolate down from.
///  \return void
///  
////////////////////////////////////////////////////////////////////////////////
void Heap_Outside_PercolateDown(Heap *h, int index)
{
  int min;
    
  // Only try to percolate down internal nodes.
  if ((2*index+1) <= h->size)
    {
                    
      // Find the minimum value of the two children of this node
      min = Heap_Minimum(h->heaparray[2*index]->priority, 2*index,
			 h->heaparray[2*index+1]->priority, 2*index+1);
        
      // IF this value is greater than the current value, then we need to move
      // our current value down the heap.  
      if (h->heaparray[index]->priority < h->heaparray[min]->priority) {
	Heap_Swap(h, index, min);
        
	// This part is recursive and allows us to continue percolating
	// down the element in question.
	Heap_Outside_PercolateDown(h, min);
      }
    }
    
  // Case where our current element has exactly one child, a left child.
  else if (h->size == 2*index) {
         
    // Compare the current item to its only child.
    // No recursive call is needed since the child of this node is a leaf.
    if (h->heaparray[index]->priority < h->heaparray[2*index]->priority) 
      Heap_Swap(h, index, 2*index);
  }
}

////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Removes the minimum value in the heap.
///  \param HeapStruct *h Pointer to a valid HeapStruct to remove the value from.
///  \return IF Successful, The value of the # deleted.
///          -1 to indicate failure.
///  
////////////////////////////////////////////////////////////////////////////////
struct BST * Heap_Outside_Pop(Heap *h)
{
  struct BST *retval;
    

  // This is where the minimum is stored.
  retval = h->heaparray[1];
        
  // Copy the last value into this top slot.
  h->heaparray[1] = h->heaparray[h->size];
        
  // Our heap will have one fewer items.
  h->size--;
        
  // Need to let this value move down to its rightful spot in the heap.
  Heap_Outside_PercolateDown(h, 1);
        
  // Now we can return our value.
  return retval;
}




////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Inserts a value into a heap.
///  \param HeapStruct Pointer to a valid HeapStruct to insert the value in.
///  \param value Value to insert into the HeapStruct.
///  \return void
///  
////////////////////////////////////////////////////////////////////////////////
void Heap_Inside_Insert(Heap *h, struct BST *person)
{
  struct BST** temp;
  h->size = h->size +1;
  h->heaparray[h->size] = person;
  Heap_Inside_PercolateUp(h, h->size);
}

////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Percolates up on a heap on a node.
///  \param HeapStruct Pointer to a valid HeapStruct to percolate up on.
///  \param index Node to percolate down from.
///  \return void
///  
////////////////////////////////////////////////////////////////////////////////
void Heap_Inside_PercolateUp(Heap *h, int index)
{

  //only if not root
  if (index > 1)
    {
      //if the exit time of parent > exit time of child, swap
      if (h->heaparray[index/2]->exit->time > h->heaparray[index]->exit->time)
	{
		Heap_Swap(h, index, index/2);
		Heap_Inside_PercolateUp(h, index/2);
	}
    }
}

////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Percolates down a heap on a node.
///  \param HeapStruct Pointer to a valid HeapStruct to percolate down on.
///  \param index Node to percolate down from.
///  \return void
///  
////////////////////////////////////////////////////////////////////////////////
void Heap_Inside_PercolateDown(Heap *h, int index)
{
  int pos;
  // only internal nodes
  if ((2*index+1) <= h->size)
    {
      //compare left & right children, get position of lesser child
      pos = Heap_Minimum(h->heaparray[2*index]->exit->time, 2*index,
			 h->heaparray[2*index+1]->exit->time, 2*index+1);

      //if the current value > than the minimum value, swap
      if (h->heaparray[index]->exit->time > h->heaparray[pos]->exit->time)
	{
	  Heap_Swap(h, index, pos);
	  Heap_Inside_PercolateDown(h, pos);
	}
    }
    
  // case if only has 1 left child
  else if (h->size == 2*index) {
    // Compare the current item to its only child.
    // No recursive call is needed since the child of this node is a leaf.
    if (h->heaparray[index]->exit->time > h->heaparray[2*index]->exit->time) 
      Heap_Swap(h, index, 2*index);
  }
}

////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Removes the minimum value in the heap.
///  \param HeapStruct *h Pointer to a valid HeapStruct to remove the value from.
///  \return IF Successful, The value of the # deleted.
///          -1 to indicate failure.
///  
////////////////////////////////////////////////////////////////////////////////
void Heap_Inside_Pop(Heap *h)
{
   h->heaparray[1] = h->heaparray[h->size];
   h->size--;
   Heap_Inside_PercolateDown(h, 1);
 }






////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Swaps the two people stored in the heap.
///  \param HeapStruct *h Pointer to a valid HeapStruct to switch values in.
///  \param int index1 First person to swap.
///  \param int index2 Second person to swap.
///  \return void
///  
////////////////////////////////////////////////////////////////////////////////
void Heap_Swap(Heap *h, int index1, int index2)
{
  struct BST *temp = h->heaparray[index1];
  h->heaparray[index1] = h->heaparray[index2];
  h->heaparray[index2] = temp;
}

////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Finds the minimum of two numbers and returns the index location.
///  \param int a First integer to compare.
///  \param int indexa Index of the first integer.
///  \param int b Second integer to compare.
///  \param int indexb Index of the second integer.
///  \return IF a<b, Returns indexa
///          ELSE Returns indexb
///  
////////////////////////////////////////////////////////////////////////////////
int Heap_Maximum(int a, int indexa, int b, int indexb)
{

  // Return the value associated with a.    
  if (a > b)
    return indexa;
        
  // Return the value associated with b.
  else
    return indexb;
}

////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Finds the minimum of two numbers and returns the index location.
///  \param int a First integer to compare.
///  \param int indexa Index of the first integer.
///  \param int b Second integer to compare.
///  \param int indexb Index of the second integer.
///  \return IF a<b, Returns indexa
///          ELSE Returns indexb
///  
////////////////////////////////////////////////////////////////////////////////
int Heap_Minimum(int a, int indexa, int b, int indexb)
{

  // Return the value associated with a.    
  if (a < b)
    return indexa;
        
  // Return the value associated with b.
  else
    return indexb;
}


















////////////////////////////////////////////////////////////////////////////////
/// BINARY SEARCH TREES
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
///
///  \brief Initializes a dynamic array of people.
///  \param size The max number of people the BST can hold.
///  \return Pointer to the newly initialized empty BST.
///
////////////////////////////////////////////////////////////////////////////////
struct BST * InitBST()
{
  //malloc enough enough size to store all of the struct
  struct BST *list = (struct BST*)(malloc(sizeof(struct BST)));
  list->enter = InitEmptyTime();
  list->exit = InitEmptyTime();
  list->left = NULL;
  list->right = NULL;
  return list;
}

////////////////////////////////////////////////////////////////////////////////
///
///  \brief Inserts a person into their proper location in a BST.
///  \param root A pointer to the root of the tree to insert the Person in.
///  \param element A pointer to the Person to be inserted.
///  \return The root of the tree with newly inserted person.
///
////////////////////////////////////////////////////////////////////////////////
struct BST * BST_Insert(struct BST *root, struct BST *element)
{
  // Empty Tree Case
  if (root == NULL) 
    return element;
  else
    {
      // insert element to the right
      if(strcmp(element->name, root->name) == -1)
	{
	  // There is a right subtree to insert the node.
	  if (root->right != NULL)
	    root->right = BST_Insert(root->right, element);
	       
	  // Place the node directly to the right of root.
	  else
	    root->right = element;
	}

      // element should be inserted to the left.
      else
	{
	  // There is a left subtree to insert the node.
	  if (root->left != NULL)
	    root->left = BST_Insert(root->left, element);

	  // Place the node directly to the left of root.
	  else
	    root->left = element;
	} 

      // Return the root pointer of the updated tree.
      return root;
    }
}

void Free_BST(struct BST * tree)
{
  if(tree->left!=NULL)
    Free_BST(tree->left);
  if(tree->right!=NULL)
    Free_BST(tree->left);
  //free(tree->enter);
  //free(tree->exit);
  //free(tree);
}

int BST_Max_Exit_Time(struct BST * tree, int time)
{
  if(tree->exit->time > time)
    time = tree->exit->time;
  if(tree->left != NULL)
    BST_Max_Exit_Time(tree->left, time);
  if(tree->right != NULL)
      BST_Max_Exit_Time(tree->right, time);
  return time;
}



int BST_Min_Enter_Time(struct BST * tree, int time)
{
  if(tree->enter->time < time)
    time = tree->enter->time;
  if(tree->left != NULL)
    BST_Min_Enter_Time(tree->left, time);
  if(tree->right != NULL)
      BST_Min_Enter_Time(tree->right, time);
  return time;
}


////////////////////////////////////////////////////////////////////////////////
///
///  \brief Searches the BST for a given name.
///  \param BST to search.
///  \param name Name to search the BST for.
///  \return Pointer to struct Person with found Name.
/// 
////////////////////////////////////////////////////////////////////////////////
struct BST* BST_FindName(struct BST *current_ptr, char name[29])
{
  // Check if there are nodes in the tree.
  if (current_ptr != NULL)
    {
      int value = strcmp(current_ptr->name, name);

      // Found the value at the root.
      if (value == 0)
	return current_ptr;

      // Search to the left.
      if (value == -1) 
	return BST_FindName(current_ptr->left, name);
    
      // Or...search to the right.
      else 
	return BST_FindName(current_ptr->right, name);
    
    }
  else
    return NULL; // No node found.

}

Leave a Reply

You must be logged in to post a comment.