Walter <walter@digitalmars.com> wrote in message news:9m4329$2vv4$1@digitaldaemon.com...
>
> "Russell Bornschlegel" <kaleja@estarcion.com> wrote in message news:3B83EF19.D755A19@estarcion.com...
> > The D spec is silent on the implementation details for
> > associative arrays, but they'd likely be binary trees (ordered
> > keys, lookup time normally O(log2(n))) or hashes (disordered keys,
> > lookup time normally O(1)).
>
> They're a mix of hash tables and binary trees. The implementation would be free to pick its own way of implementing them.
>
>

Have you checked up 'Suneido' language, where the common 'object' data type is accesible *both* as asso. arrays and vectors? Taking their own example, this is how you can specify the object literals:

#(1, 2, "abc", "def")
#(name: "Joe", age: 23)
#(1, "abc", name: "Joe")


In the last example, the value of element 2 is "Joe", also accesible thru
[2].
More on www.suneido.com

-- Rajiv

Russell Bornschlegel wrote:
> 
> Charles Hixson wrote:
> > > Yes: iterate over the whole collection, performing an arbitrary operation on each element. This is the only operation I see in your list that isn't supported by associative arrays in the D spec.
> >
> > You're right.  Ok, in addition to the "in" operator we need an "each" or "for_each" operator.  But that could be implemented as a function, though an operator would be nicer.
> 
> Turns out we have it in the D spec:
> 
>   for (int i = 0; i < assoc_array.keys.length; i++)
>   {
>       operate_on( assoc_array[ assoc_array.keys[i] ] );
>   }

	Yes, but can this break if you are adding or deleting certain elements
for the array as you go?  In that case you would have to do this:

	string[] keys = assoc_array.keys;
	for (int i = 0; i < keys.length; i++){
		if( bad_element(assoc_array[keys[i]]) )
			delete assoc_array[keys[i]];
	}

A foreach that worked on arrays with a known size and associative arrays
would be nicer and less error prone.

Dan

"Angus Graham" <agraham_d@agraham.ca> wrote in message news:9lump1$2qal$1@digitaldaemon.com...
> > Which basically proves Daniel's point. Why should the programmer have to code this explicitly?
>
> Becuase if you have a large list of things to test membership in you can
use
> a real container.

True, for instance, In Delphi (*The* pascal-derived language these days), a set may have up to 256 elements, no more. All it really is whole lot of bits side by side, 32 byets at most. Membership testing is implemented as bit testing, union as or-ing the bits, etc.

> If you have a tiny list you can use one line of code.
> How often would a built in set be useful?  To me, seldom to never, so why
> cut down a tree and put it in every D manual?

Speaking as someone who has used Delphi for several years, sets over an enum are very usefull, used often, and would be missed. The most common usage is for options to a class or proc. For instance, look at this code fragment:

type
  TFontStyle = (fsBold, fsItalic, fsUnderline, fsStrikeOut);
  TFontStyles = set of TFontStyle;

 class TFont

   procedure setStyle(style: TFontStyles); // actually this would be a
property, but one thing at a time
 ...
end;

  MyFont.setStyle( [fsBold, fsUnderline]);
.. MyFont.Style := myFont.Style + fsItalic;

The implementation is effiicient, and so is the usage syntax. And it's type-safe. Object-Pascal is not perfect, but this feature is really nice

"Charles Hixson" <charleshixsn@earthlink.net> wrote in message news:3B83D667.40505@earthlink.net...

> >...
> It's hard to argue that sets wouldn't be nice to have.  So would AVL-trees, and B+Trees.  And other classical data structures.  Perhaps a better approach would be to emphasize ways that make the language easy to extend with these features.

Most things can be added to an OO language simply by writing the appropriate classes, or finding them in the standard library.

But I have not seen sets done well this way in an efficient manner - To take an example, Java, where classes are by design the *only* mechanism for making new types, there is a set class, and no language support for enums. However using sets and option-objects is so ugly and cumbersome that everyone, sun included, just uses named integer constants. This is a giant leap backwards. Built-in enums and sets in Delphi are a great enabler.

