Feature request: two level sorting

Feature request: two level sorting

[Sebastian Gniazdowski]

Hello
Suppose you have set of file names:

files=( "aaa-A" "aab-B" "aac-A" "aad-C" )

when sorted normally, it will yield:

# print -rl -- ${(o)files[@]}
aaa-A
aab-B
aac-A
aad-C

when sorted with grouping on A, this will be:

aaa-A
aac-A
aab-B
aad-C

**The thing is** that it is easy to provide group names in separate array:

# groups=( "${files[@]//(#b)*([A-Z])/$match[1]}" )
# print -rl -- "${groups[@]}"
A
B
A
C

With that in place, one can sort with the grouping in following way:

    files=( "${(o)files[@]}" )
    group_letters=( A B C )
    integer a i grsize="${#group_letters}" size="${#files}"
    out=( )
    for (( a=1; a<=grsize; a++ )); do
        selected_group="${group_letters[a]}"
        for (( i=1; i<=size; i++ )); do
            [ "$selected_group" != "${groups[i]}" ] && continue
            out+=( "${files[i]}" )
        done
    done
    print -rl "${out[@]}"

So this is somewhat an amount of code. The group-sort flag could take
group names of sorted data in additional parameter, e.g.:
"${(ox:group_letters:)files}"

Best regards,
Sebastian Gniazdowski

Re: Feature request: two level sorting

[Sebastian Gniazdowski]

On 15 June 2016 at 07:13, Sebastian Gniazdowski <sgniazdowski@gmail.com> wrote:
> So this is somewhat an amount of code. The group-sort flag could take
> group names of sorted data in additional parameter, e.g.:
> "${(ox:group_letters:)files}"


A mistake, sorry. Besides passing $group_letters, one has also to pass
$groups, so: "${(ox:group_letters::groups:)files}". Hope this doesn't
look sophisticated, the main **thing** is that providing group names
of sorted text is a one line.

Best regards,
Sebastian Gniazdowski

Re: Feature request: two level sorting

[Sebastian Gniazdowski]

On 15 June 2016 at 07:21, Sebastian Gniazdowski <sgniazdowski@gmail.com> wrote:
> A mistake, sorry. Besides passing $group_letters, one has also to pass
> $groups, so: "${(ox:group_letters::groups:)files}". Hope this doesn't
> look sophisticated, the main **thing** is that providing group names
> of sorted text is a one line.

Also, I've provided group_letters in aim of doing the same what I did,
which is O(M*N) code, M group size, N sorted data size. What should be
really done is typical group sorting (never did that), with the fact
of the **point** that providing group names of sorted text in separate
array is a one line of code. So the syntax would be:
${(ox:groups:)files}, and Zsh would implement SQL's GROUP BY sorting.

Best regards,
Sebastian Gniazdowski

Re: Feature request: two level sorting

[Bart Schaefer]

On Jun 15,  7:13am, Sebastian Gniazdowski wrote:
}
} # print -rl -- ${(o)files[@]}
} aaa-A
} aab-B
} aac-A
} aad-C
} 
} when sorted with grouping on A, this will be:
} 
} aaa-A
} aac-A
} aab-B
} aad-C

In a follow-on message you compare this to SQL GROUP BY, but you're
conveniently ignoring that GROUP BY works on rows of data in columms
whereas here you're asking for something that works on arrays of
strings.

"Feature request: A one-line parameter expansion that converts an
array to a two-dimensional array by parsing with a pattern match,
sorts the 2d array on one axis using multiple values of the other
axis, and then reassembles the original one-dimensional array
elements again in the new ordering."

Can you even suggest a syntax for this that wouldn't look worse than
the "for" loop you already wrote?
 
} **The thing is** that it is easy to provide group names in separate
} array:
} 
} # groups=( "${files[@]//(#b)*([A-Z])/$match[1]}" )

