Make your own free website on Tripod.com
Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

range.hpp

Go to the documentation of this file.
00001 /*
00002 range and range_set utility class
00003 Copyright (C) 1999-2002 Frediano Ziglio
00004 -----
00005 
00006 This program is free software; you can redistribute it and/or modify
00007 it under the terms of the GNU General Public License as published by
00008 the Free Software Foundation; either version 2 of the License, or
00009 (at your option) any later version.
00010 
00011 This program is distributed in the hope that it will be useful,
00012 but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 GNU General Public License for more details.
00015 
00016 You should have received a copy of the GNU General Public License
00017 along with this program; if not, write to the Free Software
00018 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00019 -----
00020 
00021 INFORMATION
00022   www: http://freddy77.tripod.com/perdr/
00023   e-mail: freddy77@angelfire.com
00024 */
00025 #ifndef FILE_RANGE_HPP
00026 #define FILE_RANGE_HPP
00027 
00028 template<class T>
00029 struct range
00030 {
00031   T begin;
00032   T end;
00033   range() {};
00034   range(T a,T b):begin(a),end(b) {};
00035   // !!!
00036   bool operator<(const range<T>& rhs) const
00037   { return begin<rhs.begin; }
00038   // !!!
00039   bool operator==(const range<T>& rhs) const
00040   { return begin==rhs.begin; }
00041 };
00042 
00043 #include <vector>
00044 #include <algorithm>
00045 
00046 template <class T>
00047 class range_set
00048 {
00049 private:
00050   typedef std::vector< range<T> > TSet;
00051   TSet set;
00052 public:
00053   struct range_comp
00054   {
00055     bool operator()(const range<T>& a,const range<T>& b)
00056     { return a.end < b.begin; }
00057   };
00058 
00059   typedef typename TSet::value_type             value_type;
00060   typedef typename TSet::const_reference        reference;
00061   typedef typename TSet::const_reference        const_reference;
00062   typedef typename TSet::const_iterator         iterator;
00063   typedef typename TSet::const_iterator         const_iterator;
00064   typedef typename TSet::size_type              size_type;
00065   typedef typename TSet::difference_type        difference_type;
00066   typedef typename TSet::const_reverse_iterator reverse_iterator;
00067   typedef typename TSet::const_reverse_iterator const_reverse_iterator;
00068 
00069   // Iterators
00070   // non lascia mai modificare i range a mano
00071   const_iterator begin () const { return set.begin(); }
00072   const_iterator end () const { return set.end(); }
00073   const_reverse_iterator rbegin () const { return set.rbegin(); }
00074   const_reverse_iterator rend () const { return set.rend(); }
00075 
00076   // Capacity
00077   bool empty () const { return set.empty(); }
00078   size_type size () const { return set.size(); }
00079   size_type max_size () const { return set.max_size(); }
00080 
00081 
00082   // Modifiers
00083   bool insert (const value_type&);
00084 //  iterator insert (iterator, const value_type&);
00085   void erase (iterator i)
00086   { set.erase(const_cast<typename TSet::iterator>(i)); }
00087   void erase (const value_type&);
00088   void erase (iterator a, iterator b)
00089   { set.erase(const_cast<typename TSet::iterator>(a),const_cast<typename TSet::iterator>(b)); }
00090   void swap (range_set<T>& rhs) { set.swap(rhs.set); }
00091 
00092   // Set operations
00093 //  size_type count (const key_type& key) const { return set.count(key); }
00094 //  pair<iterator, iterator> equal_range (const  key_type&) const;
00095 //  iterator find (const key_value& key) const { return set.find(key); }
00096 //  iterator lower_bound (const key_type& key) const { return set.lower_bound(key); }
00097 //  iterator upper_bound (const key_type& key) const { return set.upper_bound(key); }
00098 };
00099 
00100 /*
00101 template <class T>
00102 std::pair<range_set<T>::iterator, bool> range_set<T>::insert (const value_type& value)
00103 {
00104   iterator i = lower_bound(value);
00105 
00106   // non trovato, inserisci
00107   if (i==end() || (*i).begin != value.begin)
00108   {
00109     return std::pair(set.insert(i,value),false);
00110   }
00111 
00112   // contenuto in quello corrente
00113   if ( value.end <= (*i.end) )
00114     return std::pair(i,true);
00115 
00116   //
00117 }
00118 */
00119 
00120 // ritorna se gia' inserito
00121 template <class T>
00122 bool range_set<T>::insert(const value_type& value)
00123 {
00124   // testa range invalido o vuoto
00125   if (value.begin >= value.end)
00126     return true;
00127 
00128   typename TSet::iterator i = std::lower_bound(set.begin(),set.end(),value,range_comp());
00129 
00130   // se fuori range inserisce e basta
00131   if (i==set.end() || value.end < (*i).begin)
00132   {
00133     set.insert(i,value);
00134     return false;
00135   }
00136 
00137   // estende inizio se necessario
00138   bool res = true;
00139   if (value.begin < (*i).begin)
00140   {
00141     (*i).begin = value.begin;
00142     res = false;
00143   }
00144 
00145   // estende fine se necessario
00146   if (value.end >= (*i).end)
00147   {
00148     // calcola fine range e range in eccesso
00149     T end = value.end;
00150     typename TSet::iterator ii = i;
00151     while(++ii != set.end())
00152     {
00153       if (end >=(*ii).begin && end<=(*ii).end)
00154         end = (*ii).end;
00155       if (end < (*ii).end)
00156         break;
00157     }
00158 
00159     // estendi range finale
00160     (*i).end = end;
00161 
00162     // cancella ranges in eccesso
00163     set.erase(++i,ii);
00164 
00165     // il range non era interamente presente
00166     return false;
00167   }
00168   return res;
00169 }
00170 
00171 template <class T>
00172 void range_set<T>::erase (const value_type& value)
00173 {
00174   // testa range invalido o vuoto
00175   if (value.begin >= value.end)
00176     return;
00177 
00178   typename TSet::iterator i = std::lower_bound(set.begin(),set.end(),value,range_comp());
00179 
00180   if (i==set.end())
00181     return;
00182 
00183   // se non interseca con nessuno esci
00184   if ( value.end <= (*i).begin )
00185     return;
00186 
00187   // tronca successivo
00188   if ( value.begin > (*i).begin )
00189   {
00190     // sdoppia range
00191     if ( value.end < (*i).end)
00192     {
00193       T begin = (*i).begin;
00194       (*i).begin = value.end;
00195       set.insert(i,value_type(begin,value.begin));
00196       return;
00197     }
00198     (*i).end = value.begin;
00199     ++i;
00200   }
00201 
00202   // cerca tutti i range che si devono togliere del tutto
00203   typename TSet::iterator ii = i;
00204   while( ii != set.end() && value.end >= (*ii).end )
00205     ++ii;
00206 
00207   // toglie parte in eccesso al range corrente
00208   if ( value.end >= (*ii).begin )
00209     (*ii).begin = value.end;
00210 
00211   // toglie ranges in eccesso
00212   set.erase(i,ii);
00213 }
00214 
00215 #endif //FILE_RANGE_HPP

Generated on Mon Jan 13 22:20:34 2003 for perdr by doxygen1.2.15