\section{\module{sets} ---
         ユニークな要素の順序なしコレクション}

\declaremodule{standard}{sets}
\modulesynopsis{ユニークな要素の集合の実装}
\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}

\module{sets}モジュールは、ユニークな要素の順序なしコレクションを構築し、
操作するためのクラスを提供します。
帰属関係のテストやシーケンスから重複を取り除いたり、
積集合・和集合・差集合・対称差集合のような標準的な数学操作などを含みます。

他のコレクションのように、\code{\var{x} in \var{set}}, \code{len(\var{set})},
\code{for \var{x} in \var{set}}をサポートします。
順序なしコレクションは、挿入の順序や要素位置を記録しません。
従って、インデックス・スライス・他のシーケンス的な振舞いをサポートしません。

ほとんどの集合のアプリケーションは、\method{__hash__()}を除いて
すべての集合のメソッドを提供する\class{Set}クラスを使用します。
ハッシュを要求する高度なアプリケーションについては、
\class{ImmutableSet}クラスが\method{__hash__()}メソッドを加えているが、
集合の内容を変更するメソッドは省略されます。
\class{Set}と\class{ImmutableSet}は、
何が集合(\code{isinstance(\var{obj}, BaseSet)})であるか決めるのに役立つ
抽象クラス\class{BaseSet}から派生します。

集合クラスは辞書を使用して実装されます。
このことから、集合の要素にするには辞書のキーと同様の要件を満たさなけれ
ばなりません。具体的には、要素になるものには \method{__eq__} と
\method{__hash__} が定義されているという条件です。
その結果、集合はリストや辞書のような変更可能な要素を含むことができません。
しかしそれらは、タプルや\class{ImmutableSet}のインスタンスのような
不変コレクションを含むことができます。
集合の集合の実装中の便宜については、内部集合が自動的に変更不可能な形式に
変換されます。
例えば、\code{Set([Set(['dog'])])}は\code{Set([ImmutableSet(['dog'])])}へ
変換されます。

\begin{classdesc}{Set}{\optional{iterable}}
新しい空の\class{Set}オブジェクトを構築します。
もしオプション\var{iterable}が与えられたら、イタレータから得られた
要素を備えた集合として更新します。
\var{iterable}中の全ての要素は、変更不可能であるか、
または\ref{immutable-transforms}で記述されたプロトコルを使って
変更不可能なものに変換可能であるべきです。
\end{classdesc}

\begin{classdesc}{ImmutableSet}{\optional{iterable}}
新しい空の\class{ImmutableSet}オブジェクトを構築します。
もしオプション\var{iterable}が与えられたら、イタレータから得られた
要素を備えた集合として更新します。
\var{iterable}中の全ての要素は、変更不可能であるか、
または\ref{immutable-transforms}で記述されたプロトコルを使って
変更不可能なものに変換可能であるべきです。

\class{ImmutableSet}オブジェクトは\method{__hash__()}メソッドを備えているので、
集合要素または辞書キーとして使用することができます。
\class{ImmutableSet}オブジェクトは要素を加えたり取り除いたりするメソッドを
持っていません。したがって、コンストラクタが呼ばれたとき要素はすべて
知られていなければなりません。
\end{classdesc}


\subsection{Set オブジェクト \label{set-objects}}

\class{Set}と\class{ImmutableSet}のインスタンスはともに、
以下の操作を備えています:

\begin{tableiii}{c|c|l}{code}{演算}{等価な演算}{結果}
  \lineiii{len(\var{s})}{}{集合\var{s}の濃度 (cardinality)}

  \hline
  \lineiii{\var{x} in \var{s}}{}
         {\var{x}が\var{s}に帰属していれば真を返す}
  \lineiii{\var{x} not in \var{s}}{}
         {\var{x}が\var{s}に帰属していなければ真を返す}
  \lineiii{\var{s}.issubset(\var{t})}{\code{\var{s} <= \var{t}}}
         {\var{s}のすべての要素が\var{t}に帰属していれば真を返す}
  \lineiii{\var{s}.issuperset(\var{t})}{\code{\var{s} >= \var{t}}}
         {\var{t}のすべての要素が\var{s}に帰属していれば真を返す}
	
  \hline
  \lineiii{\var{s}.union(\var{t})}{\var{s} \textbar{} \var{t}}
         {\var{s}と\var{t}の両方の要素からなる新しい集合}
  \lineiii{\var{s}.intersection(\var{t})}{\var{s} \&\ \var{t}}
         {\var{s}と\var{t}で共通する要素からなる新しい集合}
  \lineiii{\var{s}.difference(\var{t})}{\var{s} - \var{t}}
         {\var{s}にあるが\var{t}にない要素からなる新しい集合}
  \lineiii{\var{s}.symmetric_difference(\var{t})}{\var{s} \^\ \var{t}}
         {\var{s}と\var{t}のどちらか一方に属する要素からなる集合}
  \lineiii{\var{s}.copy()}{}
         {\var{s}の浅いコピーからなる集合}
