text: #include "vector.h"
  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  #include <ctype.h>
  #include <time.h>
  #include <limits.h>
  #include <assert.h>
  
  #define YES_OR_NO(value) (value != 0 ? "Yes" : "No")
  
  /**
   * PrintChar
   * ---------
   * Mapping function used to print one character element in a vector.  
   * The file pointer is passed as the client data, so that it can be
   * used to print to any FILE *.
   */
  
  static void PrintChar(void *elem, void *fp)
  {
    fprintf((FILE *)fp, "%c", *(char *)elem);
    fflush((FILE *)fp);
  }
  
  /**
   * CompareChar
   * -----------
   * Comparator function used to compare two character elements within a vector.
   * Used for both sorting and searching in the array of characters.  Has the same
   * return value semantics as the strcmp library function (negative if A<B, zero if A==B,
   * positive if A>B).
   */
  
  static int CompareChar(const void *elemA, const void *elemB)
  {
    return (*(char *)elemA - *(char *)elemB);
  }
  
  /**
   * Function: TestAppend
   * --------------------
   * Appends letters of alphabet in order, then appends a few digit chars.
   * Uses VectorMap to print the vector contents before and after.
   */
  
  static void TestAppend(vector *alphabet)
  {
    char ch;
    int i;
    
    for (ch = 'A'; ch <= 'Z'; ch++)   //  Start with letters of alphabet
      VectorAppend(alphabet, &ch);
    fprintf(stdout, "First, here is the alphabet: ");
    VectorMap(alphabet, PrintChar, stdout);
    
    for (i = 0; i < 10; i++) {	    // Append digit characters
      ch = '0' + i;                   // convert int to ASCII digit character
      VectorAppend(alphabet, &ch);
    }
    fprintf(stdout, "\nAfter append digits: ");
    VectorMap(alphabet, PrintChar, stdout);
  }
  
  
  /**
   * Function: TestSearch
   * --------------------
   * Tests the searching capability of the vector by looking for specific
   * character.  Calls VectorSearch twice, once to see if it finds the character
   * using a binary search (given the array is sorted) and once to see if it
   * finds the character using a linear search.  Reports results to stdout.
   */
  
  static void TestSearch(vector *v, char ch)
  {
    int foundSorted, foundNot;
    
    foundSorted = VectorSearch(v, &ch, CompareChar, 0, true); // Test sorted 
    foundNot = VectorSearch(v, &ch, CompareChar, 0, false);   // Not sorted 
    fprintf(stdout,"\nFound '%c' in sorted array? %s. How about unsorted? %s.", 
  	  ch, YES_OR_NO((foundSorted != -1)), 
  	  YES_OR_NO((foundNot != -1)));
  }
  
  /**
   * Function: TestSortSearch
   * ------------------------
   * Sorts the vector into alphabetic order and then tests searching
   * capabilities, both the linear and binary search versions.
   */
  
  static void TestSortSearch(vector *alphabet)
  {
    VectorSort(alphabet, CompareChar);	 // Sort into order again
    fprintf(stdout, "\nAfter sorting: ");
    VectorMap(alphabet, PrintChar, stdout);
    TestSearch(alphabet, 'J');	// Test searching capabilities
    TestSearch(alphabet, '$');
  }
  
  /**
   * Function: TestAt
   * ----------------
   * Uses VectorNth to access every other letter and 
   * lowercase it. Prints results using VectorMap.
   */
  
  static void TestAt(vector *alphabet)
  {
    int i;
    
    for (i = 0; i < VectorLength(alphabet); i += 2) { // Lowercase every other
      char *elem = (char *) VectorNth(alphabet, i);
      *elem = tolower(*elem);
    }
    
    fprintf(stdout, "\nAfter lowercase every other letter: ");
    VectorMap(alphabet, PrintChar, stdout);
  }
  
  /**
   * Function: TestInsertDelete
   * --------------------------
   * Inserts dashes at regular intervals, then uses delete to remove
   * them.  Makes sure that insert at allows you to insert at end of
   * array and checks no problem with deleting very last element.  It's
   * always a good idea to directly test the borderline cases to make
   * sure you have handled even the unusual scenarios.
   */
  
  static void TestInsertDelete(vector *alphabet)
  {
    char ch = '-';
    int i;
    
    for (i = 3; i < VectorLength(alphabet); i += 4) // Insert dash every 4th char 
      VectorInsert(alphabet, &ch, i);
    fprintf(stdout, "\nAfter insert dashes: ");
    VectorMap(alphabet, PrintChar, stdout);
    
    for (i = 3; i < VectorLength(alphabet); i += 3) // Delete every 4th char 
      VectorDelete(alphabet, i);
    fprintf(stdout, "\nAfter deleting dashes: ");
    VectorMap(alphabet, PrintChar, stdout);
      
    ch = '!';
    VectorInsert(alphabet, &ch, VectorLength(alphabet));
    VectorDelete(alphabet, VectorLength(alphabet) - 1);
    fprintf(stdout, "\nAfter adding and deleting to very end: ");
    VectorMap(alphabet, PrintChar, stdout);
  }
  
  /**
   * Function: TestReplace
   * ---------------------
   * Uses repeated searches to find all occurrences of a particular
   * character and then uses replace it to overwrite value.
   */
  
  static void TestReplace(vector *alphabet)
  {
    int found = 0;
    char toFind = 's', toReplace = '*';
    
    while (found < VectorLength(alphabet)) {
      found = VectorSearch(alphabet, &toFind, CompareChar, found, false);
      if (found == -1) break;
      VectorReplace(alphabet, &toReplace, found);
    }
    
    fprintf(stdout, "\nAfter changing all %c to %c: ", toFind, toReplace);
    VectorMap(alphabet, PrintChar, stdout);
  }
  
  /** 
   * Function: SimpleTest
   * --------------------
   * Exercises the vector when it stores characters.
   * Because characaters are small and don't have any
   * complicated memory requirements, this test is a
   * good starting point to see whether or not your vector
   * even has a prayer of passing more rigorous tests.
   *
   * See the documentation for each of the helper functions
   * to gain a sense as to how SimpleTest works.  The intent
   * it certainly to try out all of the vector operations so
   * that everything gets exercised.
   */
  
  static void SimpleTest()
  {
    fprintf(stdout, " ------------------------- Starting the basic test...\n");
    vector alphabet;
    VectorNew(&alphabet, sizeof(char), NULL, 4);
    TestAppend(&alphabet);
    TestSortSearch(&alphabet);
    TestAt(&alphabet);
    TestInsertDelete(&alphabet);
    TestReplace(&alphabet);
    VectorDispose(&alphabet);
  }
  
  /** 
   * Function: InsertPermutationOfNumebrs
   * ------------------------------------
   * Uses a little bit of number theory to populate the
   * presumably empty numbers vector with some permutation
   * of the integers between 0 and d - 1, inclusive.  
   * By design, each number introduced to the vector should
   * be introduces once and exactly once.  This happens
   * provided n < d and that both n and d are prime numbers.
   */
  
  static void InsertPermutationOfNumbers(vector *numbers, long n, long d)
  {
    long k;
    long residue;
    fprintf(stdout, "Generating all of the numbers between 0 and %ld (using some number theory). ", d - 1);
    fflush(stdout); // force echo to the screen... 
  
    for (k = 0; k < d; k++) {
      residue = (long) (((long long)k * (long long) n) % d);
      VectorAppend(numbers, &residue);
    }
    
    assert(VectorLength(numbers) == d);
    fprintf(stdout, "[All done]\n");
    fflush(stdout);
  }
  
  /**
   * Function: LongCompare
   * ---------------------
   * Called when searching or sorting a vector known to
   * be storing long integer data types.
   */
  
  static int LongCompare(const void *vp1, const void *vp2)
  {
    return (*(const long *)vp1) - (*(const long *)vp2);
  }
  
  /**
   * Function: SortPermutation
   * -------------------------
   * Sorts the (very, very large) vectorToSort, and confirms
   * that the sort worked.  This is slightly more strenous
   * that the TestSort routine above simply because the vector
   * is much, much bigger.
   */
  
  static void SortPermutation(vector *vectorToSort)
  {
    long residue, embeddedLong;
    vector *sortedVector;
    fprintf(stdout, "Sorting all of those numbers. ");
    fflush(stdout);
    VectorSort(vectorToSort, LongCompare);
    fprintf(stdout, "[Done]\n");
    fflush(stdout);
    fprintf(stdout, "Confirming everything was properly sorted. ");
    fflush(stdout);
    sortedVector = vectorToSort; // need better name now that it's sorted... 
    for (residue = 0; residue < VectorLength(sortedVector); residue++) {
      embeddedLong = *(const long *) VectorNth(sortedVector, residue);
      assert(embeddedLong == residue);
    }
    fprintf(stdout, "[Yep, it's sorted]\n");
    fflush(stdout);
  }
  
  /**
   * Function: DeleteEverythingVerySlowly
   * ------------------------------------
   * Empties out the vector in such a way that VectorDelete
   * is exercised to the hilt.  By repeatedly deleting from
   * within the vector, we ensure that the shifting over of
   * bytes is working properly.
   */
  
  static void DeleteEverythingVerySlowly(vector *numbers)
  {
    long largestOriginalNumber;
    fprintf(stdout, "Erasing everything in the vector by repeatedly deleting the 100th-to-last remaining element (be patient).\n");
    fflush(stdout);
    largestOriginalNumber = *(long *)VectorNth(numbers, VectorLength(numbers) - 1);
    while (VectorLength(numbers) >= 100) {
      VectorDelete(numbers, VectorLength(numbers) - 100);
      assert(largestOriginalNumber == *(long *)VectorNth(numbers, VectorLength(numbers) -1));
    }
    fprintf(stdout, "\t[Okay, almost done... deleting the last 100 elements... ");
    fflush(stdout);
    while (VectorLength(numbers) > 0) VectorDelete(numbers, 0);
    fprintf(stdout, "and we're all done... whew!]\n");
    fflush(stdout);
  }
  
  /**
   * Function: ChallengingTest
   * -------------------------
   * Uses a little bit of number theory to generate a very large vector
   * of four-byte values.  Some permutation of the numbers [0, 3021367)
   * is generated, and in the process the vector grows in such a way that
   * several realloc calls are likely made.  This will catch any errors
   * with the reallocation, particulatly those where the implementation
   * fails to catch realloc's return value.  The test then goes on the
   * sort the array, confirm that the sort succeeded, and then finally
   * delete all of the elements one by one.
   */
  
  static const long kLargePrime = 1398269;
  static const long kEvenLargerPrime = 3021377;
  static void ChallengingTest()
  {
    vector lotsOfNumbers;
    fprintf(stdout, "\n\n------------------------- Starting the more advanced tests...\n");  
    VectorNew(&lotsOfNumbers, sizeof(long), NULL, 4);
    InsertPermutationOfNumbers(&lotsOfNumbers, kLargePrime, kEvenLargerPrime);
    SortPermutation(&lotsOfNumbers);
    DeleteEverythingVerySlowly(&lotsOfNumbers);
    VectorDispose(&lotsOfNumbers);
  }
  
  /** 
   * Function: FreeString
   * --------------------
   * Understands how to free a C-string.  This
   * function should be used by all vectors that
   * store char *'s (but only when those char *s
   * point to dynamically allocated memory, as
   * they do with strings.)
   */
  
  static void FreeString(void *elemAddr)
  {
    char *s = *(char **) elemAddr;
    free(s); 
  }
  
  /** 
   * Function: PrintString
   * ---------------------
   * Understands how to print a C-string stored
   * inside a vector.  The target FILE * should
   * be passed in via the auxData parameter.
   */
  
  static void PrintString(void *elemAddr, void *auxData)
  {
    char *word = *(char **)elemAddr;
    FILE *fp = (FILE *) auxData;
    fprintf(fp, "\t%s\n", word);
  }
  
  /**
   * Function: MemoryTest
   * --------------------
   * MemoryTest exercises the vector functionality by
   * populating one with pointers to dynamically allocated
   * memory.  The insertion process marks the transfer of
   * of responsibility from the client to the vector, so
   * we now need to specify a non-NULL VectorFreeFunction so
   * the a vector can apply it to the elements it inherits
   * from the client.  Make sure you understand why the
   * casts within the two functions above (FreeString, PrintString)
   * are char ** casts and not char *.  If you truly understand,
   * they you've learned what is probably the most difficult-to-
   * learn concept taught in CS107.
   */
  
  static void MemoryTest()
  {
    int i;
    const char * const kQuestionWords[] = {"who", "what", "where", "how", "why"};
    const int kNumQuestionWords = sizeof(kQuestionWords) / sizeof(kQuestionWords[0]);
    vector questionWords;
    char *questionWord;
    
    fprintf(stdout, "\n\n------------------------- Starting the memory tests...\n");
    fprintf(stdout, "Creating a vector designed to store dynamically allocated C-strings.\n");
    VectorNew(&questionWords, sizeof(char *), FreeString, kNumQuestionWords);
    fprintf(stdout, "Populating the char * vector with the question words.\n");
    for (i = 0; i < kNumQuestionWords; i++) {
      questionWord = malloc(strlen(kQuestionWords[i]) + 1);
      strcpy(questionWord, kQuestionWords[i]);
      VectorInsert(&questionWords, &questionWord, 0);  // why the ampersand? isn't questionWord already a pointer?
    }
    
    fprintf(stdout, "Mapping over the char * vector (ask yourself: why are char **'s passed to PrintString?!!)\n");
    VectorMap(&questionWords, PrintString, stdout);
    fprintf(stdout, "Finally, destroying the char * vector.\n");
    VectorDispose(&questionWords);
  }
  
  /**
   * Function: main
   * --------------
   * The enrty point into the test application.  The
   * first test is easy, the second one is medium, and
   8 the final test is hard.
   */
  
  int main(int ignored, char **alsoIgnored) 
  {
    SimpleTest();
    ChallengingTest();
    MemoryTest();
    return 0;
  }
  
  