On 05/24/2010 04:08 PM, Steven Schveighoffer wrote:
> On Mon, 24 May 2010 16:27:46 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> wrote:
>
>> Sorry. Yes, by-key iteration should be possible.
>
> OK, so we should be able to iterate keys. And the keys are not stored in
> the trie structure itself. So how does one iterate the keys of the
> container without reconstructing them from the trie nodes using the
> heap?

You can't. At some point you need to copy tree traces into T[] arrays. If the trie stores parent nodes, you don't need to do that as you can expose a trace as a double-ended range containing the key.

There's a kind of trie that was defined to avoid such issues; it stores the keys in clear, in the leaves, at the expense of duplication. I don't remember the name offhand. Does anyone?


Andrei

On Mon, 24 May 2010 17:35:11 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> On 05/24/2010 04:08 PM, Steven Schveighoffer wrote:
>> On Mon, 24 May 2010 16:27:46 -0400, Andrei Alexandrescu
>> <SeeWebsiteForEmail@erdani.org> wrote:
>>
>>> Sorry. Yes, by-key iteration should be possible.
>>
>> OK, so we should be able to iterate keys. And the keys are not stored in
>> the trie structure itself. So how does one iterate the keys of the
>> container without reconstructing them from the trie nodes using the
>> heap?
>
> You can't. At some point you need to copy tree traces into T[] arrays. If the trie stores parent nodes, you don't need to do that as you can expose a trace as a double-ended range containing the key.
>
> There's a kind of trie that was defined to avoid such issues; it stores the keys in clear, in the leaves, at the expense of duplication. I don't remember the name offhand. Does anyone?

OK, so the keys function of Map should work just fine for a Trie implementation.  Good to know.

-Steve

On 05/24/2010 04:38 PM, Steven Schveighoffer wrote:
> On Mon, 24 May 2010 17:35:11 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> wrote:
>
>> On 05/24/2010 04:08 PM, Steven Schveighoffer wrote:
>>> On Mon, 24 May 2010 16:27:46 -0400, Andrei Alexandrescu
>>> <SeeWebsiteForEmail@erdani.org> wrote:
>>>
>>>> Sorry. Yes, by-key iteration should be possible.
>>>
>>> OK, so we should be able to iterate keys. And the keys are not stored in
>>> the trie structure itself. So how does one iterate the keys of the
>>> container without reconstructing them from the trie nodes using the
>>> heap?
>>
>> You can't. At some point you need to copy tree traces into T[] arrays.
>> If the trie stores parent nodes, you don't need to do that as you can
>> expose a trace as a double-ended range containing the key.
>>
>> There's a kind of trie that was defined to avoid such issues; it
>> stores the keys in clear, in the leaves, at the expense of
>> duplication. I don't remember the name offhand. Does anyone?
>
> OK, so the keys function of Map should work just fine for a Trie
> implementation. Good to know.

This wins a little battle but not the war. Long term you're facing the sysyphic job of either knocking new containers into the existing interfaces, or extending the interfaces to accommodate new containers. It doesn't look to me like a winning proposition.

The FIC (Federation of Independent Containers) does not have that problem. It does have its specifications and guidelines but whichever container doesn't support some or even all of the required methods can simply define its own under other names. Then users can play with the containers and with the ranges they define as they find fit.


Andrei

On Mon, 24 May 2010 17:47:18 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> On 05/24/2010 04:38 PM, Steven Schveighoffer wrote:
>> On Mon, 24 May 2010 17:35:11 -0400, Andrei Alexandrescu
>> <SeeWebsiteForEmail@erdani.org> wrote:
>>
>>> On 05/24/2010 04:08 PM, Steven Schveighoffer wrote:
>>>> On Mon, 24 May 2010 16:27:46 -0400, Andrei Alexandrescu
>>>> <SeeWebsiteForEmail@erdani.org> wrote:
>>>>
>>>>> Sorry. Yes, by-key iteration should be possible.
>>>>
>>>> OK, so we should be able to iterate keys. And the keys are not stored in
>>>> the trie structure itself. So how does one iterate the keys of the
>>>> container without reconstructing them from the trie nodes using the
>>>> heap?
>>>
>>> You can't. At some point you need to copy tree traces into T[] arrays.
>>> If the trie stores parent nodes, you don't need to do that as you can
>>> expose a trace as a double-ended range containing the key.
>>>
>>> There's a kind of trie that was defined to avoid such issues; it
>>> stores the keys in clear, in the leaves, at the expense of
>>> duplication. I don't remember the name offhand. Does anyone?
>>
>> OK, so the keys function of Map should work just fine for a Trie
>> implementation. Good to know.
>
> This wins a little battle but not the war. Long term you're facing the sysyphic job of either knocking new containers into the existing interfaces, or extending the interfaces to accommodate new containers. It doesn't look to me like a winning proposition.

