Organize lists according to criterion of sequential order

Hello everyone,

Here I come again with another topic about my automation process project. Before I start explaining the issue I'll make a little synthesis about the project. It's fertirrigation process basically and I'll use Arduino as the microcontroller to trigger solenoids to release water, open sectors, open bombs etc...

All this actions will happen in a previously determined moment, which are stored in objects containing LinkedLists with some values which I'll call Criteria Order

I suggest you to use this link to better understand how this values are received :

Then copy this byte chain into the parser :

{"ID":1002,"Program":"PRG VRO","Schedules":[{"Day":3,"Hour":"05:00:00","Eventos":[{"Sector":2,"Duration":1500,"Sequencial":1,"Recipe":"REC01","Water":1.5,"Sector":3,"Duration":1500,"Sequencial":2,"Recipe":"REC01","Water":3.0,"Sector":2,"Duration":1300,"Sequencial":3,"Recipe":"REC01","Water":3.0,"Fertilizers":[{"Silo":"Silo 1","Fertilizer":"Potássio","Volume":2.3}]}]},{"Day":3,"Hour":"07:00:00","Eventos":[{"Sector":2,"Duration":1500,"Sequencial":3,"Recipe":"REC01","Water":1.5,"Fertilizers":[{"Silo":"Silo 1","Fertilizer":"Potássio","Volume":2.3}]}]},{"Day":6,"Hour":"05:00:00","Eventos":[{"Sector":2,"Duration":1500,"Sequencial":3,"Recipe":"REC01","Water":1.5,"Fertilizers":[{"Silo":"Silo 1","Fertilizer":"Potássio","Volume":2.3}]}]},{"Day":4,"Hour":"11:00:00","Eventos":[{"Sector":2,"Duration":34,"Sequencial":3,"Recipe":"REC01","Water":113.05,"Fertilizers":[{"Silo":"Silo 15","Fertilizer":"Potássio","Volume":2.7}]}]}]}

This is an imaginary example of how I receive the values mentioned before. OK, now that you are familiar with the procedure we can move on. I extracted from this byte chain all values of interest and then stored them within objects/lists. Every '-' in the parser represts a list. Among these values, 5 of them are 'Order Criteria' which are : Day,Hour,Minute,Second, Sequencial. (From most relevant to less relevant).

I used this lib to manage Linked Lists GitHub - ivanseidel/LinkedList: 🔗 A fully implemented LinkedList made to work with general Microcontrollers and Arduino projects

So take this as an example :

Consider "Schedules" as my mother list, within it there will be indexes with object and other linked lists. So :

while(file.available()){

ReadByteChain();

Schedules.add(index,object);
index++;}

This will read all the chain, store the values and build a list containing everything, however the order of things will be the the same order as they have been received, it would be STUNNING if I could organize them based in Criteria Order. I can't even Google this matter, can someone help ? This post has a lot of content, so If you guys need any else info just let me know.

Regards,

Rezik

first a quick remark, the library can add to the end of the list easily

// add(obj) method will insert at the END of the list
myList.add(myObject);

so you don't need to maintain an index and do

Schedules.add(index,object);
index++;

if you do just Schedules.add(object);you should be fine

To your question:

You know the format of the element of the list right? so just implement a sorting algorithm by having a spare temp variable holding the current element and exchange the attributes of the list elements that need to be swapped

here is an example how to sort a simple list made with integers using the quickSort algorithm

#include <LinkedList.h>

LinkedList<int> myList = LinkedList<int>(); // I have integers in my list

void quickSort(int left, int right) {
  int i = left, j = right; // index in the list

  int pivot = myList.get((left + right) / 2); // I'm using int here because that's what is in my list as compare criteria
  int tmp; // here I use an int because that's what is in my list, should be your list content structure

  while (i <= j) {
    while (myList.get(i) < pivot) i++;// would need to access attributes for more complex structures
    while (myList.get(j) > pivot) j--;

    if (i <= j) {
      // need to exchange the content of attributes of list elements at index i and j.
      tmp = myList.get(i); // save the i element to swap. should be one of your structure instead of an int
      myList.set(i, myList.get(j));
      myList.set(j, tmp);
      i++; j--;
    }
  }

  if (left < j) quickSort(left, j);
  if (i < right) quickSort(i, right);

}

void setup()
{
  Serial.begin(115200);

  // randomize
  randomSeed(analogRead(0));

  // Add 10 random numbers between 1 and 100 to the list
  for (byte i = 0; i < 10; i++)  myList.add(random(1, 101));

  int listSize = myList.size();
  Serial.println("------");
  Serial.print(listSize); Serial.println(" integers in the list");
  // Print the list
  for (byte i = 0; i < listSize; i++) {
    Serial.print((int) myList.get(i)); Serial.print(" ");
  }
  Serial.println();
  Serial.println("------");
  // sort the list ascending
  quickSort(0, listSize - 1);

  Serial.print(listSize); Serial.println(" Sorted integers in the list");
  // Print the list
  for (byte i = 0; i < listSize; i++) {
    Serial.print((int) myList.get(i)); Serial.print(" ");
  }
  Serial.println();
}


