# yet another Set class

Find attached a class for (small) sets that can hold numbers from 0 to 255 or enum, char.
The class supports union, intersection and diff, and iterating through the set (front to back or reverse).

``````class set
{
public:
set();                      // create empty set
set(set &t);                // create copy set

void clr();                 // clear the set
void invert();              // flip all elements in the set
uint8_t count();            // return the #elements

void sub(uint8_t);          // remove element from set
void invert(uint8_t);       // flip element in set
bool has(uint8_t);          // element is in set

void operator = (set &t);   // assignment
void operator += (set &t);  // union
void operator -= (set &t);  // diff
void operator &= (set &t);  // intersection

bool operator == (set&);    // equal
bool operator != (set&);    // not equal
bool operator <= (set&);    // is subset

// iterating through the set
// returns value
// or -1 if not exist
int first();                // find first element
int next();                 // find next element
int prev();                 // find previous element
int last();                 // find last element

// TODO ??
// set(uint8_t*, uint8_t);      // constructor from uint8_t array
// inline uint8_t size() { return _size; };
// inline bool empty() { return count() == 0; };
// inline bool full() { return count() == _size; };

private:
uint8_t _mem[32];  // can hold 0..255
// uint8_t _cnt;
// uint8_t _size;
int _current;
};
``````

The attached zip has a (development) test sketch.

As always remarks are welcome
updated attachment to 0.1.08 version

Set 0.1.08.zip (5.38 KB)

@robtillaart

This is useful stuff. Did something very similar for Cosa last year; Cosa/BitSet.hh

This is a template class and has a somewhat different memory allocation strategy. I see that there are a few operations that could be ported from your implementation.

Cheers!

feel free to use the code for Cosa.

I had a test sketch with some code to see that all the states in a state machine were used. I wanted to make a more generic solution.

