All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
Namespaces | Classes | Functions
paal::data_structures Namespace Reference

Data Structure namespace. More...

Namespaces

 concepts
 Concepts of Data Structure namespace.
 
 detail
 Detail of Data Structure namespace.
 

Classes

class  bimap_mic
 the same as Bimap, but implemented using boost::multi_index_container. Unfortunately slower More...
 
class  bimap
 implements both sides mapping from the collection to (0,size(collection)) interval. More...
 
class  eraseable_bimap
 this maps support erasing elements, Alert inefficient!! More...
 
class  bimap_of_consecutive
 in this bimap we know that elements forms permutation this allows optimization More...
 
struct  bimap_traits< bimap< ValT, IdxT > >
 traits specialization for Bimap More...
 
struct  bimap_traits< eraseable_bimap< ValT, IdxT > >
 traits specialization for eraseable_bimap More...
 
struct  bimap_traits< bimap_of_consecutive< ValT, IdxT > >
 traits specialization for bimap_of_consecutive More...
 
struct  bimap_traits< bimap_mic< ValT, IdxT > >
 traits specialization for bimap_mic More...
 
struct  bimap_traits
 
class  collection_starts_from_last_change
 this collection stores some range and expose set_last_change function each time begin and end is called this class returns range which starts from last change place More...
 
class  combine_iterator_engine
 class representing set of ranges with two operation next and call More...
 
class  combine_iterator_engine< Range, RangesRest...>
 
class  combine_iterator_engine<>
 specialization for empty ranges lists More...
 
class  combine_iterator
 combine_iterator iterates through all combinations of values from given ranges and returns them joined together using given Joiner More...
 
struct  component_traits
 
struct  component_traits< detail::components< Names, Types > >
 
struct  NameWithDefault
 This structure can be passed on Names list and represents Name and the default type value. More...
 
struct  copy_tag
 Indicates that components constructor is in fact a Copy/Move Constructor. More...
 
class  components
 
struct  join
 detail More...
 
struct  join< components< NameWithDefault< Name1, Default1 >, ComponentNamesWithDefaults1...>, components<> >
 First components class has only names with defaults, second components class is empty. This case cannot be simplified to just "Second components class is empty" to disambiguate pattern matching. More...
 
struct  join< components< NameWithDefault< Name1, Default1 >, ComponentNamesWithDefaults1...>, components< NameWithDefault< Name2, Default2 >, ComponentNamesWithDefaults2...> >
 Both components classes have only names with defaults. More...
 
struct  join< components< NameWithDefault< Name1, Default1 >, ComponentNamesWithDefaults1...>, components< ComponentName2, ComponentNamesWithDefaults2...> >
 First components class has only names with defaults. More...
 
struct  join< components<>, components< ComponentNamesWithDefaults2...> >
 First components class is empty. More...
 
struct  join< components< ComponentName1, ComponentNamesWithDefaults1...>, components< ComponentNamesWithDefaults2...>>
 Normal case. More...
 
class  replaced_type
 Generic version of replaced_type. More...
 
class  replaced_type< Name, NewType, detail::components< Names, Types > >
 
struct  TypesVector
 TypesVector. More...
 
struct  size
 Computes size of TypesVector. More...
 
struct  size< TypesVector< Args...> >
 Computes size of TypesVector. More...
 
struct  fold
 Standard fold function implementation. More...
 
struct  fold< TypesVector< Arg, Args...>, StartValue, Functor >
 Standard fold function implementation. More...
 
struct  fold< TypesVector<>, StartValue, Functor >
 Standard fold function implementation, empty list case. More...
 
struct  push_back
 push back given val to TypesVector More...
 
struct  push_back< TypesVector< Args...>, Val >
 push back given val to TypesVector More...
 
struct  at
 gives element on id in TypesVector More...
 
struct  at< TypesVector< Arg, Args...>, std::integral_constant< C, i > >
 gives element on id in TypesVector More...
 
