EXTENSIBLE VECTORS -- Jens Axel S�gaard (require (planet "evector.scm" (soegaard "evector.plt"))) ABSTRACT Extensible vectors are a low level resizeable data structure resembling normal Scheme vectors. RATIONALE The purpose of extensible vectors is to provide a low level vector-like data structure, that unlike vectors can be resized in constant amortized time. SPECIFICATION Extensible vectors are heterogenous structures whose elements are indexed by integers. The average time to access a randomly chosen element is typically the same as for a vector. The length of an extensible vector is the number of elements that it contains. This number is a non-negative integer. The valid indexes of an extensible vector are the exact non-negative integers less than the length of the extensible vector. The first element in an extensible vector is indexed by zero, and the last element is indexed by one less than the length of the extensible vector. The length of an extensible vector is set by the procedure set-evector-length!. Increasing the length of an extensible vector will initialize the new elements with the fill value of the extensible vector. The fill value is a value associated with the extensible vector. An extensible vector may be automatically expandable. If the extensible vector is automatically expandable, an attempt to store an element in the extensible vector at an index k larger than or equal to the length of the extensible vector will automatically increase the length of the extensible vector to k+1 before storing the element; otherwise an error is signaled. The space occupied by an extensible vector is affected by the history of the extensible vector. The space occupied is typically less than twice the space of a vector with a length equal to the maximum of the lengths the extensible vector has had. Example: (require (planet "evector.scm" (soegaard "evector.plt"))) > (define ev (evector 1 2 3)) > (evector-pop! ev) 3 > (evector-length ev) 2 > (evector->list ev) (1 2) > (evector-set! ev 7 7) > (evector->vector ev) #8(1 2 3 #f #f #f #f 7) > (evector-push! ev 8) 8 > (evector->list ev) (1 2 3 #f #f #f #f 7 8) Further examples are found in the test suite in test-evector.scm. PROCEDURES > make-evector procedure: (make-evector k) procedure: (make-evector k fill) procedure: (make-evector k fill automatic-expansion?) Returns a newly allocated extensible vector of k elements, whose elements are initialized to the fill value. If a second argument is given, fill is used as the fill value; otherwise the fill value is unspecified. If a third argument is given, it determines whether the extensible vector is automatically expandable. Otherwise the extensible vector will be automatically expandable. > evector procedure: (evector obj ...) Returns a newly allocated automatically expandabale extensible vector whose elements contain the given arguments. The fill value is unspecified. > evector-ref procedure: (evector-ref evector k) k must be a valid index of evector. Evector-ref returns the contents of element k of evector. > evector-set! procedure: (evector-set! evector k obj) Evector-set! stores obj in element k of evector. If k is greater than the length of evector, then evector is expanded if it is automatically expandable; otherwise an error is signaled. The value returned by evector-set! is unspecified. > evector-length procedure: (evector-length evector) Returns the number of elements in evector as an exact integer. >set-evector-length! procedure: (set-evector-length! evector k) Sets the length of the extensible vector evector to k. If k is greater than the previous size of evector, the new elements with index equal to or greater to the old size will be initialised to the fill value of evector. > evector? procedure: (evector obj) Returns #t if obj is an evector, otherwise returns #f. > evector-fill > set-evector-fill! procedure: (evector-fill evector) procedure: (set-evector-fill! evector fill) Evector-fill returns the fill value of evector. Set-evector-fill! changes the fill value to fill. > evector->list > list->evector procedure: (evector->list evector) procedure: (list->evector list) Evector->list returns a newly allocated list of the objects contained in the elements of evector. List->evector returns a newly created extensible vector initialized to the elements of the list list. > evector->vector > vector->evector procdure: (evector->vector evector) procdure: (vector->evector vector) Evector->vector returns a newly allocated vector containing the elements of evector. Vector->evector returns a newly allocated extensible vector initialized to the elements of the vector vector. > evector-fill! procedure: (evector-fill! evector fill) procedure: (evector-fill! evector fill start) procedure: (evector-fill! evector fill start end) Stores fill in the elements of the evector with indexes from start inclusive to end exclusive. The default value for start is 0, and the default value for the end is the length of the extensible vector.