OK, let's examine that for a second.  What can't easily be done in the
general case might be easily done in the specific.  Can you choose a
delimiter of some kind that will never appear in $match[1] ?  Let's
try ":" for this example.

    groups=( "${files[@]//(#b)*([A-Z])(#m)/${match[1]}:$MATCH}" )

Now:

    print -rl -- "${(@)${(@o)groups}#*:}"

And there you go.  It can even be written without the extra array:

print -rl -- "${(@)${(@o)${files[@]//(#b)*([A-Z])(#m)/${match[1]}:$MATCH}}#*:}"

But it would be horrible to try to make a generic sorting flag that
can be passed the pattern plus the fields on which to group plus the
sort order to apply to the result.

Re: Feature request: two level sorting

[Mikael Magnusson]

On Wed, Jun 15, 2016 at 7:12 PM, Bart Schaefer
<schaefer@brasslantern.com> wrote:
> On Jun 15,  7:13am, Sebastian Gniazdowski wrote:
> }
> } # print -rl -- ${(o)files[@]}
> } aaa-A
> } aab-B
> } aac-A
> } aad-C
> }
> } when sorted with grouping on A, this will be:
> }
> } aaa-A
> } aac-A
> } aab-B
> } aad-C
>
> In a follow-on message you compare this to SQL GROUP BY, but you're
> conveniently ignoring that GROUP BY works on rows of data in columms
> whereas here you're asking for something that works on arrays of
> strings.
>
> "Feature request: A one-line parameter expansion that converts an
> array to a two-dimensional array by parsing with a pattern match,
> sorts the 2d array on one axis using multiple values of the other
> axis, and then reassembles the original one-dimensional array
> elements again in the new ordering."
>
> Can you even suggest a syntax for this that wouldn't look worse than
> the "for" loop you already wrote?
>
> } **The thing is** that it is easy to provide group names in separate
> } array:
> }
> } # groups=( "${files[@]//(#b)*([A-Z])/$match[1]}" )
>
> OK, let's examine that for a second.  What can't easily be done in the
> general case might be easily done in the specific.  Can you choose a
> delimiter of some kind that will never appear in $match[1] ?  Let's
> try ":" for this example.
>
>     groups=( "${files[@]//(#b)*([A-Z])(#m)/${match[1]}:$MATCH}" )
>
> Now:
>
>     print -rl -- "${(@)${(@o)groups}#*:}"
>
> And there you go.  It can even be written without the extra array:
>
> print -rl -- "${(@)${(@o)${files[@]//(#b)*([A-Z])(#m)/${match[1]}:$MATCH}}#*:}"
>
> But it would be horrible to try to make a generic sorting flag that
> can be passed the pattern plus the fields on which to group plus the
> sort order to apply to the result.

Can we do what the oe:: flag does for globbing? Ie, pass each element
to a custom code snippet that transforms it arbitrarily, and sort on
the output.

-- 
Mikael Magnusson

Re: Feature request: two level sorting

[Bart Schaefer]

On Jun 15,  8:25pm, Mikael Magnusson wrote:
}
} Can we do what the oe:: flag does for globbing? Ie, pass each element
} to a custom code snippet that transforms it arbitrarily, and sort on
} the output.

We considered that a while back, but the problem is that if you allow
arbitrary shell code to be called from within the sort algorithm there
are way too many opportunities for madness.