What I am wondering about is the (shorthand) notation union ==> += (adding the two sets) would it be better to |= ? ( in one OR in the other) intersection ==> &= (and in one and in the other) diff ==> -= (all in one minus the ones in the other

Maybe the next release just uses "union, intersect, diff"

What I am wondering about is the (shorthand) notation

You could use the conventions of Pascal. It has a very long history of supporting ordinal sets.

good old TP. quick google learned that TP uses

• union
• difference
• intersection

so the proposed interface should change

void operator &= (set &t); // intersection ==> void operator *= (set &t); // intersection

Still todo: setA = setB + setC operator setA = setB - setC operator setA = setB * setC operator

Bug fixing & refactoring & performance tuning & clean up resulted in a 0.1.05 version.
All earlier versions are now obsolete

• optimized <= (isSubset) operator
• optimized count()
• test sketch
``````class set
{
public:
set();                      // create empty set
set(set &t);                // create copy set

void clr();                 // clear the set
void invert();              // flip all elements in the set
uint8_t count();            // return the #elements

void sub(uint8_t);          // remove element from set
void invert(uint8_t);       // flip element in set
bool has(uint8_t);          // element is in set

set operator + (set &t);    // union
set operator - (set &t);    // diff
set operator * (set &t);    // intersection

void operator += (set &t);  // union
void operator -= (set &t);  // diff
void operator *= (set &t);  // intersection

bool operator == (set&);    // equal
bool operator != (set&);    // not equal
bool operator <= (set&);    // is subset

// iterating through the set
// returns value or -1 if not exist
int first();                // find first element
int next();                 // find next element
int prev();                 // find previous element
int last();                 // find last element

private:
uint8_t _mem[32];           // can hold 0..255
int _current;
};
``````

performance numbers (times in uSec)

``````Start set_demo : 0.1.05

TIMING TEST
clr(): 28
100x sub(): 340
100x has(): 376
100x invert(v): 336
invert(): 20
count() empty: 36
count() full: 152

a = b + c: 100
a = b - c: 92
a = b * c: 92
a += b: 36
a -= b: 40
a *= b: 36
a == b: 4
a != b: 4
a <= b: 4
``````

remarks are still welcome

0.1.06 is under test, to be posted later this week...

Improved the performance of the +, -, * operators by making the clr() in the constructor conditional. gain approx 25% for the union / intersection and diff operations.

``````a = b + c:  76    // union
a = b - c:  68    // diff
a = b * c:  68    // intersection
``````

todo: + timing for iterators, first next last prev

uploaded 0.1.06 version to - https://github.com/RobTillaart/Arduino/tree/master/libraries/Set - All earlier versions are now obsolete

• renamed set -> Set
• added flag to constructor to optimize +,-,*,

iterating over the set is slow ... needs a refactor ...

(from test sketch)

``````iteration 10 elements
first:  132
next:   80
first + next until -1 : 800
``````

uploaded 0.1.07 version to - Arduino/libraries/Set at master · RobTillaart/Arduino · GitHub -

All earlier versions are now obsolete

• substantial faster first/next/last/prev;
• small changes in allTest.ino
• added output files for version 0.1.06 and 0.1.07 (AVR 16MHZ)

Improved iterating over the set (see above ==> 5 times faster)

iteration 10 elements
first: 20
next: 16
first + next until -1 : 148
last + prev until -1 : 148

``````Start set_demo : 0.1.07

TIMING TEST
clr(): 16
100x sub(): 360
100x has(): 380
100x invert(v): 352
invert(): 20
count() empty: 20
count() full: 168

a = b + c: 52
a = b - c: 60
a = b * c: 40
a += b: 32
a -= b: 32
a *= b: 32
a == b: 4
a != b: 4
a <= b: 4

iteration 10 elements
first: 20
next: 16
first + next until -1 : 148
last + prev until -1 : 148

EQUAL TEST
true
false
true
true
1
equal
true
1
false
0

INTERSECTION TEST
110
116
51

union test
110
116
175

diff test
110
116
59

INTERSECTION2 TEST
110
116
51

union2 test
110
116
175

diff2 test
110
116
59

SUBSET TEST
5
5
subset
subset
subset
no subset
no subset
no subset

ITERATE OVER SET TEST
10
42 67 77 130 167 200 216 217 241 254
254 241 217 216 200 167 130 77 67 42
done...
``````

uploaded 0.1.08 version to - Arduino/libraries/Set at master · RobTillaart/Arduino · GitHub -

• improved the clr() by using memset() - slightly faster
``````Start set_demo : 0.1.08

TIMING TEST
clr():	12
100x sub():	348
100x has():	368
100x invert(v):	348
invert():	20
count() empty:	20
count() full:	164

a = b + c:	48
a = b - c:	44
a = b * c:	52
a += b:	28
a -= b:	40
a *= b:	40
a == b:	4
a != b:	4
a <= b:	4

iteration 10 elements
first:	16
next:	16
first + next until -1 :	148
last + prev until -1 :	148

EQUAL TEST
true
false
true
true
1
equal
true
1
false
0

INTERSECTION TEST
110
116
51

union test
110
116
175

diff test
110
116
59

INTERSECTION2 TEST
110
116
51

union2 test
110
116
175

diff2 test
110
116
59

SUBSET TEST
5
5
subset
subset
subset
no subset
no subset
no subset

ITERATE OVER SET TEST
10
42	67	77	130	167	200	216	217	241	254
254	241	217	216	200	167	130	77	67	42
done...
``````

uploaded 0.1.10 version to - Arduino/libraries/Set at master · RobTillaart/Arduino · GitHub -

serious performance refactor (add, sub, has, invert function)

``````Start set_demo : 0.1.10

TIMING TEST
100x clr():	1204
100x sub():	188
100x has():	200
100x invert(v):	184
invert():	16
count() empty:	20
count() full:	164

isEmpty():	20

a = b + c:	64
a = b - c:	56
a = b * c:	64
a += b:	20
a -= b:	24
a *= b:	32
a == b:	4
a != b:	4
a <= b:	4

iteration 10 elements
first:	12
next:	16
first + next until -1 :	148
last + prev until -1 :	144

EQUAL TEST
true
false
true
true
1
equal
true
1
false
0

INTERSECTION TEST
110
116
51

union test
110
116
175

diff test
110
116
59

INTERSECTION2 TEST
110
116
51

union2 test
110
116
175

diff2 test
110
116
59

SUBSET TEST
5
5
subset
subset
subset
no subset
no subset
no subset

ITERATE OVER SET TEST
10
42	67	77	130	167	200	216	217	241	254
254	241	217	216	200	167	130	77	67	42
done...
``````

should do more tests 100x to get less noise in some numbers.

update; 0.1.11 uploaded to fix a bug in count when set is full. + added isFull()