SHARE
TWEET

Untitled

a guest Feb 16th, 2020 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "restaurant.h"
  2.  
  3. /*
  4.     Sets *ptr to the i'th restaurant. If this restaurant is already in the cache,
  5.     it just copies it directly from the cache to *ptr. Otherwise, it fetches
  6.     the block containing the i'th restaurant and stores it in the cache before
  7.     setting *ptr to it.
  8. */
  9. void getRestaurant(restaurant* ptr, int i, Sd2Card* card, RestCache* cache) {
  10.     // calculate the block with the i'th restaurant
  11.     uint32_t block = REST_START_BLOCK + i/8;
  12.  
  13.     // if this is not the cached block, read the block from the card
  14.     if (block != cache->cachedBlock) {
  15.         while (!card->readBlock(block, (uint8_t*) cache->block)) {
  16.             Serial.print("readblock failed, try again");
  17.         }
  18.         cache->cachedBlock = block;
  19.     }
  20.  
  21.     // either way, we have the correct block so just get the restaurant
  22.     *ptr = cache->block[i%8];
  23. }
  24.  
  25. // Swaps the two restaurants (which is why they are pass by reference).
  26. void swap(RestDist& r1, RestDist& r2) {
  27.     RestDist tmp = r1;
  28.     r1 = r2;
  29.     r2 = tmp;
  30. }
  31.  
  32. // Insertion sort to sort the restaurants.
  33. void insertionSort(RestDist restaurants[], int restaurantsAdded) {
  34.     // Invariant: at the start of iteration i, the
  35.     // array restaurants[0 .. i-1] is sorted.
  36.     for (int i = 1; i < restaurantsAdded; ++i) {
  37.         // Swap restaurant[i] back through the sorted list restaurants[0 .. i-1]
  38.         // until it finds its place.
  39.         for (int j = i; j > 0 && restaurants[j].dist < restaurants[j-1].dist; --j) {
  40.             swap(restaurants[j-1], restaurants[j]);
  41.         }
  42.     }
  43. }
  44.  
  45. // Computes the manhattan distance between two points (x1, y1) and (x2, y2).
  46. int16_t manhattan(int16_t x1, int16_t y1, int16_t x2, int16_t y2) {
  47.     return abs(x1-x2) + abs(y1-y2);
  48. }
  49.  
  50.  
  51. int pivotSort(RestDist restaurants[], int start, int end, int pi) {
  52.     int n = end - start;
  53.  
  54.     swap(restaurants[start + pi], restaurants[end]);
  55.     int lo = 0;
  56.     int hi = n - 1;
  57.  
  58.     while (lo <= hi) {
  59.         if (restaurants[start + hi].dist > restaurants[end].dist) {
  60.             hi--;
  61.         } else if (restaurants[start + lo].dist <= restaurants[end].dist) {
  62.             lo++;
  63.         } else {
  64.             swap(restaurants[start + lo], restaurants[start + hi]);
  65.         }
  66.     }
  67.  
  68.     swap(restaurants[start + lo], restaurants[end]);
  69.     return start + lo;
  70. }
  71.  
  72. void quickSort(RestDist restaurants[], int start, int end) {
  73.     int length = end - start;
  74.     if (start >= end)
  75.         return;
  76.  
  77.     int pivot = (length) / 2;
  78.     int newPivot = pivotSort(restaurants, start, end, pivot);
  79.     quickSort(restaurants, start, newPivot - 1);
  80.     quickSort(restaurants, newPivot + 1, end);
  81. }
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98. /*
  99.     Fetches all restaurants from the card, saves their RestDist information
  100.     in restaurants[], and then sorts them based on their distance to the
  101.     point on the map represented by the MapView.
  102.  
  103.     Returns the number of restaurants which satisfy the rating level
  104. */
  105. int getAndSortRestaurants(const MapView& mv, RestDist restaurants[], Sd2Card* card, RestCache* cache, int sortingType, int rating) {
  106.     restaurant r;
  107.  
  108.     // First get all the restaurants and store their corresponding RestDist information.
  109.     int restaurantsAdded = 0;
  110.     for (int i = 0; i < NUM_RESTAURANTS; ++i) {
  111.         getRestaurant(&r, i, card, cache);
  112.         int16_t restaurantRating = max((r.rating+1)/2, 1);
  113.  
  114.         if (restaurantRating >= rating) {
  115.             restaurants[restaurantsAdded].index = i;
  116.             restaurants[restaurantsAdded].dist = manhattan(lat_to_y(r.lat), lon_to_x(r.lon),
  117.                                                                             mv.mapY + mv.cursorY, mv.mapX + mv.cursorX);
  118.             restaurantsAdded++;
  119.         }
  120.     }
  121.  
  122.  
  123.     int time = millis();
  124.  
  125.      // quicksort or both
  126.     if (sortingType == 0 || sortingType == 2)
  127.         quickSort(restaurants, 0, restaurantsAdded);
  128.  
  129.     // insertion sort or both
  130.     if (sortingType == 1 || sortingType == 2)
  131.         insertionSort(restaurants, restaurantsAdded);
  132.  
  133.     int elapsedTime = millis() - time;
  134.     Serial.println("Sorting time: ");
  135.     Serial.print(elapsedTime);
  136.     Serial.println(" ms");
  137.  
  138.     return restaurantsAdded;
  139. }
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