Next: Typed Vectors Up: Basic Objects Previous: Basic Objects

## Collections

All of the following methods are generated automatically for each type of collectionn. The instantiation of new types requires recompiling, so the process will eventually be described in the programmer's manual. However, most users should be satisfied with the types currently available, which are the same types as those enumerate for typed lists (Page ).

Figure 7.6: A Short Program to Add Vertices
| (mset-type )

Creates an empty C++ multiset to hold elements of type type. O(1)

| (set-type )

Creates an empty C++ set to hold elements of type type. O(1)

| (sequence-type )

Creates an empty C++ sequence to hold elements of type type. O(1)

| (mset-type i1 i2 ik )

Creates a C++ multiset containing the specified elements. Note: for C++ types which have close Scheme analogs, such as `int`, the elements i1 i2 ik may be appropriately-typed Scheme objects. O(n)

| (set-type i1 i2 ik )

Creates a C++ set containing the specified elements. (same note) O(n)

| (sequence-type i1 i2 ik )

Creates a C++ sequence containing the specified elements. (same note) O(n)

(list->mset-type list ) |
(list->set-type list ) (list->sequence-type list ) |

Given a Scheme list, create a C++ collection containing the elements of the list. O(n)

(mset-type->list mset ) |
(set-type->list set ) (sequence-type->list sequence ) |

Create and return a Scheme list containing the elements of the collection argument. O(n)

| (collection-int? col )

Return #t if col is a collection of `int` objects. O(1)

| (size col )

Return the number of elements in col. O(n)

| (null? col )

Return #t if col has 0 elements. O(1)

| (member? value col )

Return value if it is in the colleciton col; otherwise return #f. O(n)

| (insert! value col )

Add the element value to colleciton col. If col does not allow multiple elements, requests for multiple insertion of an element are ignored. Time complexity depends on collection implementation.

| (remove! value col )

Remove the element value to colleciton col. If value occurred k times before the call, it will occur k-1 times afterwards. Time complexity depends on collection implementation.

| (clear! col )

Remove all of the elements from colleciton col. O(n)

| (occurrences value col )

Remove number of times element value occurs in collection col. O(n)

| (eq? col col2 colk )

Return true if all argments are the same object. O(n)

| (eqv? col col2 colk )

Return true if all argments are collections with the same elements. O(n)

| (< col col2 colk )

Return true if coli < colj whenever . Ordering is lexicographic. O(n)

| (<= col col2 colk )

Return true if coli <= colj whenever . Ordering is lexicographic. O(n)

| (> col col2 colk )

Return true if coli > colj whenever . Ordering is lexicographic. O(n)

| (>= col col2 colk )

Return true if coli >= colj whenever . Ordering is lexicographic. O(n)

| (+ col col2 colk )

Return a multiset containing the union of col colk, i.e. each occurrence of each element of collection coli is added to the result. Time complexity depends on the types of the coli.

| (^col col2 colk )

Return a multiset containing the intersection of col colk. The number of occurrences of element i in the result is the minimum number of occurrences of i in any coli. Time complexity depends on the types of the coli.

| (- col col2 colk )

Return a multiset containing the difference of col colk. If rj(i) denotes the number of occurrences of element i in colj, then the number of occurrences of i in the result is the maximum of 0 and the difference between r1(i)and the sum from 2 to k of rj(i). Time complexity depends on the types of the coli.

| (subset col col2 colk )

Return #t if . Time complexity depends on the types of the coli.

| (proper-subset col col2 colk )

Return #t if where if and only if for each element e in the , <. Time complexity depends on the types of the coli.

| (cartesian-product set 1 set 2n)

Return the set of all ordered pairs in the cartesian product of set 1 and set 2n. O(n2).

| (choose set kn)

Return the set of all k-subsets of where is a LINK class object (not a multiset or sequence). O(2n).

| (power-set set )

Return the set of all subsets of where is a LINK class object (not a multiset or sequence). O(2n).

The Collection hierarchy, documented in the Programmer's Manual, provides LINK with a flexible core of set and sequence classes that interact with each other easily, facilitating the representation of a rich variety of graphs.

Figure 8.1: Definition of sets and multisets

Figure 8.2: Definition of sequences

Figure 8.3: Conversions between collections and Scheme lists

Figure 8.4: Membership testing in collections

Figure 8.5: Example of overloaded method: null?

Figure 8.6: Defining generic functions which take collections as arguments

Figure 8.7: Comparing collections

Figure 8.8: The set primitive operations

Figure 8.9: k-sets and power sets of a set

Next: Typed Vectors Up: Basic Objects Previous: Basic Objects