Either GenericSet compatible to another operand (that is, having the same element and comparator types), or a Complement of a compatible set.
Either a functor class satisfying the extended requirements for binary operations, or an untyped template of such a class wrapped into BuildBinary or BuildBinaryIt (preferably expressed via the convenience typedef from namespace polymake::operations.
Set or a row (column) of a mutable (non-const) IncidenceMatrix.
Either both operands are GenericSet with the same element and comparator types, or one operand is a scalar having the type ElementType of another operand. In the latter case it is treated as an one-element set with ElementComparator borrowed from another operand.
The real result type is a masquerade reference pm::OrderedContainer&.
Either GenericSet compatible to another operand (that is, having the same element and comparator types), or a Complement of a compatible set, or a scalar having the type ElementType of another operand. In the latter case it is treated as an one-element set with ElementComparator borrowed from another operand.
This assertion is checked only in the AVL_CHECKS compilation mode.
The concrete set type hidden behind the GenericSet.
Either a functor class satisfying the extended requirements for unary operations, or an untyped template of such a class wrapped into BuildUnary or BuildUnaryIt (preferably expressed via the convenience typedef from namespace polymake::operations.
The real return type is a temporary object (expression template) implementing the lazy evaluation of the operation result. You should have it in mind when passing the result of an expression as a GenericSet argument to a template function where it has a chance to be evaluated multiple times. See also prevent_lazy class.
In particular, this incurs that calling the size() method on such a lazy object will effectively perform the entire operation. On the contrary, empty() will run until the first resulting element is found, so it should be preferred to size() whenever possible.
The operators defined in the Polymake Template Library do take care of this, so these remarks apply more likely to your own functions.
The real result type is a masquerade reference pm::SingleElementSet&.
The real result type is a masquerade reference Indices&.

### Prerequisits

    #include <Set.h>
    using namespace polymake;

### Introduction

template <typename ElementType, typename ElementComparator=operations::cmp> class Set;

An associative container based on a balanced binary search (AVL) tree. ElementComparator is a comparator functor defining a total ordering on the element value domain. In the most cases, the default choice (lexicographical order) will suffice your needs.

The data tree is attached to the Set object via a smart pointer with reference counting.

### Generic type

template <typename _Set, typename ElementType=typename _Set::element_type, typename ElementComparator=typename _Set::element_comparator> class GenericSet;

The parent generic class for all set classes. Defines the following types:

element_type | ElementType, the persistent element type
element_comparator | ElementComparator, the comparator functor for the elements
top_type | _Set, the concrete set object behind the generic reference
generic_type | GenericSet<_Set> itself
persistent_type | Set<ElementType, ElementComparator>

Methods and friend functions applicable to GenericSet directly are scattered over the entire page. They are discernible on the prefix GenericSet:: or parameters of type GenericSet&. To use other methods via a generic reference (or pointer), you must first move to the concrete object using the top() method.

### Construction

Set(); explicit Set (const ElementComparator&);
Create an empty set. Initialize the element comparator with its default constructor (the first variant) or from a given prototype (the second variant).
template <typename Iterator> Set (Iterator src, Iterator src_end); template <typename Iterator> Set (Iterator src, end_sensitive);
Initialize the elements from an input sequence. The input data items must follow in the ascending order in the sense of the ElementComparator.
The only purpose of the dummy argument end_sensitive is to signal that the first argument src has to be treated as an end-sensitive iterator. A template constructor with a single argument would shadow all other constructors away!
template <typename OtherSet> Set (const GenericSet<OtherSet, ElementType, ElementComparator>&);
Create a set as a copy of another set with the same element and comparator types.
template <typename OtherSet, typename OtherElementType, typename OtherElementComparator> explicit Set (const GenericSet<OtherSet, OtherElementType, OtherElementComparator>&);
Copying with element conversion is also possible, but requires an explicit constructor call. Both source and target comparators must define the same element ordering.
template <int n> explicit Set (const ElementType (&a)[n]);
Create a set with elements copied from a built-in array. The array elements must follow in the ascending order in the sense of the ElementComparator.

### Modification

template <typename OtherSet> GenericSet::operator= (const GenericSet<OtherSet, ElementType, ElementComparator>&);
Assign elements from another set.
void std::swap(GenericSet&, GenericSet&);
Swap the contents of two sets in a most efficient way.
void GenericSet::clear();
Make the set empty.

### Element access

All set classes implement the STL Forward Container interface or one of its refinements. This means, every set object can be traversed using an iterator or const_iterator created by begin() method or entire() function, its size can be retrieved with size() method and so on.

Set class as well as rows and columns of an IncidenceMatrix also inherit the AVL tree data access interface, as well as following methods:

bool Set::contains(const ElementType&);
Check whether an element belongs to the set.

### Set-theoretic operations

const GenericSet operator+ (const GenericSet&, const GenericSet&);
Set union.
const GenericSet operator- (const GenericSet&, const GenericSet&);
Set difference.
const GenericSet operator* (const GenericSet&, const GenericSet&);
Set intersection.
const GenericSet operator^ (const GenericSet&, const GenericSet&);
Symmetric difference.
_Set& GenericSet::operator+= (const GenericSet&); _Set& GenericSet::operator-= (const GenericSet&); _Set& GenericSet::operator*= (const GenericSet&); _Set& GenericSet::operator^= (const GenericSet&);
Corresponding assignment versions of the set-theoretic operations.
bool operator== (const GenericSet&, const GenericSet&); bool operator!= (const GenericSet&, const GenericSet&); bool operator< (const GenericSet&, const GenericSet&); bool operator> (const GenericSet&, const GenericSet&); bool operator<= (const GenericSet&, const GenericSet&); bool operator>= (const GenericSet&, const GenericSet&);
Compare two sets lexicographically.
namespace std_ext { template <typename ElementType, typename ElementComparator> struct hash< Set<ElementType, ElementComparator> >; template <> struct hash<Bitset>; }
These specializations allow to use the sets as search keys in the containers std_ext::hash_set and std_ext::hash_map.
int incl(const GenericSet& s1, const GenericSet& s2);
Analyze the inclusion relation of two sets. Return value is:

0 | s1 = s2
-1 | s1 ⊂ s2
1 | s1 ⊃ s2
2 | none of above; s1 and s2 are independent

Set& Set::select(const GenericSet& index_set); Set& Set::select(const Complement& index_set);
Select a subset, remove the rest. index_set contains the indices (ordinal numbers) of elements to be kept (or removed as in the Complement case.) The index of the first element is 0.

### Other constructions

const Complement& operator~ (const GenericSet&);
Denote the complement of a given set. The return value is a masquerade reference, it cannot be treated as an independent object.
A complement can be used only in a context where the universal set of all possible elements is restricted by other involved operands. This includes the set intersection and difference, as well as various subset selection methods: select, Set::select, GenericVector::slice, GenericMatrix::minor, etc.
const GenericSet scalar2set(const ElementType& x); const GenericSet scalar2set<ElementComparator>(const ElementType& x);
Disguise x as a set with a single element. The first variant assumes the default element comparator cmp<ElementType> , the second variant allows to specify an alternative comparator.
const Set<int> indices(const SparseContainer& c);
Treate the indices of elements of an arbitrary sparse container as a set of integer numbers.
const GenericSet assure_ordered(const Container& c); const GenericSet assure_ordered<ElementComparator>(const Container& c);
Disguise an arbitrary container as an ordered set. This function does not check the element ordering; it just says: "provided the elements are properly sorted, this container can be used everywhere a GenericSet is accepted." If not, any further results are undefined.

### Arithmetic series

template <typename ElementType, bool step_equal_1> class Series; typedef Series<int, true> sequence; typedef Series<int, false> series;

An arithmetic series is a special case of a set, it belongs to the GenericSet family. Since the elements can be easily computed, the series can be encoded in a particulary compact form. For the ElementType, the arithmetic operators +, -, +=, -=, ++, -- must be defined.

sequence and series are aliases introduced for convenience.

The boolean template parameter step_equal_1 serves as a compile-time announcement of a yet more special case, a series with the step 1. Although this case can be obviously covered by a general series, this specialization allows for additional compiler optimization, taking into account the fact that the elements build a contigous range of integer values. This is especially important by building indexed subsets (GenericVector::slice, GenericMatrix::minor, etc.) Hence, always use sequence when the selected indices are contiguous.

Series();
The default constructor creates a series of length 0, with starting element 0.
Series(ElementType start, int length, ElementType step=1);
Create a series with given starting element and length. The step argument can be specified for contiguous sequences (step_equal_1==true ) too, but is ignored.
Series<ElementType, true> range(ElementType first, ElementType last);
Create a contiguous series with starting element first and length last-first+1, which means, last belongs to the created set.
ElementType Series::step() const;
Tell the step magnitude.
bool Series::contains(ElementType x) const;
check if x is an element of the series.

In addition, Series implements the Random Access Container interface.