summaryrefslogtreecommitdiff
path: root/common/utility/relation.H
diff options
context:
space:
mode:
Diffstat (limited to 'common/utility/relation.H')
-rw-r--r--common/utility/relation.H260
1 files changed, 260 insertions, 0 deletions
diff --git a/common/utility/relation.H b/common/utility/relation.H
new file mode 100644
index 0000000..1c5f0ad
--- /dev/null
+++ b/common/utility/relation.H
@@ -0,0 +1,260 @@
+// Copyright 2008, 2009 Brady J. Garvin
+
+// This file is part of Covering Arrays by Simulated Annealing (CASA).
+
+// CASA is free software: you can redistribute it and/or modify it
+// under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+
+// CASA is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with CASA. If not, see <http://www.gnu.org/licenses/>.
+
+
+#ifndef RELATION_H
+#define RELATION_H
+
+#include <cassert>
+#include <iostream>
+#include <set>
+#include <map>
+
+// A bidirectional (multi-)map where either the either the key or data type (or
+// both) can be forced to be unique.
+
+// Naming conventions (including abbreviations in identifier names) here
+// resemble those used in the STL, rather than the more Java-like standard in
+// the other code.
+
+template<class key_type, class data_type, bool unique_key, bool unique_data,
+ class key_compare = std::less<key_type>,
+ class data_compare = std::less<data_type> >class relation {
+protected:
+ typedef relation
+ <key_type, data_type, unique_key, unique_data, key_compare, data_compare>
+ relation_type;
+
+ std::multimap<key_type, data_type, key_compare>
+ by_key;
+ std::multimap<data_type, key_type, data_compare>
+ by_data;
+public:
+ typedef unsigned size_type;
+ typedef int difference_type;
+
+ // By-key iterators:
+#define KEY(type) \
+ typedef typename std::multimap<key_type, data_type, key_compare>::type \
+ key_ ## type
+ KEY(iterator);
+ KEY(const_iterator);
+ KEY(reverse_iterator);
+ KEY(const_reverse_iterator);
+#undef KEY
+
+ // By-data iterators:
+#define DATA(type) \
+ typedef typename std::multimap<data_type, key_type, data_compare>::type \
+ data_ ## type
+ DATA(iterator);
+ DATA(const_iterator);
+ DATA(reverse_iterator);
+ DATA(const_reverse_iterator);
+#undef DATA
+
+ // Create, copy, and delete:
+ relation() {}
+ relation(const key_compare&key_comp, const data_compare&data_comp) :
+ by_key(key_comp),
+ by_data(data_comp) {}
+ relation(const relation_type&copy) :
+ by_key(copy.by_key),
+ by_data(copy.by_data) {}
+ relation&operator =(const relation_type&copy) {
+ by_key = copy.by_key;
+ by_data = copy.by_data;
+ }
+ void swap(relation_type&other) {
+ by_key.swap(other.by_key);
+ by_data.swap(other.by_data);
+ }
+ virtual ~relation() {}
+ // Access and mutate:
+ // By key:
+ key_compare key_comp() const {
+ return by_key.key_comp();
+ }
+#define KEY(method, constness) key_ ## method() constness { \
+ return by_key.method(); \
+ }
+ key_iterator KEY(begin,);
+ key_iterator KEY(end,);
+ key_const_iterator KEY(begin, const);
+ key_const_iterator KEY(end, const);
+ key_reverse_iterator KEY(rbegin,);
+ key_reverse_iterator KEY(rend,);
+ key_const_reverse_iterator KEY(rbegin, const);
+ key_const_reverse_iterator KEY(rend, const);
+#undef KEY
+#define KEY(method,constness) key_ ## method(const key_type&key) constness { \
+ return by_key.method(key); \
+ }
+ key_iterator KEY(find,);
+ size_type KEY(count,);
+ key_iterator KEY(lower_bound,);
+ key_const_iterator KEY(lower_bound, const);
+ key_iterator KEY(upper_bound,);
+ key_const_iterator KEY(upper_bound, const);
+ std::pair<key_iterator, key_iterator> KEY(equal_range,);
+ std::pair<key_const_iterator, key_const_iterator> KEY(equal_range, const);
+#undef KEY
+ // (Return whether insertion was successful as second.)
+ std::pair<key_iterator, bool>key_insert
+ (const key_type&key, const data_type&data) {
+ key_iterator key_hint = by_key.find(key);
+ data_iterator data_hint = by_data.find(data);
+ if ((unique_key && key_hint != by_key.end()) ||
+ (unique_data && data_hint != by_data.end())) {
+ return std::pair<key_iterator, bool>(by_key.end(), false);
+ }
+ by_data.insert(data_hint, std::pair<data_type, key_type>(data, key));
+ return std::pair<key_iterator, bool>
+ (by_key.insert
+ (key_hint, std::pair<key_type, data_type>(key, data)), true);
+ }
+ void key_erase(key_iterator pos) {
+ std::pair<data_iterator, data_iterator>data_pos =
+ by_data.equal_range(pos->second);
+ key_type match = pos->first;
+ for (; data_pos.first != data_pos.second; ++data_pos.first) {
+ key_type&candidate = data_pos.first->second;
+ if (!by_key.key_comp()(candidate, match) &&
+ !by_key.key_comp()(match, candidate)) {
+ by_key.erase(pos);
+ by_data.erase(data_pos.first);
+ return;
+ }
+ }
+ assert(false);
+ }
+ size_type key_erase(const key_type&key) {
+ size_type result = 0;
+ std::pair<key_iterator, key_iterator>range = by_key.equal_range(key);
+ while (range.first != range.second) {
+ key_iterator tag = range.first++;
+ erase(tag);
+ ++result;
+ }
+ return result;
+ }
+
+ // By data:
+ data_compare data_comp() const {
+ return by_data.data_comp();
+ }
+#define DATA(method, constness) data_ ## method() constness { \
+ return by_data.method(); \
+ }
+ data_iterator DATA(begin,);
+ data_iterator DATA(end,);
+ data_const_iterator DATA(begin, const);
+ data_const_iterator DATA(end, const);
+ data_reverse_iterator DATA(rbegin,);
+ data_reverse_iterator DATA(rend,);
+ data_const_reverse_iterator DATA(rbegin, const);
+ data_const_reverse_iterator DATA(rend, const);
+#undef DATA
+#define DATA(method, constness) \
+ data_ ## method(const data_type&data) constness { \
+ return by_data.method(data); \
+ }
+ data_iterator DATA(find,);
+ size_type DATA(count,);
+ data_iterator DATA(lower_bound,);
+ data_const_iterator DATA(lower_bound, const);
+ data_iterator DATA(upper_bound,);
+ data_const_iterator DATA(upper_bound, const);
+ std::pair<data_iterator, data_iterator> DATA(equal_range,);
+ std::pair<data_const_iterator, data_const_iterator> DATA(equal_range, const);
+#undef DATA
+ // (Return whether insertion was successful as second.)
+ std::pair<data_iterator, bool>data_insert
+ (const key_type&key, const data_type&data) {
+ key_iterator key_hint = by_key.find(key);
+ data_iterator data_hint = by_data.find(data);
+ if ((unique_key && key_hint != by_key.end()) ||
+ (unique_data && data_hint != by_data.end())) {
+ return std::pair<data_iterator, bool>(by_data.end(), false);
+ }
+ by_key.insert(key_hint, std::pair<key_type, data_type>(key, data));
+ return std::pair<data_iterator, bool>
+ (by_data.insert
+ (data_hint, std::pair<data_type, key_type>(data, key)), true);
+ }
+ void data_erase(data_iterator pos) {
+ std::pair<key_iterator, key_iterator>key_pos = by_key.equal_range(pos->second);
+ data_type match = pos->first;
+ for (; key_pos.first != key_pos.second; ++key_pos.first) {
+ data_type&candidate = key_pos.first->second;
+ if (!by_data.key_comp()(candidate, match) &&
+ !by_data.key_comp()(match, candidate)) {
+ by_data.erase(pos);
+ by_key.erase(key_pos.first);
+ return;
+ }
+ }
+ assert(false);
+ }
+ size_type data_erase(const data_type&data) {
+ size_type result = 0;
+ std::pair<data_iterator, data_iterator>range = by_data.equal_range(data);
+ while (range.first != range.second) {
+ data_iterator tag = range.first++;
+ erase(tag);
+ ++result;
+ }
+ return result;
+ }
+
+ // Others:
+ void clear() {
+ by_key.clear();
+ by_data.clear();
+ }
+ size_type size() const {
+ assert(by_key.size() == by_data.size());
+ return by_key.size();
+ }
+ size_type max_size() const {
+ assert(by_key.max_size() == by_data.max_size());
+ return by_key.max_size();
+ }
+ bool empty() const {
+ assert(by_key.empty() == by_data.empty());
+ return by_key.empty();
+ }
+};
+
+template<class key_type, class data_type, bool unique_key, bool unique_data,
+ class key_compare, class data_compare>std::ostream&operator <<
+ (std::ostream&out,
+ const relation<key_type, data_type, unique_key, unique_data, key_compare,
+ data_compare>&rel) {
+ out << "relation{\n";
+ for (typename relation<key_type, data_type, unique_key, unique_data,
+ key_compare, data_compare>::key_const_iterator iterator =
+ rel.key_begin(),
+ end = rel.key_end();
+ iterator != end;
+ ++iterator) {
+ out << " " << *(iterator->first) << " with " << iterator->second << '\n';
+ }
+ return out << "}\n";
+}
+
+#endif
generated by cgit v1.2.1 (git 2.18.0) at 2024-04-19 09:31:14 +0000