Re: Sorted Array (Container) Type
On Tuesday, 15 November 2022 at 23:27:07 UTC, Siarhei Siamashka
wrote:
For doing a fast insert into an already sorted array (and
avoiding duplicated values) it's probably better to do
something like this:
```D
bool fast_insert_into_a_sorted_array(alias less = "a < b",
T)(ref T[] a, T value)
{
auto pos = a.assumeSorted!(less).lowerBound(value).length;
if (pos < a.length && a[pos] == value)
return false; // indicate no insert
a.insertInPlace(pos, value);
return true; // indicate insert
}
```
Actually the comparison needs to be done using the provided
predicate too:
```D
bool fast_insert_in_a_sorted_array(alias less = "a < b", T)(ref
T[] a, T value)
{
auto pos = a.assumeSorted!(less).lowerBound(value).length;
while (pos < a.length && !binaryFun!less(a[pos], value) &&
!binaryFun!less(value, a[pos])) {
if (a[pos++] == value)
return false; // indicate no insert
}
a.insertInPlace(pos, value);
return true; // indicate insert
}
unittest {
auto less = function bool(ref Tuple!(int, int) a,
ref Tuple!(int, int) b) { return a[0]
< b[0]; };
auto a = [tuple(0, 1), tuple(0, 2)];
a.sort!less;
assert(a.fast_insert_in_a_sorted_array!less(tuple(0, 2)) ==
false);
assert(a == [tuple(0, 1), tuple(0, 2)]);
assert(a.fast_insert_in_a_sorted_array!less(tuple(0, 3)) ==
true);
assert(a == [tuple(0, 1), tuple(0, 2), tuple(0, 3)]);
assert(a.fast_insert_in_a_sorted_array!less(tuple(-1, 0)) ==
true);
assert(a == [tuple(-1, 0), tuple(0, 1), tuple(0, 2), tuple(0,
3)]);
}
```
Re: Sorted Array (Container) Type
On Tuesday, 15 November 2022 at 20:09:40 UTC, Per Nordlöw wrote:
I wanted a sorted array because I want to include it in a
benchmark suite and study it's time and space complexity. No
application yet.
For doing a fast insert into an already sorted array (and
avoiding duplicated values) it's probably better to do something
like this:
```D
bool fast_insert_into_a_sorted_array(alias less = "a < b", T)(ref
T[] a, T value)
{
auto pos = a.assumeSorted!(less).lowerBound(value).length;
if (pos < a.length && a[pos] == value)
return false; // indicate no insert
a.insertInPlace(pos, value);
return true; // indicate insert
}
```
Re: Sorted Array (Container) Type
On Tuesday, 15 November 2022 at 22:32:56 UTC, Per Nordlöw wrote: Still, does anybody understand why the line https://github.com/nordlow/phobos-next/blob/master/src/nxt/sorted.d#L52 fails to compile Maybe add two typeof arguments? ```D completeSort!(less, ss, typeof(_source), typeof(_raw))(_source[0 .. n], _raw[n .. $]); ```
Re: Sorted Array (Container) Type
On Tuesday, 15 November 2022 at 22:15:36 UTC, Per Nordlöw wrote:
On Tuesday, 15 November 2022 at 21:03:24 UTC, Per Nordlöw wrote:
This is what I have so far.
Found some issues but still cannot instantiate my solution at
https://github.com/nordlow/phobos-next/blob/master/src/nxt/sorted.d#L15
when I uncomment the line containing
```d
// TODO: completeSort!(less, ss)(_source[0 ..
n].assumeSorted!(less), _source[n .. $]);
```
I made an adjustment to make better use of existing member
functions of SortedRange.
Still, does anybody understand why the line
https://github.com/nordlow/phobos-next/blob/master/src/nxt/sorted.d#L52 fails to compile as
```sorted.d(52): Error: none of the overloads of template
`std.algorithm.sorting.completeSort` are callable using argument
types `!("a < b", SwapStrategy.unstable)(SortedRange!(int[], "a <
b", SortedRangeOptions.assumeSorted), int[])`
/home/per/.local/dlang/linux/bin64/src/phobos/std/algorithm/sorting.d(117):Candidate
is: `completeSort(alias less = "a < b", SwapStrategy ss =
SwapStrategy.unstable, Lhs, Rhs)(SortedRange!(Lhs, less) lhs, Rhs rhs)`
sorted.d(74): Error: template instance `nxt.sorted.Sorted!(int[],
"a < b", SwapStrategy.unstable).Sorted.insert!int` error
instantiating```
Re: Sorted Array (Container) Type
On Tuesday, 15 November 2022 at 21:03:24 UTC, Per Nordlöw wrote: This is what I have so far. Found some issues but still cannot instantiate my solution at https://github.com/nordlow/phobos-next/blob/master/src/nxt/sorted.d#L15 when I uncomment the line containing ```d // TODO: completeSort!(less, ss)(_source[0 .. n].assumeSorted!(less), _source[n .. $]); ```
Re: Sorted Array (Container) Type
This is what I have so far.
```d
import std.algorithm.mutation : SwapStrategy;
/** Wrapper container around array (slice) or array-like
(container) `A`.
*
* See_Also: https://en.wikipedia.org/wiki/Sorted_array
*/
struct Sorted(A, alias less = "a < b", SwapStrategy ss =
SwapStrategy.unstable)
if (is(A == U[], U) || // isDynamicArray
__traits(isStaticArray, A))
{
private alias E = typeof(A.init[0]);
this(A source)
{
_source = source[];
import std.algorithm.sorting : sort;
sort!(less, ss)(_source[]);
}
auto opSlice() return scope => _source[];
static if (is(A == U[], U)) // isDynamicArray
bool insert(in E x) scope @trusted // TODO: @safe
{
import std.algorithm.sorting : completeSort;
foreach (ref e; _source)
if (e == x)
return false; // indicate no insert
const n = _source.length;
_source.reserve(n + 1); // TODO: use template parameter
`Growth`
_source.length += 1;
_source[n] = x;
// TODO: enable:
version(none) completeSort!(less, ss)(_source[0 .. n],
_source[n .. $]); // this fails
return true;// indicate insert
}
bool contains(in E x) const
{
foreach (ref e; _source)
if (e == x)
return true;
return false;
}
private A _source;
}
/// constructor from dynamic array
@safe pure nothrow unittest
{
scope int[] x = [3,2,1];
alias A = typeof(x);
auto sx = Sorted!(A)(x);
assert(sx[] == [1,2,3]);
assert(sx[].isSorted);
assert(!sx.insert(3));
// assert(sx.insert(4));
}
/// constructor from static array
@safe pure nothrow @nogc unittest
{
int[3] x = [3,2,1];
alias A = typeof(x);
auto sx = Sorted!(A)(x);
assert(sx[].isSorted);
}
version(unittest)
{
import std.algorithm.sorting : isSorted;
}
```
. But I don't understand why my call to completeSort isn't
allowed by the compiler and errors as
```
sorted.d(78): Error: none of the overloads of template
`std.algorithm.sorting.completeSort` are callable using argument
types `!("a < b", SwapStrategy.unstable)(int[], int[])`
std/algorithm/sorting.d(117):Candidate is:
`completeSort(alias less = "a < b", SwapStrategy ss =
SwapStrategy.unstable, Lhs, Rhs)(SortedRange!(Lhs, less) lhs, Rhs
rhs)`
sorted.d(98): Error: template instance `nxt.sorted.Sorted!(int[],
"a < b", SwapStrategy.unstable)` error instantiating
```
What am I missing?
Re: Sorted Array (Container) Type
On Monday, 14 November 2022 at 00:29:40 UTC, Tejas wrote: He said on Discord he want contiguous data structure, rbtree allocates too much rbtree has it's uses cases. I wanted a sorted array because I want to include it in a benchmark suite and study it's time and space complexity. No application yet.
Re: Actual lifetime of static array slices?
On 11/15/22 06:05, Siarhei Siamashka wrote: > Ali commented that "the > compiler cannot do anything about it in all cases and we wouldn't want > it to spend infinite amount of time to try to determine everything". Yes, that's my understanding. > This sounds like he justifies the compiler's failure and accepts this as > something normal. Despite my lack of computer science education, I think the compiler's failure in analyzing source code to determine all bugs is "normal". I base my understanding on the "halting problem" and the "separate compilation" feature that D supports. > The https://dlang.org/spec/memory-safe-d.html page also provides a > rather vague statement: "@safe functions have a number of restrictions > on what they may do and are intended to disallow operations that may > cause memory corruption". Which kinda means that it makes some effort to > catch some memory safety bugs. Exactly. My understanding is that @safe attempts to remove memory corruptions. @live is being worked on to improve the situation by tracking liveness of data. > This weasel language isn't very > reassuring, compared to a very clear Rust documentation. That's spot on. Ali
Re: Get the class name without casting the type
On Tuesday, 15 November 2022 at 14:26:22 UTC, Imperatorn wrote: Side-note, you don't override interface members, you implement them. My knowledge of D is still modest, most likely, I just didn't know that override with interfaces can not be used. Thanks for the hint!
Re: Get the class name without casting the type
On Tuesday, 15 November 2022 at 14:09:01 UTC, bauss wrote: If you cast to Object and use classinfo.name then you get the expected result of B. Thanks!
Re: Get the class name without casting the type
On Tuesday, 15 November 2022 at 12:25:22 UTC, Hipreme wrote:
On Tuesday, 15 November 2022 at 11:42:59 UTC, Alexander Zhirov
wrote:
As shown you can use Object for this.
Side-note, you don't override interface members, you implement
them.
```d
interface A
{
string text();
}
class B : A
{
string text()
{
return ": To B or not to B!";
}
}
class C : A
{
string text()
{
return ": Oh I C!";
}
}
void main()
{
Object[] a = new B[3];
B b = new B();
C c = new C();
fill(a, b);
//Just to show
a[0] = c;
foreach (val; a)
{
writeln(typeof(val).stringof, val.text());
}
}
```
Re: Get the class name without casting the type
On Tuesday, 15 November 2022 at 11:42:59 UTC, Alexander Zhirov
wrote:
Is there any way to get the name of class B?
```d
interface A {
string text();
}
class B : A {
override string text() {
return ": It's ok!";
}
}
void main() {
A[] a = cast(A[]) new B[3];
B b = new B();
fill(a, b);
foreach (val ; a) {
writeln(typeof(val).stringof, val.text());
}
}
```
Output:
```sh
A: It's ok!
A: It's ok!
A: It's ok!
```
If you cast to Object and use classinfo.name then you get the
expected result of B.
```d
interface A {
string text();
}
class B : A {
override string text() {
return ": It's ok!";
}
}
void main() {
A[] a = cast(A[]) new B[3];
B b = new B();
fill(a, b);
foreach (val ; a) {
writeln((cast(Object)val).classinfo.name, val.text()); //
Here is the magic.
}
```
Output:
```
onlineapp.B: It's ok!
onlineapp.B: It's ok!
onlineapp.B: It's ok!
```
Re: Actual lifetime of static array slices?
On Tuesday, 15 November 2022 at 13:16:18 UTC, Paul Backus wrote: D's safety model is the same. In `@safe` code, D will reject anything that the compiler cannot say for sure is memory safe. However, unlike in Rust, `@safe` is not the default in D, so you must mark your code as `@safe` manually if you want to benefit from these checks. I specifically asked for Ali's opinion. Because the context is that the compiler couldn't catch a memory safety bug in the code that was annotated as @safe (but without -dip1000) and Ali commented that "the compiler cannot do anything about it in all cases and we wouldn't want it to spend infinite amount of time to try to determine everything". This sounds like he justifies the compiler's failure and accepts this as something normal. The https://dlang.org/spec/memory-safe-d.html page also provides a rather vague statement: "@safe functions have a number of restrictions on what they may do and are intended to disallow operations that may cause memory corruption". Which kinda means that it makes some effort to catch some memory safety bugs. This weasel language isn't very reassuring, compared to a very clear Rust documentation.
Re: Actual lifetime of static array slices?
On Tuesday, 15 November 2022 at 13:01:39 UTC, Siarhei Siamashka
wrote:
Well, there's another way to look at it:
https://doc.rust-lang.org/book/ch19-01-unsafe-rust.html
('Unsafe Rust exists because, by nature, static analysis is
conservative. When the compiler tries to determine whether or
not code upholds the guarantees, it’s better for it to reject
some valid programs than to accept some invalid programs.
Although the code might be okay, **if the Rust compiler doesn’t
have enough information to be confident, it will reject the
code**. In these cases, you can use unsafe code to tell the
compiler, “Trust me, I know what I’m doing.”')
Are you saying that the D safety model is different? In the
sense that if the D compiler doesn’t have enough information to
be confident, it will accept the code?
D's safety model is the same. In `@safe` code, D will reject
anything that the compiler cannot say for sure is memory safe.
However, unlike in Rust, `@safe` is not the default in D, so you
must mark your code as `@safe` manually if you want to benefit
from these checks.
Re: Actual lifetime of static array slices?
On Tuesday, 15 November 2022 at 06:44:16 UTC, Ali Çehreli wrote:
In summary, you are right but the compiler cannot do anything
about it in all cases and we wouldn't want it to spend infinite
amount of time to try to determine everything.
Well, there's another way to look at it:
https://doc.rust-lang.org/book/ch19-01-unsafe-rust.html ('Unsafe
Rust exists because, by nature, static analysis is conservative.
When the compiler tries to determine whether or not code upholds
the guarantees, it’s better for it to reject some valid programs
than to accept some invalid programs. Although the code might be
okay, **if the Rust compiler doesn’t have enough information to
be confident, it will reject the code**. In these cases, you can
use unsafe code to tell the compiler, “Trust me, I know what I’m
doing.”')
Are you saying that the D safety model is different? In the sense
that if the D compiler doesn’t have enough information to be
confident, it will accept the code?
Re: Get the class name without casting the type
On Tuesday, 15 November 2022 at 11:42:59 UTC, Alexander Zhirov
wrote:
Is there any way to get the name of class B?
```d
interface A {
string text();
}
class B : A {
override string text() {
return ": It's ok!";
}
}
void main() {
A[] a = cast(A[]) new B[3];
B b = new B();
fill(a, b);
foreach (val ; a) {
writeln(typeof(val).stringof, val.text());
}
}
```
Output:
```sh
A: It's ok!
A: It's ok!
A: It's ok!
```
You can do it as `val.classinfo.name`
Re: Get the class name without casting the type
On Tuesday, 15 November 2022 at 12:25:22 UTC, Hipreme wrote: You can do it as `val.classinfo.name` Yes, I have already done so, but the result is the same, actually :) ```d app.A: It's ok! app.A: It's ok! app.A: It's ok! ```
Get the class name without casting the type
Is there any way to get the name of class B?
```d
interface A {
string text();
}
class B : A {
override string text() {
return ": It's ok!";
}
}
void main() {
A[] a = cast(A[]) new B[3];
B b = new B();
fill(a, b);
foreach (val ; a) {
writeln(typeof(val).stringof, val.text());
}
}
```
Output:
```sh
A: It's ok!
A: It's ok!
A: It's ok!
```
