I've rarely had the need for fill pointers, but now think I may.
However, I'm a bit confused by an apparent inconsistency, an
off-by-one error.
The definition of fill pointer given in the CLHS is as follows (from
the glossary):
fill pointer n. (of a vector) an integer associated with a vector
that represents the index above which no elements are active. (A
fill pointer is a non-negative integer no larger than the total
number of elements in the vector. Not all vectors have fill
pointers.)
So suppose the following:
(setq a (make-array 8 :fill-pointer 4))
This means that a has the following:
Fill pointer ---v
0 1 2 3 4 5 6 7
NIL NIL NIL NIL NIL NIL NIL NIL
So, since the fill pointer has the value of 4, that means that nothing
with an index > 4 is active (and, presumably, all other elements-- ie,
0-4-- are active). This has two implications:
1. There is no way to indicate that no elements are active, since the
fill pointer must be non-negative, so index 0 will never be above
the fill pointer.
2. For a vector of length N, a fill pointer of N-1 is equivalent to a
fill pointer of N (for the purposes of determining what's active).
It seems that it should be that for a fill pointer f, no elements of
index k >= f are active.
The example under "Accessor FILL-POINTER" in CLHS seems to have the
same implication:
(setq a (make-array 8 :fill-pointer 4)) => #(NIL NIL NIL NIL)
as does CLtL2:
The fill pointer is a non-negative integer no larger than the
total number of elements in the vector (as returned by
array-dimension); it is the number of ``active'' or ``filled-in''
elements in the vector. The fill pointer constitutes the ``active
length'' of the vector; all vector elements whose index is less
than the fill pointer are active, and the others are inactive.
My question, I guess, is two-fold. Am I misinterpreting the
definition, or is it in error, or what? Second, is the glossary an
official part of the standard? It has a chapter number, so I figure
it's not part of the "back matter" (as referenced in 1.4.3).
Thanks,
joelh
Joel,
A fill-pointer is the index that when a vector-push (or vector-push-extend)
is done that is where the element is put. A fill-pointer of zero
indications that no elements are active.
CL-USER 7 > (setf vec (make-array 8 :fill-pointer 0))
#()
CL-USER 8 > (vector-push 10 vec)
0
CL-USER 9 > vec
#(10)
CL-USER 10 > (fill-pointer vec)
1
CL-USER 11 > (vector-push 20 vec)
1
CL-USER 12 > (fill-pointer vec)
2
CL-USER 13 > (aref vec 0)
10
CL-USER 14 > (aref vec 1)
20
CL-USER 15 > (aref vec (fill-pointer vec))
NIL
CL-USER 16 > (aref vec 2)
NIL
CL-USER 17 > (setf (fill-pointer vec) 0)
0
CL-USER 18 > vec
#()
Wade
From: Howard Ding
Subject: Re: CLHS: Fill pointer definition: off by one?
Date:
Message-ID: <3C43A3C2.395CD6C@att.net>
Take a look at the following section:
15.1.1.3.1.1 Fill Pointers
In particular, the line:
An element of a vector is said to be active if it has an index that is
greater than or equal to zero, but less than the fill pointer (if any).
For an array that
has no fill pointer, all elements are considered active.
--
Howard Ding
<······@att.net>
http://math.sunysb.edu/~hading http://thunder.prohosting.com/~hading