void loop() {}

there are 3 places you would need to modify the quickSort function:


  int pivot = myList.get((left + right) / 2); // I'm using int here because that's what is in my list as compare criteria
  int tmp; // here I use an int because that's what is in my list, should be

pivot needs to be the attribute of a list element you want to sort on.
tmp needs to be be the same structure as an element of the list


    // would need to access attributes for more complex structures
    while (myList.get(i) < pivot) i++;
    while (myList.get(j) > pivot) j--;

you obviously need to compare the attribute from the ith element of the list with the attribute you extracted for pivot, same with j.


      // need to exchange the content of attributes of list elements at index i and j.
      tmp = myList.get(i); // save the i element to swap. should be one of your structure instead of an int
      myList.set(i, myList.get(j));
      myList.set(j, tmp);

modify this to make sure you extract into tmp all the attributes you need to swap the list elements.

Build a Criteria-ordered set of indexes into the compiled list, as the data arrives if possible, then use that to re-link the list links.

J-M-L your code is esplendid, it will be really useful.Really much thanks ! However as you already said, few changes needs to be done. So i'll invite you to think with me and we'll see if i got this code right.

Unfortunately I missed an important detail, I'm using a RTC DS1307 to serve as reference to the tasks time. So here comes a little problem. Considering data as being represented from 0 to 6 which are equal to Sunday to Saturday respectively. Let's create an imaginary scenario : We are on Thursday, which is the same of day 4 (RTC is saying that to us), If i ask you which day is closer to 4, 3 or 6? The right answer is 6 obviously. Because Saturday is closer from Thursday than Wednesday is.

With that being said I need to implement this idea to the RTC otherwise it would answer that previous question choosing 3 as the answer, right? So if I create a method which returns a int or float representing the time in seconds to my event to happen i would solve this problem I think.

So changes to be made so far :

pivot and tmp should be changed to "list" id instead of "int"

int pivot = myList.get((left + right) / 2); 
int tmp;

Instead of myList.get and pivot I would call that method I intended to create

while (i <= j) {
    while (myList.get(i) < pivot) i++;
    while (myList.get(j) > pivot) j--;
}

Do you agree?

Regards,

Rezik

With that being said I need to implement this idea to the RTC otherwise it would answer that previous question choosing 3 as the answer, right? So if I create a method which returns a int or float representing the time in seconds to my event to happen i would solve this problem I think.

You don't need to go to seconds etc... You just need a function that given 2 days of the week and knowing the current day will tell you if the first one is strictly < to the second one... that is you do the same thing as x < y but with a bit of intelligence.

for example

const byte todayDayNb = 3;  // get that from your RTC, here for example only

bool willSeeDay1BeforeDay2(byte day1, byte day2)
{
  if (day1 < todayDayNb) day1 += 7;
  if (day2 < todayDayNb) day2 += 7;
  return ((day1 - todayDayNb) < (day2 - todayDayNb));
}

will do the trick.

you can run this code for example to print all the possibilities:

const char * weekdays[] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
const byte todayDayNb = 3;  // get that from your RTC, here for example only

bool willSeeDay1BeforeDay2(byte day1, byte day2)
{
  if (day1 < todayDayNb) day1 += 7;
  if (day2 < todayDayNb) day2 += 7;
  return ((day1 - todayDayNb) < (day2 - todayDayNb));
}

void setup() {
  Serial.begin(115200);

  Serial.print ("Today is "); Serial.println(weekdays[todayDayNb]);
  Serial.println ("-----------------------");
  for (byte d1 = 0; d1 < 7; d1++) {
    for (byte d2 = 0; d2 < 7; d2++) {
      if (d1 != d2) {
        if (willSeeDay1BeforeDay2(d1, d2)) {
          Serial.print ("I will see ");
          Serial.print (weekdays[d1]);
          Serial.print (" before seeing ");
          Serial.println (weekdays[d2]);
        } else {
          Serial.print ("I will not see ");
          Serial.print (weekdays[d1]);
          Serial.print (" before seeing ");
          Serial.println (weekdays[d2]);
        }
      }
    }
    Serial.println ("-----------------------");
  }
}

void loop() {}

So, you want an algorithm to sort a linked list?

A difficulty is that you want to minimize allocating and de-allocating memory. I'd be inclined to hack up the class itself and add a sort() method to it.

