Methods to sort a list of lists.

[Anonymous]

If I want to sort a list of lists... say on the 3rd element of each how
might I go about this?

The following logic is what I thought of ?

process the lists moving all the 3rd elements to the head of each list.
extract all the car elements (was the 3rd el) into their own list.
sort this with acad_strlsort if each is a string or with a number
sorting routine if they are integers or reals.
reprocess the original list with a foreach on the sorted car elements
moving them from the origninal lists to a new list.
process the new sorted list moving all the car elements back to the 3rd
position.

problem...
If I have two or more lists that are similar like

(4 "MIKE" "MARY" "BECKY" "ALICE")
(4 "MIKE" "BILL" "BECKY" "ALICE")
(4 "MIKE" "ANNA" "BECKY" "ALICE")

How can I get them to sort like this:
(3 "MIKE" "ANNA" "BECKY" "ALICE")
(3 "MIKE" "BILL" "BECKY" "ALICE")
(3 "MIKE" "MARY" "BECKY" "ALICE")

In this case all three lists have an identical 3rd element, but in each
list the 2nd elements are different.
I suppose I would want them to sort first on the 3rd element then on the
1rst element.
but how would my application know just how the lists vary or are similar
but not exactly the same.

Any thougts?

[Anonymous]

"Doug Broad" wrote in message
news:2E3275ADEF1AE048E2F7A82BEC990F27@in.WebX.maYIadrTaRb...
> Excellent point about the removal of duplicates.
> The removal behavior, however, seems to be limited
> to lists of integers.

In fact, it doesn't (at least, not on the copy of
AutoCAD 2000 I just tried it on).

Try this:

(defun compare-elements (a b sortspec)
( (lambda (x y test)
(if (and (equal x y fuzz) (cdr sortspec))
(compare-elements a b (cdr sortspec))
(apply test (list x y))
)
)
(nth (cdar sortspec) a)
(nth (cdar sortspec) b)
(caar sortspec)
)
)

(defun complex-sort (alist sortspec)
(mapcar
'(lambda (i)
(nth i alist)
)
(vl-sort-i alist
'(lambda (a b)
(compare-elements a b sortspec)
)
)
)
)

(defun complex-sort-bad (alist sortspec)
(vl-sort alist
'(lambda (a b)
(compare-elements a b sortspec)
)
)
)


;; TEST

(defun C:TESTIT ( / lst res)

(setq lst
'( ("D" "a" 3 2 1)
("B" "c" 2 1 3)
("B" "a" 2 1 3)
("D" "b" 3 2 1)
("E" "a" 2 2 1)
("C" "b" 1 3 2)
("D" "b" 0 2 1)
)
)
(repeat 5 (setq lst (append lst lst)))
(princ (strcat "\nInput list length: " (itoa (length lst))))
(setq res
(complex-sort-bad
lst
'((< . 1) (< . 3) (< . 0)) ; sort specification
)
)
(mapcar 'print res)
(princ (strcat "\nResult list length: " (itoa (length res))))
(princ)
)

;; Here is what I get:

Command: testit

Input list length: 224
("B" "a" 2 1 3)
("D" "a" 3 2 1)
("E" "a" 2 2 1)
("D" "b" 0 2 1)
("D" "b" 0 2 1)
("D" "b" 0 2 1)
("D" "b" 0 2 1)
("D" "b" 3 2 1)
("D" "b" 3 2 1)
("D" "b" 0 2 1)
("D" "b" 0 2 1)
("D" "b" 3 2 1)
("D" "b" 0 2 1)
("D" "b" 3 2 1)
("D" "b" 0 2 1)
("C" "b" 1 3 2)
("B" "c" 2 1 3)
Result list length: 17


> It does not occur with lists of strings or lists
> or lists of lists or lists of reals.
> The behavior is strangely incosistent.

See above.

>
> The index method is very intriguing but how would you use the
> indexing method to accomplish the multi-stage sort that Mike is thinking
about?

