sparse_interval.hxx

00001 // sparse_interval.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 The Vaucanson Group.
00006 //
00007 // This program is free software; you can redistribute it and/or
00008 // modify it under the terms of the GNU General Public License
00009 // as published by the Free Software Foundation; either version 2
00010 // of the License, or (at your option) any later version.
00011 //
00012 // The complete GNU General Public Licence Notice can be found as the
00013 // `COPYING' file in the root directory.
00014 //
00015 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
00016 //
00017 #ifndef VCSN_MISC_SPARSE_INTERVAL_HXX
00018 # define VCSN_MISC_SPARSE_INTERVAL_HXX
00019 
00020 # include <vaucanson/misc/sparse_interval.hh>
00021 # include <vaucanson/misc/contract.hh>
00022 # include <sstream>
00023 
00024 namespace vcsn
00025 {
00026   namespace misc
00027   {
00028   /*---------------.
00029   | SparseIterator |
00030   `---------------*/
00031 
00032     template <class Integer, class ExcludedContainer>
00033     SparseIterator<Integer, ExcludedContainer>::
00034     SparseIterator (integer_t from,
00035                     const excluded_container_t& c)
00036       : excluded_ (&c),
00037         integer_ (from)
00038     {}
00039 
00040     template <class Integer, class ExcludedContainer>
00041     SparseIterator<Integer, ExcludedContainer>&
00042     SparseIterator<Integer, ExcludedContainer>::operator++ ()
00043     {
00044       if (excluded_->size () == 0)
00045         integer_ = integer_ + 1;
00046       else
00047         do
00048           integer_ = integer_ + 1;
00049         while (excluded_->find (integer_) != excluded_->end ());
00050       return *this;
00051     }
00052 
00053     template <class Integer, class ExcludedContainer>
00054     SparseIterator<Integer, ExcludedContainer>&
00055     SparseIterator<Integer, ExcludedContainer>::operator-- ()
00056     {
00057       if (excluded_->size () == 0)
00058         integer_ = integer_ - 1;
00059       else
00060         do
00061           integer_ = integer_ - 1;
00062         while (excluded_->find (integer_) != excluded_->end ());
00063       return *this;
00064     }
00065 
00066     template <class Integer, class ExcludedContainer>
00067     SparseIterator<Integer, ExcludedContainer>
00068     SparseIterator<Integer, ExcludedContainer>::operator++ (int)
00069     {
00070       SparseIterator tmp = *this;
00071       ++*this;
00072       return tmp;
00073     }
00074 
00075     template <class Integer, class ExcludedContainer>
00076     SparseIterator<Integer, ExcludedContainer>
00077     SparseIterator<Integer, ExcludedContainer>::operator-- (int)
00078     {
00079       SparseIterator tmp = *this;
00080       --*this;
00081       return tmp;
00082     }
00083 
00084     template <class Integer, class ExcludedContainer>
00085     typename SparseIterator<Integer, ExcludedContainer>::
00086     integer_t
00087     SparseIterator<Integer, ExcludedContainer>::operator* ()
00088     {
00089       return integer_;
00090     }
00091 
00092     template <class Integer, class ExcludedContainer>
00093     bool
00094     SparseIterator<Integer, ExcludedContainer>
00095     ::operator!= (const SparseIterator& i)
00096     {
00097       return i.integer_ != integer_;
00098     }
00099 
00100     template <class Integer, class ExcludedContainer>
00101     bool
00102     SparseIterator<Integer, ExcludedContainer>
00103     ::operator== (const SparseIterator& i)
00104     {
00105       return i.integer_ == integer_;
00106     }
00107 
00108     template <class Integer, class ExcludedContainer>
00109     SparseIterator<Integer, ExcludedContainer>&
00110     SparseIterator<Integer, ExcludedContainer>
00111     ::operator= (const SparseIterator& i)
00112     {
00113       integer_ = i.integer_;
00114       excluded_ = i.excluded_;
00115       return *this;
00116     }
00117 
00118 
00119 
00120 
00121   /*-----------------.
00122   | SparseInterval.  |
00123   `-----------------*/
00124 
00125 
00129     template <class Integer, class ExcludedContainer>
00130     SparseInterval<Integer, ExcludedContainer>
00131     ::SparseInterval (integer_t f, integer_t t, const excluded_container_t& c)
00132       : excluded_ (c),
00133         from_ (f),
00134         to_ (t)
00135     {
00136       precondition (from_ <= to_ + 1);
00137       precondition (excluded_.find (to_ + 1) == excluded_.end ());
00138     }
00139 
00140     template <class Integer, class ExcludedContainer>
00141     SparseInterval<Integer, ExcludedContainer>
00142     ::SparseInterval (const SparseInterval& a)
00143       : excluded_ (a.excluded_),
00144         from_ (a.from_),
00145         to_ (a.to_)
00146     {
00147     }
00148 
00149     template <class Integer, class ExcludedContainer>
00150     unsigned
00151     SparseInterval<Integer, ExcludedContainer>::size () const
00152     {
00153       return to_ < from_ ? 0 : to_ - from_ + 1 - excluded_.size ();
00154     }
00155 
00156     template <class Integer, class ExcludedContainer>
00157     typename SparseInterval<Integer, ExcludedContainer>::integer_t
00158     SparseInterval<Integer, ExcludedContainer>::max () const
00159     {
00160       unsigned r = to_;
00161 
00162       while (excluded_.find (r) != excluded_.end ())
00163         --r;
00164       return r;
00165     }
00166 
00167     template <class Integer, class ExcludedContainer>
00168     std::string
00169     SparseInterval<Integer, ExcludedContainer>::to_string () const
00170     {
00171       std::stringstream s;
00172       s << "from :" << from_ << " to : " << to_ << " ex:";
00173       for (typename ExcludedContainer::iterator i = excluded_.begin ();
00174            i != excluded_.end ();
00175            ++i)
00176         s << *i << " ";
00177       return s.str ();
00178     }
00179 
00180     template <class Integer, class ExcludedContainer>
00181     typename SparseInterval<Integer, ExcludedContainer>::iterator
00182     SparseInterval<Integer, ExcludedContainer>::begin () const
00183     {
00184       int from = from_;
00185 
00186       if (excluded_.size () != 0)
00187         while (excluded_.find (from) != excluded_.end ())
00188           from = from + 1;
00189       return iterator (from, excluded_);
00190     }
00191 
00192     template <class Integer, class ExcludedContainer>
00193     typename SparseInterval<Integer, ExcludedContainer>::iterator
00194     SparseInterval<Integer, ExcludedContainer>::end () const
00195     {
00196       return iterator (to_ + 1, excluded_);
00197     }
00198 
00199   } // misc
00200 } // vcsn
00201 
00202 #endif // ! VCSN_MISC_SPARSE_INTERVAL_HXX

Generated on Sun Jul 29 19:35:29 2007 for Vaucanson by  doxygen 1.5.2