LCOV - code coverage report
Current view: top level - utilities/include/mcrl2/utilities/detail - container_utility.h (source / functions) Hit Total Coverage
Test: mcrl2_coverage.info.cleaned Lines: 49 50 98.0 %
Date: 2020-02-13 00:44:47 Functions: 33 47 70.2 %
Legend: Lines: hit not hit

          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/utilities/detail/container_utility.h
      10             : /// \brief add your file description here.
      11             : 
      12             : #ifndef MCRL2_UTILITIES_DETAIL_CONTAINER_UTILITY_H
      13             : #define MCRL2_UTILITIES_DETAIL_CONTAINER_UTILITY_H
      14             : 
      15             : #include "mcrl2/utilities/exception.h"
      16             : #include <algorithm>
      17             : #include <iterator>
      18             : #include <map>
      19             : #include <set>
      20             : #include <unordered_set>
      21             : 
      22             : namespace mcrl2 {
      23             : 
      24             : namespace utilities {
      25             : 
      26             : namespace detail {
      27             : 
      28             : /// \brief Returns the value corresponding to the given key in the map m. If the key is not
      29             : /// present, an exception is thrown.
      30             : template <typename Map>
      31             : typename Map::mapped_type map_element(const Map& m, const typename Map::key_type& key)
      32             : {
      33             :   auto i = m.find(key);
      34             :   if (i == m.end())
      35             :   {
      36             :     std::ostringstream out;
      37             :     out << "missing key in map!";
      38             :     throw mcrl2::runtime_error(out.str());
      39             :   }
      40             :   return i->second;
      41             : }
      42             : 
      43             : // Returns the value corresponding to the given key in map m, or undefined_value if no such value exists.
      44             : template <typename Map>
      45           4 : typename Map::mapped_type mapped_value(const Map& m, const typename Map::key_type& key, const typename Map::mapped_type& undefined_value)
      46             : {
      47           4 :   auto i = m.find(key);
      48           4 :   if (i != m.end())
      49             :   {
      50           4 :     return i->second;
      51             :   }
      52           0 :   return undefined_value;
      53             : }
      54             : 
      55             : /// \brief Returns the value corresponding to the given key in the set m. If the key is not
      56             : /// present, an exception is thrown.
      57             : template <typename Container>
      58        8514 : bool contains(const Container& c, const typename Container::value_type& v)
      59             : {
      60        8514 :   return std::find(c.begin(), c.end(), v) != c.end();
      61             : }
      62             : 
      63             : // specialization
      64             : template <typename T>
      65       76139 : bool contains(const std::set<T>& c, const typename std::set<T>::value_type& v)
      66             : {
      67       76139 :   return c.find(v) != c.end();
      68             : }
      69             : 
      70             : // specialization
      71             : template <typename T>
      72         131 : bool contains(const std::multiset<T>& c, const typename std::multiset<T>::value_type& v)
      73             : {
      74         131 :   return c.find(v) != c.end();
      75             : }
      76             : 
      77             : // specialization
      78             : template <typename T>
      79        5583 : bool contains(const std::unordered_set<T>& c, const typename std::set<T>::value_type& v)
      80             : {
      81        5583 :   return c.find(v) != c.end();
      82             : }
      83             : 
      84             : /// \brief Returns the value corresponding to the given key in the set m. If the key is not
      85             : /// present, an exception is thrown.
      86             : template <typename Key, typename T>
      87           3 : bool has_key(const std::map<Key, T>& c, const Key& v)
      88             : {
      89           3 :   return c.find(v) != c.end();
      90             : }
      91             : 
      92             : /// \brief Returns the value corresponding to the given key in the set m. If the key is not
      93             : /// present, an exception is thrown.
      94             : template <typename Key, typename T>
      95             : bool has_key(const std::multimap<Key, T>& c, const Key& v)
      96             : {
      97             :   return c.find(v) != c.end();
      98             : }
      99             : 
     100             : // Remove an element from v, and return it.
     101             : template <typename Container>
     102         171 : typename Container::value_type pick_element(Container& v)
     103             : {
     104         171 :   auto i = v.begin();
     105         171 :   auto result = *i;
     106         171 :   v.erase(i);
     107         171 :   return result;
     108             : }
     109             : 
     110             : // inserts elements of c into s
     111             : template <typename T, typename Container>
     112             : void set_insert(std::set<T>& s, const Container& c)
     113             : {
     114             :   for (auto i = c.begin(); i != c.end(); ++i)
     115             :   {
     116             :     s.insert(*i);
     117             :   }
     118             : }
     119             : 
     120             : // removes elements of c from s
     121             : template <typename T, typename Container>
     122             : void set_remove(std::set<T>& s, const Container& c)
     123             : {
     124             :   for (auto i = c.begin(); i != c.end(); ++i)
     125             :   {
     126             :     s.erase(*i);
     127             :   }
     128             : }
     129             : 
     130             : // C++11; works for sets and maps
     131             : // Removes elements that satisfy predicate pred.
     132             : template< typename ContainerT, typename PredicateT >
     133       21445 : void remove_if(ContainerT& items, const PredicateT& predicate)
     134             : {
     135       77353 :   for (auto it = items.begin(); it != items.end();)
     136             :   {
     137       55908 :         if (predicate(*it))
     138             :         {
     139       35292 :           it = items.erase(it);
     140             :         }
     141       20616 :         else ++it;
     142             :   }
     143       21445 : }
     144             : 
     145             : /// Returns true if the sorted ranges [first1, ..., last1) and [first2, ..., last2) have an empty intersection
     146             : template <typename InputIterator1, typename InputIterator2>
     147         707 : bool has_empty_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
     148             : {
     149         881 :   while (first1 != last1 && first2 != last2)
     150             :   {
     151         279 :     if (*first1 < *first2)
     152             :     {
     153          71 :       ++first1;
     154             :     }
     155         208 :     else if (*first2 < *first1)
     156             :     {
     157         103 :       ++first2;
     158             :     }
     159             :     else
     160             :     {
     161         105 :       return false;
     162             :     }
     163             :   }
     164         428 :   return true;
     165             : }
     166             : 
     167             : template <typename SetContainer1, typename SetContainer2>
     168         132 : bool has_empty_intersection(const SetContainer1& s1, const SetContainer2& s2)
     169             : {
     170         132 :   return has_empty_intersection(s1.begin(), s1.end(), s2.begin(), s2.end());
     171             : }
     172             : 
     173             : /// \brief Returns the union of two sets.
     174             : /// \param x A set
     175             : /// \param y A set
     176             : /// \return The union of two sets.
     177             : template <typename T>
     178          14 : std::set<T> set_union(const std::set<T>& x, const std::set<T>& y)
     179             : {
     180          14 :   std::set<T> result;
     181          14 :   std::set_union(x.begin(), x.end(), y.begin(), y.end(), std::inserter(result, result.begin()));
     182          14 :   return result;
     183             : }
     184             : 
     185             : /// \brief Returns the difference of two sets.
     186             : /// \param x A set
     187             : /// \param y A set
     188             : /// \return The difference of two sets.
     189             : template <typename T>
     190         232 : std::set<T> set_difference(const std::set<T>& x, const std::set<T>& y)
     191             : {
     192         232 :   std::set<T> result;
     193         232 :   std::set_difference(x.begin(), x.end(), y.begin(), y.end(), std::inserter(result, result.begin()));
     194         232 :   return result;
     195             : }
     196             : 
     197             : /// \brief Returns the intersection of two sets.
     198             : /// \param x A set
     199             : /// \param y A set
     200             : /// \return The intersection of two sets.
     201             : template <typename T>
     202         503 : std::set<T> set_intersection(const std::set<T>& x, const std::set<T>& y)
     203             : {
     204         503 :   std::set<T> result;
     205         503 :   std::set_intersection(x.begin(), x.end(), y.begin(), y.end(), std::inserter(result, result.begin()));
     206         503 :   return result;
     207             : }
     208             : 
     209             : /// \brief Returns if y is included in x.
     210             : /// \param x A set
     211             : /// \param y A set
     212             : /// \return The intersection of two sets.
     213             : template <typename T>
     214           6 : bool set_includes(const std::set<T>& x, const std::set<T>& y)
     215             : {
     216           6 :   return std::includes(x.begin(), x.end(), y.begin(), y.end());
     217             : }
     218             : 
     219             : } // namespace detail
     220             : 
     221             : } // namespace utilities
     222             : 
     223             : } // namespace mcrl2
     224             : 
     225             : #endif // MCRL2_UTILITIES_DETAIL_CONTAINER_UTILITY_H

Generated by: LCOV version 1.13