Queue "bubble sort"

Using Arduino Programming Questions
1

Hi,

I am testing the library "CircularBufferLib" with an Arduino UNO. I am using this specific library because it is the only one I have found that can change values in the middle of the queue.

What I would like to do is that when I add some values to the queue, it changes the order so that the first one is the lowest. The problem I have had is that I have created a program that only works sometimes. The idea was to make another buffer to copy the value that I want to put to the front and then swap both numbers in the original buffer.

This is the code;

#include <CircularBufferLib.h>


CircularBuffer<int> buffer(50);
CircularBuffer<int> pens(50);


volatile int state=0;


void setup() {
   Serial.begin(9600);
  delay(200);

buffer.Add(7);
buffer.Add(5);
buffer.Add(6);
buffer.Add(4);
buffer.Add(2);
buffer.Add(2);
buffer.Add(2);
 


}




void loop() {
int count=buffer.Count();
switch(state){
  case 0:
  state=1;
  break;

  case 1:
    
    

    for(int i = 0; i <count; i++ ){
      
      if (buffer[i]<buffer.First()){
        pens.Add(buffer[i]);
        buffer.ReplaceAt(i, buffer.First());
        buffer.ReplaceFirst(pens.ExtractFirst());
        
        state--;
      }
        
      }
      
     state++;
      break;

  case 2:
    Serial.print(buffer.First());
     Serial.print("\n");
  
      break;
}


}

It is like it only works the first time the number changes, and then it does something strange.

(Maybe is the library that does not work properly)

Any type of help will be appreciated.

Thank you.

2

Search for ring buffer, and do not sort the queue each time.

3

Your buffer does not seem to be sorted in the first place.

So, is this the question? "Given a sorted buffer, how can I add a value in such a way that the result is also a sorted buffer?"

4

My question is how can I create a buffer that the lower values entered at any time get returned before the higher ones that are already stored.

I also considered using ringbuffer, but it does not give me the possibility to change a value in the middle of the buffer, only read.

Thank you.

5

So let's stay the buffer contains [1, 2, 5, 9], you add 4 and the result should be [1, 2, 4, 5, 9]?

6

I am doing this because I want to create a function for an elevator algorithm, in which if there is an input call which is closer to the target the elevator it is moving to, it will stop first at the nearest floor.

The inputs are stored in a queue using an ISR.

7

Well, the result should always be only the smallest one, the order of others does not matter

8

Then you could use an array of size number_of_floors, search for the smallest item, set that item to something invalid (e.g., -1) and return the value.

From an algorithmic point of view, this is not efficient, but for small examples, like the number of floors in a building, this should be sufficient.

9

I would like it to have memory, like if you are at floor 0, then press consecutively 2,1,3 it should first go to 1, then 2 and finally 3

10

I think we have identified a xy problem. x is the elevator algorithm problem you have encountered, and a ring buffer is your perceived solution, but you have a problem with your perceived solution, so you are asking about y, the ring buffer problem. You should stick with x being the problem as I think you can resolve your problem with a normal array and some access control. A ring buffer is generally used for interrupted queuing of a stream of data that might otherwise create a bottleneck in LIFO access of a normal array. How many floors are there in the elevator?

1 Like
11

[2, 1, 3] will become [2, -1, 3], [-1, -1, 3], [-1, -1, -1] returning 1, 2, 3 respectively when you follow the procedure described above.

This will not lead to nice elevator behaviour though. You probably also want to take the direction and the position of the elevator into account.

12

there are 5 floors

the function I wrote before in the algorithm should be something like this:

void newtarget(){
 int dist;
  count=higher.Count();
  for(int i = 0; i < count; i++ ){
    dist=stepper.currentPosition()-FloorLevel[higher[i]];
    if (abs(dist) < abs(stepper.distanceToGo())){
      temp.Add(higher[i]);
      higher.ReplaceAt(i, higher.First());
      higher.ReplaceFirst(temp.ExtractFirst());
      stepper.moveTo(FloorLevel[higher.First()]);
      state=3;
    }
  }
    
}
13

I have already taken all into account in the ISR, there is no need to worry about that, it works fine.

but the problem is when I want to reorganize the queue

14

If the floor where the elevator rests is 0 in the algorithm, with the floor above being 1 and the floor below -1, wouldn't the algorithm be as simple as absolute value? If you add a vector, so if it's going up, it will not look below it...

15

