Lesson 11 List Manipulation

Lists are at the heart of AutoLISP.  You will recall that LISP stands for "LISt Processing."  If you understand lists, and especially how AutoLISP manipulates lists, you will be able to take advantage of some of the more powerful features of AutoLISP.  But before you try to understand how lists are handled, you need to understand how lists are stored in memory.  So we begin with a discussion of list storage, and then the two main functions (car and cdr) which retrieve lists from memory.

When information is stored in memory, AutoLISP must "record" its location so it can be retrieved.  The process of assigning information to a variable (for example, with the setq function) is essentially the process of placing the information at a particular memory address and then associating that address with the user selected symbol (the variable).  Thus, the location of the information is recorded.  In order to retrieve the information, the programmer cites the variable by name.  Then AutoLISP knows where to look in memory for that information.

Different data types are stored in memory in different ways.  For example, when an integer is assigned to a variable, that variable points to a particular set of 32 adjacent bits (4 bytes) in memory which hold the 0's and 1's (low and high voltages) that represent the binary value of the integer.  (This group of bits is called a 4 byte word.)  Since the amount of memory used to store an integer is limited, the range of values for integers is also limited.  Similarly, when a real is assigned to a variable, that variable points to an 8 byte word in memory.  Even though reals take up twice as much space in memory, that space is still limited.  But with reals the limit is not on their range, but on their accuracy.  (The exact limitations of both integers and reals is given in Lesson 2.)  For the purposes of our present discussion, the point is that there is a fixed amount of memory set aside for certain data types such as integers and reals, whether 4 bytes, 8 bytes, or whatever.  But it is impossible to set aside a fixed amount of memory in which to store certain other data types, including lists, because their lengths are unpredictable.