With globbing, there's one well-defined place -- the read of the name
from the directory structure -- where the callback can be applied to
a single data element.  With a sort, the callback may be invoked many
times for pairs of data, sometimes even more than once for the same
pair depending on the algorithm, and unlike e.g. perl that has object
pointers and reference-count garbage collection and lexical scopiing
and a whole other panoply of protections against the user shooting
himself, in zshell code all sorts of havoc could be wrought.  (Yeah,
you can probably create the same havoc in perl if you work at it, but
it's a lot more difficult.)

Falling back to something lesser/safer amounts to inventing a whole
new mini-language.  It's just not worth it to internalize in the shell
something that (a) other languages do better and (b) was intended by
the original architecture to be done in an outside process anyway.

Re: Feature request: two level sorting

[Mikael Magnusson]

On Thu, Jun 16, 2016 at 12:38 AM, Bart Schaefer
<schaefer@brasslantern.com> wrote:
> On Jun 15,  8:25pm, Mikael Magnusson wrote:
> }
> } Can we do what the oe:: flag does for globbing? Ie, pass each element
> } to a custom code snippet that transforms it arbitrarily, and sort on
> } the output.
>
> We considered that a while back, but the problem is that if you allow
> arbitrary shell code to be called from within the sort algorithm there
> are way too many opportunities for madness.
>
> With globbing, there's one well-defined place -- the read of the name
> from the directory structure -- where the callback can be applied to
> a single data element.  With a sort, the callback may be invoked many
> times for pairs of data, sometimes even more than once for the same
> pair depending on the algorithm, and unlike e.g. perl that has object
> pointers and reference-count garbage collection and lexical scopiing
> and a whole other panoply of protections against the user shooting
> himself, in zshell code all sorts of havoc could be wrought.  (Yeah,
> you can probably create the same havoc in perl if you work at it, but
> it's a lot more difficult.)

Ah, yeah I suppose that makes sense, we would have to add a bunch of
extra internal state to track the "sort-name" for each member during
expansion, which is very specific, if we wanted to avoid the multiple
calls.

> Falling back to something lesser/safer amounts to inventing a whole
> new mini-language.  It's just not worth it to internalize in the shell
> something that (a) other languages do better and (b) was intended by
> the original architecture to be done in an outside process anyway.

Well, this old trick always works if you don't mind depending on /
being readable, but that's probably a safe assumption usually.

% myarray=("aaa-A" "aab-B" "aac-A" "aad-C")
% echo /(e:'reply=($myarray)':oe:'REPLY=${REPLY#*-}':)
aac-A aaa-A aab-B aad-C

-- 
Mikael Magnusson

Re: Feature request: two level sorting

[Bart Schaefer]

On Jun 16,  1:02am, Mikael Magnusson wrote:
}
} Well, this old trick always works if you don't mind depending on /
} being readable, but that's probably a safe assumption usually.
} 
} % myarray=("aaa-A" "aab-B" "aac-A" "aad-C")
} % echo /(e:'reply=($myarray)':oe:'REPLY=${REPLY#*-}':)
} aac-A aaa-A aab-B aad-C

Heh, you don't even need / to be readable, any single readable file
will do:

torch% echo /dev/null(e:'reply=($myarray)':oe:'REPLY=${REPLY#*-}':)
aac-A aaa-A aab-B aad-C

Rather hard to embed that in a parameter expansion context without
using a process substitution, though.  And I don't think it covers
the secondary sort: note that in Sebastian's original example he
wants (aaa-A aac-A) but the above output has them the other way
(the sort isn't guaranteed to be stable).

Re: Feature request: two level sorting

[Sebastian Gniazdowski]

On 16 June 2016 at 01:02, Mikael Magnusson <mikachu@gmail.com> wrote:
> Well, this old trick always works if you don't mind depending on /
> being readable, but that's probably a safe assumption usually.
>
> % myarray=("aaa-A" "aab-B" "aac-A" "aad-C")
> % echo /(e:'reply=($myarray)':oe:'REPLY=${REPLY#*-}':)
> aac-A aaa-A aab-B aad-C


Could this be used to alter numeric sort a little? The point is to
have numbers be ordered *after* letters, not *before* letters. Example

# a=( "aaa" "aeg" "aa1" "ae2" )
# echo ${(on)a[@]}
aa1 aaa ae2 aeg

This places "1" before "a" (1 < a) and "2" before "g" (2 < g). With
this reversed, the result would be:

aaa aa1 aeg ae2

So now a < 1 and g < 2.

Best regards,
Sebastian Gniazdowski

Re: Feature request: two level sorting

[Bart Schaefer]

On Jul 1,  9:16am, Sebastian Gniazdowski wrote:
} Subject: Re: Feature request: two level sorting
}
} On 16 June 2016 at 01:02, Mikael Magnusson <mikachu@gmail.com> wrote:
} > % myarray=("aaa-A" "aab-B" "aac-A" "aad-C")
} > % echo /(e:'reply=($myarray)':oe:'REPLY=${REPLY#*-}':)
} > aac-A aaa-A aab-B aad-C
} 
} Could this be used to alter numeric sort a little? The point is to
} have numbers be ordered *after* letters, not *before* letters.