struct  at< TypesVector< Arg, Args...>, std::integral_constant< C, 0 > >
 gives element on id in TypesVector, at 0 case More...
 
struct  join< TypesVector< Args1...>, TypesVector< Args2...> >
 joins to TypesVectors, implementation More...
 
struct  remove_n_first
 removes first n elements from given TypesVector More...
 
struct  remove_n_first< n, TypesVector< Arg, Args...> >
 removes first n elements from given TypesVector More...
 
struct  remove_n_first< 0, TypesVector< Arg, Args...> >
 two cases below cannot be one becasuse of ambiguity in instancaition More...
 
struct  remove_n_first< 0, TypesVector<> >
 removes first n elements from given TypesVector, n=0 case More...
 
struct  pos
 returns pos of the element in the TypesVector More...
 
struct  pos< Type, TypesVector< TypesPrefix, TypesSufix...> >
 returns pos of Type in given TypeList More...
 
struct  pos< Type, TypesVector< Type, TypesSufix...> >
 
struct  replace_at_pos
 replace element at pos to NewType More...
 
struct  replace_at_pos< pos, NewType, TypesVector< TypesPrefix, TypesSufix...> >
 replace type at pos to new type More...
 
struct  replace_at_pos< 0, NewType, TypesVector< TypesPrefix, TypesSufix...> >
 replace type at pos to new type, specialization for pos = 0 More...
 
class  cycle_start_from_last_change
 adopts any cycle to start (vbegin) i place of the last change(flip) More...
 
struct  cycle_traits
 traits for Cycle concept More...
 
class  simple_cycle
 This is the simplest implementation of the Cycle concept based on the list. More...
 
class  Simplecycle_start_from_last_change
 this class adapts Simple cycle to start from last changed position More...
 
class  splay_cycle
 Cycle based on splay tree. More...
 
class  cycle_iterator
 For given collection (begin -> end) and start iterator pointing to an element inside collection (begin -> ... -> start -> ... ->end), returns new collection created by shifting the old collection to start. More...
 
class  facility_location_solution
 describes solution to facility location The initial solution is passed as voronoi, which has to be the model of the Voronoi concept. The generators of the voronoi are the facilities and the vertices are the clients. More...
 
class  facility_location_solution_traits< facility_location_solution< FacilityCost, Voronoi > >
 traits for facility_location_solution More...
 
class  facility_location_solution_traits
 
class  k_median_solution
 solution for k median problem More...
 
class  facility_location_solution_traits< data_structures::k_median_solution< voronoi > >
 specialization of facility_location_solution_traits More...
 
struct  fraction
 simple class to represent fraction More...
 
class  mapped_file
 data structure that gets new lines for many threads More...
 
class  rectangle_array_metric
 Metric implementation on 2 dimensional array distance calls on this metric are valid opnly when x < N and y < M (N and M given in the constructor) when we know that only certain calls occurs it might be worthwhile to use this metric More...
 
class  array_metric
 this metric is rectangle_array_metric with N == M. More...
 
struct  euclidean_metric
 metric with euclidean distance More...
 
struct  metric_traits< euclidean_metric< T > >
 
struct  graph_metric_traits
 traits for graph metric More...
 
struct  graph_metric_filler_impl
 generic strategies of computing metric More...
 
struct  graph_metric_filler_impl< graph_type::sparse_tag >
 specialization for sparse_tag graphs More...
 
struct  graph_metric_filler_impl< graph_type::dense_tag >
 specialization strategies of computing metric for dense_tag graphs More...
 
class  graph_metric
 Adopts boost graph as Metric. More...
 
struct  graph_metric< Graph, DistanceType, graph_type::large_tag >
 Specialization for large graphs. More...
 
struct  graph_metric_traits< boost::adjacency_list< OutEdgeList, VertexList, Directed, VertexProperties, EdgeProperties, GraphProperties, EdgeList > >
 Specialization for adjacency_list. More...
 
