source: trunk/yat/utility/SegmentTree.h @ 4032

#ifndef theplu_yat_utility_segment_tree
#define theplu_yat_utility_segment_tree

// $Id: SegmentTree.h 4032 2021-01-21 07:44:38Z peter $

/*
  Copyright (C) 2010, 2011, 2012, 2013, 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 "Segment.h"

#include "yat_assert.h"

#include <algorithm>
#include <functional>
#include <utility>

namespace theplu {
namespace yat {
namespace utility {

  /**
     \brief Base Class for SegmentSet and SegmentMap

     - Container: underlying container (set or map)
     - Compare: functor comparing elements (same as in Segment)
     - Value2Key: functor translating a \c const_reference to \c
       key_type (or \c const&)
   */
  template<class Container, class Compare, class Value2Key>
  class SegmentTree
  {
  public:
    /**
       \brief key type is same as \c Container 's \c key_type.

       Typically Segment<element_type>.
    */
    typedef typename Container::key_type key_type;

    /**
       \brief value type is same as \c Container 's \c value_type.

       Typically a Segment<element_type> or pair<const
       Segment<element_type>, Data>.
    */
    typedef typename Container::value_type value_type;

    /**
       \brief element type is same as \c key_type 's value_type.

       If the key held is \c Segment<T>, \c value_type is \c T.
    */
    typedef typename key_type::value_type element_type;

    ///  \brief key compare
    typedef typename Container::key_compare key_compare;
    /// \brief value compare
    typedef typename Container::value_compare value_compare;
    /// \brief element compare
    typedef Compare element_compare;

    /// \brief pointer
    typedef typename Container::pointer pointer;
    /// \brief reference
    typedef typename Container::reference reference;
    /// \brief const reference
    typedef typename Container::const_reference const_reference;
    /// \brief size_type
    typedef typename Container::size_type size_type;
    /// \brief difference_type
    typedef typename Container::difference_type difference_type;
    /// \brief iterator
    typedef typename Container::iterator iterator;
    /// \brief const_iterator
    typedef typename Container::const_iterator const_iterator;

    /**
       \brief creates a SegmentTree with no segments
     */
    SegmentTree(void) {}

    /**
       \brief Destructor
    */
    virtual ~SegmentTree(void) {}

    /**
       \return const iterator pointing to beginning of container
     */
    const_iterator begin(void) const { return container_.begin(); }

    /**
       \return iterator pointing to beginning of container
     */
    iterator begin(void) { return container_.begin(); }

    /**
       \brief erases all values
     */
    void clear(void) { container_.clear(); }

    /**
       \return 1 if there is a Segment that overlaps with \a element
     */
    size_type count(const element_type& element) const;

    /**
       \return \c true if size is zero
    */
    bool empty(void) const { return container_.empty(); }

    /**
       \return a const_iterator pointing to the end of container
     */
    const_iterator end(void) const { return container_.end(); }

    /**
       \return end of container
     */
    iterator end(void) { return container_.end(); }

    /**
       \brief erase values in range [first, last)

       \since New in yat 0.8
     */
    void erase(iterator first, iterator last) { container_.erase(first, last);}

    /**
       erase value pointed to by \a pos

       \since New in yat 0.8
     */
    void erase(iterator pos) { container_.erase(pos); }

    /**
       \return iterator pointing to value containing \a element

       If no value contains \a element, end() is returned.
     */
    iterator find(const element_type& element);

    /**
       \return const iterator pointing to value containing \a element

       If no value contains \a element, end() is returned.

       \return an iterator pointing to the Segment that contains \a
       element. If no Segment contains \a element, end() is returned.
     */
    const_iterator find(const element_type& element) const;

    /**
       \brief insert value

       if \a value does not overlap with container, insert
       segment; otherwise do nothing.

       \return a pair where pair.first points to the inserted \a value
       or if \a value was not inserted it points to a value in
       container that overlaps with \a value; pair.second is true if
       \a value was inserted.
     */
    std::pair<iterator, bool> insert(const value_type& value);

    /**
       Same as insert(const&) but move \a value rather than copy.

       \since New in yat 0.19
     */
    std::pair<iterator, bool> insert(value_type&& value);

    /**
       \return Comparison functor to compare two keys (Segment)
     */
    key_compare key_comp(void) const
    {
      return container_.key_comp();
    }

    /**
       \brief similar to lower_bound in std::set and std::map

       \return iterator pointing to first value whose key overlaps
       with \a element or is greater than \a element.
     */
    iterator lower_bound(const element_type& element);

    /**
       \brief similar to lower_bound in std::set and std::map

       \return const iterator pointing to first value whose key
       overlaps with \a element or is greater than \a element.
     */
    const_iterator lower_bound(const element_type& element) const;

    /**
       \return number of values in container
     */
    size_type size(void) const { return container_.size(); }

    /**
       \return iterator pointing to first segment that is greater than
       \a segment.
     */
    iterator upper_bound(const element_type& element);

    /**
       \brief similar to upper_bound in std::set and std::map

       \return iterator pointing to first value whose key is greater
       than \a element.
     */
    const_iterator upper_bound(const element_type& element) const;

    /**
       \return the \c value_compare object used by the class to sort
       \c values
     */
    value_compare value_comp(void) const { return container_.value_comp(); }

  protected:
    /// underlying container
    Container container_;

    /**
       pair.first first (smallest) segment that overlaps with \a
       segment and pair.second first (smallest) segment that does not
       overlap with \a segment.
     */
    std::pair<iterator, iterator> overlap_range(const key_type& segment)
    {
      iterator first = container_.lower_bound(segment);
      if (first!=begin()) {
        --first;
        if (compare(*first, segment))
          ++first;
      }
      iterator last = first;
      while (last!=end() && !compare(segment, *last))
        ++last;
      YAT_ASSERT(last==end() || compare(segment, *last));
      return std::make_pair(first, last);
    }

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

  template<class Container, class Compare, class Value2Key>
  typename SegmentTree<Container, Compare, Value2Key>::size_type
  SegmentTree<Container,Compare,Value2Key>::count(const element_type& element) const
  {
    if (find(element)==end())
      return 0;
    return 1;
  }


  template<class Container, class Compare, class Value2Key>
  typename SegmentTree<Container, Compare, Value2Key>::const_iterator
  SegmentTree<Container, Compare, Value2Key>::find(const element_type& vt) const
  {
    const_iterator iter = lower_bound(vt);
    element_compare comp;
    //    if (iter==end() || comp(vt, iter->begin()))
    if (iter==end() || comp(vt, Value2Key()(*iter).begin()))
      return end();
    return iter;
  }


  template<class Container, class Compare, class Value2Key>
  typename SegmentTree<Container, Compare, Value2Key>::iterator
  SegmentTree<Container, Compare, Value2Key>::find(const element_type& vt)
  {
    iterator iter = lower_bound(vt);
    element_compare comp;
    if (iter==end() || comp(vt, Value2Key()(*iter).begin()))
      return end();
    return iter;
  }


  template<typename T, class Compare, class Value2Key>
  std::pair<typename SegmentTree<T, Compare, Value2Key>::iterator, bool>
  SegmentTree<T, Compare,Value2Key>::insert(const value_type& segment)
  {
    return container_.insert(segment);
  }


  template<typename T, class Compare, class Value2Key>
  std::pair<typename SegmentTree<T, Compare, Value2Key>::iterator, bool>
  SegmentTree<T, Compare,Value2Key>::insert(value_type&& segment)
  {
    return container_.insert(std::move(segment));
  }


  template<typename T, class Compare, class Value2Key>
  typename SegmentTree<T, Compare, Value2Key>::iterator
  SegmentTree<T, Compare,Value2Key>::lower_bound(const element_type& element)
  {
    key_type segment(element, element);
    iterator result = container_.lower_bound(segment);
    // result is larger or overlapping with segment (i.e.! result<segment)
    YAT_ASSERT(result==end()
               || !compare(Value2Key()(*result),segment));
    return result;
  }


  template<typename T, class Compare, class Value2Key>
  typename SegmentTree<T, Compare, Value2Key>::const_iterator
  SegmentTree<T, Compare,Value2Key>::lower_bound(const element_type& element) const
  {
    key_type segment(element, element);
    const_iterator result = container_.lower_bound(segment);
    // result is larger or overlapping with segment (i.e.! result<segment)
    YAT_ASSERT(result==end()
               || !compare(Value2Key()(*result),segment));
    return result;
  }


  template<typename T, class Compare, class Value2Key>
  typename SegmentTree<T, Compare, Value2Key>::iterator
  SegmentTree<T, Compare,Value2Key>::upper_bound(const element_type& element)
  {
    key_type segment(element, element);
    iterator result = container_.upper_bound(segment);
    Compare comp;
    Value2Key value2key;
    if (result==end() || comp(element, value2key(*result).begin()))
      return result;
    ++result;
    // result is larger than segment
    YAT_ASSERT(result==end() || compare(segment, value2key(*result)));
    return result;
  }


  template<typename T, class Compare, class Value2Key>
  typename SegmentTree<T, Compare, Value2Key>::const_iterator
  SegmentTree<T, Compare,Value2Key>::upper_bound(const element_type& element) const
  {
    Segment<element_type, Compare> segment(element, element);
    const_iterator result = container_.upper_bound(segment);
    Compare comp;
    Value2Key value2key;
    if (result==end() || comp(element, value2key(*result).begin()))
      return result;
    ++result;
    // result is larger than segment
    YAT_ASSERT(result==end() || compare(segment, value2key(*result)));
    return result;
  }

}}}
#endif