LEMON/LEMON-official Changeset - r39:0a01d811071f

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r39:0a01d811071f

« 38:a0cd99

40:8f4e82 »

r39:0a01d811071f

Mon, 07 Jan 2008 14:16:06

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Happy New Year (update the copyright headers)

0 17 0

default

17 files changed with 34 insertions and 16 deletions:

lemon/base.cc

lemon/bits/invalid.h

lemon/bits/utility.h

lemon/concept_check.h

lemon/concepts/maps.h

lemon/dim2.h

lemon/list_graph.h

lemon/maps.h

lemon/random.cc

lemon/random.h

lemon/tolerance.h

test/dim_test.cc

test/maps_test.cc

test/random_test.cc

test/test_tools.h

test/test_tools_fail.cc

test/test_tools_pass.cc

↑ Collapse diff ↑

lemon/base.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		///\file
 		///\brief Some basic non inline function and static global data.
 		#include<lemon/tolerance.h>
 		#include<lemon/bits/invalid.h>
 		namespace lemon {
 		  float Tolerance<float>::def_epsilon = 1e-4;
 		  double Tolerance<double>::def_epsilon = 1e-10;
 		  long double Tolerance<long double>::def_epsilon = 1e-14;
 		#ifndef LEMON_ONLY_TEMPLATES
 		  const Invalid INVALID = Invalid();
 		#endif
 		} //namespace lemon

lemon/bits/invalid.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_INVALID_H
 		#define LEMON_BITS_INVALID_H
 		///\file
 		///\brief Definition of INVALID.
 		namespace lemon {
 		  /// \brief Dummy type to make it easier to create invalid iterators.
 		  ///
 		  /// See \ref INVALID for the usage.
 		  struct Invalid {
 		  public:
 		    bool operator==(Invalid) { return true;  }
 		    bool operator!=(Invalid) { return false; }
 		    bool operator< (Invalid) { return false; }
 		  };
 		  /// \brief Invalid iterators.
 		  ///
 		  /// \ref Invalid is a global type that converts to each iterator
 		  /// in such a way that the value of the target iterator will be invalid.
 		  //Some people didn't like this:
 		  //const Invalid &INVALID = *(Invalid *)0;
 		#ifdef LEMON_ONLY_TEMPLATES
 		  const Invalid INVALID = Invalid();
 		#else
 		  extern const Invalid INVALID;
 		#endif
 		} //namespace lemon
 		#endif

lemon/bits/utility.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		// This file contains a modified version of the enable_if library from BOOST.
 		// See the appropriate copyright notice below.
 		// Boost enable_if library
 		// Copyright 2003 � The Trustees of Indiana University.
 		// Use, modification, and distribution is subject to the Boost Software
 		// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
 		// http://www.boost.org/LICENSE_1_0.txt)
 		//    Authors: Jaakko J�rvi (jajarvi at osl.iu.edu)
 		//             Jeremiah Willcock (jewillco at osl.iu.edu)
 		//             Andrew Lumsdaine (lums at osl.iu.edu)
 		#ifndef LEMON_BITS_UTILITY_H
 		#define LEMON_BITS_UTILITY_H
 		///\file
 		///\brief Miscellaneous basic utilities
 		///
 		///\todo Please rethink the organisation of the basic files like this.
 		///E.g. this file might be merged with invalid.h.
 		namespace lemon
+		{
 		  /// Basic type for defining "tags". A "YES" condition for \c enable_if.
 		  /// Basic type for defining "tags". A "YES" condition for \c enable_if.
 		  ///
 		  ///\sa False
 		  ///
 		  /// \todo This should go to a separate "basic_types.h" (or something)
 		  /// file.
 		  struct True {
 		    ///\e
 		    static const bool value = true;
 		  };
 		  /// Basic type for defining "tags". A "NO" condition for \c enable_if.
 		  /// Basic type for defining "tags". A "NO" condition for \c enable_if.
 		  ///
 		  ///\sa True
 		  struct False {
 		    ///\e
 		    static const bool value = false;
 		  };
 		  struct InvalidType {
 		  };
 		  template <typename T>
 		  struct Wrap {
 		    const T &value;
 		    Wrap(const T &t) : value(t) {}
 		  };
 		  /**************** dummy class to avoid ambiguity ****************/
 		  template<int T> struct dummy { dummy(int) {} };
 		  /**************** enable_if from BOOST ****************/
 		  template <typename Type, typename T = void>
 		  struct exists {
 		    typedef T type;
 		  };
 		  template <bool B, class T = void>
 		  struct enable_if_c {
 		    typedef T type;
 		  };
 		  template <class T>
 		  struct enable_if_c<false, T> {};
 		  template <class Cond, class T = void>
 		  struct enable_if : public enable_if_c<Cond::value, T> {};
 		  template <bool B, class T>
 		  struct lazy_enable_if_c {
 		    typedef typename T::type type;
 		  };
 		  template <class T>
 		  struct lazy_enable_if_c<false, T> {};
 		  template <class Cond, class T>
 		  struct lazy_enable_if : public lazy_enable_if_c<Cond::value, T> {};
 		  template <bool B, class T = void>
 		  struct disable_if_c {
 		    typedef T type;
 		  };
 		  template <class T>
 		  struct disable_if_c<true, T> {};
 		  template <class Cond, class T = void>
 		  struct disable_if : public disable_if_c<Cond::value, T> {};
 		  template <bool B, class T>
 		  struct lazy_disable_if_c {
 		    typedef typename T::type type;
 		  };
 		  template <class T>
 		  struct lazy_disable_if_c<true, T> {};
 		  template <class Cond, class T>
 		  struct lazy_disable_if : public lazy_disable_if_c<Cond::value, T> {};
 		} // namespace lemon
 		#endif

