OKlibrary  0.2.1.6
Subsumption.hpp
Go to the documentation of this file.
00001 // Oliver Kullmann, 2.7.2005 (Swansea)
00002 /* Copyright 2005 - 2007, 2010, 2011 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00014 #ifndef SUBSUMPTION_yhgBBv567
00015 #define SUBSUMPTION_yhgBBv567
00016 
00017 #include <algorithm>
00018 #include <iterator>
00019 #include <cassert>
00020 #include <set>
00021 
00022 #include <boost/utility.hpp>
00023 #include <boost/iterator/reverse_iterator.hpp>
00024 #include <boost/mpl/if.hpp>
00025 
00026 #include <OKlib/traits/TypeTraitsContainer.hpp>
00027 #include <OKlib/Programming/MetaProgramming/TaggingPolymorphism.hpp>
00028 
00029 namespace OKlib {
00030   namespace SetAlgorithms {
00031     namespace SubsumptionsTags {
00032 
00033       struct size_tag : OKlib::MetaProgramming::property_tag {};
00034       struct use_size_of_hyperedges : size_tag {};
00035       struct do_not_use_size_of_hyperedges : size_tag {};
00036 
00037       struct uniqueness_tag : OKlib::MetaProgramming::property_tag {};
00038       struct hyperedges_are_unique : uniqueness_tag {};
00039       struct hyperedges_may_not_be_unique : uniqueness_tag {};
00040 
00041       struct order_tag : OKlib::MetaProgramming::property_tag {};
00042       struct hyperedges_sorted_by_size : order_tag {};
00043       struct hyperedges_may_not_be_sorted_by_size : order_tag {};
00044 
00045     }
00046 
00047     // Helper constructions
00048 
00049     template <typename Iterator>
00050     struct Get_underlying_iterator {
00051       typedef Iterator iterator;
00052       const Iterator& operator() (const Iterator& i) {
00053         return i;
00054       }
00055     };
00056     template <typename Iterator>
00057     struct Get_underlying_iterator<boost::reverse_iterator<Iterator> > {
00058       typedef Iterator iterator;
00059       typedef boost::reverse_iterator<Iterator> reverse_iterator;
00060       Iterator operator() (const reverse_iterator& i) const {
00061         return boost::prior(i.base());
00062       }
00063     };
00064     template <typename Iterator>
00065     struct Get_underlying_iterator<std::reverse_iterator<Iterator> > {
00066       typedef Iterator iterator;
00067       typedef std::reverse_iterator<Iterator> reverse_iterator;
00068       Iterator operator() (const reverse_iterator& i) const {
00069         return boost::prior(i.base());
00070       }
00071     };
00072 
00073     // ###############
00074 
00091     template <class Container>
00092     struct Erase {
00093       typedef typename Container::iterator iterator;
00094       iterator operator() (Container& C, const iterator& i) const {
00095         return C.erase(i);
00096       }
00097     };
00098     template <typename T>
00099     struct Erase<std::set<T> > {
00100       typedef std::set<T> Container;
00101       typedef typename Container::iterator iterator;
00102       iterator operator() (Container& C, const iterator& i) const {
00103         iterator j(i); ++j;
00104         C.erase(i);
00105         return j;
00106       }
00107     };
00108     template <typename T>
00109     struct Erase<std::multiset<T> > {
00110       typedef std::multiset<T> Container;
00111       typedef typename Container::iterator iterator;
00112       iterator operator() (Container& C, const iterator& i) const {
00113         iterator j(i); ++j;
00114         C.erase(i);
00115         return j;
00116       }
00117     };
00118 
00119 
00120     // ############################################
00121 
00152     template <class ContainerSets,
00153               class UniquenessTag = SubsumptionsTags::hyperedges_may_not_be_unique,
00154               class OrderTag = SubsumptionsTags::hyperedges_may_not_be_sorted_by_size,
00155               class SizeTag = typename boost::mpl::if_<typename OKlib::traits::has_size_function<ContainerSets>::type, SubsumptionsTags::use_size_of_hyperedges, SubsumptionsTags::do_not_use_size_of_hyperedges>::type
00156     >
00157     struct Subsumption_elimination {
00158 
00159       typedef SizeTag size_tag;
00160       typedef UniquenessTag uniqueness_tag;
00161       typedef OrderTag order_tag;
00162 
00163       template <typename Iterator>
00164       void upward(ContainerSets& C, Iterator begin, const Iterator end) const {
00165         upward(C, begin, end, size_tag());
00166       }
00167 
00168       template <typename Iterator>
00169       void upward(ContainerSets& C, Iterator begin, const Iterator end, SubsumptionsTags::do_not_use_size_of_hyperedges) const {
00170         for (; begin != end; ++begin)
00171           for (Iterator j(boost::next(begin)); j != end;)
00172             if (std::includes(j -> begin(), j -> end(), begin -> begin(), begin -> end()))
00173               j = Iterator(Erase<ContainerSets>()(C, Get_underlying_iterator<Iterator>()(j)));
00174             else
00175               ++j;
00176       }
00177       template <typename Iterator>
00178       void upward(ContainerSets& C, Iterator begin, const Iterator end, SubsumptionsTags::use_size_of_hyperedges) const {
00179         for (; begin != end; ++begin) {
00180           typedef typename std::iterator_traits<Iterator>::value_type::size_type size_type;
00181           const size_type& size(begin -> size());
00182           for (Iterator j(boost::next(begin)); j != end;)
00183             if (cheque_unnecessary(j, size, order_tag(), uniqueness_tag()))
00184               ++j;
00185             else if (std::includes(j -> begin(), j -> end(), begin -> begin(), begin -> end()))
00186               j = Iterator(Erase<ContainerSets>()(C, Get_underlying_iterator<Iterator>()(j)));
00187             else
00188               ++j;
00189         }
00190       }
00191 
00192       template <typename Iterator, typename Size>
00193       bool cheque_unnecessary(const Iterator j, const Size size, SubsumptionsTags::hyperedges_sorted_by_size, SubsumptionsTags::hyperedges_are_unique) const {
00194         assert(size <= j -> size());
00195         return size == j -> size();
00196       }
00197       template <typename Iterator, typename Size>
00198       bool cheque_unnecessary(const Iterator j, const Size size, SubsumptionsTags::hyperedges_sorted_by_size, SubsumptionsTags::hyperedges_may_not_be_unique) const {
00199         assert(size <= j -> size());
00200         return false;
00201       }
00202       template <typename Iterator, typename Size>
00203       bool cheque_unnecessary(const Iterator j, const Size size, SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, SubsumptionsTags::hyperedges_are_unique) const {
00204         return size >= j -> size();
00205       }
00206       template <typename Iterator, typename Size>
00207       bool cheque_unnecessary(const Iterator j, const Size size, SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, SubsumptionsTags::hyperedges_may_not_be_unique) const {
00208         return size > j -> size();
00209       }
00210 
00211       void operator() (ContainerSets& C) const {
00212         eliminate(C, order_tag());
00213       }
00214 
00215       void eliminate(ContainerSets& C, SubsumptionsTags::hyperedges_sorted_by_size) const {
00216         upward(C, C.begin(), C.end());
00217       }
00218       void eliminate(ContainerSets& C, SubsumptionsTags::hyperedges_may_not_be_sorted_by_size) const {
00219         typedef typename ContainerSets::iterator iterator;
00220         const iterator& end(C.end());
00221         upward(C, C.begin(), end);
00222         upward(C, boost::make_reverse_iterator(end), boost::make_reverse_iterator(C.begin()));
00223       }
00224 
00225     };
00226     
00227     template <class ContainerSets>
00228     inline void subsumption_elimination_upward(ContainerSets& C) {
00229       Subsumption_elimination<ContainerSets>().upward(C, C.begin(), C.end());
00230     }
00231 
00232     template <class ContainerSets>
00233     inline void subsumption_elimination(ContainerSets& C) {
00234       Subsumption_elimination<ContainerSets>()(C);
00235     }
00236 
00237   }
00238 
00239 }
00240 
00241 #endif