Go Down

Topic: yet another Set class (Read 110 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)

Go Up