Mercuriallemon-main / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/bits/traits.h
author Balazs Dezso <deba@inf.elte.hu>
Fri, 11 Jul 2008 15:01:49 +0200
changeset 203 215bfc30b14f
parent 139 701c529ba737
child 209 765619b7cbb2
permissions -rw-r--r--
Cleaning of heap test and bug fix in heap concept check (ticket #100)

* The dijkstra heap test's digraph is inlined into the source file
* The random sequences are fixed
* The content of the header is moved to the source file
* Only the binary heap is checked 
     1 

     2 /* -*- C++ -*-

     3  *

     4  * This file is a part of LEMON, a generic C++ optimization library

     5  *

     6  * Copyright (C) 2003-2008

     7  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     8  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     9  *

    10  * Permission to use, modify and distribute this software is granted

    11  * provided that this copyright notice appears in all copies. For

    12  * precise terms see the accompanying LICENSE file.

    13  *

    14  * This software is provided "AS IS" with no warranty of any kind,

    15  * express or implied, and with no claim as to its suitability for any

    16  * purpose.

    17  *

    18  */

    19 

    20 #ifndef LEMON_BITS_TRAITS_H

    21 #define LEMON_BITS_TRAITS_H

    22 

    23 #include <lemon/bits/utility.h>

    24 

    25 ///\file

    26 ///\brief Traits for graphs and maps

    27 ///

    28 

    29 namespace lemon {

    30   template <typename _Graph, typename _Item>

    31   class ItemSetTraits {};

    32   

    33 

    34   template <typename Graph, typename Enable = void>

    35   struct NodeNotifierIndicator {

    36     typedef InvalidType Type;

    37   };

    38   template <typename Graph>

    39   struct NodeNotifierIndicator<

    40     Graph, 

    41     typename enable_if<typename Graph::NodeNotifier::Notifier, void>::type

    42   > { 

    43     typedef typename Graph::NodeNotifier Type;

    44   };

    45 

    46   template <typename _Graph>

    47   class ItemSetTraits<_Graph, typename _Graph::Node> {

    48   public:

    49     

    50     typedef _Graph Graph;

    51 

    52     typedef typename Graph::Node Item;

    53     typedef typename Graph::NodeIt ItemIt;

    54 

    55     typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier;

    56 

    57     template <typename _Value>

    58     class Map : public Graph::template NodeMap<_Value> {

    59     public:

    60       typedef typename Graph::template NodeMap<_Value> Parent; 

    61       typedef typename Graph::template NodeMap<_Value> Type; 

    62       typedef typename Parent::Value Value;

    63 

    64       Map(const Graph& _digraph) : Parent(_digraph) {}

    65       Map(const Graph& _digraph, const Value& _value) 

    66 	: Parent(_digraph, _value) {}

    67 

    68      };

    69 

    70   };

    71 

    72   template <typename Graph, typename Enable = void>

    73   struct ArcNotifierIndicator {

    74     typedef InvalidType Type;

    75   };

    76   template <typename Graph>

    77   struct ArcNotifierIndicator<

    78     Graph, 

    79     typename enable_if<typename Graph::ArcNotifier::Notifier, void>::type

    80   > { 

    81     typedef typename Graph::ArcNotifier Type;

    82   };

    83 

    84   template <typename _Graph>

    85   class ItemSetTraits<_Graph, typename _Graph::Arc> {

    86   public:

    87     

    88     typedef _Graph Graph;

    89 

    90     typedef typename Graph::Arc Item;

    91     typedef typename Graph::ArcIt ItemIt;

    92 

    93     typedef typename ArcNotifierIndicator<Graph>::Type ItemNotifier;

    94 

    95     template <typename _Value>

    96     class Map : public Graph::template ArcMap<_Value> {

    97     public:

    98       typedef typename Graph::template ArcMap<_Value> Parent; 

    99       typedef typename Graph::template ArcMap<_Value> Type; 

   100       typedef typename Parent::Value Value;

   101 

   102       Map(const Graph& _digraph) : Parent(_digraph) {}

   103       Map(const Graph& _digraph, const Value& _value) 

   104 	: Parent(_digraph, _value) {}

   105     };

   106 

   107   };

   108 

   109   template <typename Graph, typename Enable = void>

   110   struct EdgeNotifierIndicator {

   111     typedef InvalidType Type;

   112   };

   113   template <typename Graph>

   114   struct EdgeNotifierIndicator<

   115     Graph, 

   116     typename enable_if<typename Graph::EdgeNotifier::Notifier, void>::type

   117   > { 

   118     typedef typename Graph::EdgeNotifier Type;

   119   };

   120 

   121   template <typename _Graph>

   122   class ItemSetTraits<_Graph, typename _Graph::Edge> {

   123   public:

   124     

   125     typedef _Graph Graph;

   126 

   127     typedef typename Graph::Edge Item;

   128     typedef typename Graph::EdgeIt ItemIt;

   129 

   130     typedef typename EdgeNotifierIndicator<Graph>::Type ItemNotifier;

   131 

   132     template <typename _Value>

   133     class Map : public Graph::template EdgeMap<_Value> {

   134     public:

   135       typedef typename Graph::template EdgeMap<_Value> Parent; 

   136       typedef typename Graph::template EdgeMap<_Value> Type; 

   137       typedef typename Parent::Value Value;

   138 

   139       Map(const Graph& _digraph) : Parent(_digraph) {}

   140       Map(const Graph& _digraph, const Value& _value) 

   141 	: Parent(_digraph, _value) {}

   142     };

   143 

   144   };

   145 

   146   template <typename Map, typename Enable = void>

   147   struct MapTraits {

   148     typedef False ReferenceMapTag;

   149 

   150     typedef typename Map::Key Key;

   151     typedef typename Map::Value Value;

   152 

   153     typedef Value ConstReturnValue;

   154     typedef Value ReturnValue;

   155   };

   156 

   157   template <typename Map>

   158   struct MapTraits<

   159     Map, typename enable_if<typename Map::ReferenceMapTag, void>::type > 

   160   {

   161     typedef True ReferenceMapTag;

   162     

   163     typedef typename Map::Key Key;

   164     typedef typename Map::Value Value;

   165 

   166     typedef typename Map::ConstReference ConstReturnValue;

   167     typedef typename Map::Reference ReturnValue;

   168 

   169     typedef typename Map::ConstReference ConstReference; 

   170     typedef typename Map::Reference Reference;

   171  };

   172 

   173   template <typename MatrixMap, typename Enable = void>

   174   struct MatrixMapTraits {

   175     typedef False ReferenceMapTag;

   176 

   177     typedef typename MatrixMap::FirstKey FirstKey;

   178     typedef typename MatrixMap::SecondKey SecondKey;

   179     typedef typename MatrixMap::Value Value;

   180 

   181     typedef Value ConstReturnValue;

   182     typedef Value ReturnValue;

   183   };

   184 

   185   template <typename MatrixMap>

   186   struct MatrixMapTraits<

   187     MatrixMap, typename enable_if<typename MatrixMap::ReferenceMapTag, 

   188                                   void>::type > 

   189   {

   190     typedef True ReferenceMapTag;

   191     

   192     typedef typename MatrixMap::FirstKey FirstKey;

   193     typedef typename MatrixMap::SecondKey SecondKey;

   194     typedef typename MatrixMap::Value Value;

   195 

   196     typedef typename MatrixMap::ConstReference ConstReturnValue;

   197     typedef typename MatrixMap::Reference ReturnValue;

   198 

   199     typedef typename MatrixMap::ConstReference ConstReference; 

   200     typedef typename MatrixMap::Reference Reference;

   201  };

   202 

   203   // Indicators for the tags

   204 

   205   template <typename Graph, typename Enable = void>

   206   struct NodeNumTagIndicator {

   207     static const bool value = false;

   208   };

   209 

   210   template <typename Graph>

   211   struct NodeNumTagIndicator<

   212     Graph, 

   213     typename enable_if<typename Graph::NodeNumTag, void>::type

   214   > {

   215     static const bool value = true;

   216   };

   217 

   218   template <typename Graph, typename Enable = void>

   219   struct EdgeNumTagIndicator {

   220     static const bool value = false;

   221   };

   222 

   223   template <typename Graph>

   224   struct EdgeNumTagIndicator<

   225     Graph, 

   226     typename enable_if<typename Graph::EdgeNumTag, void>::type

   227   > {

   228     static const bool value = true;

   229   };

   230 

   231   template <typename Graph, typename Enable = void>

   232   struct FindEdgeTagIndicator {

   233     static const bool value = false;

   234   };

   235 

   236   template <typename Graph>

   237   struct FindEdgeTagIndicator<

   238     Graph, 

   239     typename enable_if<typename Graph::FindEdgeTag, void>::type

   240   > {

   241     static const bool value = true;

   242   };

   243 

   244   template <typename Graph, typename Enable = void>

   245   struct UndirectedTagIndicator {

   246     static const bool value = false;

   247   };

   248 

   249   template <typename Graph>

   250   struct UndirectedTagIndicator<

   251     Graph, 

   252     typename enable_if<typename Graph::UndirectedTag, void>::type

   253   > {

   254     static const bool value = true;

   255   };

   256 

   257   template <typename Graph, typename Enable = void>

   258   struct BuildTagIndicator {

   259     static const bool value = false;

   260   };

   261 

   262   template <typename Graph>

   263   struct BuildTagIndicator<

   264     Graph, 

   265     typename enable_if<typename Graph::BuildTag, void>::type

   266   > {

   267     static const bool value = true;

   268   };

   269 

   270 }

   271 

   272 #endif
lemon-main