lemon/concept_check.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		// This file contains a modified version of the concept checking
 		// utility from BOOST.
 		// See the appropriate copyright notice below.
 		// (C) Copyright Jeremy Siek 2000.
 		// Distributed under the Boost Software License, Version 1.0. (See
 		// accompanying file LICENSE_1_0.txt or copy at
 		// http://www.boost.org/LICENSE_1_0.txt)
 		//
 		// Revision History:
 		//   05 May   2001: Workarounds for HP aCC from Thomas Matelich. (Jeremy Siek)
 		//   02 April 2001: Removed limits header altogether. (Jeremy Siek)
 		//   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
 		//
 		// See http://www.boost.org/libs/concept_check for documentation.
 		#ifndef LEMON_CONCEPT_CHECKS_H
 		#define LEMON_CONCEPT_CHECKS_H
 		namespace lemon {
 		  /*
 		    "inline" is used for ignore_unused_variable_warning()
 		    and function_requires() to make sure there is no
 		    overtarget with g++.
 		  */
 		  template <class T> inline void ignore_unused_variable_warning(const T&) { }
 		  template <class Concept>
 		  inline void function_requires()
+		  {
 		#if !defined(NDEBUG)
 		    void (Concept::*x)() = & Concept::constraints;
 		    ignore_unused_variable_warning(x);
 		#endif
+		  }
 		  template <typename Concept, typename Type>
 		  inline void checkConcept() {
 		#if !defined(NDEBUG)
 		    typedef typename Concept::template Constraints<Type> ConceptCheck;
 		    void (ConceptCheck::*x)() = & ConceptCheck::constraints;
 		    ignore_unused_variable_warning(x);
 		#endif
+		  }
 		#define BOOST_CLASS_REQUIRE(type_var, ns, concept) \
 		  typedef void (ns::concept <type_var>::* func##type_var##concept)(); \
 		  template <func##type_var##concept Tp1_> \
 		  struct concept_checking_##type_var##concept { }; \
 		  typedef concept_checking_##type_var##concept< \
 		    BOOST_FPTR ns::concept<type_var>::constraints> \
 		    concept_checking_typedef_##type_var##concept
 		#define BOOST_CLASS_REQUIRE2(type_var1, type_var2, ns, concept) \
 		  typedef void (ns::concept <type_var1,type_var2>::* \
 		     func##type_var1##type_var2##concept)(); \
 		  template <func##type_var1##type_var2##concept Tp1_> \
 		  struct concept_checking_##type_var1##type_var2##concept { }; \
 		  typedef concept_checking_##type_var1##type_var2##concept< \
 		    BOOST_FPTR ns::concept<type_var1,type_var2>::constraints> \
 		    concept_checking_typedef_##type_var1##type_var2##concept
 		#define BOOST_CLASS_REQUIRE3(tv1, tv2, tv3, ns, concept) \
 		  typedef void (ns::concept <tv1,tv2,tv3>::* \
 		     func##tv1##tv2##tv3##concept)(); \
 		  template <func##tv1##tv2##tv3##concept Tp1_> \
 		  struct concept_checking_##tv1##tv2##tv3##concept { }; \
 		  typedef concept_checking_##tv1##tv2##tv3##concept< \
 		    BOOST_FPTR ns::concept<tv1,tv2,tv3>::constraints> \
 		    concept_checking_typedef_##tv1##tv2##tv3##concept
 		#define BOOST_CLASS_REQUIRE4(tv1, tv2, tv3, tv4, ns, concept) \
 		  typedef void (ns::concept <tv1,tv2,tv3,tv4>::* \
 		     func##tv1##tv2##tv3##tv4##concept)(); \
 		  template <func##tv1##tv2##tv3##tv4##concept Tp1_> \
 		  struct concept_checking_##tv1##tv2##tv3##tv4##concept { }; \
 		  typedef concept_checking_##tv1##tv2##tv3##tv4##concept< \
 		    BOOST_FPTR ns::concept<tv1,tv2,tv3,tv4>::constraints> \
 		    concept_checking_typedef_##tv1##tv2##tv3##tv4##concept
 		} // namespace lemon
 		#endif // LEMON_CONCEPT_CHECKS_H

lemon/concepts/maps.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_CONCEPT_MAPS_H
 		#define LEMON_CONCEPT_MAPS_H
 		#include <lemon/bits/utility.h>
 		#include <lemon/concept_check.h>
 		///\ingroup concept
 		///\file
 		///\brief Map concepts checking classes for testing and documenting.
 		namespace lemon {
 		  namespace concepts {
 		    /// \addtogroup concept
 		    /// @{
 		    /// Readable map concept
 		    /// Readable map concept.
 		    ///
 		    template<typename K, typename T>
 		    class ReadMap
+		    {
 		    public:
 		      /// The key type of the map.
 		      typedef K Key;
 		      /// The value type of the map. (The type of objects associated with the keys).
 		      typedef T Value;
 		      /// Returns the value associated with a key.
 		      /// \bug Value shouldn't need to be default constructible.
 		      ///
 		      Value operator[](const Key &) const {return Value();}
 		      template<typename _ReadMap>
 		      struct Constraints {
 			void constraints() {
 			  Value val = m[key];
 			  val = m[key];
 			  typename _ReadMap::Value own_val = m[own_key];
 			  own_val = m[own_key];
 			  ignore_unused_variable_warning(val);
 			  ignore_unused_variable_warning(own_val);
 			  ignore_unused_variable_warning(key);
+			}
 			Key& key;
 			typename _ReadMap::Key& own_key;
 			_ReadMap& m;
 		      };
 		    };
 		    /// Writable map concept
 		    /// Writable map concept.
 		    ///
 		    template<typename K, typename T>
 		    class WriteMap
+		    {
 		    public:
 		      /// The key type of the map.
 		      typedef K Key;
 		      /// The value type of the map. (The type of objects associated with the keys).
 		      typedef T Value;
 		      /// Sets the value associated with a key.
 		      void set(const Key &,const Value &) {}
 		      ///Default constructor
 		      WriteMap() {}
 		      template <typename _WriteMap>
 		      struct Constraints {
 			void constraints() {
 			  // No constraints for constructor.
 			  m.set(key, val);
 			  m.set(own_key, own_val);
 			  ignore_unused_variable_warning(key);
 			  ignore_unused_variable_warning(val);
 			  ignore_unused_variable_warning(own_key);
 			  ignore_unused_variable_warning(own_val);
+			}
 			Value& val;
 			typename _WriteMap::Value own_val;
 			Key& key;
 			typename _WriteMap::Key& own_key;
 			_WriteMap& m;
 		      };
 		    };
 		    /// Read/Writable map concept
 		    /// Read/writable map concept.
 		    ///
 		    template<typename K, typename T>
 		    class ReadWriteMap : public ReadMap<K,T>,
 					 public WriteMap<K,T>
+		    {
 		    public:
 		      /// The key type of the map.
 		      typedef K Key;
 		      /// The value type of the map. (The type of objects associated with the keys).
 		      typedef T Value;
 		      /// Returns the value associated with a key.
 		      Value operator[](const Key &) const {return Value();}
 		      /// Sets the value associated with a key.
 		      void set(const Key & ,const Value &) {}
 		      template<typename _ReadWriteMap>
 		      struct Constraints {
 			void constraints() {
 			  checkConcept<ReadMap<K, T>, _ReadWriteMap >();
 			  checkConcept<WriteMap<K, T>, _ReadWriteMap >();
+			}
 		      };
 		    };
 		    /// Dereferable map concept
 		    /// Dereferable map concept.
 		    ///
 		    template<typename K, typename T, typename R, typename CR>
 		    class ReferenceMap : public ReadWriteMap<K,T>
+		    {
 		    public:
 		      /// Tag for reference maps.
 		      typedef True ReferenceMapTag;
 		      /// The key type of the map.
 		      typedef K Key;
 		      /// The value type of the map. (The type of objects associated with the keys).
 		      typedef T Value;
 		      /// The reference type of the map.
 		      typedef R Reference;
 		      /// The const reference type of the map.
 		      typedef CR ConstReference;
 		    protected:
 		      Value tmp;
 		    public:
 		      ///Returns a reference to the value associated to a key.
 		      Reference operator[](const Key &) { return tmp; }
 		      ///Returns a const reference to the value associated to a key.
 		      ConstReference operator[](const Key &) const { return tmp; }
 		      /// Sets the value associated with a key.
 		      void set(const Key &k,const Value &t) { operator[](k)=t; }
 		      /// \todo Rethink this concept.
 		      template<typename _ReferenceMap>
 		      struct ReferenceMapConcept {
 			void constraints() {
 			  checkConcept<ReadWriteMap, _ReferenceMap >();
 			  m[key] = val;
 			  val  = m[key];
 			  m[key] = ref;
 			  ref = m[key];
 			  m[own_key] = own_val;
 			  own_val  = m[own_key];
 			  m[own_key] = own_ref;
 			  own_ref = m[own_key];
+			}
 			typename _ReferenceMap::Key& own_key;
 			typename _ReferenceMap::Value& own_val;
 			typename _ReferenceMap::Reference& own_ref;
 			Key& key;
 			Value& val;
 			Reference& ref;
 			_ReferenceMap& m;
 		      };
 		    };
 		    // @}
 		  } //namespace concepts
 		} //namespace lemon
 		#endif // LEMON_CONCEPT_MAPS_H

lemon/dim2.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_DIM2_H
 		#define LEMON_DIM2_H
 		#include <iostream>
 		#include <lemon/bits/utility.h>
 		///\ingroup misc
 		///\file
 		///\brief A simple two dimensional vector and a bounding box implementation
 		///
 		/// The class \ref lemon::dim2::Point "dim2::Point" implements
 		///a two dimensional vector with the usual
 		/// operations.
 		///
 		/// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
 		/// can be used to determine
 		/// the rectangular bounding box of a set of
 		/// \ref lemon::dim2::Point "dim2::Point"'s.
 		namespace lemon {
 		  ///Tools for handling two dimensional coordinates
 		  ///This namespace is a storage of several
 		  ///tools for handling two dimensional coordinates
 		  namespace dim2 {
 		  /// \addtogroup misc
 		  /// @{
 		  /// A simple two dimensional vector (plainvector) implementation
 		  /// A simple two dimensional vector (plainvector) implementation
 		  ///with the usual vector
 		  /// operators.
 		  ///
 		  template<typename T>
 		    class Point {
 		    public:
 		      typedef T Value;
 		      ///First coordinate
 		      T x;
 		      ///Second coordinate
 		      T y;
 		      ///Default constructor
 		      Point() {}
 		      ///Construct an instance from coordinates
 		      Point(T a, T b) : x(a), y(b) { }
 		      ///The dimension of the vector.
 		      ///The dimension of the vector.
 		      ///This function always returns 2.
 		      int size() const { return 2; }
 		      ///Subscripting operator
 		      ///\c p[0] is \c p.x and \c p[1] is \c p.y
 		      ///
 		      T& operator[](int idx) { return idx == 0 ? x : y; }
 		      ///Const subscripting operator
 		      ///\c p[0] is \c p.x and \c p[1] is \c p.y
 		      ///
 		      const T& operator[](int idx) const { return idx == 0 ? x : y; }
 		      ///Conversion constructor
 		      template<class TT> Point(const Point<TT> &p) : x(p.x), y(p.y) {}
 		      ///Give back the square of the norm of the vector
 		      T normSquare() const {
 		        return x*x+y*y;
+		      }
 		      ///Increment the left hand side by u
 		      Point<T>& operator +=(const Point<T>& u) {
 		        x += u.x;
 		        y += u.y;
 		        return *this;
+		      }
 		      ///Decrement the left hand side by u
 		      Point<T>& operator -=(const Point<T>& u) {
 		        x -= u.x;
 		        y -= u.y;
 		        return *this;
+		      }
 		      ///Multiply the left hand side with a scalar
 		      Point<T>& operator *=(const T &u) {
 		        x *= u;
 		        y *= u;
 		        return *this;
+		      }
 		      ///Divide the left hand side by a scalar
 		      Point<T>& operator /=(const T &u) {
 		        x /= u;
 		        y /= u;
 		        return *this;
+		      }
 		      ///Return the scalar product of two vectors
 		      T operator *(const Point<T>& u) const {
 		        return x*u.x+y*u.y;
+		      }
 		      ///Return the sum of two vectors
 		      Point<T> operator+(const Point<T> &u) const {
 		        Point<T> b=*this;
 		        return b+=u;
+		      }
 		      ///Return the negative of the vector
 		      Point<T> operator-() const {
 		        Point<T> b=*this;
 		        b.x=-b.x; b.y=-b.y;
 		        return b;
+		      }
 		      ///Return the difference of two vectors
 		      Point<T> operator-(const Point<T> &u) const {
 		        Point<T> b=*this;
 		        return b-=u;
+		      }
 		      ///Return a vector multiplied by a scalar
 		      Point<T> operator*(const T &u) const {
 		        Point<T> b=*this;
 		        return b*=u;
+		      }
 		      ///Return a vector divided by a scalar
 		      Point<T> operator/(const T &u) const {
 		        Point<T> b=*this;
 		        return b/=u;
+		      }
 		      ///Test equality
 		      bool operator==(const Point<T> &u) const {
 		        return (x==u.x) && (y==u.y);
+		      }
 		      ///Test inequality
 		      bool operator!=(Point u) const {
 		        return  (x!=u.x) || (y!=u.y);
+		      }
 		    };
 		  ///Return a Point
 		  ///Return a Point.
 		  ///\relates Point
 		  template <typename T>
 		  inline Point<T> makePoint(const T& x, const T& y) {
 		    return Point<T>(x, y);
+		  }
 		  ///Return a vector multiplied by a scalar
 		  ///Return a vector multiplied by a scalar.
 		  ///\relates Point
 		  template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
 		    return x*u;
+		  }
 		  ///Read a plainvector from a stream
 		  ///Read a plainvector from a stream.
 		  ///\relates Point
 		  ///
 		  template<typename T>
 		  inline std::istream& operator>>(std::istream &is, Point<T> &z) {
 		    char c;
 		    if (is >> c) {
 		      if (c != '(') is.putback(c);
 		    } else {
 		      is.clear();
+		    }
 		    if (!(is >> z.x)) return is;
 		    if (is >> c) {
 		      if (c != ',') is.putback(c);
 		    } else {
 		      is.clear();
+		    }
 		    if (!(is >> z.y)) return is;
 		    if (is >> c) {
 		      if (c != ')') is.putback(c);
 		    } else {
 		      is.clear();
+		    }
 		    return is;
+		  }
 		  ///Write a plainvector to a stream
 		  ///Write a plainvector to a stream.
 		  ///\relates Point
 		  ///
 		  template<typename T>
 		  inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
+		  {
 		    os << "(" << z.x << ", " << z.y << ")";
 		    return os;
+		  }
 		  ///Rotate by 90 degrees
 		  ///Returns the parameter rotated by 90 degrees in positive direction.
 		  ///\relates Point
 		  ///
 		  template<typename T>
 		  inline Point<T> rot90(const Point<T> &z)
+		  {
 		    return Point<T>(-z.y,z.x);
+		  }
 		  ///Rotate by 180 degrees
 		  ///Returns the parameter rotated by 180 degrees.
 		  ///\relates Point
 		  ///
 		  template<typename T>
 		  inline Point<T> rot180(const Point<T> &z)
+		  {
 		    return Point<T>(-z.x,-z.y);
+		  }
 		  ///Rotate by 270 degrees
 		  ///Returns the parameter rotated by 90 degrees in negative direction.
 		  ///\relates Point
 		  ///
 		  template<typename T>
 		  inline Point<T> rot270(const Point<T> &z)
+		  {
 		    return Point<T>(z.y,-z.x);
+		  }
 		  /// A class to calculate or store the bounding box of plainvectors.
 		  /// A class to calculate or store the bounding box of plainvectors.
 		  ///
 		    template<typename T>
 		    class BoundingBox {
 		      Point<T> bottom_left, top_right;
 		      bool _empty;
 		    public:
 		      ///Default constructor: creates an empty bounding box
 		      BoundingBox() { _empty = true; }
 		      ///Construct an instance from one point
 		      BoundingBox(Point<T> a) { bottom_left=top_right=a; _empty = false; }
 		      ///Construct an instance from two points
 		      ///Construct an instance from two points.
 		      ///\param a The bottom left corner.
 		      ///\param b The top right corner.
 		      ///\warning The coordinates of the bottom left corner must be no more
 		      ///than those of the top right one.
 		      BoundingBox(Point<T> a,Point<T> b)
+		      {
 			bottom_left=a;
 			top_right=b;
 			_empty = false;
+		      }
 		      ///Construct an instance from four numbers
 		      ///Construct an instance from four numbers.
 		      ///\param l The left side of the box.
 		      ///\param b The bottom of the box.
 		      ///\param r The right side of the box.
 		      ///\param t The top of the box.
 		      ///\warning The left side must be no more than the right side and
 		      ///bottom must be no more than the top.
 		      BoundingBox(T l,T b,T r,T t)
+		      {
 			bottom_left=Point<T>(l,b);
 			top_right=Point<T>(r,t);
 			_empty = false;
+		      }
 		      ///Return \c true if the bounding box is empty.
 		      ///Return \c true if the bounding box is empty (i.e. return \c false
 		      ///if at least one point was added to the box or the coordinates of
 		      ///the box were set).
 		      ///The coordinates of an empty bounding box are not defined.
 		      bool empty() const {
 		        return _empty;
+		      }
 		      ///Make the BoundingBox empty
 		      void clear() {
 		        _empty=1;
+		      }
 		      ///Give back the bottom left corner
 		      ///Give back the bottom left corner.
 		      ///If the bounding box is empty, then the return value is not defined.
 		      Point<T> bottomLeft() const {
 		        return bottom_left;
+		      }
 		      ///Set the bottom left corner
 		      ///Set the bottom left corner.
 		      ///It should only be used for non-empty box.
 		      void bottomLeft(Point<T> p) {
 			bottom_left = p;
+		      }
 		      ///Give back the top right corner
 		      ///Give back the top right corner.
 		      ///If the bounding box is empty, then the return value is not defined.
 		      Point<T> topRight() const {
 		        return top_right;
+		      }
 		      ///Set the top right corner
 		      ///Set the top right corner.
 		      ///It should only be used for non-empty box.
 		      void topRight(Point<T> p) {
 			top_right = p;
+		      }
 		      ///Give back the bottom right corner
 		      ///Give back the bottom right corner.
 		      ///If the bounding box is empty, then the return value is not defined.
 		      Point<T> bottomRight() const {
 		        return Point<T>(top_right.x,bottom_left.y);
+		      }
 		      ///Set the bottom right corner
 		      ///Set the bottom right corner.
 		      ///It should only be used for non-empty box.
 		      void bottomRight(Point<T> p) {
 			top_right.x = p.x;
 			bottom_left.y = p.y;
+		      }
 		      ///Give back the top left corner
 		      ///Give back the top left corner.
 		      ///If the bounding box is empty, then the return value is not defined.
 		      Point<T> topLeft() const {
 		        return Point<T>(bottom_left.x,top_right.y);
+		      }
 		      ///Set the top left corner
 		      ///Set the top left corner.
 		      ///It should only be used for non-empty box.
 		      void topLeft(Point<T> p) {
 			top_right.y = p.y;
 			bottom_left.x = p.x;
+		      }
 		      ///Give back the bottom of the box
 		      ///Give back the bottom of the box.
 		      ///If the bounding box is empty, then the return value is not defined.
 		      T bottom() const {
 		        return bottom_left.y;
+		      }
 		      ///Set the bottom of the box
 		      ///Set the bottom of the box.
 		      ///It should only be used for non-empty box.
 		      void bottom(T t) {
 			bottom_left.y = t;
+		      }
 		      ///Give back the top of the box
 		      ///Give back the top of the box.
 		      ///If the bounding box is empty, then the return value is not defined.
 		      T top() const {
 		        return top_right.y;
+		      }
 		      ///Set the top of the box
 		      ///Set the top of the box.
 		      ///It should only be used for non-empty box.
 		      void top(T t) {
 			top_right.y = t;
+		      }
 		      ///Give back the left side of the box
 		      ///Give back the left side of the box.
 		      ///If the bounding box is empty, then the return value is not defined.
 		      T left() const {
 		        return bottom_left.x;
+		      }
 		      ///Set the left side of the box
 		      ///Set the left side of the box.
 		      ///It should only be used for non-empty box.
 		      void left(T t) {
 			bottom_left.x = t;
+		      }
 		      /// Give back the right side of the box
 		      /// Give back the right side of the box.
 		      ///If the bounding box is empty, then the return value is not defined.
 		      T right() const {
 		        return top_right.x;
+		      }
 		      ///Set the right side of the box
 		      ///Set the right side of the box.
 		      ///It should only be used for non-empty box.
 		      void right(T t) {
 			top_right.x = t;
+		      }
 		      ///Give back the height of the box
 		      ///Give back the height of the box.
 		      ///If the bounding box is empty, then the return value is not defined.
 		      T height() const {
 		        return top_right.y-bottom_left.y;
+		      }
 		      ///Give back the width of the box
 		      ///Give back the width of the box.
 		      ///If the bounding box is empty, then the return value is not defined.
 		      T width() const {
 		        return top_right.x-bottom_left.x;
+		      }
 		      ///Checks whether a point is inside a bounding box
 		      bool inside(const Point<T>& u) const {
 		        if (_empty)
 		          return false;
 		        else{
 		          return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&
 		              (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
+		        }
+		      }
 		      ///Increments a bounding box with a point
 		      ///Increments a bounding box with a point.
 		      ///
 		      BoundingBox& add(const Point<T>& u){
 		        if (_empty){
 		          bottom_left=top_right=u;
 		          _empty = false;
+		        }
 		        else{
 		          if (bottom_left.x > u.x) bottom_left.x = u.x;
 		          if (bottom_left.y > u.y) bottom_left.y = u.y;
 		          if (top_right.x < u.x) top_right.x = u.x;
 		          if (top_right.y < u.y) top_right.y = u.y;
+		        }
 		        return *this;
+		      }
 		      ///Increments a bounding box to contain another bounding box
 		      ///Increments a bounding box to contain another bounding box.
 		      ///
 		      BoundingBox& add(const BoundingBox &u){
 		        if ( !u.empty() ){
 		          this->add(u.bottomLeft());
 			  this->add(u.topRight());
+		        }
 		        return *this;
+		      }
 		      ///Intersection of two bounding boxes
 		      ///Intersection of two bounding boxes.
 		      ///
 		      BoundingBox operator&(const BoundingBox& u) const {
 		        BoundingBox b;
 		        if (this->_empty || u._empty) {
 			  b._empty = true;
 			} else {
 			  b.bottom_left.x = std::max(this->bottom_left.x,u.bottom_left.x);
 			  b.bottom_left.y = std::max(this->bottom_left.y,u.bottom_left.y);
 			  b.top_right.x = std::min(this->top_right.x,u.top_right.x);
 			  b.top_right.y = std::min(this->top_right.y,u.top_right.y);
 			  b._empty = b.bottom_left.x > b.top_right.x ||
 			             b.bottom_left.y > b.top_right.y;
+			}
 		        return b;
+		      }
 		    };//class Boundingbox
 		  ///Map of x-coordinates of a \ref Point "Point"-map
 		  ///\ingroup maps
 		  ///Map of x-coordinates of a \ref Point "Point"-map.
 		  ///
 		  template<class M>
 		  class XMap
+		  {
 		    M& _map;
 		  public:
 		    typedef typename M::Value::Value Value;
 		    typedef typename M::Key Key;
 		    ///\e
 		    XMap(M& map) : _map(map) {}
 		    Value operator[](Key k) const {return _map[k].x;}
 		    void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}
 		  };
 		  ///Returns an \ref XMap class
 		  ///This function just returns an \ref XMap class.
 		  ///
 		  ///\ingroup maps
 		  ///\relates XMap
 		  template<class M>
 		  inline XMap<M> xMap(M &m)
+		  {
 		    return XMap<M>(m);
+		  }
 		  template<class M>
 		  inline XMap<M> xMap(const M &m)
+		  {
 		    return XMap<M>(m);
+		  }
 		  ///Constant (read only) version of \ref XMap
 		  ///\ingroup maps
 		  ///Constant (read only) version of \ref XMap
 		  ///
 		  template<class M>
 		  class ConstXMap
+		  {
 		    const M& _map;
 		  public:
 		    typedef typename M::Value::Value Value;
 		    typedef typename M::Key Key;
 		    ///\e
 		    ConstXMap(const M &map) : _map(map) {}
 		    Value operator[](Key k) const {return _map[k].x;}
 		  };
 		  ///Returns a \ref ConstXMap class
 		  ///This function just returns a \ref ConstXMap class.
 		  ///
 		  ///\ingroup maps
 		  ///\relates ConstXMap
 		  template<class M>
 		  inline ConstXMap<M> xMap(const M &m)
+		  {
 		    return ConstXMap<M>(m);
+		  }
 		  ///Map of y-coordinates of a \ref Point "Point"-map
 		  ///\ingroup maps
 		  ///Map of y-coordinates of a \ref Point "Point"-map.
 		  ///
 		  template<class M>
 		  class YMap
+		  {
 		    M& _map;
 		  public:
 		    typedef typename M::Value::Value Value;
 		    typedef typename M::Key Key;
 		    ///\e
 		    YMap(M& map) : _map(map) {}
 		    Value operator[](Key k) const {return _map[k].y;}
 		    void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}
 		  };
 		  ///Returns a \ref YMap class
 		  ///This function just returns a \ref YMap class.
 		  ///
 		  ///\ingroup maps
 		  ///\relates YMap
 		  template<class M>
 		  inline YMap<M> yMap(M &m)
+		  {
 		    return YMap<M>(m);
+		  }
 		  template<class M>
 		  inline YMap<M> yMap(const M &m)
+		  {
 		    return YMap<M>(m);
+		  }
 		  ///Constant (read only) version of \ref YMap
 		  ///\ingroup maps
 		  ///Constant (read only) version of \ref YMap
 		  ///
 		  template<class M>
 		  class ConstYMap
+		  {
 		    const M& _map;
 		  public:
 		    typedef typename M::Value::Value Value;
 		    typedef typename M::Key Key;
 		    ///\e
 		    ConstYMap(const M &map) : _map(map) {}
 		    Value operator[](Key k) const {return _map[k].y;}
 		  };
 		  ///Returns a \ref ConstYMap class
 		  ///This function just returns a \ref ConstYMap class.
 		  ///
 		  ///\ingroup maps
 		  ///\relates ConstYMap
 		  template<class M>
 		  inline ConstYMap<M> yMap(const M &m)
+		  {
 		    return ConstYMap<M>(m);
+		  }
 		    ///\brief Map of the \ref Point::normSquare() "normSquare()"
 		    ///of a \ref Point "Point"-map
 		    ///
 		    ///Map of the \ref Point::normSquare() "normSquare()"
 		    ///of a \ref Point "Point"-map.
 		    ///\ingroup maps
 		    ///
 		  template<class M>
 		  class NormSquareMap
+		  {
 		    const M& _map;
 		  public:
 		    typedef typename M::Value::Value Value;
 		    typedef typename M::Key Key;
 		    ///\e
 		    NormSquareMap(const M &map) : _map(map) {}
 		    Value operator[](Key k) const {return _map[k].normSquare();}
 		  };
 		  ///Returns a \ref NormSquareMap class
 		  ///This function just returns a \ref NormSquareMap class.
 		  ///
 		  ///\ingroup maps
 		  ///\relates NormSquareMap
 		  template<class M>
 		  inline NormSquareMap<M> normSquareMap(const M &m)
+		  {
 		    return NormSquareMap<M>(m);
+		  }
 		  /// @}
 		  } //namespce dim2
 		} //namespace lemon
 		#endif //LEMON_DIM2_H

lemon/list_graph.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */

lemon/maps.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_MAPS_H
 		#define LEMON_MAPS_H
 		#include <iterator>
 		#include <functional>
 		#include <vector>
 		#include <lemon/bits/utility.h>
 		// #include <lemon/bits/traits.h>
 		///\file
 		///\ingroup maps
 		///\brief Miscellaneous property maps
 		///
 		#include <map>
 		namespace lemon {
 		  /// \addtogroup maps
 		  /// @{
 		  /// Base class of maps.
 		  /// Base class of maps.
 		  /// It provides the necessary <tt>typedef</tt>s required by the map concept.
 		  template<typename K, typename T>
 		  class MapBase {
 		  public:
 		    /// The key type of the map.
 		    typedef K Key;
 		    /// The value type of the map. (The type of objects associated with the keys).
 		    typedef T Value;
 		  };
 		  /// Null map. (a.k.a. DoNothingMap)
 		  /// This map can be used if you have to provide a map only for
 		  /// its type definitions, or if you have to provide a writable map,
 		  /// but data written to it is not required (i.e. it will be sent to
 		  /// <tt>/dev/null</tt>).
 		  template<typename K, typename T>
 		  class NullMap : public MapBase<K, T> {
 		  public:
 		    typedef MapBase<K, T> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Gives back a default constructed element.
 		    T operator[](const K&) const { return T(); }
 		    /// Absorbs the value.
 		    void set(const K&, const T&) {}
 		  };
 		  ///Returns a \c NullMap class
 		  ///This function just returns a \c NullMap class.
 		  ///\relates NullMap
 		  template <typename K, typename V>
 		  NullMap<K, V> nullMap() {
 		    return NullMap<K, V>();
+		  }
 		  /// Constant map.
 		  /// This is a readable map which assigns a specified value to each key.
 		  /// In other aspects it is equivalent to the \c NullMap.
 		  template<typename K, typename T>
 		  class ConstMap : public MapBase<K, T> {
 		  private:
 		    T v;
 		  public:
 		    typedef MapBase<K, T> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// Default constructor
 		    /// Default constructor.
 		    /// The value of the map will be uninitialized.
 		    /// (More exactly it will be default constructed.)
 		    ConstMap() {}
 		    /// Constructor with specified initial value
 		    /// Constructor with specified initial value.
 		    /// \param _v is the initial value of the map.
 		    ConstMap(const T &_v) : v(_v) {}
 		    ///\e
 		    T operator[](const K&) const { return v; }
 		    ///\e
 		    void setAll(const T &t) {
 		      v = t;
+		    }
 		    template<typename T1>
 		    struct rebind {
 		      typedef ConstMap<K, T1> other;
 		    };
 		    template<typename T1>
 		    ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
 		  };
 		  ///Returns a \c ConstMap class
 		  ///This function just returns a \c ConstMap class.
 		  ///\relates ConstMap
 		  template<typename K, typename V>
 		  inline ConstMap<K, V> constMap(const V &v) {
 		    return ConstMap<K, V>(v);
+		  }
 		  template<typename T, T v>
 		  struct Const { };
 		  /// Constant map with inlined constant value.
 		  /// This is a readable map which assigns a specified value to each key.
 		  /// In other aspects it is equivalent to the \c NullMap.
 		  template<typename K, typename V, V v>
 		  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
 		  public:
 		    typedef MapBase<K, V> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    ConstMap() { }
 		    ///\e
 		    V operator[](const K&) const { return v; }
 		    ///\e
 		    void set(const K&, const V&) { }
 		  };
 		  ///Returns a \c ConstMap class
 		  ///This function just returns a \c ConstMap class with inlined value.
 		  ///\relates ConstMap
 		  template<typename K, typename V, V v>
 		  inline ConstMap<K, Const<V, v> > constMap() {
 		    return ConstMap<K, Const<V, v> >();
+		  }
 		  ///Map based on std::map
 		  ///This is essentially a wrapper for \c std::map with addition that
 		  ///you can specify a default value different from \c Value().
 		  template <typename K, typename T, typename Compare = std::less<K> >
 		  class StdMap {
 		    template <typename K1, typename T1, typename C1>
 		    friend class StdMap;
 		  public:
 		    typedef True ReferenceMapTag;
 		    ///\e
 		    typedef K Key;
 		    ///\e
 		    typedef T Value;
 		    ///\e
 		    typedef T& Reference;
 		    ///\e
 		    typedef const T& ConstReference;
 		  private:
 		    typedef std::map<K, T, Compare> Map;
 		    Value _value;
 		    Map _map;
 		  public:
 		    /// Constructor with specified default value
 		    StdMap(const T& value = T()) : _value(value) {}
 		    /// \brief Constructs the map from an appropriate std::map, and explicitly
 		    /// specifies a default value.
 		    template <typename T1, typename Comp1>
 		    StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
 		      : _map(map.begin(), map.end()), _value(value) {}
 		    /// \brief Constructs a map from an other StdMap.
 		    template<typename T1, typename Comp1>
 		    StdMap(const StdMap<Key, T1, Comp1> &c)
 		      : _map(c._map.begin(), c._map.end()), _value(c._value) {}
 		  private:
 		    StdMap& operator=(const StdMap&);
 		  public:
 		    ///\e
 		    Reference operator[](const Key &k) {
 		      typename Map::iterator it = _map.lower_bound(k);
 		      if (it != _map.end() && !_map.key_comp()(k, it->first))
 			return it->second;
 		      else
 			return _map.insert(it, std::make_pair(k, _value))->second;
+		    }
 		    /// \e
 		    ConstReference operator[](const Key &k) const {
 		      typename Map::const_iterator it = _map.find(k);
 		      if (it != _map.end())
 			return it->second;
 		      else
 			return _value;
+		    }
 		    /// \e
 		    void set(const Key &k, const T &t) {
 		      typename Map::iterator it = _map.lower_bound(k);
 		      if (it != _map.end() && !_map.key_comp()(k, it->first))
 			it->second = t;
 		      else
 			_map.insert(it, std::make_pair(k, t));
+		    }
 		    /// \e
 		    void setAll(const T &t) {
 		      _value = t;
 		      _map.clear();
+		    }
 		    template <typename T1, typename C1 = std::less<T1> >
 		    struct rebind {
 		      typedef StdMap<Key, T1, C1> other;
 		    };
 		  };
 		  /// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt>
 		  ///
 		  /// The current map has the <tt>[0..size-1]</tt> keyset and the values
 		  /// are stored in a \c std::vector<T>  container. It can be used with
 		  /// some data structures, for example \c UnionFind, \c BinHeap, when
 		  /// the used items are small integer numbers.
 		  ///
 		  /// \todo Revise its name
 		  template <typename T>
 		  class IntegerMap {
 		    template <typename T1>
 		    friend class IntegerMap;
 		  public:
 		    typedef True ReferenceMapTag;
 		    ///\e
 		    typedef int Key;
 		    ///\e
 		    typedef T Value;
 		    ///\e
 		    typedef T& Reference;
 		    ///\e
 		    typedef const T& ConstReference;
 		  private:
 		    typedef std::vector<T> Vector;
 		    Vector _vector;
 		  public:
 		    /// Constructor with specified default value
 		    IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
 		    /// \brief Constructs the map from an appropriate std::vector.
 		    template <typename T1>
 		    IntegerMap(const std::vector<T1>& vector)
 		      : _vector(vector.begin(), vector.end()) {}
 		    /// \brief Constructs a map from an other IntegerMap.
 		    template <typename T1>
 		    IntegerMap(const IntegerMap<T1> &c)
 		      : _vector(c._vector.begin(), c._vector.end()) {}
 		    /// \brief Resize the container
 		    void resize(int size, const T& value = T()) {
 		      _vector.resize(size, value);
+		    }
 		  private:
 		    IntegerMap& operator=(const IntegerMap&);
 		  public:
 		    ///\e
 		    Reference operator[](Key k) {
 		      return _vector[k];
+		    }
 		    /// \e
 		    ConstReference operator[](Key k) const {
 		      return _vector[k];
+		    }
 		    /// \e
 		    void set(const Key &k, const T& t) {
 		      _vector[k] = t;
+		    }
 		  };
 		  /// @}
 		  /// \addtogroup map_adaptors
 		  /// @{
 		  /// \brief Identity map.
 		  ///
 		  /// This map gives back the given key as value without any
 		  /// modification.
 		  template <typename T>
 		  class IdentityMap : public MapBase<T, T> {
 		  public:
 		    typedef MapBase<T, T> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    /// \e
 		    const T& operator[](const T& t) const {
 		      return t;
+		    }
 		  };
 		  ///Returns an \c IdentityMap class
 		  ///This function just returns an \c IdentityMap class.
 		  ///\relates IdentityMap
 		  template<typename T>
 		  inline IdentityMap<T> identityMap() {
 		    return IdentityMap<T>();
+		  }
 		  ///\brief Convert the \c Value of a map to another type using
 		  ///the default conversion.
 		  ///
 		  ///This \c concepts::ReadMap "read only map"
 		  ///converts the \c Value of a map to type \c T.
 		  ///Its \c Key is inherited from \c M.
 		  template <typename M, typename T>
 		  class ConvertMap : public MapBase<typename M::Key, T> {
 		    const M& m;
 		  public:
 		    typedef MapBase<typename M::Key, T> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    ///Constructor
 		    ///Constructor.
 		    ///\param _m is the underlying map.
 		    ConvertMap(const M &_m) : m(_m) {};
 		    /// \brief The subscript operator.
 		    ///
 		    /// The subscript operator.
 		    Value operator[](const Key& k) const {return m[k];}
 		  };
 		  ///Returns a \c ConvertMap class
 		  ///This function just returns a \c ConvertMap class.
 		  ///\relates ConvertMap
 		  template<typename T, typename M>
 		  inline ConvertMap<M, T> convertMap(const M &m) {
 		    return ConvertMap<M, T>(m);
+		  }
 		  ///Simple wrapping of a map
 		  ///This \c concepts::ReadMap "read only map" returns the simple
 		  ///wrapping of the given map. Sometimes the reference maps cannot be
 		  ///combined with simple read maps. This map adaptor wraps the given
 		  ///map to simple read map.
 		  ///
 		  ///\sa SimpleWriteMap
 		  ///
 		  /// \todo Revise the misleading name
 		  template<typename M>
 		  class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
 		    const M& m;
 		  public:
 		    typedef MapBase<typename M::Key, typename M::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    ///Constructor
 		    SimpleMap(const M &_m) : m(_m) {};
 		    ///\e
 		    Value operator[](Key k) const {return m[k];}
 		  };
 		  ///Simple writable wrapping of the map
 		  ///This \c concepts::WriteMap "write map" returns the simple
 		  ///wrapping of the given map. Sometimes the reference maps cannot be
 		  ///combined with simple read-write maps. This map adaptor wraps the
 		  ///given map to simple read-write map.
 		  ///
 		  ///\sa SimpleMap
 		  ///
 		  /// \todo Revise the misleading name
 		  template<typename M>
 		  class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
 		    M& m;
 		  public:
 		    typedef MapBase<typename M::Key, typename M::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    ///Constructor
 		    SimpleWriteMap(M &_m) : m(_m) {};
 		    ///\e
 		    Value operator[](Key k) const {return m[k];}
 		    ///\e
 		    void set(Key k, const Value& c) { m.set(k, c); }
 		  };
 		  ///Sum of two maps
 		  ///This \c concepts::ReadMap "read only map" returns the sum of the two
 		  ///given maps.
 		  ///Its \c Key and \c Value are inherited from \c M1.
 		  ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
 		  template<typename M1, typename M2>
 		  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
 		    const M1& m1;
 		    const M2& m2;
 		  public:
 		    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    ///Constructor
 		    AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
 		    ///\e
 		    Value operator[](Key k) const {return m1[k]+m2[k];}
 		  };
 		  ///Returns an \c AddMap class
 		  ///This function just returns an \c AddMap class.
 		  ///\todo How to call these type of functions?
 		  ///
 		  ///\relates AddMap
 		  template<typename M1, typename M2>
 		  inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
 		    return AddMap<M1, M2>(m1,m2);