\end{tableiii}

演算子を使わない書き方である \method{union()}、 \method{intersection()}、
\method{difference()}、および\method{symmetric_difference()} は任意の
イテレート可能オブジェクトを引数として受け取るのに対し、演算子を使った
書き方の方では引数は集合型でなければならないので注意してください。
これはエラーの元となる\code{Set('abc') \&\ 'cbs'} のような書き方を
排除し、より可読性のある\code{Set('abc').intersection('cbs')}
を選ばせるための仕様です。
\versionchanged[以前は全ての引数が集合型でなければなりませんでした。]{2.3.1}

加えて、\class{Set}と\class{ImmutableSet} は集合間の比較をサポートしています。
二つの集合は、各々の集合のすべての要素が他方に含まれて (各々が他方の
部分集合) いる場合、かつその場合に限り等価になります。
ある集合は、他方の集合の真の部分集合 (proper subset、部分集合で
あるが非等価) である場合、かつその場合に限り、他方の集合より小さくなります。
ある集合は、他方の集合の真の上位集合 (proper superset、上位集合で
あるが非等価) である場合、かつその場合に限り、他方の集合より大きくなります。

部分集合比較やと等値比較では、完全な順序決定関数を一般化できません。
たとえば、互いに素な 2 つの集合は等しくありませんし、互いの部
分集合でもないので、\code{\var{a}<\var{b}}、 \code{\var{a}==\var{b}}、
\code{\var{a}>\var{b}} は\emph{すべて} \code{False} を返します。
したがって集合は \method{__cmp__} メソッドを実装しません。

集合は一部の順序（部分集合の関係）を定義するだけなので、集合のリストにおいて \method{list.sort()} メソッドの出力は未定義です。

以下は\class{ImmutableSet}で利用可能であるが\class{Set}にはない操作です:

\begin{tableii}{c|l}{code}{演算}{結果}
  \lineii{hash(\var{s})}{\var{s} のハッシュ値を返す}
\end{tableii}

以下は\class{Set}で利用可能であるが\class{ImmutableSet}にはない操作です:

\begin{tableiii}{c|c|l}{code}{演算}{等価な演算}{結果}
  
  \lineiii{\var{s}.update(\var{t})}
         {\var{s} \textbar= \var{t}}
         {\var{t}を加えた要素からなる集合\var{s}を返します}
  \lineiii{\var{s}.intersection_update(\var{t})}
         {\var{s} \&= \var{t}}
         {\var{t}でも見つかった要素だけを持つ集合\var{s}を返します}
  \lineiii{\var{s}.difference_update(\var{t})}
         {\var{s} -= \var{t}}
         {\var{t}にあった要素を取り除いた後の集合\var{s}を返します}
  \lineiii{\var{s}.symmetric_difference_update(\var{t})}
         {\var{s} \textasciicircum= \var{t}}
         {\var{s}と\var{t}のどちらか一方に属する要素からなる集合
       \var{s}を返します}

  \hline
  \lineiii{\var{s}.add(\var{x})}{}
         {要素\var{x}を集合\var{s}に加えます}
  \lineiii{\var{s}.remove(\var{x})}{}
         {要素\var{x}を集合\var{s}から取り除きます; 
          \var{x} がなければ \exception{KeyError} を送出します}
  \lineiii{\var{s}.discard(\var{x})}{}
         {要素\var{x}が存在すれば、集合\var{s}から取り除きます}
  \lineiii{\var{s}.pop()}{}
         {\var{s}から要素を取り除き、それを返します;
         集合が空なら \exception{KeyError} を送出します}
  \lineiii{\var{s}.clear()}{}
         {集合\var{s}からすべての要素を取り除きます}
\end{tableiii}

演算子を使わない書き方である \method{update()}、 
\method{intersection_update()}、\method{difference_update()}、
および\method{symmetric_difference_update()} は任意の
イテレート可能オブジェクトを引数として受け取るので注意してください。
\versionchanged[以前は全ての引数が集合型でなければなりませんでした。]{2.3.1}

