"Walter" <walter@digitalmars.com> wrote in news:c3jo7a$q25$1@digitaldaemon.com:

> Anyone want to throw out ideas on collection types that would be cool in DTL?

Priority Queue

"Matthew" <matthew@stlsoft.org> wrote in message news:c3jq8m$t2q$2@digitaldaemon.com...
> More:
>
> int [] array_of_ints;
> int [<<] queue_of_ints;    // The chevron denotes that things go in one
> direction
> int[<>] stack_of_ints;       //  the <> denotes in one way, out the other.
I
> also thought of [|<], and [|<>]
> int<-> slist_of_ints;        // Singly-linked list
> int<<->> dlist_of_ints;    // Doubly-linked list
>
> I confess that I'm only really enamoured of the queue one. Better suggestions would be good for the other types, if they did indeed get into the language, rather than stay in libraries (as I think they should).

Should we invent new tokens for these unless there are generally accepted symbols for them?

"Walter" <walter@digitalmars.com> wrote in message news:c3kmnl$2afo$2@digitaldaemon.com...
>
> "Matthew" <matthew@stlsoft.org> wrote in message news:c3jq8m$t2q$2@digitaldaemon.com...
> > More:
> >
> > int [] array_of_ints;
> > int [<<] queue_of_ints;    // The chevron denotes that things go in one
> > direction
> > int[<>] stack_of_ints;       //  the <> denotes in one way, out the
other.
> I
> > also thought of [|<], and [|<>]
> > int<-> slist_of_ints;        // Singly-linked list
> > int<<->> dlist_of_ints;    // Doubly-linked list
> >
> > I confess that I'm only really enamoured of the queue one. Better suggestions would be good for the other types, if they did indeed get
into
> > the language, rather than stay in libraries (as I think they should).
>
> Should we invent new tokens for these unless there are generally accepted symbols for them?

Sorry, mate. I think I'm suffering NG overload (and I'm sure the rest of you are, of me!). I don't understand the question

In article <c3jo7a$q25$1@digitaldaemon.com>, Walter says...
>Anyone want to throw out ideas on collection types that would be cool in DTL?

I did some work on one point on a templated set of Tree classes.  The classes themselves provided most of the common trees, but it was also meant to be extensible with new tree types.  It went something like this:

Node(T) - holds an array of other Node(T)'s.  Used to implement webs where all
objects are peers

HierNode(T):Node(T) - holds two arrays of Node(T)'s, one parents array and one
children array.

TreeNode(T):HierNode(T) - a HierNode(T) with the parent array enforced to hold
only one Node(T).

BinaryTreeNode(T):TreeNode(T) - a TreeNode(T) with only two elements in the
children array.  Could be subclassed to make self-balancing trees, etc.

By polymorphism it would be possible to create some very complicated and yet potentially very useful structures out of them, and the layers of abstraction would make it pretty easy to add more specific functionalities (self-balancing, ternary trees, etc.)

Just my idea thought.

Owen Anderson

I'm not sure I'm at a point where I can digest all that <g>, but please do keep it all in mind, and in a few days take a look at DTL and let us know if there's some congruence. Hopefully we can slide in all these good ideas.

<resistor@mac.com> wrote in message news:c3kmue$2aqg$1@digitaldaemon.com...
> In article <c3jo7a$q25$1@digitaldaemon.com>, Walter says...
> >Anyone want to throw out ideas on collection types that would be cool in DTL?
>
> I did some work on one point on a templated set of Tree classes.  The
classes
> themselves provided most of the common trees, but it was also meant to be extensible with new tree types.  It went something like this:
>
> Node(T) - holds an array of other Node(T)'s.  Used to implement webs where
all
> objects are peers
>
> HierNode(T):Node(T) - holds two arrays of Node(T)'s, one parents array and
one
> children array.
>
> TreeNode(T):HierNode(T) - a HierNode(T) with the parent array enforced to
hold
> only one Node(T).
>
> BinaryTreeNode(T):TreeNode(T) - a TreeNode(T) with only two elements in
the
> children array.  Could be subclassed to make self-balancing trees, etc.
>
> By polymorphism it would be possible to create some very complicated and
yet
> potentially very useful structures out of them, and the layers of
abstraction
> would make it pretty easy to add more specific functionalities
(self-balancing,
> ternary trees, etc.)
>
> Just my idea thought.
>
> Owen Anderson
>
>