struct  graph_metric_traits< boost::adjacency_matrix< Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator > >
 Specialization for adjacency_matrix. More...
 
struct  read_values_tag
 
struct  read_indexes_tag
 
class  metric_on_idx
 This metric keeps inner metric and index. Given vertices are reindex and passed to inner metric. More...
 
struct  metric_traits< metric_on_idx< Metric, Bimap, read_indexes_tag > >
 
struct  metric_traits< metric_on_idx< Metric, Bimap, read_values_tag > >
 
struct  adjacency_matrix
 type of adjacency_matrix, for given metric More...
 
struct  _metric_traits
 base for metric traits More...
 
struct  metric_traits
 metric traits More...
 
class  object_with_copy
 keeps object and its copy. Invoke all the member functions on both: object and its copy. If you want to invoke member function on both objects, you run the object_with_copy::invoke. If you want to run member function only on the copy you run object_with_copy::invoke_on_copy. More...
 
class  splay_tree
 detail More...
 
class  stack
 Stack. More...
 
class  subsets_iterator_engine
 
class  subsets_iterator_engine< 0, Iterator >
 specialization for k==0 for boundary cases. This class stores iterator pointing to the end of the input collection More...
 
class  subsets_iterator
 Iterator to all k-subsets of given collection. More...
 
struct  tabu_list_remember_move
 This Tabu list remember some number of last moves. More...
 
class  tabu_list_remember_solution_and_move
 This Tabu list remember both current solution and move It is implemented as tabu_list_remember_move<pair<Solution, Move>> with nullptr passed as dummy solution. More...
 
struct  is_sparse_row
 
struct  is_sparse_row< RowType, typename std::enable_if< std::is_same< typename paal::decay_t< RowType >::container_type::storage_category, boost::numeric::ublas::sparse_tag >::value >::type >
 
struct  matrix_type_traits
 Traits class for matrix related types. More...
 
struct  matrix_type_traits< boost::numeric::ublas::matrix< T > >
 Specialization matrix_type_traits for ublas matrix. More...
 
class  vertex_to_edge_iterator
 transforms collection to collection of pairs consecutive elements of the input collection. The last element and the first element are considered consecutive. More...
 
class  capacitated_voronoi
 This class is assigning vertices demands to capacitated generators in such a way that the total cost is minimized. The solution is based on the min cost max flow algorithm. More...
 
class  voronoi
 simple implementation of the Voronoi concept. More...
 
struct  voronoi_traits< voronoi< Metric > >
 specialization of voronoi_traits More...
 
struct  _voronoi_traits
 voronoi traits base More...
 
struct  voronoi_traits
 default VertexType is int. More...
 
class  polymorfic_fold
 class for polymorphic join on boost fusion sequence More...
 
class  Satisfy
 Find for StaticLazyJoin. More...
 

Functions

template<typename T , typename Idx = int>
void rank (std::vector< T > const &m_id_to_t, std::vector< Idx > &m_t_to_id, int INVALID_IDX=0)
 computes rank i.e. index of element in range More...
 
template<typename... Ranges>
combine_iterator_engine
< detail::rem_ref< Ranges >...> 
make_combine_iterator_engine (Ranges &&...ranges)
 make for combine_iterator_engine More...
 
template<typename Joiner , typename... Ranges>
combine_iterator< Joiner,
detail::rem_ref< Ranges >...> 
make_combine_iterator (Joiner joiner, Ranges &&...ranges)
 make for combine_iterator More...
 
template<typename Name , typename NewType , typename Names , typename Types >
replaced_type< Name, NewType,
detail::components< Names,
Types > >::type 
replace (NewType comp, detail::components< Names, Types > components)
 This function, for a specific Name, replaces compoonent in the components class. The comonent should have deifferent type than prevoius component for this Name (If the type is the same, set member function from components class chould be used). The function returns components class fo type replaced_type<Name, NewType, Oldcomponents >::type. The function creates temporary object wich behaves like result components and creates final object calling special Copy constructor. More...
 
