Proposal for a set handling library

[Dejan Lekic]

On Thursday, 2 January 2014 at 00:22:14 UTC, Raphaël Jakse wrote:
> 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.

Is there any reason not to use Phobos Tuple? :)