www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 4114] New: Support static arrays in some algorithms

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4114

           Summary: Support static arrays in some algorithms
           Product: D
           Version: future
          Platform: All
        OS/Version: All
            Status: NEW
          Keywords: patch
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: bearophile_hugs eml.cc



Fixed-sized stack-allocated static arrays can't support all features of a
dynamic array, so they are not a fully flexible range. So it's not possible to
perform some operations/algorithms on static arrays.

But there are several basic operations that I might desire to perform on static
arrays too, like to test if their items are sorted (isSorted), to sort them
(sort()), or to compare the items of a sequence to the items of a static array
(equals).

Currently std.algorithm.isSorted doesn't work with static arrays, but I see no
point in forbidding isSorted() or sort() on a static array. A simple workaround
is to use:
isSorted(stat_arr[])
sort(stat_arr[])
to give isSorted a dynamic array view of the same contents of the static array.
This is not too much bad looking, but it gratuitously breaks some generic code.


This shows a possible simple way to fix it: to rename the current isSorted as
isSorted_impl, and add this function template that uses isSorted_impl:


import std.algorithm: isSorted_impl = isSorted;

bool isSorted(alias less="a < b", Range)(Range data)
    if (__traits(isStaticArray, Range) || isForwardRange!Range) {
        static if (__traits(isStaticArray, Range))
            return isSorted_impl!(less)(data[]);
        else
            return isSorted_impl!(less)(data);
}

void main() {
    int[3] b = [1, 2, 3];
    assert(isSorted(b));
}


Better, the original isSorted() can become a function statically nested in this
wrapper.

std.range.array, equal() and sort() can be augmented in similar ways.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 21 2010
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4114


David Simcha <dsimcha yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dsimcha yahoo.com



The issue I see here is that, since static arrays are usually stack allocated,
using them as ranges is inherently unsafe.  Even in cases where it seems safe,
the predicate may do weird things like escape the static array.  I think the
generic programming issue can be solved by simply having an unsafe function in
std.range:

auto toRange(R)(ref R stuff) if(isInputRange!R) {
    static if(isStaticArray!R) {
         return stuff[];
    } else {
        return stuff; 
    }
}

Of course, I'd also create an overload w/o the ref so it works with rvalues. 
Sound good?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 16 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4114




In my code I use fixed-sized arrays when possible because heap allocations are
slow. What I'd like is that some operations, like the sorts, counts, searches,
tests like isSorted, and few other operations, to just work with fixed-sized
arrays too. I don't think that performing a isSorted() on a fixed-sized array
is an unsafe operation, so I don't agree with you.

If you, Andrei (and Brad Roberts) are not interested in this, then you may
close this enhancement request.

Regarding that toRange() I am not sure if it's a worth addition for Phobos2,
you may ask other people.

Thank you for your work on Phobos2.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 17 2010
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4114


Jonathan M Davis <jmdavisProg gmx.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |jmdavisProg gmx.com
         Resolution|                            |WONTFIX



PDT ---
Slicing static arrays works. In some cases, there may be issues, but in most
cases, it works. Most range-based functions don't alter the original range in
manner which would be of any risk to static arrays. Predicates don't usually
escape anything either. It would be a _highly_ abnormal predicate which did,
and I'd be worried about any predicate which did. Predicates for std.algorithm
functions are generally assumed not to have state which changes and usually
won't work right if they do. The greatest risk is if you try and return a range
from a range-based function which you passed a static array to. _That_ risks
leaks, but the programmer is just going to have to be careful about that.
There's no way to disallow the use of dynamic arrays which point to static
arrays.

Creating overloads for static arrays would result in needlessly copying them
(since static arrays are value types), and would further clutter std.algorithm,
increasing its maintenance cost. We're just not going to do anything which
treats static arrays special in order to work with range-based functions. If
you want to use a static array with a range-base function, then slice it and be
sure that you don't let the resulting range escape the scope of the static
array.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 14 2011