As for algorithm, I'd be doing some sort of modified merge sort - an in place version. The algorithm would just find chains of elements in sequence and merge them, running through the list repeatedly until the whole thing was sorted.

You know: I might fork the repo and add a sort method.

-- EDIT --

Forked the repo, gcc tells me that there are problems with the code. Giving up.

PaulMurrayCbr:
A difficulty is that you want to minimize allocating and de-allocating memory. I'd be inclined to hack up the class itself and add a sort() method to it.

ideally the list will hold pointers to objects or structure (rather than a copy of the structure) and thus you can just swap attributes without de-allocating and re-allocating upon swapping elements in a sort.

But yes extending the linked list class with a sort method would be cool. Need to find a way to give the library a pointer to a function comparing two elements of the list (or need to subclass / overlaod) and implement any kind of sorting algorithm

Small question: how big in bytes is the list to be and what Arduino will hold it?

You can do large lists on SD, in time. One way is to generate sorted index files for the original data.

GoForSmoke:
Small question: how big in bytes is the list to be and what Arduino will hold it?

You can do large lists on SD, in time. One way is to generate sorted index files for the original data.

good point indeed

OK!

I have forked the repo and added a sort() method to the linked list library. My fork is here: GitHub - PaulMurrayCbr/LinkedList: A fully implemented LinkedList made to work with Arduino projects.

I have also put in a pull request, and so hopefully ivanseidel on GitHub will merge it in.

Drat - didn't update the docs. Have to do that now. I did add an example, though.

Where does this list exist to be sorted?

This will read all the chain, store the values and build a list containing everything,

Because if you read and store to HD or enough RAM to hold it all before sorting then you can change the links without concern for wearing out the storage hardware in the process. SD is different, can be worn out at computer speed changing one record at a time. You end up rewriting at least one sector for every stored object you change.
Sure it will take a good while but the practice.. it becomes "whut werks" and that will lead to apps that don't take so long to wear out what would not if used correctly.

Maybe there would be a market for an SPI ram drive board that acts like SD, perhaps with SD backup for power-off storage.

PaulMurrayCbr:
OK!

I have forked the repo and added a sort() method to the linked list library. My fork is here: GitHub - PaulMurrayCbr/LinkedList: A fully implemented LinkedList made to work with Arduino projects.

I have also put in a pull request, and so hopefully ivanseidel on GitHub will merge it in.

Drat - didn't update the docs. Have to do that now. I did add an example, though.

Thanks for your support I'm sure the community will enjoy this improvement.

You don't need to go to seconds etc... You just need a function that given 2 days of the week and knowing the current day will tell you if the first one is strictly < to the second one... that is you do the same thing as x < y but with a bit of intelligence.

Well I'm not sure if this simple idea would cover my problem, since I can have multiple task applications in the same day I would need to know inside that day which task comes first, secondly etc etc.. So I guess I'll need my deltaS function.

So I would like to share what has been modified . I could call deltaS inside quickSort() method or Sort() (by PaulMurrayCbr) . I found Sort() more friendly so basically I called deltaS function inside int compare(). I appreciate syxtax corrections in this :

#include <LinkedList.h>
#include <Wire.h>
#include "RTClib.h"

RTC_DS1307 rtc;

char daysOfTheWeek[7][12] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};

LinkedList<Schedules*> schedules = LinkedList<Schedules*>();

Schedules *moment = new Schedules; // moment is an object which all linked lists are.


LinkedList<Schedules *> list;
void setup() {
 Serial.begin(9600);
  while (!Serial);

  Serial.print("Beginning sketch in ");
  for (int i = 3; i > 0; i--) {
    Serial.print(i);
    Serial.print(' ');
    delay(500);
  }
  Serial.println("0.");

  Serial.println("Loading some strings into the linked list");
  Serial.println();

  char *p;
  int col = 0;
  for (p = strtok(testString, " ,."); p; p = strtok(NULL, " ,.")) {
    Serial.print(p);
    Serial.print(' ');
    col += strlen(p) + 1;
    if (col >= 80) {
      Serial.println();
      col = 0;
    }
    list.add(p);
  }


  if (col) {
    Serial.println();
    col = 0;
  }
  
  Serial.println();
  Serial.println("Sorting");
  Serial.println();

list.sort(compare);

  Serial.println();
  Serial.println("Result");
  Serial.println();

  while (p = list.shift()) {
    Serial.print(p);
    Serial.print(' ');
    col += strlen(p) + 1;
    if (col >= 80) {
      Serial.println();
      col = 0;
    }
  }
  if (col) {
    Serial.println();
    col = 0;
  }

  Serial.println();
  Serial.println("Done!");
}



