Vector Classes

Prerequisits

#include <Vector.h>
#include <SparseVector.h>

using namespace polymake;

Introduction

The Vector class family implement vectors in the usual algebraic notion. It contains three persistent vector types with different data storage organization:

template <typename ElementType> class Vector;

holds the elements in a contiguous array.

template <typename ElementType> class SparseVector;

is an associative container with element indices (coordinates) as keys; elements equal to the default value (lementTypeE(), which is 0 for most numerical types) are not stored, but implicitly encoded by the gaps in the key set. It is based on a balanced binary search (AVL) tree.

template <typename ElementType, int size> class FixedVector;

is a built-in array of a fixed dimension decorated with the common vector interface.

The following brief analysis might help you when choosing the most efficient representation for a concrete case. n is the number of (non-zero in sparse case) elements in the vector.

if no preceding random access operations were performed on the sparse vector

if there already were random access operations on the sparse vector

Performance comparison
Operation	`Vector`	`SparseVector`
sequential iteration	O(n)	O(n), but with greater overhead constant
random element access	O(1)	O(log(n))
append an element	O(n) + reallocation costs	O(1) or O(log(n))

Vector and SparseVector keep the data attached to a smart pointer with reference counting.

Generic type

template <typename Top, typename ElementType=typename Top::element_type> class GenericVector;

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

`element_type`	`ElementType`, the persistent element type
`top_type`	`Top`, the concrete vector object behind the generic reference
`generic_type`	`GenericVector<Top>` itself
`persistent_type`	`Vector<ElementType>` for dense vectors, `SparseVector<ElementType>` for sparse vectors.

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

Construction

Any persistent class: Vector, SparseVector, or FixedVector. In the latter case the dimension argument is ignored, as the vector dimension is hard encoded into the object type.

Vector or FixedVector. In the latter case the dimension argument is ignored, as the vector dimension is hard encoded into the object type.

Vector();

Create a vector of dimension 0.

explicit Vector (int n);

Create a vector of dimension n, initialize all elements with 0 (in SparseVector implicitly.)

Vector (int n, const ElementType& value);

Create a vector of dimension n, initialize all elements with value. Use of corresponding constructor for SparseVector would defeat all the advantages of the sparse structure, therefore it is not defined.

template <typename Iterator>

Vector (int n, Iterator src);

Create a vector of dimension n, initialize the elements from a data sequence. For SparseVector, Iterator can be either indexed, or supply index-value pairs, e.g. std::pair<int, ElementType> or a plain sequence of data items. In the latter case zero elements are filtered out.

template <typename OtherVector>

Vector (const GenericVector<OtherVector, ElementType>&);

Create a vector as a copy of another vector of the same element type.

template <typename OtherVector, typename OtherElementType>

explicit Vector (const GenericVector<OtherVector, OtherElementType>&);

Copying with element conversion is also possible, but requires an explicit constructor call.

template <int n>

Vector (const ElementType (&a)[n]);

Create a vector of dimension n, copy element values from a built-in array.

GenericVector convert_to<OtherElementType> (const GenericVector&);

Create a vector with another element type, using explicit type conversion.

Modification

Any persistent vector: Vector or SparseVector, or an alias object referring to a mutable (non-const) vector.

SparseVector or an alias object referring to a mutable sparse vector.

This assertion is active only in the debugging compilation mode.

template <typename OtherVector>

GenericVector::operator= (const GenericVector<OtherVector, ElementType>&);

template <int n>

GenericVector::operator= (const ElementType (&a)[n]);

Persistent vector objects have after the assignment the same dimension as the right hand side operand. Alias objects, such as vector slice or concatenated vector, cannot be resized, thus they must have the same dimension as on the right hand side.

void std::swap(GenericVector&, GenericVector&);

Swap the contents of two vectors in a most efficient way. If at least one non-persistent object is involved, the operands must have equal dimension.

void Vector::resize(int n);

Extend or truncate to the new dimension. In the case of extension new elements are initialized with 0 (in SparseVector implicitly.)

void Vector::clear();

Truncate to dimension 0.

template <typename Scalar>

void GenericVector::fill(const Scalar& value);

Fill with given value without changing the dimension. value can be of arbitrary type assignable to ElementType.

void GenericVector::remove0s();

Physically remove all zero elements from a sparse vector that might have creeped in by some previous operation.

Element access

int GenericVector::dim() const;

Tell the current vector dimension. For dense vectors it is always the same as size(). For sparse vectors, however, the latter tells the number of non-zero elements.

Sequential access

All vector classes implement the STL Forward Container interface or one of its refinements. This means, every vector 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.

For a vector object accessed via GenericVector reference or pointer, you need first get to the concrete class with top() method before you can use the standard container interface.

SparseVector inherits the data access methods from the binary tree. Note that dereferencing the SparseVector::iterator yields a reference to the element value, not a key-value pair as in the std::map class or other associative containers. The SparseVector::iterator::index() method tells the current element index (coordinate.)

Random access

Random-access vector object: Vector, concatenation of random-access vectors, or a slice of a random-access vector with a random-access index set (sequence or series).

The real return type is a temporary proxy object, forwarding the read/write access operations to the sparse vector. Prior to the destruction, which happens after the completion of the expression envolving the random access, it checks whether the element became zero; if so, it is removed from the vector.

ElementType& Vector::operator[] (int i);

const ElementType& Vector::operator[] (int i) const;

The index range check can be activated.

ElementType& SparseVector::operator[] (int i);

const ElementType& SparseVector::operator[] (int i) const;

The index range check can be activated. The const operator returns a reference to a static zero object if the specified element is an implicit 0.

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 a vector expression as a GenericVector argument to a template function where it has a chance to be evaluated multiple times. See also prevent_lazy class.

