Sorting question. General Answer OK

Using Arduino Programming Questions
#1

Hello Gurus,

I'm almost finished with a Scalextric, 4-lane slot car lap counter. The prototype is working. The maximum number of racers is 4 (4 lanes of analog slot cars). My code is sloppy and buggy but it's getting the job done.

What I am struggling with is how to assign (and the logic behind) placings for a lane (i.e. car). That is, "First" "Second" "Third" or "Fourth." I want these to display in real time as a particular lane's laps goes to zero. Since maybe less than 4 cars could be racing.

The interface is simple with the user inputing a custom number of laps to 99 using buttons and interacting with an LCD. The next step is calibrating photoresistors to count laps. Finally there is a count down and the race begins. The number of laps are tracked for each lane, and a real-time count down is provided in the main void loop{} sketch to the LCD. I can get it to count down no problems.

Because of my superficial level of C++ knowledge, I am struggling to determine which car is in which place. Now, the user will be able to see that they have no laps remaining and could determine this on their own, but I want this to be done by the arduino. I could do it by brute force but the amount of coding to test would be something like 4^4 conditions. I feel there must be something easier with arrays or sorting or something.

Can you point me towards further reading buzzwords or make a suggestion on what I should look for? A sorting algo at first seemed to be the ticket, but because I can't figure out how to keep the lanes corresponding to the unsigned long "times" in the array. I feel like there is a simple solution that I am failing to grasp.

Many thanks.
DrG

#2

Use qsort().

#3

I’d disagree, qsort is just a type disaster waiting to happen.

Use std::sort instead.

It’s available out of the box for all common Arduino boards except AVR, just #include and you’re good to go.
On AVR, you can install it as part of the ArduinoSTL library or the Arduino-Helpers library (example sketch).

Regarding your original question, you can create a struct or a tuple that groups a lane number and a timestamp. Then sort the array of tuples by timestamp. The first tuple has the earliest time stamp and the lane number of the winning car, etc.

Pieter

#4

I am curious. I am a huge fan of STL, or I was when I was coding for PC, that was some time ago. Are you telling me I can use such features safely and without much memory overhead in this MPU environment? That would really make a difference in how I approach some things...
also will test with STM32 boards of different flavours since you mention the AVR difference.

I already often use Streaming.h by Mikal Hart for output.

#5

Thank you Pieter. Just after I posted, I learned of the existence of "struct".

I assume you can sort "structs" by a single element within it? I guess you would have a "Placing" element within the structure.

thinking about something like this:

struct {
int LapsRemaining;
bool FinishedRace;
int Placing;
unsigned long FinishTime;

} Lane1, Lane2, Lane3, Lane4;

I will do some reading. Dang it. This was supposed to be "fun, quick and easy." At least with the "stay at home" orders I have something to tinker with.

My best,
DrG

#6

doktor_g:
I assume you can sort "structs" by a single element within it? I guess you would have a "Placing" element within the structure.

Certainly, you can. Struct elements are identified with the dot operator, as in:
int current = widget[i].Placingwhere widget is an array of your structs.

However, I think the STL idea might be good for you because if you can get over the initial pain of figuring it out, all the really messy work is done for you by the library. There are, I don't know, probably 100 sort algorithms? There are some simple ones if you don't care about performance. The one that I can always remember is the swap sort - while indexing through the array, swap consecutive pairs of elements, if the first is greater than the second. Keep doing this until you reach the end without a need to swap. That may have over simplified it but it works.

#7

aarg:
I am curious. I am a huge fan of STL, or I was when I was coding for PC, that was some time ago. Are you telling me I can use such features safely and without much memory overhead in this MPU environment?

When using the STL on microcontrollers, there are two main concerns: dynamic memory usage and exceptions.

The same precautions of heap fragmentation that you have to take when using Arduino Strings still apply to all parts of the STL that allocate memory (e.g. std::string, std::vector, etc.).

Most Arduino Cores (e.g. AVR, Teensy) disable exceptions altogether, so if you use std::array::at with an index that’s out of bounds, it won’t throw an exception, but it’ll either just read/write out of bounds (like ArduinoSTL), or it’ll stop your program (Arduino-Helpers prints the error to Serial if debugging is enabled, and enter a loop blinking the built-in LED).
I don’t know what the toolchain’s STL does on ARM boards.
Espressif boards have exceptions enabled, so you can throw and catch exceptions like you would in a desktop application. An uncaught exception will abort the program, print a stack trace to Serial, and reset the chip.

Luckily large parts of the STL don’t rely on dynamic memory usage or exceptions, and it’s perfectly fine to use things like the standard algorithms, math functions, type traits, limits, std::array, std::tuple, std::optional, std::variant, etc. Again, there are cases where an exception could be thrown (array, optional, variant) so it’s up to you to make sure that this doesn’t happen.
Even though it uses dynamic memory, std::vector can still be very useful, and you can use it without problems if you preallocate them etc. Smart pointers are very handy when you occasionally do need dynamic memory allocations.

Some parts of the STL are not optimized for MCUs of course, so depending on the implementation, std::bitset<8> might use more than one byte of storage.
Personally, I haven’t had any problems with memory usage, even on AVR.

Here’s a simple std::sort example with cars and lanes to get you started:

