• API
• FAQ
• Tools
• Archive
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)) {
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.
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) {
117.                                                                             mv.mapY + mv.cursorY, mv.mapX + mv.cursorX);
119.         }
120.     }
121.
122.
123.     int time = millis();
124.
125.      // quicksort or both
126.     if (sortingType == 0 || sortingType == 2)
128.
129.     // insertion sort or both
130.     if (sortingType == 1 || sortingType == 2)