Proposal for a set handling library

[Raphaël Jakse]

Le 02/01/2014 16:00, Dejan Lekic a écrit :
> 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? :)

My ignorance. Fixed, thanks ;-)