Anthony Steele wrote:

> "Charles Hixson" <charleshixsn@earthlink.net> wrote in
> message news:3B83D667.40505@earthlink.net...
>
>
>>> ...
>>>
>> It's hard to argue that sets wouldn't be nice to have.  So
>>  would AVL-trees, and B+Trees.  And other classical data
>> structures.  Perhaps a better approach would be to
>> emphasize ways that make the language easy to extend with
>>  these features.
>>
>
> Most things can be added to an OO language simply by writing
>  the appropriate classes, or finding them in the standard
> library.
>
> But I have not seen sets done well this way in an efficient
> manner - To take an example, Java, where classes are by
> design the *only* mechanism for making new types, there is
> a set class, and no language support for enums. However
> using sets and option-objects is so ugly and cumbersome that everyone, sun included, just uses named integer constants. This is a giant
> leap backwards. Built-in enums and sets in Delphi are a great enabler.
>
The primary feature needed to allow this (efficiently) is the ability to overload the indexing operators.



> > everyone, sun included, just uses named integer
> constants. This is a giant leap backwards. Built-in enums
> and sets in Delphi are a great enabler.
>
The primary feature needed to allow this (efficiently) is the ability to overload the indexing operators.  In Python, e.g., the same opeartors used to set and access the hash table directories, can also be used to access B+Tree style databases.  It's true that one needs ancillary operations to access the additional features (e.g., in-order traversal), but the features of set by key and retrieve by key can be accessed via a simple:
a{"peanut"} = "butter";
print a{"peanut"}
--> butter

In python the key step is that when on initializes the variable ("a" in this case), instead of initializing it as a hash table:
a = {} or a = {"Able" : "was", "I" : "ere"}
one initializes it as a database:
a = db("C:\file\location.dbm")
The type of database is determined by the module "anydbm" which looks at the file to figure out which of three or four kinds of database it is.  The B+Tree version that I'm speaking of is the SleepyCat database.

But most of this doesn't require run-time configuration. Clearly one might prefer to declare at compile time that it was a B+Tree rather than a flat-file lookup table, but as long as the ancestral class (abstract class or interface?), say, DBM, had the requisite methods defined, that would be all that was required.  Then the methods could be activated at run time.  But if the standard operations can't be overloaded, then this falls through.  As an alternative, I have proposed using demarkations, e.g. :+:, but this doesn't work well when used as indexing syntax, consider:
a:[:"peanut":}: = "butter";
I'd almost prefer:
a.set("peanut").to("butter");
or:
a("peanut").set_to("butter");

An array of bits in D probably comes closest to what you're looking for. -Walter

Russell Bornschlegel wrote in message <3B83EF19.D755A19@estarcion.com>...
>The D spec is silent on the implementation details for
>associative arrays, but they'd likely be binary trees (ordered
>keys, lookup time normally O(log2(n))) or hashes (disordered keys,
>lookup time normally O(1)).


It's supposed to be an implementation detail <g>, but they are implemented as a hashed array of binary trees. My experience with them is that they are very efficient.

Daniel Mantione wrote in message <9m19an$1a1b$1@digitaldaemon.com>...
>Luckily you can turn off range checking, which you usually do when your program is bug-free.

Range checking is a wonderful feature that goes too far when you can't turn it off for the production release.

"Russell Bornschlegel" <kaleja@estarcion.com> wrote in message news:3B8422B8.80B09E1C@estarcion.com...
> Daniel Mantione wrote:
> > Yes, this looks like a very promising implementation to use sets. What
you
> > are essentially saying is that an array of bits has set semantics, like
the
> > "in" operator.
>
> As currently specified, though, associative-array-of-bit actually has three states per key: 1, 0, or not-in-set. That's not a great fit to an underlying array-of-bit implementation.

Seems like a set is more of an associative array of a type that has no value and takes no storage.  So I don't think associative array of any value type would be an optimal way to implement a set.

Sean