A generic vector class for integers of width $w\in [1..64]$ . More...

#include <int_vector.hpp>

Public Types
typedef int_vector_trait < fixedIntWidth, size_type_class >::value_type	value_type
typedef int_vector_trait < fixedIntWidth, size_type_class >::iterator	iterator
typedef int_vector_trait < fixedIntWidth, size_type_class > ::const_iterator	const_iterator
typedef int_vector_trait < fixedIntWidth, size_type_class >::reference	reference
typedef int_vector_trait < fixedIntWidth, size_type_class > ::const_reference	const_reference
typedef int_vector_reference < int_vector > *	pointer
typedef const value_type *	const_pointer
typedef ptrdiff_t	difference_type
typedef size_type_class	size_type
typedef int_vector_trait < fixedIntWidth, size_type_class > ::int_width_type	int_width_type
typedef rank_support_v< 1, 1 >	rank_1_type
typedef rank_support_v< 0, 1 >	rank_0_type
typedef select_support_mcl< 1, 1 >	select_1_type
typedef select_support_mcl< 0, 1 >	select_0_type
Public Member Functions
	int_vector (size_type elements=0, value_type default_value=0, uint8_t intWidth=fixedIntWidth)
	Constructor for int_vector.
	int_vector (const int_vector &v)
	Copy constructor for int_vector.
	~int_vector ()
	Destructor for int_vector.
bool	empty () const
	Equivalent to size() == 0.
void	swap (int_vector &v)
	Swap method for int_vector.
void	resize (const size_type size)
	Resize the int_vector in terms of elements.
void	bit_resize (const size_type size)
	Resize the int_vector in terms of bits.
size_type	size () const
	The number of elements in the int_vector.
size_type	bit_size () const
	The number of bits in the int_vector.
size_type	capacity () const
	Returns the size of the occupied bits of the int_vector.
const uint64_t *	data () const
	Pointer to the raw data of the int_vector.
const value_type	get_int (size_type idx, const uint8_t len=64) const
	Get the integer value of the binary string of length len starting at position idx in the int_vector.
void	set_int (size_type idx, value_type x, const uint8_t len=64)
	Set the bits from position idx to idx+len-1 to the binary representation of integer x.
const uint8_t	get_int_width () const
	Returns the width of the integers which are accessed via the [] operator.
void	set_int_width (uint8_t intWidth)
	Sets the width of the integers which are accessed via the [] operator, if fixedIntWidth equals 0.
size_type	serialize (std::ostream &out, structure_tree_node *v=NULL, std::string name="", bool write_fixed_as_variable=false) const
	Serializes the int_vector to a stream.
void	load (std::istream &in)
	Load the int_vector for a stream.
reference	operator[] (const size_type &i)
	non const version of [] operator
const_reference	operator[] (const size_type &i) const
	const version of [] operator
int_vector &	operator= (const int_vector &v)
	Assignment operator for the int_vector.
bool	operator== (const int_vector< fixedIntWidth > &v) const
	Equality operator for two int_vectors.
bool	operator!= (const int_vector &v) const
	Inequality operator for two int_vectors.
bool	operator< (const int_vector &v) const
	Less operator for two int_vectors.
bool	operator> (const int_vector &v) const
	Greater operator for two int_vectors.
bool	operator<= (const int_vector &v) const
	Less or equal operator.
bool	operator>= (const int_vector &v) const
	Greater of equal operator.
const iterator	begin ()
	Iterator that points to the first element of the int_vector.
const iterator	end ()
	Iterator that points to the element after the last element of int_vector.
const const_iterator	begin () const
	Const iterator that points to the first element of the int_vector.
const const_iterator	end () const
	Const iterator that points to the element after the last element of int_vector.
template<>
int_vector< 64 >::reference	operator[] (const size_type &idx)
template<>
int_vector< 32 >::reference	operator[] (const size_type &idx)
template<>
int_vector< 16 >::reference	operator[] (const size_type &idx)
template<>
int_vector< 8 >::reference	operator[] (const size_type &idx)
template<>
int_vector< 0 >::const_reference	operator[] (const size_type &idx) const
template<>
int_vector< 64 >::const_reference	operator[] (const size_type &idx) const
template<>
int_vector< 32 >::const_reference	operator[] (const size_type &idx) const
template<>
int_vector< 16 >::const_reference	operator[] (const size_type &idx) const
template<>
int_vector< 8 >::const_reference	operator[] (const size_type &idx) const
template<>
int_vector< 1 >::const_reference	operator[] (const size_type &idx) const
Static Public Member Functions
static size_type	max_size ()
	Maximum size of the int_vector.