+		  }
 		  ///Shift a map with a constant.
 		  ///This \c concepts::ReadMap "read only map" returns the sum of the
 		  ///given map and a constant value.
 		  ///Its \c Key and \c Value are inherited from \c M.
 		  ///
 		  ///Actually,
 		  ///\code
 		  ///  ShiftMap<X> sh(x,v);
 		  ///\endcode
 		  ///is equivalent to
 		  ///\code
 		  ///  ConstMap<X::Key, X::Value> c_tmp(v);
 		  ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
 		  ///\endcode
 		  ///
 		  ///\sa ShiftWriteMap
 		  template<typename M, typename C = typename M::Value>
 		  class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
 		    const M& m;
 		    C v;
 		  public:
 		    typedef MapBase<typename M::Key, typename M::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    ///Constructor
 		    ///Constructor.
 		    ///\param _m is the undelying map.
 		    ///\param _v is the shift value.
 		    ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
 		    ///\e
 		    Value operator[](Key k) const {return m[k] + v;}
 		  };
 		  ///Shift a map with a constant (ReadWrite version).
 		  ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the
 		  ///given map and a constant value. It makes also possible to write the map.
 		  ///Its \c Key and \c Value are inherited from \c M.
 		  ///
 		  ///\sa ShiftMap
 		  template<typename M, typename C = typename M::Value>
 		  class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
 		    M& m;
 		    C v;
 		  public:
 		    typedef MapBase<typename M::Key, typename M::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    ///Constructor
 		    ///Constructor.
 		    ///\param _m is the undelying map.
 		    ///\param _v is the shift value.
 		    ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
 		    /// \e
 		    Value operator[](Key k) const {return m[k] + v;}
 		    /// \e
 		    void set(Key k, const Value& c) { m.set(k, c - v); }
 		  };
 		  ///Returns a \c ShiftMap class
 		  ///This function just returns a \c ShiftMap class.
 		  ///\relates ShiftMap
 		  template<typename M, typename C>
 		  inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
 		    return ShiftMap<M, C>(m,v);
