---

range.hpp

Go to the documentation of this file.

/*
range and range_set utility class
Copyright (C) 1999-2002 Frediano Ziglio
-----

This program 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 2 of the License, or
(at your option) any later version.

This program 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 this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
-----

INFORMATION
  www: https://freddy77.tripod.com/perdr/
  e-mail: freddy77@angelfire.com
*/
#ifndef FILE_RANGE_HPP
#define FILE_RANGE_HPP

template<class T>
struct range
{
  T begin;
  T end;
  range() {};
  range(T a,T b):begin(a),end(b) {};
  // !!!
  bool operator<(const range<T>& rhs) const
  { return begin<rhs.begin; }
  // !!!
  bool operator==(const range<T>& rhs) const
  { return begin==rhs.begin; }
};

#include <vector>
#include <algorithm>

template <class T>
class range_set
{
private:
  typedef std::vector< range<T> > TSet;
  TSet set;
public:
  struct range_comp
  {
    bool operator()(const range<T>& a,const range<T>& b)
    { return a.end < b.begin; }
  };

  typedef typename TSet::value_type             value_type;
  typedef typename TSet::const_reference        reference;
  typedef typename TSet::const_reference        const_reference;
  typedef typename TSet::const_iterator         iterator;
  typedef typename TSet::const_iterator         const_iterator;
  typedef typename TSet::size_type              size_type;
  typedef typename TSet::difference_type        difference_type;
  typedef typename TSet::const_reverse_iterator reverse_iterator;
  typedef typename TSet::const_reverse_iterator const_reverse_iterator;

  // Iterators
  // non lascia mai modificare i range a mano
  const_iterator begin () const { return set.begin(); }
  const_iterator end () const { return set.end(); }
  const_reverse_iterator rbegin () const { return set.rbegin(); }
  const_reverse_iterator rend () const { return set.rend(); }

  // Capacity
  bool empty () const { return set.empty(); }
  size_type size () const { return set.size(); }
  size_type max_size () const { return set.max_size(); }


  // Modifiers
  bool insert (const value_type&);
//  iterator insert (iterator, const value_type&);
  void erase (iterator i)
  { set.erase(const_cast<typename TSet::iterator>(i)); }
  void erase (const value_type&);
  void erase (iterator a, iterator b)
  { set.erase(const_cast<typename TSet::iterator>(a),const_cast<typename TSet::iterator>(b)); }
  void swap (range_set<T>& rhs) { set.swap(rhs.set); }

  // Set operations
//  size_type count (const key_type& key) const { return set.count(key); }
//  pair<iterator, iterator> equal_range (const  key_type&) const;
//  iterator find (const key_value& key) const { return set.find(key); }
//  iterator lower_bound (const key_type& key) const { return set.lower_bound(key); }
//  iterator upper_bound (const key_type& key) const { return set.upper_bound(key); }
};

/*
template <class T>
std::pair<range_set<T>::iterator, bool> range_set<T>::insert (const value_type& value)
{
  iterator i = lower_bound(value);

  // non trovato, inserisci
  if (i==end() || (*i).begin != value.begin)
  {
    return std::pair(set.insert(i,value),false);
  }

  // contenuto in quello corrente
  if ( value.end <= (*i.end) )
    return std::pair(i,true);

  //
}
*/

// ritorna se gia' inserito
template <class T>
bool range_set<T>::insert(const value_type& value)
{
  // testa range invalido o vuoto
  if (value.begin >= value.end)
    return true;

  typename TSet::iterator i = std::lower_bound(set.begin(),set.end(),value,range_comp());

  // se fuori range inserisce e basta
  if (i==set.end() || value.end < (*i).begin)
  {
    set.insert(i,value);
    return false;
  }

  // estende inizio se necessario
  bool res = true;
  if (value.begin < (*i).begin)
  {
    (*i).begin = value.begin;
    res = false;
  }

  // estende fine se necessario
  if (value.end >= (*i).end)
  {
    // calcola fine range e range in eccesso
    T end = value.end;
    typename TSet::iterator ii = i;
    while(++ii != set.end())
    {
      if (end >=(*ii).begin && end<=(*ii).end)
        end = (*ii).end;
      if (end < (*ii).end)
        break;
    }

    // estendi range finale
    (*i).end = end;

    // cancella ranges in eccesso
    set.erase(++i,ii);

    // il range non era interamente presente
    return false;
  }
  return res;
}

template <class T>
void range_set<T>::erase (const value_type& value)
{
  // testa range invalido o vuoto
  if (value.begin >= value.end)
    return;

  typename TSet::iterator i = std::lower_bound(set.begin(),set.end(),value,range_comp());

  if (i==set.end())
    return;

  // se non interseca con nessuno esci
  if ( value.end <= (*i).begin )
    return;

  // tronca successivo
  if ( value.begin > (*i).begin )
  {
    // sdoppia range
    if ( value.end < (*i).end)
    {
      T begin = (*i).begin;
      (*i).begin = value.end;
      set.insert(i,value_type(begin,value.begin));
      return;
    }
    (*i).end = value.begin;
    ++i;
  }

  // cerca tutti i range che si devono togliere del tutto
  typename TSet::iterator ii = i;
  while( ii != set.end() && value.end >= (*ii).end )
    ++ii;

  // toglie parte in eccesso al range corrente
  if ( value.end >= (*ii).begin )
    (*ii).begin = value.end;

  // toglie ranges in eccesso
  set.erase(i,ii);
}

#endif //FILE_RANGE_HPP

---