Friends
struct	int_vector_trait< fixedIntWidth, size_type_class >
class	int_vector_iterator_base< int_vector >
class	int_vector_iterator< int_vector >
class	int_vector_const_iterator< int_vector >
class	coder::elias_delta
class	coder::fibonacci
class	coder::ternary
class	int_vector_file_buffer< fixedIntWidth, size_type_class >
std::istream &	operator>> (std::istream &, int_vector< 1 > &)
	Operator to create an int_vector<1> (aka bit_vector) from an input stream.
void	util::set_random_bits (int_vector &v, int)
void	util::set_zero_bits (int_vector &v)
void	util::set_one_bits (int_vector &v)
void	util::bit_compress (int_vector &v)
void	util::set_all_values_to_k (int_vector &v, uint64_t k)
void	algorithm::calculate_sa (const unsigned char *c, typename int_vector< fixedIntWidth >::size_type len, int_vector< fixedIntWidth > &sa)

Detailed Description

template<uint8_t fixedIntWidth, class size_type_class>
class sdsl::int_vector< fixedIntWidth, size_type_class >

A generic vector class for integers of width $w\in [1..64]$ .

Author:

Simon Gog

   This generic vector class could be used to generate a vector
   that contains integers of fixed width \form#173.
   E.g.

sdsl::int_vector<34> v(10);