I would probably use an array of booleans to denote which buttons are pressed. E.g., [false, true, false, true] means that buttons on floor 1 and 3 are pressed. If your elevator is on floor 2 and going up, it simply needs to check all elements larger than 2, stop whenever the value is true and set it to false.

[edit] Maybe not, that would not be very fair in some cases.

16

I agree with @Perehama. This is an X-Y problem. Let's take a step back. Forget about any particular solution. Describe the problem.

How many lifts? (Sorry, "elevators"). How many floors? Can all lifts reach all floors?

17

It has only one elevator (5 floors).

My intention was to make 3 algorithms . 1 of them is finished (FIFO queue). Here is the code that works fine:

#include <AccelStepper.h>
#include <CircularBuffer.h>
#include <Servo.h>

Servo myservo;

#define dirPin 4
#define stepPin 5
#define motorInterfaceType 1

AccelStepper stepper = AccelStepper(motorInterfaceType, stepPin, dirPin);

const byte NumberOfFloors = 5;
const unsigned long FloorLevel[NumberOfFloors] = {0, 180, 360, 540, 720};
const unsigned long pins [NumberOfFloors] = {2, 3, 18, 19, 20};
const int LED[NumberOfFloors] = {40, 41, 42, 43, 44};

volatile int state = 0;
int doorspeed = 8;
int servopin = 14;



CircularBuffer<int,50> buffer;
CircularBuffer<int,20> led;

int segPins[] = {30, 31, 32, 33, 34, 35, 36};/*assigning pins of Arduino for the seven-segment*/

byte segCode[6][7] = { /*declaring an array of the number  from 0 to 9 in the order from a of g*/
  //a  b  c  d  e  f  g
  
  { 1, 1, 1, 1, 1, 1, 0},  // for displaying 0
  { 0, 1, 1, 0, 0, 0, 0},  // for displaying 1
  { 1, 1, 0, 1, 1, 0, 1},  // for displaying 2
  { 1, 1, 1, 1, 0, 0, 1},  // for displaying 3
  { 0, 1, 1, 0, 0, 1, 1},  // for displaying 4
  { 0, 0, 0, 0, 0, 0, 0},   // for displaying off
};
void displayDigit(int digit) /*creating a function for initializing the each segment of the display*/
{
  for (int a=0; a < 7; a++)
  {
    digitalWrite(segPins[a], segCode[digit][a]);/* instructing the respective segments for the numbers from 0 to 4 */
  }
}


void setup()
{
  Serial.begin(9600);
  delay(200);

  attachInterrupt(digitalPinToInterrupt(pins[0]), button0_ISR, RISING);
  attachInterrupt(digitalPinToInterrupt(pins[1]), button1_ISR, RISING);
  attachInterrupt(digitalPinToInterrupt(pins[2]), button2_ISR, RISING);
  attachInterrupt(digitalPinToInterrupt(pins[3]), button3_ISR, RISING);
  attachInterrupt(digitalPinToInterrupt(pins[4]), button4_ISR, RISING);
 myservo.write(180);
 for (int a=0; a < 5; a++) // assigning the OUTPUT mode to all the 7 seven-segments*/
  {
    pinMode(LED[a], OUTPUT);
  }

 for (int a=0; a < 7; a++) // assigning the OUTPUT mode to all the 7 seven-segments*/
  {
    pinMode(segPins[a], OUTPUT);
  }

  myservo.attach(servopin);

  stepper.setMaxSpeed(1000);
  stepper.setAcceleration(100);
}

void loop()
{
showdigit();

 switch (state){
  case 0:
    empty();
    break;
  
  case 1:
   steppermove();
   break;
 
  case 2:
   delay(100);
    door();
    delay(100);
    state=3;
    break;

  case 3:
   buffer.shift();
   state=0;
    break;
 }
  
}


void showdigit(){
  if(buffer.isEmpty()==false){
    displayDigit(buffer.first());
  }
  else{
    displayDigit(5);
  }
}


void empty(){
  if(buffer.isEmpty()==false) {
        stepper.moveTo(FloorLevel[buffer.first()]);
      //show led display
      state=1;
      }

}

void steppermove(){
  stepper.run();
  if (stepper.currentPosition() == FloorLevel[buffer.first()]){
          digitalWrite(LED[led.first()], LOW);
          led.shift();
          keepled();
        state=2;
      }
  
}