Indexing is just like sorting except that the original
data is not rearranged. Instead, indexing generates just
the information required to describe the original data in
a given sorted order (in this case, a list of integers
representing the indices of each element in the sorted
order is all that's required).

This is indexing:


(setq index (vl-sort-i '>) ;; descending
(setq index2 (vl-sort-i '<) ;; ascending

The result are two lists of integers, that you can use
to process the list in sorted order using:

(mapcar
'(lambda (i)
(SomeProcessingFunction (nth i ))
)

)

In otherwords, sorting is something that is often done
in advance of processing the resulting sorted list in
the sorted order.

So, really it's not necessary to generate a sorted copy
of the original list, when you can generate just a list
of integers describing the sorted order, which can be
used to process the original data in the sorted order.

[Anonymous]

Tony,
My comments regarding deletion of elements were concerning ACAD's version
of vl-sort, not on your compare-elements subroutine, which seems to always
delete duplicates.

Deleting duplicates may be advantageous (if it is the desired behavior). It
might be more desirable to have the calling function decide how duplicates
are handled. Your function is very consistent but AutoCAD's VL-SORT is
not as consistent.

;;Here are some of my tests on AC2002/ADT 3.3

(setq lsti '( 1 2 3 1 4 1 5))
(1 2 3 1 4 1 5)
_$ (vl-sort lsti '<)
(1 2 3 4 5)
;;vl-sort removed the duplicate integers
_$ (vl-sort lsti '>)
(5 4 3 2 1)
;;Same thing
_$ (setq lsts '("a" "b" "a" "b" "c" "b" "a"))
("a" "b" "a" "b" "c" "b" "a")
_$ (vl-sort lsts '>)
("c" "b" "b" "b" "a" "a" "a")
;;No duplicates removed
_$ (vl-sort lsts '<)
("a" "a" "a" "b" "b" "b" "c")
;;No duplicates removed
(setq lstl '(("a" "b" 1)("b" "c" 1) ("c" "a" 1)))
(("a" "b" 1) ("b" "c" 1) ("c" "a" 1))
_$ (vl-sort lstl '(lambda (a b) (< (caddr a)(caddr b))))
(("a" "b" 1) ("b" "c" 1) ("c" "a" 1))
;;No duplicates removed - but no identical elements anyway
(setq lstl '(("a" "b")("a" "b")("c" "d")("d" "c")("a" "b")))
(("a" "b") ("a" "b") ("c" "d") ("d" "c") ("a" "b"))
_$ (vl-sort lstl '(lambda (a b) (< (car a)(car b))))
(("a" "b") ("a" "b") ("a" "b") ("c" "d") ("d" "c"))
;;No duplicates removed


My question regarding indexing was not how it could be done on a single
sort but how it could accomplish a mult-level sort.

Lets say that the list is to be first sorted by one key and then by another
key and then by a third key. Since the original list wouldn't have changed
its order (only an index list was made), how could the second and third
sorts refine the first sort?

Regards,
Doug

"Tony Tanzillo" wrote in message news:33B6A4F5DBF4CFC19BCAA175362D8BF2@in.WebX.maYIadrTaRb...
> "Doug Broad" wrote in message
> news:2E3275ADEF1AE048E2F7A82BEC990F27@in.WebX.maYIadrTaRb...
> > Excellent point about the removal of duplicates.
> > The removal behavior, however, seems to be limited
> > to lists of integers.
>
> In fact, it doesn't (at least, not on the copy of
> AutoCAD 2000 I just tried it on).
>
> Try this:
>
> (defun compare-elements (a b sortspec)
> ( (lambda (x y test)
> (if (and (equal x y fuzz) (cdr sortspec))
> (compare-elements a b (cdr sortspec))
> (apply test (list x y))
> )
> )
> (nth (cdar sortspec) a)
> (nth (cdar sortspec) b)
> (caar sortspec)
> )
> )
>
> (defun complex-sort (alist sortspec)
> (mapcar
> '(lambda (i)
> (nth i alist)
> )
> (vl-sort-i alist
> '(lambda (a b)
> (compare-elements a b sortspec)
> )
> )
> )
> )
>
> (defun complex-sort-bad (alist sortspec)
> (vl-sort alist
> '(lambda (a b)
> (compare-elements a b sortspec)
> )
> )
> )
>
>
> ;; TEST
>
> (defun C:TESTIT ( / lst res)
>
> (setq lst
> '( ("D" "a" 3 2 1)
> ("B" "c" 2 1 3)
> ("B" "a" 2 1 3)
> ("D" "b" 3 2 1)
> ("E" "a" 2 2 1)
> ("C" "b" 1 3 2)
> ("D" "b" 0 2 1)
> )
> )
> (repeat 5 (setq lst (append lst lst)))
> (princ (strcat "\nInput list length: " (itoa (length lst))))
> (setq res
> (complex-sort-bad
> lst
> '((< . 1) (< . 3) (< . 0)) ; sort specification
> )
> )
> (mapcar 'print res)
> (princ (strcat "\nResult list length: " (itoa (length res))))
> (princ)
> )
>
> ;; Here is what I get:
>
> Command: testit
>
> Input list length: 224
> ("B" "a" 2 1 3)
> ("D" "a" 3 2 1)
> ("E" "a" 2 2 1)
> ("D" "b" 0 2 1)
> ("D" "b" 0 2 1)
> ("D" "b" 0 2 1)
> ("D" "b" 0 2 1)
> ("D" "b" 3 2 1)
> ("D" "b" 3 2 1)
> ("D" "b" 0 2 1)
> ("D" "b" 0 2 1)
> ("D" "b" 3 2 1)
> ("D" "b" 0 2 1)
> ("D" "b" 3 2 1)
> ("D" "b" 0 2 1)
> ("C" "b" 1 3 2)
> ("B" "c" 2 1 3)
> Result list length: 17
>
>
> > It does not occur with lists of strings or lists
> > or lists of lists or lists of reals.
> > The behavior is strangely incosistent.
>
> See above.
>
> >
> > The index method is very intriguing but how would you use the
> > indexing method to accomplish the multi-stage sort that Mike is thinking
> about?
>
> Indexing is just like sorting except that the original
> data is not rearranged. Instead, indexing generates just
> the information required to describe the original data in
> a given sorted order (in this case, a list of integers
> representing the indices of each element in the sorted
> order is all that's required).
>
> This is indexing:
>
>
> (setq index (vl-sort-i '>) ;; descending
> (setq index2 (vl-sort-i '<) ;; ascending
>
> The result are two lists of integers, that you can use
> to process the list in sorted order using:
>
> (mapcar
> '(lambda (i)
> (SomeProcessingFunction (nth i ))
> )
>
> )
>
> In otherwords, sorting is something that is often done
> in advance of processing the resulting sorted list in
> the sorted order.
>
> So, really it's not necessary to generate a sorted copy
> of the original list, when you can generate just a list
> of integers describing the sorted order, which can be
> used to process the original data in the sorted order.
>
>
>
>

[Anonymous]

"Doug Broad" wrote in message
news:505BC882E60EB2F966998DB3BF3A4FE8@in.WebX.maYIadrTaRb...
> Tony,

> My comments regarding deletion of elements were concerning ACAD's version
> of vl-sort, not on your compare-elements subroutine, which seems to always
> delete duplicates.

It's not my code that's deleting the elements, it's
AutoCAD's (VL-SORT) function (which is called by the
one of the two versions of (complex-sort)).

Here is a verbatim transcript straight from the command line:

Command: (setq alist '((1 2 3) (4 5 6) (7 8 9)))
((1 2 3) (4 5 6) (7 8 9))

Command: (repeat 3 (setq alist (append alist alist)))
((1 2 3) (4 5 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9) (1
2
3) (4 5 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9) (1 2 3)
(4 5
6) (7 8 9) (1 2 3) (4 5 6) (7 8 9))

Command: (vl-sort alist '(lambda (x y) (> (car x) (car y))))
((7 8 9) (4 5 6) (1 2 3))

The reason why this is happening is because of how
the list is constructed (using append), and in fact,
the list 'alist' in the above, only contains three
unique elements. The remaining elements are merely
copies of one of those three unique elements, as can
be seen here:

Command: (setq foo '(1 2 3))
(1 2 3)

Command: (setq list1 (list foo foo))
((1 2 3) (1 2 3))

Command: (setq list2 (list foo '(1 2 3)))
((1 2 3) (1 2 3))

Command: (equal list1 list2)
T

So list1 and list2 are the same, right?
Well, no not really:

Command: (eq (car list1) (cadr list1))
T

Command: (eq (car list2) (cadr list2))
nil

Notice that even though list1 and list2 *appear* to
be identical (and equal says they are), in fact they
are very different. As the (eq) function discloses,
list1 contains two *copies* of the same list (the same
list that is assigned to 'foo'), while list2 contains
two completely different lists. In fact, list1 consumes
only half the memory consumed by list2.

This is why (vl-sort) can sometimes remove lists, namely
in cases where they are actually the same list (and I
believe this is a bug).

And because it is entirely unpredicable as to whether a
given list may contain multiple copies of the same element,
you should *never* use (vl-sort) for complex list sorting.


> My question regarding indexing was not how it could be done on a single
> sort but how it could accomplish a mult-level sort.

If a 'multi-level sort' means to sort on multiple keys,
doing that does not require multiple sorts.

> Lets say that the list is to be first sorted by one key
> and then by another key and then by a third key.

Yes, that's exactly what (complex-sort) does. It sorts on
multiple keys, but it doesn't have to sort the list more
than once to do that.

A multi-key sort or index can be performed by a single sort
or indexing operation. the trick is in how the comparison is
done. The comparison function (compare-elements) takes two
lists that it must compare. To do that, it first looks at the
first (or 'primary') sort key's value for each list, and if
they're equal then it looks at the next sort key's values and
if they're equal then it looks at the next sort key's values,
ad infinitum.

If any sort key's values are not equal then there is no
need to compare any further sort key values for the same
two elements because the relative order of the two elements
being compared has been determined.

Given (compare-elements), this is all you need to index a
list on multiple keys:

(defun complex-index (lst sortspec)
(vl-sort-i lst
'(lambda (a b)
(compare-elements a b sortspec)
)
)
)

[Anonymous]

Tony:

You've outdone even yourself this time. Nice get! Thanks for taking the time
to explain.

--
John Uhden, Cadlantic/formerly CADvantage
http://www.cadlantic.com
Sea Girt, NJ


"Tony Tanzillo" wrote in message
news:26B310A0EDBB66E0BEBF8704A6406508@in.WebX.maYIadrTaRb...
> "Doug Broad" wrote in message
> news:505BC882E60EB2F966998DB3BF3A4FE8@in.WebX.maYIadrTaRb...
> > Tony,
>
> > My comments regarding deletion of elements were concerning ACAD's version
> > of vl-sort, not on your compare-elements subroutine, which seems to always
> > delete duplicates.
>
> It's not my code that's deleting the elements, it's
> AutoCAD's (VL-SORT) function (which is called by the
> one of the two versions of (complex-sort)).
>
> Here is a verbatim transcript straight from the command line:
>
> Command: (setq alist '((1 2 3) (4 5 6) (7 8 9)))
> ((1 2 3) (4 5 6) (7 8 9))
>
> Command: (repeat 3 (setq alist (append alist alist)))
> ((1 2 3) (4 5 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9) (1
> 2
> 3) (4 5 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9) (1 2 3)
> (4 5
> 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9))
>
> Command: (vl-sort alist '(lambda (x y) (> (car x) (car y))))
> ((7 8 9) (4 5 6) (1 2 3))
>
> The reason why this is happening is because of how
> the list is constructed (using append), and in fact,
> the list 'alist' in the above, only contains three
> unique elements. The remaining elements are merely
> copies of one of those three unique elements, as can
> be seen here:
>
> Command: (setq foo '(1 2 3))
> (1 2 3)
>
> Command: (setq list1 (list foo foo))
> ((1 2 3) (1 2 3))
>
> Command: (setq list2 (list foo '(1 2 3)))
> ((1 2 3) (1 2 3))
>
> Command: (equal list1 list2)
> T
>
> So list1 and list2 are the same, right?
> Well, no not really:
>
> Command: (eq (car list1) (cadr list1))
> T
>
> Command: (eq (car list2) (cadr list2))
> nil
>
> Notice that even though list1 and list2 *appear* to
> be identical (and equal says they are), in fact they
> are very different. As the (eq) function discloses,
> list1 contains two *copies* of the same list (the same
> list that is assigned to 'foo'), while list2 contains
> two completely different lists. In fact, list1 consumes
> only half the memory consumed by list2.
>
> This is why (vl-sort) can sometimes remove lists, namely
> in cases where they are actually the same list (and I
> believe this is a bug).
>
> And because it is entirely unpredicable as to whether a
> given list may contain multiple copies of the same element,
> you should *never* use (vl-sort) for complex list sorting.
>
>
> > My question regarding indexing was not how it could be done on a single
> > sort but how it could accomplish a mult-level sort.
>
> If a 'multi-level sort' means to sort on multiple keys,
> doing that does not require multiple sorts.
>
> > Lets say that the list is to be first sorted by one key
> > and then by another key and then by a third key.
>
> Yes, that's exactly what (complex-sort) does. It sorts on
> multiple keys, but it doesn't have to sort the list more
> than once to do that.
>
> A multi-key sort or index can be performed by a single sort
> or indexing operation. the trick is in how the comparison is
> done. The comparison function (compare-elements) takes two
> lists that it must compare. To do that, it first looks at the
> first (or 'primary') sort key's value for each list, and if
> they're equal then it looks at the next sort key's values and
> if they're equal then it looks at the next sort key's values,
> ad infinitum.
>
> If any sort key's values are not equal then there is no
> need to compare any further sort key values for the same
> two elements because the relative order of the two elements
> being compared has been determined.
>
> Given (compare-elements), this is all you need to index a
> list on multiple keys:
>
> (defun complex-index (lst sortspec)
> (vl-sort-i lst
> '(lambda (a b)
> (compare-elements a b sortspec)
> )
> )
> )
>
>
>
>
>
>

[Anonymous]

I agree with John. Superb explanation. Thanks again Tony. It does
appear that vl-sort has a fatal flaw. Thanks for the detailed analysis.
I tested it also on strings and found the same behavior.

Thanks also for the answer to the mult-key sort question. I appreciate
the time you took.

Regards,
Doug


"John Uhden" wrote in message news:98FB03E84D8B377BD760F78667F26A48@in.WebX.maYIadrTaRb...
> Tony:
>
> You've outdone even yourself this time. Nice get! Thanks for taking the time
> to explain.
>
> --
> John Uhden, Cadlantic/formerly CADvantage
> http://www.cadlantic.com
> Sea Girt, NJ
>
>
> "Tony Tanzillo" wrote in message
> news:26B310A0EDBB66E0BEBF8704A6406508@in.WebX.maYIadrTaRb...
> > "Doug Broad" wrote in message
> > news:505BC882E60EB2F966998DB3BF3A4FE8@in.WebX.maYIadrTaRb...
> > > Tony,
> >
> > > My comments regarding deletion of elements were concerning ACAD's version
> > > of vl-sort, not on your compare-elements subroutine, which seems to always
> > > delete duplicates.
> >
> > It's not my code that's deleting the elements, it's
> > AutoCAD's (VL-SORT) function (which is called by the
> > one of the two versions of (complex-sort)).
> >
> > Here is a verbatim transcript straight from the command line:
> >
> > Command: (setq alist '((1 2 3) (4 5 6) (7 8 9)))
> > ((1 2 3) (4 5 6) (7 8 9))
> >
> > Command: (repeat 3 (setq alist (append alist alist)))
> > ((1 2 3) (4 5 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9) (1
> > 2
> > 3) (4 5 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9) (1 2 3)
> > (4 5
> > 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9))
> >
> > Command: (vl-sort alist '(lambda (x y) (> (car x) (car y))))
> > ((7 8 9) (4 5 6) (1 2 3))
> >
> > The reason why this is happening is because of how
> > the list is constructed (using append), and in fact,
> > the list 'alist' in the above, only contains three
> > unique elements. The remaining elements are merely
> > copies of one of those three unique elements, as can
> > be seen here:
> >
> > Command: (setq foo '(1 2 3))
> > (1 2 3)
> >
> > Command: (setq list1 (list foo foo))
> > ((1 2 3) (1 2 3))
> >
> > Command: (setq list2 (list foo '(1 2 3)))
> > ((1 2 3) (1 2 3))
> >
> > Command: (equal list1 list2)
> > T
> >
> > So list1 and list2 are the same, right?
> > Well, no not really:
> >
> > Command: (eq (car list1) (cadr list1))
> > T
> >
> > Command: (eq (car list2) (cadr list2))
> > nil
> >
> > Notice that even though list1 and list2 *appear* to
> > be identical (and equal says they are), in fact they
> > are very different. As the (eq) function discloses,
> > list1 contains two *copies* of the same list (the same
> > list that is assigned to 'foo'), while list2 contains
> > two completely different lists. In fact, list1 consumes
> > only half the memory consumed by list2.
> >
> > This is why (vl-sort) can sometimes remove lists, namely
> > in cases where they are actually the same list (and I
> > believe this is a bug).
> >
> > And because it is entirely unpredicable as to whether a
> > given list may contain multiple copies of the same element,
> > you should *never* use (vl-sort) for complex list sorting.
> >
> >
> > > My question regarding indexing was not how it could be done on a single
> > > sort but how it could accomplish a mult-level sort.
> >
> > If a 'multi-level sort' means to sort on multiple keys,
> > doing that does not require multiple sorts.
> >
> > > Lets say that the list is to be first sorted by one key
> > > and then by another key and then by a third key.
> >
> > Yes, that's exactly what (complex-sort) does. It sorts on
> > multiple keys, but it doesn't have to sort the list more
> > than once to do that.
> >
> > A multi-key sort or index can be performed by a single sort
> > or indexing operation. the trick is in how the comparison is
> > done. The comparison function (compare-elements) takes two
> > lists that it must compare. To do that, it first looks at the
> > first (or 'primary') sort key's value for each list, and if
> > they're equal then it looks at the next sort key's values and
> > if they're equal then it looks at the next sort key's values,
> > ad infinitum.
> >
> > If any sort key's values are not equal then there is no
> > need to compare any further sort key values for the same
> > two elements because the relative order of the two elements
> > being compared has been determined.
> >
> > Given (compare-elements), this is all you need to index a
> > list on multiple keys:
> >
> > (defun complex-index (lst sortspec)
> > (vl-sort-i lst
> > '(lambda (a b)
> > (compare-elements a b sortspec)
> > )
> > )
> > )
> >
> >
> >
> >
> >
> >
>

[Anonymous]

Maestro!

Why don't you give us a seminar or workshop, I really would like to attend
to one and have the chance to meet you in person and learn more from you.

Very excellent Tony.

Regards,
Luis.

[Anonymous]

Tony,

Would there be a faster fix for VL-SORT than the following
(assuming we are not trying to support R14)?

;;approximately 4-6 times slower than vl-sort but without the flaws
(defun vlsort (lst comparefun / ndx)
(setq ndx (vl-sort-i lst comparefun))
(mapcar (function(lambda (n) (nth n lst))) ndx))

Can the NTH search be improved?

[Anonymous]

Thanks so much as well.
I have a complex sort that must happen within my application...
and your explainations make a certain amount of sense (given my reletively low
level of expertise).
<< you should *never* use (vl-sort) for complex list sorting.>>
... I wonder if Vl-sort can still be relied upon in my case? My lists are
constructed from data pulled from attribute laden autocad blocks. The data is
minipulated, counted, organized then sorted. There really should not be any
dups (yet to be determined.) But if there are the dups most likely will not be
exact copies... then again it may a bit early.
perhaps I should use vl-sort-i instead ?


Tony Tanzillo wrote:

> "Doug Broad" wrote in message
> news:505BC882E60EB2F966998DB3BF3A4FE8@in.WebX.maYIadrTaRb...
> > Tony,
>
> > My comments regarding deletion of elements were concerning ACAD's version
> > of vl-sort, not on your compare-elements subroutine, which seems to always
> > delete duplicates.
>
> It's not my code that's deleting the elements, it's
> AutoCAD's (VL-SORT) function (which is called by the
> one of the two versions of (complex-sort)).
>
> Here is a verbatim transcript straight from the command line:
>
> Command: (setq alist '((1 2 3) (4 5 6) (7 8 9)))
> ((1 2 3) (4 5 6) (7 8 9))
>
> Command: (repeat 3 (setq alist (append alist alist)))
> ((1 2 3) (4 5 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9) (1
> 2
> 3) (4 5 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9) (1 2 3)
> (4 5
> 6) (7 8 9) (1 2 3) (4 5 6) (7 8 9))
>
> Command: (vl-sort alist '(lambda (x y) (> (car x) (car y))))
> ((7 8 9) (4 5 6) (1 2 3))
>
> The reason why this is happening is because of how
> the list is constructed (using append), and in fact,
> the list 'alist' in the above, only contains three
> unique elements. The remaining elements are merely
> copies of one of those three unique elements, as can
> be seen here:
>
> Command: (setq foo '(1 2 3))
> (1 2 3)
>
> Command: (setq list1 (list foo foo))
> ((1 2 3) (1 2 3))
>
> Command: (setq list2 (list foo '(1 2 3)))
> ((1 2 3) (1 2 3))
>
> Command: (equal list1 list2)
> T
>
> So list1 and list2 are the same, right?
> Well, no not really:
>
> Command: (eq (car list1) (cadr list1))
> T
>
> Command: (eq (car list2) (cadr list2))
> nil
>
> Notice that even though list1 and list2 *appear* to
> be identical (and equal says they are), in fact they
> are very different. As the (eq) function discloses,
> list1 contains two *copies* of the same list (the same
> list that is assigned to 'foo'), while list2 contains
> two completely different lists. In fact, list1 consumes
> only half the memory consumed by list2.
>
> This is why (vl-sort) can sometimes remove lists, namely
> in cases where they are actually the same list (and I
> believe this is a bug).
>
> And because it is entirely unpredicable as to whether a
> given list may contain multiple copies of the same element,
> you should *never* use (vl-sort) for complex list sorting.
>
> > My question regarding indexing was not how it could be done on a single
> > sort but how it could accomplish a mult-level sort.
>
> If a 'multi-level sort' means to sort on multiple keys,
> doing that does not require multiple sorts.
>
> > Lets say that the list is to be first sorted by one key
> > and then by another key and then by a third key.
>
> Yes, that's exactly what (complex-sort) does. It sorts on
> multiple keys, but it doesn't have to sort the list more
> than once to do that.
>
> A multi-key sort or index can be performed by a single sort
> or indexing operation. the trick is in how the comparison is
> done. The comparison function (compare-elements) takes two
> lists that it must compare. To do that, it first looks at the
> first (or 'primary') sort key's value for each list, and if
> they're equal then it looks at the next sort key's values and
> if they're equal then it looks at the next sort key's values,
> ad infinitum.
>
> If any sort key's values are not equal then there is no
> need to compare any further sort key values for the same
> two elements because the relative order of the two elements
> being compared has been determined.
>
> Given (compare-elements), this is all you need to index a
> list on multiple keys:
>
> (defun complex-index (lst sortspec)
> (vl-sort-i lst
> '(lambda (a b)
> (compare-elements a b sortspec)
> )
> )
> )

[Anonymous]

"Tony Tanzillo" writes:

> Notice that even though list1 and list2 *appear* to
> be identical (and equal says they are), in fact they
> are very different. As the (eq) function discloses,
> list1 contains two *copies* of the same list (the same
> list that is assigned to 'foo'), while list2 contains
> two completely different lists.

The behaviour with string is certainly odd. In
Autolisp any two string are eq if they are
equal. But vl-sort doesn't follow this convention:

Command: (setq b '("a" "b" "a" "c" "f" "c"))
("a" "b" "a" "c" "f" "c")

Command: (vl-sort b '<)
("a" "a" "b" "c" "c" "f")

Command: (setq str1 "a")
"a"

Command: (setq c (list str1 "b" "c" "b" str1 str1))
("a" "b" "c" "b" "a" "a")

Command: (vl-sort c '<)
("a" "b" "b" "c")

Command: (eq "a" "a")
T

Command: (eq "a" str1)
T

Command: (setq str2 "a")
"a"

Command: (eq str1 str2)
T

It seems that vl-sort uses some kind of internal
eq function so that it will only remove "real-eq"
strings.


--

Eduardo Muñoz

[Anonymous]

Jumping in late here.... 🙂

It looks like vl-sort considers elements as duplicates to be removed if their
memory addresses are the same (the technique popular in C-programming).
Append really creates duplicates in that sense.

See this:

Command: (setq lstl '(("a" "b")("a" "b")("c" "d")("d" "c")("a" "b")))
(("a" "b") ("a" "b") ("c" "d") ("d" "c") ("a" "b"))

Command: (vl-sort lstl '(lambda (a b) (< (car a)(car b))))
(("a" "b") ("a" "b") ("a" "b") ("c" "d") ("d" "c"))

Command: (Setq lstl2 (append lstl lstl))
(("a" "b") ("a" "b") ("c" "d") ("d" "c") ("a" "b") ("a" "b") ("a" "b") ("c"
"d") ("d" "c") ("a" "b"))

Command: (vl-sort lstl2 '(lambda (a b) (< (car a)(car b))))
(("a" "b") ("a" "b") ("a" "b") ("a" "b") ("a" "b") ("c" "d") ("d" "c"))

..... only 7 elements instead of 10 !
This is obviously some inconsistent behavior. We can probably
prevent it if we pass vl-sort the copy of our lists.

Command: (defun copy-llist (x) ; works on list of lists
(_> (if x (cons
(((_> (mapcar '(lambda(e) e) (car x)) ; rebuild sub-lists
(((_> (copy-llist (cdr x)))))
COPY-LLIST

Command: (vl-sort (copy-llist lstl2) '(lambda (a b) (< (car a)(car b))))
(("a" "b") ("a" "b") ("a" "b") ("a" "b") ("a" "b") ("a" "b") ("c" "d") ("c"
"d") ("d" "c") ("d" "c"))




Doug Broad wrote in message news:505BC882E60EB2F966998DB3BF3A4FE8@in.WebX.maYIadrTaRb...
> Tony,
> My comments regarding deletion of elements were concerning ACAD's version
> of vl-sort, not on your compare-elements subroutine, which seems to always
> delete duplicates.
>
> Deleting duplicates may be advantageous (if it is the desired behavior). It
> might be more desirable to have the calling function decide how duplicates
> are handled. Your function is very consistent but AutoCAD's VL-SORT is
> not as consistent.
>
> ;;Here are some of my tests on AC2002/ADT 3.3
>
> (setq lsti '( 1 2 3 1 4 1 5))
> (1 2 3 1 4 1 5)
> _$ (vl-sort lsti '<)
> (1 2 3 4 5)
> ;;vl-sort removed the duplicate integers
> _$ (vl-sort lsti '>)
> (5 4 3 2 1)
> ;;Same thing
> _$ (setq lsts '("a" "b" "a" "b" "c" "b" "a"))
> ("a" "b" "a" "b" "c" "b" "a")
> _$ (vl-sort lsts '>)
> ("c" "b" "b" "b" "a" "a" "a")
> ;;No duplicates removed
> _$ (vl-sort lsts '<)
> ("a" "a" "a" "b" "b" "b" "c")
> ;;No duplicates removed
> (setq lstl '(("a" "b" 1)("b" "c" 1) ("c" "a" 1)))
> (("a" "b" 1) ("b" "c" 1) ("c" "a" 1))
> _$ (vl-sort lstl '(lambda (a b) (< (caddr a)(caddr b))))
> (("a" "b" 1) ("b" "c" 1) ("c" "a" 1))
> ;;No duplicates removed - but no identical elements anyway
> (setq lstl '(("a" "b")("a" "b")("c" "d")("d" "c")("a" "b")))
> (("a" "b") ("a" "b") ("c" "d") ("d" "c") ("a" "b"))
> _$ (vl-sort lstl '(lambda (a b) (< (car a)(car b))))
> (("a" "b") ("a" "b") ("a" "b") ("c" "d") ("d" "c"))
> ;;No duplicates removed
>
>
> My question regarding indexing was not how it could be done on a single
> sort but how it could accomplish a mult-level sort.
>
> Lets say that the list is to be first sorted by one key and then by another
> key and then by a third key. Since the original list wouldn't have changed
> its order (only an index list was made), how could the second and third
> sorts refine the first sort?
>
> Regards,
> Doug
>
> "Tony Tanzillo" wrote in message news:33B6A4F5DBF4CFC19BCAA175362D8BF2@in.WebX.maYIadrTaRb...
> > "Doug Broad" wrote in message
> > news:2E3275ADEF1AE048E2F7A82BEC990F27@in.WebX.maYIadrTaRb...
> > > Excellent point about the removal of duplicates.
> > > The removal behavior, however, seems to be limited
> > > to lists of integers.
> >
> > In fact, it doesn't (at least, not on the copy of
> > AutoCAD 2000 I just tried it on).
> >
> > Try this:
> >
> > (defun compare-elements (a b sortspec)
> > ( (lambda (x y test)
> > (if (and (equal x y fuzz) (cdr sortspec))
> > (compare-elements a b (cdr sortspec))
> > (apply test (list x y))
> > )
> > )
> > (nth (cdar sortspec) a)
> > (nth (cdar sortspec) b)
> > (caar sortspec)
> > )
> > )
> >
> > (defun complex-sort (alist sortspec)
> > (mapcar
> > '(lambda (i)
> > (nth i alist)
> > )
> > (vl-sort-i alist
> > '(lambda (a b)
> > (compare-elements a b sortspec)
> > )
> > )
> > )
> > )
> >
> > (defun complex-sort-bad (alist sortspec)
> > (vl-sort alist
> > '(lambda (a b)
> > (compare-elements a b sortspec)
> > )
> > )
> > )
> >
> >
> > ;; TEST
> >
> > (defun C:TESTIT ( / lst res)
> >
> > (setq lst
> > '( ("D" "a" 3 2 1)
> > ("B" "c" 2 1 3)
> > ("B" "a" 2 1 3)
> > ("D" "b" 3 2 1)
> > ("E" "a" 2 2 1)
> > ("C" "b" 1 3 2)
> > ("D" "b" 0 2 1)
> > )
> > )
> > (repeat 5 (setq lst (append lst lst)))
> > (princ (strcat "\nInput list length: " (itoa (length lst))))
> > (setq res
> > (complex-sort-bad
> > lst
> > '((< . 1) (< . 3) (< . 0)) ; sort specification
> > )
> > )
> > (mapcar 'print res)
> > (princ (strcat "\nResult list length: " (itoa (length res))))
> > (princ)
> > )
> >
> > ;; Here is what I get:
> >
> > Command: testit
> >
> > Input list length: 224
> > ("B" "a" 2 1 3)
> > ("D" "a" 3 2 1)
> > ("E" "a" 2 2 1)
> > ("D" "b" 0 2 1)
> > ("D" "b" 0 2 1)
> > ("D" "b" 0 2 1)
> > ("D" "b" 0 2 1)
> > ("D" "b" 3 2 1)
> > ("D" "b" 3 2 1)
> > ("D" "b" 0 2 1)
> > ("D" "b" 0 2 1)
> > ("D" "b" 3 2 1)
> > ("D" "b" 0 2 1)
> > ("D" "b" 3 2 1)
> > ("D" "b" 0 2 1)
> > ("C" "b" 1 3 2)
> > ("B" "c" 2 1 3)
> > Result list length: 17
> >
> >
> > > It does not occur with lists of strings or lists
> > > or lists of lists or lists of reals.
> > > The behavior is strangely incosistent.
> >
> > See above.
> >
> > >
> > > The index method is very intriguing but how would you use the
> > > indexing method to accomplish the multi-stage sort that Mike is thinking
> > about?
> >
> > Indexing is just like sorting except that the original
> > data is not rearranged. Instead, indexing generates just
> > the information required to describe the original data in
> > a given sorted order (in this case, a list of integers
> > representing the indices of each element in the sorted
> > order is all that's required).
> >
> > This is indexing:
> >
> >
> > (setq index (vl-sort-i '>) ;; descending
> > (setq index2 (vl-sort-i '<) ;; ascending
> >
> > The result are two lists of integers, that you can use
> > to process the list in sorted order using:
> >
> > (mapcar
> > '(lambda (i)
> > (SomeProcessingFunction (nth i ))
> > )
> >
> > )
> >
> > In otherwords, sorting is something that is often done
> > in advance of processing the resulting sorted list in
> > the sorted order.
> >
> > So, really it's not necessary to generate a sorted copy
> > of the original list, when you can generate just a list
> > of integers describing the sorted order, which can be
> > used to process the original data in the sorted order.
> >
> >
> >
> >
>
>

[Anonymous]

"Vladimir Nesterovsky" wrote in message
news:100E0D46A615C1E5ADB6EF3499E3B2B8@in.WebX.maYIadrTaRb...
> Jumping in late here.... 🙂
>
> It looks like vl-sort considers elements as duplicates to be removed if
their
> memory addresses are the same (the technique popular in C-programming).
> Append really creates duplicates in that sense.

Thanks for repeating what I said 🙂

[Anonymous]

Tony Tanzillo wrote in message news:0B967D4FFD29C5B6F4972616D8A601A9@in.WebX.maYIadrTaRb...
> Visual LISP is somewhat different in terms of how it
> handles recursion (it's said to be 'properly tail
> recursive'),

Really? Where? I don't think that's true, judging from this crude
example:

(defun t1 (i / a)
(princ "\n...Testing...")
(repeat i ;;19973 is the max
(setq a (cons 1 a)))
(t2 a))

(defun t2 (x) ; a tail-recursive function
(if (null x)
'OK
(t2 (cdr x))))

In IDE on running (t1 19973) it says ...Testing...OK
but for any number greater then the threshold it just prints ...Testing... ,
meaning, it didn't even return a value. That's hardly 'proper'.

I thought there's no limit to recursion stack if working w/out IDE, only
on command line, but still it caused an error:

(t1 19996)

...Testing...Hard error occurred ***
internal stack limit reached (simulated)

which means it does use the stack to handle tail-recursion,
which it should not do. I think Vital Lisp RTS had no internal
limit to stack depth, but having no limit and not using
the stack is two very different things.

But that's hardly a problem here, since any tail-recursive function
can be re-written into an iterative one (using 'while'), so no need
to tempt fate:

(defun compare-elements (a b sortspec / x y test done result)
(while (and (not done) sortspec)
(setq x (nth (cdar sortspec) a)
y (nth (cdar sortspec) b)
test (caar sortspec))
(if (equal x y fuzz)
(setq sortspec (cdr sortspec))
(setq result (apply test (list x y))
done 't)))
result)

Actually, I think compiled separate-name VLX also has no limit
to its stack depth like Vital RTS did, but I didn't check this.


> and in fact, you can recurse very deeply
> (much more than you could in legacy AutoLISP) without
> a stack overflow.
>
> And as you mention, the chances that a routine like
> this will ever exhaust the stack are slim-to-none,
> since it would require a scenario where the list that
> is sorted has elements with hundreds of sub-elements,
> and where you are sorting on hundreds of sort keys 🙂
>
> "Doug Broad" wrote in message
> news:EC11936A0CE625797D49150E44E6DEAA@in.WebX.maYIadrTaRb...
> > Sorry Tony,
> > It is very very doubtful that "stack overflow" would EVER occur with your
> code
> > especially given the arguments anticipated. In the past with recursive
> > procedures, I have run into the problem of stack overflow. It hasn't
> > happened to me yet with AC2002 but I have learned to be very careful.
> > I am sure you know what the term "stack overflow" means but
> > for the benefit of others reading, I excerpt from the help files:
> >

[Anonymous]

"Vladimir Nesterovsky" wrote in message
news:EB9243337E79F2DF80FEC0BEB22B426F@in.WebX.maYIadrTaRb...
> Tony Tanzillo wrote in message
news:0B967D4FFD29C5B6F4972616D8A601A9@in.WebX.maYIadrTaRb...
> > Visual LISP is somewhat different in terms of how it
> > handles recursion (it's said to be 'properly tail
> > recursive'),
>
> Really? Where? I don't think that's true...

Have you tried compiling?


>
> But that's hardly a problem here, since any tail-recursive function
> can be re-written into an iterative one (using 'while'), so no need
> to tempt fate:

I'm sorry, but I really find absolutely no point
in this sort of theoretical nonsense.

The fact of the matter is that under no real-world
circumstance would a recusive solution to compare-elements
*ever* reach the stack limit.

You would be eaten alive by a grizzly bear first.

[Anonymous]

Tony Tanzillo wrote in message news:0C445DD9E82A4623C7AD6C3AEF496F8F@in.WebX.maYIadrTaRb...
> "Vladimir Nesterovsky" wrote in message
> news:EB9243337E79F2DF80FEC0BEB22B426F@in.WebX.maYIadrTaRb...
> > Tony Tanzillo wrote in message
> news:0B967D4FFD29C5B6F4972616D8A601A9@in.WebX.maYIadrTaRb...
> > > Visual LISP is somewhat different in terms of how it
> > > handles recursion (it's said to be 'properly tail
> > > recursive'),
> >
> > Really? Where? I don't think that's true...
>
> Have you tried compiling?

No, I'll try that later. But again, no limit on stack and no usage of stack
is different things.

Even if compiled code runs with no limit we can still detect the difference.
The properly handled tail-recursive code will run forever since it won't
consume any more resources as it works; the improperly handled,
no-stack-limited-code will continually consume more and more memory
and thus will eventually run out of available resources ---- although, on
modern kind of computers this can take a little while. 🙂

> > But that's hardly a problem here, since any tail-recursive function
> > can be re-written into an iterative one (using 'while'), so no need
> > to tempt fate:
>
> I'm sorry, but I really find absolutely no point
> in this sort of theoretical nonsense.

I thought providing an actual re-write makes it practical. 🙂

> The fact of the matter is that under no real-world
> circumstance would a recusive solution to compare-elements
> *ever* reach the stack limit.

Of course. I never argued that.

> You would be eaten alive by a grizzly bear first.

Not if I never go to forest I won't. 🙂