creates a vector that can hold ten integers of width 34. You could use the object like a container of the Standard Template Library (STL, see http://www.sgi.com/tech/stl/ ) as we have implemented all requirements for this concept. Therefore you could apply many algorithms of the stl to our datastructure. Let's have a look at bit_vector_and_stl.e.cpp for an example.

If you set the fixed width parameter to zero

sdsl::int_vector<0> v(10);

you get a vector v of 10 elements which can each hold a 64-bit integer by default. See the int_vector_variable.e.cpp example for the behavior of the vector if you change the int width by calling the set_int_width() method.

Constructor & Destructor Documentation

template<uint8_t fixedIntWidth, class size_type_class >

sdsl::int_vector< fixedIntWidth, size_type_class >::int_vector	(	size_type	elements = `0`,
		value_type	default_value = `0`,
		uint8_t	intWidth = `fixedIntWidth`
	)		`[inline]`

Constructor for int_vector.

Parameters:

elements	The number of elements in the int_vector. Default value is 0.
default_value	The default value to initialize the elements.
intWidth	The width of integers which could be accessed via the [] operator.

See also:: resize, set_int_width

template<uint8_t fixedIntWidth, class size_type_class >

sdsl::int_vector< fixedIntWidth, size_type_class >::int_vector ( const int_vector< fixedIntWidth, size_type_class > & v ) [inline]

Copy constructor for int_vector.

Parameters:

v	The int_vector to copy Required for the STL Assignable Concept

Member Function Documentation

template<uint8_t fixedIntWidth, class size_type_class >

const int_vector< fixedIntWidth, size_type_class >::iterator sdsl::int_vector< fixedIntWidth, size_type_class >::begin ( ) [inline]

Iterator that points to the first element of the int_vector.

Required for Container Concept of the STL. Complexity guaranty is O(1).

template<uint8_t fixedIntWidth, class size_type_class >

const int_vector< fixedIntWidth, size_type_class >::const_iterator sdsl::int_vector< fixedIntWidth, size_type_class >::begin ( ) const [inline]

Const iterator that points to the first element of the int_vector.

Required for Container Concept of the STL.

template<uint8_t fixedIntWidth, class size_type_class >

void sdsl::int_vector< fixedIntWidth, size_type_class >::bit_resize ( const size_type size )

Resize the int_vector in terms of bits.

Parameters:

size	The size to resize the int_vector in terms of bits.

template<uint8_t fixedIntWidth, class size_type_class >

int_vector< fixedIntWidth, size_type_class >::size_type sdsl::int_vector< fixedIntWidth, size_type_class >::bit_size ( ) const

The number of bits in the int_vector.

See also:: size, max_size, bit_size, capacity

template<uint8_t fixedIntWidth, class size_type_class >

int_vector< fixedIntWidth, size_type_class >::size_type sdsl::int_vector< fixedIntWidth, size_type_class >::capacity ( ) const [inline]

Returns the size of the occupied bits of the int_vector.

The capacity of a int_vector is greater or equal to the bit_size of the vector: capacity() >= bit_size().

See also:: size, bit_size, max_size, capacity

template<uint8_t fixedIntWidth, class size_type_class>

const uint64_t* sdsl::int_vector< fixedIntWidth, size_type_class >::data ( ) const [inline]

Pointer to the raw data of the int_vector.

Returns:: Const pointer to the raw data of the int_vector

template<uint8_t fixedIntWidth, class size_type_class >

bool sdsl::int_vector< fixedIntWidth, size_type_class >::empty ( ) const

Equivalent to size() == 0.

Required for the STL Container Concept

See also:: size()

template<uint8_t fixedIntWidth, class size_type_class >

const int_vector< fixedIntWidth, size_type_class >::iterator sdsl::int_vector< fixedIntWidth, size_type_class >::end ( ) [inline]

Iterator that points to the element after the last element of int_vector.

Required for Container Concept of the STL. Complexity guaranty is O(1).

template<uint8_t fixedIntWidth, class size_type_class >

const int_vector< fixedIntWidth, size_type_class >::const_iterator sdsl::int_vector< fixedIntWidth, size_type_class >::end ( ) const [inline]

Const iterator that points to the element after the last element of int_vector.

Required for Container Concept of the STL.

template<uint8_t fixedIntWidth, class size_type_class >

const int_vector< fixedIntWidth, size_type_class >::value_type sdsl::int_vector< fixedIntWidth, size_type_class >::get_int	(	size_type	idx,
		const uint8_t	len = `64`
	)		const `[inline]`

Get the integer value of the binary string of length len starting at position idx in the int_vector.

Parameters:

idx	Starting index of the binary representation of the integer.
len	Length of the binary representation of the integer. Default value is 64.

Returns:: The integer value of the binary string of length len starting at position idx.

See also:: setInt, getBit, setBit

template<uint8_t fixedIntWidth, class size_type_class >

const uint8_t sdsl::int_vector< fixedIntWidth, size_type_class >::get_int_width ( ) const

Returns the width of the integers which are accessed via the [] operator.

Returns:: The width of the integers which are accessed via the [] operator.

See also:: set_int_width

template<uint8_t fixedIntWidth, class size_type_class >

int_vector< fixedIntWidth, size_type_class >::size_type sdsl::int_vector< fixedIntWidth, size_type_class >::max_size ( ) [static]

Maximum size of the int_vector.

Required for the Container Concept of the STL.

See also:: size, bit_size, capacity

template<uint8_t fixedIntWidth, class size_type_class >

bool sdsl::int_vector< fixedIntWidth, size_type_class >::operator!= ( const int_vector< fixedIntWidth, size_type_class > & v ) const

Inequality operator for two int_vectors.

Two int_vectors are not equal if

capacities and sizes are not equal or
- IntWidths are not equal or
- the bits in the range [0..bit_size()-1] are not equal.
Required for the STL Equality Comparable Concept.

See also:
operator==

template<uint8_t fixedIntWidth, class size_type_class >

bool sdsl::int_vector< fixedIntWidth, size_type_class >::operator< ( const int_vector< fixedIntWidth, size_type_class > & v ) const

Less operator for two int_vectors.

int_vector w is less than v if

w[i]==v[i] for i<j and w[j]<v[j] with j in [0, min(w.size(), v.size()) )
or w[i]==v[i] for all i < min(w.size(), v.size()) and w.size()<v.size().

Required for the STL LessThan Comparable Concept.

See also:
operator>

template<uint8_t fixedIntWidth, class size_type_class >

bool sdsl::int_vector< fixedIntWidth, size_type_class >::operator<= ( const int_vector< fixedIntWidth, size_type_class > & v ) const

Less or equal operator.

Required for the STL LessThan Comparable Concept.

See also:: operator>=, operator==, operator<

template<uint8_t fixedIntWidth, class size_type_class >

int_vector< fixedIntWidth, size_type_class > & sdsl::int_vector< fixedIntWidth, size_type_class >::operator= ( const int_vector< fixedIntWidth, size_type_class > & v )

Assignment operator for the int_vector.

Parameters:

v	The vector v which should be assigned

Returns:: A copy of v.

Required for the Assignable Conecpt of the STL.

template<uint8_t fixedIntWidth, class size_type_class >

bool sdsl::int_vector< fixedIntWidth, size_type_class >::operator== ( const int_vector< fixedIntWidth > & v ) const

Equality operator for two int_vectors.

Two int_vectors are equal if

capacities and sizes are equal and
- IntWidths are equal and
- the bits in the range [0..bit_size()-1] are equal.
Required for the STL Equality Comparable Concept.

See also:
operator!=

template<uint8_t fixedIntWidth, class size_type_class >

bool sdsl::int_vector< fixedIntWidth, size_type_class >::operator> ( const int_vector< fixedIntWidth, size_type_class > & v ) const

Greater operator for two int_vectors.

int_vector w is greater than v if

w[i]==v[i] for i<j and w[j]>v[j] with j in [0, min(w.size(), v.size()) )
or w[i]==v[i] for all i < min(w.size(), v.size()) and w.size()>v.size().

Required for the STL LessThan Comparable Concept.

See also:
operator<

template<uint8_t fixedIntWidth, class size_type_class >

bool sdsl::int_vector< fixedIntWidth, size_type_class >::operator>= ( const int_vector< fixedIntWidth, size_type_class > & v ) const

Greater of equal operator.

Required for the STL LessThan Comparable Concept.

See also:: operator<=, operator==, operator>

template<uint8_t fixedIntWidth, class size_type_class >

int_vector< fixedIntWidth, size_type_class >::reference sdsl::int_vector< fixedIntWidth, size_type_class >::operator[] ( const size_type & i ) [inline]

non const version of [] operator

Parameters:

i	Index the i-th integer of length get_int_width().

Returns:: A reference to the i-th integer of length get_int_width().

Required for the STL Random Access Container Concept.

template<uint8_t fixedIntWidth, class size_type_class >

int_vector< fixedIntWidth, size_type_class >::const_reference sdsl::int_vector< fixedIntWidth, size_type_class >::operator[] ( const size_type & i ) const [inline]

const version of [] operator

Parameters:

i	Index the i-th integer of length get_int_width().

Returns:: The value of the i-th integer of length get_int_width().

Required for the STL Random Access Container Concept.

template<uint8_t fixedIntWidth, class size_type_class >

void sdsl::int_vector< fixedIntWidth, size_type_class >::resize ( const size_type size )

Resize the int_vector in terms of elements.

Parameters:

size	The size to resize the int_vector in terms of elements.

Required for the Sequence Concept of the STL.

template<uint8_t fixedIntWidth, class size_type_class>

int_vector< fixedIntWidth, size_type_class >::size_type sdsl::int_vector< fixedIntWidth, size_type_class >::serialize	(	std::ostream &	out,
		structure_tree_node *	v = `NULL`,
		std::string	name = `""`,
		bool	write_fixed_as_variable = `false`
	)		const

Serializes the int_vector to a stream.

Returns:: The number of bytes written to out.

See also:: load

template<uint8_t fixedIntWidth, class size_type_class >

void sdsl::int_vector< fixedIntWidth, size_type_class >::set_int	(	size_type	idx,
		value_type	x,
		const uint8_t	len = `64`
	)		`[inline]`

Set the bits from position idx to idx+len-1 to the binary representation of integer x.

The bit at position idx represents the least significant bit(lsb), and the bit at position idx+len-1 the most significant bit (msb) of x.

Parameters:

idx	Starting index of the binary representation of x.
x	The integer to store in the int_vector.
len	The length used to store x in the int_vector. Default value is 64.

See also:: getInt, getBit, setBit

template<uint8_t fixedIntWidth, class size_type_class >

void sdsl::int_vector< fixedIntWidth, size_type_class >::set_int_width ( uint8_t intWidth )

Sets the width of the integers which are accessed via the [] operator, if fixedIntWidth equals 0.

Parameters:

intWidth New width of the integers accessed via the [] operator.

Note:: This method has no effect if fixedIntWidth is in the range [1..64].

See also:: get_int_width

template<uint8_t fixedIntWidth, class size_type_class >

int_vector< fixedIntWidth, size_type_class >::size_type sdsl::int_vector< fixedIntWidth, size_type_class >::size ( ) const

The number of elements in the int_vector.

Required for the Container Concept of the STL.

See also:: max_size, bit_size, capacity

The documentation for this class was generated from the following file:

sdsl/include/sdsl/int_vector.hpp

Public Types

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

template<uint8_t fixedIntWidth, class size_type_class> class sdsl::int_vector< fixedIntWidth, size_type_class >

Constructor & Destructor Documentation

Member Function Documentation

template<uint8_t fixedIntWidth, class size_type_class>
class sdsl::int_vector< fixedIntWidth, size_type_class >