diff options
Diffstat (limited to 'extern/quadriflow/3rd/lemon-1.3.1/lemon/bits')
17 files changed, 5774 insertions, 0 deletions
diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/alteration_notifier.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/alteration_notifier.h new file mode 100644 index 00000000000..d14fe3634dd --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/alteration_notifier.h @@ -0,0 +1,472 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2013 + * 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_ALTERATION_NOTIFIER_H +#define LEMON_BITS_ALTERATION_NOTIFIER_H + +#include <vector> +#include <list> + +#include <lemon/core.h> +#include <lemon/bits/lock.h> + +//\ingroup graphbits +//\file +//\brief Observer notifier for graph alteration observers. + +namespace lemon { + + // \ingroup graphbits + // + // \brief Notifier class to notify observes about alterations in + // a container. + // + // The simple graphs can be refered as two containers: a node container + // and an edge container. But they do not store values directly, they + // are just key continars for more value containers, which are the + // node and edge maps. + // + // The node and edge sets of the graphs can be changed as we add or erase + // nodes and edges in the graph. LEMON would like to handle easily + // that the node and edge maps should contain values for all nodes or + // edges. If we want to check on every indicing if the map contains + // the current indicing key that cause a drawback in the performance + // in the library. We use another solution: we notify all maps about + // an alteration in the graph, which cause only drawback on the + // alteration of the graph. + // + // This class provides an interface to a node or edge container. + // The first() and next() member functions make possible + // to iterate on the keys of the container. + // The id() function returns an integer id for each key. + // The maxId() function gives back an upper bound of the ids. + // + // For the proper functonality of this class, we should notify it + // about each alteration in the container. The alterations have four type: + // add(), erase(), build() and clear(). The add() and + // erase() signal that only one or few items added or erased to or + // from the graph. If all items are erased from the graph or if a new graph + // is built from an empty graph, then it can be signaled with the + // clear() and build() members. Important rule that if we erase items + // from graphs we should first signal the alteration and after that erase + // them from the container, on the other way on item addition we should + // first extend the container and just after that signal the alteration. + // + // The alteration can be observed with a class inherited from the + // ObserverBase nested class. The signals can be handled with + // overriding the virtual functions defined in the base class. The + // observer base can be attached to the notifier with the + // attach() member and can be detached with detach() function. The + // alteration handlers should not call any function which signals + // an other alteration in the same notifier and should not + // detach any observer from the notifier. + // + // Alteration observers try to be exception safe. If an add() or + // a clear() function throws an exception then the remaining + // observeres will not be notified and the fulfilled additions will + // be rolled back by calling the erase() or clear() functions. + // Hence erase() and clear() should not throw exception. + // Actullay, they can throw only \ref ImmediateDetach exception, + // which detach the observer from the notifier. + // + // There are some cases, when the alteration observing is not completly + // reliable. If we want to carry out the node degree in the graph + // as in the \ref InDegMap and we use the reverseArc(), then it cause + // unreliable functionality. Because the alteration observing signals + // only erasing and adding but not the reversing, it will stores bad + // degrees. Apart form that the subgraph adaptors cannot even signal + // the alterations because just a setting in the filter map can modify + // the graph and this cannot be watched in any way. + // + // \param _Container The container which is observed. + // \param _Item The item type which is obserbved. + + template <typename _Container, typename _Item> + class AlterationNotifier { + public: + + typedef True Notifier; + + typedef _Container Container; + typedef _Item Item; + + // \brief Exception which can be called from clear() and + // erase(). + // + // From the clear() and erase() function only this + // exception is allowed to throw. The exception immediatly + // detaches the current observer from the notifier. Because the + // clear() and erase() should not throw other exceptions + // it can be used to invalidate the observer. + struct ImmediateDetach {}; + + // \brief ObserverBase is the base class for the observers. + // + // ObserverBase is the abstract base class for the observers. + // It will be notified about an item was inserted into or + // erased from the graph. + // + // The observer interface contains some pure virtual functions + // to override. The add() and erase() functions are + // to notify the oberver when one item is added or erased. + // + // The build() and clear() members are to notify the observer + // about the container is built from an empty container or + // is cleared to an empty container. + class ObserverBase { + protected: + typedef AlterationNotifier Notifier; + + friend class AlterationNotifier; + + // \brief Default constructor. + // + // Default constructor for ObserverBase. + ObserverBase() : _notifier(0) {} + + // \brief Constructor which attach the observer into notifier. + // + // Constructor which attach the observer into notifier. + ObserverBase(AlterationNotifier& nf) { + attach(nf); + } + + // \brief Constructor which attach the obserever to the same notifier. + // + // Constructor which attach the obserever to the same notifier as + // the other observer is attached to. + ObserverBase(const ObserverBase& copy) { + if (copy.attached()) { + attach(*copy.notifier()); + } + } + + // \brief Destructor + virtual ~ObserverBase() { + if (attached()) { + detach(); + } + } + + // \brief Attaches the observer into an AlterationNotifier. + // + // This member attaches the observer into an AlterationNotifier. + void attach(AlterationNotifier& nf) { + nf.attach(*this); + } + + // \brief Detaches the observer into an AlterationNotifier. + // + // This member detaches the observer from an AlterationNotifier. + void detach() { + _notifier->detach(*this); + } + + // \brief Gives back a pointer to the notifier which the map + // attached into. + // + // This function gives back a pointer to the notifier which the map + // attached into. + Notifier* notifier() const { return const_cast<Notifier*>(_notifier); } + + // Gives back true when the observer is attached into a notifier. + bool attached() const { return _notifier != 0; } + + private: + + ObserverBase& operator=(const ObserverBase& copy); + + protected: + + Notifier* _notifier; + typename std::list<ObserverBase*>::iterator _index; + + // \brief The member function to notificate the observer about an + // item is added to the container. + // + // The add() member function notificates the observer about an item + // is added to the container. It have to be overrided in the + // subclasses. + virtual void add(const Item&) = 0; + + // \brief The member function to notificate the observer about + // more item is added to the container. + // + // The add() member function notificates the observer about more item + // is added to the container. It have to be overrided in the + // subclasses. + virtual void add(const std::vector<Item>& items) = 0; + + // \brief The member function to notificate the observer about an + // item is erased from the container. + // + // The erase() member function notificates the observer about an + // item is erased from the container. It have to be overrided in + // the subclasses. + virtual void erase(const Item&) = 0; + + // \brief The member function to notificate the observer about + // more item is erased from the container. + // + // The erase() member function notificates the observer about more item + // is erased from the container. It have to be overrided in the + // subclasses. + virtual void erase(const std::vector<Item>& items) = 0; + + // \brief The member function to notificate the observer about the + // container is built. + // + // The build() member function notificates the observer about the + // container is built from an empty container. It have to be + // overrided in the subclasses. + virtual void build() = 0; + + // \brief The member function to notificate the observer about all + // items are erased from the container. + // + // The clear() member function notificates the observer about all + // items are erased from the container. It have to be overrided in + // the subclasses. + virtual void clear() = 0; + + }; + + protected: + + const Container* container; + + typedef std::list<ObserverBase*> Observers; + Observers _observers; + lemon::bits::Lock _lock; + + public: + + // \brief Default constructor. + // + // The default constructor of the AlterationNotifier. + // It creates an empty notifier. + AlterationNotifier() + : container(0) {} + + // \brief Constructor. + // + // Constructor with the observed container parameter. + AlterationNotifier(const Container& _container) + : container(&_container) {} + + // \brief Copy Constructor of the AlterationNotifier. + // + // Copy constructor of the AlterationNotifier. + // It creates only an empty notifier because the copiable + // notifier's observers have to be registered still into that notifier. + AlterationNotifier(const AlterationNotifier& _notifier) + : container(_notifier.container) {} + + // \brief Destructor. + // + // Destructor of the AlterationNotifier. + ~AlterationNotifier() { + typename Observers::iterator it; + for (it = _observers.begin(); it != _observers.end(); ++it) { + (*it)->_notifier = 0; + } + } + + // \brief Sets the container. + // + // Sets the container. + void setContainer(const Container& _container) { + container = &_container; + } + + protected: + + AlterationNotifier& operator=(const AlterationNotifier&); + + public: + + // \brief First item in the container. + // + // Returns the first item in the container. It is + // for start the iteration on the container. + void first(Item& item) const { + container->first(item); + } + + // \brief Next item in the container. + // + // Returns the next item in the container. It is + // for iterate on the container. + void next(Item& item) const { + container->next(item); + } + + // \brief Returns the id of the item. + // + // Returns the id of the item provided by the container. + int id(const Item& item) const { + return container->id(item); + } + + // \brief Returns the maximum id of the container. + // + // Returns the maximum id of the container. + int maxId() const { + return container->maxId(Item()); + } + + protected: + + void attach(ObserverBase& observer) { + _lock.lock(); + observer._index = _observers.insert(_observers.begin(), &observer); + observer._notifier = this; + _lock.unlock(); + } + + void detach(ObserverBase& observer) { + _lock.lock(); + _observers.erase(observer._index); + observer._index = _observers.end(); + observer._notifier = 0; + _lock.unlock(); + } + + public: + + // \brief Notifies all the registed observers about an item added to + // the container. + // + // It notifies all the registed observers about an item added to + // the container. + void add(const Item& item) { + typename Observers::reverse_iterator it; + try { + for (it = _observers.rbegin(); it != _observers.rend(); ++it) { + (*it)->add(item); + } + } catch (...) { + typename Observers::iterator jt; + for (jt = it.base(); jt != _observers.end(); ++jt) { + (*jt)->erase(item); + } + throw; + } + } + + // \brief Notifies all the registed observers about more item added to + // the container. + // + // It notifies all the registed observers about more item added to + // the container. + void add(const std::vector<Item>& items) { + typename Observers::reverse_iterator it; + try { + for (it = _observers.rbegin(); it != _observers.rend(); ++it) { + (*it)->add(items); + } + } catch (...) { + typename Observers::iterator jt; + for (jt = it.base(); jt != _observers.end(); ++jt) { + (*jt)->erase(items); + } + throw; + } + } + + // \brief Notifies all the registed observers about an item erased from + // the container. + // + // It notifies all the registed observers about an item erased from + // the container. + void erase(const Item& item) throw() { + typename Observers::iterator it = _observers.begin(); + while (it != _observers.end()) { + try { + (*it)->erase(item); + ++it; + } catch (const ImmediateDetach&) { + (*it)->_index = _observers.end(); + (*it)->_notifier = 0; + it = _observers.erase(it); + } + } + } + + // \brief Notifies all the registed observers about more item erased + // from the container. + // + // It notifies all the registed observers about more item erased from + // the container. + void erase(const std::vector<Item>& items) { + typename Observers::iterator it = _observers.begin(); + while (it != _observers.end()) { + try { + (*it)->erase(items); + ++it; + } catch (const ImmediateDetach&) { + (*it)->_index = _observers.end(); + (*it)->_notifier = 0; + it = _observers.erase(it); + } + } + } + + // \brief Notifies all the registed observers about the container is + // built. + // + // Notifies all the registed observers about the container is built + // from an empty container. + void build() { + typename Observers::reverse_iterator it; + try { + for (it = _observers.rbegin(); it != _observers.rend(); ++it) { + (*it)->build(); + } + } catch (...) { + typename Observers::iterator jt; + for (jt = it.base(); jt != _observers.end(); ++jt) { + (*jt)->clear(); + } + throw; + } + } + + // \brief Notifies all the registed observers about all items are + // erased. + // + // Notifies all the registed observers about all items are erased + // from the container. + void clear() { + typename Observers::iterator it = _observers.begin(); + while (it != _observers.end()) { + try { + (*it)->clear(); + ++it; + } catch (const ImmediateDetach&) { + (*it)->_index = _observers.end(); + (*it)->_notifier = 0; + it = _observers.erase(it); + } + } + } + }; + +} + +#endif diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/array_map.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/array_map.h new file mode 100644 index 00000000000..355ee008246 --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/array_map.h @@ -0,0 +1,351 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2013 + * 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_ARRAY_MAP_H +#define LEMON_BITS_ARRAY_MAP_H + +#include <memory> + +#include <lemon/bits/traits.h> +#include <lemon/bits/alteration_notifier.h> +#include <lemon/concept_check.h> +#include <lemon/concepts/maps.h> + +// \ingroup graphbits +// \file +// \brief Graph map based on the array storage. + +namespace lemon { + + // \ingroup graphbits + // + // \brief Graph map based on the array storage. + // + // The ArrayMap template class is graph map structure that automatically + // updates the map when a key is added to or erased from the graph. + // This map uses the allocators to implement the container functionality. + // + // The template parameters are the Graph, the current Item type and + // the Value type of the map. + template <typename _Graph, typename _Item, typename _Value> + class ArrayMap + : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { + public: + // The graph type. + typedef _Graph GraphType; + // The item type. + typedef _Item Item; + // The reference map tag. + typedef True ReferenceMapTag; + + // The key type of the map. + typedef _Item Key; + // The value type of the map. + typedef _Value Value; + + // The const reference type of the map. + typedef const _Value& ConstReference; + // The reference type of the map. + typedef _Value& Reference; + + // The map type. + typedef ArrayMap Map; + + // The notifier type. + typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier; + + private: + + // The MapBase of the Map which imlements the core regisitry function. + typedef typename Notifier::ObserverBase Parent; + + typedef std::allocator<Value> Allocator; + + public: + + // \brief Graph initialized map constructor. + // + // Graph initialized map constructor. + explicit ArrayMap(const GraphType& graph) { + Parent::attach(graph.notifier(Item())); + allocate_memory(); + Notifier* nf = Parent::notifier(); + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + int id = nf->id(it);; + allocator.construct(&(values[id]), Value()); + } + } + + // \brief Constructor to use default value to initialize the map. + // + // It constructs a map and initialize all of the the map. + ArrayMap(const GraphType& graph, const Value& value) { + Parent::attach(graph.notifier(Item())); + allocate_memory(); + Notifier* nf = Parent::notifier(); + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + int id = nf->id(it);; + allocator.construct(&(values[id]), value); + } + } + + private: + // \brief Constructor to copy a map of the same map type. + // + // Constructor to copy a map of the same map type. + ArrayMap(const ArrayMap& copy) : Parent() { + if (copy.attached()) { + attach(*copy.notifier()); + } + capacity = copy.capacity; + if (capacity == 0) return; + values = allocator.allocate(capacity); + Notifier* nf = Parent::notifier(); + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + int id = nf->id(it);; + allocator.construct(&(values[id]), copy.values[id]); + } + } + + // \brief Assign operator. + // + // This operator assigns for each item in the map the + // value mapped to the same item in the copied map. + // The parameter map should be indiced with the same + // itemset because this assign operator does not change + // the container of the map. + ArrayMap& operator=(const ArrayMap& cmap) { + return operator=<ArrayMap>(cmap); + } + + + // \brief Template assign operator. + // + // The given parameter should conform to the ReadMap + // concecpt and could be indiced by the current item set of + // the NodeMap. In this case the value for each item + // is assigned by the value of the given ReadMap. + template <typename CMap> + ArrayMap& operator=(const CMap& cmap) { + checkConcept<concepts::ReadMap<Key, _Value>, CMap>(); + const typename Parent::Notifier* nf = Parent::notifier(); + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + set(it, cmap[it]); + } + return *this; + } + + public: + // \brief The destructor of the map. + // + // The destructor of the map. + virtual ~ArrayMap() { + if (attached()) { + clear(); + detach(); + } + } + + protected: + + using Parent::attach; + using Parent::detach; + using Parent::attached; + + public: + + // \brief The subscript operator. + // + // The subscript operator. The map can be subscripted by the + // actual keys of the graph. + Value& operator[](const Key& key) { + int id = Parent::notifier()->id(key); + return values[id]; + } + + // \brief The const subscript operator. + // + // The const subscript operator. The map can be subscripted by the + // actual keys of the graph. + const Value& operator[](const Key& key) const { + int id = Parent::notifier()->id(key); + return values[id]; + } + + // \brief Setter function of the map. + // + // Setter function of the map. Equivalent with map[key] = val. + // This is a compatibility feature with the not dereferable maps. + void set(const Key& key, const Value& val) { + (*this)[key] = val; + } + + protected: + + // \brief Adds a new key to the map. + // + // It adds a new key to the map. It is called by the observer notifier + // and it overrides the add() member function of the observer base. + virtual void add(const Key& key) { + Notifier* nf = Parent::notifier(); + int id = nf->id(key); + if (id >= capacity) { + int new_capacity = (capacity == 0 ? 1 : capacity); + while (new_capacity <= id) { + new_capacity <<= 1; + } + Value* new_values = allocator.allocate(new_capacity); + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + int jd = nf->id(it);; + if (id != jd) { + allocator.construct(&(new_values[jd]), values[jd]); + allocator.destroy(&(values[jd])); + } + } + if (capacity != 0) allocator.deallocate(values, capacity); + values = new_values; + capacity = new_capacity; + } + allocator.construct(&(values[id]), Value()); + } + + // \brief Adds more new keys to the map. + // + // It adds more new keys to the map. It is called by the observer notifier + // and it overrides the add() member function of the observer base. + virtual void add(const std::vector<Key>& keys) { + Notifier* nf = Parent::notifier(); + int max_id = -1; + for (int i = 0; i < int(keys.size()); ++i) { + int id = nf->id(keys[i]); + if (id > max_id) { + max_id = id; + } + } + if (max_id >= capacity) { + int new_capacity = (capacity == 0 ? 1 : capacity); + while (new_capacity <= max_id) { + new_capacity <<= 1; + } + Value* new_values = allocator.allocate(new_capacity); + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + int id = nf->id(it); + bool found = false; + for (int i = 0; i < int(keys.size()); ++i) { + int jd = nf->id(keys[i]); + if (id == jd) { + found = true; + break; + } + } + if (found) continue; + allocator.construct(&(new_values[id]), values[id]); + allocator.destroy(&(values[id])); + } + if (capacity != 0) allocator.deallocate(values, capacity); + values = new_values; + capacity = new_capacity; + } + for (int i = 0; i < int(keys.size()); ++i) { + int id = nf->id(keys[i]); + allocator.construct(&(values[id]), Value()); + } + } + + // \brief Erase a key from the map. + // + // Erase a key from the map. It is called by the observer notifier + // and it overrides the erase() member function of the observer base. + virtual void erase(const Key& key) { + int id = Parent::notifier()->id(key); + allocator.destroy(&(values[id])); + } + + // \brief Erase more keys from the map. + // + // Erase more keys from the map. It is called by the observer notifier + // and it overrides the erase() member function of the observer base. + virtual void erase(const std::vector<Key>& keys) { + for (int i = 0; i < int(keys.size()); ++i) { + int id = Parent::notifier()->id(keys[i]); + allocator.destroy(&(values[id])); + } + } + + // \brief Builds the map. + // + // It builds the map. It is called by the observer notifier + // and it overrides the build() member function of the observer base. + virtual void build() { + Notifier* nf = Parent::notifier(); + allocate_memory(); + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + int id = nf->id(it);; + allocator.construct(&(values[id]), Value()); + } + } + + // \brief Clear the map. + // + // It erase all items from the map. It is called by the observer notifier + // and it overrides the clear() member function of the observer base. + virtual void clear() { + Notifier* nf = Parent::notifier(); + if (capacity != 0) { + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + int id = nf->id(it); + allocator.destroy(&(values[id])); + } + allocator.deallocate(values, capacity); + capacity = 0; + } + } + + private: + + void allocate_memory() { + int max_id = Parent::notifier()->maxId(); + if (max_id == -1) { + capacity = 0; + values = 0; + return; + } + capacity = 1; + while (capacity <= max_id) { + capacity <<= 1; + } + values = allocator.allocate(capacity); + } + + int capacity; + Value* values; + Allocator allocator; + + }; + +} + +#endif diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/bezier.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/bezier.h new file mode 100644 index 00000000000..9d8d1413d07 --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/bezier.h @@ -0,0 +1,174 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2013 + * 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_BEZIER_H +#define LEMON_BEZIER_H + +//\ingroup misc +//\file +//\brief Classes to compute with Bezier curves. +// +//Up to now this file is used internally by \ref graph_to_eps.h + +#include<lemon/dim2.h> + +namespace lemon { + namespace dim2 { + +class BezierBase { +public: + typedef lemon::dim2::Point<double> Point; +protected: + static Point conv(Point x,Point y,double t) {return (1-t)*x+t*y;} +}; + +class Bezier1 : public BezierBase +{ +public: + Point p1,p2; + + Bezier1() {} + Bezier1(Point _p1, Point _p2) :p1(_p1), p2(_p2) {} + + Point operator()(double t) const + { + // return conv(conv(p1,p2,t),conv(p2,p3,t),t); + return conv(p1,p2,t); + } + Bezier1 before(double t) const + { + return Bezier1(p1,conv(p1,p2,t)); + } + + Bezier1 after(double t) const + { + return Bezier1(conv(p1,p2,t),p2); + } + + Bezier1 revert() const { return Bezier1(p2,p1);} + Bezier1 operator()(double a,double b) const { return before(b).after(a/b); } + Point grad() const { return p2-p1; } + Point norm() const { return rot90(p2-p1); } + Point grad(double) const { return grad(); } + Point norm(double t) const { return rot90(grad(t)); } +}; + +class Bezier2 : public BezierBase +{ +public: + Point p1,p2,p3; + + Bezier2() {} + Bezier2(Point _p1, Point _p2, Point _p3) :p1(_p1), p2(_p2), p3(_p3) {} + Bezier2(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,.5)), p3(b.p2) {} + Point operator()(double t) const + { + // return conv(conv(p1,p2,t),conv(p2,p3,t),t); + return ((1-t)*(1-t))*p1+(2*(1-t)*t)*p2+(t*t)*p3; + } + Bezier2 before(double t) const + { + Point q(conv(p1,p2,t)); + Point r(conv(p2,p3,t)); + return Bezier2(p1,q,conv(q,r,t)); + } + + Bezier2 after(double t) const + { + Point q(conv(p1,p2,t)); + Point r(conv(p2,p3,t)); + return Bezier2(conv(q,r,t),r,p3); + } + Bezier2 revert() const { return Bezier2(p3,p2,p1);} + Bezier2 operator()(double a,double b) const { return before(b).after(a/b); } + Bezier1 grad() const { return Bezier1(2.0*(p2-p1),2.0*(p3-p2)); } + Bezier1 norm() const { return Bezier1(2.0*rot90(p2-p1),2.0*rot90(p3-p2)); } + Point grad(double t) const { return grad()(t); } + Point norm(double t) const { return rot90(grad(t)); } +}; + +class Bezier3 : public BezierBase +{ +public: + Point p1,p2,p3,p4; + + Bezier3() {} + Bezier3(Point _p1, Point _p2, Point _p3, Point _p4) + : p1(_p1), p2(_p2), p3(_p3), p4(_p4) {} + Bezier3(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,1.0/3.0)), + p3(conv(b.p1,b.p2,2.0/3.0)), p4(b.p2) {} + Bezier3(const Bezier2 &b) : p1(b.p1), p2(conv(b.p1,b.p2,2.0/3.0)), + p3(conv(b.p2,b.p3,1.0/3.0)), p4(b.p3) {} + + Point operator()(double t) const + { + // return Bezier2(conv(p1,p2,t),conv(p2,p3,t),conv(p3,p4,t))(t); + return ((1-t)*(1-t)*(1-t))*p1+(3*t*(1-t)*(1-t))*p2+ + (3*t*t*(1-t))*p3+(t*t*t)*p4; + } + Bezier3 before(double t) const + { + Point p(conv(p1,p2,t)); + Point q(conv(p2,p3,t)); + Point r(conv(p3,p4,t)); + Point a(conv(p,q,t)); + Point b(conv(q,r,t)); + Point c(conv(a,b,t)); + return Bezier3(p1,p,a,c); + } + + Bezier3 after(double t) const + { + Point p(conv(p1,p2,t)); + Point q(conv(p2,p3,t)); + Point r(conv(p3,p4,t)); + Point a(conv(p,q,t)); + Point b(conv(q,r,t)); + Point c(conv(a,b,t)); + return Bezier3(c,b,r,p4); + } + Bezier3 revert() const { return Bezier3(p4,p3,p2,p1);} + Bezier3 operator()(double a,double b) const { return before(b).after(a/b); } + Bezier2 grad() const { return Bezier2(3.0*(p2-p1),3.0*(p3-p2),3.0*(p4-p3)); } + Bezier2 norm() const { return Bezier2(3.0*rot90(p2-p1), + 3.0*rot90(p3-p2), + 3.0*rot90(p4-p3)); } + Point grad(double t) const { return grad()(t); } + Point norm(double t) const { return rot90(grad(t)); } + + template<class R,class F,class S,class D> + R recSplit(F &_f,const S &_s,D _d) const + { + const Point a=(p1+p2)/2; + const Point b=(p2+p3)/2; + const Point c=(p3+p4)/2; + const Point d=(a+b)/2; + const Point e=(b+c)/2; + // const Point f=(d+e)/2; + R f1=_f(Bezier3(p1,a,d,e),_d); + R f2=_f(Bezier3(e,d,c,p4),_d); + return _s(f1,f2); + } + +}; + + +} //END OF NAMESPACE dim2 +} //END OF NAMESPACE lemon + +#endif // LEMON_BEZIER_H diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/default_map.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/default_map.h new file mode 100644 index 00000000000..23728e427ad --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/default_map.h @@ -0,0 +1,182 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2013 + * 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_DEFAULT_MAP_H +#define LEMON_BITS_DEFAULT_MAP_H + +#include <lemon/config.h> +#include <lemon/bits/array_map.h> +#include <lemon/bits/vector_map.h> +//#include <lemon/bits/debug_map.h> + +//\ingroup graphbits +//\file +//\brief Graph maps that construct and destruct their elements dynamically. + +namespace lemon { + + + //#ifndef LEMON_USE_DEBUG_MAP + + template <typename _Graph, typename _Item, typename _Value> + struct DefaultMapSelector { + typedef ArrayMap<_Graph, _Item, _Value> Map; + }; + + // bool + template <typename _Graph, typename _Item> + struct DefaultMapSelector<_Graph, _Item, bool> { + typedef VectorMap<_Graph, _Item, bool> Map; + }; + + // char + template <typename _Graph, typename _Item> + struct DefaultMapSelector<_Graph, _Item, char> { + typedef VectorMap<_Graph, _Item, char> Map; + }; + + template <typename _Graph, typename _Item> + struct DefaultMapSelector<_Graph, _Item, signed char> { + typedef VectorMap<_Graph, _Item, signed char> Map; + }; + + template <typename _Graph, typename _Item> + struct DefaultMapSelector<_Graph, _Item, unsigned char> { + typedef VectorMap<_Graph, _Item, unsigned char> Map; + }; + + + // int + template <typename _Graph, typename _Item> + struct DefaultMapSelector<_Graph, _Item, signed int> { + typedef VectorMap<_Graph, _Item, signed int> Map; + }; + + template <typename _Graph, typename _Item> + struct DefaultMapSelector<_Graph, _Item, unsigned int> { + typedef VectorMap<_Graph, _Item, unsigned int> Map; + }; + + + // short + template <typename _Graph, typename _Item> + struct DefaultMapSelector<_Graph, _Item, signed short> { + typedef VectorMap<_Graph, _Item, signed short> Map; + }; + + template <typename _Graph, typename _Item> + struct DefaultMapSelector<_Graph, _Item, unsigned short> { + typedef VectorMap<_Graph, _Item, unsigned short> Map; + }; + + + // long + template <typename _Graph, typename _Item> + struct DefaultMapSelector<_Graph, _Item, signed long> { + typedef VectorMap<_Graph, _Item, signed long> Map; + }; + + template <typename _Graph, typename _Item> + struct DefaultMapSelector<_Graph, _Item, unsigned long> { + typedef VectorMap<_Graph, _Item, unsigned long> Map; + }; + + +#if defined LEMON_HAVE_LONG_LONG + + // long long + template <typename _Graph, typename _Item> + struct DefaultMapSelector<_Graph, _Item, signed long long> { + typedef VectorMap<_Graph, _Item, signed long long> Map; + }; + + template <typename _Graph, typename _Item> + struct DefaultMapSelector<_Graph, _Item, unsigned long long> { + typedef VectorMap<_Graph, _Item, unsigned long long> Map; + }; + +#endif + + + // float + template <typename _Graph, typename _Item> + struct DefaultMapSelector<_Graph, _Item, float> { + typedef VectorMap<_Graph, _Item, float> Map; + }; + + + // double + template <typename _Graph, typename _Item> + struct DefaultMapSelector<_Graph, _Item, double> { + typedef VectorMap<_Graph, _Item, double> Map; + }; + + + // long double + template <typename _Graph, typename _Item> + struct DefaultMapSelector<_Graph, _Item, long double> { + typedef VectorMap<_Graph, _Item, long double> Map; + }; + + + // pointer + template <typename _Graph, typename _Item, typename _Ptr> + struct DefaultMapSelector<_Graph, _Item, _Ptr*> { + typedef VectorMap<_Graph, _Item, _Ptr*> Map; + }; + +// #else + +// template <typename _Graph, typename _Item, typename _Value> +// struct DefaultMapSelector { +// typedef DebugMap<_Graph, _Item, _Value> Map; +// }; + +// #endif + + // DefaultMap class + template <typename _Graph, typename _Item, typename _Value> + class DefaultMap + : public DefaultMapSelector<_Graph, _Item, _Value>::Map { + typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent; + + public: + typedef DefaultMap<_Graph, _Item, _Value> Map; + + typedef typename Parent::GraphType GraphType; + typedef typename Parent::Value Value; + + explicit DefaultMap(const GraphType& graph) : Parent(graph) {} + DefaultMap(const GraphType& graph, const Value& value) + : Parent(graph, value) {} + + DefaultMap& operator=(const DefaultMap& cmap) { + return operator=<DefaultMap>(cmap); + } + + template <typename CMap> + DefaultMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + + }; + +} + +#endif diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/edge_set_extender.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/edge_set_extender.h new file mode 100644 index 00000000000..364ca2ee6a9 --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/edge_set_extender.h @@ -0,0 +1,627 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2013 + * 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_EDGE_SET_EXTENDER_H +#define LEMON_BITS_EDGE_SET_EXTENDER_H + +#include <lemon/core.h> +#include <lemon/error.h> +#include <lemon/bits/default_map.h> +#include <lemon/bits/map_extender.h> + +//\ingroup digraphbits +//\file +//\brief Extenders for the arc set types +namespace lemon { + + // \ingroup digraphbits + // + // \brief Extender for the ArcSets + template <typename Base> + class ArcSetExtender : public Base { + typedef Base Parent; + + public: + + typedef ArcSetExtender Digraph; + + // Base extensions + + typedef typename Parent::Node Node; + typedef typename Parent::Arc Arc; + + int maxId(Node) const { + return Parent::maxNodeId(); + } + + int maxId(Arc) const { + return Parent::maxArcId(); + } + + Node fromId(int id, Node) const { + return Parent::nodeFromId(id); + } + + Arc fromId(int id, Arc) const { + return Parent::arcFromId(id); + } + + Node oppositeNode(const Node &n, const Arc &e) const { + if (n == Parent::source(e)) + return Parent::target(e); + else if(n==Parent::target(e)) + return Parent::source(e); + else + return INVALID; + } + + + // Alteration notifier extensions + + // The arc observer registry. + typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier; + + protected: + + mutable ArcNotifier arc_notifier; + + public: + + using Parent::notifier; + + // Gives back the arc alteration notifier. + ArcNotifier& notifier(Arc) const { + return arc_notifier; + } + + // Iterable extensions + + class NodeIt : public Node { + const Digraph* digraph; + public: + + NodeIt() {} + + NodeIt(Invalid i) : Node(i) { } + + explicit NodeIt(const Digraph& _graph) : digraph(&_graph) { + _graph.first(static_cast<Node&>(*this)); + } + + NodeIt(const Digraph& _graph, const Node& node) + : Node(node), digraph(&_graph) {} + + NodeIt& operator++() { + digraph->next(*this); + return *this; + } + + }; + + + class ArcIt : public Arc { + const Digraph* digraph; + public: + + ArcIt() { } + + ArcIt(Invalid i) : Arc(i) { } + + explicit ArcIt(const Digraph& _graph) : digraph(&_graph) { + _graph.first(static_cast<Arc&>(*this)); + } + + ArcIt(const Digraph& _graph, const Arc& e) : + Arc(e), digraph(&_graph) { } + + ArcIt& operator++() { + digraph->next(*this); + return *this; + } + + }; + + + class OutArcIt : public Arc { + const Digraph* digraph; + public: + + OutArcIt() { } + + OutArcIt(Invalid i) : Arc(i) { } + + OutArcIt(const Digraph& _graph, const Node& node) + : digraph(&_graph) { + _graph.firstOut(*this, node); + } + + OutArcIt(const Digraph& _graph, const Arc& arc) + : Arc(arc), digraph(&_graph) {} + + OutArcIt& operator++() { + digraph->nextOut(*this); + return *this; + } + + }; + + + class InArcIt : public Arc { + const Digraph* digraph; + public: + + InArcIt() { } + + InArcIt(Invalid i) : Arc(i) { } + + InArcIt(const Digraph& _graph, const Node& node) + : digraph(&_graph) { + _graph.firstIn(*this, node); + } + + InArcIt(const Digraph& _graph, const Arc& arc) : + Arc(arc), digraph(&_graph) {} + + InArcIt& operator++() { + digraph->nextIn(*this); + return *this; + } + + }; + + // \brief Base node of the iterator + // + // Returns the base node (ie. the source in this case) of the iterator + Node baseNode(const OutArcIt &e) const { + return Parent::source(static_cast<const Arc&>(e)); + } + // \brief Running node of the iterator + // + // Returns the running node (ie. the target in this case) of the + // iterator + Node runningNode(const OutArcIt &e) const { + return Parent::target(static_cast<const Arc&>(e)); + } + + // \brief Base node of the iterator + // + // Returns the base node (ie. the target in this case) of the iterator + Node baseNode(const InArcIt &e) const { + return Parent::target(static_cast<const Arc&>(e)); + } + // \brief Running node of the iterator + // + // Returns the running node (ie. the source in this case) of the + // iterator + Node runningNode(const InArcIt &e) const { + return Parent::source(static_cast<const Arc&>(e)); + } + + using Parent::first; + + // Mappable extension + + template <typename _Value> + class ArcMap + : public MapExtender<DefaultMap<Digraph, Arc, _Value> > { + typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent; + + public: + explicit ArcMap(const Digraph& _g) + : Parent(_g) {} + ArcMap(const Digraph& _g, const _Value& _v) + : Parent(_g, _v) {} + + ArcMap& operator=(const ArcMap& cmap) { + return operator=<ArcMap>(cmap); + } + + template <typename CMap> + ArcMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + + }; + + + // Alteration extension + + Arc addArc(const Node& from, const Node& to) { + Arc arc = Parent::addArc(from, to); + notifier(Arc()).add(arc); + return arc; + } + + void clear() { + notifier(Arc()).clear(); + Parent::clear(); + } + + void erase(const Arc& arc) { + notifier(Arc()).erase(arc); + Parent::erase(arc); + } + + ArcSetExtender() { + arc_notifier.setContainer(*this); + } + + ~ArcSetExtender() { + arc_notifier.clear(); + } + + }; + + + // \ingroup digraphbits + // + // \brief Extender for the EdgeSets + template <typename Base> + class EdgeSetExtender : public Base { + typedef Base Parent; + + public: + + typedef EdgeSetExtender Graph; + + typedef True UndirectedTag; + + typedef typename Parent::Node Node; + typedef typename Parent::Arc Arc; + typedef typename Parent::Edge Edge; + + int maxId(Node) const { + return Parent::maxNodeId(); + } + + int maxId(Arc) const { + return Parent::maxArcId(); + } + + int maxId(Edge) const { + return Parent::maxEdgeId(); + } + + Node fromId(int id, Node) const { + return Parent::nodeFromId(id); + } + + Arc fromId(int id, Arc) const { + return Parent::arcFromId(id); + } + + Edge fromId(int id, Edge) const { + return Parent::edgeFromId(id); + } + + Node oppositeNode(const Node &n, const Edge &e) const { + if( n == Parent::u(e)) + return Parent::v(e); + else if( n == Parent::v(e)) + return Parent::u(e); + else + return INVALID; + } + + Arc oppositeArc(const Arc &e) const { + return Parent::direct(e, !Parent::direction(e)); + } + + using Parent::direct; + Arc direct(const Edge &e, const Node &s) const { + return Parent::direct(e, Parent::u(e) == s); + } + + typedef AlterationNotifier<EdgeSetExtender, Arc> ArcNotifier; + typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier; + + + protected: + + mutable ArcNotifier arc_notifier; + mutable EdgeNotifier edge_notifier; + + public: + + using Parent::notifier; + + ArcNotifier& notifier(Arc) const { + return arc_notifier; + } + + EdgeNotifier& notifier(Edge) const { + return edge_notifier; + } + + + class NodeIt : public Node { + const Graph* graph; + public: + + NodeIt() {} + + NodeIt(Invalid i) : Node(i) { } + + explicit NodeIt(const Graph& _graph) : graph(&_graph) { + _graph.first(static_cast<Node&>(*this)); + } + + NodeIt(const Graph& _graph, const Node& node) + : Node(node), graph(&_graph) {} + + NodeIt& operator++() { + graph->next(*this); + return *this; + } + + }; + + + class ArcIt : public Arc { + const Graph* graph; + public: + + ArcIt() { } + + ArcIt(Invalid i) : Arc(i) { } + + explicit ArcIt(const Graph& _graph) : graph(&_graph) { + _graph.first(static_cast<Arc&>(*this)); + } + + ArcIt(const Graph& _graph, const Arc& e) : + Arc(e), graph(&_graph) { } + + ArcIt& operator++() { + graph->next(*this); + return *this; + } + + }; + + + class OutArcIt : public Arc { + const Graph* graph; + public: + + OutArcIt() { } + + OutArcIt(Invalid i) : Arc(i) { } + + OutArcIt(const Graph& _graph, const Node& node) + : graph(&_graph) { + _graph.firstOut(*this, node); + } + + OutArcIt(const Graph& _graph, const Arc& arc) + : Arc(arc), graph(&_graph) {} + + OutArcIt& operator++() { + graph->nextOut(*this); + return *this; + } + + }; + + + class InArcIt : public Arc { + const Graph* graph; + public: + + InArcIt() { } + + InArcIt(Invalid i) : Arc(i) { } + + InArcIt(const Graph& _graph, const Node& node) + : graph(&_graph) { + _graph.firstIn(*this, node); + } + + InArcIt(const Graph& _graph, const Arc& arc) : + Arc(arc), graph(&_graph) {} + + InArcIt& operator++() { + graph->nextIn(*this); + return *this; + } + + }; + + + class EdgeIt : public Parent::Edge { + const Graph* graph; + public: + + EdgeIt() { } + + EdgeIt(Invalid i) : Edge(i) { } + + explicit EdgeIt(const Graph& _graph) : graph(&_graph) { + _graph.first(static_cast<Edge&>(*this)); + } + + EdgeIt(const Graph& _graph, const Edge& e) : + Edge(e), graph(&_graph) { } + + EdgeIt& operator++() { + graph->next(*this); + return *this; + } + + }; + + class IncEdgeIt : public Parent::Edge { + friend class EdgeSetExtender; + const Graph* graph; + bool direction; + public: + + IncEdgeIt() { } + + IncEdgeIt(Invalid i) : Edge(i), direction(false) { } + + IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { + _graph.firstInc(*this, direction, n); + } + + IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n) + : graph(&_graph), Edge(ue) { + direction = (_graph.source(ue) == n); + } + + IncEdgeIt& operator++() { + graph->nextInc(*this, direction); + return *this; + } + }; + + // \brief Base node of the iterator + // + // Returns the base node (ie. the source in this case) of the iterator + Node baseNode(const OutArcIt &e) const { + return Parent::source(static_cast<const Arc&>(e)); + } + // \brief Running node of the iterator + // + // Returns the running node (ie. the target in this case) of the + // iterator + Node runningNode(const OutArcIt &e) const { + return Parent::target(static_cast<const Arc&>(e)); + } + + // \brief Base node of the iterator + // + // Returns the base node (ie. the target in this case) of the iterator + Node baseNode(const InArcIt &e) const { + return Parent::target(static_cast<const Arc&>(e)); + } + // \brief Running node of the iterator + // + // Returns the running node (ie. the source in this case) of the + // iterator + Node runningNode(const InArcIt &e) const { + return Parent::source(static_cast<const Arc&>(e)); + } + + // Base node of the iterator + // + // Returns the base node of the iterator + Node baseNode(const IncEdgeIt &e) const { + return e.direction ? this->u(e) : this->v(e); + } + // Running node of the iterator + // + // Returns the running node of the iterator + Node runningNode(const IncEdgeIt &e) const { + return e.direction ? this->v(e) : this->u(e); + } + + + template <typename _Value> + class ArcMap + : public MapExtender<DefaultMap<Graph, Arc, _Value> > { + typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent; + + public: + explicit ArcMap(const Graph& _g) + : Parent(_g) {} + ArcMap(const Graph& _g, const _Value& _v) + : Parent(_g, _v) {} + + ArcMap& operator=(const ArcMap& cmap) { + return operator=<ArcMap>(cmap); + } + + template <typename CMap> + ArcMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + + }; + + + template <typename _Value> + class EdgeMap + : public MapExtender<DefaultMap<Graph, Edge, _Value> > { + typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; + + public: + explicit EdgeMap(const Graph& _g) + : Parent(_g) {} + + EdgeMap(const Graph& _g, const _Value& _v) + : Parent(_g, _v) {} + + EdgeMap& operator=(const EdgeMap& cmap) { + return operator=<EdgeMap>(cmap); + } + + template <typename CMap> + EdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + + }; + + + // Alteration extension + + Edge addEdge(const Node& from, const Node& to) { + Edge edge = Parent::addEdge(from, to); + notifier(Edge()).add(edge); + std::vector<Arc> arcs; + arcs.push_back(Parent::direct(edge, true)); + arcs.push_back(Parent::direct(edge, false)); + notifier(Arc()).add(arcs); + return edge; + } + + void clear() { + notifier(Arc()).clear(); + notifier(Edge()).clear(); + Parent::clear(); + } + + void erase(const Edge& edge) { + std::vector<Arc> arcs; + arcs.push_back(Parent::direct(edge, true)); + arcs.push_back(Parent::direct(edge, false)); + notifier(Arc()).erase(arcs); + notifier(Edge()).erase(edge); + Parent::erase(edge); + } + + + EdgeSetExtender() { + arc_notifier.setContainer(*this); + edge_notifier.setContainer(*this); + } + + ~EdgeSetExtender() { + edge_notifier.clear(); + arc_notifier.clear(); + } + + }; + +} + +#endif diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/enable_if.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/enable_if.h new file mode 100644 index 00000000000..f0d8de4d3cc --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/enable_if.h @@ -0,0 +1,131 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * 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 (c) 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 Jarvi (jajarvi at osl.iu.edu) +// Jeremiah Willcock (jewillco at osl.iu.edu) +// Andrew Lumsdaine (lums at osl.iu.edu) + + +#ifndef LEMON_BITS_ENABLE_IF_H +#define LEMON_BITS_ENABLE_IF_H + +//\file +//\brief Miscellaneous basic utilities + +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 + 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; + }; + + + + 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 diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/graph_adaptor_extender.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/graph_adaptor_extender.h new file mode 100644 index 00000000000..c38c8e1d608 --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/graph_adaptor_extender.h @@ -0,0 +1,401 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2013 + * 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_GRAPH_ADAPTOR_EXTENDER_H +#define LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H + +#include <lemon/core.h> +#include <lemon/error.h> + +namespace lemon { + + template <typename _Digraph> + class DigraphAdaptorExtender : public _Digraph { + typedef _Digraph Parent; + + public: + + typedef _Digraph Digraph; + typedef DigraphAdaptorExtender Adaptor; + + // Base extensions + + typedef typename Parent::Node Node; + typedef typename Parent::Arc Arc; + + int maxId(Node) const { + return Parent::maxNodeId(); + } + + int maxId(Arc) const { + return Parent::maxArcId(); + } + + Node fromId(int id, Node) const { + return Parent::nodeFromId(id); + } + + Arc fromId(int id, Arc) const { + return Parent::arcFromId(id); + } + + Node oppositeNode(const Node &n, const Arc &e) const { + if (n == Parent::source(e)) + return Parent::target(e); + else if(n==Parent::target(e)) + return Parent::source(e); + else + return INVALID; + } + + class NodeIt : public Node { + const Adaptor* _adaptor; + public: + + NodeIt() {} + + NodeIt(Invalid i) : Node(i) { } + + explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) { + _adaptor->first(static_cast<Node&>(*this)); + } + + NodeIt(const Adaptor& adaptor, const Node& node) + : Node(node), _adaptor(&adaptor) {} + + NodeIt& operator++() { + _adaptor->next(*this); + return *this; + } + + }; + + + class ArcIt : public Arc { + const Adaptor* _adaptor; + public: + + ArcIt() { } + + ArcIt(Invalid i) : Arc(i) { } + + explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) { + _adaptor->first(static_cast<Arc&>(*this)); + } + + ArcIt(const Adaptor& adaptor, const Arc& e) : + Arc(e), _adaptor(&adaptor) { } + + ArcIt& operator++() { + _adaptor->next(*this); + return *this; + } + + }; + + + class OutArcIt : public Arc { + const Adaptor* _adaptor; + public: + + OutArcIt() { } + + OutArcIt(Invalid i) : Arc(i) { } + + OutArcIt(const Adaptor& adaptor, const Node& node) + : _adaptor(&adaptor) { + _adaptor->firstOut(*this, node); + } + + OutArcIt(const Adaptor& adaptor, const Arc& arc) + : Arc(arc), _adaptor(&adaptor) {} + + OutArcIt& operator++() { + _adaptor->nextOut(*this); + return *this; + } + + }; + + + class InArcIt : public Arc { + const Adaptor* _adaptor; + public: + + InArcIt() { } + + InArcIt(Invalid i) : Arc(i) { } + + InArcIt(const Adaptor& adaptor, const Node& node) + : _adaptor(&adaptor) { + _adaptor->firstIn(*this, node); + } + + InArcIt(const Adaptor& adaptor, const Arc& arc) : + Arc(arc), _adaptor(&adaptor) {} + + InArcIt& operator++() { + _adaptor->nextIn(*this); + return *this; + } + + }; + + Node baseNode(const OutArcIt &e) const { + return Parent::source(e); + } + Node runningNode(const OutArcIt &e) const { + return Parent::target(e); + } + + Node baseNode(const InArcIt &e) const { + return Parent::target(e); + } + Node runningNode(const InArcIt &e) const { + return Parent::source(e); + } + + }; + + template <typename _Graph> + class GraphAdaptorExtender : public _Graph { + typedef _Graph Parent; + + public: + + typedef _Graph Graph; + typedef GraphAdaptorExtender Adaptor; + + typedef True UndirectedTag; + + typedef typename Parent::Node Node; + typedef typename Parent::Arc Arc; + typedef typename Parent::Edge Edge; + + // Graph extension + + int maxId(Node) const { + return Parent::maxNodeId(); + } + + int maxId(Arc) const { + return Parent::maxArcId(); + } + + int maxId(Edge) const { + return Parent::maxEdgeId(); + } + + Node fromId(int id, Node) const { + return Parent::nodeFromId(id); + } + + Arc fromId(int id, Arc) const { + return Parent::arcFromId(id); + } + + Edge fromId(int id, Edge) const { + return Parent::edgeFromId(id); + } + + Node oppositeNode(const Node &n, const Edge &e) const { + if( n == Parent::u(e)) + return Parent::v(e); + else if( n == Parent::v(e)) + return Parent::u(e); + else + return INVALID; + } + + Arc oppositeArc(const Arc &a) const { + return Parent::direct(a, !Parent::direction(a)); + } + + using Parent::direct; + Arc direct(const Edge &e, const Node &s) const { + return Parent::direct(e, Parent::u(e) == s); + } + + + class NodeIt : public Node { + const Adaptor* _adaptor; + public: + + NodeIt() {} + + NodeIt(Invalid i) : Node(i) { } + + explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) { + _adaptor->first(static_cast<Node&>(*this)); + } + + NodeIt(const Adaptor& adaptor, const Node& node) + : Node(node), _adaptor(&adaptor) {} + + NodeIt& operator++() { + _adaptor->next(*this); + return *this; + } + + }; + + + class ArcIt : public Arc { + const Adaptor* _adaptor; + public: + + ArcIt() { } + + ArcIt(Invalid i) : Arc(i) { } + + explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) { + _adaptor->first(static_cast<Arc&>(*this)); + } + + ArcIt(const Adaptor& adaptor, const Arc& e) : + Arc(e), _adaptor(&adaptor) { } + + ArcIt& operator++() { + _adaptor->next(*this); + return *this; + } + + }; + + + class OutArcIt : public Arc { + const Adaptor* _adaptor; + public: + + OutArcIt() { } + + OutArcIt(Invalid i) : Arc(i) { } + + OutArcIt(const Adaptor& adaptor, const Node& node) + : _adaptor(&adaptor) { + _adaptor->firstOut(*this, node); + } + + OutArcIt(const Adaptor& adaptor, const Arc& arc) + : Arc(arc), _adaptor(&adaptor) {} + + OutArcIt& operator++() { + _adaptor->nextOut(*this); + return *this; + } + + }; + + + class InArcIt : public Arc { + const Adaptor* _adaptor; + public: + + InArcIt() { } + + InArcIt(Invalid i) : Arc(i) { } + + InArcIt(const Adaptor& adaptor, const Node& node) + : _adaptor(&adaptor) { + _adaptor->firstIn(*this, node); + } + + InArcIt(const Adaptor& adaptor, const Arc& arc) : + Arc(arc), _adaptor(&adaptor) {} + + InArcIt& operator++() { + _adaptor->nextIn(*this); + return *this; + } + + }; + + class EdgeIt : public Parent::Edge { + const Adaptor* _adaptor; + public: + + EdgeIt() { } + + EdgeIt(Invalid i) : Edge(i) { } + + explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) { + _adaptor->first(static_cast<Edge&>(*this)); + } + + EdgeIt(const Adaptor& adaptor, const Edge& e) : + Edge(e), _adaptor(&adaptor) { } + + EdgeIt& operator++() { + _adaptor->next(*this); + return *this; + } + + }; + + class IncEdgeIt : public Edge { + friend class GraphAdaptorExtender; + const Adaptor* _adaptor; + bool direction; + public: + + IncEdgeIt() { } + + IncEdgeIt(Invalid i) : Edge(i), direction(false) { } + + IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) { + _adaptor->firstInc(static_cast<Edge&>(*this), direction, n); + } + + IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n) + : _adaptor(&adaptor), Edge(e) { + direction = (_adaptor->u(e) == n); + } + + IncEdgeIt& operator++() { + _adaptor->nextInc(*this, direction); + return *this; + } + }; + + Node baseNode(const OutArcIt &a) const { + return Parent::source(a); + } + Node runningNode(const OutArcIt &a) const { + return Parent::target(a); + } + + Node baseNode(const InArcIt &a) const { + return Parent::target(a); + } + Node runningNode(const InArcIt &a) const { + return Parent::source(a); + } + + Node baseNode(const IncEdgeIt &e) const { + return e.direction ? Parent::u(e) : Parent::v(e); + } + Node runningNode(const IncEdgeIt &e) const { + return e.direction ? Parent::v(e) : Parent::u(e); + } + + }; + +} + + +#endif diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/graph_extender.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/graph_extender.h new file mode 100644 index 00000000000..755a8907f50 --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/graph_extender.h @@ -0,0 +1,1332 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2013 + * 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_GRAPH_EXTENDER_H +#define LEMON_BITS_GRAPH_EXTENDER_H + +#include <lemon/core.h> + +#include <lemon/bits/map_extender.h> +#include <lemon/bits/default_map.h> + +#include <lemon/concept_check.h> +#include <lemon/concepts/maps.h> + +//\ingroup graphbits +//\file +//\brief Extenders for the graph types +namespace lemon { + + // \ingroup graphbits + // + // \brief Extender for the digraph implementations + template <typename Base> + class DigraphExtender : public Base { + typedef Base Parent; + + public: + + typedef DigraphExtender Digraph; + + // Base extensions + + typedef typename Parent::Node Node; + typedef typename Parent::Arc Arc; + + int maxId(Node) const { + return Parent::maxNodeId(); + } + + int maxId(Arc) const { + return Parent::maxArcId(); + } + + static Node fromId(int id, Node) { + return Parent::nodeFromId(id); + } + + static Arc fromId(int id, Arc) { + return Parent::arcFromId(id); + } + + Node oppositeNode(const Node &node, const Arc &arc) const { + if (node == Parent::source(arc)) + return Parent::target(arc); + else if(node == Parent::target(arc)) + return Parent::source(arc); + else + return INVALID; + } + + // Alterable extension + + typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier; + typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier; + + + protected: + + mutable NodeNotifier node_notifier; + mutable ArcNotifier arc_notifier; + + public: + + NodeNotifier& notifier(Node) const { + return node_notifier; + } + + ArcNotifier& notifier(Arc) const { + return arc_notifier; + } + + class NodeIt : public Node { + const Digraph* _digraph; + public: + + NodeIt() {} + + NodeIt(Invalid i) : Node(i) { } + + explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) { + _digraph->first(static_cast<Node&>(*this)); + } + + NodeIt(const Digraph& digraph, const Node& node) + : Node(node), _digraph(&digraph) {} + + NodeIt& operator++() { + _digraph->next(*this); + return *this; + } + + }; + + + class ArcIt : public Arc { + const Digraph* _digraph; + public: + + ArcIt() { } + + ArcIt(Invalid i) : Arc(i) { } + + explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) { + _digraph->first(static_cast<Arc&>(*this)); + } + + ArcIt(const Digraph& digraph, const Arc& arc) : + Arc(arc), _digraph(&digraph) { } + + ArcIt& operator++() { + _digraph->next(*this); + return *this; + } + + }; + + + class OutArcIt : public Arc { + const Digraph* _digraph; + public: + + OutArcIt() { } + + OutArcIt(Invalid i) : Arc(i) { } + + OutArcIt(const Digraph& digraph, const Node& node) + : _digraph(&digraph) { + _digraph->firstOut(*this, node); + } + + OutArcIt(const Digraph& digraph, const Arc& arc) + : Arc(arc), _digraph(&digraph) {} + + OutArcIt& operator++() { + _digraph->nextOut(*this); + return *this; + } + + }; + + + class InArcIt : public Arc { + const Digraph* _digraph; + public: + + InArcIt() { } + + InArcIt(Invalid i) : Arc(i) { } + + InArcIt(const Digraph& digraph, const Node& node) + : _digraph(&digraph) { + _digraph->firstIn(*this, node); + } + + InArcIt(const Digraph& digraph, const Arc& arc) : + Arc(arc), _digraph(&digraph) {} + + InArcIt& operator++() { + _digraph->nextIn(*this); + return *this; + } + + }; + + // \brief Base node of the iterator + // + // Returns the base node (i.e. the source in this case) of the iterator + Node baseNode(const OutArcIt &arc) const { + return Parent::source(arc); + } + // \brief Running node of the iterator + // + // Returns the running node (i.e. the target in this case) of the + // iterator + Node runningNode(const OutArcIt &arc) const { + return Parent::target(arc); + } + + // \brief Base node of the iterator + // + // Returns the base node (i.e. the target in this case) of the iterator + Node baseNode(const InArcIt &arc) const { + return Parent::target(arc); + } + // \brief Running node of the iterator + // + // Returns the running node (i.e. the source in this case) of the + // iterator + Node runningNode(const InArcIt &arc) const { + return Parent::source(arc); + } + + + template <typename _Value> + class NodeMap + : public MapExtender<DefaultMap<Digraph, Node, _Value> > { + typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent; + + public: + explicit NodeMap(const Digraph& digraph) + : Parent(digraph) {} + NodeMap(const Digraph& digraph, const _Value& value) + : Parent(digraph, value) {} + + private: + NodeMap& operator=(const NodeMap& cmap) { + return operator=<NodeMap>(cmap); + } + + template <typename CMap> + NodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + + }; + + template <typename _Value> + class ArcMap + : public MapExtender<DefaultMap<Digraph, Arc, _Value> > { + typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent; + + public: + explicit ArcMap(const Digraph& digraph) + : Parent(digraph) {} + ArcMap(const Digraph& digraph, const _Value& value) + : Parent(digraph, value) {} + + private: + ArcMap& operator=(const ArcMap& cmap) { + return operator=<ArcMap>(cmap); + } + + template <typename CMap> + ArcMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + + Node addNode() { + Node node = Parent::addNode(); + notifier(Node()).add(node); + return node; + } + + Arc addArc(const Node& from, const Node& to) { + Arc arc = Parent::addArc(from, to); + notifier(Arc()).add(arc); + return arc; + } + + void clear() { + notifier(Arc()).clear(); + notifier(Node()).clear(); + Parent::clear(); + } + + template <typename Digraph, typename NodeRefMap, typename ArcRefMap> + void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) { + Parent::build(digraph, nodeRef, arcRef); + notifier(Node()).build(); + notifier(Arc()).build(); + } + + void erase(const Node& node) { + Arc arc; + Parent::firstOut(arc, node); + while (arc != INVALID ) { + erase(arc); + Parent::firstOut(arc, node); + } + + Parent::firstIn(arc, node); + while (arc != INVALID ) { + erase(arc); + Parent::firstIn(arc, node); + } + + notifier(Node()).erase(node); + Parent::erase(node); + } + + void erase(const Arc& arc) { + notifier(Arc()).erase(arc); + Parent::erase(arc); + } + + DigraphExtender() { + node_notifier.setContainer(*this); + arc_notifier.setContainer(*this); + } + + + ~DigraphExtender() { + arc_notifier.clear(); + node_notifier.clear(); + } + }; + + // \ingroup _graphbits + // + // \brief Extender for the Graphs + template <typename Base> + class GraphExtender : public Base { + typedef Base Parent; + + public: + + typedef GraphExtender Graph; + + typedef True UndirectedTag; + + typedef typename Parent::Node Node; + typedef typename Parent::Arc Arc; + typedef typename Parent::Edge Edge; + + // Graph extension + + int maxId(Node) const { + return Parent::maxNodeId(); + } + + int maxId(Arc) const { + return Parent::maxArcId(); + } + + int maxId(Edge) const { + return Parent::maxEdgeId(); + } + + static Node fromId(int id, Node) { + return Parent::nodeFromId(id); + } + + static Arc fromId(int id, Arc) { + return Parent::arcFromId(id); + } + + static Edge fromId(int id, Edge) { + return Parent::edgeFromId(id); + } + + Node oppositeNode(const Node &n, const Edge &e) const { + if( n == Parent::u(e)) + return Parent::v(e); + else if( n == Parent::v(e)) + return Parent::u(e); + else + return INVALID; + } + + Arc oppositeArc(const Arc &arc) const { + return Parent::direct(arc, !Parent::direction(arc)); + } + + using Parent::direct; + Arc direct(const Edge &edge, const Node &node) const { + return Parent::direct(edge, Parent::u(edge) == node); + } + + // Alterable extension + + typedef AlterationNotifier<GraphExtender, Node> NodeNotifier; + typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier; + typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier; + + + protected: + + mutable NodeNotifier node_notifier; + mutable ArcNotifier arc_notifier; + mutable EdgeNotifier edge_notifier; + + public: + + NodeNotifier& notifier(Node) const { + return node_notifier; + } + + ArcNotifier& notifier(Arc) const { + return arc_notifier; + } + + EdgeNotifier& notifier(Edge) const { + return edge_notifier; + } + + + + class NodeIt : public Node { + const Graph* _graph; + public: + + NodeIt() {} + + NodeIt(Invalid i) : Node(i) { } + + explicit NodeIt(const Graph& graph) : _graph(&graph) { + _graph->first(static_cast<Node&>(*this)); + } + + NodeIt(const Graph& graph, const Node& node) + : Node(node), _graph(&graph) {} + + NodeIt& operator++() { + _graph->next(*this); + return *this; + } + + }; + + + class ArcIt : public Arc { + const Graph* _graph; + public: + + ArcIt() { } + + ArcIt(Invalid i) : Arc(i) { } + + explicit ArcIt(const Graph& graph) : _graph(&graph) { + _graph->first(static_cast<Arc&>(*this)); + } + + ArcIt(const Graph& graph, const Arc& arc) : + Arc(arc), _graph(&graph) { } + + ArcIt& operator++() { + _graph->next(*this); + return *this; + } + + }; + + + class OutArcIt : public Arc { + const Graph* _graph; + public: + + OutArcIt() { } + + OutArcIt(Invalid i) : Arc(i) { } + + OutArcIt(const Graph& graph, const Node& node) + : _graph(&graph) { + _graph->firstOut(*this, node); + } + + OutArcIt(const Graph& graph, const Arc& arc) + : Arc(arc), _graph(&graph) {} + + OutArcIt& operator++() { + _graph->nextOut(*this); + return *this; + } + + }; + + + class InArcIt : public Arc { + const Graph* _graph; + public: + + InArcIt() { } + + InArcIt(Invalid i) : Arc(i) { } + + InArcIt(const Graph& graph, const Node& node) + : _graph(&graph) { + _graph->firstIn(*this, node); + } + + InArcIt(const Graph& graph, const Arc& arc) : + Arc(arc), _graph(&graph) {} + + InArcIt& operator++() { + _graph->nextIn(*this); + return *this; + } + + }; + + + class EdgeIt : public Parent::Edge { + const Graph* _graph; + public: + + EdgeIt() { } + + EdgeIt(Invalid i) : Edge(i) { } + + explicit EdgeIt(const Graph& graph) : _graph(&graph) { + _graph->first(static_cast<Edge&>(*this)); + } + + EdgeIt(const Graph& graph, const Edge& edge) : + Edge(edge), _graph(&graph) { } + + EdgeIt& operator++() { + _graph->next(*this); + return *this; + } + + }; + + class IncEdgeIt : public Parent::Edge { + friend class GraphExtender; + const Graph* _graph; + bool _direction; + public: + + IncEdgeIt() { } + + IncEdgeIt(Invalid i) : Edge(i), _direction(false) { } + + IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) { + _graph->firstInc(*this, _direction, node); + } + + IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node) + : _graph(&graph), Edge(edge) { + _direction = (_graph->source(edge) == node); + } + + IncEdgeIt& operator++() { + _graph->nextInc(*this, _direction); + return *this; + } + }; + + // \brief Base node of the iterator + // + // Returns the base node (ie. the source in this case) of the iterator + Node baseNode(const OutArcIt &arc) const { + return Parent::source(static_cast<const Arc&>(arc)); + } + // \brief Running node of the iterator + // + // Returns the running node (ie. the target in this case) of the + // iterator + Node runningNode(const OutArcIt &arc) const { + return Parent::target(static_cast<const Arc&>(arc)); + } + + // \brief Base node of the iterator + // + // Returns the base node (ie. the target in this case) of the iterator + Node baseNode(const InArcIt &arc) const { + return Parent::target(static_cast<const Arc&>(arc)); + } + // \brief Running node of the iterator + // + // Returns the running node (ie. the source in this case) of the + // iterator + Node runningNode(const InArcIt &arc) const { + return Parent::source(static_cast<const Arc&>(arc)); + } + + // Base node of the iterator + // + // Returns the base node of the iterator + Node baseNode(const IncEdgeIt &edge) const { + return edge._direction ? this->u(edge) : this->v(edge); + } + // Running node of the iterator + // + // Returns the running node of the iterator + Node runningNode(const IncEdgeIt &edge) const { + return edge._direction ? this->v(edge) : this->u(edge); + } + + // Mappable extension + + template <typename _Value> + class NodeMap + : public MapExtender<DefaultMap<Graph, Node, _Value> > { + typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent; + + public: + explicit NodeMap(const Graph& graph) + : Parent(graph) {} + NodeMap(const Graph& graph, const _Value& value) + : Parent(graph, value) {} + + private: + NodeMap& operator=(const NodeMap& cmap) { + return operator=<NodeMap>(cmap); + } + + template <typename CMap> + NodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + + }; + + template <typename _Value> + class ArcMap + : public MapExtender<DefaultMap<Graph, Arc, _Value> > { + typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent; + + public: + explicit ArcMap(const Graph& graph) + : Parent(graph) {} + ArcMap(const Graph& graph, const _Value& value) + : Parent(graph, value) {} + + private: + ArcMap& operator=(const ArcMap& cmap) { + return operator=<ArcMap>(cmap); + } + + template <typename CMap> + ArcMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + + template <typename _Value> + class EdgeMap + : public MapExtender<DefaultMap<Graph, Edge, _Value> > { + typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; + + public: + explicit EdgeMap(const Graph& graph) + : Parent(graph) {} + + EdgeMap(const Graph& graph, const _Value& value) + : Parent(graph, value) {} + + private: + EdgeMap& operator=(const EdgeMap& cmap) { + return operator=<EdgeMap>(cmap); + } + + template <typename CMap> + EdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + + }; + + // Alteration extension + + Node addNode() { + Node node = Parent::addNode(); + notifier(Node()).add(node); + return node; + } + + Edge addEdge(const Node& from, const Node& to) { + Edge edge = Parent::addEdge(from, to); + notifier(Edge()).add(edge); + std::vector<Arc> ev; + ev.push_back(Parent::direct(edge, true)); + ev.push_back(Parent::direct(edge, false)); + notifier(Arc()).add(ev); + return edge; + } + + void clear() { + notifier(Arc()).clear(); + notifier(Edge()).clear(); + notifier(Node()).clear(); + Parent::clear(); + } + + template <typename Graph, typename NodeRefMap, typename EdgeRefMap> + void build(const Graph& graph, NodeRefMap& nodeRef, + EdgeRefMap& edgeRef) { + Parent::build(graph, nodeRef, edgeRef); + notifier(Node()).build(); + notifier(Edge()).build(); + notifier(Arc()).build(); + } + + void erase(const Node& node) { + Arc arc; + Parent::firstOut(arc, node); + while (arc != INVALID ) { + erase(arc); + Parent::firstOut(arc, node); + } + + Parent::firstIn(arc, node); + while (arc != INVALID ) { + erase(arc); + Parent::firstIn(arc, node); + } + + notifier(Node()).erase(node); + Parent::erase(node); + } + + void erase(const Edge& edge) { + std::vector<Arc> av; + av.push_back(Parent::direct(edge, true)); + av.push_back(Parent::direct(edge, false)); + notifier(Arc()).erase(av); + notifier(Edge()).erase(edge); + Parent::erase(edge); + } + + GraphExtender() { + node_notifier.setContainer(*this); + arc_notifier.setContainer(*this); + edge_notifier.setContainer(*this); + } + + ~GraphExtender() { + edge_notifier.clear(); + arc_notifier.clear(); + node_notifier.clear(); + } + + }; + + // \ingroup _graphbits + // + // \brief Extender for the BpGraphs + template <typename Base> + class BpGraphExtender : public Base { + typedef Base Parent; + + public: + + typedef BpGraphExtender BpGraph; + + typedef True UndirectedTag; + + typedef typename Parent::Node Node; + typedef typename Parent::RedNode RedNode; + typedef typename Parent::BlueNode BlueNode; + typedef typename Parent::Arc Arc; + typedef typename Parent::Edge Edge; + + // BpGraph extension + + using Parent::first; + using Parent::next; + using Parent::id; + + int maxId(Node) const { + return Parent::maxNodeId(); + } + + int maxId(RedNode) const { + return Parent::maxRedId(); + } + + int maxId(BlueNode) const { + return Parent::maxBlueId(); + } + + int maxId(Arc) const { + return Parent::maxArcId(); + } + + int maxId(Edge) const { + return Parent::maxEdgeId(); + } + + static Node fromId(int id, Node) { + return Parent::nodeFromId(id); + } + + static Arc fromId(int id, Arc) { + return Parent::arcFromId(id); + } + + static Edge fromId(int id, Edge) { + return Parent::edgeFromId(id); + } + + Node u(Edge e) const { return this->redNode(e); } + Node v(Edge e) const { return this->blueNode(e); } + + Node oppositeNode(const Node &n, const Edge &e) const { + if( n == u(e)) + return v(e); + else if( n == v(e)) + return u(e); + else + return INVALID; + } + + Arc oppositeArc(const Arc &arc) const { + return Parent::direct(arc, !Parent::direction(arc)); + } + + using Parent::direct; + Arc direct(const Edge &edge, const Node &node) const { + return Parent::direct(edge, Parent::redNode(edge) == node); + } + + RedNode asRedNode(const Node& node) const { + if (node == INVALID || Parent::blue(node)) { + return INVALID; + } else { + return Parent::asRedNodeUnsafe(node); + } + } + + BlueNode asBlueNode(const Node& node) const { + if (node == INVALID || Parent::red(node)) { + return INVALID; + } else { + return Parent::asBlueNodeUnsafe(node); + } + } + + // Alterable extension + + typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier; + typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier; + typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier; + typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier; + typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier; + + + protected: + + mutable NodeNotifier node_notifier; + mutable RedNodeNotifier red_node_notifier; + mutable BlueNodeNotifier blue_node_notifier; + mutable ArcNotifier arc_notifier; + mutable EdgeNotifier edge_notifier; + + public: + + NodeNotifier& notifier(Node) const { + return node_notifier; + } + + RedNodeNotifier& notifier(RedNode) const { + return red_node_notifier; + } + + BlueNodeNotifier& notifier(BlueNode) const { + return blue_node_notifier; + } + + ArcNotifier& notifier(Arc) const { + return arc_notifier; + } + + EdgeNotifier& notifier(Edge) const { + return edge_notifier; + } + + + + class NodeIt : public Node { + const BpGraph* _graph; + public: + + NodeIt() {} + + NodeIt(Invalid i) : Node(i) { } + + explicit NodeIt(const BpGraph& graph) : _graph(&graph) { + _graph->first(static_cast<Node&>(*this)); + } + + NodeIt(const BpGraph& graph, const Node& node) + : Node(node), _graph(&graph) {} + + NodeIt& operator++() { + _graph->next(*this); + return *this; + } + + }; + + class RedNodeIt : public RedNode { + const BpGraph* _graph; + public: + + RedNodeIt() {} + + RedNodeIt(Invalid i) : RedNode(i) { } + + explicit RedNodeIt(const BpGraph& graph) : _graph(&graph) { + _graph->first(static_cast<RedNode&>(*this)); + } + + RedNodeIt(const BpGraph& graph, const RedNode& node) + : RedNode(node), _graph(&graph) {} + + RedNodeIt& operator++() { + _graph->next(static_cast<RedNode&>(*this)); + return *this; + } + + }; + + class BlueNodeIt : public BlueNode { + const BpGraph* _graph; + public: + + BlueNodeIt() {} + + BlueNodeIt(Invalid i) : BlueNode(i) { } + + explicit BlueNodeIt(const BpGraph& graph) : _graph(&graph) { + _graph->first(static_cast<BlueNode&>(*this)); + } + + BlueNodeIt(const BpGraph& graph, const BlueNode& node) + : BlueNode(node), _graph(&graph) {} + + BlueNodeIt& operator++() { + _graph->next(static_cast<BlueNode&>(*this)); + return *this; + } + + }; + + + class ArcIt : public Arc { + const BpGraph* _graph; + public: + + ArcIt() { } + + ArcIt(Invalid i) : Arc(i) { } + + explicit ArcIt(const BpGraph& graph) : _graph(&graph) { + _graph->first(static_cast<Arc&>(*this)); + } + + ArcIt(const BpGraph& graph, const Arc& arc) : + Arc(arc), _graph(&graph) { } + + ArcIt& operator++() { + _graph->next(*this); + return *this; + } + + }; + + + class OutArcIt : public Arc { + const BpGraph* _graph; + public: + + OutArcIt() { } + + OutArcIt(Invalid i) : Arc(i) { } + + OutArcIt(const BpGraph& graph, const Node& node) + : _graph(&graph) { + _graph->firstOut(*this, node); + } + + OutArcIt(const BpGraph& graph, const Arc& arc) + : Arc(arc), _graph(&graph) {} + + OutArcIt& operator++() { + _graph->nextOut(*this); + return *this; + } + + }; + + + class InArcIt : public Arc { + const BpGraph* _graph; + public: + + InArcIt() { } + + InArcIt(Invalid i) : Arc(i) { } + + InArcIt(const BpGraph& graph, const Node& node) + : _graph(&graph) { + _graph->firstIn(*this, node); + } + + InArcIt(const BpGraph& graph, const Arc& arc) : + Arc(arc), _graph(&graph) {} + + InArcIt& operator++() { + _graph->nextIn(*this); + return *this; + } + + }; + + + class EdgeIt : public Parent::Edge { + const BpGraph* _graph; + public: + + EdgeIt() { } + + EdgeIt(Invalid i) : Edge(i) { } + + explicit EdgeIt(const BpGraph& graph) : _graph(&graph) { + _graph->first(static_cast<Edge&>(*this)); + } + + EdgeIt(const BpGraph& graph, const Edge& edge) : + Edge(edge), _graph(&graph) { } + + EdgeIt& operator++() { + _graph->next(*this); + return *this; + } + + }; + + class IncEdgeIt : public Parent::Edge { + friend class BpGraphExtender; + const BpGraph* _graph; + bool _direction; + public: + + IncEdgeIt() { } + + IncEdgeIt(Invalid i) : Edge(i), _direction(false) { } + + IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) { + _graph->firstInc(*this, _direction, node); + } + + IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node) + : _graph(&graph), Edge(edge) { + _direction = (_graph->source(edge) == node); + } + + IncEdgeIt& operator++() { + _graph->nextInc(*this, _direction); + return *this; + } + }; + + // \brief Base node of the iterator + // + // Returns the base node (ie. the source in this case) of the iterator + Node baseNode(const OutArcIt &arc) const { + return Parent::source(static_cast<const Arc&>(arc)); + } + // \brief Running node of the iterator + // + // Returns the running node (ie. the target in this case) of the + // iterator + Node runningNode(const OutArcIt &arc) const { + return Parent::target(static_cast<const Arc&>(arc)); + } + + // \brief Base node of the iterator + // + // Returns the base node (ie. the target in this case) of the iterator + Node baseNode(const InArcIt &arc) const { + return Parent::target(static_cast<const Arc&>(arc)); + } + // \brief Running node of the iterator + // + // Returns the running node (ie. the source in this case) of the + // iterator + Node runningNode(const InArcIt &arc) const { + return Parent::source(static_cast<const Arc&>(arc)); + } + + // Base node of the iterator + // + // Returns the base node of the iterator + Node baseNode(const IncEdgeIt &edge) const { + return edge._direction ? this->u(edge) : this->v(edge); + } + // Running node of the iterator + // + // Returns the running node of the iterator + Node runningNode(const IncEdgeIt &edge) const { + return edge._direction ? this->v(edge) : this->u(edge); + } + + // Mappable extension + + template <typename _Value> + class NodeMap + : public MapExtender<DefaultMap<BpGraph, Node, _Value> > { + typedef MapExtender<DefaultMap<BpGraph, Node, _Value> > Parent; + + public: + explicit NodeMap(const BpGraph& bpgraph) + : Parent(bpgraph) {} + NodeMap(const BpGraph& bpgraph, const _Value& value) + : Parent(bpgraph, value) {} + + private: + NodeMap& operator=(const NodeMap& cmap) { + return operator=<NodeMap>(cmap); + } + + template <typename CMap> + NodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + + }; + + template <typename _Value> + class RedNodeMap + : public MapExtender<DefaultMap<BpGraph, RedNode, _Value> > { + typedef MapExtender<DefaultMap<BpGraph, RedNode, _Value> > Parent; + + public: + explicit RedNodeMap(const BpGraph& bpgraph) + : Parent(bpgraph) {} + RedNodeMap(const BpGraph& bpgraph, const _Value& value) + : Parent(bpgraph, value) {} + + private: + RedNodeMap& operator=(const RedNodeMap& cmap) { + return operator=<RedNodeMap>(cmap); + } + + template <typename CMap> + RedNodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + + }; + + template <typename _Value> + class BlueNodeMap + : public MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > { + typedef MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > Parent; + + public: + explicit BlueNodeMap(const BpGraph& bpgraph) + : Parent(bpgraph) {} + BlueNodeMap(const BpGraph& bpgraph, const _Value& value) + : Parent(bpgraph, value) {} + + private: + BlueNodeMap& operator=(const BlueNodeMap& cmap) { + return operator=<BlueNodeMap>(cmap); + } + + template <typename CMap> + BlueNodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + + }; + + template <typename _Value> + class ArcMap + : public MapExtender<DefaultMap<BpGraph, Arc, _Value> > { + typedef MapExtender<DefaultMap<BpGraph, Arc, _Value> > Parent; + + public: + explicit ArcMap(const BpGraph& graph) + : Parent(graph) {} + ArcMap(const BpGraph& graph, const _Value& value) + : Parent(graph, value) {} + + private: + ArcMap& operator=(const ArcMap& cmap) { + return operator=<ArcMap>(cmap); + } + + template <typename CMap> + ArcMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + + template <typename _Value> + class EdgeMap + : public MapExtender<DefaultMap<BpGraph, Edge, _Value> > { + typedef MapExtender<DefaultMap<BpGraph, Edge, _Value> > Parent; + + public: + explicit EdgeMap(const BpGraph& graph) + : Parent(graph) {} + + EdgeMap(const BpGraph& graph, const _Value& value) + : Parent(graph, value) {} + + private: + EdgeMap& operator=(const EdgeMap& cmap) { + return operator=<EdgeMap>(cmap); + } + + template <typename CMap> + EdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + + }; + + // Alteration extension + + RedNode addRedNode() { + RedNode node = Parent::addRedNode(); + notifier(RedNode()).add(node); + notifier(Node()).add(node); + return node; + } + + BlueNode addBlueNode() { + BlueNode node = Parent::addBlueNode(); + notifier(BlueNode()).add(node); + notifier(Node()).add(node); + return node; + } + + Edge addEdge(const RedNode& from, const BlueNode& to) { + Edge edge = Parent::addEdge(from, to); + notifier(Edge()).add(edge); + std::vector<Arc> av; + av.push_back(Parent::direct(edge, true)); + av.push_back(Parent::direct(edge, false)); + notifier(Arc()).add(av); + return edge; + } + + void clear() { + notifier(Arc()).clear(); + notifier(Edge()).clear(); + notifier(Node()).clear(); + notifier(BlueNode()).clear(); + notifier(RedNode()).clear(); + Parent::clear(); + } + + template <typename BpGraph, typename NodeRefMap, typename EdgeRefMap> + void build(const BpGraph& graph, NodeRefMap& nodeRef, + EdgeRefMap& edgeRef) { + Parent::build(graph, nodeRef, edgeRef); + notifier(RedNode()).build(); + notifier(BlueNode()).build(); + notifier(Node()).build(); + notifier(Edge()).build(); + notifier(Arc()).build(); + } + + void erase(const Node& node) { + Arc arc; + Parent::firstOut(arc, node); + while (arc != INVALID ) { + erase(arc); + Parent::firstOut(arc, node); + } + + Parent::firstIn(arc, node); + while (arc != INVALID ) { + erase(arc); + Parent::firstIn(arc, node); + } + + if (Parent::red(node)) { + notifier(RedNode()).erase(this->asRedNodeUnsafe(node)); + } else { + notifier(BlueNode()).erase(this->asBlueNodeUnsafe(node)); + } + + notifier(Node()).erase(node); + Parent::erase(node); + } + + void erase(const Edge& edge) { + std::vector<Arc> av; + av.push_back(Parent::direct(edge, true)); + av.push_back(Parent::direct(edge, false)); + notifier(Arc()).erase(av); + notifier(Edge()).erase(edge); + Parent::erase(edge); + } + + BpGraphExtender() { + red_node_notifier.setContainer(*this); + blue_node_notifier.setContainer(*this); + node_notifier.setContainer(*this); + arc_notifier.setContainer(*this); + edge_notifier.setContainer(*this); + } + + ~BpGraphExtender() { + edge_notifier.clear(); + arc_notifier.clear(); + node_notifier.clear(); + blue_node_notifier.clear(); + red_node_notifier.clear(); + } + + }; + +} + +#endif diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/lock.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/lock.h new file mode 100644 index 00000000000..09069998cdb --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/lock.h @@ -0,0 +1,65 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2013 + * 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_LOCK_H +#define LEMON_BITS_LOCK_H + +#include <lemon/config.h> +#if defined(LEMON_USE_PTHREAD) +#include <pthread.h> +#elif defined(LEMON_USE_WIN32_THREADS) +#include <lemon/bits/windows.h> +#endif + +namespace lemon { + namespace bits { + +#if defined(LEMON_USE_PTHREAD) + class Lock { + public: + Lock() { + pthread_mutex_init(&_lock, 0); + } + ~Lock() { + pthread_mutex_destroy(&_lock); + } + void lock() { + pthread_mutex_lock(&_lock); + } + void unlock() { + pthread_mutex_unlock(&_lock); + } + + private: + pthread_mutex_t _lock; + }; +#elif defined(LEMON_USE_WIN32_THREADS) + class Lock : public WinLock {}; +#else + class Lock { + public: + Lock() {} + ~Lock() {} + void lock() {} + void unlock() {} + }; +#endif + } +} + +#endif diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/map_extender.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/map_extender.h new file mode 100644 index 00000000000..f32403e65ae --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/map_extender.h @@ -0,0 +1,332 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2013 + * 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_MAP_EXTENDER_H +#define LEMON_BITS_MAP_EXTENDER_H + +#include <iterator> + +#include <lemon/bits/traits.h> + +#include <lemon/concept_check.h> +#include <lemon/concepts/maps.h> + +//\file +//\brief Extenders for iterable maps. + +namespace lemon { + + // \ingroup graphbits + // + // \brief Extender for maps + template <typename _Map> + class MapExtender : public _Map { + typedef _Map Parent; + typedef typename Parent::GraphType GraphType; + + public: + + typedef MapExtender Map; + typedef typename Parent::Key Item; + + typedef typename Parent::Key Key; + typedef typename Parent::Value Value; + typedef typename Parent::Reference Reference; + typedef typename Parent::ConstReference ConstReference; + + typedef typename Parent::ReferenceMapTag ReferenceMapTag; + + class MapIt; + class ConstMapIt; + + friend class MapIt; + friend class ConstMapIt; + + public: + + MapExtender(const GraphType& graph) + : Parent(graph) {} + + MapExtender(const GraphType& graph, const Value& value) + : Parent(graph, value) {} + + private: + MapExtender& operator=(const MapExtender& cmap) { + return operator=<MapExtender>(cmap); + } + + template <typename CMap> + MapExtender& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + + public: + class MapIt : public Item { + typedef Item Parent; + + public: + + typedef typename Map::Value Value; + + MapIt() : map(NULL) {} + + MapIt(Invalid i) : Parent(i), map(NULL) {} + + explicit MapIt(Map& _map) : map(&_map) { + map->notifier()->first(*this); + } + + MapIt(const Map& _map, const Item& item) + : Parent(item), map(&_map) {} + + MapIt& operator++() { + map->notifier()->next(*this); + return *this; + } + + typename MapTraits<Map>::ConstReturnValue operator*() const { + return (*map)[*this]; + } + + typename MapTraits<Map>::ReturnValue operator*() { + return (*map)[*this]; + } + + void set(const Value& value) { + map->set(*this, value); + } + + protected: + Map* map; + + }; + + class ConstMapIt : public Item { + typedef Item Parent; + + public: + + typedef typename Map::Value Value; + + ConstMapIt() : map(NULL) {} + + ConstMapIt(Invalid i) : Parent(i), map(NULL) {} + + explicit ConstMapIt(Map& _map) : map(&_map) { + map->notifier()->first(*this); + } + + ConstMapIt(const Map& _map, const Item& item) + : Parent(item), map(_map) {} + + ConstMapIt& operator++() { + map->notifier()->next(*this); + return *this; + } + + typename MapTraits<Map>::ConstReturnValue operator*() const { + return map[*this]; + } + + protected: + const Map* map; + }; + + class ItemIt : public Item { + typedef Item Parent; + + public: + ItemIt() : map(NULL) {} + + + ItemIt(Invalid i) : Parent(i), map(NULL) {} + + explicit ItemIt(Map& _map) : map(&_map) { + map->notifier()->first(*this); + } + + ItemIt(const Map& _map, const Item& item) + : Parent(item), map(&_map) {} + + ItemIt& operator++() { + map->notifier()->next(*this); + return *this; + } + + protected: + const Map* map; + + }; + }; + + // \ingroup graphbits + // + // \brief Extender for maps which use a subset of the items. + template <typename _Graph, typename _Map> + class SubMapExtender : public _Map { + typedef _Map Parent; + typedef _Graph GraphType; + + public: + + typedef SubMapExtender Map; + typedef typename Parent::Key Item; + + typedef typename Parent::Key Key; + typedef typename Parent::Value Value; + typedef typename Parent::Reference Reference; + typedef typename Parent::ConstReference ConstReference; + + typedef typename Parent::ReferenceMapTag ReferenceMapTag; + + class MapIt; + class ConstMapIt; + + friend class MapIt; + friend class ConstMapIt; + + public: + + SubMapExtender(const GraphType& _graph) + : Parent(_graph), graph(_graph) {} + + SubMapExtender(const GraphType& _graph, const Value& _value) + : Parent(_graph, _value), graph(_graph) {} + + private: + SubMapExtender& operator=(const SubMapExtender& cmap) { + return operator=<MapExtender>(cmap); + } + + template <typename CMap> + SubMapExtender& operator=(const CMap& cmap) { + checkConcept<concepts::ReadMap<Key, Value>, CMap>(); + Item it; + for (graph.first(it); it != INVALID; graph.next(it)) { + Parent::set(it, cmap[it]); + } + return *this; + } + + public: + class MapIt : public Item { + typedef Item Parent; + + public: + typedef typename Map::Value Value; + + MapIt() : map(NULL) {} + + MapIt(Invalid i) : Parent(i), map(NULL) { } + + explicit MapIt(Map& _map) : map(&_map) { + map->graph.first(*this); + } + + MapIt(const Map& _map, const Item& item) + : Parent(item), map(&_map) {} + + MapIt& operator++() { + map->graph.next(*this); + return *this; + } + + typename MapTraits<Map>::ConstReturnValue operator*() const { + return (*map)[*this]; + } + + typename MapTraits<Map>::ReturnValue operator*() { + return (*map)[*this]; + } + + void set(const Value& value) { + map->set(*this, value); + } + + protected: + Map* map; + + }; + + class ConstMapIt : public Item { + typedef Item Parent; + + public: + + typedef typename Map::Value Value; + + ConstMapIt() : map(NULL) {} + + ConstMapIt(Invalid i) : Parent(i), map(NULL) { } + + explicit ConstMapIt(Map& _map) : map(&_map) { + map->graph.first(*this); + } + + ConstMapIt(const Map& _map, const Item& item) + : Parent(item), map(&_map) {} + + ConstMapIt& operator++() { + map->graph.next(*this); + return *this; + } + + typename MapTraits<Map>::ConstReturnValue operator*() const { + return (*map)[*this]; + } + + protected: + const Map* map; + }; + + class ItemIt : public Item { + typedef Item Parent; + + public: + ItemIt() : map(NULL) {} + + + ItemIt(Invalid i) : Parent(i), map(NULL) { } + + explicit ItemIt(Map& _map) : map(&_map) { + map->graph.first(*this); + } + + ItemIt(const Map& _map, const Item& item) + : Parent(item), map(&_map) {} + + ItemIt& operator++() { + map->graph.next(*this); + return *this; + } + + protected: + const Map* map; + + }; + + private: + + const GraphType& graph; + + }; + +} + +#endif diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/path_dump.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/path_dump.h new file mode 100644 index 00000000000..3e8cb8dd58c --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/path_dump.h @@ -0,0 +1,177 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2013 + * 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_PATH_DUMP_H +#define LEMON_BITS_PATH_DUMP_H + +#include <lemon/core.h> +#include <lemon/concept_check.h> + +namespace lemon { + + template <typename _Digraph, typename _PredMap> + class PredMapPath { + public: + typedef True RevPathTag; + + typedef _Digraph Digraph; + typedef typename Digraph::Arc Arc; + typedef _PredMap PredMap; + + PredMapPath(const Digraph& _digraph, const PredMap& _predMap, + typename Digraph::Node _target) + : digraph(_digraph), predMap(_predMap), target(_target) {} + + int length() const { + int len = 0; + typename Digraph::Node node = target; + typename Digraph::Arc arc; + while ((arc = predMap[node]) != INVALID) { + node = digraph.source(arc); + ++len; + } + return len; + } + + bool empty() const { + return predMap[target] == INVALID; + } + + class RevArcIt { + public: + RevArcIt() {} + RevArcIt(Invalid) : path(0), current(INVALID) {} + RevArcIt(const PredMapPath& _path) + : path(&_path), current(_path.target) { + if (path->predMap[current] == INVALID) current = INVALID; + } + + operator const typename Digraph::Arc() const { + return path->predMap[current]; + } + + RevArcIt& operator++() { + current = path->digraph.source(path->predMap[current]); + if (path->predMap[current] == INVALID) current = INVALID; + return *this; + } + + bool operator==(const RevArcIt& e) const { + return current == e.current; + } + + bool operator!=(const RevArcIt& e) const { + return current != e.current; + } + + bool operator<(const RevArcIt& e) const { + return current < e.current; + } + + private: + const PredMapPath* path; + typename Digraph::Node current; + }; + + private: + const Digraph& digraph; + const PredMap& predMap; + typename Digraph::Node target; + }; + + + template <typename _Digraph, typename _PredMatrixMap> + class PredMatrixMapPath { + public: + typedef True RevPathTag; + + typedef _Digraph Digraph; + typedef typename Digraph::Arc Arc; + typedef _PredMatrixMap PredMatrixMap; + + PredMatrixMapPath(const Digraph& _digraph, + const PredMatrixMap& _predMatrixMap, + typename Digraph::Node _source, + typename Digraph::Node _target) + : digraph(_digraph), predMatrixMap(_predMatrixMap), + source(_source), target(_target) {} + + int length() const { + int len = 0; + typename Digraph::Node node = target; + typename Digraph::Arc arc; + while ((arc = predMatrixMap(source, node)) != INVALID) { + node = digraph.source(arc); + ++len; + } + return len; + } + + bool empty() const { + return predMatrixMap(source, target) == INVALID; + } + + class RevArcIt { + public: + RevArcIt() {} + RevArcIt(Invalid) : path(0), current(INVALID) {} + RevArcIt(const PredMatrixMapPath& _path) + : path(&_path), current(_path.target) { + if (path->predMatrixMap(path->source, current) == INVALID) + current = INVALID; + } + + operator const typename Digraph::Arc() const { + return path->predMatrixMap(path->source, current); + } + + RevArcIt& operator++() { + current = + path->digraph.source(path->predMatrixMap(path->source, current)); + if (path->predMatrixMap(path->source, current) == INVALID) + current = INVALID; + return *this; + } + + bool operator==(const RevArcIt& e) const { + return current == e.current; + } + + bool operator!=(const RevArcIt& e) const { + return current != e.current; + } + + bool operator<(const RevArcIt& e) const { + return current < e.current; + } + + private: + const PredMatrixMapPath* path; + typename Digraph::Node current; + }; + + private: + const Digraph& digraph; + const PredMatrixMap& predMatrixMap; + typename Digraph::Node source; + typename Digraph::Node target; + }; + +} + +#endif diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/solver_bits.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/solver_bits.h new file mode 100644 index 00000000000..c34212be8cd --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/solver_bits.h @@ -0,0 +1,194 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2013 + * 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_SOLVER_BITS_H +#define LEMON_BITS_SOLVER_BITS_H + +#include <vector> + +namespace lemon { + + namespace _solver_bits { + + class VarIndex { + private: + struct ItemT { + int prev, next; + int index; + }; + std::vector<ItemT> items; + int first_item, last_item, first_free_item; + + std::vector<int> cross; + + public: + + VarIndex() + : first_item(-1), last_item(-1), first_free_item(-1) { + } + + void clear() { + first_item = -1; + last_item = -1; + first_free_item = -1; + items.clear(); + cross.clear(); + } + + int addIndex(int idx) { + int n; + if (first_free_item == -1) { + n = items.size(); + items.push_back(ItemT()); + } else { + n = first_free_item; + first_free_item = items[n].next; + if (first_free_item != -1) { + items[first_free_item].prev = -1; + } + } + items[n].index = idx; + if (static_cast<int>(cross.size()) <= idx) { + cross.resize(idx + 1, -1); + } + cross[idx] = n; + + items[n].prev = last_item; + items[n].next = -1; + if (last_item != -1) { + items[last_item].next = n; + } else { + first_item = n; + } + last_item = n; + + return n; + } + + int addIndex(int idx, int n) { + while (n >= static_cast<int>(items.size())) { + items.push_back(ItemT()); + items.back().prev = -1; + items.back().next = first_free_item; + if (first_free_item != -1) { + items[first_free_item].prev = items.size() - 1; + } + first_free_item = items.size() - 1; + } + if (items[n].next != -1) { + items[items[n].next].prev = items[n].prev; + } + if (items[n].prev != -1) { + items[items[n].prev].next = items[n].next; + } else { + first_free_item = items[n].next; + } + + items[n].index = idx; + if (static_cast<int>(cross.size()) <= idx) { + cross.resize(idx + 1, -1); + } + cross[idx] = n; + + items[n].prev = last_item; + items[n].next = -1; + if (last_item != -1) { + items[last_item].next = n; + } else { + first_item = n; + } + last_item = n; + + return n; + } + + void eraseIndex(int idx) { + int n = cross[idx]; + + if (items[n].prev != -1) { + items[items[n].prev].next = items[n].next; + } else { + first_item = items[n].next; + } + if (items[n].next != -1) { + items[items[n].next].prev = items[n].prev; + } else { + last_item = items[n].prev; + } + + if (first_free_item != -1) { + items[first_free_item].prev = n; + } + items[n].next = first_free_item; + items[n].prev = -1; + first_free_item = n; + + while (!cross.empty() && cross.back() == -1) { + cross.pop_back(); + } + } + + int maxIndex() const { + return cross.size() - 1; + } + + void shiftIndices(int idx) { + for (int i = idx + 1; i < static_cast<int>(cross.size()); ++i) { + cross[i - 1] = cross[i]; + if (cross[i] != -1) { + --items[cross[i]].index; + } + } + cross.back() = -1; + cross.pop_back(); + while (!cross.empty() && cross.back() == -1) { + cross.pop_back(); + } + } + + void relocateIndex(int idx, int jdx) { + cross[idx] = cross[jdx]; + items[cross[jdx]].index = idx; + cross[jdx] = -1; + + while (!cross.empty() && cross.back() == -1) { + cross.pop_back(); + } + } + + int operator[](int idx) const { + return cross[idx]; + } + + int operator()(int fdx) const { + return items[fdx].index; + } + + void firstItem(int& fdx) const { + fdx = first_item; + } + + void nextItem(int& fdx) const { + fdx = items[fdx].next; + } + + }; + } +} + +#endif diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/traits.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/traits.h new file mode 100644 index 00000000000..53fbd45647a --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/traits.h @@ -0,0 +1,388 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2013 + * 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_TRAITS_H +#define LEMON_BITS_TRAITS_H + +//\file +//\brief Traits for graphs and maps +// + +#include <lemon/bits/enable_if.h> + +namespace lemon { + + struct InvalidType {}; + + template <typename GR, typename _Item> + class ItemSetTraits {}; + + + template <typename GR, typename Enable = void> + struct NodeNotifierIndicator { + typedef InvalidType Type; + }; + template <typename GR> + struct NodeNotifierIndicator< + GR, + typename enable_if<typename GR::NodeNotifier::Notifier, void>::type + > { + typedef typename GR::NodeNotifier Type; + }; + + template <typename GR> + class ItemSetTraits<GR, typename GR::Node> { + public: + + typedef GR Graph; + typedef GR Digraph; + + typedef typename GR::Node Item; + typedef typename GR::NodeIt ItemIt; + + typedef typename NodeNotifierIndicator<GR>::Type ItemNotifier; + + template <typename V> + class Map : public GR::template NodeMap<V> { + typedef typename GR::template NodeMap<V> Parent; + + public: + typedef typename GR::template NodeMap<V> Type; + typedef typename Parent::Value Value; + + Map(const GR& _digraph) : Parent(_digraph) {} + Map(const GR& _digraph, const Value& _value) + : Parent(_digraph, _value) {} + + }; + + }; + + template <typename GR, typename Enable = void> + struct ArcNotifierIndicator { + typedef InvalidType Type; + }; + template <typename GR> + struct ArcNotifierIndicator< + GR, + typename enable_if<typename GR::ArcNotifier::Notifier, void>::type + > { + typedef typename GR::ArcNotifier Type; + }; + + template <typename GR> + class ItemSetTraits<GR, typename GR::Arc> { + public: + + typedef GR Graph; + typedef GR Digraph; + + typedef typename GR::Arc Item; + typedef typename GR::ArcIt ItemIt; + + typedef typename ArcNotifierIndicator<GR>::Type ItemNotifier; + + template <typename V> + class Map : public GR::template ArcMap<V> { + typedef typename GR::template ArcMap<V> Parent; + + public: + typedef typename GR::template ArcMap<V> Type; + typedef typename Parent::Value Value; + + Map(const GR& _digraph) : Parent(_digraph) {} + Map(const GR& _digraph, const Value& _value) + : Parent(_digraph, _value) {} + }; + + }; + + template <typename GR, typename Enable = void> + struct EdgeNotifierIndicator { + typedef InvalidType Type; + }; + template <typename GR> + struct EdgeNotifierIndicator< + GR, + typename enable_if<typename GR::EdgeNotifier::Notifier, void>::type + > { + typedef typename GR::EdgeNotifier Type; + }; + + template <typename GR> + class ItemSetTraits<GR, typename GR::Edge> { + public: + + typedef GR Graph; + typedef GR Digraph; + + typedef typename GR::Edge Item; + typedef typename GR::EdgeIt ItemIt; + + typedef typename EdgeNotifierIndicator<GR>::Type ItemNotifier; + + template <typename V> + class Map : public GR::template EdgeMap<V> { + typedef typename GR::template EdgeMap<V> Parent; + + public: + typedef typename GR::template EdgeMap<V> Type; + typedef typename Parent::Value Value; + + Map(const GR& _digraph) : Parent(_digraph) {} + Map(const GR& _digraph, const Value& _value) + : Parent(_digraph, _value) {} + }; + + }; + + template <typename GR, typename Enable = void> + struct RedNodeNotifierIndicator { + typedef InvalidType Type; + }; + template <typename GR> + struct RedNodeNotifierIndicator< + GR, + typename enable_if<typename GR::RedNodeNotifier::Notifier, void>::type + > { + typedef typename GR::RedNodeNotifier Type; + }; + + template <typename GR> + class ItemSetTraits<GR, typename GR::RedNode> { + public: + + typedef GR BpGraph; + typedef GR Graph; + typedef GR Digraph; + + typedef typename GR::RedNode Item; + typedef typename GR::RedNodeIt ItemIt; + + typedef typename RedNodeNotifierIndicator<GR>::Type ItemNotifier; + + template <typename V> + class Map : public GR::template RedNodeMap<V> { + typedef typename GR::template RedNodeMap<V> Parent; + + public: + typedef typename GR::template RedNodeMap<V> Type; + typedef typename Parent::Value Value; + + Map(const GR& _bpgraph) : Parent(_bpgraph) {} + Map(const GR& _bpgraph, const Value& _value) + : Parent(_bpgraph, _value) {} + + }; + + }; + + template <typename GR, typename Enable = void> + struct BlueNodeNotifierIndicator { + typedef InvalidType Type; + }; + template <typename GR> + struct BlueNodeNotifierIndicator< + GR, + typename enable_if<typename GR::BlueNodeNotifier::Notifier, void>::type + > { + typedef typename GR::BlueNodeNotifier Type; + }; + + template <typename GR> + class ItemSetTraits<GR, typename GR::BlueNode> { + public: + + typedef GR BpGraph; + typedef GR Graph; + typedef GR Digraph; + + typedef typename GR::BlueNode Item; + typedef typename GR::BlueNodeIt ItemIt; + + typedef typename BlueNodeNotifierIndicator<GR>::Type ItemNotifier; + + template <typename V> + class Map : public GR::template BlueNodeMap<V> { + typedef typename GR::template BlueNodeMap<V> Parent; + + public: + typedef typename GR::template BlueNodeMap<V> Type; + typedef typename Parent::Value Value; + + Map(const GR& _bpgraph) : Parent(_bpgraph) {} + Map(const GR& _bpgraph, const Value& _value) + : Parent(_bpgraph, _value) {} + + }; + + }; + + template <typename Map, typename Enable = void> + struct MapTraits { + typedef False ReferenceMapTag; + + typedef typename Map::Key Key; + typedef typename Map::Value Value; + + typedef Value ConstReturnValue; + typedef Value ReturnValue; + }; + + template <typename Map> + struct MapTraits< + Map, typename enable_if<typename Map::ReferenceMapTag, void>::type > + { + typedef True ReferenceMapTag; + + typedef typename Map::Key Key; + typedef typename Map::Value Value; + + typedef typename Map::ConstReference ConstReturnValue; + typedef typename Map::Reference ReturnValue; + + typedef typename Map::ConstReference ConstReference; + typedef typename Map::Reference Reference; + }; + + template <typename MatrixMap, typename Enable = void> + struct MatrixMapTraits { + typedef False ReferenceMapTag; + + typedef typename MatrixMap::FirstKey FirstKey; + typedef typename MatrixMap::SecondKey SecondKey; + typedef typename MatrixMap::Value Value; + + typedef Value ConstReturnValue; + typedef Value ReturnValue; + }; + + template <typename MatrixMap> + struct MatrixMapTraits< + MatrixMap, typename enable_if<typename MatrixMap::ReferenceMapTag, + void>::type > + { + typedef True ReferenceMapTag; + + typedef typename MatrixMap::FirstKey FirstKey; + typedef typename MatrixMap::SecondKey SecondKey; + typedef typename MatrixMap::Value Value; + + typedef typename MatrixMap::ConstReference ConstReturnValue; + typedef typename MatrixMap::Reference ReturnValue; + + typedef typename MatrixMap::ConstReference ConstReference; + typedef typename MatrixMap::Reference Reference; + }; + + // Indicators for the tags + + template <typename GR, typename Enable = void> + struct NodeNumTagIndicator { + static const bool value = false; + }; + + template <typename GR> + struct NodeNumTagIndicator< + GR, + typename enable_if<typename GR::NodeNumTag, void>::type + > { + static const bool value = true; + }; + + template <typename GR, typename Enable = void> + struct ArcNumTagIndicator { + static const bool value = false; + }; + + template <typename GR> + struct ArcNumTagIndicator< + GR, + typename enable_if<typename GR::ArcNumTag, void>::type + > { + static const bool value = true; + }; + + template <typename GR, typename Enable = void> + struct EdgeNumTagIndicator { + static const bool value = false; + }; + + template <typename GR> + struct EdgeNumTagIndicator< + GR, + typename enable_if<typename GR::EdgeNumTag, void>::type + > { + static const bool value = true; + }; + + template <typename GR, typename Enable = void> + struct FindArcTagIndicator { + static const bool value = false; + }; + + template <typename GR> + struct FindArcTagIndicator< + GR, + typename enable_if<typename GR::FindArcTag, void>::type + > { + static const bool value = true; + }; + + template <typename GR, typename Enable = void> + struct FindEdgeTagIndicator { + static const bool value = false; + }; + + template <typename GR> + struct FindEdgeTagIndicator< + GR, + typename enable_if<typename GR::FindEdgeTag, void>::type + > { + static const bool value = true; + }; + + template <typename GR, typename Enable = void> + struct UndirectedTagIndicator { + static const bool value = false; + }; + + template <typename GR> + struct UndirectedTagIndicator< + GR, + typename enable_if<typename GR::UndirectedTag, void>::type + > { + static const bool value = true; + }; + + template <typename GR, typename Enable = void> + struct BuildTagIndicator { + static const bool value = false; + }; + + template <typename GR> + struct BuildTagIndicator< + GR, + typename enable_if<typename GR::BuildTag, void>::type + > { + static const bool value = true; + }; + +} + +#endif diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/variant.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/variant.h new file mode 100644 index 00000000000..b8301892e61 --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/variant.h @@ -0,0 +1,494 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * 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_VARIANT_H +#define LEMON_BITS_VARIANT_H + +#include <lemon/assert.h> + +// \file +// \brief Variant types + +namespace lemon { + + namespace _variant_bits { + + template <int left, int right> + struct CTMax { + static const int value = left < right ? right : left; + }; + + } + + + // \brief Simple Variant type for two types + // + // Simple Variant type for two types. The Variant type is a type-safe + // union. C++ has strong limitations for using unions, for + // example you cannot store a type with non-default constructor or + // destructor in a union. This class always knowns the current + // state of the variant and it cares for the proper construction + // and destruction. + template <typename _First, typename _Second> + class BiVariant { + public: + + // \brief The \c First type. + typedef _First First; + // \brief The \c Second type. + typedef _Second Second; + + // \brief Constructor + // + // This constructor initalizes to the default value of the \c First + // type. + BiVariant() { + flag = true; + new(reinterpret_cast<First*>(data)) First(); + } + + // \brief Constructor + // + // This constructor initalizes to the given value of the \c First + // type. + BiVariant(const First& f) { + flag = true; + new(reinterpret_cast<First*>(data)) First(f); + } + + // \brief Constructor + // + // This constructor initalizes to the given value of the \c + // Second type. + BiVariant(const Second& s) { + flag = false; + new(reinterpret_cast<Second*>(data)) Second(s); + } + + // \brief Copy constructor + // + // Copy constructor + BiVariant(const BiVariant& bivariant) { + flag = bivariant.flag; + if (flag) { + new(reinterpret_cast<First*>(data)) First(bivariant.first()); + } else { + new(reinterpret_cast<Second*>(data)) Second(bivariant.second()); + } + } + + // \brief Destrcutor + // + // Destructor + ~BiVariant() { + destroy(); + } + + // \brief Set to the default value of the \c First type. + // + // This function sets the variant to the default value of the \c + // First type. + BiVariant& setFirst() { + destroy(); + flag = true; + new(reinterpret_cast<First*>(data)) First(); + return *this; + } + + // \brief Set to the given value of the \c First type. + // + // This function sets the variant to the given value of the \c + // First type. + BiVariant& setFirst(const First& f) { + destroy(); + flag = true; + new(reinterpret_cast<First*>(data)) First(f); + return *this; + } + + // \brief Set to the default value of the \c Second type. + // + // This function sets the variant to the default value of the \c + // Second type. + BiVariant& setSecond() { + destroy(); + flag = false; + new(reinterpret_cast<Second*>(data)) Second(); + return *this; + } + + // \brief Set to the given value of the \c Second type. + // + // This function sets the variant to the given value of the \c + // Second type. + BiVariant& setSecond(const Second& s) { + destroy(); + flag = false; + new(reinterpret_cast<Second*>(data)) Second(s); + return *this; + } + + // \brief Operator form of the \c setFirst() + BiVariant& operator=(const First& f) { + return setFirst(f); + } + + // \brief Operator form of the \c setSecond() + BiVariant& operator=(const Second& s) { + return setSecond(s); + } + + // \brief Assign operator + BiVariant& operator=(const BiVariant& bivariant) { + if (this == &bivariant) return *this; + destroy(); + flag = bivariant.flag; + if (flag) { + new(reinterpret_cast<First*>(data)) First(bivariant.first()); + } else { + new(reinterpret_cast<Second*>(data)) Second(bivariant.second()); + } + return *this; + } + + // \brief Reference to the value + // + // Reference to the value of the \c First type. + // \pre The BiVariant should store value of \c First type. + First& first() { + LEMON_DEBUG(flag, "Variant wrong state"); + return *reinterpret_cast<First*>(data); + } + + // \brief Const reference to the value + // + // Const reference to the value of the \c First type. + // \pre The BiVariant should store value of \c First type. + const First& first() const { + LEMON_DEBUG(flag, "Variant wrong state"); + return *reinterpret_cast<const First*>(data); + } + + // \brief Operator form of the \c first() + operator First&() { return first(); } + // \brief Operator form of the const \c first() + operator const First&() const { return first(); } + + // \brief Reference to the value + // + // Reference to the value of the \c Second type. + // \pre The BiVariant should store value of \c Second type. + Second& second() { + LEMON_DEBUG(!flag, "Variant wrong state"); + return *reinterpret_cast<Second*>(data); + } + + // \brief Const reference to the value + // + // Const reference to the value of the \c Second type. + // \pre The BiVariant should store value of \c Second type. + const Second& second() const { + LEMON_DEBUG(!flag, "Variant wrong state"); + return *reinterpret_cast<const Second*>(data); + } + + // \brief Operator form of the \c second() + operator Second&() { return second(); } + // \brief Operator form of the const \c second() + operator const Second&() const { return second(); } + + // \brief %True when the variant is in the first state + // + // %True when the variant stores value of the \c First type. + bool firstState() const { return flag; } + + // \brief %True when the variant is in the second state + // + // %True when the variant stores value of the \c Second type. + bool secondState() const { return !flag; } + + private: + + void destroy() { + if (flag) { + reinterpret_cast<First*>(data)->~First(); + } else { + reinterpret_cast<Second*>(data)->~Second(); + } + } + + char data[_variant_bits::CTMax<sizeof(First), sizeof(Second)>::value]; + bool flag; + }; + + namespace _variant_bits { + + template <int _idx, typename _TypeMap> + struct Memory { + + typedef typename _TypeMap::template Map<_idx>::Type Current; + + static void destroy(int index, char* place) { + if (index == _idx) { + reinterpret_cast<Current*>(place)->~Current(); + } else { + Memory<_idx - 1, _TypeMap>::destroy(index, place); + } + } + + static void copy(int index, char* to, const char* from) { + if (index == _idx) { + new (reinterpret_cast<Current*>(to)) + Current(reinterpret_cast<const Current*>(from)); + } else { + Memory<_idx - 1, _TypeMap>::copy(index, to, from); + } + } + + }; + + template <typename _TypeMap> + struct Memory<-1, _TypeMap> { + + static void destroy(int, char*) { + LEMON_DEBUG(false, "Variant wrong index."); + } + + static void copy(int, char*, const char*) { + LEMON_DEBUG(false, "Variant wrong index."); + } + }; + + template <int _idx, typename _TypeMap> + struct Size { + static const int value = + CTMax<sizeof(typename _TypeMap::template Map<_idx>::Type), + Size<_idx - 1, _TypeMap>::value>::value; + }; + + template <typename _TypeMap> + struct Size<0, _TypeMap> { + static const int value = + sizeof(typename _TypeMap::template Map<0>::Type); + }; + + } + + // \brief Variant type + // + // Simple Variant type. The Variant type is a type-safe union. + // C++ has strong limitations for using unions, for example you + // cannot store type with non-default constructor or destructor in + // a union. This class always knowns the current state of the + // variant and it cares for the proper construction and + // destruction. + // + // \param _num The number of the types which can be stored in the + // variant type. + // \param _TypeMap This class describes the types of the Variant. The + // _TypeMap::Map<index>::Type should be a valid type for each index + // in the range {0, 1, ..., _num - 1}. The \c VariantTypeMap is helper + // class to define such type mappings up to 10 types. + // + // And the usage of the class: + //\code + // typedef Variant<3, VariantTypeMap<int, std::string, double> > MyVariant; + // MyVariant var; + // var.set<0>(12); + // std::cout << var.get<0>() << std::endl; + // var.set<1>("alpha"); + // std::cout << var.get<1>() << std::endl; + // var.set<2>(0.75); + // std::cout << var.get<2>() << std::endl; + //\endcode + // + // The result of course: + //\code + // 12 + // alpha + // 0.75 + //\endcode + template <int _num, typename _TypeMap> + class Variant { + public: + + static const int num = _num; + + typedef _TypeMap TypeMap; + + // \brief Constructor + // + // This constructor initalizes to the default value of the \c type + // with 0 index. + Variant() { + flag = 0; + new(reinterpret_cast<typename TypeMap::template Map<0>::Type*>(data)) + typename TypeMap::template Map<0>::Type(); + } + + + // \brief Copy constructor + // + // Copy constructor + Variant(const Variant& variant) { + flag = variant.flag; + _variant_bits::Memory<num - 1, TypeMap>::copy(flag, data, variant.data); + } + + // \brief Assign operator + // + // Assign operator + Variant& operator=(const Variant& variant) { + if (this == &variant) return *this; + _variant_bits::Memory<num - 1, TypeMap>:: + destroy(flag, data); + flag = variant.flag; + _variant_bits::Memory<num - 1, TypeMap>:: + copy(flag, data, variant.data); + return *this; + } + + // \brief Destrcutor + // + // Destructor + ~Variant() { + _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data); + } + + // \brief Set to the default value of the type with \c _idx index. + // + // This function sets the variant to the default value of the + // type with \c _idx index. + template <int _idx> + Variant& set() { + _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data); + flag = _idx; + new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data)) + typename TypeMap::template Map<_idx>::Type(); + return *this; + } + + // \brief Set to the given value of the type with \c _idx index. + // + // This function sets the variant to the given value of the type + // with \c _idx index. + template <int _idx> + Variant& set(const typename _TypeMap::template Map<_idx>::Type& init) { + _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data); + flag = _idx; + new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data)) + typename TypeMap::template Map<_idx>::Type(init); + return *this; + } + + // \brief Gets the current value of the type with \c _idx index. + // + // Gets the current value of the type with \c _idx index. + template <int _idx> + const typename TypeMap::template Map<_idx>::Type& get() const { + LEMON_DEBUG(_idx == flag, "Variant wrong index"); + return *reinterpret_cast<const typename TypeMap:: + template Map<_idx>::Type*>(data); + } + + // \brief Gets the current value of the type with \c _idx index. + // + // Gets the current value of the type with \c _idx index. + template <int _idx> + typename _TypeMap::template Map<_idx>::Type& get() { + LEMON_DEBUG(_idx == flag, "Variant wrong index"); + return *reinterpret_cast<typename TypeMap::template Map<_idx>::Type*> + (data); + } + + // \brief Returns the current state of the variant. + // + // Returns the current state of the variant. + int state() const { + return flag; + } + + private: + + char data[_variant_bits::Size<num - 1, TypeMap>::value]; + int flag; + }; + + namespace _variant_bits { + + template <int _index, typename _List> + struct Get { + typedef typename Get<_index - 1, typename _List::Next>::Type Type; + }; + + template <typename _List> + struct Get<0, _List> { + typedef typename _List::Type Type; + }; + + struct List {}; + + template <typename _Type, typename _List> + struct Insert { + typedef _List Next; + typedef _Type Type; + }; + + template <int _idx, typename _T0, typename _T1, typename _T2, + typename _T3, typename _T4, typename _T5, typename _T6, + typename _T7, typename _T8, typename _T9> + struct Mapper { + typedef List L10; + typedef Insert<_T9, L10> L9; + typedef Insert<_T8, L9> L8; + typedef Insert<_T7, L8> L7; + typedef Insert<_T6, L7> L6; + typedef Insert<_T5, L6> L5; + typedef Insert<_T4, L5> L4; + typedef Insert<_T3, L4> L3; + typedef Insert<_T2, L3> L2; + typedef Insert<_T1, L2> L1; + typedef Insert<_T0, L1> L0; + typedef typename Get<_idx, L0>::Type Type; + }; + + } + + // \brief Helper class for Variant + // + // Helper class to define type mappings for Variant. This class + // converts the template parameters to be mappable by integer. + // \see Variant + template < + typename _T0, + typename _T1 = void, typename _T2 = void, typename _T3 = void, + typename _T4 = void, typename _T5 = void, typename _T6 = void, + typename _T7 = void, typename _T8 = void, typename _T9 = void> + struct VariantTypeMap { + template <int _idx> + struct Map { + typedef typename _variant_bits:: + Mapper<_idx, _T0, _T1, _T2, _T3, _T4, _T5, _T6, _T7, _T8, _T9>::Type + Type; + }; + }; + +} + + +#endif diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/vector_map.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/vector_map.h new file mode 100644 index 00000000000..d60841defbd --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/vector_map.h @@ -0,0 +1,244 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * 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_VECTOR_MAP_H +#define LEMON_BITS_VECTOR_MAP_H + +#include <vector> +#include <algorithm> + +#include <lemon/core.h> +#include <lemon/bits/alteration_notifier.h> + +#include <lemon/concept_check.h> +#include <lemon/concepts/maps.h> + +//\ingroup graphbits +// +//\file +//\brief Vector based graph maps. +namespace lemon { + + // \ingroup graphbits + // + // \brief Graph map based on the std::vector storage. + // + // The VectorMap template class is graph map structure that automatically + // updates the map when a key is added to or erased from the graph. + // This map type uses std::vector to store the values. + // + // \tparam _Graph The graph this map is attached to. + // \tparam _Item The item type of the graph items. + // \tparam _Value The value type of the map. + template <typename _Graph, typename _Item, typename _Value> + class VectorMap + : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { + private: + + // The container type of the map. + typedef std::vector<_Value> Container; + + public: + + // The graph type of the map. + typedef _Graph GraphType; + // The item type of the map. + typedef _Item Item; + // The reference map tag. + typedef True ReferenceMapTag; + + // The key type of the map. + typedef _Item Key; + // The value type of the map. + typedef _Value Value; + + // The notifier type. + typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier; + + // The map type. + typedef VectorMap Map; + + // The reference type of the map; + typedef typename Container::reference Reference; + // The const reference type of the map; + typedef typename Container::const_reference ConstReference; + + private: + + // The base class of the map. + typedef typename Notifier::ObserverBase Parent; + + public: + + // \brief Constructor to attach the new map into the notifier. + // + // It constructs a map and attachs it into the notifier. + // It adds all the items of the graph to the map. + VectorMap(const GraphType& graph) { + Parent::attach(graph.notifier(Item())); + container.resize(Parent::notifier()->maxId() + 1); + } + + // \brief Constructor uses given value to initialize the map. + // + // It constructs a map uses a given value to initialize the map. + // It adds all the items of the graph to the map. + VectorMap(const GraphType& graph, const Value& value) { + Parent::attach(graph.notifier(Item())); + container.resize(Parent::notifier()->maxId() + 1, value); + } + + private: + // \brief Copy constructor + // + // Copy constructor. + VectorMap(const VectorMap& _copy) : Parent() { + if (_copy.attached()) { + Parent::attach(*_copy.notifier()); + container = _copy.container; + } + } + + // \brief Assign operator. + // + // This operator assigns for each item in the map the + // value mapped to the same item in the copied map. + // The parameter map should be indiced with the same + // itemset because this assign operator does not change + // the container of the map. + VectorMap& operator=(const VectorMap& cmap) { + return operator=<VectorMap>(cmap); + } + + + // \brief Template assign operator. + // + // The given parameter should conform to the ReadMap + // concecpt and could be indiced by the current item set of + // the NodeMap. In this case the value for each item + // is assigned by the value of the given ReadMap. + template <typename CMap> + VectorMap& operator=(const CMap& cmap) { + checkConcept<concepts::ReadMap<Key, _Value>, CMap>(); + const typename Parent::Notifier* nf = Parent::notifier(); + Item it; + for (nf->first(it); it != INVALID; nf->next(it)) { + set(it, cmap[it]); + } + return *this; + } + + public: + + // \brief The subcript operator. + // + // The subscript operator. The map can be subscripted by the + // actual items of the graph. + Reference operator[](const Key& key) { + return container[Parent::notifier()->id(key)]; + } + + // \brief The const subcript operator. + // + // The const subscript operator. The map can be subscripted by the + // actual items of the graph. + ConstReference operator[](const Key& key) const { + return container[Parent::notifier()->id(key)]; + } + + + // \brief The setter function of the map. + // + // It the same as operator[](key) = value expression. + void set(const Key& key, const Value& value) { + (*this)[key] = value; + } + + protected: + + // \brief Adds a new key to the map. + // + // It adds a new key to the map. It is called by the observer notifier + // and it overrides the add() member function of the observer base. + virtual void add(const Key& key) { + int id = Parent::notifier()->id(key); + if (id >= int(container.size())) { + container.resize(id + 1); + } + } + + // \brief Adds more new keys to the map. + // + // It adds more new keys to the map. It is called by the observer notifier + // and it overrides the add() member function of the observer base. + virtual void add(const std::vector<Key>& keys) { + int max = container.size() - 1; + for (int i = 0; i < int(keys.size()); ++i) { + int id = Parent::notifier()->id(keys[i]); + if (id >= max) { + max = id; + } + } + container.resize(max + 1); + } + + // \brief Erase a key from the map. + // + // Erase a key from the map. It is called by the observer notifier + // and it overrides the erase() member function of the observer base. + virtual void erase(const Key& key) { + container[Parent::notifier()->id(key)] = Value(); + } + + // \brief Erase more keys from the map. + // + // It erases more keys from the map. It is called by the observer notifier + // and it overrides the erase() member function of the observer base. + virtual void erase(const std::vector<Key>& keys) { + for (int i = 0; i < int(keys.size()); ++i) { + container[Parent::notifier()->id(keys[i])] = Value(); + } + } + + // \brief Build the map. + // + // It builds the map. It is called by the observer notifier + // and it overrides the build() member function of the observer base. + virtual void build() { + int size = Parent::notifier()->maxId() + 1; + container.reserve(size); + container.resize(size); + } + + // \brief Clear the map. + // + // It erases all items from the map. It is called by the observer notifier + // and it overrides the clear() member function of the observer base. + virtual void clear() { + container.clear(); + } + + private: + + Container container; + + }; + +} + +#endif diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/windows.cc b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/windows.cc new file mode 100644 index 00000000000..7ad901c619c --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/windows.cc @@ -0,0 +1,166 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2013 + * 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 functions and static global data. + +#include<lemon/bits/windows.h> + +#ifdef WIN32 +#ifndef WIN32_LEAN_AND_MEAN +#define WIN32_LEAN_AND_MEAN +#endif +#ifndef NOMINMAX +#define NOMINMAX +#endif +#ifdef UNICODE +#undef UNICODE +#endif +#include <windows.h> +#ifdef LOCALE_INVARIANT +#define MY_LOCALE LOCALE_INVARIANT +#else +#define MY_LOCALE LOCALE_NEUTRAL +#endif +#else +#include <unistd.h> +#include <ctime> +#ifndef WIN32 +#include <sys/times.h> +#endif +#include <sys/time.h> +#endif + +#include <cmath> +#include <sstream> + +namespace lemon { + namespace bits { + void getWinProcTimes(double &rtime, + double &utime, double &stime, + double &cutime, double &cstime) + { +#ifdef WIN32 + static const double ch = 4294967296.0e-7; + static const double cl = 1.0e-7; + + FILETIME system; + GetSystemTimeAsFileTime(&system); + rtime = ch * system.dwHighDateTime + cl * system.dwLowDateTime; + + FILETIME create, exit, kernel, user; + if (GetProcessTimes(GetCurrentProcess(),&create, &exit, &kernel, &user)) { + utime = ch * user.dwHighDateTime + cl * user.dwLowDateTime; + stime = ch * kernel.dwHighDateTime + cl * kernel.dwLowDateTime; + cutime = 0; + cstime = 0; + } else { + rtime = 0; + utime = 0; + stime = 0; + cutime = 0; + cstime = 0; + } +#else + timeval tv; + gettimeofday(&tv, 0); + rtime=tv.tv_sec+double(tv.tv_usec)/1e6; + + tms ts; + double tck=sysconf(_SC_CLK_TCK); + times(&ts); + utime=ts.tms_utime/tck; + stime=ts.tms_stime/tck; + cutime=ts.tms_cutime/tck; + cstime=ts.tms_cstime/tck; +#endif + } + + std::string getWinFormattedDate() + { + std::ostringstream os; +#ifdef WIN32 + SYSTEMTIME time; + GetSystemTime(&time); + char buf1[11], buf2[9], buf3[5]; + if (GetDateFormat(MY_LOCALE, 0, &time, + ("ddd MMM dd"), buf1, 11) && + GetTimeFormat(MY_LOCALE, 0, &time, + ("HH':'mm':'ss"), buf2, 9) && + GetDateFormat(MY_LOCALE, 0, &time, + ("yyyy"), buf3, 5)) { + os << buf1 << ' ' << buf2 << ' ' << buf3; + } + else os << "unknown"; +#else + timeval tv; + gettimeofday(&tv, 0); + + char cbuf[26]; + ctime_r(&tv.tv_sec,cbuf); + os << cbuf; +#endif + return os.str(); + } + + int getWinRndSeed() + { +#ifdef WIN32 + FILETIME time; + GetSystemTimeAsFileTime(&time); + return GetCurrentProcessId() + time.dwHighDateTime + time.dwLowDateTime; +#else + timeval tv; + gettimeofday(&tv, 0); + return getpid() + tv.tv_sec + tv.tv_usec; +#endif + } + + WinLock::WinLock() { +#ifdef WIN32 + CRITICAL_SECTION *lock = new CRITICAL_SECTION; + InitializeCriticalSection(lock); + _repr = lock; +#else + _repr = 0; //Just to avoid 'unused variable' warning with clang +#endif + } + + WinLock::~WinLock() { +#ifdef WIN32 + CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr); + DeleteCriticalSection(lock); + delete lock; +#endif + } + + void WinLock::lock() { +#ifdef WIN32 + CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr); + EnterCriticalSection(lock); +#endif + } + + void WinLock::unlock() { +#ifdef WIN32 + CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr); + LeaveCriticalSection(lock); +#endif + } + } +} diff --git a/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/windows.h b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/windows.h new file mode 100644 index 00000000000..c09bb1284c5 --- /dev/null +++ b/extern/quadriflow/3rd/lemon-1.3.1/lemon/bits/windows.h @@ -0,0 +1,44 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2013 + * 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_WINDOWS_H +#define LEMON_BITS_WINDOWS_H + +#include <string> + +namespace lemon { + namespace bits { + void getWinProcTimes(double &rtime, + double &utime, double &stime, + double &cutime, double &cstime); + std::string getWinFormattedDate(); + int getWinRndSeed(); + + class WinLock { + public: + WinLock(); + ~WinLock(); + void lock(); + void unlock(); + private: + void *_repr; + }; + } +} + +#endif |