+		  }
 		  ///Returns a \c ShiftWriteMap class
 		  ///This function just returns a \c ShiftWriteMap class.
 		  ///\relates ShiftWriteMap
 		  template<typename M, typename C>
 		  inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
 		    return ShiftWriteMap<M, C>(m,v);
+		  }
 		  ///Difference of two maps
 		  ///This \c concepts::ReadMap "read only map" returns the difference
 		  ///of the values of the two given maps.
 		  ///Its \c Key and \c Value are inherited from \c M1.
 		  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
 		  ///
 		  /// \todo Revise the misleading name
 		  template<typename M1, typename M2>
 		  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
 		    const M1& m1;
 		    const M2& m2;
 		  public:
 		    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    ///Constructor
 		    SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
 		    /// \e
 		    Value operator[](Key k) const {return m1[k]-m2[k];}
 		  };
 		  ///Returns a \c SubMap class
 		  ///This function just returns a \c SubMap class.
 		  ///
 		  ///\relates SubMap
 		  template<typename M1, typename M2>
 		  inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
 		    return SubMap<M1, M2>(m1, m2);
+		  }
 		  ///Product of two maps
 		  ///This \c concepts::ReadMap "read only map" returns the product of the
 		  ///values of the two given maps.
 		  ///Its \c Key and \c Value are inherited from \c M1.
 		  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
 		  template<typename M1, typename M2>
 		  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
 		    const M1& m1;
 		    const M2& m2;
 		  public:
 		    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    ///Constructor
 		    MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
 		    /// \e
 		    Value operator[](Key k) const {return m1[k]*m2[k];}
 		  };
 		  ///Returns a \c MulMap class
 		  ///This function just returns a \c MulMap class.
 		  ///\relates MulMap
 		  template<typename M1, typename M2>
 		  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
 		    return MulMap<M1, M2>(m1,m2);
+		  }
 		  ///Scales a map with a constant.
 		  ///This \c concepts::ReadMap "read only map" returns the value of the
 		  ///given map multiplied from the left side with a constant value.
 		  ///Its \c Key and \c Value are inherited from \c M.
 		  ///
 		  ///Actually,
 		  ///\code
 		  ///  ScaleMap<X> sc(x,v);
 		  ///\endcode
 		  ///is equivalent to
 		  ///\code
 		  ///  ConstMap<X::Key, X::Value> c_tmp(v);
 		  ///  MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
 		  ///\endcode
 		  ///
 		  ///\sa ScaleWriteMap
 		  template<typename M, typename C = typename M::Value>
 		  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
 		    const M& m;
 		    C v;
 		  public:
 		    typedef MapBase<typename M::Key, typename M::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    ///Constructor
 		    ///Constructor.
 		    ///\param _m is the undelying map.
 		    ///\param _v is the scaling value.
 		    ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
 		    /// \e
 		    Value operator[](Key k) const {return v * m[k];}
 		  };
 		  ///Scales a map with a constant (ReadWrite version).
 		  ///This \c concepts::ReadWriteMap "read-write map" returns the value of the
 		  ///given map multiplied from the left side with a constant value. It can
 		  ///also be used as write map if the \c / operator is defined between
 		  ///\c Value and \c C and the given multiplier is not zero.
 		  ///Its \c Key and \c Value are inherited from \c M.
 		  ///
 		  ///\sa ScaleMap
 		  template<typename M, typename C = typename M::Value>
 		  class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
 		    M& m;
 		    C v;
 		  public:
 		    typedef MapBase<typename M::Key, typename M::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    ///Constructor
 		    ///Constructor.
 		    ///\param _m is the undelying map.
 		    ///\param _v is the scaling value.
 		    ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
 		    /// \e
 		    Value operator[](Key k) const {return v * m[k];}
 		    /// \e
 		    void set(Key k, const Value& c) { m.set(k, c / v);}
 		  };
 		  ///Returns a \c ScaleMap class
 		  ///This function just returns a \c ScaleMap class.
 		  ///\relates ScaleMap
 		  template<typename M, typename C>
 		  inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
 		    return ScaleMap<M, C>(m,v);
