Line data    Source code

       1             : // Author(s): Wieger Wesselink
       2             : // Copyright: see the accompanying file COPYING or copy at
       3             : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
       4             : //
       5             : // Distributed under the Boost Software License, Version 1.0.
       6             : // (See accompanying file LICENSE_1_0.txt or copy at
       7             : // http://www.boost.org/LICENSE_1_0.txt)
       8             : //
       9             : /// \file mcrl2/data/detail/sequence_algorithm.h
      10             : /// \brief Add your file description here.
      11             : 
      12             : #ifndef MCRL2_DATA_DETAIL_SEQUENCE_ALGORITHM_H
      13             : #define MCRL2_DATA_DETAIL_SEQUENCE_ALGORITHM_H
      14             : 
      15             : #include <algorithm>
      16             : #include <iterator>
      17             : #include <set>
      18             : #include <vector>
      19             : 
      20             : namespace mcrl2
      21             : {
      22             : 
      23             : namespace data
      24             : {
      25             : 
      26             : namespace detail
      27             : {
      28             : 
      29             : /// \brief Returns true if the sequence [first, last) contains duplicates.
      30             : /// \param first Start of a sequence
      31             : /// \param last End of a sequence
      32             : /// \return True if the sequence [first, last) contains duplicates.
      33             : template <typename Iterator>
      34        2075 : bool sequence_contains_duplicates(Iterator first, Iterator last)
      35             : {
      36             :   // TODO: this implementation is not particularly efficient
      37        2075 :   std::set<typename std::iterator_traits<Iterator>::value_type> s(first, last);
      38        4150 :   return s.size() < static_cast <std::size_t>(std::distance(first, last));
      39        2075 : }
      40             : 
      41             : /// \brief Returns true if the two sequences [first1, last1) and [first2, last2) have a non empty intersection.
      42             : /// \param first1 Start of a sequence
      43             : /// \param last1 End of a sequence
      44             : /// \param first2 Start of a sequence
      45             : /// \param last2 End of a sequence
      46             : /// \return True if the two sequences [first1, last1) and [first2, last2) have a non empty intersection.
      47             : template <typename Iterator1, typename Iterator2>
      48           0 : bool sequences_do_overlap(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2)
      49             : {
      50             :   typedef typename std::iterator_traits<Iterator1>::value_type value_type;
      51           0 :   std::set<value_type> s1(first1, last1);
      52           0 :   std::set<value_type> s2(first2, last2);
      53           0 :   std::vector<value_type> intersection;
      54           0 :   std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(intersection));
      55           0 :   return !intersection.empty();
      56           0 : }
      57             : 
      58             : /// \brief Returns true if all elements of the range [first, last) are element of the set s.
      59             : /// \param first Start of a sequence
      60             : /// \param last End of a sequence
      61             : /// \param s A set
      62             : /// \return True if all elements of the range [first, last) are element of the set s.
      63             : template <typename Iterator, typename T>
      64             : bool sequence_is_subset_of_set(Iterator first, Iterator last, const std::set<T>& s)
      65             : {
      66             :   for (Iterator i = first; i != last; ++i)
      67             :   {
      68             :     if (s.find(*i) == s.end())
      69             :     {
      70             :       return false;
      71             :     }
      72             :   }
      73             :   return true;
      74             : }
      75             : 
      76             : /// \brief Makes a set of the given container.
      77             : /// \param c A container
      78             : /// \return A set containing the elements of the container
      79             : template <class Container>
      80        1556 : std::set<typename Container::value_type> make_set(const Container& c)
      81             : {
      82        1556 :   std::set<typename Container::value_type> result;
      83        1556 :   std::copy(c.begin(), c.end(), std::inserter(result, result.begin()));
      84        1556 :   return result;
      85           0 : }
      86             : 
      87             : /// \brief Determines if the unordered sequences s1 and s2 have an empty intersection
      88             : /// \param s1 A sequence
      89             : /// \param s2 A sequence
      90             : /// \return True if the intersection of s1 and s2 is empty
      91             : template <typename Sequence>
      92             : bool sequence_empty_intersection(Sequence s1, Sequence s2)
      93             : {
      94             :   for (typename Sequence::const_iterator i = s1.begin(); i != s1.end(); ++i)
      95             :   {
      96             :     if (std::find(s2.begin(), s2.end(), *i) != s2.end())
      97             :     {
      98             :       return false;
      99             :     }
     100             :   }
     101             :   return true;
     102             : }
     103             : 
     104             : } // namespace detail
     105             : 
     106             : } // namespace data
     107             : 
     108             : } // namespace mcrl2
     109             : 
     110             : #endif // MCRL2_DATA_DETAIL_SEQUENCE_ALGORITHM_H