text: /******************************************************************************\
  * Copyright (c) 2016, Robert van Engelen, Genivia Inc. All rights reserved.    *
  *                                                                              *
  * Redistribution and use in source and binary forms, with or without           *
  * modification, are permitted provided that the following conditions are met:  *
  *                                                                              *
  *   (1) Redistributions of source code must retain the above copyright notice, *
  *       this list of conditions and the following disclaimer.                  *
  *                                                                              *
  *   (2) Redistributions in binary form must reproduce the above copyright      *
  *       notice, this list of conditions and the following disclaimer in the    *
  *       documentation and/or other materials provided with the distribution.   *
  *                                                                              *
  *   (3) The name of the author may not be used to endorse or promote products  *
  *       derived from this software without specific prior written permission.  *
  *                                                                              *
  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED *
  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF         *
  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO   *
  * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,       *
  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, *
  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;  *
  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,     *
  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR      *
  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF       *
  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.                                   *
  \******************************************************************************/
  
  /**
  @file      setop.h
  @brief     RE/flex operations on STL containers and sets
  @author    Robert van Engelen - engelen@genivia.com
  @copyright (c) 2016-2020, Robert van Engelen, Genivia Inc. All rights reserved.
  @copyright (c) BSD-3 License - see LICENSE.txt
  
  Usage
  -----
  
  `reflex::is_disjoint<S1,S2>(S1 s1, S2 s2)` is true if `s1` and `s2` are
  disjoint sets.
  
  `reflex::is_subset<S1,S2>(S1 s1, S2 s2)` is true if `s1` is a subset of `s2`.
  
  `reflex::is_in_set<T,S>(T x, S s)` is true if `x` is in `s`.
  
  `reflex::set_insert<S1,S2>(S1 s1, S2 s2)` inserts elements of `s2` into `s1`.
  
  `reflex::set_delete<S1,S2>(S1 s1, S2 s2)` deletes elements of `s2` from `s1`.
  
  `reflex::lazy_intersection<S1,S2>(S1 s1, S2 s2)` is a structure with an
  iterator over elements that are in `s1` and in `s2`.
  
  `reflex::lazy_union<S1,S2>(S1 s1, S2 s2)` is a structure with an iterator over
  elements that are in `s1` or in `s2`.
  
  The rationale for using `reflex::lazy_intersection` and `reflex::lazy_union` is
  to save memory when the results do not need to be stored in a set, since the
  elements are lazely produced by an iterator.
  
  Example
  -------
  
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~{.cpp}
      std::set<int> s1;
      s1.insert(1);
      assert(reflex::is_in_set(1, s1) == true);
      std::set<int> s2;
      s2.insert(1);
      s2.insert(2);
      assert(reflex::is_disjoint(s1, s2) == false);
      assert(reflex::is_subset(s1, s2) == true);
      reflex::lazy_union< std::set<int>,std::set<int> > U(s1, s2);
      for (reflex::lazy_union< std::set<int>,std::set<int> >::iterator i = U.begin(); i != U.end(); ++i)
        std::cout << *i << std::endl; // prints 1 and 2
      reflex::lazy_intersection< std::set<int>,std::set<int> > I(s1, s2);
      for (reflex::lazy_intersection< std::set<int>,std::set<int> >::iterator i = I.begin(); i != I.end(); ++i)
        std::cout << *i << std::endl; // prints 1
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  
  */
  
  #ifndef REFLEX_SETOP_H
  #define REFLEX_SETOP_H
  
  namespace reflex {
  
  /// Check if sets `s1` and `s2` are disjoint.
  template<typename S1, typename S2> 
  bool is_disjoint(
      const S1& s1,
      const S2& s2)
    /// @returns true or false
  {
    if (s1.empty() || s2.empty())
      return true;
    typename S1::const_iterator i1 = s1.begin();
    typename S2::const_iterator i2 = s2.begin();
    typename S1::key_compare lt = s1.key_comp();
    if (lt(*s2.rbegin(), *i1) || lt(*s1.rbegin(), *i2))
      return true;
    typename S1::const_iterator i1_end = s1.end();
    typename S2::const_iterator i2_end = s2.end();
    while (i1 != i1_end && i2 != i2_end)
    {
      if (lt(*i1, *i2))
        i1++;
      else if (lt(*i2, *i1))
        i2++;
      else
        return false;
    }
    return true;
  }
  
  /// Check if value `x` is in set `s`.
  template<typename T, typename S> 
  inline bool is_in_set(
      const T& x,
      const S& s)
    /// @returns true or false
  {
    return s.find(x) != s.end();
  }
  
  /// Check if set `s1` is a subset of set `s2`.
  template<typename S1, typename S2> 
  bool is_subset(
      const S1& s1,
      const S2& s2)
    /// @returns true or false
  {
    if (s1.empty())
      return true;
    if (s2.empty())
      return false;
    typename S1::const_iterator i1 = s1.begin();
    typename S2::const_iterator i2 = s2.begin();
    typename S1::key_compare lt = s1.key_comp();
    if (lt(*s2.rbegin(), *i1) || lt(*s1.rbegin(), *i2))
      return false;
    typename S1::const_iterator i1_end = s1.end();
    typename S2::const_iterator i2_end = s2.end();
    while (i1 != i1_end && i2 != i2_end)
    {
      if (lt(*i1, *i2))
        return false;
      if (!lt(*i2, *i1))
        i1++;
      i2++;
    }
    return (i1 == i1_end);
  }
  
  /// Insert set `s2` into set `s1`.
  template<typename S1, typename S2>
  inline void set_insert(
      S1& s1,
      const S2& s2)
  {
    s1.insert(s2.begin(), s2.end());
  }
  
  /// Delete elements of set `s2` from set `s1`.
  template<typename S1, typename S2>
  void set_delete(
      S1& s1,
      const S2& s2)
  {
    if (s1.empty() || s2.empty())
      return;
    typename S1::const_iterator i1 = s1.begin();
    typename S2::const_iterator i2 = s2.begin();
    typename S1::key_compare lt = s1.key_comp();
    if (lt(*s2.rbegin(), *i1) || lt(*s1.rbegin(), *i2))
      return;
    typename S1::const_iterator i1_end = s1.end();
    typename S2::const_iterator i2_end = s2.end();
    while (i1 != i1_end && i2 != i2_end)
    {
      if (lt(*i1, *i2))
        i1++;
      else if (lt(*i2, *i1))
        i2++;
      else
      {
        i1 = s1.erase(i1);
        i2++;
      }
    }
  }
  
  /// Intersection of two ordered sets, with an iterator to get elements lazely.
  template<typename S1, typename S2> 
  struct lazy_intersection {
    /// Iterator to lazely get elements of a set intersection.
    struct iterator {
      iterator(
          const S1& s1,
          const S2& s2)
        :
          i1(s1.begin()),
          i1_end(s1.end()),
          i2(s2.begin()),
          i2_end(s2.end()),
          lt(s1.key_comp())
      {
        find();
      }
      iterator(
          const typename S1::const_iterator& i1,
          const typename S2::const_iterator& i2)
        :
          i1(i1),
          i1_end(i1),
          i2(i2),
          i2_end(i2)
      {
        find();
      }
      const typename S1::key_type operator*() const
      {
        return *i1;
      }
      iterator& operator++()
      {
        next();
        return *this;
      }
      iterator operator++(int)
      {
        iterator copy = *this;
        next();
        return copy;
      }
      bool operator==(const iterator& rhs) const
      {
        return (i1 == rhs.i1 && i2 == rhs.i2) || (i1 == i1_end && rhs.i1 == rhs.i1_end) || (i2 == i2_end && rhs.i2 == rhs.i2_end);
      }
      bool operator!=(const iterator& rhs) const
      {
        return !operator==(rhs);
      }
      void find(void)
      {
        while (i1 != i1_end && i2 != i2_end)
        {
          if (lt(*i1, *i2))
            i1++;
          else if (lt(*i2, *i1))
            i2++;
          else
            break;
        }
      }
      void next(void)
      {
        if (i1 != i1_end)
          i1++;
        find();
      }
      typename S1::const_iterator i1, i1_end;
      typename S2::const_iterator i2, i2_end;
      typename S1::key_compare lt;
    };
    typedef struct iterator const_iterator;
    lazy_intersection(
        const S1& s1,
        const S2& s2)
      :
        s1(s1),
        s2(s2)
    { }
    const_iterator begin(void) const
    {
      return const_iterator(s1, s2);
    }
    const_iterator end(void) const
    {
      return const_iterator(s1.end(), s2.end());
    }
    const S1& s1;
    const S2& s2;
  };
  
  /// Union of two ordered sets, with an iterator to get elements lazely.
  template<typename S1, typename S2> 
  struct lazy_union {
    /// Iterator to lazely get elements of a set union.
    struct iterator {
      iterator(
          const S1& s1,
          const S2& s2)
        :
          i1(s1.begin()),
          i1_end(s1.end()),
          i2(s2.begin()),
          i2_end(s2.end()),
          lt(s1.key_comp())
      {
        find();
      }
      iterator(
          const typename S1::const_iterator& i1,
          const typename S2::const_iterator& i2)
        :
          i1(i1),
          i1_end(i1),
          i2(i2),
          i2_end(i2)
      {
        find();
      }
      const typename S1::key_type operator*() const
      {
        return second ? *i2 : *i1;
      }
      iterator& operator++()
      {
        next();
        return *this;
      }
      iterator operator++(int)
      {
        iterator copy = *this;
        next();
        return copy;
      }
      bool operator==(const iterator& rhs) const
      {
        return (i1 == rhs.i1 && i2 == rhs.i2) || (i1 == i1_end && rhs.i1 == rhs.i1_end && i2 == i2_end && rhs.i2 == rhs.i2_end);
      }
      bool operator!=(const iterator& rhs) const
      {
        return !operator==(rhs);
      }
      void find(void)
      {
        if (i1 == i1_end)
        {
          second = true;
        }
        else
        {
          while (i2 != i2_end && !lt(*i1, *i2) && !lt(*i2, *i1))
            ++i2;
        }
      }
      void next(void)
      {
        if (i1 == i1_end)
        {
          if (i2 != i2_end)
            ++i2;
          second = true;
        }
        else if (i2 == i2_end)
        { 
          if (i1 != i1_end)
            ++i1;
          second = false;
        }
        else
        {
          if (second)
          {
            ++i2;
            second = false;
          }
          else
          {
            ++i1;
            second = true;
          }
          while (i1 != i1_end && i2 != i2_end)
          {
            if (lt(*i1, *i2))
            {
              second = false;
              break;
            }
            else if (lt(*i2, *i1))
            {
              second = true;
              break;
            }
            else
            {
              ++i2;
            }
          }
        }
      }
      typename S1::const_iterator i1, i1_end;
      typename S2::const_iterator i2, i2_end;
      typename S1::key_compare lt;
      bool second;
    };
    typedef struct iterator const_iterator;
    lazy_union(
        const S1& s1,
        const S2& s2)
      :
        s1(s1),
        s2(s2)
    { }
    const_iterator begin(void) const
    {
      return const_iterator(s1, s2);
    }
    const_iterator end(void) const
    {
      return const_iterator(s1.end(), s2.end());
    }
    const S1& s1;
    const S2& s2;
  };
  
  } // namespace reflex
  
  #endif
  