Proposal for a set handling library

[Raphaël Jakse]

Le 01/01/2014 22:54, Cooler a écrit :
> Example in C++:
>    set<int> uniqueInts;
>    assert(uniqueInts.count(99) == 0);
>    uniqueInts.insert(99);
>    assert(uniqueInts.count(99) == 1);
>    uniqueInts.erase(99);
>    assert(uniqueInts.count(99) == 0);
>
> Which it will be analogue solution in D?
>
> I need a collection that can hold number of items, and can tell me
> weather is an item in the collection or not. I found that RedBlackTree
> can help me. But RedBlackTree uses O(log(n)) time for insert/remove
> operations. On the other hand we have built-in associative arrays with
> hashed keys. But associative arrays requires pairs of (key, value),
> which is quite wasting in my case.
> May be it will be convenient to allow void[key] built-in collections?
> Any suggestion?

Hello,

I don't know if it fits with your needs, but I just pushed a library for 
handling sets I wrote months ago.

It supports basic operations like adding, removing, testing the presence 
of an object in the set, intersection, union, powerset, difference, 
symmetric difference.

Sets can be untyped (it accepts elements of any type) or typed (more 
efficient, accepts only elements of a given type like int).

If I'm not mistaken, complexity of insertion, presence checking and 
removal is O(1).

You can get it here:

		https://gitorious.org/set/set/

Feel free to ask question, make suggestions... if you have any.

Example of code:

     import std.stdio;
     import std.conv;
     import set;

     void main() {
         auto S = new Set!();
         S.add("hello");
         S.add(42);
         writeln(S);
         writeln("has 42? ", S.contains(42));
         writeln("has \"42\"? ", S.contains("42"));
         writeln("has \"hello\"? ", S.contains("hello"));
         S.remove("hello");
         writeln(S);
         writeln("has \"hello\"? ", S.contains("hello"));
         writeln("address of 42 : ", S.addressOf(42));

         auto E = new Set!int([1,2,3,4]); // it is possible to declare 
an empty set
         auto F = new Set!int([3,4,5,6]); // of int like this: auto G = 
new Set!int;

         writeln("union: ", E.Union(F));
         writeln("inter: ", E.Inter(F));
         writeln("symmetric difference: ", E.SymDiff(F));
         writeln("minus: ", E.Minus(F));
         writeln("Powerset: ", E.Powerset);

         S.UnionInPlace(E);
         writeln("Union in place: ", S);

         // lets iterate over elements:
         foreach (element ; S) {
             write(element);

             // beware, because S is an untyped set (Set!() or Set!Object),
             // type of element is Element.
             // If you want the real value, cast to 
Element!the_type_of_your_element
             // and access to the e property of the class.

             auto el = cast(Element!int)(element);
             write(" (", el.e, ") ");

             // el.e is an int
             // Note that this works only because the only remaining 
values in S
             // are integer values. If another type were present in the 
set, we
             // would experience a segmentation fault.
         }
         writeln();
     }

Expected output:

     {hello, 42}
     has 42? true
     has "42"? false
     has "hello"? true
     {42}
     has "hello"? false
     address of 42 : 7F9323979F60
     union: {4, 1, 5, 2, 6, 3}
     inter: {4, 3}
     symmetric difference: {1, 5, 2, 6}
     minus: {1, 2}
     Powerset: {{}, {4}, {1, 3}, {4, 1, 3}, {1}, {4, 1}, {2, 3}, {4, 2, 
3}, {2}, {4, 2}, {1, 2, 3}, {4, 1, 2, 3}, {1, 2}, {4, 1, 2}, {3}, {4, 3}}
     Union in place: {4, 1, 42, 2, 3}
     4 (4) 1 (1) 42 (42) 2 (2) 3 (3)

Should Phobos have something similar built in?

Happy new year to everyone,
Raphaël.