All Sorts of Possibilitiles (Harry's Code Class Newsletter)

Visual LISP offers built-in and definable options for automatically arranging data in ascending, descending, or alphabetical order.

At some time in your AutoCAD programming adventures, you will find yourself working with a collection, or list, of data accumulated from a drawing or from user input. The list could be a series of coordinates or block names used in the drawing, including a count. If you need to report the data in some fashion, chances are good you will want to put that data in a sequence. Sequencing or ordering data based on simple rules is known as sorting.

Data sorting happens a lot in computer programming. You may be alphabetizing names or arranging numbers in ascending or descending order. Visual LISP provides two very easy-to-use functions: VL-SORT and VL-SORT-I. Both are essentially the same, except for the results they return. VL-SORT returns a list of the sorted data; VL-SORT-I returns a list of indices into the source list representing the sequenced order.

Basics of Sorting
Before we can investigate sorting in Visual LISP, we must get a handle on some list and sort programming concepts. Sorting applies only to data that is related in some fashion. The sort action works with the related data, comparing each item and determining which should appear in front of the other. When you run a LISP routine that produces a list of data, you have absolute control over how the data will appear in the list. What you may not have absolute control over is the order in which data is added to the list. That is when sorting comes into play.

Data is most often sorted for presentation purposes in Visual LISP. Sorted data lists can be used in dialog boxes, reports, and tables created in a drawing. A classic example is a list of part numbers with a counter that tracks each time the part number is used in the drawing. You may want to create a report that lists those parts in order by part number or by quantity. Sorting allows you to create either report from the same data set.

LISP allows us to create lists of any description, where description implies a scheme, definition, or map of data. However, for purposes of a sort (as noted earlier), list members must have the same general description. For sorts to work successfully, you must keep in mind a simple rule of thumb when determining how data will be stored: Define a key. Each member of a suitable data list will contain an element, called a key, that is meant to be sequenced. In most applications, you will want the key value of each member to be unique. An example of a key element could be a part number or block name. Beyond a key, the contents of each member of a list to be sorted -- where contents refers to the actual data expressed as a general term -- are entirely up to the programmer.

Swap Test
The basic workhorse in any sorting system is the swap test. The swap test is a predicate to determine if two elements from your data list are in the right order. If not, the two elements need to be swapped. The speed of a Visual LISP sorting system is based on the complexity of the swap test. Internally, Visual LISP is implementing the same sort algorithm and will require a significantly increasing amount of time based on the number of elements to be sorted as well as the initial order of the data. Generally, the sorting action is very fast for reasonably sized lists and a relatively basic swap test.

VL-SORT and VL-SORT-I are both supplied a list and a swap test. The swap test is supplied as a quoted function that accepts two arguments and produces a T (true) result if the two arguments are in the right order, or an NIL (false) result if not. The simplest example is '< and '>. The '< is a "less than" test and will return T if the first value is less than the second value. Less-than testing can be used to create a list of numbers in ascending order. Using "greater than" '> will produce a list of numbers in descending order.

(setq aList '(10 5 3 1 8 9 2)) creates a list of seven members in which each member is an integer. To sort the list in ascending sequence, you can use the expression (vl-sort aList '<). The result would be (1 2 3 5 8 9 10) and can be set to a new symbol or back into the symbol of the source list, as in the following:

 (setq aList (vl-sort aList '<))

When the Basics Won't Do
If you need to do more than simple tests, you'll have to define a function. Functions for a swap test return either T (true) or NIL (false). The true result means that the two elements being tested are in the order desired. False indicates the need for a swap.

A function for a swap test receives two values. Each is a list element from the source list. Inside the function, you can compare the list elements and make a sequence decision, sending back the T or NIL response. Generally a swap test function is short and can be defined using the anonymous LAMBDA function expression.

LAMBDA is used to declare a function-like sequence of code right in the middle of an expression. It operates like a function definition and contains a parameter list that, in the case of a swap test, has two arguments.

To understand the need and application of the LAMBDA, consider a list of points that you desire to sort in ascending X value order. There is no simple function in Visual LISP that accepts two points and returns T if the first one has an X value less than the second. So, we must create one. If this is the only time we are going to do that test, why not just define the function using the LAMBDA expression in place?

(setq aList '((1 1) (0 2) (0.5 3) (3 2))) creates a nested list of points. Each member of the list is a point list consisting of an X and Y element. We want to sort the X elements, or (CAR), of each member in the list.

(vl-sort aList '(lambda (A B) (< (car A) (car B)))) results in the list ((0 2) (0.5 3) (1 1) (3 2)).

The LAMBDA expression defines a temporary function that has two arguments (A and B). This function merely takes the (CAR) or X value from the first argument A and compares it against the X of the second argument B. If the X of A is less than the X of B, then a T (true) is the result. Otherwise, the result is NIL.

LAMBDA helps fill in that void between the defined base functions and our own defined, more complex, functions. It is often employed in other LISP expressions that work with lists, such as MAPCAR.

Value of the Index
You are probably wondering why you would want to use anything other than VL-SORT to sort a list. The index result sort is useful when you are referencing back into another list. For example, suppose we want to sort our point list based on the distance from a known point. One way to code this sort request using the point list aList from above would be as follows:

 (setq basePoint (getpoint "\nSelect the base point: "))
 (setq sList (mapcar '(lambda (P) (distance P basePoint)) aList))

The list sList would now contain a list of the distances from each point in aList to the input basePoint.

 (setq sList (vl-sort-i sList '<))

The above expression will sort the input list sList in ascending order, returning a list of the indices. The nearest point value can be found by using the first index in the result list and the nth function.

 (nth (car sList) aList)

The above expression gets the first index value from sList and uses it to retrieve an nth value out of aList.

Because we were sorting on the distance values and didn't care about them when finished, the index sort was the most sensible choice. The index sort variation is also handy when referencing back to selection sets as the source of data. Suppose the input values in aList originated from a selection set. Index results could be used to retrieve entity data from the selection set as a result of the sort.

There is another reason that many programmers use VL-SORT-I exclusively. VL-SORT will remove duplicate entries in the list before returning the result. For some applications this is useful, but in most cases you will want to preserve the list, and that is where the indexed version is needed.

Sorting Non-Numerical Lists
Sorting is not limited to numbers. You can also sort strings to put a list into alphabetical order. This can be confusing for numbers because the string "011" will come before "10." When sorting strings containing numbers, it is sometimes necessary to convert them to integers first, do the sort, then return the resulting list after converting back to a string. You may want to use the index sort in these instances. Take a close look at the following expressions and results:

(setq aList '("07" "03" "002" "10" "0011" "3")) results in the list ("07" "03" "002" "10" "0011" "3").

(vl-sort alist '<) returns ("0011" "002" "03" "07" "10" "3"), which is obviously not what we intended.

So let's convert the list of strings into integers and save the result with the symbol iList.

(setq iList (mapcar 'atoi aList)) returns (7 3 2 10 11 3).

Can we just sort that list? Not really. Check out the result list and note that there is only one 3 value:

(vl-sort iList '<) returns (2 3 7 10 11).

A better way to solve this is by using the index sort.

(setq iList (vl-sort-i iList '<)) returns (2 5 1 0 3 4).

Now we use the index values in iList to get the original data from aList.

(mapcar '(lambda (I)(nth I aList)) iList) returns ("002" "3" "03" "07" "10" "0011").

Put Sort Routines to Work for You
The sort routines in Visual LISP are quite useful and can be used to create powerful tools. Bills of materials, charts, references, and other tables can be built from the sorted data, meaning you can exploit the intelligence built into a drawing to make your job faster, better, and more fun.

Until next time, keep on programmin'.

Check out these resources for more information and examples of VL-SORT/VL-SORT-I in action:

• Visual LISP System Utilities: Bill Kramer explores features in Visual LISP that relate to the operating system.

• Plant Lists in AutoCAD: In this AutoLISP Solutions column, Tony Hotchkiss presents a routine that calculates plant quantities from landscape architecture drawings to produce a plant list for contractors.

• Reorder List Elements: Here is the thread on Cadalyst's Hot Tip Harry Requests discussion forum that led to this article.

• VL-SORT Examples: A sampling of sorting functions from Bill Kramer's AutoCode Web site.