SHARE
TWEET

Untitled

a guest Dec 7th, 2019 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <ctype.h>
  4. #define __USE_BSD
  5. #include <string.h>
  6.  
  7. #include "global.h"
  8. #include "darray.h"
  9. #include "sorting.h"
  10.  
  11. // Can be redefined if Value_Type changes
  12. int compare(Value_Type a, Value_Type b){
  13.   return strcmp(a,b);
  14. }
  15.  
  16.  
  17. struct darray* initialize_set (int size)
  18. {
  19.  
  20.   struct darray* arr = malloc(sizeof(struct darray));
  21.   check(arr);
  22.   arr->cells = (Value_Type*) (malloc(sizeof(Value_Type)*size));
  23.   check(arr->cells);
  24.   arr->capacity = size;
  25.   arr->size = 0;
  26.   arr->sorted = false;
  27.   arr->resizes = 0;
  28.   return arr;
  29. }
  30.  
  31. void tidy(struct darray* arr)
  32. {
  33.   if(arr){
  34.     // free memory created by strdup
  35.     for(unsigned i=0; i<arr->size;i++){ free(arr->cells[i]); }
  36.     // free array and struct
  37.     free(arr->cells);
  38.     free(arr);
  39.   }
  40. }
  41.  
  42. int size(struct darray* arr){ return arr->size; }
  43.  
  44. struct darray* insert (Value_Type value, struct darray* arr)
  45. {
  46.   // If we have reached capacity, double size and copy
  47.   if(arr->size >= arr->capacity){
  48.     struct darray* new_arr = initialize_set(arr->capacity*2);
  49.     for(unsigned int i=0;i<arr->size;i++){
  50.       new_arr->cells[i] = arr->cells[i];
  51.     }
  52.     new_arr->size = arr->size;
  53.     new_arr->resizes = arr->resizes+1;
  54.     free(arr->cells);
  55.     free(arr);
  56.     arr = new_arr;
  57.   }
  58.  
  59.   arr->cells[arr->size] = strdup(value);
  60.   arr->size++;
  61.  
  62.   // changing the array means it may no longer be sorted
  63.   arr->sorted = false;
  64.  
  65.   return arr;
  66. }
  67.  
  68. bool find (Value_Type value, struct darray* arr)
  69. {
  70.   if(mode == LINEAR_SEARCH){
  71.     unsigned int i = 0;
  72.     bool Found = false;
  73.     // loop over every element in the darray
  74.     // untill the value is found or is hits the end
  75.     while((i<arr->size) && (!Found)) {
  76.       if(compare(value, arr->cells[i]) == 0){ Found = true; }
  77.       i++;
  78.     }
  79.     return Found;
  80.   }
  81.   else{ // Binary Search
  82.     if(!arr->sorted){
  83.       if(verbose > 2){
  84.         printf("Dynamic Array not sorted, sorting...\n");
  85.       }
  86.       sort(arr,mode);
  87.       if(verbose > 2){
  88.         printf("Dynamic Array sorted\n");
  89.       }
  90.       arr->sorted = true;
  91.     }
  92.   // call the binary search function
  93.   return binarySearch(value, arr, 0, arr->size-1);
  94.   }
  95. }
  96.  
  97. bool binarySearch (Value_Type value, struct darray* arr, int low, int high)
  98. {
  99.   int mid = ((high+low)/2);
  100.   //printf("LOW: %d\nMID: %d\nHIGH: %d\n", low, mid, high); // delete
  101.   // if low is greater than high, then the element hasnt been found
  102.   if (low>high){ return false; }
  103.   // if the value is less than the middle value,
  104.   // binary seach the lower half of the darray
  105.   else if (compare(value, arr->cells[mid]) < 0) {
  106.     return binarySearch(value, arr, low, mid-1);
  107.   }
  108.   // if the value is greater than the middle value,
  109.   // binary seach the upper half of the darray
  110.   else if (compare(value, arr->cells[mid]) > 0) {
  111.     return binarySearch(value, arr, mid+1, high);
  112.   }
  113.   // this mean that value is equal to the middle value
  114.   else { return true; }
  115. }
  116.  
  117. // You can make any changes you want to this function
  118. void print_set (struct darray* arr)
  119. {
  120.   printf("DArray:\n");
  121.   for(unsigned i=0;i<arr->size;i++){
  122.     printf("\t%s\n",arr->cells[i]);
  123.   }
  124. }
  125.  
  126. // You can make any changes you want to this function
  127. void print_stats (struct darray* arr)
  128. {
  129.   printf("Dynamic array of capacity %d contains %d elements\n",arr->capacity,arr->size);
  130.   printf("Dynamic array was resized %d times\n",arr->resizes);
  131. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top