Queue system in arduino?

Hey Guys! i am trying to make a queue system, though i am having a hard time figuring it out, as i am not very skilled with arduino.

i want a system where every line i send to my arduino is put into a list, and if the line sent, already exists, it has to be removed.

like this:

  1. i send “Hubert” to the arduino
  2. the arduino puts “Hubert” into the list
  3. i send “Bob” to the arduino
  4. the arduino puts “Bob” in the list, under Hubert like below:

Hubert
Bob

  1. i send “Hubert” to the arduino
  2. the arduino notices that “Hubert” is already on the list, and then removes it, so that only “Bob” is left on the list.

How do i do this? i know how to send to the arduino, but i need to make the list.
Please help.

Thanks in advance :slight_smile:

Start reading the tutorial section about array's . There are a lot of code examples that solve part of your problem.

Don't think of the problem as a need to remove "Hubert" but as a need to mark as empty the space where Hubert is. (That's what happens on your hard disk when you delete a file, and it's why the cops can recover the evidence of your past misdeeds :)

Also, bear in mind that the Arduino has very little memory. If you can pre-allocate the space for all your names it will make the programming easier, but that means allocating the same space for all names.

If you were programming on a PC you would probably use Strings (upper case S) for storing the names but Strings cause memory problems on an Arduino and are best avoided.

Having variable length names without using Strings will make for a much more complex program.

...R

Robin2: Don't think of the problem as a need to remove "Hubert" but as a need to mark as empty the space where Hubert is. (That's what happens on your hard disk when you delete a file, and it's why the cops can recover the evidence of your past misdeeds :)

Also, bear in mind that the Arduino has very little memory. If you can pre-allocate the space for all your names it will make the programming easier, but that means allocating the same space for all names.

If you were programming on a PC you would probably use Strings (upper case S) for storing the names but Strings cause memory problems on an Arduino and are best avoided.

Having variable length names without using Strings will make for a much more complex program.

...R

SO have you got any tips for me ? I am looking at the queuelist library, but i don't really know how to set it up. :/ http://playground.arduino.cc/Code/QueueList

I would avoid using QueueList as it's likely doing to use dynamic memory allocation, and you're likely to run into issues later. Search Circular Buffer Queue; this is a combination of some fundamental programming concepts, so there should be plenty of information around it.

kasperhangard: SO have you got any tips for me ?

How many entries do you want in your list? What is the maximum length of an individual entry?

...R

Robin2:

kasperhangard: SO have you got any tips for me ?

How many entries do you want in your list? What is the maximum length of an individual entry?

...R

About 30 i think. that would be nice. :) maximum length i take as the maximum string length, yes? That would be about 17 characters :)

I would create two arrays (there are other ways, including a struct)

char nameList[30][18]; // allows 30 entries of 17 chars + a 0 terminating byte boolean listEmpty[30];

When you want to add a name to the list you go through the listEmpty[] array to find the first one marked true and use the index number of that to index into the nameList[][] array. And change the relevant listEmpty[] entry to false.

If you want to "delete" a name find the name in nameList[][] and use the index number to index into listEmpty[] and mark it false.

Hope that makes sense.

...R

I don't know whether I'd call this a "Queue", since that usually implies some specific ordering of insertion and extraction. More like a "symbol table." Robin2's strategy seems reasonable, although I don't see the need for a separate listEmpty array, since it's "no problem" to put null strings in the actual data array.

I think you are actually wanting a set, not a queue. One normally would use a hash table for a set, but given how very little RAM there is a managed list (in an array) is probably the simplest way to achieve this.

A queue has operations insert() and extract() and gives first-in first-out semantics.

A stack has operations push() and pop() and gives first-in last-out semantics.

A dequeue is a combination of stack and queue and can be inserted or extracted from either end.

A set has operations add(), remove(), is_member() - its the only data-structure in this list that has a lookup function.

So you are wanting a set and your pseudo code is something like:

if (set.is_present (tag)) set.remove (tag) else set.add (tag)

MarkT: if (set.is_present (tag)) set.remove (tag) else set.add (tag)

This right here is exactly what i need! thanks a bunch man! I will try to look into sets then.

Also thank you to everyone else, putting their time into helping me! :)

westfw: although I don't see the need for a separate listEmpty array, since it's "no problem" to put null strings in the actual data array.

I guess if you write 0 to the first element of the nameList[][] array it can be used exactly like the listEmpty[] array.

@kasperhangard, set.present() etc will need a dataset to work on. It is an adjunct to the data array, not a replacement for it.

...R

Robin2:

westfw: although I don't see the need for a separate listEmpty array, since it's "no problem" to put null strings in the actual data array.

I guess if you write 0 to the first element of the nameList[][] array it can be used exactly like the listEmpty[] array.

@kasperhangard, set.present() etc will need a dataset to work on. It is an adjunct to the data array, not a replacement for it.

...R

Oh. So how would i go about making it? I really need to be able to lookup a name.

If you use a simple array of C strings then you can do the job with less overhead.

char nameList[ 30 ][ 18 ]; // which initializes to all zeros.

The strcmp() function compares 2 strings easily and can be run inside of a loop to check each entry as needed.
To use strcmp() you must
#include <string.h>

char compareName[ 18 ]; // and somewhere this gets filled with a new entry to check in the list
byte listIndex;