It's basically just a way of having templated tree classes, but leaving the hierarchy open enough that it would be feasible to add new tree variants with the absolute minimum of effort.  I'm a big supporter of class hierarchies so the functionality can be divided into clear levels.  In my imaginary tree hierarchy, it might go something like this:

Container -> Node -> HierNode -> TreeNode -> BinaryTreeNode -> RedBlackTreeNode

Each class implements as little as possible, but by the time you reach something as far down the chain as RedBlackTreeNode you've got significantly useful stuff. Also, like I said, having lots of layers makes it easier for someone writing a custom class to find exactly the right thing to inherit from without having to inherit unwanted functionality.

Owen

In article <c3kn3d$2b2u$1@digitaldaemon.com>, Matthew says...
>
>I'm not sure I'm at a point where I can digest all that <g>, but please do keep it all in mind, and in a few days take a look at DTL and let us know if there's some congruence. Hopefully we can slide in all these good ideas.
>
><resistor@mac.com> wrote in message news:c3kmue$2aqg$1@digitaldaemon.com...
>> In article <c3jo7a$q25$1@digitaldaemon.com>, Walter says...
>> >Anyone want to throw out ideas on collection types that would be cool in DTL?
>>
>> I did some work on one point on a templated set of Tree classes.  The
>classes
>> themselves provided most of the common trees, but it was also meant to be extensible with new tree types.  It went something like this:
>>
>> Node(T) - holds an array of other Node(T)'s.  Used to implement webs where
>all
>> objects are peers
>>
>> HierNode(T):Node(T) - holds two arrays of Node(T)'s, one parents array and
>one
>> children array.
>>
>> TreeNode(T):HierNode(T) - a HierNode(T) with the parent array enforced to
>hold
>> only one Node(T).
>>
>> BinaryTreeNode(T):TreeNode(T) - a TreeNode(T) with only two elements in
>the
>> children array.  Could be subclassed to make self-balancing trees, etc.
>>
>> By polymorphism it would be possible to create some very complicated and
>yet
>> potentially very useful structures out of them, and the layers of
>abstraction
>> would make it pretty easy to add more specific functionalities
>(self-balancing,
>> ternary trees, etc.)
>>
>> Just my idea thought.
>>
>> Owen Anderson
>>
>>
>
>

Matthew wrote:

> More:
> 
> int [] array_of_ints;
> int [<<] queue_of_ints;    // The chevron denotes that things go in one
> direction
> int[<>] stack_of_ints;       //  the <> denotes in one way, out the other.
> I also thought of [|<], and [|<>]
> int<-> slist_of_ints;        // Singly-linked list
> int<<->> dlist_of_ints;    // Doubly-linked list
> 
> I confess that I'm only really enamoured of the queue one. Better suggestions would be good for the other types, if they did indeed get into the language, rather than stay in libraries (as I think they should).

These are pretty nifty looking ideas.  I hope they can be implemented is some form in the future.

Matthew wrote:
>>>Anyone want to throw out ideas on collection types that would be cool in
>>>DTL?
>>
>>Deque.
> 
> Already covered in List, since it has push_front/back, front/back,
> pop_front/back

I'd like deque implemented with linked arrays, like C++ std::dequeue<>. It has significantly faster performance than a list for random access and than an array for insertion/removal. Less importantly, they are more compact than lists.

Chris.

Walter wrote:
> Anyone want to throw out ideas on collection types that would be cool in
> DTL?

I just measured my usage of the C++ containers in some recent projects...

35% vector
27% list
15% map
14% set
 6% multimap

Interestingly, the more recent projects use vector<> & list<> less and set<> & multimap<> more. I guess this comes from realising that more things are associative then a crusty old C programmer is at first prepared to admit.

I'd like tree *and* hash implementations of the associative containers. It is annoying that C++ doesn't yet provide any hash containers (outside boost) and that other languages use them for everything. Choice please!

Call a spade a spade, please. multimap<> should be treemap<> (though redblacktreemap<> is going too far). The worst is multiset<>, which should be called bag<> (or treebag<> & hashbag<>). My pet gripe is that D "associative arrays" are called arrays at all. They are hashmaps, not arrays, right?

Chris.

Chris Paulson-Ellis wrote:

>
> I'd like tree *and* hash implementations of the associative containers. It is annoying that C++ doesn't yet provide any hash containers (outside boost) and that other languages use them for everything. Choice please!
>
Hu? I assume your talking about stl. What about hash_map?

> Chris.


-- 
-Anderson: http://badmama.com.au/~anderson/