next up previous contents
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 $\ldots$ 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 $\ldots$ ik may be appropriately-typed Scheme objects. O(n)









  (set-type i1 i2 $\ldots$ ik )



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









  (sequence-type i1 i2 $\ldots$ 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 $\ldots$ colk )



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









   (eqv? col col2 $\ldots$ colk )



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









   (< col col2 $\ldots$ colk )



Return true if coli < colj whenever $i \mbox{$<$}\ j$. Ordering is lexicographic. O(n)









   (<= col col2 $\ldots$ colk )



Return true if coli <= colj whenever $i \mbox{$<=$}\ j$. Ordering is lexicographic. O(n)









   (> col col2 $\ldots$ colk )



Return true if coli > colj whenever $i \mbox{$\gt$}\ j$. Ordering is lexicographic. O(n)









   (>= col col2 $\ldots$ colk )



Return true if coli >= colj whenever $i \mbox{$\gt=$}\ j$. Ordering is lexicographic. O(n)









   (+ col col2 $\ldots$ colk )



Return a multiset containing the union of col $\ldots$ 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 $\ldots$ colk )



Return a multiset containing the intersection of col $\ldots$ 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 $\ldots$ colk )



Return a multiset containing the difference of col $\ldots$ 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 $\ldots$ colk )



Return #t if $\mbox{$col$}\ \subseteq \mbox{$col_2$}\ \subseteq \mbox{$col_k$}\ $. Time complexity depends on the types of the coli.









   (proper-subset col col2 $\ldots$ colk )



Return #t if $\mbox{$col$}\ \subset \mbox{$col_2$}\ \subset \mbox{$col_k$}\ ,$ where $\mbox{$col_i$}\ \subset \mbox{$col_j$}\ $ if and only if for each element e in the $\mbox{$col_i$}\ \cup \mbox{$col_j$}\ $, $r\_i(e) $<$ r\_j(e)$. 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 $\mbox{$set$},$ where $\mbox{$set$}\ $ is a LINK $\mbox{$set$}\ $ class object (not a multiset or sequence). O(2n).









   (power-set set )



Return the set of all subsets of $\mbox{$set$},$ where $\mbox{$set$}\ $ is a LINK $\mbox{$set$}\ $ 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
\begin{figure}
\begin{flushleft}
\hrulefill

\begin{alltt}
\relax
STk\gt {\bf (d...
 ...3\(\}\)
\(\char93 \)f} }
\relax\end{alltt}
\hrulefill\end{flushleft}\end{figure}


  
Figure 8.2: Definition of sequences
\begin{figure}
\begin{flushleft}
\hrulefill

\begin{alltt}
\relax
STk\gt {\bf (d...
 ...3\(\}\)
\(\char93 \)f} }
\relax\end{alltt}
\hrulefill\end{flushleft}\end{figure}


  
Figure 8.3: Conversions between collections and Scheme lists
\begin{figure}
\begin{flushleft}
\hrulefill

\begin{alltt}
\relax
STk\gt {\bf (d...
 ...\(\gt\)
\(\char93 \)f} }
\relax\end{alltt}
\hrulefill\end{flushleft}\end{figure}


  
Figure 8.4: Membership testing in collections
\begin{figure}
\begin{flushleft}
\hrulefill

\begin{alltt}
\relax
STk\gt {\bf (d...
 ...3\(\}\)
\(\char93 \)f} }
\relax\end{alltt}
\hrulefill\end{flushleft}\end{figure}


  
Figure 8.5: Example of overloaded method: null?
\begin{figure}
\begin{flushleft}
\hrulefill

\begin{alltt}
\relax
STk\gt {\bf (d...
 ... }{\em{
\(\char93 \)t} }
\relax\end{alltt}
\hrulefill\end{flushleft}\end{figure}


  
Figure 8.6: Defining generic functions which take collections as arguments
\begin{figure}
\begin{flushleft}
\hrulefill

\begin{alltt}
\relax
STk\gt {\bf (d...
 ...t\)\(\gt\) 4022e340])} }
\relax\end{alltt}
\hrulefill\end{flushleft}\end{figure}


  
Figure 8.7: Comparing collections
\begin{figure}
\begin{flushleft}
\hrulefill

\begin{alltt}
\relax
STk\gt {\bf (d...
 ...)) }{\em{
seq-greater} }
\relax\end{alltt}
\hrulefill\end{flushleft}\end{figure}


  
Figure 8.8: The set primitive operations
\begin{figure}
\begin{flushleft}
\hrulefill

\begin{alltt}
\relax
STk\gt {\bf (d...
 ...3\(\}\)
\(\char93 \)f} }
\relax\end{alltt}
\hrulefill\end{flushleft}\end{figure}


  
Figure 8.9: k-sets and power sets of a set
\begin{figure}
\begin{flushleft}
\hrulefill

\begin{alltt}
\relax
STk\gt {\bf (d...
 ...)\(\}\)
\(\char93 \)f} }
\relax\end{alltt}
\hrulefill\end{flushleft}\end{figure}


next up previous contents
Next: Typed Vectors Up: Basic Objects Previous: Basic Objects
RHS Linux User
1/26/1998