template<class A , class B , class C , class D >
bool operator< (const fraction< A, B > &f1, const fraction< C, D > &f2)
 operator< More...
 
template<class A , class B , class C , class D >
bool operator> (const fraction< A, B > &f1, const fraction< C, D > &f2)
 operator> More...
 
template<class A , class B , class C , class D >
bool operator<= (const fraction< A, B > &f1, const fraction< C, D > &f2)
 operator<= More...
 
template<class A , class B , class C , class D >
bool operator>= (const fraction< A, B > &f1, const fraction< C, D > &f2)
 operator>= More...
 
template<class A , class B , class C , class D , class EPS = A>
bool are_fractions_equal (const fraction< A, B > &f1, const fraction< C, D > &f2, EPS eps=A{})
 operator== More...
 
template<class A , class B >
fraction< A, B > make_fraction (A a, B b)
 make function for fraction More...
 
template<class A , class B , class C >
auto operator* (C c, const fraction< A, B > &f)
 operator* More...
 
template<typename Functor >
auto for_each_line (Functor f, std::string const &file_path, unsigned threads_count=std::thread::hardware_concurrency())
 for_every_line function provides basic functionality for processing text files quickly and clearly. Thanks to mmap() functionality it doesn't have to seek through file but it loads it to virtual memory instantly and uses only ram cache to do that. Furthermore file is split instantly - thanks to that it can be processed effectively using threads. Downside of using mmap is that this functionality will not work effectively if threads have small jobs to be done comparing reading the line charge. It's supposed to work with O(threads_count) memory usage but remember - RES (resident size) stands for how much memory of this process is loaded in physical memory, so file pages loaded in ram cache are added to that value. More...
 
template<typename Strategy = read_indexes_tag, typename Metric , typename Bimap >
metric_on_idx< Metric, Bimap,
Strategy > 
make_metric_on_idx (Metric &&m, Bimap &&b)
 make for metric_on_idx More...
 
template<typename Metric , typename Vertices >
adjacency_matrix< Metric >::type metric_to_bgl (const Metric &m, Vertices &&vertices)
 we assume that vertices is sequence of values (0, vertices.size()). More...
 
template<typename Metric , typename Vertices >
adjacency_matrix< Metric >::type metric_to_bgl_with_index (const Metric &m, Vertices &&vertices, bimap< typename boost::range_value< Vertices >::type > &idx)
 produces graph from metric with index More...
 
template<int k, typename Iterator >
subsets_iterator_engine< k,
Iterator > 
make_subsets_iterator_engine (Iterator b, Iterator e)
 make for subsets_iterator_engine More...
 
template<int k, typename Iterator , typename Joiner = make_tuple>
boost::iterator_range
< subsets_iterator< k,
Iterator, Joiner > > 
make_subsets_iterator_range (Iterator b, Iterator e, Joiner joiner=Joiner{})
 make for subsets_iterator More...
 
template<int k, typename Range , typename Joiner = make_tuple>
auto make_subsets_iterator_range (const Range &range, Joiner joiner=Joiner{})
 
template<typename vertex_iterator >
vertex_to_edge_iterator
< vertex_iterator > 
make_vertex_to_edge_iterator (vertex_iterator b, vertex_iterator e)
 make for vertex_to_edge_iterator More...
 
template<typename vertex_iterator >
vertex_to_edge_iterator
< vertex_iterator > 
make_vertex_to_edge_iterator (std::pair< vertex_iterator, vertex_iterator > r)
 make for vertex_to_edge_iterator form Vertex iterator pair More...
 
template<typename Metric >
voronoi< Metric > make_voronoi (const detail::generators_set_t< Metric > &generators, detail::generators_set_t< Metric > vertices, const Metric &metric, detail::dist_t< Metric > costOfNoGenerator=std::numeric_limits< detail::dist_t< Metric >>::max())
 make for voronoi
 

Detailed Description