+		  }
 		  ///Returns a \c ScaleWriteMap class
 		  ///This function just returns a \c ScaleWriteMap class.
 		  ///\relates ScaleWriteMap
 		  template<typename M, typename C>
 		  inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
 		    return ScaleWriteMap<M, C>(m,v);
+		  }
 		  ///Quotient of two maps
 		  ///This \c concepts::ReadMap "read only map" returns the quotient of the
 		  ///values of the two given maps.
 		  ///Its \c Key and \c Value are inherited from \c M1.
 		  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
 		  template<typename M1, typename M2>
 		  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
 		    const M1& m1;
 		    const M2& m2;
 		  public:
 		    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    ///Constructor
 		    DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
 		    /// \e
 		    Value operator[](Key k) const {return m1[k]/m2[k];}
 		  };
 		  ///Returns a \c DivMap class
 		  ///This function just returns a \c DivMap class.
 		  ///\relates DivMap
 		  template<typename M1, typename M2>
 		  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
 		    return DivMap<M1, M2>(m1,m2);
+		  }
 		  ///Composition of two maps
 		  ///This \c concepts::ReadMap "read only map" returns the composition of
 		  ///two given maps.
 		  ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
 		  ///then for
 		  ///\code
 		  ///  ComposeMap<M1, M2> cm(m1,m2);
 		  ///\endcode
 		  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
 		  ///
 		  ///Its \c Key is inherited from \c M2 and its \c Value is from \c M1.
 		  ///\c M2::Value must be convertible to \c M1::Key.
 		  ///
 		  ///\sa CombineMap
 		  ///
 		  ///\todo Check the requirements.
 		  template <typename M1, typename M2>
 		  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
 		    const M1& m1;
 		    const M2& m2;
 		  public:
 		    typedef MapBase<typename M2::Key, typename M1::Value> Parent;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    ///Constructor
 		    ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
 		    /// \e
 		    /// \todo Use the  MapTraits once it is ported.
 		    ///
 		    //typename MapTraits<M1>::ConstReturnValue
 		    typename M1::Value

lemon/random.cc

Show inline comments

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2007
 * Copyright (C) 2003-2008
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

///\file
///\brief Instantiation of the Random class.

#include <lemon/random.h>

namespace lemon {
  /// \brief Global random number generator instance
  ///
  /// A global Mersenne Twister random number generator instance.
  Random rnd;
}

