Re: Reverse the order of an array?

Re: Reverse the order of an array?

[Derek Peschel]

On Mon, Feb 11, 2002 at 01:26:20PM +0000, Oliver Kiddle wrote:

> Allowing array slices to go backwards, is a possibility though I'd not
> be suprised if implementing it caused other things to break. The
> easiest might be a parameter expension flag (r and R are gone so we'd
> need a letter. ^ perhaps as we used that for the reversed prompt
> state). Does anyone else have any views on whether we should add
> something for this and if so how?

Eww, I don't like the idea of using ^.

I picked ^ as a prompt escape because it was similar to _.  ^ is not
supposed to remind you of reversing in general (because the only thing
you can reverse is the parser state, I think).  Instead, ^ is supposed
to be a variation of _ (that just happens to be reversed) and ^ is
supposed to remind you of _.

I hope I'm making sense.  Anyway, is v or V (reVerse) used in parameter
expansion flags?  How about b or B (backwards)?

It's too bad that the same ideas (reversing) keep popping up without
a consistent way to express them.  (APL is very consistent about
expressing ideas, but I don't want to start using APL characters in
the shell!)  We could probably find a consistent way, but it would
not be backward-compatible.

-- Derek

Re: Reverse the order of an array?

[Oliver Kiddle]

Derek wrote:

> Eww, I don't like the idea of using ^.

Okay, that was a bad idea.

Bart wrote:

>
> > Allowing array slices to go backwards, is a possibility though I'd
not
> > be suprised if implementing it caused other things to break.
>
> Right now, using a backwards array slice references an imaginary
"empty
> element" to the left of the left end of the slice; assigning to that
> imaginary element makes it real.  E.g.:
>
> zsh% x=(a b c d e)
> zsh% x[4,2]=(y)
> zsh% echo $x
> a b c y d e
>
> This was motivated by desiring to have a syntax for inserting
elements
> into the array; "forwards" array slices only allow for replacement.

You could now also do that with x[3]+=(y) but I made use of the
existing code for inserting elements so it would be affected by such a
change to array slices. Also, if in the future we added support for
arrays of arrays, we'd need this syntax for something else.

> We could also use a subscripting flag (though that doesn't help with
r/R).

Yes. I can't think of any advantages to that over glob qualifiers
though.

> How about if (oa) means "sort in array index order" and (Oa) means
"sort
> in reverse array index order"?  There's precedent with (oi) and (Oi)
for
> case-insensitive sorting.  Obviously (oa) is equivalent to the
default,
> but so what?

That's a good idea. Patch below implements that.

Should we perhaps also add an argument to the `o' glob qualifier to
specify no sorting (i.e. pure directory order). If so, it should
perhaps be the same letter as here in which case `a' is not available.

Oliver

--- Src/subst.c Mon Jan  7 11:31:05 2002
+++ Src/subst.c       Tue Feb 12 21:06:15 2002
@@ -773,7 +773,7 @@
     Value v = NULL;
     int flags = 0;
     int flnum = 0;
-    int sortit = 0, casind = 0;
+    int sortit = 0, casind = 0, indord = 0;
     int unique = 0;
     int casmod = 0;
     int quotemod = 0, quotetype = 0, quoteerr = 0;
@@ -881,6 +881,9 @@
                case 'i':
                    casind = 1;
                    break;
+               case 'a':
+                   indord = 1;
+                   break;

                case 'V':
                    visiblemod++;
@@ -1894,16 +1897,29 @@
                zhuniqarray(aval);
        }
        if (sortit) {
-           static CompareFn sortfn[] = {
-               strpcmp, invstrpcmp, cstrpcmp, invcstrpcmp
-           };
-
            if (!copied)
                aval = arrdup(aval);
-
-           i = arrlen(aval);
-           if (i && (*aval[i-1] || --i))
-               qsort(aval, i, sizeof(char *), sortfn[sortit-1]);
+           if (indord) {
+               if (sortit & 2) {
+                   char *copy;
+                   char **end = aval + arrlen(aval) - 1, **start =
aval;
+
+                   /* reverse the array */
+                   while (start < end) {
+                       copy = *end;
+                       *end-- = *start;
+                       *start++ = copy;
+                   }
+               }
+           } else {
+               static CompareFn sortfn[] = {
+                   strpcmp, invstrpcmp, cstrpcmp, invcstrpcmp
+               };
+
+               i = arrlen(aval);
+               if (i && (*aval[i-1] || --i))
+                   qsort(aval, i, sizeof(char *), sortfn[sortit-1]);
+           }
        }
        if (plan9) {
            LinkNode tn;


__________________________________________________
Do You Yahoo!?
Everything you'll ever need on one web page
from News and Sport to Email and Music Charts
http://uk.my.yahoo.com

Re: Reverse the order of an array?

[Bart Schaefer]

On Feb 13,  4:36pm, Oliver Kiddle wrote:
}
} > How about if (oa) means "sort in array index order" and (Oa) means
} > "sort in reverse array index order"?
} 
} Should we perhaps also add an argument to the `o' glob qualifier to
} specify no sorting (i.e. pure directory order). If so, it should
} perhaps be the same letter as here in which case `a' is not available.