Data Structure namespace.

Function Documentation

template<class A , class B , class C , class D , class EPS = A>
bool paal::data_structures::are_fractions_equal ( const fraction< A, B > &  f1,
const fraction< C, D > &  f2,
EPS  eps = A{} 
)

operator==

Template Parameters
A
B
C
D
EPS
Parameters
f1
f2
eps
Returns

Definition at line 131 of file fraction.hpp.

template<typename Functor >
auto paal::data_structures::for_each_line ( Functor  f,
std::string const &  file_path,
unsigned  threads_count = std::thread::hardware_concurrency() 
)

for_every_line function provides basic functionality for processing text files quickly and clearly. Thanks to mmap() functionality it doesn't have to seek through file but it loads it to virtual memory instantly and uses only ram cache to do that. Furthermore file is split instantly - thanks to that it can be processed effectively using threads. Downside of using mmap is that this functionality will not work effectively if threads have small jobs to be done comparing reading the line charge. It's supposed to work with O(threads_count) memory usage but remember - RES (resident size) stands for how much memory of this process is loaded in physical memory, so file pages loaded in ram cache are added to that value.

Template Parameters
Functor= std::string -> Result
Parameters
f- Functor that should be evaluated for every line in file
file_path- path to the file for which values should be computed
threads_count- default std::thread::hardware_concurrency()

Definition at line 148 of file mapped_file.hpp.

template<typename Joiner , typename... Ranges>
combine_iterator<Joiner, detail::rem_ref<Ranges>...> paal::data_structures::make_combine_iterator ( Joiner  joiner,
Ranges &&...  ranges 
)

make for combine_iterator

Template Parameters
Joiner
Ranges
Parameters
joiner
ranges
Returns

Definition at line 288 of file combine_iterator.hpp.

template<typename... Ranges>
combine_iterator_engine<detail::rem_ref<Ranges>...> paal::data_structures::make_combine_iterator_engine ( Ranges &&...  ranges)

make for combine_iterator_engine

Template Parameters
Ranges
Parameters
ranges
Returns

Definition at line 172 of file combine_iterator.hpp.

template<class A , class B >
fraction<A, B> paal::data_structures::make_fraction ( a,
b 
)

make function for fraction

Template Parameters
A
B
Parameters
a
b
Returns

Definition at line 149 of file fraction.hpp.

template<typename Strategy = read_indexes_tag, typename Metric , typename Bimap >
metric_on_idx<Metric, Bimap, Strategy> paal::data_structures::make_metric_on_idx ( Metric &&  m,
Bimap &&  b 
)

make for metric_on_idx

Template Parameters
Metric
Bimap
Parameters
m
b
Returns

Definition at line 102 of file metric_on_idx.hpp.

template<int k, typename Iterator >
subsets_iterator_engine<k, Iterator> paal::data_structures::make_subsets_iterator_engine ( Iterator  b,
Iterator  e 
)

make for subsets_iterator_engine

Template Parameters
k
Iterator
Parameters
b
e
Returns

Definition at line 234 of file subset_iterator.hpp.

template<int k, typename Iterator , typename Joiner = make_tuple>
boost::iterator_range<subsets_iterator<k, Iterator, Joiner> > paal::data_structures::make_subsets_iterator_range ( Iterator  b,
Iterator  e,
Joiner  joiner = Joiner{} 
)

make for subsets_iterator

Template Parameters
Iterator
k
Joiner
Parameters
b
e
joiner
Returns

Definition at line 328 of file subset_iterator.hpp.

template<int k, typename Range , typename Joiner = make_tuple>
auto paal::data_structures::make_subsets_iterator_range ( const Range &  range,
Joiner  joiner = Joiner{} 
)
Template Parameters
k
Range
Joiner
Parameters
range
joiner
Returns

Definition at line 345 of file subset_iterator.hpp.

template<typename vertex_iterator >
vertex_to_edge_iterator<vertex_iterator> paal::data_structures::make_vertex_to_edge_iterator ( vertex_iterator  b,
vertex_iterator  e 
)

