ztsdb
vector_set.hpp
1 // (C) 2016 Leonardo Silvestri
2 //
3 // This file is part of ztsdb.
4 //
5 // ztsdb is free software: you can redistribute it and/or modify
6 // it under the terms of the GNU General Public License as published by
7 // the Free Software Foundation, either version 3 of the License, or
8 // (at your option) any later version.
9 //
10 // ztsdb is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU General Public License for more details.
14 //
15 // You should have received a copy of the GNU General Public License
16 // along with ztsdb. If not, see <http://www.gnu.org/licenses/>.
17 
18 
19 #ifndef VECTOR_SET_HPP
20 #define VECTOR_SET_HPP
21 
22 
23 #include <algorithm>
24 #include <utility>
25 #include "vector.hpp"
26 
27 
29 namespace arr {
30 
31  template <typename T, typename U>
32  Vector<T> intersect(const Vector<T>& v1, const Vector<U>& v2);
33 
34  template <typename T, typename U, typename I>
35  std::pair<Vector<I>, Vector<I>> intersect_idx(const Vector<T>& v1, const Vector<U>& v2);
36 
37  template <typename T, typename U>
38  Vector<T> _union(const Vector<T>& v1, const Vector<U>& v2);
39 
40  template <typename T, typename U, typename I>
41  std::pair<Vector<I>, Vector<I>> union_idx(const Vector<T>& v1, const Vector<U>& v2);
42 
43 
44  template <typename T, typename U>
45  Vector<T> setdiff(const Vector<T>& v1, const Vector<U>& v2);
46 
47 
48  template <typename T, typename U, typename I>
49  std::pair<Vector<I>, Vector<I>> setdiff_idx(const Vector<T>& v1, const Vector<U>& v2);
50 
51 }
52 
53 
54 // ----------------------------------------------------------------------------
55 // Implementation.
56 
57 namespace arr {
58 
59  template <typename T, typename U, template <typename, typename> class F>
60  static Vector<T> conditional_sort_helper(const Vector<T>& v1, const Vector<U>& v2)
61  {
62  if (!v1.isOrdered() && !v2.isOrdered()) {
63  auto s1 = v1;
64  std::sort(s1.begin(), s1.end()); // OOO LLL use a vector sort
65  auto s2 = v2;
66  std::sort(s2.begin(), s2.end());
67  return F<T,U>::f(s1, s2);
68  }
69  if (!v1.isOrdered()) {
70  auto s1 = v1;
71  std::sort(s1.begin(), s1.end());
72  return F<T,U>::f(s1, v2);
73  }
74  if (!v2.isOrdered()) {
75  auto s2 = v2;
76  std::sort(s2.begin(), s2.end());
77  return F<T,U>::f(v1, s2);
78  }
79  return F<T,U>::f(v1, v2);
80  }
81 
82 
83  template <typename T, typename U, typename I, template <typename, typename, typename> class F>
84  static std::pair<Vector<I>, Vector<I>>
85  conditional_sort_idx_helper(const Vector<T>& v1, const Vector<U>& v2)
86  {
87  // we need the indices to be correct, so if we sorted we need to translate the result
88  if (!v1.isOrdered() && !v2.isOrdered()) {
89  auto s1 = v1;
90  std::sort(s1.begin(), s1.end());
91  auto s2 = v2;
92  std::sort(s2.begin(), s2.end());
93  return F<T,U,I>::f(s1, s2);
94  }
95  if (!v1.isOrdered()) {
96  auto s1 = v1;
97  std::sort(s1.begin(), s1.end());
98  return F<T,U,I>::f(s1, v2);
99  }
100  if (!v2.isOrdered()) {
101  auto s2 = v2;
102  std::sort(s2.begin(), s2.end());
103  return F<T,U,I>::f(v1, s2);
104  }
105  return F<T,U,I>::f(v1, v2);
106  }
107 
108 
109  template <typename T,
110  typename U,
111  typename I,
112  typename NANF,
113  template <typename, typename, typename, typename> class F>
114  static std::pair<Vector<I>, Vector<I>>
115  conditional_sort_idx_nan_helper(const Vector<T>& v1, const Vector<U>& v2)
116  {
117  // we need the indices to be correct, so if we sorted we need to translate the result
118  if (!v1.isOrdered() && !v2.isOrdered()) {
119  auto s1 = v1;
120  std::sort(s1.begin(), s1.end());
121  auto s2 = v2;
122  std::sort(s2.begin(), s2.end());
123  return F<T,U,I,NANF>::f(s1, s2);
124  }
125  if (!v1.isOrdered()) {
126  auto s1 = v1;
127  std::sort(s1.begin(), s1.end());
128  return F<T,U,I,NANF>::f(s1, v2);
129  }
130  if (!v2.isOrdered()) {
131  auto s2 = v2;
132  std::sort(s2.begin(), s2.end());
133  return F<T,U,I,NANF>::f(v1, s2);
134  }
135  return F<T,U,I,NANF>::f(v1, v2);
136  }
137 
138 
139 
140  // --------------------------------------
141  // intersects ---------------------------
142 
143  template <typename T, typename U>
144  struct intersect_helper {
145  static Vector<T> f(const Vector<T>& v1, const Vector<U>& v2)
146  {
147  Vector<T> res;
148  size_t i1 = 0, i2 = 0;
149  while (i1 < v1.size() && i2 < v2.size()) {
150  if (v1[i1] < v2[i2]) {
151  ++i1;
152  } else if (v1[i1] > v2[i2]) {
153  ++i2;
154  } else {
155  if (res.size()==0 || v1[i1] != res.back()) {
156  res.push_back(v1[i1]);
157  }
158  ++i1;
159  //++i2; this is correct for T==U, but not for example when
160  //T==time and U==interval
161  }
162  }
163  return res;
164  }
165  };
166 
167 
168  template <typename T, typename U>
169  Vector<T> intersect(const Vector<T>& v1, const Vector<U>& v2)
170  {
171  return conditional_sort_helper<T, U, intersect_helper>(v1, v2);
172  }
173 
174 
175  template <typename T, typename U, typename I>
176  struct intersect_idx_helper {
177  static std::pair<Vector<I>, Vector<I>> f(const Vector<T>& v1, const Vector<U>& v2)
178  {
179  std::pair<Vector<I>, Vector<I>> res;
180  size_t i1 = 0, i2 = 0;
181  while (i1 < v1.size() && i2 < v2.size()) {
182  if (v1[i1] < v2[i2]) {
183  ++i1;
184  } else if (v1[i1] > v2[i2]) {
185  ++i2;
186  } else {
187  if (v1.size()==0 || v1[i1] != v1[i1-1]) {
188  res.first.push_back(i1+1);
189  res.second.push_back(i2+1);
190  }
191  ++i1;
192  //++i2; this is correct for T==U, but not for example when
193  //T==time and U==interval
194  }
195  }
196  return res;
197  }
198  };
199 
200  template <typename T, typename U, typename I>
201  std::pair<Vector<I>, Vector<I>> intersect_idx(const Vector<T>& v1, const Vector<U>& v2)
202  {
203  return conditional_sort_idx_helper<T, U, I, intersect_idx_helper>(v1, v2);
204  }
205 
206 
207  // --------------------------------------
208  // unions -------------------------------
209 
210  template <typename T, typename U>
211  struct union_helper {
212  static Vector<T> f(const Vector<T>& v1, const Vector<U>& v2)
213  {
214  Vector<T> res;
215  size_t i1 = 0, i2 = 0;
216  while (i1 < v1.size() && i2 < v2.size()) {
217  if (v1[i1] < v2[i2]) {
218  if (res.size()==0 || v1[i1] != res.back()) {
219  res.push_back(v1[i1]);
220  }
221  ++i1;
222  } else if (v1[i1] > v2[i2]) {
223  if (res.size()==0 || v2[i2] != res.back()) {
224  res.push_back(v2[i2]);
225  }
226  ++i2;
227  } else {
228  if (res.size()==0 || v1[i1] != res.back()) {
229  res.push_back(v1[i1]);
230  }
231  ++i1;
232  ++i2;
233  }
234  }
235 
236  while (i1 < v1.size()) {
237  if (i1==0 || v1[i1] != v1[i1-1]) {
238  res.push_back(v1[i1]);
239  }
240  ++i1;
241  }
242  while (i2 < v2.size()) {
243  if (i2==0 || v2[i2] != v2[i2-1]) {
244  res.push_back(v2[i2]);
245  }
246  ++i2;
247  }
248 
249  return res;
250  }
251  };
252 
253  template <typename T, typename U>
254  Vector<T> _union(const Vector<T>& v1, const Vector<U>& v2)
255  {
256  return conditional_sort_helper<T, U, union_helper>(v1, v2);
257  }
258 
259 
260  template <typename T, typename U, typename I, typename NANF>
261  struct union_idx_helper {
262  static std::pair<Vector<I>, Vector<I>> f(const Vector<T>& v1, const Vector<U>& v2)
263  {
264  std::pair<Vector<I>, Vector<I>> res;
265  size_t i1 = 0, i2 = 0;
266  while (i1 < v1.size() && i2 < v2.size()) {
267  if (v1[i1] < v2[i2]) {
268  if (i1==0 || v1[i1] != v1[i1-1]) {
269  res.first.push_back(i1+1);
270  res.second.push_back(NANF::f());
271  }
272  ++i1;
273  } else if (v1[i1] > v2[i2]) {
274  if (i2==0 || v2[i2] != v1[i2-1]) {
275  res.first.push_back(NANF::f());
276  res.second.push_back(i2+1);
277  }
278  ++i2;
279  } else {
280  if (i1==0 || v1[i1] != v1[i1-1]) {
281  res.first.push_back(i1+1);
282  res.second.push_back(i2+1);
283  }
284  ++i1;
285  ++i2;
286  }
287  }
288 
289  while (i1 < v1.size()) {
290  if (i1==0 || v1[i1] != v1[i1-1]) {
291  res.first.push_back(i1+1);
292  res.second.push_back(NANF::f());
293  }
294  ++i1;
295  }
296  while (i2 < v2.size()) {
297  if (i2==0 || v2[i2] != v2[i2-1]) {
298  res.first.push_back(NANF::f());
299  res.second.push_back(i2+1);
300  }
301  ++i2;
302  }
303 
304  return res;
305  }
306  };
307 
308  template <typename T, typename U, typename I, template <typename> class NANF>
309  std::pair<Vector<I>, Vector<I>> union_idx(const Vector<T>& v1,
310  const Vector<U>& v2)
311  {
312  return conditional_sort_idx_nan_helper<T, U, I, NANF<I>, union_idx_helper>(v1, v2);
313  }
314 
315 
316  // --------------------------------------
317  // setdiffs -------------------------------
318 
319  template <typename T, typename U>
320  struct setdiff_helper {
321  static Vector<T> f(const Vector<T>& v1,
322  const Vector<U>& v2)
323  {
324  Vector<T> res;
325  size_t i1 = 0, i2 = 0;
326  while (i1 < v1.size() && i2 < v2.size()) {
327  if (v1[i1] < v2[i2]) {
328  res.push_back(v1[i1++]);
329  } else if (v1[i1] > v2[i2]) {
330  ++i2;
331  } else {
332  ++i1;
333  //++i2; this is correct for T==U, but not for example when
334  //T==time and U==interval
335  }
336  }
337 
338  // pick up elts left in v1:
339  while (i1 < v1.size()) {
340  res.push_back(v1[i1++]);
341  }
342 
343  return res;
344  }
345  };
346 
347  template <typename T, typename U>
348  Vector<T> setdiff(const Vector<T>& v1, const Vector<U>& v2)
349  {
350  return conditional_sort_helper<T, U, setdiff_helper>(v1, v2);
351  }
352 
353 
354  template <typename T, typename U, typename I>
355  struct setdiff_idx_helper {
356  static std::pair<Vector<I>, Vector<I>> f(const Vector<T>& v1, const Vector<U>& v2)
357  {
358  std::pair<Vector<I>, Vector<I>> res;
359  size_t i1 = 0, i2 = 0;
360  while (i1 < v1.size() && i2 < v2.size()) {
361  if (v1[i1] < v2[i2]) {
362  res.first.push_back(i1+1);
363  ++i1;
364  } else if (v1[i1] > v2[i2]) {
365  res.second.push_back(i2+1);
366  ++i2;
367  } else {
368  ++i1;
369  ++i2;
370  }
371  }
372 
373  // pick up elts left in v1:
374  while (i1 < v1.size()) {
375  res.first.push_back(i1+1);
376  ++i1;
377  }
378  // pick up elts left in v2:
379  while (i2 < v2.size()) {
380  res.second.push_back(i2+1);
381  ++i2;
382  }
383 
384  return res;
385  }
386  };
387 
388  template <typename T, typename U, typename I>
389  std::pair<Vector<I>, Vector<I>> setdiff_idx(const Vector<T>& v1, const Vector<U>& v2)
390  {
391  return conditional_sort_idx_helper<T, U, I, setdiff_idx_helper>(v1, v2);
392  }
393 
394 
395 }
396 
397 #endif
arr::Vector< T >
arr::union_idx_helper
Definition: vector_set.hpp:261
arr::setdiff_idx_helper
Definition: vector_set.hpp:355
NANF
Definition: base_funcs_set.cpp:205
arr::intersect_idx_helper
Definition: vector_set.hpp:176
arr
Contains the classes and functions that implement a multidimentional array type.
Definition: allocator.hpp:29
arr::union_helper
Definition: vector_set.hpp:211
arr::setdiff_helper
Definition: vector_set.hpp:320
arr::intersect_helper
Definition: vector_set.hpp:144
Generated on Sun Jul 5 2020 18:04:52 for ztsdb by   doxygen 1.8.17