void interrupt(long pin){
  static unsigned long last_interrupt_time = 0;
  unsigned long interrupt_time = millis();
  if (interrupt_time - last_interrupt_time > 200) 
  {
    buffer.push(pin);
    led.push(pin);
    
  }
  last_interrupt_time = interrupt_time;
    digitalWrite(LED[pin], HIGH);
    delay(100);
     if (stepper.currentPosition() == FloorLevel[buffer.first()]){
          digitalWrite(LED[buffer.first()], LOW);
    }
}


void button0_ISR(){
    interrupt(0);
    
}

void button1_ISR(){
    interrupt(1);
   
}

void button2_ISR(){
    interrupt(2);
   
}

void button3_ISR(){
    interrupt(3);
   
}


void button4_ISR(){
    interrupt(4);
    
}



void door(){
  myservo.write(0);
      delay(1000);
      myservo.write(180);
  
}

void keepled(){
for(int i = 0; i < led.size(); i++ )
  digitalWrite(LED[led[i]], HIGH);
}

Then I want to make another that when it finishes a call input, it goes to the nearest one. This is the code (it does not work):

#include <CircularBufferLib.h>
#include <AccelStepper.h>
#include <Servo.h>


Servo myservo;

#define dirPin 4
#define stepPin 5
#define motorInterfaceType 1

AccelStepper stepper = AccelStepper(motorInterfaceType, stepPin, dirPin);

const byte NumberOfFloors = 5;
const unsigned long FloorLevel[NumberOfFloors] = {0, 100, 200, 300, 400};
const unsigned long pins [NumberOfFloors] = {2, 3, 18, 19, 20};
const int LED[NumberOfFloors] = {40, 41, 42, 43, 44};

volatile int state = 0;
int doorspeed = 8;
int servopin = 14;

CircularBuffer<int> buffer(50);
CircularBuffer<int> temp(10);


int segPins[] = {22, 23, 24, 25, 26, 27, 28};/*assigning pins of Arduino for the seven-segment*/

byte segCode[6][7] = { /*declaring an array of the number  from 0 to 9 in the order from a of g*/
  //a  b  c  d  e  f  g
  
  { 0, 0, 0, 0, 0, 0, 1},  // for displaying 0
  { 1, 0, 0, 1, 1, 1, 1},  // for displaying 1
  { 0, 0, 1, 0, 0, 1, 0},  // for displaying 2
  { 0, 0, 0, 0, 1, 1, 0},  // for displaying 3
  { 1, 0, 0, 1, 1, 0, 0},  // for displaying 4
  { 1, 1, 1, 1, 1, 1, 1},   // for displaying off
};
void displayDigit(int digit) /*creating a function for initializing the each segment of the display*/
{
  for (int a=0; a < 7; a++)
  {
    digitalWrite(segPins[a], segCode[digit][a]);/* instructing the respective segments for the numbers from 0 to 9 */
  }
}


void setup()
{
  Serial.begin(9600);
  delay(200);

  attachInterrupt(digitalPinToInterrupt(pins[0]), button0_ISR, RISING);
  attachInterrupt(digitalPinToInterrupt(pins[1]), button1_ISR, RISING);
  attachInterrupt(digitalPinToInterrupt(pins[2]), button2_ISR, RISING);
  attachInterrupt(digitalPinToInterrupt(pins[3]), button3_ISR, RISING);
  attachInterrupt(digitalPinToInterrupt(pins[4]), button4_ISR, RISING);
 


 for (int a=0; a < 7; a++) // assigning the OUTPUT mode to all the 7 seven-segments*/
  {
    pinMode(segPins[a], OUTPUT);
  }

  myservo.attach(servopin);

  stepper.setMaxSpeed(1000);
  stepper.setAcceleration(100);
}

void loop()
{
showdigit();

 switch (state){
  case 0:
    empty();
    break;

  case 1:
    newtarget();
  break;
  
  case 2:
   steppermove();
   break;
 
  case 3:
   delay(100);
    door();
    delay(100);
    state=4;
    break;

  case 4:
   buffer.RemoveFirst();
   state=0;
    break;
 }
  
}


void showdigit(){

if (buffer.Count()>0){
    displayDigit(buffer.First());
  }
  else{
    displayDigit(5);
  }
}




void steppermove(){
  stepper.run();
  if (stepper.currentPosition() == FloorLevel[buffer.First()]){
          
  
        state=3;
      }
  
}

