GNU Info

(slib.info)Collections

---

Next: Dynamic Data Type Prev: Portable Image Files Up: Data Structures

---

Enter node , (file) or (file)node

Collections
-----------

  `(require 'collect)'

  Routines for managing collections.  Collections are aggregate data
structures supporting iteration over their elements, similar to the
Dylan(TM) language, but with a different interface.  They have
"elements" indexed by corresponding "keys", although the keys may be
implicit (as with lists).

  New types of collections may be defined as YASOS objects (Note:
Yasos).  They must support the following operations:
   * `(collection? SELF)' (always returns `#t');

   * `(size SELF)' returns the number of elements in the collection;

   * `(print SELF PORT)' is a specialized print operation for the
     collection which prints a suitable representation on the given
     PORT or returns it as a string if PORT is `#t';

   * `(gen-elts SELF)' returns a thunk which on successive invocations
     yields elements of SELF in order or gives an error if it is
     invoked more than `(size SELF)' times;

   * `(gen-keys SELF)' is like `gen-elts', but yields the collection's
     keys in order.

  They might support specialized `for-each-key' and `for-each-elt'
operations.

 - Function: collection? obj
     A predicate, true initially of lists, vectors and strings.  New
     sorts of collections must answer `#t' to `collection?'.

 - Procedure: map-elts proc collection1 ...
 - Procedure: do-elts proc collection1 ...
     PROC is a procedure taking as many arguments as there are
     COLLECTIONS (at least one).  The COLLECTIONS are iterated over in
     their natural order and PROC is applied to the elements yielded by
     each iteration in turn.  The order in which the arguments are
     supplied corresponds to te order in which the COLLECTIONS appear.
     `do-elts' is used when only side-effects of PROC are of interest
     and its return value is unspecified.  `map-elts' returns a
     collection (actually a vector) of the results of the applications
     of PROC.

     Example:
          (map-elts + (list 1 2 3) (vector 1 2 3))
             => #(2 4 6)

 - Procedure: map-keys proc collection1 ...
 - Procedure: do-keys proc collection1 ...
     These are analogous to `map-elts' and `do-elts', but each
     iteration is over the COLLECTIONS' _keys_ rather than their
     elements.

     Example:
          (map-keys + (list 1 2 3) (vector 1 2 3))
             => #(0 2 4)

 - Procedure: for-each-key collection proc
 - Procedure: for-each-elt collection proc
     These are like `do-keys' and `do-elts' but only for a single
     collection; they are potentially more efficient.

 - Function: reduce proc seed collection1 ...
     A generalization of the list-based `comlist:reduce-init' (Note:
     Lists as sequences) to collections which will shadow the
     list-based version if `(require 'collect)' follows `(require
     'common-list-functions)' (Note: Common List Functions).

     Examples:
          (reduce + 0 (vector 1 2 3))
             => 6
          (reduce union '() '((a b c) (b c d) (d a)))
             => (c b d a).

 - Function: any? pred collection1 ...
     A generalization of the list-based `some' (Note: Lists as
     sequences) to collections.

     Example:
          (any? odd? (list 2 3 4 5))
             => #t

 - Function: every? pred collection1 ...
     A generalization of the list-based `every' (Note: Lists as
     sequences) to collections.

     Example:
          (every? collection? '((1 2) #(1 2)))
             => #t

 - Function: empty? collection
     Returns `#t' iff there are no elements in COLLECTION.

     `(empty? COLLECTION) == (zero? (size COLLECTION))'

 - Function: size collection
     Returns the number of elements in COLLECTION.

 - Function: Setter list-ref
     See Note: Setters for a definition of "setter".  N.B.  `(setter
     list-ref)' doesn't work properly for element 0 of a list.

  Here is a sample collection: `simple-table' which is also a `table'.
     (define-predicate TABLE?)
     (define-operation (LOOKUP table key failure-object))
     (define-operation (ASSOCIATE! table key value)) ;; returns key
     (define-operation (REMOVE! table key))          ;; returns value
     
     (define (MAKE-SIMPLE-TABLE)
       (let ( (table (list)) )
         (object
          ;; table behaviors
          ((TABLE? self) #t)
          ((SIZE self) (size table))
          ((PRINT self port) (format port "#<SIMPLE-TABLE>"))
          ((LOOKUP self key failure-object)
           (cond
            ((assq key table) => cdr)
            (else failure-object)
            ))
          ((ASSOCIATE! self key value)
           (cond
            ((assq key table)
             => (lambda (bucket) (set-cdr! bucket value) key))
            (else
             (set! table (cons (cons key value) table))
             key)
            ))
          ((REMOVE! self key);; returns old value
           (cond
            ((null? table) (slib:error "TABLE:REMOVE! Key not found: " key))
            ((eq? key (caar table))
             (let ( (value (cdar table)) )
               (set! table (cdr table))
               value)
             )
            (else
             (let loop ( (last table) (this (cdr table)) )
               (cond
                ((null? this)
                 (slib:error "TABLE:REMOVE! Key not found: " key))
                ((eq? key (caar this))
                 (let ( (value (cdar this)) )
                   (set-cdr! last (cdr this))
                   value)
                 )
                (else
                 (loop (cdr last) (cdr this)))
                ) ) )
            ))
          ;; collection behaviors
          ((COLLECTION? self) #t)
          ((GEN-KEYS self) (collect:list-gen-elts (map car table)))
          ((GEN-ELTS self) (collect:list-gen-elts (map cdr table)))
          ((FOR-EACH-KEY self proc)
           (for-each (lambda (bucket) (proc (car bucket))) table)
           )
          ((FOR-EACH-ELT self proc)
           (for-each (lambda (bucket) (proc (cdr bucket))) table)
           )
          ) ) )