No, it can't.

Re: Feature request: two level sorting

[Sebastian Gniazdowski]

On 1 July 2016 at 18:43, Bart Schaefer <schaefer@brasslantern.com> wrote:
> } Could this be used to alter numeric sort a little? The point is to
> } have numbers be ordered *after* letters, not *before* letters.
>
> No, it can't.

Good that I can get away with the problem by using capital letters,
which aren't originally used in the data.

Best regards,
Sebastian Gniazdowski

Re: Feature request: two level sorting

[Bart Schaefer]

On Jul 2,  6:09am, Sebastian Gniazdowski wrote:
}
} Good that I can get away with the problem by using capital letters,
} which aren't originally used in the data.

If you can find a character not in your data that collates after 'z',
you can do something like this:

  setopt extendedglob
  LC_COLLATE=C
  c='~'
  a=( "aaa" "aeg" "aa1" "ae2" )
  x=( ${a//<->(#m)/$c$MATCH} )
  print ${${(o)$x}//$c}

Re: Feature request: two level sorting

[Sebastian Gniazdowski]

On 15 June 2016 at 19:12, Bart Schaefer <schaefer@brasslantern.com> wrote:
>
> "Feature request: A one-line parameter expansion that converts an
> array to a two-dimensional array by parsing with a pattern match,
> sorts the 2d array on one axis using multiple values of the other
> axis, and then reassembles the original one-dimensional array
> elements again in the new ordering."

Not sure what you mean, I didn't propose such functionality. I went
for a compromise. A shellish or hackish compromise. What can be done
without multi-dimensional arrays in this case? Not much. Except for
providing separate array. A shellish solution. I think such style
gives various opportunities later.

Reading this after hour I see what you mean. You converted two line
"gather array, pass to parameter" to one line "call with pattern
gathering array". Should we do this? It's not shellish. It might
however be Zshish ;) i.e. reasonable, one line, difficult at first
glance. I will keep in mind the call for syntax through the day and
see what I can came up with.

> Can you even suggest a syntax for this that wouldn't look worse than
> the "for" loop you already wrote?

I don't think the for loop is that bad. It's typical imperative code.
One can code in Zsh this way. I had a choice whether to solve
imperatively or via modifying the string in similar manner you later
show, so that "sort string" would equal "sort with grouping". I've
chosen imperative option.

-- 
Best regards,
Sebastian Gniazdowski

Re: Feature request: two level sorting

[Bart Schaefer]

On Jun 16,  6:53am, Sebastian Gniazdowski wrote:
} Subject: Re: Feature request: two level sorting
}
} On 15 June 2016 at 19:12, Bart Schaefer <schaefer@brasslantern.com> wrote:
} >
} > "Feature request: A one-line parameter expansion that ...
} 
} Not sure what you mean, I didn't propose such functionality.

OK, I see.  You were actually proposing that the final solution use a
second array to group the first one; I misread that as only an example
of how to get the result you wanted.

So what you're really suggesting is --

Given two arrays AA and AB which must be of equal length:
(1) sort AB and apply that new ordering to the elements of AA
(2) except that if two elements of AB are the same, use another
    sort to order the corresponding elements of AA

-- and you want a syntax that passes the name of AB, the order to be
applied to AB, and the secondary order of AA, via the expansion flags
of a reference to AA.

Have I got it this time?