void interrupt(long pin){
  static unsigned long last_interrupt_time = 0;
  unsigned long interrupt_time = millis();
  if (interrupt_time - last_interrupt_time > 200) 
  {
    buffer.Add(pin);
    
  }
  last_interrupt_time = interrupt_time;
  
    
}


void button0_ISR(){
    interrupt(0);
    
}

void button1_ISR(){
    interrupt(1);
   
}

void button2_ISR(){
    interrupt(2);
   
}

void button3_ISR(){
    interrupt(3);
   
}


void button4_ISR(){
    interrupt(4);
    
}



void door(){
  myservo.write(90 + doorspeed);
      delay(1000);
      myservo.write(90);
      delay(1000);
      myservo.write(90 - doorspeed);
      delay(1000);
      myservo.write(90);
}


void empty(){
if (buffer.Count()>0){
  stepper.moveTo(FloorLevel[buffer.First()]);
   state=1;
}

}


void newtarget(){
  int dist;
  const int count=buffer.Count();
  for(int i = 0; i < count; i++ ){
    dist=stepper.currentPosition()-FloorLevel[buffer[i]];
    if (abs(dist) < abs(stepper.distanceToGo())){
      temp.Add(buffer[i]);
      buffer.ReplaceAt(i, buffer.First());
      buffer.ReplaceFirst(temp.ExtractFirst());
      
      
      state=0;
    }
  }
  state=2;  
   
}

