Re: if Condition expression can't have function?
On 04/25/2014 09:14 AM, FrankLike via Digitalmars-d wrote:
Hi,everyone,
Here has a error after run: main.exe 11 or main.exe 10 :
template find(T)
{
size_t find(T[] Array,T Element)
{
find returns a size_t being a nonnegativ number.
return -1;
But here it returns -1.
In your main code you check find() = 0, so maybe the compiler
simplifies it in some situations because a size_t value is always = 0.
Matthias
Re: Testing presence of member functions with same name but different signature.
On 02/06/2014 10:44 PM, Timon Gehr wrote: On 02/06/2014 10:32 PM, Matthias Walter wrote: Is this a bug? Yes. Okay, added a ticket: http://d.puremagic.com/issues/show_bug.cgi?id=12102
Testing presence of member functions with same name but different signature.
Hi,
I realized the following behavior and want to ask whether this is
expected behavior and if yes, I'd like to know a reason.
The check of MyClass.func(MyClass.A) and MyClass.func(MyClass.B) in the
main() function succeeds, but the alias line *in* the class definition
fails with template instance main.ConditionalUse!(MyClass) does not
match template declaration ConditionalUse(T) if (hasFuncs!T).
If I rename func to funcA and funcB (making the name unambiguous), both
checks succeed.
Is this a bug?
template hasFuncs(T) // Checks presence of T.func(T.A) and T.func(T.B)
{
enum bool hasFuncs =
is(typeof((T t, T.A a){ t.func(a); }))
is(typeof((T t, T.B b){ t.func(b); }));
}
struct ConditionalUse(T) if (hasFuncs!T) { }
// This line fails with
//
// template instance main.ConditionalUse!(MyClass) does not
// match template declaration ConditionalUse(T) if (hasFuncs!T)
class MyClass
{
struct A {}
struct B {}
alias ConditionalUse!MyClass Foo;
void func(A a) { }
void func(B b) { }
}
int main(char[][] args)
{
static assert(hasFuncs!MyClass); // This assert is fine.
return 0;
}
Best regards,
Matthias
inout type constructor applied to this-reference
Hi,
I read about inout functions in the language documentation which allows
to use inout in order to set the constness of the return type based on
the constness of some argument. What is not mentioned is that this also
works for the this-reference by marking the function itself inout:
So instead of
class C
{
OtherClass foo;
const(OtherClass) getOther() const { return foo; }
OtherClass getOther() { return foo; }
}
we can write
class C
{
OtherClass foo;
inout(OtherClass) getOther() inout { return foo; }
}
Since the documentation only talks about marking arguments inout, can I
nevertheless rely on its behavior? Anyways, I think it is worth to be
included in the docs.
Best regards,
Matthias
Member-assignment for std.container.Array!Struct
Hi,
about 2 years ago I stopped using D for my projects since there were too
many bugs that hindered me from making quick progress. Since I got
several mails from bugzilla about those bugs being fixed I wanted to
give it another try. Unfortunately, the following non-working code made
me think to stop using it once again:
struct S
{
int i;
}
Array!S array = [ S(0) ];
array[0].i = 1;
The reason is certainly that the change only affects a copy and not the
true array-member. I remember that there was a discussion about sealed
containers and returning references, etc.
My question is now: Has there been any progress in this direction? I
know that the design of ref's semantics is a nontrivial topic, but on
the other hand in my opinion std.container.Array is completely useless
if not even the above code works as one would expect!
Best regards,
Matthias
Re: Initialization of std.typecons.RefCounted objects
On 07/18/2012 03:32 PM, Christophe Travert wrote: Matthias Walter , dans le message (digitalmars.D:172673), a écrit : I looked at Bug #6153 (Array!(Array!int) failure) and found that the This exactly is what makes the following code fail: Array!(Array!int) array2d; array2d.length = 1; array2d[0].insert(1); The inner array array2d[0] was not initialized and hence the reference pointer is null. Since Array.opIndex returns by value, the 'insert' method is called on a temporary object and does not affect the inner array (still being empty) which is stored in the outer array. What do you think about this? Must the user ensure that the Array container is always initialized explicitly? If yes, how shall this happen since the only constructor takes a (non-empty) tuple of new elements. Or shall opIndex return by reference? I think opIndex should return by reference. opIndexAssign is of no help when the user want to use a function that takes a reference (here Array.insert). It is normal that Array uses default construction when someone increases the array's length. Okay, I fully agree here. Besides that point, I don't see why default-constructed Array have an uninitialised Payload. This makes uninitialised Array behaves unexpectedly, because making a copy and using the copy will not affect the original, which is not the intended reference value behavior. Well the reason is that no user-defined function is called when a struct is default-constructed and then copied into another variable (the first one is this(this) which only known the new variable). Hence no user code can be written that would initialize the payload. Do we need a paradigm to perform explicit initialization of structs? Best regards, Matthias
Re: Initialization of std.typecons.RefCounted objects
On 07/19/2012 10:14 AM, Christophe Travert wrote: monarch_dodra , dans le message (digitalmars.D:172700), a écrit : I think it would be better to initialize on copy, rather than default initialize. There are too many cases an empty array is created, then initialized on the next line, or passed to something else that does the initialization proper. Not default-initializing Array has a cost for every legitimate use of an Array. I think people use Array more often than they create uninitialized ones that are not going to be used before an other Array instance is assigned to them, so Array would be more efficient if it was default initialized and never check it is initialized again. But that's just speculation. I agree here. Additionally my question: Is it possible (at the moment) to really do initialize on copy? As far as I see it, the only way to interact here is to implement 'this(this)' which is called after bit-copying and hence cannot access the source of the copy process.
Re: Initialization of std.typecons.RefCounted objects
On 07/19/2012 02:16 PM, Christophe Travert wrote: monarch_dodra , dans le message (digitalmars.D:172710), a écrit : One of the reason the implementation doesn't let you escape a reference is that that reference may become (_unverifiably_) invalid. The same applies to a dynamic array: it is undistinguishable from a sliced static array. More generally, as long as you allow variables on the stack with no escaped reference tracking, you can't ensure references remain valid. Even in safe code. If I want my references to remain valid, I use dynamic array and garbage collection. If I use Array, I accept that my references may die. Array that protects the validity of their references are awesome. But, IMHO, not at that cost. ...That said, I see no reason for the other containers (SList, I'm looking at you), not to expose references. I'm against not exposing reference, but all containers will be implemented with custom allocator someday. The current work around? Copy-Extract, manipulate, re-insert. Sucks. IMO, what sucks even more is that arr[0].insert(foo) compiles while it has no effect. arr[0] is a R-value, but applying method to R-value is allowed. I don't know the state of debates about forbiding to call non-const methods on R-values. I think this would break too much code. As it seems the issue really should be resolved by making opIndex return by reference and press thumbs hard that something like a 'scope ref' will be implemented? Furthermore, since RefCounted objects do not behave like reference types until initialized, they *must* be initialized before anything else happens and hence I propose to change std.container.Array like Christophe said: Replace 'isInitialized()' checks by assertions and add a method with which the user explicitly initialized the reference counter. Or is there a reasonable alternative? Best regards, Matthias Walter
Re: Getting a range over a const Container
On 07/19/2012 06:44 AM, Jonathan M Davis wrote: On Thursday, July 19, 2012 04:39:26 Francisco Soulignac wrote: So, my question is how can I (correctly) traverse a const SList, const DList, etc? Right now? I'm pretty sure that that's impossible. Hopefully that will change, but getting const and ranges to work together can be rather difficult, and std.container needs more work in that regard. Well it doesn't work yet. But in principle it could since we can always copy a const pointer to a non-const one to const data: Node* actual; // but 'this' is const and hence the type is const(Node*) const(Node)* i_will_traverse = actual; Best regards, Matthias
Re: ~= call copy ctor?
On 07/19/2012 02:27 PM, Namespace wrote:
I have a 2 questions.
I have this code:
[code]
import std.stdio;
struct Test {
public:
this(int i = 0) {
writeln(Test CTor.);
}
this(this) {
writeln(Test Copy CTor);
}
~this() {
writeln(Test DTor);
}
}
Test[] _arr;
void copy_save(Test t) {
_arr ~= t;
}
void by_ref_save(ref Test t) {
_arr ~= t;
}
[/code]
Why get i with
[code]
void main() {
Test t = 42;
by_ref_save(t);
}
[/code]
this output:
Test CTor.
Test Copy CTor
Test DTor
As you mentioned in the subject the copy constructor is not called while
the struct is passed by reference but on array concatenation.
But this must occur since the array has its memory region and the
original variable t in main() also has. Since they are different, at
some point the struct must be copied from t in main() into the array.
The ref only ensures that it is passed via reference (a pointer to the
memory of t in main()) to the function by_ref_save().
And the same if i have this:
[code]
void main() {
Test t = 42;
copy_save(t);
}
[/code]
t is already a clone. Why it is copied again?
Here it is once copied from t in main() into the local variable t in
copy_save() and then copied (as in your 1st example) into the array.
Imagine the copy_save routine is in a different module and only its
signature is exposed to main. When calling the function, the compiler
does not know what happens inside copy_save but it must put the variable
onto the stack at the position of the first parameter (well, in this
case it is probably put into a CPU register, but that doesn't matter here).
Then, when copy_save is invoked it only knows the local variable which
it then copies into the array memory (after enlarging the array).
It *may* be the when you enable compiler optimizations (-O -inline) that
copy_save gets inlined and hence the compiler can optimize one of the
copy calls away. But that I don't know for sure.
Best regards,
Matthias
Re: ~= call copy ctor?
On 07/19/2012 03:00 PM, Namespace wrote: Is there any way to avoid the implizit copy ctor by array concatenation? Or is the only way to use a pointer? Yes, in some way you have to. If you want to not copy a lot of data (or avoid additional on-copy effort) you either have to you pointers explicitly (Test*[]) or implicitly. The latter works e.g. by making Test a class which means that the variable actually does store a pointer to the instance. Note that for struct pointers you should not escape them, i.e. have a variable local in a function, puts its address into some array and returning that array. Since the local variable is gone, the pointer is invalid as well. (Nothing happens if you do not access it). Best regards, Matthias
Initialization of std.typecons.RefCounted objects
Hi, I looked at Bug #6153 (Array!(Array!int) failure) and found that the reason is the following behavior: Given some type T you wrap as RefCounted!T object, then proper use of the auto-initialization feature or manual initialization on demand ensures that no null-pointer dereference will happen. But the other problem is that as long as the wrapped object is uninitialized, the object behaves like a value type instead of a reference type. This exactly is what makes the following code fail: Array!(Array!int) array2d; array2d.length = 1; array2d[0].insert(1); The inner array array2d[0] was not initialized and hence the reference pointer is null. Since Array.opIndex returns by value, the 'insert' method is called on a temporary object and does not affect the inner array (still being empty) which is stored in the outer array. What do you think about this? Must the user ensure that the Array container is always initialized explicitly? If yes, how shall this happen since the only constructor takes a (non-empty) tuple of new elements. Or shall opIndex return by reference? The problem arises in the same way if Array was a class - but then the user typically knows that after enlarging the outer array, the inner array is a null pointer which must be created by new. Best regards, Matthias Walter
Progress on std.container
Hi, I'd like to know who is currently working on std.container - at some point I read that Andrei works on user-controlled allocation and then the issues of container structures will be addressed. Unforntunately, at the moment std.container.Array is unusable for me because of missing const Range (8248) and impossible arrays of arrays (6153). Is there a way to see how far this development is? Can one contribute somehow? I would offer to contribute but only on a basis where the general design is fixed (e.g. there is a reference implementation for a certain container) to add other missing containers. Best regards, Matthias
Re: Progress on std.container
On 07/17/2012 12:41 AM, Andrei Alexandrescu wrote: On 7/16/12 4:19 AM, Matthias Walter wrote: Hi, I'd like to know who is currently working on std.container - at some point I read that Andrei works on user-controlled allocation and then the issues of container structures will be addressed. Unforntunately, at the moment std.container.Array is unusable for me because of missing const Range (8248) and impossible arrays of arrays (6153). Is there a way to see how far this development is? Can one contribute somehow? I would offer to contribute but only on a basis where the general design is fixed (e.g. there is a reference implementation for a certain container) to add other missing containers. I'm the bottleneck for that. My list of actual work (aside from my duties as phobos/druntime/tools/dlang.org curator) is: 1. Put std.benchmark through the review process 2. Define allocators 3. Integrate allocators with std.container If you have fixes for std.container that are faraway from allocation issues, I think it's safe to propose them as pull requests. I assume the advent of allocators will be a uniform additive changes for all containers. That's good news - despite the fact the you have loads of work. I will probably work on these things. Thank you!
Re: foreach syntax
On 06/29/2012 12:47 PM, Namespace wrote:
A friend of mine ask me why D's foreach isn't like C#
Means, why is it like
int[] arr = [1, 2, 3];
foreach (int val; arr) {
and not
foreach (int val in arr) {
which it is more intuitive.
I could give him no clever answer to, so maybe someone here knows the
reasons.
I suppose it is because the usual 'for' loop is a relative of 'foreach'.
And there we (and the C world) uses ';'.
Re: Primary Ranges of Containers
On 06/19/2012 04:04 PM, Timon Gehr wrote:
On 06/19/2012 02:54 PM, Christophe Travert wrote:
Jonathan M Davis , dans le message (digitalmars.D:170054), a écrit :
I'd propose to always add a bool template parameter (maybe isConst?) to
the range since most of the write-functionality can be removed by a
static if statement in order to make the range read-only.
Any suggestions?
Boolean parameters are very obscure.
How do you guess what is the meaning of false in:
Range!false;
Range!IsConst.no would be better.
struct ArrayRange(bool isConst) {...}
alias ArrayRange!false Range;
alias ArrayRange!true ConstRange;
Range and ConstRange seems a good thing to have, just like c++
containers have iterator and const_iterator.
Something along these lines seems to be a superior design:
struct ArrayRange(T){ ... }
class Array(T){
...
ArrayRange!T opSlice(){ ... }
ArrayRange!(const(T)) opSlice()const{ ... }
ArrayRange!(immutable(T)) opSlice()immutable{ ... }
...
}
(Where the opSlice functions can be generated automatically.)
I like the design. I looked at the actual implementation of
std.container.Array and realized the following problem:
The payload is stored in a RefCounted object. The range returned by
opSlice() const must obviously somehow access the payload. By
documentation of RefCounted, no references to the payload should be
escaped outside the RefCounted object. which implies that we need to
create a copy of the RefCounted variable to have proper access.
On the other hand, given the constness of opSlice() we only have access
to a const version of the RefCounted variable which cannot be used to
create another reference since the reference counter is const as well.
So how can a ConstRange be implemented *somehow*?
Matthias
Re: Primary Ranges of Containers
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
On 06/18/2012 01:08 PM, Jonathan M Davis wrote:
On Monday, June 18, 2012 10:06:44 Matthias Walter wrote:
Hi,
last week I realized that a const version of
std.container.Array.opSlice() is missing. Now I looked at the
code and I think that it is a general design problem.
The docs state that c.Range is The primary range type
associated with the container.. I think we really always need
two Range types (one for const view and one for non-const view)
by design.
I'd propose to always add a bool template parameter (maybe
isConst?) to the range since most of the write-functionality can
be removed by a static if statement in order to make the range
read-only.
Any suggestions?
Yeah, it'll probably have to be templated. C++ already has to do
something similar with iterators and const_iterators. But since you
don't normally use the type of a range explicitly, it shouldn't be
a big deal. The one downside that might pose a problem though is
that if someone _does_ use the type explicitly, their code will
break if the type gets templated. We could make a second type
(ConstRange?) for the iterating over a const Array, but I'd be
tempted to just templatize the thing and let it break any code that
it breaks. std.container is already likely to break stuff to at
least some extent when the custom allocators get added anyway. I
suppose that we could just rename the type and then create an alias
for the current type
struct ArrayRange(bool isConst) {...} alias ArrayRange!false
Range; alias ArrayRange!true ConstRange;
but that might be overkill. I don't know. Regardless, it _is_
likely that the range type will have to be templatized to fix the
problem. Ranges and range- based functions in general need to be
cleaned up a bit to deal with const, since the way that they're
designed doesn't work with const very well, and we need to make it
work. I think that it _can_ work, but it takes more effort to do
so.
I fully agree with all that. In order to migrate older code we may
make isConst have a default value of false.
Best regards,
Matthias
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
iQEcBAEBAgAGBQJP4B8OAAoJEPdcuJbq5/sR7h0H/jeJ+KPUMoiP9SqiamE0qv4V
IantID2fzML8b55CWGQ2ZU7YbhQqOPIIEVtRriNAUIA4sHqWXQA03YgFrDk7XZZy
jrhx9VCUkiMeIuHhSdXQIwAWH+dkfnQoOS9EwbbiwZjBG+zU5iH/s9tduRzKadTr
Bb4QLAx7hEjlsvgRArj0O5z88YeGWbLhUzTz70utoE+1VgROuVF4WzJL9S803ZWX
ZZR1HOx0ktE60jvBTMoK2TzSfB5/JjiDQSWjK8ikEQGSw8QR3M3DWD3WkFucOAaL
3K6xH/yoDTBMOT+IVjkfVOsnv0iBB7ARpJKxOD2r+bJOoGWCQ1YQAoyY8rwrez0=
=yhaM
-END PGP SIGNATURE-
Re: How to break const
On 06/18/2012 07:36 AM, Mehrdad wrote:
Is it just me, or did I subvert the type system here?
import std.stdio;
struct Const
{
this(void delegate() increment)
{ this.increment = increment; }
int a;
void delegate() increment;
void oops() const { this.increment(); }
}
void main()
{
Const c;
c = Const({ c.a++; });
writeln(c.a);
c.oops();
writeln(c.a);
}
I don't think so. When calling oops you have two references to the object c:
- The this-pointer of the object itself which is not allowed to change
the object in the const-call.
- The reference from within main which is allowed to change it and can
be reached via the frame pointer of the delegate.
I see this as perfectly valid code. Of course, opinions may differ here.
Matthias
Re: How to break const
On 06/18/2012 08:04 AM, Mehrdad wrote:
On Monday, 18 June 2012 at 06:00:11 UTC, Matthias Walter wrote:
On 06/18/2012 07:36 AM, Mehrdad wrote:
Is it just me, or did I subvert the type system here?
import std.stdio;
struct Const
{
this(void delegate() increment)
{ this.increment = increment; }
int a;
void delegate() increment;
void oops() const { this.increment(); }
}
void main()
{
Const c;
c = Const({ c.a++; });
writeln(c.a);
c.oops();
writeln(c.a);
}
I don't think so. When calling oops you have two references to the
object c:
- The this-pointer of the object itself which is not allowed to change
the object in the const-call.
- The reference from within main which is allowed to change it and can
be reached via the frame pointer of the delegate.
I see this as perfectly valid code. Of course, opinions may differ here.
Matthias
My trouble isn't with the delegate, it's with the const method.
It's with the idea that you can tell something about the code just by
looking at it.
The way I understood it, you can assume that a `const` method cannot
modify an object, but... that doesn't seem to be the case here.
What am I misunderstanding?
Its not, that a const method cannot modify an object, it just ensures
that the const method cannot modify the object *by using the this-pointer*.
Other things cannot be ensured with const: For example, a const method
could wake up a 2nd thread and proceed with a longer computation. Then
this 2nd thread may have a reference to the object and may change it
while your computation is going on.
Re: How to break const
On 06/18/2012 08:19 AM, Mehrdad wrote: On Monday, 18 June 2012 at 06:14:22 UTC, Matthias Walter wrote: Its not, that a const method cannot modify an object, it just ensures that the const method cannot modify the object *by using the this-pointer*. I see... So that means you /can't/ tell something just by looking at a part of the code, right? (Just mentioning this since this idea seemed to be emphasized a lot by D.) Yes, you are right with that.
Primary Ranges of Containers
Hi, last week I realized that a const version of std.container.Array.opSlice() is missing. Now I looked at the code and I think that it is a general design problem. The docs state that c.Range is The primary range type associated with the container.. I think we really always need two Range types (one for const view and one for non-const view) by design. I'd propose to always add a bool template parameter (maybe isConst?) to the range since most of the write-functionality can be removed by a static if statement in order to make the range read-only. Any suggestions? Best regards, Matthias
Getting a range over a const Container
Hi, I have a const std.container object (e.g., a const(Array!int)) of which I'd like to have a range which can traverse that container having read-only access. This does not seem to be possible with opSlice(). Is there an alternative? Best regards, Matthias
Re: const version for foreach/opApply
On 06/10/2012 12:30 AM, Era Scarecrow wrote: On Saturday, 9 June 2012 at 10:09:25 UTC, Matthias Walter wrote: First, thank you for your answer. I've already made some tiny modifications in order to make BitArray work for my purposes: https://github.com/xammy/phobos/commit/eb46d99217f2bf1e6d173964e2954248b08146d6 If you plan to create pull requests for your changes - please consider my changes as well. When do you expect to finish, I.e., create a pull request for phobos? Curious... Almost all of the changes you proposed I've already added in my version, the toHash is the only one missing and I don't know if I can work that very well. The new version is going to include 'slice-like' features, which is mostly a couple extra numbers specifying the offset in bits from the beginning to the end; The problem with that is hashing would have a huge speed drop. I'm adding an 'realign' function that handles those cases, but the downside is shared slices where you would want to make changes may or may not work. Caching the result would also be useful... Hmmm... I don't suppose you have a toHash where I can enter the odd bits and then also bulk ones and have the hash return the same could you? I can I see the problem. I don't know whether my hash function is a good one - I just needed it to make AAs work with BitArray as a key type. But the question is interesting. Finding a good hash function for bit arrays which is invariant under realignment. see xor easily having this type of effect... Anyways, here's some things I can do so far; Got a few improvements left to do, but not many. (const immutable friendly of course :) ) -- const BitArray ba = BitArray([1,1,0,0,1]); const BitArray slice = ba[1 .. ba.length]; BitArray m = slice.dup; immutable BitArray im = slice.idup; assert(slice == ba[1 .. ba.length]); assert(slice == [1,0,0,1]); assert(slice == m); assert(slice == im); assert(slice.isCompact); writeln(GC not used); Looks interesting!
Re: const version for foreach/opApply
On 2012-06-08 22:47, Era Scarecrow wrote: On Friday, 8 June 2012 at 16:33:28 UTC, Matthias Walter wrote: Hi, trying to traverse the entries of a std.bitmanip.BitArray I stumbled upon the following problem: In case I want to accept const(BitArray) objects, it shall look like the following (maybe using ref const(bool) for the delegate parameter?): int opApply(scope int delegate(bool) dg) const Can one glue both things together into a single routine (using inout magic or whatever)? I want to say you can't, because ref bool. If you ignore the reference, you don't need the non-const version (I think). I am currently working on BitArray updates, and it is const/immutable friendly according to as many tests as I could come up with for valid usage; This has taught me a lot on using templates, traits, constraints and how inout actually works. I haven't tried for a bit but I can try once more to send my code to GitHub, then you can give it a try. First, thank you for your answer. I've already made some tiny modifications in order to make BitArray work for my purposes: https://github.com/xammy/phobos/commit/eb46d99217f2bf1e6d173964e2954248b08146d6 If you plan to create pull requests for your changes - please consider my changes as well. When do you expect to finish, i.e., create a pull request for phobos?
const version for foreach/opApply
Hi,
trying to traverse the entries of a std.bitmanip.BitArray I stumbled
upon the following problem:
The original code is as follows:
int opApply(scope int delegate(ref bool) dg)
{
int result;
for (size_t i = 0; i len; i++)
{
bool b = opIndex(i);
result = dg(b);
this[i] = b;
if (result)
break;
}
return result;
}
In case I want to accept const(BitArray) objects, it shall look like the
following (maybe using ref const(bool) for the delegate parameter?):
int opApply(scope int delegate(bool) dg) const
{
int result;
for (size_t i = 0; i len; i++)
{
bool b = opIndex(i);
result = dg(b);
if (result)
break;
}
return result;
}
Can one glue both things together into a single routine (using inout
magic or whatever)?
Best regards,
Matthias Walter
Re: Website
On 06/01/2012 07:42 AM, d coder wrote: Why am I being taken to Digital Daemon when I goto http://dlang.org ? Seems like the DNS entry points still to the original IP address. That's all I could find out. Where can I find official D language site now? http://erdani.com/d/web/index.html exists but don't know how old this version is. best regards, Matthias
Re: How to test for equality of types?
On 2012-05-19 09:05, Philippe Sigaud wrote:
On Fri, May 18, 2012 at 11:51 PM, Simen Kjaeraas simen.kja...@gmail.com
wrote:
Because Wrapper!(AliasStruct).Wrap does not exist. And _error_ is not
equal to any other type.
Yes. Wrap is included in the complete template name (Wrapper!(Wrap))
and has no independent existence.
You _can_ get access to it by exposing it as an alias, as you do in
AliasStruct:
struct Wrapper(Wrap)
{
alias Wrap Wrapped; // cannot call it 'Wrap'
...
}
Yes, of course you are right. This was my fault - after exposing it via
an alias, it prints true.
(third case)
false
And here I disagree. This prints true on 2.059. Regression?
AFAICT, this should print true.
And, concerning Artur questio, on 2.059 (Linux):
pragma(msg, is(w._wrap.Alias == AliasStruct.Alias));// - true
pragma(msg, typeof(w._wrap).Alias.stringof); // - MyStruct
pragma(msg, AliasStruct.Alias.stringof); // - MyStruct
I would open a bug report with the following code which is a bit smaller
than my first wrong version:
=
module main;
struct MyStruct { }
struct AliasStruct
{
alias MyStruct Alias;
}
struct Wrapper
{
AliasStruct aliasStruct;
}
void main()
{
Wrapper w;
pragma(msg, typeof(w.aliasStruct).Alias.stringof); // - MyStruct
pragma(msg, AliasStruct.Alias.stringof); // - MyStruct
static assert(is(typeof(w.aliasStruct) == AliasStruct)); // - true
static assert(is(typeof(w.aliasStruct).Alias == AliasStruct.Alias));
// - false
}
=
Best regards,
Matthias
Re: How to test for equality of types?
On 2012-05-19 15:28, Philippe Sigaud wrote:
On Sat, May 19, 2012 at 12:23 PM, Matthias Walter
xa...@xammy.homelinux.net wrote:
I would open a bug report with the following code which is a bit smaller
than my first wrong version:
=
(...)
pragma(msg, typeof(w.aliasStruct).Alias.stringof); // - MyStruct
pragma(msg, AliasStruct.Alias.stringof); // - MyStruct
static assert(is(typeof(w.aliasStruct) == AliasStruct)); // - true
static assert(is(typeof(w.aliasStruct).Alias == AliasStruct.Alias));
// - false
}
Seems like a pb concerning whether Alias is a type or a symbol. See
A,B,C,D below:
void main()
{
Wrapper w;
pragma(msg, typeof(w.aliasStruct).Alias.stringof); // - MyStruct
pragma(msg, AliasStruct.Alias.stringof); // - MyStruct
static assert(is(typeof(w.aliasStruct) == AliasStruct)); // - true
static assert(is(w.aliasStruct.Alias == AliasStruct.Alias)); // - true
alias typeof(w.aliasStruct) A; // - OK
//alias typeof(w.aliasStruct).Alias B; // - NOK
//alias A.Alias C; // - NOK
alias w.aliasStruct.Alias D; // - OK
static assert(is(A.Alias == AliasStruct.Alias)); // - true
//static assert(is(B == AliasStruct.Alias));
//static assert(is(C == AliasStruct.Alias));
static assert(is(D == AliasStruct.Alias)); // - true
}
I think A is enough for your need, but I don't get why B and C are not
accepted (DMD 2.059, Linux)
Using the current git version of dmd I realized that C works! Hence, as
a workaround it can be used by creating a local alias A and subsequently
using A.Alias in the is-expressions. But it seems odd that
alias typeof(X).A B; does not work but
alias typeof(X) Y; alias Y.A B; does.
Is this considered as a bug?
Best regards,
Matthias
How to test for equality of types?
Hi, how do I test two types for equality? Suppose I have A and B aliasing some type(s), how do I find out if they are aliases the same thing? I tried the is(A == B) expression, but this does not always work (tell me if I shall give an example). On the other hand, according to the spec the IsExpression is not supposed to compare two aliases with each other. Best regards, Matthias
Re: How to test for equality of types?
On 2012-05-18 16:12, Steven Schveighoffer wrote:
On Fri, 18 May 2012 06:06:45 -0400, Matthias Walter wrote:
how do I test two types for equality? Suppose I have A and B aliasing
some type(s), how do I find out if they are aliases the same thing?
I tried the is(A == B) expression, but this does not always work (tell
me if I shall give an example).
I would expect this to work. What situation does it not (maybe you
aren't actually testing for equality there).
It could be a bug...
=
struct MyStruct { }
struct Wrapper(Wrap)
{
Wrap _wrap;
this(Wrap wrap)
{
_wrap = wrap;
}
}
struct AliasStruct
{
public:
alias MyStruct Alias;
}
int main(char[][] args)
{
auto w = Wrapper!(AliasStruct)(AliasStruct.init);
pragma(msg, is(Wrapper!(AliasStruct).Wrap == AliasStruct) ? true :
false);
pragma(msg, is(typeof(w._wrap) == AliasStruct) ? true : false);
pragma(msg, is(typeof(w._wrap).Alias == AliasStruct.Alias) ? true :
false);
return 0;
}
=
prints out
false
true
false
during compilation using current git version of dmd. In my application I
used the third case, i.e., wanted to find out whether they alias the
same thing.
On the other hand, according to the spec the IsExpression is not
supposed to compare two aliases with each other.
where does it say that?
Okay, this seems to be my fault. It states different cases for the RHS
operator of is(LHS == RHS), e.g., Type == TypeSpecialization, but
nothing like Type == Type. But TypeSpecialization includes Type as well...
Best regards,
Matthias
Re: Keyword arguments / Named parameters library implementation
On 03/19/2012 08:21 PM, Andrej Mitrovic wrote: On 3/19/12, Matthias Walter xa...@xammy.homelinux.net wrote: Hi, I've written a small module (at the moment called utils.keywordargs) which simulates keyword arguments (aka named parameters). Cool. A small tip (in case you didn't already know): You can use allSatisfy from std.typetuple when checking a single constraint on multiple parameters: static assert(allSatisfy!(isKeywordArgument, H, V)); Didn't know that - thanks a lot!
Re: Keyword arguments / Named parameters library implementation
On 03/19/2012 07:53 PM, bearophile wrote: Matthias Walter: I've written a small module (at the moment called utils.keywordargs) which simulates keyword arguments (aka named parameters). The documentation can be found here, Regardless the implementation quality of your code, I wait for the real thing :-) I understand the real thing as a language implementation of keyword arguments instead of a library workaround, right?
Keyword arguments / Named parameters library implementation
Hi, I've written a small module (at the moment called utils.keywordargs) which simulates keyword arguments (aka named parameters). The documentation can be found here, http://xammy.xammy.homelinux.net/~xammy/utils_keywordargs.html while the code is at http://xammy.xammy.homelinux.net/~xammy/keywordargs.d or in a better readable format: http://pastebin.com/AfqKKziW There was some discussion about introducing them in the language a while ago. One argument against keyword arguments was that the names become part of the interface. This wouldn't be different when using my implementation, but as the names are compile-time strings, handling different versions of a library is just a matter of putting the right string constant into the keyword argument template. Any comments? Is something like that interesting for phobos? If yes, I'd suggest to put it on github to make further work easier. Best regards, Matthias
Remarks on std.container
Hi, I wanted to have a binary heap where I can update entries and restore the heap structure. 1. First I observed that due to the implementation of std.container.BinaryHeap, keeping track of the position of a certain value in the heap cannot be done directly, but it would be helpful to pass a Swapper object (or function) to the methods that may change the order of the elements such that this Swapper is called for every swap() operation such that the user of the BinaryHeap can keep track of the permutation. 2. I tried to create a heap structure on my own, using std.container.Array as a store. Of course, it I also needs to perform swap operations, but the following did not work: std.algorithm.swap(arrayInstance[i], arrayInstance[j]); Also there is no usable swap() method of Array. So do I really have to perform the swap on my own? I mean, 3 lines of code aren't that much but I really expected an easy way. 3. For my structure I wanted to check the heap structure in an invariant(). Unfortunately, accessing stored elements of Array is no const operation, hence I could not implement such an invariant. Maybe I'm not using it correctly, so any help or comments would be nice. Best regards, Matthias
Named parameters workaround
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
Hi,
named parameters have been discussed awhile ago and it seems to me
that they won't get into the language soon. I came up with a
workaround that makes it possible to use them with some extra typing.
Suppose we have a function
foo(int a, int b, string c, MyStruct d, MyClass e);
and want to call with with named parameters. It is possible to write a
wrapper function as follows
foo(N)(N n)
{
foo(
n.has!a() ? n.get!a() : 42, // 42 is the default parameter
n.get!b(), // Complain if b is not given
n.has!c() ? n.get!c() : foo,
n.has!d() ? n.get!d() : MyStruct(),
n.has!e() ? n.get!e() : new MyClass()
);
}
and then call it
foo(named!c,b,e(Foo, 0, new MyClass()));
With some more work we could also allow
foo(named!c(Foo), named!b(0), named!e(new MyClass()));
All this can be handled by a templated Wrapper-Object that is created
by named()(). When doing the code generation of the wrapper object via
a mixin, we could also allow ref parameters (with named!ref
e(my_class) and by storing a pointer).
Of course, the code for the wrapper can be inlined because the
presence of every parameter can be decided at compile time.
Any ideas?
Best regards,
Matthias
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
iQEcBAEBAgAGBQJPM5SOAAoJEPdcuJbq5/sRr/MIAL0tJBGWdkhrPUbaS5gqb9ho
jkyKW8u+akVMnlTW4BKQ7lHSkJBySZxn4Ty/zIJEmqoIHrlsI308z26miSy5bDeK
XcNAx1M+3wUuvYPoJpg3nlARofez9R0n1opfS6DnDYHGYLZH9AK924bwKyChFfP9
a/6mEyPHsMem/+2CWIWJjsLzEBkc+OacgCmzj7dGZfoJBhmF/EjxZgdwYpnA8q3N
KYIl28gqyf+JBkmdzVhhDuBMUb1PlqqqnbXS66EaYcQIA7bUESPc8dKJKIQTKVy3
Lq5MSg8BuvMdnIXYVn0HK4R2LWTshZn5kXkfy7EX8Xw4yyT4e6VIkcwDOyy8iMQ=
=T4UD
-END PGP SIGNATURE-
Mixture of type tuple and expression tuple
Hi, I'd like to have a function foo which shall depend on several compile-time expressions (e.g. strings) and gets several arguments whose types are templatized. Here, several means in both cases that the number of expressions/arguments are to be determined at compile-time. Here is an example: foo!(a, b, c)(42, new MyClass(), 7.0); At compile-time, some template parameters (strings a, b and c) shall be given explicitly and some more template parameters (types of arguments int, MyClass, double) shall be deduced from the function arguments. Is that possible? Of course, I cannot setup two TemplateTupleParameters. Best regards, Matthias
dup method const or not?
Hi, Recently, I realized that several dup methods in D2's phobos are declared like the one for BitArray: @property BitArray dup() My question is why it is declared without const? Is it a bug or is there a reason for it? I can think of a case where one only has implemented a shallow copy and wants to omit the const due to the involved transitivity, but this shouldn't be the case for BitArray (the underlying array is dup'ed). Is there a general rule/recommendation when to make a dup method const and when not? My problem arises in a copy constructor for a struct S which takes a const(S) instance. But as S has a BitArray member, duping is not allowed, so I need a way to duplicate a const(BitArray) object. Matthias
Re: dup method const or not?
On 2011-11-27 23:48, mta`chrono wrote:
that's a real good question. it fails with the following error:
Error: function std.bitmanip.BitArray.dup () is not callable using
argument types () const
here is a hack:
---
import std.bitmanip;
import core.stdc.string;
void main()
{
const(BitArray) foo;
BitArray bar;
memcpy(bar, foo, BitArray.sizeof);
}
Well, this hack doesn't even work - as it does a shallow copy only,
immediately setting bits of bar also changes bits of foo!
Matthias
Stable sort in std.algorithm throws Range violation
Hi,
when using the most recent D2/32bit version from github of
dmd+druntime+phobos I get a Range violation from the following code:
| import std.algorithm;
|
| void main(char[][] args)
| {
| sort!(a b, SwapStrategy.stable)([1,0, 3, 2]);
| }
Can anybody confirm this? Shall I file a bug?
best regards,
Matthias Walter
Re: greatest common divisor implementation
1. Are there any further suggestions on the implementations / Did I forget something? Are benchmarks done with BigInt and long too? (If you test bigints you need bigger numbers too, and to test that the results are correct). Yeah, so I did tests for long now, too. Unfortunately with gdc I was unable to generate uniform long numbers (UniformIntGenerator.popFront not implemented for large ranges). Interestingly, with DMD it works... The dmd-only results of long as type, with random long values: SimpleRecursive!(long): 0.134 SimpleIterative!(long): 0.127 BinaryRecursive!(long): 1.727 BinaryIterative!(long): 0.345 BoostIterative!(long): 0.136 BoostBinary!(long): 0.575 gcdSteinTable!(long, 1): 0.594 gcdSteinTable!(long, 2): 0.527 gcdSteinTable!(long, 3): 0.489 gcdSteinTable!(long, 4): 0.536 gcdSteinTable!(long, 5): 0.489 gcdSteinTable!(long, 6): 0.531 gcdSteinTable!(long, 7): 0.498 gcdSteinTable!(long, 8): 0.542 gcdSteinTable!(long, 9): 0.491 gcdSteinTable!(long,10): 0.539 gcdSteinTable!(long,11): 0.494 gcdSteinTable!(long,12): 0.538 The results for dmd and gdc with long as type, but random int values: SimpleRecursive!(long): 0.110 0.143 SimpleIterative!(long): 0.100 0.136 BinaryRecursive!(long): 0.661 0.208 BinaryIterative!(long): 0.166 0.133 BoostIterative!(long): 0.104 0.142 BoostBinary!(long): 0.277 0.174 gcdSteinTable!(long, 1): 0.275 0.134 gcdSteinTable!(long, 2): 0.259 0.130 gcdSteinTable!(long, 3): 0.249 0.108 gcdSteinTable!(long, 4): 0.253 0.095 gcdSteinTable!(long, 5): 0.243 0.089 gcdSteinTable!(long, 6): 0.243 0.086 gcdSteinTable!(long, 7): 0.245 0.084 gcdSteinTable!(long, 8): 0.245 0.082 gcdSteinTable!(long, 9): 0.246 0.081 gcdSteinTable!(long,10): 0.245 0.081 gcdSteinTable!(long,11): 0.246 0.080 gcdSteinTable!(long,12): 0.250 0.081 2. What do you think, we should finally use? It seems more complex algorithms don't pay much for int values. I agree on that and suggest to take Boost's implementation which is very readable, too. I will probably do some tests with BigInt, too. But I suspect that the result looks totally different which means that we'll use different specializations. The same holds true for the extended algorithm. @Andrei: As soon as I'm done, I'll submit a pull request to github. Matthias
Re: greatest common divisor implementation
1. Are there any further suggestions on the implementations / Did I forget something? Are benchmarks done with BigInt and long too? (If you test bigints you need bigger numbers too, and to test that the results are correct). I'd like to work on the BigInt things but there are a couple of blockers: 1. abs() does not work, because opCmp for BigInts is not pure, yet. IIRC Don waits / waited for a pure/nothrow bug to be fixed before he'd continue working on BigInt purity, etc. 2. I don't think the current random number implementation has code to generate BigInts easily via uniform() method. There was a fixed number of bits that are used per call. So I suggest to work on the Extended Euclidean algorithm implementations and get results for int/long for those. If this is done I'll submit a pull request with nice code for int+long and code for BigInt that just works but is not benchmarked. Then we should change the gcd bug to BigInt-only (or open another one...) Matthias
Re: greatest common divisor implementation
On 02/07/2011 05:13 PM, Andrei Alexandrescu wrote: On 2/7/11 3:18 PM, Matthias Walter wrote: Hi everyone, as I'm currently working on a C++ project which involves gcd computations I had a quick look at phobos' implementation. 1. First thing I saw is that gcd(-3,6) raises an exception, although mathematically it is just 2. Of course checking the sign of the arguments takes computation time, but for my stuff I'd definitely need it. If it's really too expensive then there should be at least another routine. 2. I'd be happy to implement the Extended Euclidean algorithm for phobos which also gives multipliers s and t such that gcd(x,y) = s*x + t*y. Any comments before I start working on it? Matthias Please do. I implemented gcd in a hurry because I needed it for unsigned numbers, so it's not the greatest it could be. A github pull request would be much appreciated! I re-implemented [1] several things like recursive / iterative or modulo / binary implementations. For the latter I found one with a lookup-table that pre-computes partial results. The testbed generated a sequence of 1 int pairs, computing the gcd of a pair of ints and adding the sum of all (as checksum and to avoid removal by the compiler). This was repeated 100 times using the same sequence. Time is per gcd call and given in nanoseconds. First column: dmd -O -release -inline Second column: gdc -O3 SimpleRecursive:0.096 0.086 SimpleIterative:0.090 0.083 BinaryRecursive:0.240 0.213 BinaryIterative:0.141 0.133 BoostIterative: 0.087 0.085 BoostBinary:0.219 0.177 gcdSteinTable!(int, 1): 0.161 0.136 gcdSteinTable!(int, 2): 0.133 0.130 gcdSteinTable!(int, 3): 0.107 0.108 gcdSteinTable!(int, 4): 0.093 0.094 gcdSteinTable!(int, 5): 0.089 0.088 gcdSteinTable!(int, 6): 0.087 0.083 gcdSteinTable!(int, 7): 0.086 0.081 gcdSteinTable!(int, 8): 0.085 0.081 gcdSteinTable!(int, 9): 0.085 0.082 gcdSteinTable!(int,10): 0.085 0.080 gcdSteinTable!(int,11): 0.086 0.082 gcdSteinTable!(int,12): 0.086 0.080 Remark: The 2nd template parameter of the gcdSteinTable implementation means the number of bits for the lookup-table. It therefore uses 2^bits bytes of memory! 1. Are there any further suggestions on the implementations / Did I forget something? 2. What do you think, we should finally use? 3. I will also implement the extended gcd (i.e. having gcd(a, b) = z = x * a + y * b we are interested in x,y,z) Matthias [1] http://pastebin.com/sXpsdK5S
greatest common divisor implementation
Hi everyone, as I'm currently working on a C++ project which involves gcd computations I had a quick look at phobos' implementation. 1. First thing I saw is that gcd(-3,6) raises an exception, although mathematically it is just 2. Of course checking the sign of the arguments takes computation time, but for my stuff I'd definitely need it. If it's really too expensive then there should be at least another routine. 2. I'd be happy to implement the Extended Euclidean algorithm for phobos which also gives multipliers s and t such that gcd(x,y) = s*x + t*y. Any comments before I start working on it? Matthias
Re: On 80 columns should (not) be enough for everyone
On 01/30/2011 01:01 PM, Peter Alexander wrote: On 30/01/11 5:17 PM, Andrej Mitrovic wrote: The unittest topic is about to get derailed so I want to continue this silly discussion here. Wheres Nick? I want to see the CRT vs LCD discussion heated up again with Andrei claiming that LCDs are so Godlike but yet claims 80 columns is enough for everyone. 80 colums is an artifact of the old age. Just like the preprocessor is an artifact of the C language. And many other old things are artifacts. There's no reason to keep these artifacts around anymore. snip Is this really worth arguing about? Just stick to 80 columns. It's not a big deal. One argument that I can think of is to at least raise the number of allowed columns. Why? Well, phobos' names like tr will be (or are) refactored to translate and with camelcase we encourage people to use descriptive names. And with template parameters and everything I do not want to call functions, putting 1 argument on every line. I'd suggest raising it to 120 or 150...
Re: structs vs classes
On 01/29/2011 09:13 AM, Jim wrote:
so Wrote:
I'm a bit troubled with the class/struct dichotomy. I would prefer them
both to use the same keyword. Heap/stack allocation could be specified
during instantiation instead. Why? Now you need to choose one over the
other. Not even C++ has this limitation.
This keeps coming and i have no idea how people think C++ treatment is any
way good.
You are free to call the D design of struct/class the worst possible, but
at least don't base your reasoning to C++ please.
C++: both class and struct are exactly same, except one trivial:
struct A : B {
};
means:
class A : public B {
public:
};
In D they are quite different and they have different keywords.
http://www.digitalmars.com/d/2.0/class.html
http://www.digitalmars.com/d/2.0/struct.html
I'm only discussing the heap/stack difference.
That is of course a difference, but no argument. The reason is that you
can decide whether you want to allocate a class on the stack:
http://www.digitalmars.com/d/2.0/memory.html#stackclass
Matthias
Re: thin heaps
On 12/20/2010 05:01 PM, Andrei Alexandrescu wrote: Just saw this: http://www.reddit.com/r/programming/comments/eoq15/implementing_shortest_path_in_c_is_much_easier/ in which a reader points to this paper on thin heaps: http://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/thin%20heap.pdf Does anyone here have experience with thin heaps? I think they'd be a good addition to std.container. You might have realized my recent interest in std.container.BinHeap as a priority queue. In fact I thought about implementing Fibonacci Heaps with the same interface for D. I worked on a C++ implementation a while ago, so maybe I should give the Thin Heaps a try? Matthias
Re: Binary heap method to update an entry.
On 12/16/2010 04:17 AM, Andrei Alexandrescu wrote: On 12/15/10 10:21 PM, Matthias Walter wrote: Hi all, I uploaded [1] a patch for std.container to use BinaryHeap as a priority queue. For the latter one it is often necessary to change a value (often called decreaseKey in a MinHeap). For example, Dijkstra's shortest path algorithm would need such a method. My implementation expects that the user calls the update method after changing the entry in the underlying store. My method works for value-decrease and -increase, but one might want to split this functionality into two methods for efficiency reasons. But I thought it'll be better, because one can change the MaxHeap to be a MaxHeap by changing the template alias parameter, but this wouldn't change the method names :-) The patch is against current svn trunk. [1] http://xammy.xammy.homelinux.net/files/BinaryHeap-PriorityQueue.patch A better primitive is to define update to take an index and a new value, such that user code does not need to deal simultaneously with the underlying array and the heap. No? Well, I thought of the case where you have an array of structs and use a custom less function for ordering. There you might not have a new value, i.e. a replaced struct, but just a minor change internally. But I see your idea, in most cases you would just call update after replacing your array entry... Could we provide both, maybe? Matthias Walter
Re: Binary heap method to update an entry.
On 12/16/2010 10:53 AM, Andrei Alexandrescu wrote: On 12/16/10 7:55 AM, Matthias Walter wrote: On 12/16/2010 04:17 AM, Andrei Alexandrescu wrote: On 12/15/10 10:21 PM, Matthias Walter wrote: Hi all, I uploaded [1] a patch for std.container to use BinaryHeap as a priority queue. For the latter one it is often necessary to change a value (often called decreaseKey in a MinHeap). For example, Dijkstra's shortest path algorithm would need such a method. My implementation expects that the user calls the update method after changing the entry in the underlying store. My method works for value-decrease and -increase, but one might want to split this functionality into two methods for efficiency reasons. But I thought it'll be better, because one can change the MaxHeap to be a MaxHeap by changing the template alias parameter, but this wouldn't change the method names :-) The patch is against current svn trunk. [1] http://xammy.xammy.homelinux.net/files/BinaryHeap-PriorityQueue.patch A better primitive is to define update to take an index and a new value, such that user code does not need to deal simultaneously with the underlying array and the heap. No? Well, I thought of the case where you have an array of structs and use a custom less function for ordering. There you might not have a new value, i.e. a replaced struct, but just a minor change internally. But I see your idea, in most cases you would just call update after replacing your array entry... Could we provide both, maybe? Good point. Here's what I suggest: /** Applies unary function fun to the element at position index, after which moves that element to preserve the heap property. (It is assumed that fun changes the element.) Returns the new position of the element in the heap. Example: int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ]; auto h = heapify(a); assert(equal(a, [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ])); h.update!a -= 5(1); assert(equal(a, [ 16, 10, 9, 9, 8, 7, 4, 3, 2, 1 ])); */ size_t update(alias fun)(size_t index); Let me know of what you think, and thanks for contributing. When using unaryFun inside update, don't forget to pass true as the second argument to unaryFun to make sure you enact pass by reference. Good idea. I like the interface! Btw, can I then call a routine in the string, too? Like h.update!a.updatePriority()(1); Although this does look ugly, so separating the call would probably make more sense. Matthias
Re: (Improved) Benchmark for Phobos Sort Algorithm
On 12/16/2010 09:36 PM, Craig Black wrote: It was brought to my attention that the quick sort has a very bad worst case, so I implemented a simple fix for it. Now the worst case (completely ordered) is the best case, and it only slows down the general case by a small percentage. I thought to myself, it can't be this easy to fix quick sort. Does anyone see a flaw in this simple fix? Performs much better than Phobos in completely random and completely sorted data. Perhaps there is another case where it doesn't do as well? Yes, there is a flaw: There are still instances of arrays where you will end up with a pivot element being one of the largest or one of the smallest elements in *every* call. The means, that you split your array from length n not into two arrays roughly of size n/2 and n/2, but of O(1) and n - O(1). This implies a running time of n^2 (in contrast to n log n), which is obviously bad. I don't know how std.algorithm.sort works, but C++ STL uses an Introspective sort, which is a quick-sort variant like you have, but it has some measurements that observe whether the above worst case occurs (e.g. by looking at the recursion depth) and switches to a heap-sort in this case. [1] Matthias [1] http://en.wikipedia.org/wiki/Introsort
Binary heap method to update an entry.
Hi all, I uploaded [1] a patch for std.container to use BinaryHeap as a priority queue. For the latter one it is often necessary to change a value (often called decreaseKey in a MinHeap). For example, Dijkstra's shortest path algorithm would need such a method. My implementation expects that the user calls the update method after changing the entry in the underlying store. My method works for value-decrease and -increase, but one might want to split this functionality into two methods for efficiency reasons. But I thought it'll be better, because one can change the MaxHeap to be a MaxHeap by changing the template alias parameter, but this wouldn't change the method names :-) The patch is against current svn trunk. [1] http://xammy.xammy.homelinux.net/files/BinaryHeap-PriorityQueue.patch
BinaryHeap usage
Hi all, suppose I have an array of comparable Foo structs which I want to access in a sorted order (e.g. a priority queue) using a BinaryHeap object (I know that for just sorting, the BinHeap is not the right tools), but I do not want to change the order of the objects in the original array. I have two ideas on how to do this and just want to know whether they are the right way: a) Have an array of Foo*, initialize it from the original and instantiate the BinaryHeap with a Comparision-predicate that dereferences first. b) Have an array of indices that are indicies in the original array (like a permutation in a permutation group) and access the corresponding index of the original array for comparison. Any further ideas for this problem, or did I cover everything already? Matthias
Re: Casting functions to delegates
On 12/12/2010 06:15 AM, Dmitry Olshansky wrote:
On 12.12.2010 7:25, Matthias Walter wrote:
Hi all,
there was a discussion in 2006 but w/o a result, and I didn't find any
bugs about implicitely casting functions to delegates. It seems to be
impossible as long as function-pointer calls work differently than
delegate calls in the ABI. Will this at some point be fixed?
If not, is there a conversion function in phobos (I didn't find one)? I
played a bit and found that this one might work:
R delegate(A) funcionToDelegate (R, A...) (R function(A) func)
{
return (A a){ return func(a); };
}
Matthias
There is actually almost forgotten function in std.functional -
toDelegate, which does it in the most general way, functional objects
covered.
Sadly enough it's not listed in docs, because of the auto return.
Ah, thank you very much! That looks like what I was looking for.
Re: ByToken Range
On 12/12/2010 02:04 AM, Christopher Nicholson-Sauls wrote: On 12/11/10 22:41, Matthias Walter wrote: Hi all, I wrote a ByToken tokenizer that models Range, i.e. it can be used in a foreach loop to read from a std.stdio.File. For it to work one has to supply it with a delegate, taking a current buffer and a controller class instance. It is called to extract a token from the unprocessed part of the buffer, but can act as follows (by calling methods from the controller class): - It can skip some bytes. - It can succeed, by eating some bytes and setting the token to be read by the front() property. - It can request more data. - It can indicate that the data is invalid, in which case further processing is stopped and a user-supplied delegate is invoked that may or may not handle this failure. It is efficient, because it reuses the same buffer every time and just supplies the user with a slice of unprocessed data. If more data is requested, the remaining unprocessed part is copied to the beginning and more data is read. If there is no such unprocessed data, the buffer is enlarged, i.e. length doubled. The ByToken class has the type of a token as a template parameter. Does this behavior make sense? Any further suggestions? Is there any interest in having this functionality, i.e. should I create a dsource project, or does everybody use parser-generators for everything? Matthias I write lexers/parsers relatively often -- and I don't use generators... because I'm masochistic like that! And because there aren't many options for D. There was Enki for D1 a while back, which might still work pretty well, and there's GOLD although I'm not aware of how their D support is right now. I might be forgetting another. So I, for one, like the idea of it at the very least. I'd have to see it in action, though, to say much beyond that. My current version can be used as follows to yield a simple word-tokenizer: http://pastebin.com/qjH6y0Mf As I'm going to use it for one or two real-world file formats I might change some things, but for now I like it. If you have any suggestions for improvements, please let me know. Matthias
Casting functions to delegates
Hi all,
there was a discussion in 2006 but w/o a result, and I didn't find any
bugs about implicitely casting functions to delegates. It seems to be
impossible as long as function-pointer calls work differently than
delegate calls in the ABI. Will this at some point be fixed?
If not, is there a conversion function in phobos (I didn't find one)? I
played a bit and found that this one might work:
R delegate(A) funcionToDelegate (R, A...) (R function(A) func)
{
return (A a){ return func(a); };
}
Matthias
ByToken Range
Hi all, I wrote a ByToken tokenizer that models Range, i.e. it can be used in a foreach loop to read from a std.stdio.File. For it to work one has to supply it with a delegate, taking a current buffer and a controller class instance. It is called to extract a token from the unprocessed part of the buffer, but can act as follows (by calling methods from the controller class): - It can skip some bytes. - It can succeed, by eating some bytes and setting the token to be read by the front() property. - It can request more data. - It can indicate that the data is invalid, in which case further processing is stopped and a user-supplied delegate is invoked that may or may not handle this failure. It is efficient, because it reuses the same buffer every time and just supplies the user with a slice of unprocessed data. If more data is requested, the remaining unprocessed part is copied to the beginning and more data is read. If there is no such unprocessed data, the buffer is enlarged, i.e. length doubled. The ByToken class has the type of a token as a template parameter. Does this behavior make sense? Any further suggestions? Is there any interest in having this functionality, i.e. should I create a dsource project, or does everybody use parser-generators for everything? Matthias
Re: D2 byChunk
On 12/11/2010 01:00 AM, Christopher Nicholson-Sauls wrote:
On 12/10/10 22:36, Matthias Walter wrote:
On 12/10/2010 09:57 PM, Matthias Walter wrote:
Hi all,
I currently work on a parser for some file format. I wanted to use the
std.stdio.ByChunk Range to read from a file and extract tokens from the
chunks. Obviously it can happen that the current chunk ends before a
token can be extracted, in which case I can ask for the next chunk from
the Range. In order to keep the already-read part in mind, I need to dup
at least the unprocessed part of the older chunk and concatenate it in
front of the next part or at least write the code that works like they
were concatenated. This looks like a stupid approach to me.
Here is a small example:
file contents: Hello world
chunks: Hello w orld
First I read the token Hello from the first chunk and maybe skip the
whitespace. Then I have the w (which I need to move away from the
buffer, because ByChunk fill overwrite it) and get orld.
My idea was to have a ByChunk-related Object, which the user can tell
how much of the buffer he/she actually used, such that it can move this
data to the beginning of the buffer and append the next chunk. This
wouldn't need further allocations and give the user contiguous data
he/she can work with.
I coded something that works like this:
foreach (ref ubyte[] data; byBuffer(file, 12))
{
writefln([%s], cast(string) data);
data = data[$-2 .. $];
}
The 2nd line in the loop tells ByBuffer that we didn't process the last
two chars and would like to get them again along with newly read data.
And as long as we do process something, the internal buffer does not get
reallocated.
It works and respects the formal requirements of ranges. Whether it
respects the intended semantics, one can discuss about. Any comments
whether the above things make sense or is an evil exploit of the
provided syntax sugar?
I don't think it's a bad approach, but I have a suggestion.
It leaves a lot of room for abuse or misuse if you require the user code
to modify the data[] array in order to send this protect some
characters message. I think it would be better to provide an explicit
function/method that means precisely that. Maybe return a transparent
struct wrapping a view to the buffer's data, that further provides a
function for doing precisely this.
foreach( data; byBuffer( file, 12 )) {
// do things with data, decide we need to keep 2 chars
data.save( 2 );
}
Or something like it. With regards to this, you may want to allow the
internal buffer to grow (if you aren't already) as needed. Imagine what
would otherwise happen if you needed to 'save' the entire current buffer.
-- Chris N-S
Thank you! This is a really good idea. So I basically wrap the
buffer-array and implement it such that the default behavior (without
explicitely doing something) is like the ByChunk mechanism.
Matthias
Re: setting array dimensions at runtime
The only thing I've been able to think of is
byte[][] a;
a.length = size;
for (int i; i size; i++) {
a[i].length = size;
}
Well, you can do at least:
auto a = new byte[][size];
foreach (ref row; a)
row = new byte[size];
Matthias
Re: bigint
On 11/27/2010 02:05 PM, bearophile wrote: Reduced case for bugzilla: http://d.puremagic.com/issues/show_bug.cgi?id=5281 I investigated into the bug and the reason is the signature of opEquals, which currently is bool opEquals(Tdummy=void)(ref const BigInt y) const bool opEquals(T: int)(T y) const The only working sigature for array-of-structs-comparison to work is bool opEquals(ref const BigInt y) const But this removes the ability to compare against ints. (btw, it should probably be long in the 2nd signature?!) array-comparison should definitely take templated opEquals functions into account, or is there something mentioned in the spec? Matthias
Re: value range propagation for %
On 11/27/2010 12:54 PM, Ellery Newcomer wrote: Hello. Today I've been thinking about calculating the range of values for x % y You might want to state the problem more precisely. What exactly is a range of values x % y ? Do you look at the result for x,y in some sets? Or is either x or y fixed? From your example I would suppose that x shall be fixed and y goes through a range?! Matthias
Re: Basic coding style
On 11/23/2010 12:12 AM, Jonathan M Davis wrote: On Monday 22 November 2010 21:03:27 Walter Bright wrote: Matthias Walter wrote: What about adding a compiler switch that one can turn on and that warns on obviously wrong names? Is this realistic? At least to check the usage of underscores and captial first letter. The CamelCase can probably not be verified, but hopefully a lot of programmers will use it, if the compiler encourages them to not use underscores... Just an idea, you can flame on, if you like. If you want, it would be easy to write a simple program that read the .json output of the compiler, and then enforce any naming convention you need. That could be a useful tool. And I do think that a basic set of typical D naming conventions and the like could be useful. But I don't really think that it makes sense to have the compiler itself enforcing style. That sort of thing definitely belongcs in external tools. So we should talk to the IDE designers, s.t. they include this into their list of planned features. I recommend a 3-minute alarm sound per badly named variable/function :) Matthias
Re: Basic coding style
On 11/22/2010 06:21 PM, JimBob wrote: bearophile bearophileh...@lycos.com wrote in message news:icdnn4$2cn...@digitalmars.com... I have four or five times tried to explain why coding standards are important for the development of the D community And them there stupid people just wont listen to ya. Thats mighty unreasonable of them, you being president of the world an all. Come on guys, please don't flame here... I don't like to force anybody in using a style they maybe don't like. But on the other hand I think bearophile's arguments have some truth in them. What about adding a compiler switch that one can turn on and that warns on obviously wrong names? Is this realistic? At least to check the usage of underscores and captial first letter. The CamelCase can probably not be verified, but hopefully a lot of programmers will use it, if the compiler encourages them to not use underscores... Just an idea, you can flame on, if you like. Matthias
Re: Repairing BigInt const
On 11/21/2010 04:33 PM, Don wrote: Matthias Walter wrote: as it seems, the current version of BigInt is not capable of const, i.e. BigInt(1) + const(BigInt)(1) does not work. Is there already an effort to fix this or would it make sense if I had taken some time to create a fix for it? I have no idea of all the asm in the x86 specialization but as const is an interface thing, I should be able to figure out everything without that knowledge. Or are there general design problems, such that this would be a waste of time? It's been prevented by some compiler bugs. The changes to pure in 2.050 were triggered by attempts to make BigInt pure. 2.051 will include several fixes to nothrow. You mean by making BigInt pure that all the computation-methods (like opBinary, etc.) will be pure, right? Or can D structs be pure as well? (Whatever this would mean...) Note that const is transitive (unlike C++), so it isn't just an interface thing. That's clear. For +, I succeeded in making it const, but of course I had to modify the biguintcore module, too. So I guess that you will work on BigInt when 2.051 is out and patch it to work with const and immutable, right? So I have a good chance to have a fixed version in the next month(s)?!
Repairing BigInt const
Hi all, as it seems, the current version of BigInt is not capable of const, i.e. BigInt(1) + const(BigInt)(1) does not work. Is there already an effort to fix this or would it make sense if I had taken some time to create a fix for it? I have no idea of all the asm in the x86 specialization but as const is an interface thing, I should be able to figure out everything without that knowledge. Or are there general design problems, such that this would be a waste of time? Matthias
Current status of toString in phobos
Hi, I'm currently using DMD v2.049 with phobos. I found an old discussion about how toString should be designed and how it is supposed to work. As the following code does not print out the number, I wonder what is the current status of how to implement a toString function for a struct/class: | auto n = BigInt(42); | writefln(%s, n); Thanks Matthias
Re: A module comprehensive template-specialization
On 06/28/2010 05:32 AM, Simen kjaeraas wrote:
Matthias Walter xa...@xammy.homelinux.net wrote:
Can I handle this in another way (like making the template a conditional
one)?
Template constraints[1] sounds like what you want.
Basically, you want the following:
== Module a ==
| module a;
|
| template Base (T) if (!is(T t : t*))
| {
| alias T Base;
| }
== Module b ==
| module b;
|
| import a;
|
| template Base(T) if (is(T t : t*))
| {
| alias Base !(T) Base;
| }
== Main module ==
|
| import a, b;
|
| int main(char[][] args)
| {
| alias Base !(int*) foo;
|
| return 0;
| }
Not tested, ymmv.
[1]: http://digitalmars.com/d/2.0/template.html#Constraint
The problem with constraints arises when I want to make an existing
class (who's code I cannot modify) match a Concept, in which case I
would just add another template specialization for this class. Here I
would have to add further conditions to the template constraints, which
would also mean to modify a library. A prominent example for Boost Graph
Library is the LEDA graph class, which can be enabled to be used by BGL
by more or less just specializing the graph_traits template.
Any further ideas?
Re: A module comprehensive template-specialization
On 06/28/2010 09:49 AM, Justin Spahr-Summers wrote:
On Sun, 27 Jun 2010 18:51:35 +0200, Matthias Walter
xa...@xammy.homelinux.net wrote:
Hi list,
I tried to write a traits class comparable to iterator_traits in C++ STL
or graph_traits in Boost Graph Library in D 2.0, but failed to do so via
template specialization which is put into different modules. Putting
everything into one module interferes with extensibility. I tried the
following:
== Module a ==
| module a;
|
| template Base (T)
| {
| alias T Base;
| }
== Module b ==
| module b;
|
| import a;
|
| template Base(T: T*)
| {
| alias Base !(T) Base;
| }
== Main module ==
|
| import a, b;
|
| int main(char[][] args)
| {
| alias Base !(int*) foo;
|
| return 0;
| }
The error message is:
bug.d(8): Error: template instance ambiguous template declaration
b.Base(T : T*) and a.Base(T)
Can I handle this in another way (like making the template a conditional
one)?
best regards
Matthias Walter
I believe this is intended behavior, as it prevents template hijacking
and the like. Using alias to import the two templates into the same
scope might help, though I'm not sure exactly how it should be done.
I tried to do so in some variants but did not succeed unfortunately. If
you have a precise idea, please let me know!
On another note, though, have you looked at __traits() and std.traits?
I looked at them but didn't find them helpful for this precise problem.
The whole reason for doing this is to make it possible to make another
existing class model the concept (i.e. have some aliases / typedefs
done) of my library class without editing any of them. As I mentioned in
my other response, a prominent example for Boost Graph
Library is the LEDA graph class, which can be enabled to be used by BGL
by more or less just specializing the graph_traits template. I'd like to
have this kind of technique available, too.
Any further suggestions?
A module comprehensive template-specialization
Hi list,
I tried to write a traits class comparable to iterator_traits in C++ STL
or graph_traits in Boost Graph Library in D 2.0, but failed to do so via
template specialization which is put into different modules. Putting
everything into one module interferes with extensibility. I tried the
following:
== Module a ==
| module a;
|
| template Base (T)
| {
| alias T Base;
| }
== Module b ==
| module b;
|
| import a;
|
| template Base(T: T*)
| {
| alias Base !(T) Base;
| }
== Main module ==
|
| import a, b;
|
| int main(char[][] args)
| {
| alias Base !(int*) foo;
|
| return 0;
| }
The error message is:
bug.d(8): Error: template instance ambiguous template declaration
b.Base(T : T*) and a.Base(T)
Can I handle this in another way (like making the template a conditional
one)?
best regards
Matthias Walter