もう一つ注意を述べますが、このモジュールでは \method{union_update()}
が \method{update()} の別名として含まれています。
このメソッドは後方互換性のために残されているものです。
プログラマは組み込みの \class{set()} および \class{frozenset()} で
サポートされている \method{update()} を選ぶべきです。

\subsection{使用例 \label{set-example}}

\begin{verbatim}
>>> from sets import Set
>>> engineers = Set(['John', 'Jane', 'Jack', 'Janice'])
>>> programmers = Set(['Jack', 'Sam', 'Susan', 'Janice'])
>>> managers = Set(['Jane', 'Jack', 'Susan', 'Zack'])
>>> employees = engineers | programmers | managers           # union
>>> engineering_management = engineers & managers            # intersection
>>> fulltime_management = managers - engineers - programmers # difference
>>> engineers.add('Marvin')                                  # add element
>>> print engineers
Set(['Jane', 'Marvin', 'Janice', 'John', 'Jack'])
>>> employees.issuperset(engineers)           # superset test
False
>>> employees.union_update(engineers)         # update from another set
>>> employees.issuperset(engineers)
True
>>> for group in [engineers, programmers, managers, 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{不変に自動変換するためのプロトコル
            \label{immutable-transforms}}

集合は変更不可能な要素だけを含むことできます。
都合上、変更可能な\class{Set}オブジェクトは、集合要素として加えられる前に、
自動的に\class{ImmutableSet}へコピーします。
そのメカニズムはハッシュ可能な要素を常に加えることですが、
もしハッシュ不可能な場合は、その要素は変更不可能な等価物を返す
\method{__as_immutable__()}メソッドを持っているかどうかチェックされます。

\class{Set}オブジェクトは、\class{ImmutableSet}のインスタンスを返す
\method{__as_immutable__()}メソッドを持っているので、集合の集合を構築
することが可能です。

集合内のメンバーであることをチェックするために、
要素をハッシュする必要がある\method{__contains__()}メソッドと
\method{remove()}メソッドが、同様のメカニズムを必要としています。
これらのメソッドは要素がハッシュできるかチェックします。
もし出来なければ--\method{__hash__()},\method{__eq__()},\method{__ne__()}
のための一時的なメソッドを備えたクラスによってラップされた要素を返すメソッド--
\method{__as_temporarily_immutable__()}メソッドをチェックします。

代理メカニズムは、オリジナルの可変オブジェクトから分かれたコピーを
組み上げる手間を助けてくれます。

\class{Set}オブジェクトは、新しいクラス\class{_TemporarilyImmutableSet}
によってラップされた\class{Set}オブジェクトを返す、
\method{__as_temporarily_immutable__()}メソッドを実装します。

ハッシュ可能を与えるための2つのメカニズムは通常ユーザーに見えません。
しかしながら、マルチスレッド環境下においては、
\class{_TemporarilyImmutableSet}によって一時的にラップされたものを
持っているスレッドがあるときに、もう一つのスレッドが集合を更新することで、
衝突を発生させることができます。
言いかえれば、変更可能な集合の集合はスレッドセーフではありません。


\subsection{組み込み \class{set} 型との比較
            \label{comparison-to-builtin-set}}

組み込みの \class{set} および \class{frozenset} 型はこの \module{sets} で
学んだことを生かして設計されています。主な違いは次の通りです。

\begin{itemize}
\item \class{Set} と \class{ImmutableSet} は \class{set} と \class{frozenset}
      に改名されました。
\item \class{BaseSet} に相当するものはありません。代わりに
      \code{isinstance(x, (set, frozenset))} を使って下さい。
\item 組み込みのものに使われているハッシュアルゴリズムは、
      多くのデータ集合に対してずっと良い性能(少ない衝突)を実現します。
\item 組み込みのものはより空間効率良く pickle 化できます。
\item 組み込みのものには \method{union_update()} メソッドがありません。
      代わりに同じ機能の \method{update()} メソッドを使って下さい。
\item 組み込みのものには \method{_repr(sorted=True)} メソッドがありません。
      代わりに組み込み関数の \function{repr()} と \function{sorted()}
      を使って \code{repr(sorted(s))} として下さい。
\item 組み込みのものは変更不可能なものに自動で変換するプロトコルがありません。
      この機能は多くの人が困惑を覚えるわりに、コミュニティの誰からも実際的な
      使用例の報告がありませんでした。
\end{itemize}    