What if you need "two levels" of sorting for the desired order AB?

} > Can you even suggest a syntax for this that wouldn't look worse than
} > the "for" loop you already wrote?
} 
} I don't think the for loop is that bad.

I wouldn't have said so either, except that you want a new feature to
replace it, so you must not like having to use the loop.

Re: Feature request: two level sorting

[Sebastian Gniazdowski]

On 16 June 2016 at 09:21, Bart Schaefer <schaefer@brasslantern.com> wrote:
> So what you're really suggesting is --
>
> Given two arrays AA and AB which must be of equal length:
> (1) sort AB and apply that new ordering to the elements of AA
> (2) except that if two elements of AB are the same, use another
>     sort to order the corresponding elements of AA
>
> -- and you want a syntax that passes the name of AB, the order to be
> applied to AB, and the secondary order of AA, via the expansion flags
> of a reference to AA.
>
> Have I got it this time?

I think yes. Not sure how tricky GROUP BY sorting is, but it sounds tricky.

> What if you need "two levels" of sorting for the desired order AB?

Yeah that's an issue. But that's least we can do, GROUP BY sorting on
one group. What's important in this, is that it will allow to avoid
O(N^2) situations. Ultimate solution would be own comparing code,
thing used e.g. C++ where it has proven to be well abstract, allowing
to face variety of demands, rather all of them. What I'm really hoping
is that the (x:groups:) flag would be similarly elastic, resulting in
uses that are hard to predict. But I cannot provide any trick that
(x:groups:) would allow.

Also, own comparing code would be rather slow? Zsh doesn't do
compilation I think, so it would evaluate the code at each comparison,
so that's a drawback. (x:groups:) wouldn't have this issue. And it
could open door to variety of O(N^2)-avoid tricks.

PS. Could the (x:groups:) array contain multiple groups separated via
available-separator e.g. ":"? I mean, one can have objections to mess
with his original data adding prefix separated with ":". That's why
I've chosen the imperative way of solving, the loop mentioned. Didn't
want to mess with data, change way it looks and track this with
extensive thought. But I could surely mess with separate groups array,
it would feel natural to provide "A:1:x" there and similar
sub-group-pretending things.

Best regards,
Sebastian Gniazdowski

Re: Feature request: two level sorting

[Bart Schaefer]

On Jun 18, 12:56pm, Sebastian Gniazdowski wrote:
} Subject: Re: Feature request: two level sorting
}
} On 16 June 2016 at 09:21, Bart Schaefer <schaefer@brasslantern.com> wrote:
} > Given two arrays AA and AB which must be of equal length:
} > (1) sort AB and apply that new ordering to the elements of AA
} > (2) except that if two elements of AB are the same, use another
} >     sort to order the corresponding elements of AA
} 
} I think yes. Not sure how tricky GROUP BY sorting is, but it sounds
} tricky.

Well, firstly GROUP BY doesn't work the way you seem to think.  It's
not a sort; in SQL a GROUP BY will produce a single row of output that
combines the data from the matching rows, not the original rows
arranged in groups.  The order in which the matching rows accumulate
is unspecified; any ORDER BY is applied to the resulting composites.

What you're really asking for in your original example is sorting by
two different keys, except that you want one key to be a substring
of the input data.  This thing with the parallel arrays amounts to
nothing more than a way to separate out the substring so you can
pretend there are two distinct fields each of which is a key.

The icky bit with zsh is that to sort with any efficiency on multiple
fields you need to be able to manipulate arrays of pointers, but
parameter expansion only gives you arrays of values.

So while I appreciate your "didn't want to mess with data" sentiment,
it might require a lot of reworking of the parameter implementation to
manipulate anything other than the data.  In other words, even if I am
correct about "given two arrays ..." you shouldn't hold your breath
expecting that to get implemented.

} Ultimate solution would be own comparing code

See my other response to Mikael.  tl;dr: Not safe, not something shells
were intended to do, and already done better in other languages.