Finally, I want to make an algorithm that only goes up, e.g. if the cabis is at floor 0 and there are calls at 2,3,4 it will stop at all of them, and once there is a lower input the cabin needs to reach the top floor, then back to 0 and go to those calls (it doesn't work too):

Adam Gills
#include <CircularBufferLib.h>
#include <AccelStepper.h>

#include <Servo.h>

Servo myservo;

#define dirPin 4
#define stepPin 5
#define motorInterfaceType 1

AccelStepper stepper = AccelStepper(motorInterfaceType, stepPin, dirPin);

const byte NumberOfFloors = 5;
const unsigned long FloorLevel[NumberOfFloors] = {0, 100, 200, 300, 400};
const unsigned long pins [NumberOfFloors] = {2, 3, 18, 19, 20};
const int LED[NumberOfFloors] = {40, 41, 42, 43, 44};
int segPins[] = {22, 23, 24, 25, 26, 27, 28};/*assigning pins of Arduino for the seven-segment*/

volatile int state = 0;
int doorspeed = 8;
int servopin = 14;
volatile int count;



CircularBuffer<int> higher(50);
CircularBuffer<int> lower(50);

CircularBuffer<int> temp(10);

byte segCode[6][7] = { /*declaring an array of the number  from 0 to 9 in the order from a of g*/
  //a  b  c  d  e  f  g
  
  { 0, 0, 0, 0, 0, 0, 1},  // for displaying 0
  { 1, 0, 0, 1, 1, 1, 1},  // for displaying 1
  { 0, 0, 1, 0, 0, 1, 0},  // for displaying 2
  { 0, 0, 0, 0, 1, 1, 0},  // for displaying 3
  { 1, 0, 0, 1, 1, 0, 0},  // for displaying 4
  { 1, 1, 1, 1, 1, 1, 1},   // for displaying off
};
void displayDigit(int digit) /*creating a function for initializing the each segment of the display*/
{
  for (int a=0; a < 7; a++)
  {
    digitalWrite(segPins[a], segCode[digit][a]);/* instructing the respective segments for the numbers from 0 to 9 */
  }
}

void setup()
{
  Serial.begin(9600);
  delay(200);

  attachInterrupt(digitalPinToInterrupt(pins[0]), button0_ISR, RISING);
  attachInterrupt(digitalPinToInterrupt(pins[1]), button1_ISR, RISING);
  attachInterrupt(digitalPinToInterrupt(pins[2]), button2_ISR, RISING);
  attachInterrupt(digitalPinToInterrupt(pins[3]), button3_ISR, RISING);
  attachInterrupt(digitalPinToInterrupt(pins[4]), button4_ISR, RISING);

  myservo.attach(servopin);

  stepper.setMaxSpeed(1000);
  stepper.setAcceleration(100);

 for (int a=0; a < 5; a++) // assigning the OUTPUT mode to all the 7 seven-segments*/
  {
    pinMode(LED[a], OUTPUT);
  }

  for (int a=0; a < 7; a++) // assigning the OUTPUT mode to all the 7 seven-segments*/
  {
    pinMode(segPins[a], OUTPUT);
  }

}

void loop()
{
  newtarget();
  showdigit();
  switch (state) {
    case 0:
      empty();
      break;

    case 1:
      steppertop();
      break;

    case 2:
      stepperbottom();
      
      break;

    case 3:
      steppermove();
      
      break;


    case 4:
        delay(100);
      door();
      delay(100);
      state = 5;

      break;

    case 5:
      higher.RemoveFirst();;
      state = 0;
      break;

   
  }
}

void showdigit(){
  if(higher.Count() > 0 ){
    displayDigit(higher.First());
  }
  else{
    displayDigit(5);
  }
}

void empty(){
    if (higher.Count() > 0 ) {
      stepper.moveTo(FloorLevel[higher.First()]);
      //show led display
      state = 3;
    }
    if (higher.Count() == 0 && lower.Count() > 0) {
      stepper.moveTo(FloorLevel[4]);
      state = 1;
    }

}


void steppertop() {
  stepper.run();
  if (stepper.currentPosition() == FloorLevel[4]) {
    stepper.moveTo(FloorLevel[0]);
    state = 2;
  }

}

void stepperbottom() {
  stepper.run();
  if (stepper.currentPosition() == FloorLevel[0]) {
    lowtohigh();
    stepper.moveTo(FloorLevel[higher.First()]);
    state = 3;
  }

}


void steppermove() {
  stepper.run();
  if (stepper.currentPosition() == FloorLevel[higher.First()]) {
    digitalWrite(LED[higher.First()], LOW);
    state = 4;
  }

}





void interrupt(long pin) {
  static unsigned long last_interrupt_time = 0;
  unsigned long interrupt_time = millis();
  if (interrupt_time - last_interrupt_time > 200)
  {

   if (stepper.currentPosition()>FloorLevel[pin] || state==2){
    lower.Add(pin);
   }

   else{
    higher.Add(pin);
   }
    

  }
  last_interrupt_time = interrupt_time;
   digitalWrite(LED[pin], HIGH);
     if (stepper.currentPosition() == FloorLevel[higher.First()]){
          digitalWrite(LED[higher.First()], LOW);
    }
  }



void button0_ISR() {
  interrupt(0);

}

void button1_ISR() {
  interrupt(1);

}

void button2_ISR() {
  interrupt(2);

}

void button3_ISR() {
  interrupt(3);

}


void button4_ISR() {
  interrupt(4);

}



void door() {
  myservo.write(90 + doorspeed);
  delay(1000);
  myservo.write(90);
  delay(1000);
  myservo.write(90 - doorspeed);
  delay(1000);
  myservo.write(90);
}



void newtarget(){
 int dist;
  count=higher.Count();
  for(int i = 0; i < count; i++ ){
    dist=stepper.currentPosition()-FloorLevel[higher[i]];
    if (abs(dist) < abs(stepper.distanceToGo())){
      temp.Add(higher[i]);
      higher.ReplaceAt(i, higher.First());
      higher.ReplaceFirst(temp.ExtractFirst());
      stepper.moveTo(FloorLevel[higher.First()]);
      state=3;
    }
  }
    
}

void lowtohigh(){
  count=lower.Count();
  for(int i=0; i<count; i++){
    higher.Add(lower.ExtractFirst());
    
  }
}

The ones that do not work use circularbufferLib

18

the only thing I would like to change is the newtarget() function, because it does not do its job

19

For me, before I try to develop a complicated algorithm, I put the data down in a lookup table, and often I just work with it like that... a two-dimensional lookup table can help us see some of the patterns that exist between the elevator floor and the 5 destinations.

const char floorsLUT[5][5] = {{0, 1, 2, 3, 4},
                              {-1, 0, 1, 2, 3},
                              {-2, -1, 0, 1, 2},
                              {-3, -2, -1, 0, 1},
                              {-4, -3, -2, -1, 0}
                             };
20

For the 2nd & 3rd solutions I would agree with @jfjlaros. Just use an array of booleans to record which floors have been requested. When a floor is requested, set the index for that floor to true. When the lift arrives at a floor, set the index for that floor to false.

For the 2nd solution, simultaneously search up and down the indexes until one is found that is set to true. Move the lift in that direction until a requested floor is reached.

For the 3rd solution, only change direction if there are no further floors to visit in that direction.