Go Down

Topic: yet another Set class (Read 275 times) previous topic - next topic

robtillaart

Nov 14, 2014, 08:24 pm Last Edit: Nov 18, 2014, 08:40 pm by robtillaart
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).

Code: (interface) [Select]
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.06 version
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

kowalski

@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!

robtillaart

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"
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Coding Badly

Quote
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.


robtillaart

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
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

robtillaart

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 -

Code: [Select]

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
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

robtillaart

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
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

robtillaart

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

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

robtillaart

#8
Mar 07, 2015, 09:38 pm Last Edit: Mar 07, 2015, 09:46 pm by robtillaart
uploaded 0.1.07 version to - https://github.com/RobTillaart/Arduino/tree/master/libraries/Set -

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

Code: ("output timing sketch - timing in uSec") [Select]

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...
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Go Up
 


Please enter a valid email to subscribe

Confirm your email address

We need to confirm your email address.
To complete the subscription, please click the link in the email we just sent you.

Thank you for subscribing!

Arduino
via Egeo 16
Torino, 10131
Italy