lemon/random.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		/*
 		 * This file contains the reimplemented version of the Mersenne Twister
 		 * Generator of Matsumoto and Nishimura.
+		 *
 		 * See the appropriate copyright notice below.
+		 *
 		 * Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
 		 * All rights reserved.
+		 *
 		 * Redistribution and use in source and binary forms, with or without
 		 * modification, are permitted provided that the following conditions
 		 * are met:
+		 *
 		 * 1. Redistributions of source code must retain the above copyright
 		 *    notice, this list of conditions and the following disclaimer.
+		 *
 		 * 2. Redistributions in binary form must reproduce the above copyright
 		 *    notice, this list of conditions and the following disclaimer in the
 		 *    documentation and/or other materials provided with the distribution.
+		 *
 		 * 3. The names of its contributors may not be used to endorse or promote
 		 *    products derived from this software without specific prior written
 		 *    permission.
+		 *
 		 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 		 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 		 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 		 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
 		 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 		 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 		 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 		 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 		 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 		 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 		 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 		 * OF THE POSSIBILITY OF SUCH DAMAGE.
+		 *
+		 *
 		 * Any feedback is very welcome.
 		 * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
 		 * email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space)
 		 */
 		#ifndef LEMON_RANDOM_H
 		#define LEMON_RANDOM_H
 		#include <algorithm>
 		#include <iterator>
 		#include <vector>
 		#include <ctime>
 		#include <cmath>
 		#include <lemon/dim2.h>
 		///\ingroup misc
 		///\file
 		///\brief Mersenne Twister random number generator
 		namespace lemon {
 		  namespace _random_bits {
 		    template <typename _Word, int _bits = std::numeric_limits<_Word>::digits>
 		    struct RandomTraits {};
 		    template <typename _Word>
 		    struct RandomTraits<_Word, 32> {
 		      typedef _Word Word;
 		      static const int bits = 32;
 		      static const int length = 624;
 		      static const int shift = 397;
 		      static const Word mul = 0x6c078965u;
 		      static const Word arrayInit = 0x012BD6AAu;
 		      static const Word arrayMul1 = 0x0019660Du;
 		      static const Word arrayMul2 = 0x5D588B65u;
 		      static const Word mask = 0x9908B0DFu;
 		      static const Word loMask = (1u << 31) - 1;
 		      static const Word hiMask = ~loMask;
 		      static Word tempering(Word rnd) {
 		        rnd ^= (rnd >> 11);
 		        rnd ^= (rnd << 7) & 0x9D2C5680u;
 		        rnd ^= (rnd << 15) & 0xEFC60000u;
 		        rnd ^= (rnd >> 18);
 		        return rnd;
+		      }
 		    };
 		    template <typename _Word>
 		    struct RandomTraits<_Word, 64> {
 		      typedef _Word Word;
 		      static const int bits = 64;
 		      static const int length = 312;
 		      static const int shift = 156;
 		      static const Word mul = Word(0x5851F42Du) << 32 | Word(0x4C957F2Du);
 		      static const Word arrayInit = Word(0x00000000u) << 32 |Word(0x012BD6AAu);
 		      static const Word arrayMul1 = Word(0x369DEA0Fu) << 32 |Word(0x31A53F85u);
 		      static const Word arrayMul2 = Word(0x27BB2EE6u) << 32 |Word(0x87B0B0FDu);
 		      static const Word mask = Word(0xB5026F5Au) << 32 | Word(0xA96619E9u);
 		      static const Word loMask = (Word(1u) << 31) - 1;
 		      static const Word hiMask = ~loMask;
 		      static Word tempering(Word rnd) {
 		        rnd ^= (rnd >> 29) & (Word(0x55555555u) << 32 | Word(0x55555555u));
 		        rnd ^= (rnd << 17) & (Word(0x71D67FFFu) << 32 | Word(0xEDA60000u));
 		        rnd ^= (rnd << 37) & (Word(0xFFF7EEE0u) << 32 | Word(0x00000000u));
 		        rnd ^= (rnd >> 43);
 		        return rnd;
+		      }
 		    };
 		    template <typename _Word>
 		    class RandomCore {
 		    public:
 		      typedef _Word Word;
 		    private:
 		      static const int bits = RandomTraits<Word>::bits;
 		      static const int length = RandomTraits<Word>::length;
 		      static const int shift = RandomTraits<Word>::shift;
 		    public:
 		      void initState() {
 		        static const Word seedArray[4] = {
 x12345u, 0x23456u, 0x34567u, 0x45678u
 		        };
 		        initState(seedArray, seedArray + 4);
+		      }
 		      void initState(Word seed) {
 		        static const Word mul = RandomTraits<Word>::mul;
 		        current = state;
 		        Word *curr = state + length - 1;
 		        curr[0] = seed; --curr;
 		        for (int i = 1; i < length; ++i) {
 		          curr[0] = (mul * ( curr[1] ^ (curr[1] >> (bits - 2)) ) + i);
 		          --curr;
+		        }
+		      }
 		      template <typename Iterator>
 		      void initState(Iterator begin, Iterator end) {
 		        static const Word init = RandomTraits<Word>::arrayInit;
 		        static const Word mul1 = RandomTraits<Word>::arrayMul1;
 		        static const Word mul2 = RandomTraits<Word>::arrayMul2;
 		        Word *curr = state + length - 1; --curr;
 		        Iterator it = begin; int cnt = 0;
 		        int num;
 		        initState(init);
 		        num = length > end - begin ? length : end - begin;
 		        while (num--) {
 		          curr[0] = (curr[0] ^ ((curr[1] ^ (curr[1] >> (bits - 2))) * mul1))
 		            + *it + cnt;
 		          ++it; ++cnt;
 		          if (it == end) {
 		            it = begin; cnt = 0;
+		          }
 		          if (curr == state) {
 		            curr = state + length - 1; curr[0] = state[0];
+		          }
 		          --curr;
+		        }
 		        num = length - 1; cnt = length - (curr - state) - 1;
 		        while (num--) {
 		          curr[0] = (curr[0] ^ ((curr[1] ^ (curr[1] >> (bits - 2))) * mul2))
 		            - cnt;
 		          --curr; ++cnt;
 		          if (curr == state) {
 		            curr = state + length - 1; curr[0] = state[0]; --curr;
 		            cnt = 1;
+		          }
+		        }
 		        state[length - 1] = Word(1) << (bits - 1);
+		      }
 		      void copyState(const RandomCore& other) {
 		        std::copy(other.state, other.state + length, state);
 		        current = state + (other.current - other.state);
+		      }
 		      Word operator()() {
 		        if (current == state) fillState();
 		        --current;
 		        Word rnd = *current;
 		        return RandomTraits<Word>::tempering(rnd);
+		      }
 		    private:
 		      void fillState() {
 		        static const Word mask[2] = { 0x0ul, RandomTraits<Word>::mask };
 		        static const Word loMask = RandomTraits<Word>::loMask;
 		        static const Word hiMask = RandomTraits<Word>::hiMask;
 		        current = state + length;
 		        register Word *curr = state + length - 1;
 		        register long num;
 		        num = length - shift;
 		        while (num--) {
 		          curr[0] = (((curr[0] & hiMask) | (curr[-1] & loMask)) >> 1) ^
 		            curr[- shift] ^ mask[curr[-1] & 1ul];
 		          --curr;
+		        }
 		        num = shift - 1;
 		        while (num--) {
 		          curr[0] = (((curr[0] & hiMask) | (curr[-1] & loMask)) >> 1) ^
 		            curr[length - shift] ^ mask[curr[-1] & 1ul];
 		          --curr;
+		        }
 		        curr[0] = (((curr[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
 		          curr[length - shift] ^ mask[curr[length - 1] & 1ul];
+		      }
 		      Word *current;
 		      Word state[length];
 		    };
 		    template <typename Result,
 		              int shift = (std::numeric_limits<Result>::digits + 1) / 2>
 		    struct Masker {
 		      static Result mask(const Result& result) {
 		        return Masker<Result, (shift + 1) / 2>::
 		          mask(static_cast<Result>(result | (result >> shift)));
+		      }
 		    };
 		    template <typename Result>
 		    struct Masker<Result, 1> {
 		      static Result mask(const Result& result) {
 		        return static_cast<Result>(result | (result >> 1));
+		      }
 		    };
 		    template <typename Result, typename Word,
 		              int rest = std::numeric_limits<Result>::digits, int shift = 0,
 		              bool last = rest <= std::numeric_limits<Word>::digits>
 		    struct IntConversion {
 		      static const int bits = std::numeric_limits<Word>::digits;
 		      static Result convert(RandomCore<Word>& rnd) {
 		        return static_cast<Result>(rnd() >> (bits - rest)) << shift;
+		      }
 		    };
 		    template <typename Result, typename Word, int rest, int shift>
 		    struct IntConversion<Result, Word, rest, shift, false> {
 		      static const int bits = std::numeric_limits<Word>::digits;
 		      static Result convert(RandomCore<Word>& rnd) {
 		        return (static_cast<Result>(rnd()) << shift) |
 		          IntConversion<Result, Word, rest - bits, shift + bits>::convert(rnd);
+		      }
 		    };
 		    template <typename Result, typename Word,
 		              bool one_word = (std::numeric_limits<Word>::digits <
 					       std::numeric_limits<Result>::digits) >
 		    struct Mapping {
 		      static Result map(RandomCore<Word>& rnd, const Result& bound) {
 		        Word max = Word(bound - 1);
 		        Result mask = Masker<Result>::mask(bound - 1);
 		        Result num;
 		        do {
 		          num = IntConversion<Result, Word>::convert(rnd) & mask;
 		        } while (num > max);
 		        return num;
+		      }
 		    };
 		    template <typename Result, typename Word>
 		    struct Mapping<Result, Word, false> {
 		      static Result map(RandomCore<Word>& rnd, const Result& bound) {
 		        Word max = Word(bound - 1);
 		        Word mask = Masker<Word, (std::numeric_limits<Result>::digits + 1) / 2>
 		          ::mask(max);
 		        Word num;
 		        do {
 		          num = rnd() & mask;
 		        } while (num > max);
 		        return num;
+		      }
 		    };
 		    template <typename Result, int exp, bool pos = (exp >= 0)>
 		    struct ShiftMultiplier {
 		      static const Result multiplier() {
 		        Result res = ShiftMultiplier<Result, exp / 2>::multiplier();
 		        res *= res;
 		        if ((exp & 1) == 1) res *= static_cast<Result>(2.0);
 		        return res;
+		      }
 		    };
 		    template <typename Result, int exp>
 		    struct ShiftMultiplier<Result, exp, false> {
 		      static const Result multiplier() {
 		        Result res = ShiftMultiplier<Result, exp / 2>::multiplier();
 		        res *= res;
 		        if ((exp & 1) == 1) res *= static_cast<Result>(0.5);
 		        return res;
+		      }
 		    };
 		    template <typename Result>
 		    struct ShiftMultiplier<Result, 0, true> {
 		      static const Result multiplier() {
 		        return static_cast<Result>(1.0);
+		      }
 		    };
 		    template <typename Result>
 		    struct ShiftMultiplier<Result, -20, true> {
 		      static const Result multiplier() {
 		        return static_cast<Result>(1.0/1048576.0);
+		      }
 		    };
 		    template <typename Result>
 		    struct ShiftMultiplier<Result, -32, true> {
 		      static const Result multiplier() {
 		        return static_cast<Result>(1.0/424967296.0);
+		      }
 		    };
 		    template <typename Result>
 		    struct ShiftMultiplier<Result, -53, true> {
 		      static const Result multiplier() {
 		        return static_cast<Result>(1.0/9007199254740992.0);
+		      }
 		    };
 		    template <typename Result>
 		    struct ShiftMultiplier<Result, -64, true> {
 		      static const Result multiplier() {
 		        return static_cast<Result>(1.0/18446744073709551616.0);
+		      }
 		    };
 		    template <typename Result, int exp>
 		    struct Shifting {
 		      static Result shift(const Result& result) {
 		        return result * ShiftMultiplier<Result, exp>::multiplier();
+		      }
 		    };
 		    template <typename Result, typename Word,
 		              int rest = std::numeric_limits<Result>::digits, int shift = 0,
 		              bool last = rest <= std::numeric_limits<Word>::digits>
 		    struct RealConversion{
 		      static const int bits = std::numeric_limits<Word>::digits;
 		      static Result convert(RandomCore<Word>& rnd) {
 		        return Shifting<Result, - shift - rest>::
 		          shift(static_cast<Result>(rnd() >> (bits - rest)));
+		      }
 		    };
 		    template <typename Result, typename Word, int rest, int shift>
 		    struct RealConversion<Result, Word, rest, shift, false> {
 		      static const int bits = std::numeric_limits<Word>::digits;
 		      static Result convert(RandomCore<Word>& rnd) {
 		        return Shifting<Result, - shift - bits>::
 		          shift(static_cast<Result>(rnd())) +
 		          RealConversion<Result, Word, rest-bits, shift + bits>::
 		          convert(rnd);
+		      }
 		    };
 		    template <typename Result, typename Word>
 		    struct Initializer {
 		      template <typename Iterator>
 		      static void init(RandomCore<Word>& rnd, Iterator begin, Iterator end) {
 		        std::vector<Word> ws;
 		        for (Iterator it = begin; it != end; ++it) {
 		          ws.push_back(Word(*it));
+		        }
 		        rnd.initState(ws.begin(), ws.end());
+		      }
 		      static void init(RandomCore<Word>& rnd, Result seed) {
 		        rnd.initState(seed);
+		      }
 		    };
 		    template <typename Word>
 		    struct BoolConversion {
 		      static bool convert(RandomCore<Word>& rnd) {
 		        return (rnd() & 1) == 1;
+		      }
 		    };
 		    template <typename Word>
 		    struct BoolProducer {
 		      Word buffer;
 		      int num;
 		      BoolProducer() : num(0) {}
 		      bool convert(RandomCore<Word>& rnd) {
 		        if (num == 0) {
 		          buffer = rnd();
 		          num = RandomTraits<Word>::bits;
+		        }
 		        bool r = (buffer & 1);
 		        buffer >>= 1;
 		        --num;
 		        return r;
+		      }
 		    };
+		  }
 		  /// \ingroup misc
 		  ///
 		  /// \brief Mersenne Twister random number generator
 		  ///
 		  /// The Mersenne Twister is a twisted generalized feedback
 		  /// shift-register generator of Matsumoto and Nishimura. The period
 		  /// of this generator is \f$ 2^{19937} - 1 \f$ and it is
 		  /// equi-distributed in 623 dimensions for 32-bit numbers. The time
 		  /// performance of this generator is comparable to the commonly used
 		  /// generators.
 		  ///
 		  /// This implementation is specialized for both 32-bit and 64-bit
 		  /// architectures. The generators differ sligthly in the
 		  /// initialization and generation phase so they produce two
 		  /// completly different sequences.
 		  ///
 		  /// The generator gives back random numbers of serveral types. To
 		  /// get a random number from a range of a floating point type you
 		  /// can use one form of the \c operator() or the \c real() member
 		  /// function. If you want to get random number from the {0, 1, ...,
 		  /// n-1} integer range use the \c operator[] or the \c integer()
 		  /// method. And to get random number from the whole range of an
 		  /// integer type you can use the argumentless \c integer() or \c
 		  /// uinteger() functions. After all you can get random bool with
 		  /// equal chance of true and false or given probability of true
 		  /// result with the \c boolean() member functions.
 		  ///
 		  ///\code
 		  /// // The commented code is identical to the other
 		  /// double a = rnd();                     // [0.0, 1.0)
 		  /// // double a = rnd.real();             // [0.0, 1.0)
 		  /// double b = rnd(100.0);                // [0.0, 100.0)
 		  /// // double b = rnd.real(100.0);        // [0.0, 100.0)
 		  /// double c = rnd(1.0, 2.0);             // [1.0, 2.0)
 		  /// // double c = rnd.real(1.0, 2.0);     // [1.0, 2.0)
 		  /// int d = rnd[100000];                  // 0..99999
 		  /// // int d = rnd.integer(100000);       // 0..99999
 		  /// int e = rnd[6] + 1;                   // 1..6
 		  /// // int e = rnd.integer(1, 1 + 6);     // 1..6
 		  /// int b = rnd.uinteger<int>();          // 0 .. 2^31 - 1
 		  /// int c = rnd.integer<int>();           // - 2^31 .. 2^31 - 1
 		  /// bool g = rnd.boolean();               // P(g = true) = 0.5
 		  /// bool h = rnd.boolean(0.8);            // P(h = true) = 0.8
 		  ///\endcode
 		  ///
 		  /// The lemon provides a global instance of the random number
 		  /// generator which name is \ref lemon::rnd "rnd". Usually it is a
 		  /// good programming convenience to use this global generator to get
 		  /// random numbers.
 		  class Random {
 		  private:
 		    // Architecture word
 		    typedef unsigned long Word;
 		    _random_bits::RandomCore<Word> core;
 		    _random_bits::BoolProducer<Word> bool_producer;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor with constant seeding.
 		    Random() { core.initState(); }
 		    /// \brief Constructor
 		    ///
 		    /// Constructor with seed. The current number type will be converted
 		    /// to the architecture word type.
 		    template <typename Number>
 		    Random(Number seed) {
 		      _random_bits::Initializer<Number, Word>::init(core, seed);
+		    }
 		    /// \brief Constructor
 		    ///
 		    /// Constructor with array seeding. The given range should contain
 		    /// any number type and the numbers will be converted to the
 		    /// architecture word type.
 		    template <typename Iterator>
 		    Random(Iterator begin, Iterator end) {
 		      typedef typename std::iterator_traits<Iterator>::value_type Number;
 		      _random_bits::Initializer<Number, Word>::init(core, begin, end);
+		    }
 		    /// \brief Copy constructor
 		    ///
 		    /// Copy constructor. The generated sequence will be identical to
 		    /// the other sequence. It can be used to save the current state
 		    /// of the generator and later use it to generate the same
 		    /// sequence.
 		    Random(const Random& other) {
 		      core.copyState(other.core);
+		    }
 		    /// \brief Assign operator
 		    ///
 		    /// Assign operator. The generated sequence will be identical to
 		    /// the other sequence. It can be used to save the current state
 		    /// of the generator and later use it to generate the same
 		    /// sequence.
 		    Random& operator=(const Random& other) {
 		      if (&other != this) {
 		        core.copyState(other.core);
+		      }
 		      return *this;
+		    }
 		    /// \brief Returns a random real number from the range [0, 1)
 		    ///
 		    /// It returns a random real number from the range [0, 1). The
 		    /// default Number type is double.
 		    template <typename Number>
 		    Number real() {
 		      return _random_bits::RealConversion<Number, Word>::convert(core);
+		    }
 		    double real() {
 		      return real<double>();
+		    }
 		    /// \brief Returns a random real number the range [0, b)
 		    ///
 		    /// It returns a random real number from the range [0, b).
 		    template <typename Number>
 		    Number real(Number b) {
 		      return real<Number>() * b;
+		    }
 		    /// \brief Returns a random real number from the range [a, b)
 		    ///
 		    /// It returns a random real number from the range [a, b).
 		    template <typename Number>
 		    Number real(Number a, Number b) {
 		      return real<Number>() * (b - a) + a;
+		    }
 		    /// \brief Returns a random real number from the range [0, 1)
 		    ///
 		    /// It returns a random double from the range [0, 1).
 		    double operator()() {
 		      return real<double>();
+		    }
 		    /// \brief Returns a random real number from the range [0, b)
 		    ///
 		    /// It returns a random real number from the range [0, b).
 		    template <typename Number>
 		    Number operator()(Number b) {
 		      return real<Number>() * b;
+		    }
 		    /// \brief Returns a random real number from the range [a, b)
 		    ///
 		    /// It returns a random real number from the range [a, b).
 		    template <typename Number>
 		    Number operator()(Number a, Number b) {
 		      return real<Number>() * (b - a) + a;
+		    }
 		    /// \brief Returns a random integer from a range
 		    ///
 		    /// It returns a random integer from the range {0, 1, ..., b - 1}.
 		    template <typename Number>
 		    Number integer(Number b) {
 		      return _random_bits::Mapping<Number, Word>::map(core, b);
+		    }
 		    /// \brief Returns a random integer from a range
 		    ///
 		    /// It returns a random integer from the range {a, a + 1, ..., b - 1}.
 		    template <typename Number>
 		    Number integer(Number a, Number b) {
 		      return _random_bits::Mapping<Number, Word>::map(core, b - a) + a;
+		    }
 		    /// \brief Returns a random integer from a range
 		    ///
 		    /// It returns a random integer from the range {0, 1, ..., b - 1}.
 		    template <typename Number>
 		    Number operator[](Number b) {
 		      return _random_bits::Mapping<Number, Word>::map(core, b);
+		    }
 		    /// \brief Returns a random non-negative integer
 		    ///
 		    /// It returns a random non-negative integer uniformly from the
 		    /// whole range of the current \c Number type.  The default result
 		    /// type of this function is unsigned int.
 		    template <typename Number>
 		    Number uinteger() {
 		      return _random_bits::IntConversion<Number, Word>::convert(core);
+		    }
 		    unsigned int uinteger() {
 		      return uinteger<unsigned int>();
+		    }
 		    /// \brief Returns a random integer
 		    ///
 		    /// It returns a random integer uniformly from the whole range of
 		    /// the current \c Number type. The default result type of this
 		    /// function is int.
 		    template <typename Number>
 		    Number integer() {
 		      static const int nb = std::numeric_limits<Number>::digits +
 		        (std::numeric_limits<Number>::is_signed ? 1 : 0);
 		      return _random_bits::IntConversion<Number, Word, nb>::convert(core);
+		    }
 		    int integer() {
 		      return integer<int>();
+		    }
 		    /// \brief Returns a random bool
 		    ///
 		    /// It returns a random bool. The generator holds a buffer for
 		    /// random bits. Every time when it become empty the generator makes
 		    /// a new random word and fill the buffer up.
 		    bool boolean() {
 		      return bool_producer.convert(core);
+		    }
 		    ///\name Nonuniform distributions
 		    ///
 		    ///@{
 		    /// \brief Returns a random bool
 		    ///
 		    /// It returns a random bool with given probability of true result.
 		    bool boolean(double p) {
 		      return operator()() < p;
+		    }
 		    /// Standard Gauss distribution
 		    /// Standard Gauss distribution.
 		    /// \note The Cartesian form of the Box-Muller
 		    /// transformation is used to generate a random normal distribution.
 		    /// \todo Consider using the "ziggurat" method instead.
 		    double gauss()
+		    {
 		      double V1,V2,S;
 		      do {
 			V1=2*real<double>()-1;
 			V2=2*real<double>()-1;
 			S=V1*V1+V2*V2;
 		      } while(S>=1);
 		      return std::sqrt(-2*std::log(S)/S)*V1;
+		    }
 		    /// Gauss distribution with given mean and standard deviation
 		    /// Gauss distribution with given mean and standard deviation.
 		    /// \sa gauss()
 		    double gauss(double mean,double std_dev)
+		    {
 		      return gauss()*std_dev+mean;
+		    }
 		    /// Exponential distribution with given mean
 		    /// This function generates an exponential distribution random number
 		    /// with mean <tt>1/lambda</tt>.
 		    ///
 		    double exponential(double lambda=1.0)
+		    {
 		      return -std::log(1.0-real<double>())/lambda;
+		    }
 		    /// Gamma distribution with given integer shape
 		    /// This function generates a gamma distribution random number.
 		    ///
 		    ///\param k shape parameter (<tt>k>0</tt> integer)
 		    double gamma(int k)
+		    {
 		      double s = 0;
 		      for(int i=0;i<k;i++) s-=std::log(1.0-real<double>());
 		      return s;
+		    }
 		    /// Gamma distribution with given shape and scale parameter
 		    /// This function generates a gamma distribution random number.
 		    ///
 		    ///\param k shape parameter (<tt>k>0</tt>)
 		    ///\param theta scale parameter
 		    ///
 		    double gamma(double k,double theta=1.0)
+		    {
 		      double xi,nu;
 		      const double delta = k-std::floor(k);
 		      const double v0=M_E/(M_E-delta);
 		      do {
 			double V0=1.0-real<double>();
 			double V1=1.0-real<double>();
 			double V2=1.0-real<double>();
 			if(V2<=v0)
+			  {
 			    xi=std::pow(V1,1.0/delta);
 			    nu=V0*std::pow(xi,delta-1.0);
+			  }
 			else
+			  {

lemon/tolerance.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_TOLERANCE_H
 		#define LEMON_TOLERANCE_H
 		///\ingroup misc
 		///\file
 		///\brief A basic tool to handle the anomalies of calculation with
 		///floating point numbers.
 		///
 		///\todo It should be in a module like "Basic tools"
 		namespace lemon {
 		  /// \addtogroup misc
 		  /// @{
 		  ///\brief A class to provide a basic way to
 		  ///handle the comparison of numbers that are obtained
 		  ///as a result of a probably inexact computation.
 		  ///
 		  ///Tolerance is a class to provide a basic way to
 		  ///handle the comparison of numbers that are obtained
 		  ///as a result of a probably inexact computation.
 		  ///
 		  ///This is an abstract class, it should be specialized for all numerical
 		  ///data types. These specialized classes like \ref Tolerance\<double\>
 		  ///may offer additional tuning parameters.
 		  ///
 		  ///\sa Tolerance<float>
 		  ///\sa Tolerance<double>
 		  ///\sa Tolerance<long double>
 		  ///\sa Tolerance<int>
 		#if defined __GNUC__ && !defined __STRICT_ANSI__
 		  ///\sa Tolerance<long long int>
 		#endif
 		  ///\sa Tolerance<unsigned int>
 		#if defined __GNUC__ && !defined __STRICT_ANSI__
 		  ///\sa Tolerance<unsigned long long int>
 		#endif
 		  template<class T>
 		  class Tolerance
+		  {
 		  public:
 		    typedef T Value;
 		    ///\name Comparisons
 		    ///The concept is that these bool functions return with \c true only if
 		    ///the related comparisons hold even if some numerical error appeared
 		    ///during the computations.
 		    ///@{
 		    ///Returns \c true if \c a is \e surely strictly less than \c b
 		    static bool less(Value a,Value b) {return false;}
 		    ///Returns \c true if \c a is \e surely different from \c b
 		    static bool different(Value a,Value b) {return false;}
 		    ///Returns \c true if \c a is \e surely positive
 		    static bool positive(Value a) {return false;}
 		    ///Returns \c true if \c a is \e surely negative
 		    static bool negative(Value a) {return false;}
 		    ///Returns \c true if \c a is \e surely non-zero
 		    static bool nonZero(Value a) {return false;}
 		    ///@}
 		    ///Returns the zero value.
 		    static Value zero() {return T();}
 		    //   static bool finite(Value a) {}
 		    //   static Value big() {}
 		    //   static Value negativeBig() {}
 		  };
 		  ///Float specialization of \ref Tolerance.
 		  ///Float specialization of \ref Tolerance.
 		  ///\sa Tolerance
 		  ///\relates Tolerance
 		  template<>
 		  class Tolerance<float>
+		  {
 		    static float def_epsilon;
 		    float _epsilon;
 		  public:
 		    ///\e
 		    typedef float Value;
 		    ///Constructor setting the epsilon tolerance to the default value.
 		    Tolerance() : _epsilon(def_epsilon) {}
 		    ///Constructor setting the epsilon tolerance.
 		    Tolerance(float e) : _epsilon(e) {}
 		    ///Return the epsilon value.
 		    Value epsilon() const {return _epsilon;}
 		    ///Set the epsilon value.
 		    void epsilon(Value e) {_epsilon=e;}
 		    ///Return the default epsilon value.
 		    static Value defaultEpsilon() {return def_epsilon;}
 		    ///Set the default epsilon value.
 		    static void defaultEpsilon(Value e) {def_epsilon=e;}
 		    ///\name Comparisons
 		    ///See class Tolerance for more details.
 		    ///@{
 		    ///Returns \c true if \c a is \e surely strictly less than \c b
 		    bool less(Value a,Value b) const {return a+_epsilon<b;}
 		    ///Returns \c true if \c a is \e surely different from \c b
 		    bool different(Value a,Value b) const { return less(a,b)||less(b,a); }
 		    ///Returns \c true if \c a is \e surely positive
 		    bool positive(Value a) const { return _epsilon<a; }
 		    ///Returns \c true if \c a is \e surely negative
 		    bool negative(Value a) const { return -_epsilon>a; }
 		    ///Returns \c true if \c a is \e surely non-zero
 		    bool nonZero(Value a) const { return positive(a)||negative(a); }
 		    ///@}
 		    ///Returns zero
 		    static Value zero() {return 0;}
 		  };
 		  ///Double specialization of \ref Tolerance.
 		  ///Double specialization of \ref Tolerance.
 		  ///\sa Tolerance
 		  ///\relates Tolerance
 		  template<>
 		  class Tolerance<double>
+		  {
 		    static double def_epsilon;
 		    double _epsilon;
 		  public:
 		    ///\e
 		    typedef double Value;
 		    ///Constructor setting the epsilon tolerance to the default value.
 		    Tolerance() : _epsilon(def_epsilon) {}
 		    ///Constructor setting the epsilon tolerance.
 		    Tolerance(double e) : _epsilon(e) {}
 		    ///Return the epsilon value.
 		    Value epsilon() const {return _epsilon;}
 		    ///Set the epsilon value.
 		    void epsilon(Value e) {_epsilon=e;}
 		    ///Return the default epsilon value.
 		    static Value defaultEpsilon() {return def_epsilon;}
 		    ///Set the default epsilon value.
 		    static void defaultEpsilon(Value e) {def_epsilon=e;}
 		    ///\name Comparisons
 		    ///See class Tolerance for more details.
 		    ///@{
 		    ///Returns \c true if \c a is \e surely strictly less than \c b
 		    bool less(Value a,Value b) const {return a+_epsilon<b;}
 		    ///Returns \c true if \c a is \e surely different from \c b
 		    bool different(Value a,Value b) const { return less(a,b)||less(b,a); }
 		    ///Returns \c true if \c a is \e surely positive
 		    bool positive(Value a) const { return _epsilon<a; }
 		    ///Returns \c true if \c a is \e surely negative
 		    bool negative(Value a) const { return -_epsilon>a; }
 		    ///Returns \c true if \c a is \e surely non-zero
 		    bool nonZero(Value a) const { return positive(a)||negative(a); }
 		    ///@}
 		    ///Returns zero
 		    static Value zero() {return 0;}
 		  };
 		  ///Long double specialization of \ref Tolerance.
 		  ///Long double specialization of \ref Tolerance.
 		  ///\sa Tolerance
 		  ///\relates Tolerance
 		  template<>
 		  class Tolerance<long double>
+		  {
 		    static long double def_epsilon;
 		    long double _epsilon;
 		  public:
 		    ///\e
 		    typedef long double Value;
 		    ///Constructor setting the epsilon tolerance to the default value.
 		    Tolerance() : _epsilon(def_epsilon) {}
 		    ///Constructor setting the epsilon tolerance.
 		    Tolerance(long double e) : _epsilon(e) {}
 		    ///Return the epsilon value.
 		    Value epsilon() const {return _epsilon;}
 		    ///Set the epsilon value.
 		    void epsilon(Value e) {_epsilon=e;}
 		    ///Return the default epsilon value.
 		    static Value defaultEpsilon() {return def_epsilon;}
 		    ///Set the default epsilon value.
 		    static void defaultEpsilon(Value e) {def_epsilon=e;}
 		    ///\name Comparisons
 		    ///See class Tolerance for more details.
 		    ///@{
 		    ///Returns \c true if \c a is \e surely strictly less than \c b
 		    bool less(Value a,Value b) const {return a+_epsilon<b;}
 		    ///Returns \c true if \c a is \e surely different from \c b
 		    bool different(Value a,Value b) const { return less(a,b)||less(b,a); }
 		    ///Returns \c true if \c a is \e surely positive
 		    bool positive(Value a) const { return _epsilon<a; }
 		    ///Returns \c true if \c a is \e surely negative
 		    bool negative(Value a) const { return -_epsilon>a; }
 		    ///Returns \c true if \c a is \e surely non-zero
 		    bool nonZero(Value a) const { return positive(a)||negative(a); }
 		    ///@}
 		    ///Returns zero
 		    static Value zero() {return 0;}
 		  };
 		  ///Integer specialization of \ref Tolerance.
 		  ///Integer specialization of \ref Tolerance.
 		  ///\sa Tolerance
 		  template<>
 		  class Tolerance<int>
+		  {
 		  public:
 		    ///\e
 		    typedef int Value;
 		    ///\name Comparisons
 		    ///See \ref Tolerance for more details.
 		    ///@{
 		    ///Returns \c true if \c a is \e surely strictly less than \c b
 		    static bool less(Value a,Value b) { return a<b;}
 		    ///Returns \c true if \c a is \e surely different from \c b
 		    static bool different(Value a,Value b) { return a!=b; }
 		    ///Returns \c true if \c a is \e surely positive
 		    static bool positive(Value a) { return 0<a; }
 		    ///Returns \c true if \c a is \e surely negative
 		    static bool negative(Value a) { return 0>a; }
 		    ///Returns \c true if \c a is \e surely non-zero
 		    static bool nonZero(Value a) { return a!=0; }
 		    ///@}
 		    ///Returns zero
 		    static Value zero() {return 0;}
 		  };
 		  ///Unsigned integer specialization of \ref Tolerance.
 		  ///Unsigned integer specialization of \ref Tolerance.
 		  ///\sa Tolerance
 		  template<>
 		  class Tolerance<unsigned int>
+		  {
 		  public:
 		    ///\e
 		    typedef unsigned int Value;
 		    ///\name Comparisons
 		    ///See \ref Tolerance for more details.
 		    ///@{
 		    ///Returns \c true if \c a is \e surely strictly less than \c b
 		    static bool less(Value a,Value b) { return a<b;}
 		    ///Returns \c true if \c a is \e surely different from \c b
 		    static bool different(Value a,Value b) { return a!=b; }
 		    ///Returns \c true if \c a is \e surely positive
 		    static bool positive(Value a) { return 0<a; }
 		    ///Returns \c true if \c a is \e surely negative
 		    static bool negative(Value) { return false; }
 		    ///Returns \c true if \c a is \e surely non-zero
 		    static bool nonZero(Value a) { return a!=0; }
 		    ///@}
 		    ///Returns zero
 		    static Value zero() {return 0;}
 		  };
 		  ///Long integer specialization of \ref Tolerance.
 		  ///Long integer specialization of \ref Tolerance.
 		  ///\sa Tolerance
 		  template<>
 		  class Tolerance<long int>
+		  {
 		  public:
 		    ///\e
 		    typedef long int Value;
 		    ///\name Comparisons
 		    ///See \ref Tolerance for more details.
 		    ///@{
 		    ///Returns \c true if \c a is \e surely strictly less than \c b
 		    static bool less(Value a,Value b) { return a<b;}
 		    ///Returns \c true if \c a is \e surely different from \c b
 		    static bool different(Value a,Value b) { return a!=b; }
 		    ///Returns \c true if \c a is \e surely positive
 		    static bool positive(Value a) { return 0<a; }
 		    ///Returns \c true if \c a is \e surely negative
 		    static bool negative(Value a) { return 0>a; }
 		    ///Returns \c true if \c a is \e surely non-zero
 		    static bool nonZero(Value a) { return a!=0;}
 		    ///@}
 		    ///Returns zero
 		    static Value zero() {return 0;}
 		  };
 		  ///Unsigned long integer specialization of \ref Tolerance.
 		  ///Unsigned long integer specialization of \ref Tolerance.
 		  ///\sa Tolerance
 		  template<>
 		  class Tolerance<unsigned long int>
+		  {
 		  public:
 		    ///\e
 		    typedef unsigned long int Value;
 		    ///\name Comparisons
 		    ///See \ref Tolerance for more details.
 		    ///@{
 		    ///Returns \c true if \c a is \e surely strictly less than \c b
 		    static bool less(Value a,Value b) { return a<b;}
 		    ///Returns \c true if \c a is \e surely different from \c b
 		    static bool different(Value a,Value b) { return a!=b; }
 		    ///Returns \c true if \c a is \e surely positive
 		    static bool positive(Value a) { return 0<a; }
 		    ///Returns \c true if \c a is \e surely negative
 		    static bool negative(Value) { return false; }
 		    ///Returns \c true if \c a is \e surely non-zero
 		    static bool nonZero(Value a) { return a!=0;}
 		    ///@}
 		    ///Returns zero
 		    static Value zero() {return 0;}
 		  };
 		#if defined __GNUC__ && !defined __STRICT_ANSI__
 		  ///Long long integer specialization of \ref Tolerance.
 		  ///Long long integer specialization of \ref Tolerance.
 		  ///\warning This class (more exactly, type <tt>long long</tt>)
 		  ///is not ansi compatible.
 		  ///\sa Tolerance
 		  template<>
 		  class Tolerance<long long int>
+		  {
 		  public:
 		    ///\e
 		    typedef long long int Value;
 		    ///\name Comparisons
 		    ///See \ref Tolerance for more details.
 		    ///@{
 		    ///Returns \c true if \c a is \e surely strictly less than \c b
 		    static bool less(Value a,Value b) { return a<b;}
 		    ///Returns \c true if \c a is \e surely different from \c b
 		    static bool different(Value a,Value b) { return a!=b; }
 		    ///Returns \c true if \c a is \e surely positive
 		    static bool positive(Value a) { return 0<a; }
 		    ///Returns \c true if \c a is \e surely negative
 		    static bool negative(Value a) { return 0>a; }
 		    ///Returns \c true if \c a is \e surely non-zero
 		    static bool nonZero(Value a) { return a!=0;}
 		    ///@}
 		    ///Returns zero
 		    static Value zero() {return 0;}
 		  };
 		  ///Unsigned long long integer specialization of \ref Tolerance.
 		  ///Unsigned long long integer specialization of \ref Tolerance.
 		  ///\warning This class (more exactly, type <tt>unsigned long long</tt>)
 		  ///is not ansi compatible.
 		  ///\sa Tolerance
 		  template<>
 		  class Tolerance<unsigned long long int>
+		  {
 		  public:
 		    ///\e
 		    typedef unsigned long long int Value;
 		    ///\name Comparisons
 		    ///See \ref Tolerance for more details.
 		    ///@{
 		    ///Returns \c true if \c a is \e surely strictly less than \c b
 		    static bool less(Value a,Value b) { return a<b;}
 		    ///Returns \c true if \c a is \e surely different from \c b
 		    static bool different(Value a,Value b) { return a!=b; }
 		    ///Returns \c true if \c a is \e surely positive
 		    static bool positive(Value a) { return 0<a; }
 		    ///Returns \c true if \c a is \e surely negative
 		    static bool negative(Value) { return false; }
 		    ///Returns \c true if \c a is \e surely non-zero
 		    static bool nonZero(Value a) { return a!=0;}
 		    ///@}
 		    ///Returns zero
 		    static Value zero() {return 0;}
 		  };
 		#endif
 		  /// @}
 		} //namespace lemon
 		#endif //LEMON_TOLERANCE_H

test/dim_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#include <lemon/dim2.h>
 		#include <iostream>
 		#include "test_tools.h"
 		using namespace std;
 		using namespace lemon;
 		int main()
+		{
 		  cout << "Testing classes 'dim2::Point' and 'dim2::BoundingBox'." << endl;
 		  typedef dim2::Point<int> Point;
 		  Point p;
 		  check(p.size()==2, "Wrong vector initialization.");
 		  Point a(1,2);
 		  Point b(3,4);
 		  check(a[0]==1 && a[1]==2, "Wrong vector initialization.");
 		  p = a+b;
 		  check(p.x==4 && p.y==6, "Wrong vector addition.");
 		  p = a-b;
 		  check(p.x==-2 && p.y==-2, "Wrong vector subtraction.");
 		  check(a.normSquare()==5,"Wrong vector norm calculation.");
 		  check(a*b==11, "Wrong vector scalar product.");
 		  int l=2;
 		  p = a*l;
 		  check(p.x==2 && p.y==4, "Wrong vector multiplication by a scalar.");
 		  p = b/l;
 		  check(p.x==1 && p.y==2, "Wrong vector division by a scalar.");
 		  typedef dim2::BoundingBox<int> BB;
 		  BB box1;
 		  check(box1.empty(), "It should be empty.");
 		  box1.add(a);
 		  check(!box1.empty(), "It should not be empty.");
 		  box1.add(b);
 		  check(box1.bottomLeft().x==1 &&
 		        box1.bottomLeft().y==2 &&
 		        box1.topRight().x==3 &&
 		        box1.topRight().y==4,
 		        "Wrong addition of points to box.");
 		  p.x=2; p.y=3;
 		  check(box1.inside(p), "It should be inside.");
 		  p.x=1; p.y=3;
 		  check(box1.inside(p), "It should be inside.");
 		  p.x=0; p.y=3;
 		  check(!box1.inside(p), "It should not be inside.");
 		  BB box2(p);
 		  check(!box2.empty(),
 		        "It should not be empty. Constructed from 1 point.");
 		  box2.add(box1);
 		  check(box2.inside(p),
 		        "It should be inside. Incremented a box with another one.");
 		  return 0;
+		}

test/maps_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#include <deque>
 		#include <set>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/maps.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		using namespace lemon::concepts;
 		struct A {};
 		inline bool operator<(A, A) { return true; }
 		struct B {};
 		class F {
 		public:
 		  typedef A argument_type;
 		  typedef B result_type;
 		  B operator()(const A &) const {return B();}
 		};
 		int func(A) {return 3;}
 		int binc(int, B) {return 4;}
 		typedef ReadMap<A,double> DoubleMap;
 		typedef ReadWriteMap<A, double> WriteDoubleMap;
 		typedef ReadMap<A,bool> BoolMap;
 		typedef ReadWriteMap<A, bool> BoolWriteMap;
 		int main()
 		{ // checking graph components
 		  checkConcept<ReadMap<A,B>, ReadMap<A,B> >();
 		  checkConcept<WriteMap<A,B>, WriteMap<A,B> >();
 		  checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();
 		  checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();
 		  checkConcept<ReadMap<A,double>, AddMap<DoubleMap,DoubleMap> >();
 		  checkConcept<ReadMap<A,double>, SubMap<DoubleMap,DoubleMap> >();
 		  checkConcept<ReadMap<A,double>, MulMap<DoubleMap,DoubleMap> >();
 		  checkConcept<ReadMap<A,double>, DivMap<DoubleMap,DoubleMap> >();
 		  checkConcept<ReadMap<A,double>, NegMap<DoubleMap> >();
 		  checkConcept<ReadWriteMap<A,double>, NegWriteMap<WriteDoubleMap> >();
 		  checkConcept<ReadMap<A,double>, AbsMap<DoubleMap> >();
 		  checkConcept<ReadMap<A,double>, ShiftMap<DoubleMap> >();
 		  checkConcept<ReadWriteMap<A,double>, ShiftWriteMap<WriteDoubleMap> >();
 		  checkConcept<ReadMap<A,double>, ScaleMap<DoubleMap> >();
 		  checkConcept<ReadWriteMap<A,double>, ScaleWriteMap<WriteDoubleMap> >();
 		  checkConcept<ReadMap<A,double>, ForkMap<DoubleMap, DoubleMap> >();
 		  checkConcept<ReadWriteMap<A,double>,
 		    ForkWriteMap<WriteDoubleMap, WriteDoubleMap> >();
 		  checkConcept<ReadMap<B,double>, ComposeMap<DoubleMap,ReadMap<B,A> > >();
 		  checkConcept<ReadMap<A,B>, FunctorMap<F, A, B> >();
 		  checkConcept<ReadMap<A, bool>, NotMap<BoolMap> >();
 		  checkConcept<ReadWriteMap<A, bool>, NotWriteMap<BoolWriteMap> >();
 		  checkConcept<WriteMap<A, bool>, StoreBoolMap<A*> >();
 		  checkConcept<WriteMap<A, bool>, BackInserterBoolMap<std::deque<A> > >();
 		  checkConcept<WriteMap<A, bool>, FrontInserterBoolMap<std::deque<A> > >();
 		  checkConcept<WriteMap<A, bool>, InserterBoolMap<std::set<A> > >();
 		  checkConcept<WriteMap<A, bool>, FillBoolMap<WriteMap<A, B> > >();
 		  checkConcept<WriteMap<A, bool>, SettingOrderBoolMap<WriteMap<A, int> > >();
 		  int a;
 		  a=mapFunctor(constMap<A,int>(2))(A());
 		  check(a==2,"Something is wrong with mapFunctor");
 		  B b;
 		  b=functorMap(F())[A()];
 		  a=functorMap(&func)[A()];
 		  check(a==3,"Something is wrong with functorMap");
 		  a=combineMap(constMap<B, int, 1>(), identityMap<B>(), &binc)[B()];
 		  check(a==4,"Something is wrong with combineMap");
 		  std::cout << __FILE__ ": All tests passed.\n";
 		  return 0;
+		}

test/random_test.cc

Show inline comments

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2007
 * Copyright (C) 2003-2008
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#include <lemon/random.h>
#include "test_tools.h"

///\file \brief Test cases for random.h
///
///\todo To be extended
///

int main()
{
  double a=lemon::rnd();
  check(a<1.0&&a>0.0,"This should be in [0,1)");
  a=lemon::rnd.gauss();
  a=lemon::rnd.gamma(3.45,0);
  a=lemon::rnd.gamma(4);
  //Does gamma work with integer k?
  a=lemon::rnd.gamma(4.0,0);
}

test/test_tools.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
-		 * Copyright (C) 2003-2007
+		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_TEST_TEST_TOOLS_H
 		#define LEMON_TEST_TEST_TOOLS_H
 		#include <iostream>
 		//! \ingroup misc
 		//! \file
 		//! \brief Some utilities to write test programs.
 		///If \c rc is fail, writes an error message end exit.
 		///If \c rc is fail, writes an error message end exit.
 		///The error message contains the file name and the line number of the
 		///source code in a standard from, which makes it possible to go there
 		///using good source browsers like e.g. \c emacs.
 		///
 		///For example
 		///\code check(0==1,"This is obviously false.");\endcode will
 		///print this (and then exits).
 		///\verbatim graph_test.cc:123: error: This is obviously false. \endverbatim
 		///
 		///\todo It should be in \c error.h
 		#define check(rc, msg) \
 		  if(!(rc)) { \
 		    std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
 		    abort(); \
 		  } else { } \
 		#endif

test/test_tools_fail.cc

Show inline comments

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2007
 * Copyright (C) 2003-2008
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#include "test_tools.h"

int main() 
{
  check(false, "Don't panic. Failing is the right behaviour here.");
  return 0;
}

test/test_tools_pass.cc

Show inline comments

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2007
 * Copyright (C) 2003-2008
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#include "test_tools.h"

int main() 
{
  check(true, "It should pass.");
  return 0;
}

0 comments (0 inline)

RhodeCode

Login to your account

1	1	/* -- C++ --
2	2	*
3	3	* This file is a part of LEMON, a generic C++ optimization library
4	4	*
5		* Copyright (C) 2003-~~2007~~
	5	* Copyright (C) 2003-2008
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
8	8	*
9	9	* Permission to use, modify and distribute this software is granted
10	10	* provided that this copyright notice appears in all copies. For
11	11	* precise terms see the accompanying LICENSE file.
12	12	*
13	13	* This software is provided "AS IS" with no warranty of any kind,
14	14	* express or implied, and with no claim as to its suitability for any
15	15	* purpose.
16	16	*
17	17	*/
18	18
19	19	///\file
20	20	///\brief Instantiation of the Random class.
21	21
22	22	#include <lemon/random.h>
23	23
24	24	namespace lemon {
25	25	/// \brief Global random number generator instance
26	26	///
27	27	/// A global Mersenne Twister random number generator instance.
28	28	Random rnd;
29	29	}