make for vertex_to_edge_iterator

Template Parameters
vertex_iterator
Parameters
b
e
Returns

Definition at line 149 of file vertex_to_edge_iterator.hpp.

template<typename vertex_iterator >
vertex_to_edge_iterator<vertex_iterator> paal::data_structures::make_vertex_to_edge_iterator ( std::pair< vertex_iterator, vertex_iterator >  r)

make for vertex_to_edge_iterator form Vertex iterator pair

Template Parameters
vertex_iterator
Parameters
r
Returns

Definition at line 163 of file vertex_to_edge_iterator.hpp.

template<typename Metric , typename Vertices >
adjacency_matrix<Metric>::type paal::data_structures::metric_to_bgl ( const Metric &  m,
Vertices &&  vertices 
)

we assume that vertices is sequence of values (0, vertices.size()).

Parameters
m
vertices

Definition at line 52 of file metric_to_bgl.hpp.

template<typename Metric , typename Vertices >
adjacency_matrix<Metric>::type paal::data_structures::metric_to_bgl_with_index ( const Metric &  m,
Vertices &&  vertices,
bimap< typename boost::range_value< Vertices >::type > &  idx 
)

produces graph from metric with index

Template Parameters
Metric
Vertices
Parameters
m
vertices
idx
Returns

Definition at line 84 of file metric_to_bgl.hpp.

template<class A , class B , class C >
auto paal::data_structures::operator* ( c,
const fraction< A, B > &  f 
)

operator*

Template Parameters
A
B
C
Parameters
c
f
Returns

Definition at line 166 of file fraction.hpp.

template<class A , class B , class C , class D >
bool paal::data_structures::operator< ( const fraction< A, B > &  f1,
const fraction< C, D > &  f2 
)

operator<

Template Parameters
A
B
C
D
Parameters
f1
f2
Returns

Definition at line 57 of file fraction.hpp.

template<class A , class B , class C , class D >
bool paal::data_structures::operator<= ( const fraction< A, B > &  f1,
const fraction< C, D > &  f2 
)

operator<=

Template Parameters
A
B
C
D
Parameters
f1
f2
Returns

Definition at line 93 of file fraction.hpp.

template<class A , class B , class C , class D >
bool paal::data_structures::operator> ( const fraction< A, B > &  f1,
const fraction< C, D > &  f2 
)

operator>

Template Parameters
A
B
C
D
Parameters
f1
f2
Returns

Definition at line 75 of file fraction.hpp.

template<class A , class B , class C , class D >
bool paal::data_structures::operator>= ( const fraction< A, B > &  f1,
const fraction< C, D > &  f2 
)

operator>=

Template Parameters
A
B
C
D
Parameters
f1
f2
Returns

Definition at line 111 of file fraction.hpp.

template<typename T , typename Idx = int>
void paal::data_structures::rank ( std::vector< T > const &  m_id_to_t,
std::vector< Idx > &  m_t_to_id,
int  INVALID_IDX = 0 
)

computes rank i.e. index of element in range

Template Parameters
T
Idx
Parameters
m_id_to_t
m_t_to_id
INVALID_IDX

Definition at line 364 of file bimap.hpp.

template<typename Name , typename NewType , typename Names , typename Types >
replaced_type<Name, NewType, detail::components<Names, Types> >::type paal::data_structures::replace ( NewType  comp,
detail::components< Names, Types >  components 
)

This function, for a specific Name, replaces compoonent in the components class. The comonent should have deifferent type than prevoius component for this Name (If the type is the same, set member function from components class chould be used). The function returns components class fo type replaced_type<Name, NewType, Oldcomponents >::type. The function creates temporary object wich behaves like result components and creates final object calling special Copy constructor.

Template Parameters
Name
NewType
Names
Types
Parameters
comp
components
Returns

Definition at line 139 of file components_replace.hpp.