There are already a number of inconsistencies between glob qualifiers
and parameter flags in this regard.  Order matters in glob qualifiers;
e.g. (n) by itself is numeric sorting (which we don't yet do in arrays),
(no) is an error, and (on) means sort by name.  In parameter flags (i)
by itself is meaningless, but both (io) and (oi) mean to sort case-
independently (an option that we don't have in the glob qualifiers).

Also, directory order is not likely to have been carefully crafted by
the user the way array ordering is.  The main use of pure directory
order would be to avoid sorting when there are a large number of files.

-- 
Bart Schaefer                                 Brass Lantern Enterprises
http://www.well.com/user/barts              http://www.brasslantern.com

Zsh: http://www.zsh.org | PHPerl Project: http://phperl.sourceforge.net   

Re: Reverse the order of an array?

[Oliver Kiddle]

 --- Bart Schaefer <schaefer@brasslantern.com> wrote:

> There are already a number of inconsistencies between glob qualifiers
> and parameter flags in this regard.  Order matters in glob
> qualifiers;
> e.g. (n) by itself is numeric sorting (which we don't yet do in
> arrays),
> (no) is an error, and (on) means sort by name.  In parameter flags
> (i)
> by itself is meaningless, but both (io) and (oi) mean to sort case-
> independently (an option that we don't have in the glob qualifiers).
> 
> Also, directory order is not likely to have been carefully crafted by
> the user the way array ordering is.  The main use of pure directory
> order would be to avoid sorting when there are a large number of
> files.

I'll not worry about about directory order then. Is there any demand
for case insensitive glob sorting? (i) is free.

Seeing as you mentioned it I've added the numeric ordering. It'll save
you having to rescue (n) from being used for something else again (as
you did in 16350). This also means that `(oin)' should result in
case-insensitive numeric ordering.

Could someone better at C and perhaps more awake than me please take a
look at instrpcmp(). Is there a cleaner way I can get a pointer to a
pointer of the VARARRs to pass on to nstrpcmp()? I can avoid the cast
with `char (*e)[] = &c;' but the SGI compiler prints a warning for
that. I was hoping to avoid the e and f variables.

I've swiped notstrcmp() out of glob.c for this so the patch is longer
than it really is. I hope nobody minds about that function's move and
rename? Patch includes documentation for this and the new (a) flag.

Oliver

--- Src/subst.c.before	Wed Feb 20 19:34:54 2002
+++ Src/subst.c	Thu Feb 21 23:44:14 2002
@@ -540,6 +540,72 @@
 }
 
 /**/
+int
+nstrpcmp(const void *a, const void *b)
+{
+    char *c = *(char **)a, *d = *(char **)b;
+    int cmp;
+
+#ifdef HAVE_STRCOLL
+    cmp = strcoll(c, d);
+#endif
+    for (; *c == *d && *c; c++, d++);
+#ifndef HAVE_STRCOLL
+    cmp = (int)STOUC(*c) - (int)STOUC(*d);
+#endif
+    if (idigit(*c) || idigit(*d)) {
+	for (; c > *(char **)b && idigit(c[-1]); c--, d--);
+	if (idigit(*c) && idigit(*d)) {
+	    while (*c == '0')
+		c++;
+	    while (*d == '0')
+		d++;
+	    for (; idigit(*c) && *c == *d; c++, d++);
+	    if (idigit(*c) || idigit(*d)) {
+		cmp = (int)STOUC(*c) - (int)STOUC(*d);
+		while (idigit(*c) && idigit(*d))
+		    c++, d++;
+		if (idigit(*c) && !idigit(*d))
+		    return 1;
+		if (idigit(*d) && !idigit(*c))
+		    return -1;
+	    }
+	}
+    }
+    return cmp;
+}
+
+/**/
+int
+invnstrpcmp(const void *a, const void *b)
+{
+    return -nstrpcmp(a, b);
+}
+
+/**/
+int
+instrpcmp(const void *a, const void *b)
+{
+    VARARR(char, c, strlen(*(char **) a) + 1);
+    VARARR(char, d, strlen(*(char **) b) + 1);
+    char **e = (char **)&c;
+    char **f = (char **)&d;
+    char *s, *t;
+
+    for (s = *(char **) a, t = c; (*t++ = tulower(*s++)););
+    for (s = *(char **) b, t = d; (*t++ = tulower(*s++)););
+
+    return nstrpcmp(&e, &f);
+}
+
+/**/
+int
+invinstrpcmp(const void *a, const void *b)
+{
+    return -instrpcmp(a, b);
+}
+
+/**/
 static char *
 dopadding(char *str, int prenum, int postnum, char *preone, char
*postone, char *premul, char *postmul)
 {
@@ -773,7 +839,7 @@
     Value v = NULL;
     int flags = 0;
     int flnum = 0;
-    int sortit = 0, casind = 0, indord = 0;
+    int sortit = 0, casind = 0, numord = 0, indord = 0;
     int unique = 0;
     int casmod = 0;
     int quotemod = 0, quotetype = 0, quoteerr = 0;
@@ -881,6 +947,9 @@
 		case 'i':
 		    casind = 1;
 		    break;
+		case 'n':
+		    numord = 1;
+		    break;
 		case 'a':
 		    indord = 1;
 		    break;
@@ -1021,7 +1090,7 @@
 	}
     }
     if (sortit)
-	sortit += (casind << 1);
+	sortit += (casind << 1) + (numord << 2);
 
     if (!premul)
 	premul = " ";
@@ -1913,7 +1982,8 @@
 		}
 	    } else {
 		static CompareFn sortfn[] = {
-		    strpcmp, invstrpcmp, cstrpcmp, invcstrpcmp
+		    strpcmp, invstrpcmp, cstrpcmp, invcstrpcmp,
+		    nstrpcmp, invnstrpcmp, instrpcmp, invinstrpcmp
 		};
 
 		i = arrlen(aval);
--- Src/glob.c.before	Thu Feb 21 23:25:39 2002
+++ Src/glob.c	Thu Feb 21 23:44:14 2002
@@ -854,7 +854,10 @@
     for (i = gf_nsorts, s = gf_sortlist; i; i--, s++) {
 	switch (*s & ~GS_DESC) {
 	case GS_NAME:
-	    r = notstrcmp(&a->name, &b->name);
+	    if (gf_numsort)
+	    	r = nstrpcmp(&b->name, &a->name);
+	    else
+	    	r = strpcmp(&b->name, &a->name);
 	    break;
 	case GS_DEPTH:
 	    {
@@ -1609,46 +1612,6 @@
     free(matchbuf);
 
     restore_globstate(saved);
-}
-
-/* Return the order of two strings, taking into account *
- * possible numeric order if NUMERICGLOBSORT is set.    *
- * The comparison here is reversed.                     */
-
-/**/
-static int
-notstrcmp(char **a, char **b)
-{
-    char *c = *b, *d = *a;
-    int cmp;
-
-#ifdef HAVE_STRCOLL
-    cmp = strcoll(c, d);
-#endif
-    for (; *c == *d && *c; c++, d++);
-#ifndef HAVE_STRCOLL
-    cmp = (int)STOUC(*c) - (int)STOUC(*d);
-#endif
-    if (gf_numsort && (idigit(*c) || idigit(*d))) {
-	for (; c > *b && idigit(c[-1]); c--, d--);
-	if (idigit(*c) && idigit(*d)) {
-	    while (*c == '0')
-		c++;
-	    while (*d == '0')
-		d++;
-	    for (; idigit(*c) && *c == *d; c++, d++);
-	    if (idigit(*c) || idigit(*d)) {
-		cmp = (int)STOUC(*c) - (int)STOUC(*d);
-		while (idigit(*c) && idigit(*d))
-		    c++, d++;
-		if (idigit(*c) && !idigit(*d))
-		    return 1;
-		if (idigit(*d) && !idigit(*c))
-		    return -1;
-	    }
-	}
-    }
-    return cmp;
 }
 
 /* Return the trailing character for marking file types */
--- Doc/Zsh/expn.yo.before      Thu Feb 21 23:44:08 2002
+++ Doc/Zsh/expn.yo     Thu Feb 21 23:44:14 2002
@@ -620,6 +620,11 @@
 example by using `tt(${(AA)=)var(name)tt(=)...tt(})' to activate
 field splitting, when creating an associative array.
 )
+item(tt(a))(
+With tt(o) or tt(O), sort in array index order. Note that `tt(oa)' is
+therefore equivalent to the default but `tt(Oa)' is useful for
+obtaining an array's elements in reverse order.
+)
 item(tt(c))(
 With tt(${#)var(name)tt(}), count the total number of characters in an
array,
 as if the elements were concatenated with spaces between them.
@@ -660,6 +665,9 @@
 )
 item(tt(O))(
 Sort the resulting words in descending order.
+)
+item(tt(n))(
+With tt(o) or tt(O), sort numerically.
 )
 item(tt(P))(
 This forces the value of the parameter var(name) to be interpreted as
a


__________________________________________________
Do You Yahoo!?
Everything you'll ever need on one web page
from News and Sport to Email and Music Charts
http://uk.my.yahoo.com

Re: Reverse the order of an array?

[Bart Schaefer]

On Feb 22,  9:20am, Oliver Kiddle wrote:
}
} I'll not worry about about directory order then. Is there any demand
} for case insensitive glob sorting? (i) is free.

I've never heard anyone ask for it, but it might be useful in the same
cases where (#i) is useful.  On the other hand, it'd be nicest to have
the sort be case-insensitive only in the regions where the glob itself
is case-insentive, which is probably a prohibitive amount of work.
 
} Could someone better at C and perhaps more awake than me please take a
} look at instrpcmp(). Is there a cleaner way I can get a pointer to a
} pointer of the VARARRs to pass on to nstrpcmp()?

I think that's about the best you can do given that you don't know whether
VARARR() will produce a stack array or an allocated pointer.

-- 
Bart Schaefer                                 Brass Lantern Enterprises
http://www.well.com/user/barts              http://www.brasslantern.com

Zsh: http://www.zsh.org | PHPerl Project: http://phperl.sourceforge.net