listIndex = 0;
while ( listIndex < 30 )
{
if ( strcmp( nameList[ listIndex ], compareName ) == 0 )
{
nameList[ listIndex ][ 0 ] = 0; // name removed
listIndex = 100; // 100 means found and removed, 30 means not found
}
}

if ( listIndex == 30 )
{
// name not found, go back down the list to find the first empty slot and copy it there
}

GoForSmoke:
If you use a simple array of C strings then you can do the job with less overhead.

char nameList[ 30 ][ 18 ]; // which initializes to all zeros.

The strcmp() function compares 2 strings easily and can be run inside of a loop to check each entry as needed.
To use strcmp() you must
#include <string.h>

char compareName[ 18 ]; // and somewhere this gets filled with a new entry to check in the list
byte listIndex;

listIndex = 0;
while ( listIndex < 30 )
{
if ( strcmp( nameList[ listIndex ], compareName ) == 0 )
{
nameList[ listIndex ][ 0 ] = 0; // name removed
listIndex = 100; // 100 means found and removed, 30 means not found
}
}

if ( listIndex == 30 )
{
// name not found, go back down the list to find the first empty slot and copy it there
}

thanks man. i got some questions.

if ( strcmp( nameList[ listIndex ], compareName ) == 0 )
compareName, is where the next entry gets put in, it will then look for that entry in the nameList right?
the == 0 means that it found no comparison?

nameList[ listIndex ][ 0 ] = 0; // name removed
is to reset the listindex, to start over ?

how listindex get to 30 or 100?

the == 0 means that it found no comparison?

it means strcmp() found no difference.

kasperhangard:

GoForSmoke:
If you use a simple array of C strings then you can do the job with less overhead.

char nameList[ 30 ][ 18 ]; // which initializes to all zeros.

The strcmp() function compares 2 strings easily and can be run inside of a loop to check each entry as needed.
To use strcmp() you must
#include <string.h>

char compareName[ 18 ]; // and somewhere this gets filled with a new entry to check in the list
byte listIndex;

listIndex = 0;
while ( listIndex < 30 )
{
if ( strcmp( nameList[ listIndex ], compareName ) == 0 )
{
nameList[ listIndex ][ 0 ] = 0; // name removed
listIndex = 100; // 100 means found and removed, 30 means not found
}
}

if ( listIndex == 30 )
{
// name not found, go back down the list to find the first empty slot and copy it there
}

thanks man. i got some questions.

if ( strcmp( nameList[ listIndex ], compareName ) == 0 )
compareName, is where the next entry gets put in, it will then look for that entry in the nameList right?
the == 0 means that it found no comparison?

From the AVR GCC (the base of Arduino IDE) library reference, link below:

int strcmp ( const char * s1,
const char * s2
)

Compare two strings.

The strcmp() function compares the two strings s1 and s2.

Returns:
The strcmp() function returns an integer less than, equal to, or greater than zero if s1 is found, respectively, to be less than, to match, or be greater than s2. A consequence of the ordering used by strcmp() is that if s1 is an initial substring of s2, then s1 is considered to be “less than” s2.

You can use strcmp() to sort strings.
There is also strncmp() that compares only n chars. Many string.h functions have an n (number/count) version.

nameList[ listIndex ][ 0 ] = 0; // name removed
is to reset the listindex, to start over ?

A C string array is a char or byte array that may contain text as ASCII code terminated by a NULL (zero) char.
If the string starts with 0, it is an empty string, same as “”.

What makes a string and how they work is a very simple fundamental that a lot of people just skip.
But if you don’t have that then trying to make sense of the string.h functions would be hell.

how listindex get to 30 or 100?

You’re right, I didn’t put an increment in!

while ( listIndex < 30 )
{
  if ( strcmp( nameList[ listIndex ], compareName ) == 0 )
  {
    nameList[ listIndex ][ 0 ] = 0; // name removed
    listIndex = 100; // 100 means found and removed, 30 means not found
  }
  else
  {
    listIndex++;
  }
}

Here links to the AVR GCC library references, highly valuable!
http://www.nongnu.org/avr-libc/user-manual/modules.html

Here’s the string.h page:
http://www.nongnu.org/avr-libc/user-manual/group__avr__string.html

When learning to program, it is very useful - no, even necessary - to learn about data structures, such as lists, queues, stacks, maps, trees, etc. Remember that programming is almost entirely about data manipulation. You need to learn how data is structured and how you can exploit the data structures to make the program do what you want. Once you learn that, you can apply the same principles to any kind of object, whether it is a number, a string, or an instance of some class. With the help of data structures, you can juggle your data around and make your programs do pretty amazing stuff, by the use of very general principles, which are very easy to implement and re-use.

Of course, you may have to unlearn a bunch of your "data structures" class to implement this sort of thing on a tiny microcontroller. All of the examples for queues and symbol tables you're likely to find online, in classes, or in books are likely to be written in nice languages with dynamic memory allocation and well-behaved string functions. And probably "templates" as well, for C++, and something similar for Java (generics?)

Here's an example discussion: http://algs4.cs.princeton.edu/31elementary/ It shouldn't be too awful to pare down some of his example code (ArrayST.java, for example) to do what you want in the arduino C++ language... (Sedgewick is awesome! Take his online classes!)