summaryrefslogtreecommitdiffstats
path: root/Doc/lib/libsets.tex
diff options
context:
space:
mode:
Diffstat (limited to 'Doc/lib/libsets.tex')
-rw-r--r--Doc/lib/libsets.tex219
1 files changed, 219 insertions, 0 deletions
diff --git a/Doc/lib/libsets.tex b/Doc/lib/libsets.tex
new file mode 100644
index 0000000..65ca8e7
--- /dev/null
+++ b/Doc/lib/libsets.tex
@@ -0,0 +1,219 @@
+\section{\module{sets} ---
+ Unordered collections of unique elements}
+
+\declaremodule{standard}{sets}
+\modulesynopsis{Implementation of sets of unique elements.}
+\moduleauthor{Greg V. Wilson}{gvwilson@nevex.com}
+\moduleauthor{Alex Martelli}{aleax@aleax.it}
+\moduleauthor{Guido van Rossum}{guido@python.org}
+\sectionauthor{Raymond D. Hettinger}{python@rcn.com}
+
+\versionadded{2.3}
+
+The \module{sets} module provides classes for constructing and manipulating
+unordered collections of unique elements. Common uses include membership
+testing, removing duplicates from a sequence, and computing standard math
+operations on sets such as intersection, union, difference, and symmetric
+difference.
+
+Like other collections, sets support \code{x in s}, \code{len(s)}, and
+\code{for x in s}. Being an unordered collection, sets do not record element
+position or order of insertion. Accordingly, sets do not support indexing,
+slicing or other sequence-like behavior.
+
+Most set applications use the \class{Set} class which provides every set
+method except for \method{__hash__()}. For advanced applications requiring
+a hash method, the \class{ImmutableSet} class adds a \method{__hash__()}
+method but omits methods which alter the contents of the set. Both
+\class{Set} and \class{ImmutableSet} derive from \class{BaseSet}, an
+abstract class useful for determining whether something is a set:
+\code{isinstance(x, BaseSet)}.
+
+The set classes are implemented using dictionaries. As a result, sets cannot
+contain mutable elements such as lists or dictionaries. However, they can
+contain immutable collections such as tuples or instances of
+\class(ImmutableSet). For convenience in implementing sets of sets,
+inner sets are automatically converted to immutable form, for example,
+\code{Set([Set(['dog'])])} is transformed to
+\code{Set([ImmutableSet(['dog'])])}.
+
+\begin{classdesc}{Set}{\optional{iterable}}
+Constructs a new empty \class{Set} object. If the optional \var{iterable}
+parameter is supplied, updates the set with elements obtained from iteration.
+All of the elements in \var{iterable} should be immutable or be transformable
+to an immutable using the protocol described at \ref{immutable-transforms}.
+\end{classdesc}
+
+\begin{classdesc}{ImmutableSet}{\optional{iterable}}
+Constructs a new empty \class{ImmutableSet} object. If the optional
+\var{iterable} parameter is supplied, updates the set with elements obtained
+from iteration. All of the elements in \var{iterable} should be immutable or
+be transformable to an immutable using the protocol described at
+\ref{immutable-transforms}.
+
+Because \class{ImmutableSet} objects provide a \method{__hash__()} method,
+they can be used as set elements or as dictionary keys. \class{ImmutableSet}
+objects do not have methods for adding or removing elements, so all of the
+elements must be known when the constructor is called.
+\end{classdesc}
+
+
+\subsection{set Objects}
+
+Instances of \class{Set} and \class{ImmutableSet} both provide
+the following operations:
+
+\begin{tableiii}{c|l|c}{code}{Operation}{Result}{Notes}
+ \lineiii{len(\var{s})}{cardinality of set \var{s}}{}
+
+ \hline
+ \lineiii{\var{x} in \var{s}}
+ {test \var{x} for membership in \var{s}}{}
+ \lineiii{\var{x} not in \var{s}}
+ {test \var{x} for non-membership in \var{s}}{}
+ \lineiii{\var{s}.issubset(\var{t})}
+ {test whether every element in \var{s} is in \var{t}}{}
+ \lineiii{\var{s}.issuperset(\var{t})}
+ {test whether every element in \var{t} is in \var{s}}{}
+
+ \hline
+ \lineiii{\var{s} | \var{t}}
+ {new set with elements from both \var{s} and \var{t}}{}
+ \lineiii{\var{s}.union(\var{t})}
+ {new set with elements from both \var{s} and \var{t}}{}
+ \lineiii{\var{s} & \var{t}}
+ {new set with elements common to \var{s} and \var{t}}{}
+ \lineiii{\var{s}.intersection(\var{t})}
+ {new set with elements common to \var{s} and \var{t}}{}
+ \lineiii{\var{s} - \var{t}}
+ {new set with elements in \var{s} but not in \var{t}}{}
+ \lineiii{\var{s}.difference(\var{t})}
+ {new set with elements in \var{s} but not in \var{t}}{}
+ \lineiii{\var{s} ^ \var{t}}
+ {new set with elements in either \var{s} or \var{t} but not both}{}
+ \lineiii{\var{s}.symmetric_difference(\var{t})}
+ {new set with elements in either \var{s} or \var{t} but not both}{}
+ \lineiii{\var{s}.copy()}
+ {new set with a shallow copy of \var{s}}{}
+\end{tableiii}
+
+In addition to the above operations, both \class{Set} and \class{ImmutableSet}
+support set to set comparison operators based on the contents of their
+internal dictionaries. Two sets are equal if and only if every element of
+each set is contained in the other.
+
+The following table lists operations available in \class{ImmutableSet}
+but not found in \class{Set}:
+
+\begin{tableiii}{c|l|c}{code}{Operation}{Result}{Notes}
+ \lineiii{hash(\var{s})}{returns a hash value for \var{s}}{}
+\end{tableiii}
+
+The following table lists operations available in \class{Set}
+but not found in \class{ImmutableSet}:
+
+\begin{tableiii}{c|l|c}{code}{Operation}{Result}{Notes}
+ \lineiii{\var{s} |= \var{t}}
+ {return set \var{s} with elements added from \var{t}}{}
+ \lineiii{\var{s}.union_update(\var{t})}
+ {return set \var{s} with elements added from \var{t}}{}
+ \lineiii{\var{s} &= \var{t}}
+ {return set \var{s} keeping only elements also found in \var{t}}{}
+ \lineiii{\var{s}.intersection_update(\var{t})}
+ {return set \var{s} keeping only elements also found in \var{t}}{}
+ \lineiii{\var{s} -= \var{t}}
+ {return set \var{s} after removing elements found in \var{t}}{}
+ \lineiii{\var{s}.difference_update(\var{t})}
+ {return set \var{s} after removing elements found in \var{t}}{}
+ \lineiii{\var{s} ^= \var{t}}
+ {return set \var{s} with elements from \var{s} or \var{t} but not both}{}
+ \lineiii{\var{s}.symmetric_difference_update(\var{t})}
+ {return set \var{s} with elements from \var{s} or \var{t} but not both}{}
+
+ \hline
+ \lineiii{\var{s}.add(\var{x})}
+ {Add element \var{x} to set \var{s}}{}
+ \lineiii{\var{s}.remove(\var{x})}
+ {Remove element \var{x} from set \var{s}}{}
+ \lineiii{\var{s}.discard(\var{x})}
+ {Removes element \var{x} from set \var{s} like \var{s}.remove(\var{x})
+ but does not raise a KeyError if \var{x} is not in \var{s}}{}
+ \lineiii{\var{s}.pop()}
+ {Remove and return a randomly-chosen element from \var{s}}{}
+ \lineiii{\var{s}.update(\var{t})}
+ {Add elements from \var{t} to set \var{s}}{}
+ \lineiii{\var{s}.clear()}
+ {Remove all elements from set \var{s}}{}
+\end{tableiii}
+
+
+\subsection{Example}
+
+\begin{verbatim}
+>>> from sets import Set
+>>> engineers = Set(['John', 'Jane', 'Jack', 'Janice'])
+>>> programmers = Set(['Jack', 'Sam', 'Susan', 'Janice'])
+>>> management = Set(['Jane', 'Jack', 'Susan', 'Zack'])
+>>> employees = engineers | programmers | management # union
+>>> engineering_management = engineers & programmers # intersection
+>>> fulltime_management = management - engineers - programmers # difference
+>>> engineers.add('Marvin') # add element
+>>> print engineers
+Set(['Jane', 'Marvin', 'Janice', 'John', 'Jack'])
+>>> employees.issuperset(engineers) # superset test
+False
+>>> employees.update(engineers) # update from another set
+>>> employees.issuperset(engineers)
+True
+>>> for group in [engineers, programmers, management, employees]:
+ group.discard('Susan') # unconditionally remove element
+ print group
+
+Set(['Jane', 'Marvin', 'Janice', 'John', 'Jack'])
+Set(['Janice', 'Jack', 'Sam'])
+Set(['Jane', 'Zack', 'Jack'])
+Set(['Jack', 'Sam', 'Jane', 'Marvin', 'Janice', 'John', 'Zack'])
+\end{verbatim}
+
+
+\subsection{Protocol for automatic conversion to immutable
+ \label{immutable-transforms}}
+
+Sets can only contain immutable elements. For convenience, mutable
+\class{Set} objects are automatically copied to an \class{ImmutableSet}
+before being added as a set element.
+
+The mechanism is to always add a hashable element, or if it is not hashable,
+the element is checked to see if it has an \method{_as_immutable()} method
+which returns an immutable equivalent.
+
+Since \class{Set} objects have a \method{_as_immutable()} method
+returning an instance of \class{ImmutableSet}, it is possible to
+construct sets of sets.
+
+A similar mechanism is needed by the \method{__contains__()} and
+\method{remove()} methods which need to hash an element to check
+for membership in a set. Those methods check an element for hashability
+and, if not, check for a \method{_as_Temporarily_Immutable} method
+which returns the element wrapped by a class that provides temporary
+methods for \method{__hash__()}, \method{__eq__()}, and \method{__ne__()}.
+
+The alternate mechanism spares the need to build a separate copy of
+the original mutable object.
+
+\class{Set} objects implement the \method{_as_Temporarily_Immutable} method
+which returns the \class{Set} object wrapped by a new class
+\class{_TemporarilyImmutableSet}.
+
+The two mechanisms for adding hashability are normally invisible to the
+user; however, a conflict can arise in a multi-threaded environment
+where one thread is updating a Set while another has temporarily wrapped it
+in \class{_TemporarilyImmutableSet}. In other words, sets of mutable sets
+are not thread-safe.
+
+
+
+
+
+
+