Line data Source code
1 : /*
2 : * Copyright (c) 2013-2015: G-CSC, Goethe University Frankfurt
3 : * Author: Martin Rupp
4 : *
5 : * This file is part of UG4.
6 : *
7 : * UG4 is free software: you can redistribute it and/or modify it under the
8 : * terms of the GNU Lesser General Public License version 3 (as published by the
9 : * Free Software Foundation) with the following additional attribution
10 : * requirements (according to LGPL/GPL v3 §7):
11 : *
12 : * (1) The following notice must be displayed in the Appropriate Legal Notices
13 : * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
14 : *
15 : * (2) The following notice must be displayed at a prominent place in the
16 : * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
17 : *
18 : * (3) The following bibliography is recommended for citation and must be
19 : * preserved in all covered files:
20 : * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
21 : * parallel geometric multigrid solver on hierarchically distributed grids.
22 : * Computing and visualization in science 16, 4 (2013), 151-164"
23 : * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
24 : * flexible software system for simulating pde based models on high performance
25 : * computers. Computing and visualization in science 16, 4 (2013), 165-179"
26 : *
27 : * This program is distributed in the hope that it will be useful,
28 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 : * GNU Lesser General Public License for more details.
31 : */
32 :
33 : #ifndef UNSORTED_VECTOR_H_
34 : #define UNSORTED_VECTOR_H_
35 :
36 : #include <vector>
37 : #include "connection.h"
38 :
39 : namespace ug{
40 :
41 : /**
42 : * This is in most cases faster than the std::map-based SparseVector in sparse_vector.h
43 : * because it uses and "posInConnection" array which reduces all operations to O(1),
44 : * instead of O(log n) for std::map when number of non-zeroes in the vector.
45 : * The additional array is as long as the (non-sparse) size of the vector, so this makes only sense if you
46 : * REUSE the UnsortedSparseVector, like
47 : * \code
48 : * N = 10000; // N is the non-sparse total size of the vector
49 : * UnsortedSparseVector<int> vec(N); // expensive.
50 : * for(size_t i=0; i < N; i++)
51 : * {
52 : * vec.clear();
53 : * for(size_t j=0; j<50; j++)
54 : * vec(rand()%N)++; // O(1)
55 : * }
56 : * \endcode
57 : */
58 : template<typename TValue>
59 0 : class UnsortedSparseVector
60 : {
61 : public:
62 : typedef TValue value_type;
63 : typedef AlgebraicConnection<TValue> connection;
64 :
65 : typedef typename std::vector<connection>::iterator iterator;
66 : typedef typename std::vector<connection>::const_iterator const_iterator;
67 :
68 : private:
69 : std::vector<int> posInConnections;
70 : std::vector<connection > con;
71 : size_t m_size;
72 : public:
73 :
74 0 : UnsortedSparseVector(size_t s) : posInConnections(s, -1), m_size(s)
75 : {
76 0 : con.reserve(32);
77 0 : }
78 : iterator begin()
79 : {
80 : return con.begin();
81 : }
82 : iterator end()
83 : {
84 : return con.end();
85 : }
86 : const_iterator begin() const
87 : {
88 : return con.begin();
89 : }
90 : const_iterator end() const
91 : {
92 : return con.end();
93 : }
94 :
95 : size_t num_connections() const
96 : {
97 : return con.size();
98 : }
99 :
100 : size_t size() const
101 : {
102 : return m_size;
103 : }
104 :
105 : connection *unsorted_raw_ptr()
106 : {
107 : return &con[0];
108 : }
109 :
110 :
111 0 : void clear()
112 : {
113 0 : for(size_t i=0; i<con.size(); i++)
114 0 : posInConnections[con[i].iIndex] = -1;
115 : con.clear();
116 0 : }
117 :
118 : const value_type &operator()(size_t c) const
119 : {
120 : assert(c < m_size);
121 : int p = posInConnections[c];
122 : if(p != -1)
123 : return con[p].value();
124 : else
125 : assert(0 && "const_and_not_available");
126 : }
127 0 : value_type &operator()(size_t c)
128 : {
129 : assert(c < m_size);
130 0 : int p = posInConnections[c];
131 0 : if(p != -1)
132 0 : return con[p].value();
133 : else
134 : {
135 0 : p = posInConnections[c] = con.size();
136 0 : con.push_back(connection(c, TValue(0)));
137 0 : return con[p].value();
138 : }
139 : }
140 : bool has_connection(size_t c) const
141 : {
142 : assert(c < m_size);
143 : return posInConnections[c] != -1;
144 : }
145 : };
146 :
147 :
148 : }
149 : #endif /* UNSORTED_VECTOR_H_ */
|
