On Mon, 27 Dec 2010 05:22:14 -0200
Guilherme Vieira <n2.nitrogen@gmail.com> wrote:

> Right now I'm wondering how's the best way to create a dynamic array object which will only accept "unique" elements (i.e., elements != from the existing elements in the array).

(Take my words with precaution because I don not know D very well myself.)

Hello Guilherme. If I understand your purpose correctly, what you're trying to define is a set, not an array, in the common sense of the terms in programming. To ensure uniqueness, you'd need to check whether the element exits already, which can only be very slow using an array (O(n)): you need to traverse the array element per element. Sets instead are build using data structures that allow this check to be far faster, by looking up a given element in a more clever way.

There is no builtin Set type in D yet. The simplest way (and maybe the best) would be use associative arrays where keys would be actual elements and values just fake. (e in set) would tell you what you need. Depending on your requirements, trying to put an existing element would just put it again with no change, or should throw an error. In the latter case, you need to check it yourself or build a wrapper type (struct or class) around builtin associative arrays.

For instance:
    Existence[Element] set;
    Element[] elements = ['a','c','e'];
    Element[] values = ['a','b','c','d','e'];
    foreach (element ; elements)
        set[element] = EXISTS;
    // Note: 'in' actually return a pointer to element.
    foreach (value ; values)
        writeln(cast(bool)(value in set));

Note: I have a Set type in stock at https://bitbucket.org/denispir/denispir-d/src/b543fb352803/collections.d, but wonder whether it's really necessary given the above. But you can have a look to see how it's done (this would give you some hints about "language methods" called 'opSomething', see TDPL's index).


Denis
-- -- -- -- -- -- --
vit esse estrany ☣

spir.wikidot.com

Ah, yeah. I think you're right. Set is exactly what I need, and the fact that it works with hashes is even better. A pity D still doesn't have it, since it looks very useful, but thanks for your response. I'll take a look at your implementation later.

Is there any prevision for sets in core D or Phobos?

-- 
Atenciosamente / Sincerely,
Guilherme ("n2liquid") Vieira


On Mon, Dec 27, 2010 at 11:39 AM, spir <denis.spir@gmail.com> wrote:

> On Mon, 27 Dec 2010 05:22:14 -0200
> Guilherme Vieira <n2.nitrogen@gmail.com> wrote:
>
> > Right now I'm wondering how's the best way to create a dynamic array
> object
> > which will only accept "unique" elements (i.e., elements != from the
> > existing elements in the array).
>
> (Take my words with precaution because I don not know D very well myself.)
>
> Hello Guilherme. If I understand your purpose correctly, what you're trying to define is a set, not an array, in the common sense of the terms in programming. To ensure uniqueness, you'd need to check whether the element exits already, which can only be very slow using an array (O(n)): you need to traverse the array element per element. Sets instead are build using data structures that allow this check to be far faster, by looking up a given element in a more clever way.
>
> There is no builtin Set type in D yet. The simplest way (and maybe the best) would be use associative arrays where keys would be actual elements and values just fake. (e in set) would tell you what you need. Depending on your requirements, trying to put an existing element would just put it again with no change, or should throw an error. In the latter case, you need to check it yourself or build a wrapper type (struct or class) around builtin associative arrays.
>
> For instance:
>    Existence[Element] set;
>    Element[] elements = ['a','c','e'];
>    Element[] values = ['a','b','c','d','e'];
>    foreach (element ; elements)
>        set[element] = EXISTS;
>    // Note: 'in' actually return a pointer to element.
>    foreach (value ; values)
>        writeln(cast(bool)(value in set));
>
> Note: I have a Set type in stock at https://bitbucket.org/denispir/denispir-d/src/b543fb352803/collections.d, but wonder whether it's really necessary given the above. But you can have a look to see how it's done (this would give you some hints about "language methods" called 'opSomething', see TDPL's index).
>
>
> Denis
> -- -- -- -- -- -- --
> vit esse estrany ☣
>
> spir.wikidot.com
>
>

On Mon, Dec 27, 2010 at 12:14 PM, Guilherme Vieira <n2.nitrogen@gmail.com>wrote:

> Ah, yeah. I think you're right. Set is exactly what I need, and the fact that it works with hashes is even better. A pity D still doesn't have it, since it looks very useful, but thanks for your response. I'll take a look at your implementation later.
>
> Is there any prevision for sets in core D or Phobos?
>
> --
>
> Atenciosamente / Sincerely,
> Guilherme ("n2liquid") Vieira
>
>
> On Mon, Dec 27, 2010 at 11:39 AM, spir <denis.spir@gmail.com> wrote:
>
>> On Mon, 27 Dec 2010 05:22:14 -0200
>> Guilherme Vieira <n2.nitrogen@gmail.com> wrote:
>>
>> > Right now I'm wondering how's the best way to create a dynamic array
>> object
>> > which will only accept "unique" elements (i.e., elements != from the
>> > existing elements in the array).
>>
>> (Take my words with precaution because I don not know D very well myself.)
>>
>> Hello Guilherme. If I understand your purpose correctly, what you're
>> trying to define is a set, not an array, in the common sense of the terms in
>> programming. To ensure uniqueness, you'd need to check whether the element
>> exits already, which can only be very slow using an array (O(n)): you need
>> to traverse the array element per element. Sets instead are build using data
>> structures that allow this check to be far faster, by looking up a given
>> element in a more clever way.
>>
>> There is no builtin Set type in D yet. The simplest way (and maybe the best) would be use associative arrays where keys would be actual elements and values just fake. (e in set) would tell you what you need. Depending on your requirements, trying to put an existing element would just put it again with no change, or should throw an error. In the latter case, you need to check it yourself or build a wrapper type (struct or class) around builtin associative arrays.
>>
>> For instance:
>>    Existence[Element] set;
>>    Element[] elements = ['a','c','e'];
>>    Element[] values = ['a','b','c','d','e'];
>>    foreach (element ; elements)
>>        set[element] = EXISTS;
>>    // Note: 'in' actually return a pointer to element.
>>    foreach (value ; values)
>>        writeln(cast(bool)(value in set));
>>
>> Note: I have a Set type in stock at https://bitbucket.org/denispir/denispir-d/src/b543fb352803/collections.d, but wonder whether it's really necessary given the above. But you can have a look to see how it's done (this would give you some hints about "language methods" called 'opSomething', see TDPL's index).
>>
>>
>> Denis
>> -- -- -- -- -- -- --
>> vit esse estrany ☣
>>
>> spir.wikidot.com
>>
>>
Eek..! sorry for top-posting.

-- 
Atenciosamente / Sincerely,
Guilherme ("n2liquid") Vieira

On 12/27/10 3:14 PM, Guilherme Vieira wrote:
> Ah, yeah. I think you're right. Set is exactly what I need, and the fact
> that it works with hashes is even better. A pity D still doesn't have
> it, since it looks very useful, but thanks for your response. I'll take
> a look at your implementation later.
>
> Is there any prevision for sets in core D or Phobos?

I don't know about the Phobos part, but for your D1/D2 collection needs, DCollections (http://www.dsource.org/projects/dcollections) might be worth a look.

David