So lists are stored in memory using a clever scheme that allows them to expand to any length needed.  Each element of a list is stored in a certain number of bytes (appropriate to that element's data type), then in the next few bytes is stored a pointer to the memory location holding the next element in the list.  Thus each element requires two portions, called registers.

• The first register begins at the memory location addressed (pointed to) by the variable.  It holds the value of that element of the list.  This register is called the "address register."
• The second register holds a pointer to the address of the next element in the list.  This register is called the "decrement register."

 The car and cdr functions are the two main functions which retrieve parts of a list.  The function name "car" stands for Contents of Address Register, while "cdr" stands for Contents of Decrement Register.

Suppose that the list pictured above is simply four integers (1 2 3 4) and this list is assigned to variable L1.  Then the car and cdr functions produce the following results:

    (car L1)  returns 1
    (cdr L1)  returns (2 3 4)

The car function retrieves the contents of the address register that the variable points to, which is the first element in the list.  The cdr function retrieves the contents of the decrement register, which is another pointer, so the remainder of the list is retrieved.

Here is a table with some more examples to illustrate the use of car and cdr.  In practical terms, car retrieves the first element from a list while cdr retrieves the list without its first element.  The original list remains unchanged.  Notice that, if all the top level elements in the list are atoms, car produces an atom while cdr produces a list
 

Also see car and cdr in "9 - List manipulation" in the Function definitions.

AutoLISP includes a set of functions that are derived from car and cdr.  See the NOTE following cdr in "9 - List manipulation" in the Function definitions.

Remember that points are actually lists of three coordinates.  Therefore you will use the cadr and caddr functions often.

The cadr function

Extracts the second element in a list (such as a Y coordinate).  It is an abbreviation of (car (cdr ....

The caddr function

Extracts the third element in a list (such as a Z coordinate).  It is an abbreviation of (car (cdr (cdr ....

    (car point1)  returns 7.0
    (cadr point1)  returns 8.0
    (caddr point1)  returns 9.0
 

The above functions are fine when lists are short or when you need to retrieve items from near the beginning of the lists.

When you need to retrieve the last element in a list, use the last function.  For example,

    (last (list 2 4 6 8))  returns 8 as an atom.

When you need to retrieve an element from within a long list, the nth function is helpful.  For example

    (nth 3 (list 1 2 3 4 5 6 7 8 9))  returns 4.

Notice that the nth function counts the first element as zero, the second as 1, the third as 2, etc.

The reverse function returns a list whose top level elements are in the opposite order.  It does not change the original list unless the reversed list is re-assigned to the same variable.  For example, after (setq L1 (list 1 2 3 4 5)),

    (reverse L1)  returns (5 4 3 2 1), but L1 remains unchanged.
    (setq L1 (reverse L1))  returns (5 4 3 2 1) and places this reversed list back in L1.

To find out how many top level elements are in a list, use the length function.  For example,

    (length (list 1 3 5 7 9))  returns 5
    (length (list 1 (list 3 5) (cons 7 (list 9))))  returns 3 since only top level elements are counted.

To find out if a certain element is contained in a list, use the member function.  Rather than returning T or nil, the member function returns a list containing that member along with all other elements in the rest of the original list.  For example,

    (member 55 (list 44 55 66))  returns (55 66)

There are also other more advanced functions, such as assoc and subst.  These functions will be discussed later in connection with entity access.

There are several functions that can create and build lists.  The list function creates new lists and the cons and append functions add items to existing lists.  A typical use of these three functions might be as follows:

First, use the list function to form a list, assigning it to a variable.

    (setq L1 (list 55 66 77))

Variable L1 now holds a three member list.

To add an item to the beginning of the list, use the cons function, assigning it to a different variable.

    (setq L2 (cons 44 L1))

Variable L2 now holds a list identical to L1 but with the new member 44 at the beginning: (44 55 66 77).  L1 remains unchanged.

To add an item to the end of the list, use the append function, assigning it to a different variable.

    (setq L3 (append L2 (list 88)))

Variable L3 now holds a list identical to L2 but with the new member 88 at the end: (44 55 66 77 88).  L2 remain unchanged.

Often, instead of placing the modified lists in new variables, they are placed back in the same variable, as follows:

    (setq L1 (list 55 66 77))
    (setq L1 (cons 44 L1))
    (setq L1 (append L1 (list 88)))

A null (empty) list is a valid list.  Such a list can be created in either of the two following ways:

    (setq L1 ())
    (setq L1 nil)

Initializing a variable as a null list is often necessary before entering a loop which adds elements to the list, as illustrated below in the sample program called trimlist (section 30, line 2).

A dotted pair is a special type of list which saves memory space.  Two items could be placed in a regular list which, as described above under "List storage," would require four registers.  But a dotted pair is stored in two adjacent registers with the second value taking the place of the pointer in the decrement register.

Dotted pairs are created with the cons function.  Often, cons is used to add a new element at the beginning of an existing list, as explained above under "Functions that form lists."  In that case, cons has a list as its second argument.  However, when cons has an atom as its second argument, then a dotted pair is formed.  For example,

    (cons 7 8)  returns the dotted pair (7 . 8)

When the car function is used on a dotted pair, it returns the first element as would be expected.  But when the cdr function is used on a dotted pair, instead of returning a list, it returns an atom since the contents of the decrement register is an atom rather than a pointer.

    (car (7 . 8))  returns 7
    (cdr (7 . 8))  returns 8 rather than (8)

In each of the problems below, create the list then perform each of the operations under the list.

1.  Create this list and assign it to a variable:  (2 3 4 5 6 7 8)

Add the integer 1 as a new item at the beginning of the list, reassign the new list to the same variable.

Add the integer 9 as a new item at the end of the list, reassign the new list to the same variable.

Extract the first element.

Extract the second element.

Extract the third element.

Extract the fourth element.

Extract the fifth element.

Extract the last element.

Extract the next to last element.

Reverse the list, reassign the new list to the same variable.

Remove the first element from the list, reassign the new list to the same variable.

Remove the last element from the list, reassign the new list to the same variable.

Find out the length of the list.

Find out if 9 is a member of the list.

2.  Create this list and assign it to a variable:  ("one" . "two")

Extract the first element.

Extract the second element.

3.  Create this list and assign it to a variable:  ("Judy" ("Billy" . "Bob") ("Warren" "Wendel" "Willy"))

Find out the length of the list.

Note: Perform each of the following operations using (1) a combination of car and cdr, and (2) a single derived function.

Extract the second element.

Extract the second element of the third element, that is, "Wendel".

Extract the second element of the second element, that is, "Bob".

The program ol, short for on-line, allows you to locate a new point on a line (imaginary or real) between two existing points.  The new point can be located either at an absolute distance from one of the existing points toward the other, or at a fraction of the distance between the two existing points.  Also, the new point can be between the two existing points or "outside" of them in either direction.  This program illustrates the car, cadr, and caddr functions used to extract coordinates from a point (end of section 10), and the list function used to build a point from coordinates (end of section 20).

This program is not run at the command prompt.  Rather, it is run in the middle of any drawing or editing command when you are prompted for a point.  To run the command you must call it as a function by including the parentheses.  In other words, when prompted for a point you would enter  (ol).  Note that the program is defined as a function rather than a command (there is no "c:" in front of the function name).

Suppose you need to create a circle with its center 3/4 of the way between two existing points, you would begin the circle command, then when prompted for the center, enter (ol), pick the two points, then enter 3/4.

When prompted for a distance you can enter a positive or negative distance, but not zero.  A positive distance will place the new point along a line from the first point picked toward (or beyond) the second.  A negative distance will place the new point in the opposite direction.  Instead of entering a distance, you can enter the letter "F" and then enter a fraction of the distance between the two points.  This fraction can be positive or negative and can be less than or greater than one, but not zero.  A positive fraction greater than one places the new point beyond the second picked point.

The program sets a running osnap mode of endpoint when the user picks the first and second points by setting "osmode" to 1.  Then, in order to insure that the point that is returned is not affected by that running osnap mode, the program turns it off by setting system variable "osmode" to 0.

What this program accomplishes can also be done in several other ways, but each one has its disadvantages.  For example,

• You could create a construction line between the two existing points then use LENGTHEN to adjust the length of the line.  This gives you an endpoint to snap to at the desired location, but requires the extra steps of creating, lengthening/shortening, and erasing the construction line.
• You could use CAL, the graphics calculator, but this requires learning the syntax of the CAL program.
• If the two existing points are lined up orthogonally, you can place the cursor in the desired direction and enter a distance, but this is limited to orthogonal lines and absolute distances.

------ marker ------ beginning of working program ------ try it out ------

;|  OL, short for On Line
    Copyright © 1990,1993,1998 Ronald W. Leigh
    USAGE: USE (INCLUDE PARENTHESES) WHEN PROMPTED FOR A
           POINT.  DO NOT USE AT COMMAND LINE
    Input: Two points and absolute or fractional distance
    Output: Returns the point that lies at the requested
      distance from the first point toward the second point
Variables:
dis       Distance between points
frac      Fraction
len       Length between points
p1/p2     Endpoints in current UCS
x1/y1/z1  Coordinates of p1
x2/y2/z2  Coordinates of p2            |;

;10====PROGRAM, GET POINTS

(defun ol (/ dis frac len p1 p2 x1 y1 z1 x2 y2 z2)
(setvar "osmode" 1)
(setq p1 (getpoint "\n--Pick first point: "))
(setq p2 (getpoint "\n--Pick second point: "))
(setq len (distance p1 p2))
(setvar "osmode" 0)
(setq x1 (car p1) y1 (cadr p1) z1 (caddr p1)
      x2 (car p2) y2 (cadr p2) z2 (caddr p2))

;20====GET DISTANCE OR FRACTION, BUILD NEW POINT

(princ (strcat "\n--Distance between points is " (rtos len)))
(initget 3 "Fraction")
(setq dis (getdist "\n--Distance from first endpoint (or F for fraction): "))
(if (/= dis "Fraction")
  (setq frac (/ dis len))
  (progn
    (initget 3)
    (setq frac (getdist "\n--Fraction of above distance: "))))
(list (+ x1 (* frac (- x2 x1)))
      (+ y1 (* frac (- y2 y1)))
      (+ z1 (* frac (- z2 z1))))
)

-------- marker -------- end of working program -------- try it out --------
 

This is one of those do-nothing programs which is useful only for illustrating functions that work with lists.  It asks the user to enter a central point, an inclusion radius, then ten other points (some inside and some outside the radius), then indicates which points are within the radius.  Of course, the user does not need this program because he/she can easily see which points are inside the circle and which are not.  Nevertheless, if you use this program a few times and get a feel for the way it appears on screen, you will find it easier to understand the program when you examine it in detail.

This entire program could be written without the use of any list manipulating functions, simply by having it evaluate each of the ten points as it is located.  But we are trying to illustrate the manipulation of lists, so the program places all ten points in a list.  Then the program works through the list evaluating each point.  It creates a second list (a trimmed list, or short list) which contains only the close points.  Both of these lists are built using the cons function (sections 30 and 40).

The functions in the expression at the end of section 20 that extracts the radius of the circle from the drawing database are covered in a later lesson.
 

------ marker ------ beginning of working program ------ try it out ------

;|  TRIMLIST, short for TRIMmed LIST
    Copyright © 1988,1998 Ronald W. Leigh
    Input: Central point, inclusion radius, 10 other points
    Output: Circles all points within a certain radius
Variables:
cnt    Counter
cp     Central point
ir     Inclusion radius
obm    Old blipmode
opdm   Old point display mode
opds   Old point display size
pt     Point
plist1 Original list of 10 points
plist2 Trimmed point list
vsize  height of current viewport
vvv    Value in foreach loop                |;

;10====PROGRAM, SETUP

(defun c:trimlist (/ cnt cp ir obm opdm opds pt plist1 plist2 vsize vvv)
(setq opdm (getvar "pdmode"))
(setq opds (getvar "pdsize"))
(setq obm (getvar "blipmode"))
(setvar "pdmode" 3)
(setvar "pdsize" -3)
(setvar "blipmode" 0)
(setq vsize (getvar "viewsize"))

;20====GET CENTRAL POINT & INCLUSION RADIUS

(initget 1)
(setq cp (getpoint "\nLocate central point: "))
(command ".donut" 0.0 (* vsize 0.025) cp "")
(princ "\nInclusion radius (pick point on screen): ")
(setvar "cmdecho" 0)
(command ".circle" cp pause)
(setq el (entget (entlast)) ir (cdr (assoc 40 el)))

;30====GET TEN OTHER POINTS

(princ "\nLocate 10 points, some inside circle, some outside.")
(setq cnt 0 plist1 nil)
(repeat 10
  (setq cnt (1+ cnt))
  (setq pt (getpoint (strcat
             "\nLocate point number " (itoa cnt) ": ")))
  (setq plist1 (cons pt plist1))
  (command ".point" pt))

;40====GENERATE TRIMMED LIST

(setq plist2 nil)
(foreach vvv plist1
  (if (<= (distance cp vvv) ir) (setq plist2 (cons vvv plist2))))

;50====DISPLAY RESULTS

(foreach vvv plist2 (command ".circle" vvv (* vsize 0.025)))

;60====RESET

(setvar "cmdecho" 1)
(setvar "pdmode" opdm)
(setvar "pdsize" opds)
(setvar "blipmode" obm)
(princ)
)

-------- marker -------- end of working program -------- try it out --------