Segment.h

#ifndef theplu_yat_utility_segment
#define theplu_yat_utility_segment

// $Id: Segment.h 4089 2021-09-07 00:56:40Z peter $

/*
  Copyright (C) 2010, 2015, 2016, 2017 Peter Johansson
  Copyright (C) 2019 Jari Häkkinen
  Copyright (C) 2021 Peter Johansson

  This file is part of the yat library, http://dev.thep.lu.se/yat

  The yat library 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.

  The yat library 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 yat. If not, see <http://www.gnu.org/licenses/>.
*/

#include "yat_assert.h"

#include <algorithm>
#include <functional>

namespace theplu {
namespace yat {
namespace utility {

  template<typename T, class Compare = std::less<T> >
  class Segment
  {
  public:
    typedef T value_type;

    Segment(void) {}

    Segment(const T& begin, const T& end)
      : begin_(begin), end_(end) {}

    Segment(T&& begin, T&& end)
      : begin_(std::move(begin)), end_(std::move(end)) {}

    T& begin(void) { return begin_; }

    const T& begin(void) const { return begin_; }

    T& end(void) { return end_; }

    const T& end(void) const { return end_; }

  private:
    T begin_;
    T end_;

    // using compiler generated copying
    //Segment(const Segment&);
    //Segment& operator=(const Segment&);
  };


  template<typename T>
  Segment<T> make_segment(T first, T last)
  {
    return Segment<T>(first, last);
  }


  template<typename T, class Compare>
  bool operator!=(const Segment<T, Compare>& lhs,
                  const Segment<T, Compare>& rhs)
  {
    Compare comp;
    return comp(lhs.begin(), rhs.begin()) ||  comp(rhs.begin(), lhs.begin())
      || comp(lhs.end(), rhs.end()) || comp(rhs.end(), lhs.end());
  }


  template<typename T, class Compare>
  bool operator==(const Segment<T, Compare>& lhs,
                  const Segment<T, Compare>& rhs)
  {
    return !(lhs!=rhs);
  }


  template<typename T, class Compare>
  bool compare(const Segment<T, Compare>& lhs, const Segment<T, Compare>& rhs)
  {
    Compare c;
    // begin <= end
    YAT_ASSERT(!c(lhs.end(), lhs.begin()));
    YAT_ASSERT(!c(rhs.end(), rhs.begin()));
    // take care of case when both sides are zero segments
    if (!c(lhs.begin(), lhs.end()) && !c(rhs.begin(), rhs.end())) {
      return c(lhs.begin(), rhs.begin());
    }

    return ! c(rhs.begin(), lhs.end());
  }

  template<typename T, class Compare>
  int compare_3way(const Segment<T, Compare>& lhs,
                   const Segment<T, Compare>& rhs)
  {
    if (compare(lhs, rhs))
      return -1;
    if (compare(rhs, lhs))
      return 1;
    return 0;
  }

  template<typename T, class Compare>
  int compare_3way(const T& element,
                   const Segment<T, Compare>& segment)
  {
    Compare comp;
    if (comp(element, segment.begin()))
      return -1;
    if (comp(element, segment.end()))
      return 0;
    return 1;
  }

  template<typename T, class Compare>
  int compare_3way(const Segment<T, Compare>& segment,
                   const T& element)
  {
    return -compare_3way(element, segment);
  }

  template<typename T, class Compare>
  Segment<T, Compare> intersection(const Segment<T, Compare>& a,
                                   const Segment<T, Compare>& b)
  {
    Compare comp;
    Segment<T, Compare> result;

    result.begin() = std::max(a.begin(), b.begin(), comp);
    // the first max is needed in case a and b don't overlap
    result.end() = std::max(result.begin(),
                            std::min(a.end(), b.end(), comp),
                            comp);
    return result;
  }


  template<typename T, class Compare>
  Segment<T, Compare> set_union(const Segment<T, Compare>& a,
                                const Segment<T, Compare>& b)
  {
    Compare comp;
    return Segment<T, Compare>(std::min(a.begin(), b.begin(), comp),
                               std::max(a.end(), b.end(), comp));
  }


  template<typename T, class Compare>
  bool includes(const yat::utility::Segment<T, Compare>& lhs,
                const yat::utility::Segment<T, Compare>& rhs)
  {
    Compare comp;
    return !(comp(lhs.begin(), rhs.begin()) || comp(rhs.end(), lhs.end()));
  }


  template<typename T, class Compare>
  bool overlap(const yat::utility::Segment<T, Compare>& lhs,
               const yat::utility::Segment<T, Compare>& rhs)
  {
    return !compare(lhs, rhs) && !compare(rhs, lhs);
  }


  template<typename T, class Compare>
  struct SegmentCompare :
    public std::binary_function<Segment<T,Compare>, Segment<T,Compare>, bool>
  {
    bool operator()(const Segment<T, Compare>& lhs,
                    const Segment<T, Compare>& rhs) const
    { return compare(lhs, rhs); }
  };

}}}
#endif