It's always easy to say that there may come a day when the interfaces don't work -- none of us can see the future.  When that day comes, we can find a solution to it.  The worst case scenario is that you simply don't implement any interfaces.  It does not detract from the interfaces that exist.  It would seem odd that some of the collections do not implement the interfaces while others do.  At the very least though, all containers should be iterable, meaning they will implement the Iterator!V interface.  That at least allows it to interact with the other container types.

On the flip side, if containers did not implement interfaces, having to do this:

class WrappedSet!(alias Impl, V) : Set!V
{
   private Impl!V impl;
   int functionToSatisfySet() { return impl.functionToSatisfySet(); }
   ...
}

seems to me like a lot more crufty and bloated than simply adding : Set!V on the end of the class declarations.

But I'm willing to drop the interfaces for now since interfaces obviously are an unpopular choice.

-Steve

Steven Schveighoffer <schveiguy@yahoo.com> wrote:
> On the flip side, if containers did not implement interfaces, having to do this:
>
> class WrappedSet!(alias Impl, V) : Set!V
> {
>     private Impl!V impl;
>     int functionToSatisfySet() { return impl.functionToSatisfySet(); }
>     ...
> }
>
> seems to me like a lot more crufty and bloated than simply adding : Set!V on the end of the class declarations.

This would not be necessary. We can get the function names off of the
interface, so we could have a template do this for us.

-- 
Simen

On Mon, 24 May 2010 11:01:06 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
> It's done all the time in Java and .NET.  For example, A GUI listbox widget exposes its elements as an array of elements, which implement the List interface.  You don't ever see the implementation or need it. Granted Java and .NET have less problems than C++ and D with binary compatibility, since the function tables are dynamic, but the potential is there for D to make binary compatibility possible with interfaces.
> 

Cocoa (NeXT's/Apple's framework for Objective-C) uses a very successful and well-thought-out delegation pattern, whereby GUI elements representing large amounts of data, like table views, have delegates (not in the D sense of the word) that provide them with the actual contents. Granted, Objective-C's runtime is much more dynamic than D, but a simplified version of such a pattern could still work in D. After all, user interfacing is typically where dynamism is more important than speed.

On 24/05/2010 16:45, Andrei Alexandrescu wrote:
>> In the past I have built a C++ library that abstracted features of
>> the OS. My goal was to make it possible to dynamically load a module
>> that abstracted things like setting the IP address of a network
>> interface. My modules used std::string instead of char * to lookup
>> services to get objects that implement the interface. Big mistake. On
>> a later version of the standard C++ runtime, the private
>> implementation of std::string changed, so the dynamically loaded
>> libraries crashed horribly. No change in string's interface, just the
>> private stuff changed, but because it's a template, the code that
>> uses it necessarily has to be aware of it. We ended up ditching the
>> standard C++ library's version of string, and used STLPort so we
>> could control the library.
>>
>> I envision this same sort of problem would be likely with D
>> collection objects that were not used via interfaces.
>
> I see no problem retrofitting a no-interface container into a formal
> interface if so needed.


I don't understand this discussion: isn't the reason above pretty much a dead-on hard requirement for the collections to have interfaces?
Something like, for example, an interface version of the range traits?

-- 
Bruno Medeiros - Software Engineer

On Wed, 26 May 2010 10:06:32 -0400, Bruno Medeiros <brunodomedeiros+spam@com.gmail> wrote:

> On 24/05/2010 16:45, Andrei Alexandrescu wrote:
>>> In the past I have built a C++ library that abstracted features of
>>> the OS. My goal was to make it possible to dynamically load a module
>>> that abstracted things like setting the IP address of a network
>>> interface. My modules used std::string instead of char * to lookup
>>> services to get objects that implement the interface. Big mistake. On
>>> a later version of the standard C++ runtime, the private
>>> implementation of std::string changed, so the dynamically loaded
>>> libraries crashed horribly. No change in string's interface, just the
>>> private stuff changed, but because it's a template, the code that
>>> uses it necessarily has to be aware of it. We ended up ditching the
>>> standard C++ library's version of string, and used STLPort so we
>>> could control the library.
>>>
>>> I envision this same sort of problem would be likely with D
>>> collection objects that were not used via interfaces.
>>
>> I see no problem retrofitting a no-interface container into a formal
>> interface if so needed.
>
>
> I don't understand this discussion: isn't the reason above pretty much a dead-on hard requirement for the collections to have interfaces?
> Something like, for example, an interface version of the range traits?

Only if you wish to have binary compatibility with dynamic libs.  Such a thing isn't likely today since dynamic libs aren't very well supported in D, and even phobos or dcollections isn't a dynamic lib.

And I have specifically decided not to use interfaces with ranges because that makes them reference types.  Ranges work well as value types, but not well as reference types.  Therefore, to use dcollections as interfaces, you must not require the range traits.

-Steve

On Wed, 19 May 2010 17:18:04 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:

> Andrej Mitrovic Wrote:
>
>
>> Well as long as you're here can I submit an error here? :)
>>
>> I get an error while building the D2 branch:
>>
>> Error: ArrayMultiset.obj : No such file or directory
>
> Crud, I admit that I assumed anything that built on Linux would build on Windows.  I still believe it will, but of course, I need to change the batch file :)
>
>>
>> It seems the ArrayMultiset.d is not in the dcollections folder for the D2.x  branch, although it is in trunk (I guess the trunk is the D1.x one?).
>
> Yes, D1 is trunk, D2 is going to eventually be trunk
>
>>
>> Is that module deprecated for d2.x? (although it's listed in the win32 batch file)
>
> Yes, just remove it.  I'll fix it when I get a chance.

I've fixed the windows build files and recreated the zip/tarball files for 2.0a.  Learned some batch-fu online and hopefully the new versions will be future-proof.

Please re-download the zipfile to build with windows.

Thanks

-Steve

On 2010-05-27 12:32, Steven Schveighoffer wrote:
> On Wed, 26 May 2010 10:06:32 -0400, Bruno Medeiros
> <brunodomedeiros+spam@com.gmail> wrote:
>
>> On 24/05/2010 16:45, Andrei Alexandrescu wrote:
>>>> In the past I have built a C++ library that abstracted features of
>>>> the OS. My goal was to make it possible to dynamically load a module
>>>> that abstracted things like setting the IP address of a network
>>>> interface. My modules used std::string instead of char * to lookup
>>>> services to get objects that implement the interface. Big mistake. On
>>>> a later version of the standard C++ runtime, the private
>>>> implementation of std::string changed, so the dynamically loaded
>>>> libraries crashed horribly. No change in string's interface, just the
>>>> private stuff changed, but because it's a template, the code that
>>>> uses it necessarily has to be aware of it. We ended up ditching the
>>>> standard C++ library's version of string, and used STLPort so we
>>>> could control the library.
>>>>
>>>> I envision this same sort of problem would be likely with D
>>>> collection objects that were not used via interfaces.
>>>
>>> I see no problem retrofitting a no-interface container into a formal
>>> interface if so needed.
>>
>>
>> I don't understand this discussion: isn't the reason above pretty much
>> a dead-on hard requirement for the collections to have interfaces?
>> Something like, for example, an interface version of the range traits?
>
> Only if you wish to have binary compatibility with dynamic libs. Such a
> thing isn't likely today since dynamic libs aren't very well supported
> in D, and even phobos or dcollections isn't a dynamic lib.

I've got my patch, for build Tango as a dynamic library on Mac, quite recently included in trunk. And I've also have a patch for druntime and Phobos in bugzilla just waiting to be included + one patch making it easier creating dynamic libraries directly with DMD. I would say it's a bad idea to still think that dynamic libraries aren't support, we have to think forward and assume they will be supported.

> And I have specifically decided not to use interfaces with ranges
> because that makes them reference types. Ranges work well as value
> types, but not well as reference types. Therefore, to use dcollections
> as interfaces, you must not require the range traits.
>
> -Steve


-- 
/Jacob Carlborg