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 add(uint8_t);          // add element to the set
    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

  • added +,-,* operators
  • optimized <= (isSubset) operator
  • optimized count()
  • test sketch

Code - https://github.com/RobTillaart/Arduino/tree/master/libraries/set -

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 add(uint8_t);          // add element to the set
    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 add(): 348
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 add(): 360
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
  • added some comments
Start set_demo : 0.1.08

TIMING TEST
clr():	12
100x add():	352
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)
added faster isEmpty() function.

Start set_demo : 0.1.10

TIMING TEST
100x clr():	1204
100x add():	244
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()