The vector and matrix operators defined in the Polymake Template Library do take care of this, so this remark applies more likely to your own functions.

The concrete vector type hidden behind the GenericVector.

const GenericVector operator- (const GenericVector&);

const GenericVector operator+ (const GenericVector&, const GenericVector&);

const GenericVector operator- (const GenericVector&, const GenericVector&);

const GenericVector operator* (const Scalar&, const GenericVector&);

const GenericVector operator* (const GenericVector&, const Scalar&);

const GenericVector operator/ (const GenericVector&, const Scalar&);

ElementType operator* (const GenericVector&, const GenericVector&);

Do exactly what the mnemonics suggest. Every type combination is allowed, including mixing of sparse and dense vectors. ElementType of vector operands and Scalar type can be different, provided the arithmetic operator with corresponding arguments exists. The dimension check can be activated.

Top& GenericVector::negate();

Top& GenericVector::operator+= (const GenericVector&);

Top& GenericVector::operator-= (const GenericVector&);

Top& GenericVector::operator*= (const Scalar&);

Top& GenericVector::operator/= (const Scalar&);

Corresponding assignment versions of the arithmetic operators.

ElementType sqr(const GenericVector& a);

Scalar product a∗a.

const GenericVector tensor_product(const GenericVector& a, const GenericVector& b);

Tensor product T=a ⊗ b: T[i∗b.dim() + j] = a[i] ∗ b[j].

bool operator== (const GenericVector&, const GenericVector&);

bool operator!= (const GenericVector&, const GenericVector&);

bool operator< (const GenericVector&, const GenericVector&);

bool operator> (const GenericVector&, const GenericVector&);

bool operator<= (const GenericVector&, const GenericVector&);

bool operator>= (const GenericVector&, const GenericVector&);

Compare two vectors lexicographically.

namespace std_ext {
   template <typename ElementType> struct hash< Vector<ElementType> >;
   template <typename ElementType> struct hash< SparseVector<ElementType> >;
}

These specializations allow to use the vectors as search keys in the containers std_ext::hash_set and std_ext::hash_map.

Other constructions

The real result type is a temporary alias object of type pm::VectorSlice. It inherits the const-ness from the original vector.

The real result type is a temporary alias object of type pm::VectorChain. It is mutable only if both operands are mutable too.

The real result type is a masquerade reference pm::SingleElementVector&.

The real result type is a temporary object of type pm::SameElementVector. It contains only a single copy of an element, or just a reference to an element, but makes it to appear as a sequence of identical elements.

The real result type is a temporary object of type pm::SameElementSparseVector. It contains only a single copy of an element, or just a reference to it, but makes it to appear as a sequence of elements.

A GenericSet or Complement is allowed here.

GenericVector GenericVector::slice (const IndexSet& indices);

GenericVector GenericVector::slice (int start, int size=0);

Select a vector slice consisting of elements with given indices. The last variant selects a contiguous range of indices beginning with start. size==0 means up to the end of the vector. The const variants of these methods create immutable slice objects. The index range check can be activated.

GenericVector operator| (const GenericVector&, const GenericVector&);

GenericVector operator| (const Scalar&, const GenericVector&);

GenericVector operator| (const GenericVector&, const Scalar&);

Concatenate two vectors, yielding a longer vector. A scalar argument is treated as a vector of dimension 1. ElementType of vector operands must be identical, otherwise you will get a rather cryptic message from the compiler.

Vector& Vector::operator|= (const GenericVector&);

Vector& Vector::operator|= (const Scalar&);

Append a vector or a scalar, increasing the vector dimension.

const GenericVector scalar2vector(const ElementType& x);

const GenericVector scalar2sparse_vector(const ElementType& x);

Disguise x as a dense rsp. sparse vector of dimension 1.

const GenericVector same_element_vector(const ElementType& x, int n);

const GenericVector ones_vector<ElementType>(int n);

const GenericVector zero_vector<ElementType>(int n);

Create a dense vector of dimension n, with all elements equal to x, 1, or 0, respectively. Note the obligatory explicit specification of the template parameter ElementType, where it cannot be deduced from the function arguments.

const GenericVector same_element_sparse_vector<ElementType> (const Set& indices, int n);

const GenericVector same_element_sparse_vector (const Set& indices, const ElementType& x, int n);

Create a sparse vector of dimension n, with elements equal to x at given coordinates and 0 as the rest (vice versa by Complement.) If omitted, x is taken as 1; note the obligatory explicit template parameter specification in this case.

const GenericVector unit_vector(int n, int i, const ElementType& x);

const GenericVector unit_vector<ElementType>(int n, int i);

Create a sparse vector of dimension n, whose only non-zero element has the coordinate i and value x. If omitted, x is taken as 1; note the obligatory explicit template parameter specification in this case.

Input/output

std::ostream& operator<< (std::ostream&, const GenericVector&);

If std::ostream::width() is not 0 before the operator is called, each element of a vector is printed in a width-wide field; lacking elements of a sparse vector are printed as dots.

If width is 0, a dense vector as well as a sparse vector with fill grade over 0.5 is printed as a space-separated list of elements. A "really" sparse vector appears as a list of (index value) pairs.

std::istream& operator>> (std::istream&, GenericVector&);

Read the space-separated data items from the input stream and assign them to the vector elements. The current dimension of the vector is not changed. When reading a sparse vector, single dots and items equal to zero are not stored.

explicit Vector (Poly&);

Poly& operator>> (Poly&, Vector&);

Read a property from the polymake server. Set the vector dimension to the number of elements read. Parse errors are reported by raising the std::iostream::failure exception in the constructor, or via std::iostream::fail() flag in the input operator.