This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch tuple_sketch
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-cpp.git
The following commit(s) were added to refs/heads/tuple_sketch by this push:
new 9fe078d move-friendly set difference
9fe078d is described below
commit 9fe078d9301f6cb6c17aa014b5460dc211896f18
Author: AlexanderSaydakov <[email protected]>
AuthorDate: Mon Jul 13 18:31:38 2020 -0700
move-friendly set difference
---
common/include/conditional_back_inserter.hpp | 7 +++++-
common/include/conditional_forward.hpp | 30 ++++++++++++++++++++++++
tuple/include/theta_comparators.hpp | 6 ++---
tuple/include/theta_set_difference_base.hpp | 6 +++--
tuple/include/theta_set_difference_base_impl.hpp | 16 ++++++++-----
tuple/include/tuple_a_not_b.hpp | 3 ++-
tuple/include/tuple_a_not_b_impl.hpp | 5 ++--
7 files changed, 58 insertions(+), 15 deletions(-)
diff --git a/common/include/conditional_back_inserter.hpp
b/common/include/conditional_back_inserter.hpp
index 9b33833..8a2b38b 100644
--- a/common/include/conditional_back_inserter.hpp
+++ b/common/include/conditional_back_inserter.hpp
@@ -40,11 +40,16 @@ public:
return *this;
}
- conditional_back_insert_iterator& operator=(typename
Container::const_reference value) {
+ conditional_back_insert_iterator& operator=(const typename
Container::value_type& value) {
if (p(value)) std::back_insert_iterator<Container>::operator=(value);
return *this;
}
+ conditional_back_insert_iterator& operator=(typename Container::value_type&&
value) {
+ if (p(value))
std::back_insert_iterator<Container>::operator=(std::move(value));
+ return *this;
+ }
+
conditional_back_insert_iterator& operator*() { return *this; }
conditional_back_insert_iterator& operator++() { return *this; }
conditional_back_insert_iterator& operator++(int) { return *this; }
diff --git a/common/include/conditional_forward.hpp
b/common/include/conditional_forward.hpp
index e0745ee..4648b85 100644
--- a/common/include/conditional_forward.hpp
+++ b/common/include/conditional_forward.hpp
@@ -35,6 +35,36 @@ fwd_type<T1, T2> conditional_forward(T2&& value) {
return std::forward<fwd_type<T1, T2>>(std::forward<T2>(value));
}
+// Forward container as iterators
+
+template<typename Container>
+auto forward_begin(Container&& c) ->
+typename std::enable_if<std::is_lvalue_reference<Container>::value,
decltype(c.begin())>::type
+{
+ return c.begin();
+}
+
+template<typename Container>
+auto forward_begin(Container&& c) ->
+typename std::enable_if<!std::is_lvalue_reference<Container>::value,
decltype(std::make_move_iterator(c.begin()))>::type
+{
+ return std::make_move_iterator(c.begin());
+}
+
+template<typename Container>
+auto forward_end(Container&& c) ->
+typename std::enable_if<std::is_lvalue_reference<Container>::value,
decltype(c.end())>::type
+{
+ return c.end();
+}
+
+template<typename Container>
+auto forward_end(Container&& c) ->
+typename std::enable_if<!std::is_lvalue_reference<Container>::value,
decltype(std::make_move_iterator(c.end()))>::type
+{
+ return std::make_move_iterator(c.end());
+}
+
} /* namespace datasketches */
#endif
diff --git a/tuple/include/theta_comparators.hpp
b/tuple/include/theta_comparators.hpp
index a7520c1..e8a39b7 100644
--- a/tuple/include/theta_comparators.hpp
+++ b/tuple/include/theta_comparators.hpp
@@ -24,9 +24,9 @@ namespace datasketches {
template<typename ExtractKey>
struct compare_by_key {
- template<typename Entry>
- bool operator()(Entry&& a, Entry&& b) const {
- return ExtractKey()(std::forward<Entry>(a)) <
ExtractKey()(std::forward<Entry>(b));
+ template<typename Entry1, typename Entry2>
+ bool operator()(Entry1&& a, Entry2&& b) const {
+ return ExtractKey()(std::forward<Entry1>(a)) <
ExtractKey()(std::forward<Entry2>(b));
}
};
diff --git a/tuple/include/theta_set_difference_base.hpp
b/tuple/include/theta_set_difference_base.hpp
index 253fbba..0c84129 100644
--- a/tuple/include/theta_set_difference_base.hpp
+++ b/tuple/include/theta_set_difference_base.hpp
@@ -35,11 +35,13 @@ template<
class theta_set_difference_base {
public:
using comparator = compare_by_key<ExtractKey>;
- using hash_table = theta_update_sketch_base<Entry, ExtractKey, Allocator>;
+ using AllocU64 = typename std::allocator_traits<Allocator>::template
rebind_alloc<uint64_t>;
+ using hash_table = theta_update_sketch_base<uint64_t, trivial_extract_key,
AllocU64>;
theta_set_difference_base(uint64_t seed);
- CompactSketch compute(const Sketch& a, const Sketch& b, bool ordered) const;
+ template<typename SS>
+ CompactSketch compute(SS&& a, const Sketch& b, bool ordered) const;
private:
uint16_t seed_hash_;
diff --git a/tuple/include/theta_set_difference_base_impl.hpp
b/tuple/include/theta_set_difference_base_impl.hpp
index 7273c9f..98c7ade 100644
--- a/tuple/include/theta_set_difference_base_impl.hpp
+++ b/tuple/include/theta_set_difference_base_impl.hpp
@@ -20,6 +20,7 @@
#include <algorithm>
#include "conditional_back_inserter.hpp"
+#include "conditional_forward.hpp"
namespace datasketches {
@@ -29,7 +30,8 @@ seed_hash_(compute_seed_hash(seed))
{}
template<typename EN, typename EK, typename S, typename CS, typename A>
-CS theta_set_difference_base<EN, EK, S, CS, A>::compute(const S& a, const S&
b, bool ordered) const {
+template<typename SS>
+CS theta_set_difference_base<EN, EK, S, CS, A>::compute(SS&& a, const S& b,
bool ordered) const {
if (a.is_empty() || a.get_num_retained() == 0 || b.is_empty()) return CS(a,
ordered);
if (a.get_seed_hash() != seed_hash_) throw std::invalid_argument("A seed
hash mismatch");
if (b.get_seed_hash() != seed_hash_) throw std::invalid_argument("B seed
hash mismatch");
@@ -39,28 +41,30 @@ CS theta_set_difference_base<EN, EK, S, CS,
A>::compute(const S& a, const S& b,
bool is_empty = a.is_empty();
if (b.get_num_retained() == 0) {
- std::copy_if(a.begin(), a.end(), std::back_inserter(entries),
key_less_than<uint64_t, EN, EK>(theta));
+ std::copy_if(forward_begin(std::forward<SS>(a)),
forward_end(std::forward<SS>(a)), std::back_inserter(entries),
+ key_less_than<uint64_t, EN, EK>(theta));
} else {
if (a.is_ordered() && b.is_ordered()) { // sort-based
- std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
conditional_back_inserter(entries, key_less_than<uint64_t, EN, EK>(theta)));
+ std::set_difference(forward_begin(std::forward<SS>(a)),
forward_end(std::forward<SS>(a)), b.begin(), b.end(),
+ conditional_back_inserter(entries, key_less_than<uint64_t, EN,
EK>(theta)), comparator());
} else { // hash-based
const uint8_t lg_size = lg_size_from_count(b.get_num_retained(),
hash_table::REBUILD_THRESHOLD);
hash_table table(lg_size, lg_size, hash_table::resize_factor::X1, 1, 0);
// seed is not used here
for (const auto& entry: b) {
const uint64_t hash = EK()(entry);
if (hash < theta) {
- table.insert(table.find(hash).first, entry);
+ table.insert(table.find(hash).first, hash);
} else if (b.is_ordered()) {
break; // early stop
}
}
// scan A lookup B
- for (const auto& entry: a) {
+ for (auto& entry: a) {
const uint64_t hash = EK()(entry);
if (hash < theta) {
auto result = table.find(hash);
- if (!result.second) entries.push_back(entry);
+ if (!result.second)
entries.push_back(conditional_forward<SS>(entry));
} else if (a.is_ordered()) {
break; // early stop
}
diff --git a/tuple/include/tuple_a_not_b.hpp b/tuple/include/tuple_a_not_b.hpp
index 5883d73..923e2e1 100644
--- a/tuple/include/tuple_a_not_b.hpp
+++ b/tuple/include/tuple_a_not_b.hpp
@@ -44,7 +44,8 @@ public:
* Computes the a-not-b set operation given two sketches.
* @return the result of a-not-b
*/
- CompactSketch compute(const Sketch& a, const Sketch& b, bool ordered = true)
const;
+ template<typename FwdSketch>
+ CompactSketch compute(FwdSketch&& a, const Sketch& b, bool ordered = true)
const;
private:
State state_;
diff --git a/tuple/include/tuple_a_not_b_impl.hpp
b/tuple/include/tuple_a_not_b_impl.hpp
index ccc081d..4ba2e41 100644
--- a/tuple/include/tuple_a_not_b_impl.hpp
+++ b/tuple/include/tuple_a_not_b_impl.hpp
@@ -25,8 +25,9 @@ state_(seed)
{}
template<typename S, typename A>
-auto tuple_a_not_b<S, A>::compute(const Sketch& a, const Sketch& b, bool
ordered) const -> CompactSketch {
- return state_.compute(a, b, ordered);
+template<typename SS>
+auto tuple_a_not_b<S, A>::compute(SS&& a, const Sketch& b, bool ordered) const
-> CompactSketch {
+ return state_.compute(std::forward<SS>(a), b, ordered);
}
} /* namespace datasketches */
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
