OKlibrary  0.2.1.6
Variables.hpp
Go to the documentation of this file.
00001 // Oliver Kullmann, 21.2.2003 (Swansea)
00002 /* Copyright 2003 - 2007, 2008 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00015 #ifndef VARIABLESWAECHTER_ahsd3549FG
00016 
00017 #define VARIABLESWAECHTER_ahsd3549FG
00018 
00019 #include <string>
00020 #include <map>
00021 #include <vector>
00022 #include <ostream>
00023 #include <limits>
00024 #include <cstddef>
00025 #include <algorithm>
00026 #include <cassert>
00027 #include <iterator>
00028 
00029 #include <boost/shared_ptr.hpp>
00030 #include <boost/static_assert.hpp>
00031 
00032 #include <OKlib/General/ErrorHandling.hpp>
00033 #include <OKlib/General/StringHandling.hpp>
00034 #include <OKlib/General/FunctionHandling.hpp>
00035 
00036 #include <OKlib/OKsolver/Experimental/AllgKlassen200203/Auxiliary.hpp>
00037 #include <OKlib/OKsolver/Experimental/AllgKlassen200203/Traits_General.hpp>
00038 #include <OKlib/OKsolver/Experimental/AllgKlassen200203/Concepts_Variables.hpp>
00039 #include <OKlib/OKsolver/Experimental/AllgKlassen200203/Traits_Variables.hpp>
00040 
00041 // Only temporary, to still compile the old implementations:
00042 #include <OKlib/OKsolver/Experimental/AllgKlassen200203/ConceptDefinitions.hpp>
00043 
00044 
00045 namespace Variables {
00046 
00047   // -----------------------------------------------------------------
00048   // Implementation of variables as integers
00049   // -----------------------------------------------------------------
00050 
00051   template <typename Int>
00052   class VariablesAsIntegers {
00053 
00054     BOOST_STATIC_ASSERT(std::numeric_limits<Int>::is_integer);
00055     BOOST_STATIC_ASSERT(std::numeric_limits<Int>::is_signed);
00056 
00057     Int v;
00058     template <typename, typename>
00059     friend class VariablesAsIntegers_DomainWithNameAdministration;
00060     template <typename>
00061     friend class Iterator_VariablesAsIntegers;
00062     explicit VariablesAsIntegers(Int i) : v(i) {
00063       assert(i >= 0);
00064     }
00065 
00066   public :
00067 
00068     VariablesAsIntegers() : v(0) {}
00069 
00070     friend inline bool operator ==(const VariablesAsIntegers lhs, const VariablesAsIntegers rhs) { return lhs.v == rhs.v; }
00071     friend inline bool operator <(const VariablesAsIntegers lhs, const VariablesAsIntegers rhs) { return lhs.v < rhs.v; }
00072  
00073     bool null() const { return v == 0; }
00074   };
00075 
00076   template <typename Int>
00077   inline bool operator !=(const VariablesAsIntegers<Int> lhs, const VariablesAsIntegers<Int> rhs) { return not (lhs == rhs); }
00078   template <typename Int>
00079   inline bool operator >(const VariablesAsIntegers<Int> lhs, const VariablesAsIntegers<Int> rhs) { return rhs < lhs; }
00080   template <typename Int>
00081   inline bool operator <=(const VariablesAsIntegers<Int> lhs, const VariablesAsIntegers<Int> rhs) { return lhs < rhs or lhs == rhs; }
00082   template <typename Int>
00083   inline bool operator >=(const VariablesAsIntegers<Int> lhs, const VariablesAsIntegers<Int> rhs) { return lhs > rhs or lhs == rhs; }
00084 
00085   // -----------------------------------------------------------------
00086   // Determining the domain of safe arithmetical negation
00087   // -----------------------------------------------------------------
00088 
00089   template <typename Int>
00090   Int signed_max() {
00091     const Int max = std::numeric_limits<Int>::max();
00092     const Int min = std::numeric_limits<Int>::min();
00093     return (min + max <= 0) ? max : - min;
00094   }
00095   // x of type Int can be safely negated iff
00096   // - signed_max() <= x <= signed_max().
00097 
00098   // -----------------------------------------------------------------
00099   // Associated iterator type
00100   // -----------------------------------------------------------------
00101 
00102   template <typename Int>
00103   class Iterator_VariablesAsIntegers {
00104     Int i;
00105     typedef VariablesAsIntegers<Int> Var;
00106     template <typename, typename>
00107     friend class VariablesAsIntegers_DomainWithNameAdministration;
00108     explicit Iterator_VariablesAsIntegers(Int i) : i(i) {}
00109 
00110   public :
00111     Iterator_VariablesAsIntegers() : i(0) {}
00112     Iterator_VariablesAsIntegers(Var v) : i(v.v) {}
00113     
00114     typedef Var value_type;
00115     typedef Var reference;
00116     typedef Var* pointer;
00117     typedef Int difference_type;
00118     typedef std::bidirectional_iterator_tag iterator_category;
00119 
00120     friend inline bool operator ==(Iterator_VariablesAsIntegers lhs, Iterator_VariablesAsIntegers rhs) { return lhs.i == rhs.i; }
00121 
00122     Var operator *() const { return Var(i); }
00123 
00124     Iterator_VariablesAsIntegers& operator ++() {
00125       assert(i < signed_max<Int>() - 1);
00126       ++i; return *this;
00127     }
00128     Iterator_VariablesAsIntegers operator ++(int) {
00129       assert(i < signed_max<Int>() - 1);
00130       const Iterator_VariablesAsIntegers j = *this; ++i; return j;
00131     }
00132     Iterator_VariablesAsIntegers& operator --() {
00133       assert(i > 0);
00134       --i; return *this;
00135     }
00136     Iterator_VariablesAsIntegers operator --(int) {
00137       assert(i > 0);
00138       const Iterator_VariablesAsIntegers j = *this; --i; return j;
00139     }
00140   };
00141 
00142   template <typename Int>
00143   inline bool operator !=(Iterator_VariablesAsIntegers<Int> lhs, Iterator_VariablesAsIntegers<Int> rhs) { return not (lhs == rhs); }
00144 
00145 
00146 }
00147 
00148 namespace Traits_General {
00149 
00150   template <typename Int>
00151   struct MetaData<Variables::VariablesAsIntegers<Int> > {
00152     typedef Concepts_Variables::Variable_tag concept_tag;
00153   };
00154 
00155 }
00156 
00157 
00158 namespace Traits_General {
00159   namespace Basis_VariablesAsIntegers_DomainWithNameAdministration {
00160     template <typename Int, typename Name>
00161     class Basis_Traits;
00162   }
00163 }
00164 
00165 namespace Variables {
00166 
00167   // -----------------------------------------------------------------
00168   // Signed size type template
00169   // -----------------------------------------------------------------
00170 
00171   template <typename Integer>
00172   class Size_type_signed {
00173     Integer x;
00174   public :
00175     Size_type_signed() : x(0) {}
00176 
00177     friend inline bool operator ==(Size_type_signed lhs, Size_type_signed rhs) { return lhs.x == rhs.x; }
00178     friend inline bool operator <(Size_type_signed lhs, Size_type_signed rhs) { return lhs.x < rhs.x; }
00179 
00180     friend inline Size_type_signed operator -(Size_type_signed lhs, Size_type_signed rhs) {
00181       assert(lhs >= Size_type_signed() and rhs >= Size_type_signed());
00182       if (rhs >= lhs) return Size_type_signed();
00183       else
00184   return Size_type_signed(lhs.x - rhs.x);
00185     }
00186 
00187   private :
00188 
00189     template <typename, class>
00190     friend class VariablesAsIntegers_DomainWithNameAdministration;
00191 
00192     explicit Size_type_signed(Integer x) : x(x) { assert(x >= 0); }
00193   };
00194 
00195   template <typename Integer>
00196   inline bool operator !=(Size_type_signed<Integer> lhs, Size_type_signed<Integer> rhs) {
00197     return not (lhs == rhs);
00198   }
00199   template <typename Integer>
00200   inline bool operator <=(Size_type_signed<Integer> lhs, Size_type_signed<Integer> rhs) {
00201     return lhs < rhs or lhs == rhs;
00202   }
00203   template <typename Integer>
00204   inline bool operator >(Size_type_signed<Integer> lhs, Size_type_signed<Integer> rhs) {
00205     return rhs < lhs;
00206   }
00207   template <typename Integer>
00208   inline bool operator >=(Size_type_signed<Integer> lhs, Size_type_signed<Integer> rhs) {
00209     return rhs < lhs or lhs == rhs;
00210   }
00211 
00212   // -----------------------------------------------------------------
00213   // Domain for variables as integers
00214   // -----------------------------------------------------------------
00215 
00216   template <typename Int, typename Name>
00217   class VariablesAsIntegers_DomainWithNameAdministration {
00218 
00219     BOOST_STATIC_ASSERT(std::numeric_limits<Int>::is_integer);
00220     BOOST_STATIC_ASSERT(std::numeric_limits<Int>::is_signed);
00221 
00222     friend class ::Traits_General::Basis_VariablesAsIntegers_DomainWithNameAdministration::Basis_Traits<Int, Name>;
00223 
00224     Int next; // the index of the next variable
00225 
00226     typedef Name name_type;
00227     typedef VariablesAsIntegers<Int> Var;
00228     typedef Size_type_signed<Int> size_type;
00229 
00230     static Int max() { return signed_max<Int>(); }
00231 
00232   public :
00233 
00234     VariablesAsIntegers_DomainWithNameAdministration() : next(1) {}
00235 
00236     Var operator()(const name_type& name) {
00237       return Var(insert(name));
00238     }
00239     const name_type& name(Var v) const {
00240       return na.hash_vector[v.v] -> first;
00241     }
00242 
00243     static size_type max_size() { return size_type(max()); }
00244     static size_type size_type_cast(unsigned int ui) {
00245       if (ui <= max())
00246   return size_type(Int(ui));
00247       else
00248   throw Error_Variables::CapacityOverflow("VariablesAsIntegers_DomainWithNameAdministration::size_type_cast : " + StringHandling::toString_nc(ui));
00249     }
00250     void reserve(size_type r) {
00251       if (r.x > na.name_map.max_size() or r.x > na.hash_vector.max_size())
00252   throw Error_Variables::CapacityOverflow("VariablesAsIntegers_DomainWithNameAdministration::reserve : " + StringHandling::toString_nc(r.x));
00253       else
00254   na.hash_vector.reserve(r.x);
00255     }
00256     size_type capacity() const {
00257       const typename HashVectorType::size_type c = na.hash_vector.capacity();
00258       if (c >= max())
00259   return max_size();
00260       else
00261   return size_type(Int(c));
00262     }
00263     void increase_capacity(size_type s) {
00264       if (s.x <= 0)
00265   return;
00266       if (s.x > max() or na.hash_vector.capacity() > max() - s.x)
00267   throw Error_Variables::CapacityOverflow("VariablesAsIntegers_DomainWithNameAdministration::increase_capacity : " + StringHandling::toString_nc(s.x));
00268       else
00269   reserve(size_type(Int(na.hash_vector.capacity()) + s.x));
00270     }
00271     size_type size() const {
00272       assert(next >= 1); return size_type(next);
00273     }
00274     size_type n() const {
00275       assert(next >= 1); return size_type(next-1);
00276     }
00277 
00278   public :
00279 
00280     typedef Iterator_VariablesAsIntegers<Int> iterator;
00281 
00282     iterator begin() const {
00283       return iterator(0);
00284     }
00285     iterator first() const {
00286       return iterator(1);
00287     }
00288     iterator end() const {
00289       return iterator(next);
00290     }
00291 
00292     iterator find(const name_type& name) const {
00293       const MapIterator i = na.name_map.find(name);
00294       if (i == na.name_map.end())
00295   return end();
00296       else
00297   return iterator(i -> second);
00298     }
00299 
00300   private :
00301     typedef typename std::map<name_type, Int> MapType;
00302     // given a name, get the index
00303     typedef typename MapType::const_iterator MapIterator;
00304     typedef typename std::vector<MapIterator> HashVectorType;
00305     // given an index, get the iterator to <name, index>
00306     
00307     struct NameAdmin {
00308       MapType name_map;
00309       HashVectorType hash_vector;
00310       NameAdmin() {
00311   create_null_var();
00312       }
00313     private :
00314       void create_null_var() {
00315   name_map.insert(std::make_pair(name_type(), 0));
00316   hash_vector.push_back(name_map.begin());
00317       }
00318     };
00319     
00320     NameAdmin na;
00321      
00322     Int insert(const name_type& name) {
00323       typename MapType::iterator i = na.name_map.lower_bound(name);
00324       if (i != na.name_map.end() and i -> first == name) // old
00325   return i -> second;
00326       else { // new
00327   if (next == max() - 1)
00328     throw Error_Variables::CapacityOverflow("VariablesAsIntegers_DomainWithNameAdministration::insert : " + StringHandling::toString_nc(next));
00329   {
00330     i = na.name_map.insert(i, std::make_pair(name, next));
00331     na.hash_vector.push_back(i);
00332     // not exception safe, if the insert succeeds, but not the push_back
00333   }
00334   return next++;
00335       }
00336       
00337     };
00338 
00339   };
00340 
00341 }
00342 
00343 namespace Traits_General {
00344 
00345   namespace Basis_VariablesAsIntegers_DomainWithNameAdministration {
00346     template <typename Int, class Name>
00347     struct Basis_Traits {
00348       typedef Concepts_Variables::VariableDomainWithIteratorAndAllocation_tag concept_tag;
00349       
00350       typedef Traits_Variables::ThrowsTotalCapacityOverflow overflow_throw_property;
00351       typedef Traits_Variables::NoInvalidNames invalid_name_throw_property;
00352       typedef Traits_Variables::LocalDomainsIdentified comparison_property;
00353       typedef Traits_Variables::SafeAllocation allocation_property;
00354       typedef Traits_Variables::GeneralNames name_property;
00355       typedef Traits_Variables::OrderByCreation order_property;
00356       typedef Traits_Variables::NaturalSize size_property;
00357 
00358       typedef Variables::VariablesAsIntegers_DomainWithNameAdministration<Int, Name> VarD;
00359       typedef typename VarD::name_type name_type;
00360       typedef typename VarD::Var Var;
00361       typedef typename VarD::size_type size_type;
00362       typedef typename VarD::iterator iterator;
00363     private :
00364       ~Basis_Traits();
00365     };
00366   }
00367   template <typename Int, class Name>
00368   struct MetaData<Variables::VariablesAsIntegers_DomainWithNameAdministration<Int, Name> > : Basis_VariablesAsIntegers_DomainWithNameAdministration::Basis_Traits<Int, Name> {
00369   private :
00370     ~MetaData();
00371   };
00372 
00373   template <typename Int>
00374   struct MetaData<Variables::VariablesAsIntegers_DomainWithNameAdministration<Int, std::string> > : Basis_VariablesAsIntegers_DomainWithNameAdministration::Basis_Traits<Int, std::string> {
00375     typedef Traits_Variables::StringConvertibleName name_property;
00376   private :
00377     ~MetaData();
00378   };
00379 
00380 }
00381 
00382 
00383 // --------------------------------------------------------------------
00384 // DEPRECATED :
00385 // --------------------------------------------------------------------
00386 
00387 namespace Literals {
00388   template <typename Index, template <typename> class InfoPolicyVar, template <typename> class InfoPolicyLit, typename Name>
00389   class LiteralsAsIntegers;
00390 }
00391 
00392 
00393 namespace Variables {
00394 
00395   struct Error_Variables : ErrorHandling::Error {
00396     Error_Variables(const std::string& what) : ErrorHandling::Error(what) {}
00397   };
00398 
00399   struct Overflow_Variables : Error_Variables {
00400     Overflow_Variables(const std::string& what) : Error_Variables(what) {}
00401   };
00402 
00403 }
00404 
00405 namespace Variables {
00406 
00407   template <class InfoPolicy, typename Name, class LiteralLink>
00408   class VariablesAsIndices : public InfoPolicy {
00409 
00410     BOOST_CLASS_REQUIRE(InfoPolicy, ConceptDefinitions, VariableIndexInfoPolicy_concept);
00411     BOOST_CLASS_REQUIRE(Name, boost, DefaultConstructibleConcept);
00412     BOOST_CLASS_REQUIRE(Name, ConceptDefinitions, OutputStreamableConcept);
00413 
00414     typedef typename InfoPolicy::Index Index;
00415     Index index;
00416     enum dummy { avoid_confusion };
00417     explicit VariablesAsIndices(Index i, dummy) : index(i) {}
00418 
00419   public :
00420 
00421     typedef typename InfoPolicy::DeliveredConcept Concept;
00422     typedef Name NameType;
00423 
00424     VariablesAsIndices() : index(0) {}
00425     explicit VariablesAsIndices(const NameType& name) : index(insert(name)) {}
00426     VariablesAsIndices(const VariablesAsIndices& v) : index(v.index) {}
00427 
00428     VariablesAsIndices& operator =(const VariablesAsIndices& v) {
00429       index = v.index;
00430       return *this;
00431     }
00432 
00433     friend inline bool operator ==(VariablesAsIndices lhs, VariablesAsIndices rhs) { return lhs.index == rhs.index; }
00434     friend inline bool operator !=(VariablesAsIndices lhs, VariablesAsIndices rhs) { return not (lhs == rhs); }
00435     friend inline bool operator <(VariablesAsIndices lhs, VariablesAsIndices rhs) { return lhs.index < rhs.index; }
00436     friend inline bool operator >(VariablesAsIndices lhs, VariablesAsIndices rhs) { return rhs < lhs; }
00437     friend inline bool operator <=(VariablesAsIndices lhs, VariablesAsIndices rhs) { return lhs < rhs or lhs == rhs; }
00438     friend inline bool operator >=(VariablesAsIndices lhs, VariablesAsIndices rhs) { return lhs > rhs or lhs == rhs; }
00439 
00440     bool null() const { return index == 0; }
00441 
00442     const NameType& name() const {
00443       return na.hash_vector[index] -> first;
00444     }
00445 
00446     friend inline std::ostream& operator <<(std::ostream& o, VariablesAsIndices v) {
00447       if (v.null())
00448   return o << Auxiliary::null_variable_tag;
00449       else
00450   return o << v.name();
00451     }
00452 
00453     static void clear() {
00454       na.clear();
00455       InfoPolicy::clear_info();
00456       LiteralLink::clear();
00457       N = 1;
00458       assert(na.name_map.size() == 1 and na.hash_vector.size() == 1 and size() == 1);
00459     }
00460 
00461     typedef Index size_type;
00462 
00463     static void reserve(size_type max) {
00464       na.hash_vector.reserve(max);
00465       reserve_info(max);
00466       LiteralLink::reserve(max);
00467     }
00468 
00469     static size_type capacity() {
00470       assert(na.hash_vector.capacity() >= 1 and LiteralLink::capacity() >= 1);
00471       return (na.hash_vector.capacity() < LiteralLink::capacity()) ? na.hash_vector.capacity() : LiteralLink::capacity();
00472     }
00473 
00474     static size_type size() {
00475       assert(N == na.hash_vector.size() and N == na.name_map.size());
00476       return N;
00477     }
00478     static size_type n() {
00479       assert(N == na.hash_vector.size() and N == na.name_map.size());
00480       return N-1;
00481     }
00482 
00483     typedef typename InfoPolicy::InfoValueType value_type;
00484     typedef typename InfoPolicy::InfoReferenceType reference;
00485     typedef typename InfoPolicy::InfoPointerType pointer;
00486     typedef size_type difference_type;
00487     typedef std::bidirectional_iterator_tag iterator_category;
00488 
00489     reference operator *() const {
00490       assert(index >= 0 and index < N);
00491       return get_info(index);
00492     }
00493     VariablesAsIndices& operator ++() {
00494       assert(index != N);
00495       ++index;
00496       return *this;
00497     }
00498     VariablesAsIndices operator ++(int) {
00499       assert(index != N);
00500       Index i = index;
00501       ++index;
00502       return VariablesAsIndices(i, avoid_confusion);
00503     }
00504     VariablesAsIndices& operator --() {
00505       assert(index != 0);
00506       --index;
00507       return *this;
00508     }
00509     VariablesAsIndices operator --(int) {
00510       assert(index != 0);
00511       Index i = index;
00512       --index;
00513       return VariablesAsIndices(i, avoid_confusion);
00514     }
00515 
00516     pointer operator ->() const {
00517       assert(index < N);
00518       return get_info_pointer(index);
00519     }
00520     
00521     static VariablesAsIndices begin() {
00522       return VariablesAsIndices(0, avoid_confusion);
00523     }
00524     static VariablesAsIndices end() {
00525       return VariablesAsIndices(N, avoid_confusion);
00526     }
00527 
00528     static VariablesAsIndices find(const NameType& name) {
00529       const MapIterator i = na.name_map.find(name);
00530       if (i == na.name_map.end())
00531   return end();
00532       else
00533   return VariablesAsIndices(i -> second, avoid_confusion);
00534     }
00535 
00536   private :
00537 
00538     typedef typename std::map< NameType, Index > MapType;
00539     // given a name, get the index
00540     typedef typename MapType::const_iterator MapIterator;
00541     typedef typename std::vector<MapIterator> HashVectorType;
00542     // given an index, get the iterator to <name, index>
00543 
00544     struct NameAdmin {
00545       MapType name_map;
00546       HashVectorType hash_vector;
00547       NameAdmin() {
00548   create_null_var();
00549       }
00550       void clear() {
00551   name_map.clear();
00552   hash_vector.clear();
00553   create_null_var();
00554       }
00555     private :
00556       void create_null_var() {
00557   name_map.insert(std::make_pair(NameType(), 0));
00558   hash_vector.push_back(name_map.begin());
00559       }
00560     };
00561 
00562     static NameAdmin na;
00563     static Index N;
00564 
00565     Index insert(const NameType& name) {
00566       typename MapType::iterator i = na.name_map.lower_bound(name);
00567       if (i != na.name_map.end() and i -> first == name) // old
00568   return i -> second;
00569       else { // new
00570   if (N == std::numeric_limits<Index>::max())
00571     throw Overflow_Variables("VariablesAsIndices::insert : " + StringHandling::toString_nc(N));
00572         InfoPolicy::new_info();
00573   {
00574     i = na.name_map.insert(i, std::make_pair(name, N));
00575     na.hash_vector.push_back(i);
00576     LiteralLink::new_variable();
00577   } // EXCEPTION SAFETY ??
00578   return N++;
00579       }
00580     }
00581 
00582     template <typename, template <typename> class, template <typename> class, typename>
00583     friend class Literals::LiteralsAsIntegers;
00584 
00585   };
00586   template <typename Info, typename NameType, typename LiteralLink>
00587   typename VariablesAsIndices<Info, NameType, LiteralLink>::NameAdmin VariablesAsIndices<Info, NameType, LiteralLink>::na;
00588 
00589   template <typename Info, typename NameType, typename LiteralLink>
00590   typename Info::Index VariablesAsIndices<Info, NameType, LiteralLink>::N(1);
00591 
00592 
00593   // -------------------
00594   // Info policy classes
00595   // -------------------
00596 
00597   template <typename InfoType, typename IndexType>
00598   class InfoPolicyIndexVector {
00599   public :
00600     typedef ConceptDefinitions::VariableIndexInfoPolicy_tag Concept;
00601   protected :
00602     typedef ConceptDefinitions::VariableWithInfo_tag DeliveredConcept;
00603     typedef InfoType InfoValueType;
00604     typedef InfoType& InfoReferenceType;
00605     typedef InfoType* InfoPointerType;
00606     typedef IndexType Index;
00607   private :
00608     typedef typename std::vector<InfoValueType> InfoVectorType;
00609     static InfoVectorType info_vector;
00610   protected :
00611     ~InfoPolicyIndexVector() {}
00612     static void new_info() {
00613       info_vector.push_back(InfoValueType());
00614     }
00615     static void reserve_info(Index max) {
00616       info_vector.reserve(max);
00617     }
00618     static InfoReferenceType get_info(Index i) {
00619       return info_vector[i];
00620     }
00621     static InfoPointerType get_info_pointer(Index i) {
00622       return &info_vector[i];
00623     }
00624     static void clear_info() {
00625       info_vector.clear();
00626       new_info();
00627     }
00628   };
00629   template <typename Info, typename Index>
00630   typename InfoPolicyIndexVector<Info,Index>::InfoVectorType InfoPolicyIndexVector<Info,Index>::info_vector(1, Info());
00631 
00632   template <typename IndexType>
00633   class InfoPolicyEmpty {
00634   public :
00635     typedef ConceptDefinitions::VariableIndexInfoPolicy_tag Concept;
00636   protected :
00637     typedef ConceptDefinitions::VariableWithCounting_tag DeliveredConcept;
00638     typedef IndexType Index;
00639     ~InfoPolicyEmpty() {}
00640     static void new_info() {}
00641     static void reserve_info(Index max) {}
00642     class Dummy {};
00643     typedef Dummy InfoReferenceType;
00644     typedef Dummy InfoValueType;
00645     typedef Dummy InfoPointerType;
00646     // get_info not implemented
00647     static void clear_info() {}
00648   };
00649 
00650   // Policy class in case, literals don't provide info containers
00651   template <typename Index>
00652   struct EmptyLiteralLink {
00653     static void new_variable() {}
00654     static void reserve(Index max) {}
00655     static Index capacity(){ return std::numeric_limits<Index>::max(); }
00656     static void clear() {}
00657   };
00658 
00659 }
00660 
00661 namespace Variables {
00662 
00663   // -----------------------------------------------------------------
00664   // Implementation of variables as names
00665   // -----------------------------------------------------------------
00666   
00667   template <class Name>
00668   class VariablesAsNames {
00669 
00670     BOOST_CLASS_REQUIRE(Name, ConceptDefinitions, FullyConstructibleConcept);
00671     BOOST_CLASS_REQUIRE(Name, ConceptDefinitions, TotalOrderComparableConcept);
00672     BOOST_CLASS_REQUIRE(Name, ConceptDefinitions, OutputStreamableConcept);
00673 
00674     Name name_;
00675 
00676   public :
00677 
00678     typedef typename ConceptDefinitions::Variable_tag Concept;
00679     typedef Name NameType;
00680 
00681     VariablesAsNames() {}
00682     VariablesAsNames(const NameType& name) : name_(name) {}
00683     VariablesAsNames(const VariablesAsNames& v) : name_(v.name_) {}
00684 
00685     VariablesAsNames& operator =(const VariablesAsNames& v) {
00686       name_ = v.name_;
00687       return *this;
00688     }
00689     
00690     friend inline bool operator ==(VariablesAsNames lhs, VariablesAsNames rhs) { return lhs.name_ == rhs.name_; }
00691     friend inline bool operator !=(VariablesAsNames lhs, VariablesAsNames rhs) { return not (lhs == rhs); }
00692     friend inline bool operator <(VariablesAsNames lhs, VariablesAsNames rhs) { return lhs.name_ < rhs.name_; }
00693     friend inline bool operator >(VariablesAsNames lhs, VariablesAsNames rhs) { return rhs < lhs; }
00694     friend inline bool operator <=(VariablesAsNames lhs, VariablesAsNames rhs) { return lhs < rhs or lhs == rhs; }
00695     friend inline bool operator >=(VariablesAsNames lhs, VariablesAsNames rhs) { return lhs > rhs or lhs == rhs; }
00696 
00697     static void clear() {}
00698     bool null() const { return name_ == NameType(); }
00699     const NameType& name() const { return name_; }
00700     
00701     friend inline std::ostream& operator <<(std::ostream& o, VariablesAsNames v) {
00702       if (v.null())
00703   return o << Auxiliary::null_variable_tag;
00704       else
00705   return o << v.name();
00706     }
00707   };
00708   
00709 }
00710 
00711 namespace Variables {
00712 
00713   // -----------------------------------------------------------------
00714   // Implementation of variables via a global list of indexed names
00715   // -----------------------------------------------------------------
00716 
00717   template <class Name, typename Index>
00718   class VariablesViaReferenceCounting {
00719 
00720     BOOST_CLASS_REQUIRE(Name, ConceptDefinitions, FullyConstructibleConcept);
00721     BOOST_CLASS_REQUIRE(Name, ConceptDefinitions, OutputStreamableConcept);
00722 
00723     typedef typename FunctionHandling::Counter<Index> CounterType;
00724     static CounterType count;
00725     typedef typename CounterType::IndexType IndexType;
00726 
00727     struct Var_rep {
00728       const IndexType c;
00729       const Name n;
00730       explicit Var_rep(Name n) : c(count()), n(n) {
00731   if (c ==  std::numeric_limits<IndexType>::max())
00732     throw Overflow_Variables("VariablesViaReferenceCounting::Var_rep() : " + StringHandling::toString_nc(c));
00733       }
00734     };
00735 
00736     typedef typename boost::shared_ptr<Var_rep> Pointer;
00737     Pointer vp;
00738 
00739   public :
00740 
00741     typedef typename ConceptDefinitions::VariableWithHistory_tag Concept;
00742     typedef Name NameType;
00743 
00744     VariablesViaReferenceCounting() {}
00745     explicit VariablesViaReferenceCounting(const NameType& name) {
00746       if (name != Name()) {
00747   const Pointer p(new Var_rep(name));
00748   vp = p;
00749       }
00750     }
00751     VariablesViaReferenceCounting(const VariablesViaReferenceCounting& v) : vp(v.vp) {}
00752 
00753     VariablesViaReferenceCounting& operator =(const VariablesViaReferenceCounting& var) {
00754       vp = var.vp;
00755       return *this;
00756     }
00757 
00758     friend inline bool operator ==(VariablesViaReferenceCounting lhs, VariablesViaReferenceCounting rhs) { return (lhs.null() and rhs.null()) or (not lhs.null() and not rhs.null() and (lhs.vp -> c == rhs.vp -> c or lhs.vp -> n == rhs.vp -> n)); }
00759     friend inline bool operator !=(VariablesViaReferenceCounting lhs, VariablesViaReferenceCounting rhs) { return not (lhs == rhs); }
00760     friend inline bool operator <(VariablesViaReferenceCounting lhs, VariablesViaReferenceCounting rhs) { return not rhs.null() and (lhs.null() or lhs.vp -> c < rhs.vp -> c); }
00761     friend inline bool operator >(VariablesViaReferenceCounting lhs, VariablesViaReferenceCounting rhs) { return rhs < lhs; }
00762     friend inline bool operator <=(VariablesViaReferenceCounting lhs, VariablesViaReferenceCounting rhs) { return lhs < rhs or lhs == rhs; }
00763     friend inline bool operator >=(VariablesViaReferenceCounting lhs, VariablesViaReferenceCounting rhs) { return lhs > rhs or lhs == rhs; }
00764 
00765     bool null() const { return vp == Pointer(); }
00766 
00767     const NameType& name() const {
00768       if (null())
00769   return NameType();
00770       else
00771   return vp -> n;
00772     }
00773 
00774     friend inline std::ostream& operator <<(std::ostream& o, VariablesViaReferenceCounting v) {
00775       if (v.null())
00776   return o << Auxiliary::null_variable_tag;
00777       else
00778   return o << v.name();
00779     }
00780 
00781     static void clear() {}
00782 
00783   };
00784   template <class Name, typename Index>
00785   FunctionHandling::Counter<Index> VariablesViaReferenceCounting<Name,Index>::count;
00786 }
00787 
00788 namespace Variables {
00789 
00790   // -----------------------------------------------------------------
00791   // Implementation of literals and variables as pointers
00792   // -----------------------------------------------------------------
00793   // NEEDS A COMPLETE MAKE UP
00794 
00795   template <class InfoPolicy, typename Name, class LiteralLink>
00796   class VariablesAsPointers : public InfoPolicy {
00797   public :
00798 
00799     typedef Name NameType;
00800     typedef std::ptrdiff_t size_type;
00801 
00802     VariablesAsPointers() : p(InfoPolicy::start()) {};
00803 
00804     explicit VariablesAsPointers(const NameType& name) : p(insert(name)) {}
00805  
00806     VariablesAsPointers(const VariablesAsPointers& v) : p(v.p) {}
00807 
00808     VariablesAsPointers& operator =(const VariablesAsPointers& v) {
00809       p = v.p;
00810     }
00811 
00812     bool operator ==(VariablesAsPointers v) const {
00813       return p == v.p;
00814     }
00815     bool operator !=(VariablesAsPointers v) const {
00816       return not operator ==(v);
00817     }
00818     bool operator <(VariablesAsPointers v) const {
00819       return p < v.p;
00820     }
00821 
00822     operator bool() const { return p != InfoPolicy::start(); }
00823 
00824     static void reserve(typename InfoPolicy::size_type max) {
00825       hash_vector.reserve(max);
00826       reserve_info(max);
00827       LiteralLink::reserve(max);
00828     }
00829 
00830     static typename InfoPolicy::size_type n() { return InfoPolicy::size(); }
00831 
00832      friend std::ostream& operator <<(std::ostream& o, VariablesAsPointers v) {
00833       if (v)
00834   return o << hash_vector[v.p - InfoPolicy::start()] -> first;
00835       else
00836   return o << "UNDEF";
00837     }
00838 
00839     typename InfoPolicy::InfoReferenceType operator *() const {
00840       return get_info(p);
00841     }
00842 
00843   private :
00844 
00845     typedef typename InfoPolicy::InfoPointerType PointerType;
00846     PointerType p;
00847 
00848     typedef typename std::map< NameType, PointerType > MapType;
00849     typedef typename MapType::const_iterator MapIterator;
00850 
00851     static MapType name_map;
00852 
00853     PointerType insert(const NameType& name) {
00854       const std::pair<MapIterator, bool> ins = name_map.insert(std::make_pair(name, 0));
00855       if (ins.second) { // new
00856   const PointerType p = InfoPolicy::new_info();
00857   hash_vector.push_back(ins.first);
00858   LiteralLink::new_variable(p);
00859   return p;
00860       }
00861       else // old
00862   return ins.first -> second;
00863     }
00864 
00865     typedef typename std::vector<MapIterator> HashVectorType;
00866     static HashVectorType hash_vector;
00867   };
00868   template <typename Info, typename NameType, typename LiteralLink>
00869   typename VariablesAsPointers<Info, NameType, LiteralLink>::MapType VariablesAsPointers<Info, NameType, LiteralLink>::name_map;
00870 
00871   template <typename Info, typename NameType, typename LiteralLink>
00872   typename VariablesAsPointers<Info, NameType, LiteralLink>::HashVectorType VariablesAsPointers<Info, NameType, LiteralLink>::hash_vector(1, MapIterator());
00873 
00874   // -------------------
00875   // Info policy classes
00876   // -------------------
00877   
00878   template <typename Info>
00879   class InfoPolicyPointerVector {
00880   public :
00881     typedef Info InfoValueType;
00882     typedef Info& InfoReferenceType;
00883     typedef Info* InfoPointerType;
00884   private :
00885     typedef typename std::vector<Info> InfoVectorType;
00886     static InfoVectorType info_vector;
00887   public :
00888     typedef typename InfoVectorType::size_type size_type;
00889   protected :
00890     ~InfoPolicyPointerVector() {}
00891      InfoPointerType new_info() const {
00892       info_vector.push_back(Info());
00893       return info_vector.end() - 1;
00894     }
00895     void reserve_info(size_type max) const {
00896       info_vector.reserve(max + 1);
00897     }
00898     Info& get_info(Info* p) const {
00899       return *p;
00900     }
00901 
00902     Info* start() const {
00903       return &info_vector[0];
00904     }
00905   };
00906   template <typename Info>
00907   typename InfoPolicyPointerVector<Info>::InfoVectorType InfoPolicyPointerVector<Info>::info_vector(1, Info());
00908 
00909 }
00910 
00911 namespace Variables {
00912 
00913   // -----------------------------------------------------------------
00914   // Typedefs for testing
00915   // -----------------------------------------------------------------
00916 
00917   struct Occurrences {
00918     int occ;
00919     Occurrences() : occ(0) {}
00920     Occurrences(int o) : occ(o) {}
00921   };
00922   
00923   template <typename Index>
00924   class InfoPolicyIndexVectorOccurrences : public InfoPolicyIndexVector<Occurrences,Index> {};
00925 
00926   typedef VariablesAsIndices<InfoPolicyIndexVectorOccurrences<int>, std::string, EmptyLiteralLink<int> > VarIntOccString;
00927   typedef VariablesAsIndices<InfoPolicyIndexVector<Occurrences,signed char>, int, EmptyLiteralLink<signed char> > VarCharOccInt;
00928 
00929   typedef VariablesAsIndices<InfoPolicyEmpty<int>, std::string, EmptyLiteralLink<int> > VarIntEmptyString;
00930 
00931   typedef VariablesViaReferenceCounting<std::string, unsigned int> VarRefIntString;
00932   typedef VariablesViaReferenceCounting<int, signed char> VarRefCharInt;
00933   
00934 }
00935 
00936 #endif