int secondsToHappen (Schedules*moment){
  int deltaS =0;
 
 if(moment->getDay(dia) < now.day()){
    deltaS = ((momento->getDay(dia) +7) - now.day())*(86400)
    }
  else {
    deltaS = (moment->getDay(dia) - now.day())*86400
    }
         deltaS = deltaS + (3600* (moment-> *getHora(hora) - now.hour())) + ((moment->getMinute(minuto)- now.minute()) * 60) + (moment->getSecond(segundo) - now.second());
    }



int compare(Schedules*&a,Schedules*&b) {
  return secondsToHappen(Schedules*&a - Schedules*&b);
}



void loop() {
  // put your main code here, to run repeatedly:

}

Thanks for your time and support.

Regards,

rezik

If you don't mind code that's doomed to fail in 2038 then you can use Unix Time Stamps.
Those are 32-bit seconds since the start of Jan 1, 1970.
There's a complete set of functions to go back and forth between UTS and times/days/and dates.

The stamps print out nice as 8 hex digits for serial text data log time stamps; later always makes a bigger number than earlier.

On Jan 19, 2038, the whole scheme comes crashing down. One plan is to move to 64-bit time stamps which have the capacity to be working when our sun turns into a red giant and Earth gets the ultimate global warming.

int compare(Schedules*&a,Schedules*&b) {
  return secondsToHappen(Schedules*&a - Schedules*&b);
}

If you are storing pointers to Schedules in your linked list (ie: you create Schedules objects with new), then the syntax would be:

int compare(Schedules*&a,Schedules*&b) {
  return secondsToHappen(a)  - secondsToHappen(b) ;
}

int secondsToHappen(Schedules *s) {
  // work out how many seconds from now to *s
}

Rather than re-sorting the list each time, a different way to go is to sort the list once and then to pop the first item off the list and add it to the tail of the list.

The problem is that that will cause list nodes to be freed and reallocated. Maybe the linked-list object needs a "roll" function.

I apreciate your suggestion, thanks !

Let me just ask you question about this LinkedList lib, with the intention of saving the char array content within an object I made this :

Read array, print array content, save it within object :

i = 0; s = 0;
        char sArray[7];
        LeCaracter('"', arquivo);
        s = arquivo.read();
        while (s != '"') {
          sArray[i++] = s;
          sArray[i] = '\0'; 
          s = arquivo.read();       
        }
        for(i=0;i<7;i++){
        Serial.print(sArray[i]);}
        //fertilizante->setSilo(*sArray);

setSilo and getSilo shown below :

void Fertilizantes::setSilo(char *s){
	 strcpy(_silo,s);
 }

char Fertilizantes::getSilo(){
	return _silo;
}

Why fertilizante->setSilo(*sArray); is not doing what I expect ? Is there synthax error? Thanks in advance.

Why fertilizante->setSilo(*sArray); is not doing what I expect ?

How are we supposed to know? You don't way what it actually does. You don't way what you expect it to do.

Where is _silo defined? How is it defined? Is it really large enough to hold whatever string you pass to the function?

PaulS:
How are we supposed to know? You don't way what it actually does. You don't way what you expect it to do.

Where is _silo defined? How is it defined? Is it really large enough to hold whatever string you pass to the function?

You don't way what it actually does.

Before the code there is a little explanation "Read array, print array content, save it within object", thought this was enough.

You don't way what you expect it to do.

rezik:
Let me just ask you question about this LinkedList lib, with the intention of saving the char array content within an object I made this :

Really ??? :o

Where is _silo defined? How is it defined?

Here :

class Fertilizantes
	{
		public :
			void setSilo(char *s);
			void setVol(float volumeFert);
			char getSilo();
			float getVol();

		private :
			char _silo;
			float volumeF;
	};

Is it really large enough to hold whatever string you pass to the function?

I declared sArray[7], this is the maximum size of the string at this moment, since its default is Silo+espace bar+ int1 int2 .

I declared sArray[7], this is the maximum size of the string at this moment, since its default is Silo+espace bar+ int1 int2 .

And yet you try to copy it into

			char _silo;

How the hell can you expect to shove a size 7 foot in a size 1 shoe?

PaulS:
And yet you try to copy it into

			char _silo;

How the hell can you expect to shove a size 7 foot in a size 1 shoe?

Amazing ! So the synthax I was using to save an array within an object was right ?

class Fertilizantes
	{
		public :
			void setSilo(char *s);
			void setVol(float volumeFert);
			char getSilo();
			float getVol();

		private :
			char _silo[7];
			float volumeF;
	};

Fits just right then?

Fits just right then?

You really should use strncpy(), so you can make sure that you are not trying to copy more data into the _silo array than it can hold. Otherwise, those snippets look better.

Except that GetSilo() returns a char, not a char array, so you can't return the array. GetSilo()'s return type should be char *.