[color=#5e6d03]#include[/color] [color=#434f54]<[/color][b][color=#d35400]Arduino_Helpers[/color][/b][color=#434f54].[/color]h[color=#434f54]>[/color]

[color=#5e6d03]#include[/color] [color=#434f54]<[/color][b][color=#d35400]AH[/color][/b][color=#434f54]/[/color]STL[color=#434f54]/[/color]algorithm[color=#434f54]>[/color]               [color=#434f54]// std::sort[/color]
[color=#5e6d03]#include[/color] [color=#434f54]<[/color][b][color=#d35400]AH[/color][/b][color=#434f54]/[/color]STL[color=#434f54]/[/color]tuple[color=#434f54]>[/color]                   [color=#434f54]// std::tie[/color]
[color=#5e6d03]#include[/color] [color=#434f54]<[/color][b][color=#d35400]AH[/color][/b][color=#434f54]/[/color]PrintStream[color=#434f54]/[/color]PrintStream[color=#434f54].[/color]hpp[color=#434f54]>[/color] [color=#434f54]// Serial << ... << endl;[/color]

[color=#00979c]struct[/color] Car {
  [color=#434f54]/// The lane this car is in.[/color]
  [color=#00979c]uint8_t[/color] lane;
  [color=#434f54]/// How many laps the car has left[/color]
  [color=#00979c]uint8_t[/color] lapsLeft;
  [color=#434f54]/// The timestamp when the car entered its current lap[/color]
  [color=#00979c]unsigned[/color] [color=#00979c]long[/color] lapTime;

  [color=#434f54]/// Less than operator to compare the position of two cars for sorting[/color]
  [color=#00979c]bool[/color] [color=#00979c]operator[/color][color=#434f54]<[/color](Car that) [color=#00979c]const[/color] {
    [color=#434f54]// Lexographically compare the number of laps left and the lap start time[/color]
    [color=#5e6d03]return[/color] std[color=#434f54]:[/color][color=#434f54]:[/color]tie([color=#5e6d03]this[/color][color=#434f54]-[/color][color=#434f54]>[/color]lapsLeft[color=#434f54],[/color] [color=#5e6d03]this[/color][color=#434f54]-[/color][color=#434f54]>[/color]lapTime)
           [color=#434f54]<[/color] std[color=#434f54]:[/color][color=#434f54]:[/color]tie(that[color=#434f54].[/color]lapsLeft[color=#434f54],[/color] that[color=#434f54].[/color]lapTime);
    [color=#434f54]// The number of laps left is the most important criterion, if a car has more[/color]
    [color=#434f54]// laps left, it's always behind the other car.[/color]
    [color=#434f54]// If they have the same number of laps left, the car that passed the[/color]
    [color=#434f54]// checkpoint/counter first is (probably) before the other car.[/color]
  }
};

Car cars[color=#000000][[/color][color=#000000]][/color] [color=#434f54]=[/color] {
  {1[color=#434f54],[/color] 3[color=#434f54],[/color] 1000}[color=#434f54],[/color] [color=#434f54]// Car in lane 1, has 3 laps left, started this lap at t=1000ms[/color]
  {2[color=#434f54],[/color] 2[color=#434f54],[/color] 1200}[color=#434f54],[/color]
  {3[color=#434f54],[/color] 2[color=#434f54],[/color] 1100}[color=#434f54],[/color]
  {4[color=#434f54],[/color] 2[color=#434f54],[/color] 1300}[color=#434f54],[/color]
};

[color=#00979c]void[/color] [color=#5e6d03]setup[/color]() {
  [b][color=#d35400]Serial[/color][/b][color=#434f54].[/color][color=#d35400]begin[/color](115200);
  [color=#5e6d03]while[/color] ([color=#434f54]![/color][b][color=#d35400]Serial[/color][/b]);

  [color=#434f54]// Sort the array of cars by position[/color]
  std[color=#434f54]:[/color][color=#434f54]:[/color]sort(std[color=#434f54]:[/color][color=#434f54]:[/color][color=#d35400]begin[/color](cars)[color=#434f54],[/color] std[color=#434f54]:[/color][color=#434f54]:[/color][color=#d35400]end[/color](cars));
  [color=#434f54]// Print the leader board to Serial[/color]
  [color=#5e6d03]for[/color] ([color=#00979c]const[/color] Car [color=#434f54]&[/color]car [color=#434f54]:[/color] cars)
    [b][color=#d35400]Serial[/color][/b] [color=#434f54]<<[/color] car[color=#434f54].[/color]lane [color=#434f54]<<[/color] endl;

  [color=#434f54]// Expected output:
  //   3
  //   2
  //   4
  //   1

  // Implementation tips:
  //
  // 1. Initialize all cars with their lane number, set the laps remaining
  //    to the total number of laps, e.g. 5, initialize the lap start time to
  //    zero.
  // 2. When a car passes the checkpoint/counter, subtract one from the laps
  //    remaining, and record the current time as the lap start time.
  // 3. Sort the array of cars as shown above, and print the leaderboard.
  //
  // There are two options too look up a car given its lane:
  //
  // a. Keep the main cars array sorted by lane number, so you can get the
  //    array index from the lane number directly.
  //    When sorting the array, don't sort the main cars array, but sort a copy
  //    of the array.
  // b. Sort the main cars array by position, and look up the car by lane
  //    number using std::find.[/color]
}

[color=#00979c]void[/color] [color=#5e6d03]loop[/color]() {}
#8