Figure 7.6:
A Short Program to Add Vertices
|
(mset-type ) |
Creates an empty C++ multiset to hold elements of type
type.
O(1)
Creates an empty C++ set to hold elements of type
type.
O(1)
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)
Return #t if
col is a collection of
int
objects.
O(1)
Return the number of elements in
col.
O(
n)
Return #t if
col has 0 elements.
O(1)
Return
value if it is in the colleciton
col; otherwise return #f.
O(
n)
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 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.
Remove all of the elements from colleciton
col.
O(
n)
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).
Return the set of all k-subsets of

where

is a LINK

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

where

is a LINK

class object (not a multiset or sequence).
O(2
n).