lemon/hypercube_graph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 19 Feb 2010 14:08:32 +0100
changeset 844 a6eb9698c321
parent 787 c2230649a493
parent 786 e20173729589
permissions -rw-r--r--
Support tolerance technique for BellmanFord (#51)

A new operation traits class BellmanFordToleranceOperationTraits
is introduced, which uses the tolerance technique in its less()
function. This class can be used with the SetOperationTraits
named template parameter.
kpeter@364
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@364
     2
 *
kpeter@364
     3
 * This file is a part of LEMON, a generic C++ optimization library.
kpeter@364
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
kpeter@364
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@364
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@364
     8
 *
kpeter@364
     9
 * Permission to use, modify and distribute this software is granted
kpeter@364
    10
 * provided that this copyright notice appears in all copies. For
kpeter@364
    11
 * precise terms see the accompanying LICENSE file.
kpeter@364
    12
 *
kpeter@364
    13
 * This software is provided "AS IS" with no warranty of any kind,
kpeter@364
    14
 * express or implied, and with no claim as to its suitability for any
kpeter@364
    15
 * purpose.
kpeter@364
    16
 *
kpeter@364
    17
 */
kpeter@364
    18
kpeter@364
    19
#ifndef HYPERCUBE_GRAPH_H
kpeter@364
    20
#define HYPERCUBE_GRAPH_H
kpeter@364
    21
kpeter@364
    22
#include <vector>
kpeter@364
    23
#include <lemon/core.h>
kpeter@365
    24
#include <lemon/assert.h>
kpeter@364
    25
#include <lemon/bits/graph_extender.h>
kpeter@364
    26
kpeter@364
    27
///\ingroup graphs
kpeter@364
    28
///\file
kpeter@365
    29
///\brief HypercubeGraph class.
kpeter@364
    30
kpeter@364
    31
namespace lemon {
kpeter@364
    32
kpeter@365
    33
  class HypercubeGraphBase {
kpeter@364
    34
kpeter@364
    35
  public:
kpeter@364
    36
kpeter@365
    37
    typedef HypercubeGraphBase Graph;
kpeter@364
    38
kpeter@364
    39
    class Node;
kpeter@365
    40
    class Edge;
kpeter@364
    41
    class Arc;
kpeter@364
    42
kpeter@364
    43
  public:
kpeter@364
    44
kpeter@365
    45
    HypercubeGraphBase() {}
kpeter@364
    46
kpeter@364
    47
  protected:
kpeter@364
    48
kpeter@364
    49
    void construct(int dim) {
kpeter@365
    50
      LEMON_ASSERT(dim >= 1, "The number of dimensions must be at least 1.");
kpeter@364
    51
      _dim = dim;
kpeter@365
    52
      _node_num = 1 << dim;
alpar@372
    53
      _edge_num = dim * (1 << (dim-1));
kpeter@364
    54
    }
kpeter@364
    55
kpeter@364
    56
  public:
kpeter@364
    57
kpeter@364
    58
    typedef True NodeNumTag;
kpeter@365
    59
    typedef True EdgeNumTag;
kpeter@364
    60
    typedef True ArcNumTag;
kpeter@364
    61
kpeter@365
    62
    int nodeNum() const { return _node_num; }
kpeter@365
    63
    int edgeNum() const { return _edge_num; }
kpeter@365
    64
    int arcNum() const { return 2 * _edge_num; }
kpeter@364
    65
kpeter@365
    66
    int maxNodeId() const { return _node_num - 1; }
kpeter@365
    67
    int maxEdgeId() const { return _edge_num - 1; }
kpeter@365
    68
    int maxArcId() const { return 2 * _edge_num - 1; }
kpeter@364
    69
kpeter@365
    70
    static Node nodeFromId(int id) { return Node(id); }
kpeter@365
    71
    static Edge edgeFromId(int id) { return Edge(id); }
kpeter@365
    72
    static Arc arcFromId(int id) { return Arc(id); }
kpeter@365
    73
kpeter@365
    74
    static int id(Node node) { return node._id; }
kpeter@365
    75
    static int id(Edge edge) { return edge._id; }
kpeter@365
    76
    static int id(Arc arc) { return arc._id; }
kpeter@365
    77
kpeter@365
    78
    Node u(Edge edge) const {
alpar@372
    79
      int base = edge._id & ((1 << (_dim-1)) - 1);
alpar@372
    80
      int k = edge._id >> (_dim-1);
alpar@372
    81
      return ((base >> k) << (k+1)) | (base & ((1 << k) - 1));
kpeter@364
    82
    }
kpeter@364
    83
kpeter@365
    84
    Node v(Edge edge) const {
alpar@372
    85
      int base = edge._id & ((1 << (_dim-1)) - 1);
alpar@372
    86
      int k = edge._id >> (_dim-1);
alpar@372
    87
      return ((base >> k) << (k+1)) | (base & ((1 << k) - 1)) | (1 << k);
kpeter@364
    88
    }
kpeter@364
    89
kpeter@365
    90
    Node source(Arc arc) const {
kpeter@365
    91
      return (arc._id & 1) == 1 ? u(arc) : v(arc);
kpeter@365
    92
    }
kpeter@364
    93
kpeter@365
    94
    Node target(Arc arc) const {
kpeter@365
    95
      return (arc._id & 1) == 1 ? v(arc) : u(arc);
kpeter@365
    96
    }
kpeter@364
    97
kpeter@365
    98
    typedef True FindEdgeTag;
kpeter@365
    99
    typedef True FindArcTag;
kpeter@365
   100
kpeter@365
   101
    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
kpeter@365
   102
      if (prev != INVALID) return INVALID;
kpeter@365
   103
      int d = u._id ^ v._id;
kpeter@365
   104
      int k = 0;
kpeter@365
   105
      if (d == 0) return INVALID;
kpeter@365
   106
      for ( ; (d & 1) == 0; d >>= 1) ++k;
kpeter@365
   107
      if (d >> 1 != 0) return INVALID;
alpar@372
   108
      return (k << (_dim-1)) | ((u._id >> (k+1)) << k) |
alpar@372
   109
        (u._id & ((1 << k) - 1));
kpeter@365
   110
    }
kpeter@365
   111
kpeter@365
   112
    Arc findArc(Node u, Node v, Arc prev = INVALID) const {
kpeter@365
   113
      Edge edge = findEdge(u, v, prev);
kpeter@365
   114
      if (edge == INVALID) return INVALID;
alpar@372
   115
      int k = edge._id >> (_dim-1);
kpeter@365
   116
      return ((u._id >> k) & 1) == 1 ? edge._id << 1 : (edge._id << 1) | 1;
kpeter@365
   117
    }
kpeter@364
   118
kpeter@364
   119
    class Node {
kpeter@365
   120
      friend class HypercubeGraphBase;
kpeter@365
   121
kpeter@364
   122
    protected:
kpeter@365
   123
      int _id;
kpeter@365
   124
      Node(int id) : _id(id) {}
kpeter@364
   125
    public:
kpeter@364
   126
      Node() {}
kpeter@365
   127
      Node (Invalid) : _id(-1) {}
kpeter@365
   128
      bool operator==(const Node node) const {return _id == node._id;}
kpeter@365
   129
      bool operator!=(const Node node) const {return _id != node._id;}
kpeter@365
   130
      bool operator<(const Node node) const {return _id < node._id;}
kpeter@365
   131
    };
kpeter@365
   132
kpeter@365
   133
    class Edge {
kpeter@365
   134
      friend class HypercubeGraphBase;
kpeter@365
   135
      friend class Arc;
kpeter@365
   136
kpeter@365
   137
    protected:
kpeter@365
   138
      int _id;
kpeter@365
   139
kpeter@365
   140
      Edge(int id) : _id(id) {}
kpeter@365
   141
kpeter@365
   142
    public:
kpeter@365
   143
      Edge() {}
kpeter@365
   144
      Edge (Invalid) : _id(-1) {}
kpeter@365
   145
      bool operator==(const Edge edge) const {return _id == edge._id;}
kpeter@365
   146
      bool operator!=(const Edge edge) const {return _id != edge._id;}
kpeter@365
   147
      bool operator<(const Edge edge) const {return _id < edge._id;}
kpeter@364
   148
    };
kpeter@364
   149
kpeter@364
   150
    class Arc {
kpeter@365
   151
      friend class HypercubeGraphBase;
kpeter@365
   152
kpeter@364
   153
    protected:
kpeter@365
   154
      int _id;
kpeter@365
   155
kpeter@365
   156
      Arc(int id) : _id(id) {}
kpeter@365
   157
kpeter@364
   158
    public:
kpeter@365
   159
      Arc() {}
kpeter@365
   160
      Arc (Invalid) : _id(-1) {}
kpeter@365
   161
      operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
kpeter@365
   162
      bool operator==(const Arc arc) const {return _id == arc._id;}
kpeter@365
   163
      bool operator!=(const Arc arc) const {return _id != arc._id;}
kpeter@365
   164
      bool operator<(const Arc arc) const {return _id < arc._id;}
kpeter@364
   165
    };
kpeter@364
   166
kpeter@364
   167
    void first(Node& node) const {
kpeter@365
   168
      node._id = _node_num - 1;
kpeter@364
   169
    }
kpeter@364
   170
kpeter@364
   171
    static void next(Node& node) {
kpeter@365
   172
      --node._id;
kpeter@365
   173
    }
kpeter@365
   174
kpeter@365
   175
    void first(Edge& edge) const {
kpeter@365
   176
      edge._id = _edge_num - 1;
kpeter@365
   177
    }
kpeter@365
   178
kpeter@365
   179
    static void next(Edge& edge) {
kpeter@365
   180
      --edge._id;
kpeter@364
   181
    }
kpeter@364
   182
kpeter@364
   183
    void first(Arc& arc) const {
kpeter@365
   184
      arc._id = 2 * _edge_num - 1;
kpeter@364
   185
    }
kpeter@364
   186
kpeter@364
   187
    static void next(Arc& arc) {
kpeter@365
   188
      --arc._id;
kpeter@365
   189
    }
kpeter@365
   190
kpeter@365
   191
    void firstInc(Edge& edge, bool& dir, const Node& node) const {
kpeter@365
   192
      edge._id = node._id >> 1;
kpeter@365
   193
      dir = (node._id & 1) == 0;
kpeter@365
   194
    }
kpeter@365
   195
kpeter@365
   196
    void nextInc(Edge& edge, bool& dir) const {
kpeter@365
   197
      Node n = dir ? u(edge) : v(edge);
alpar@372
   198
      int k = (edge._id >> (_dim-1)) + 1;
kpeter@365
   199
      if (k < _dim) {
alpar@372
   200
        edge._id = (k << (_dim-1)) |
alpar@372
   201
          ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
kpeter@365
   202
        dir = ((n._id >> k) & 1) == 0;
kpeter@365
   203
      } else {
kpeter@365
   204
        edge._id = -1;
kpeter@365
   205
        dir = true;
kpeter@365
   206
      }
kpeter@364
   207
    }
kpeter@364
   208
kpeter@364
   209
    void firstOut(Arc& arc, const Node& node) const {
kpeter@365
   210
      arc._id = ((node._id >> 1) << 1) | (~node._id & 1);
kpeter@364
   211
    }
kpeter@364
   212
kpeter@364
   213
    void nextOut(Arc& arc) const {
kpeter@365
   214
      Node n = (arc._id & 1) == 1 ? u(arc) : v(arc);
kpeter@365
   215
      int k = (arc._id >> _dim) + 1;
kpeter@365
   216
      if (k < _dim) {
alpar@372
   217
        arc._id = (k << (_dim-1)) |
alpar@372
   218
          ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
kpeter@365
   219
        arc._id = (arc._id << 1) | (~(n._id >> k) & 1);
kpeter@365
   220
      } else {
kpeter@365
   221
        arc._id = -1;
kpeter@365
   222
      }
kpeter@364
   223
    }
kpeter@364
   224
kpeter@364
   225
    void firstIn(Arc& arc, const Node& node) const {
kpeter@365
   226
      arc._id = ((node._id >> 1) << 1) | (node._id & 1);
kpeter@364
   227
    }
kpeter@364
   228
kpeter@364
   229
    void nextIn(Arc& arc) const {
kpeter@365
   230
      Node n = (arc._id & 1) == 1 ? v(arc) : u(arc);
kpeter@365
   231
      int k = (arc._id >> _dim) + 1;
kpeter@365
   232
      if (k < _dim) {
alpar@372
   233
        arc._id = (k << (_dim-1)) |
alpar@372
   234
          ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
kpeter@365
   235
        arc._id = (arc._id << 1) | ((n._id >> k) & 1);
kpeter@364
   236
      } else {
kpeter@365
   237
        arc._id = -1;
kpeter@364
   238
      }
kpeter@364
   239
    }
kpeter@364
   240
kpeter@365
   241
    static bool direction(Arc arc) {
kpeter@365
   242
      return (arc._id & 1) == 1;
kpeter@365
   243
    }
kpeter@365
   244
kpeter@365
   245
    static Arc direct(Edge edge, bool dir) {
kpeter@365
   246
      return Arc((edge._id << 1) | (dir ? 1 : 0));
kpeter@365
   247
    }
kpeter@365
   248
kpeter@364
   249
    int dimension() const {
kpeter@364
   250
      return _dim;
kpeter@364
   251
    }
kpeter@364
   252
kpeter@364
   253
    bool projection(Node node, int n) const {
kpeter@365
   254
      return static_cast<bool>(node._id & (1 << n));
kpeter@365
   255
    }
kpeter@365
   256
kpeter@365
   257
    int dimension(Edge edge) const {
alpar@372
   258
      return edge._id >> (_dim-1);
kpeter@364
   259
    }
kpeter@364
   260
kpeter@364
   261
    int dimension(Arc arc) const {
kpeter@365
   262
      return arc._id >> _dim;
kpeter@364
   263
    }
kpeter@364
   264
kpeter@778
   265
    static int index(Node node) {
kpeter@365
   266
      return node._id;
kpeter@364
   267
    }
kpeter@364
   268
kpeter@364
   269
    Node operator()(int ix) const {
kpeter@364
   270
      return Node(ix);
kpeter@364
   271
    }
kpeter@364
   272
kpeter@364
   273
  private:
kpeter@365
   274
    int _dim;
kpeter@365
   275
    int _node_num, _edge_num;
kpeter@364
   276
  };
kpeter@364
   277
kpeter@364
   278
kpeter@365
   279
  typedef GraphExtender<HypercubeGraphBase> ExtendedHypercubeGraphBase;
kpeter@364
   280
kpeter@365
   281
  /// \ingroup graphs
kpeter@364
   282
  ///
kpeter@365
   283
  /// \brief Hypercube graph class
kpeter@364
   284
  ///
kpeter@735
   285
  /// HypercubeGraph implements a special graph type. The nodes of the
kpeter@735
   286
  /// graph are indexed with integers having at most \c dim binary digits.
kpeter@365
   287
  /// Two nodes are connected in the graph if and only if their indices
kpeter@365
   288
  /// differ only on one position in the binary form.
kpeter@735
   289
  /// This class is completely static and it needs constant memory space.
kpeter@786
   290
  /// Thus you can neither add nor delete nodes or edges, however,
kpeter@737
   291
  /// the structure can be resized using resize().
kpeter@735
   292
  ///
kpeter@735
   293
  /// This type fully conforms to the \ref concepts::Graph "Graph concept".
kpeter@735
   294
  /// Most of its member functions and nested classes are documented
kpeter@735
   295
  /// only in the concept class.
kpeter@364
   296
  ///
kpeter@787
   297
  /// This class provides constant time counting for nodes, edges and arcs.
kpeter@787
   298
  ///
kpeter@365
   299
  /// \note The type of the indices is chosen to \c int for efficiency
kpeter@365
   300
  /// reasons. Thus the maximum dimension of this implementation is 26
kpeter@365
   301
  /// (assuming that the size of \c int is 32 bit).
kpeter@365
   302
  class HypercubeGraph : public ExtendedHypercubeGraphBase {
kpeter@617
   303
    typedef ExtendedHypercubeGraphBase Parent;
kpeter@617
   304
kpeter@364
   305
  public:
kpeter@364
   306
kpeter@365
   307
    /// \brief Constructs a hypercube graph with \c dim dimensions.
kpeter@364
   308
    ///
kpeter@365
   309
    /// Constructs a hypercube graph with \c dim dimensions.
kpeter@365
   310
    HypercubeGraph(int dim) { construct(dim); }
kpeter@364
   311
kpeter@737
   312
    /// \brief Resizes the graph
kpeter@737
   313
    ///
kpeter@737
   314
    /// This function resizes the graph. It fully destroys and
kpeter@737
   315
    /// rebuilds the structure, therefore the maps of the graph will be
kpeter@737
   316
    /// reallocated automatically and the previous values will be lost.
kpeter@737
   317
    void resize(int dim) {
kpeter@737
   318
      Parent::notifier(Arc()).clear();
kpeter@737
   319
      Parent::notifier(Edge()).clear();
kpeter@737
   320
      Parent::notifier(Node()).clear();
kpeter@737
   321
      construct(dim);
kpeter@737
   322
      Parent::notifier(Node()).build();
kpeter@737
   323
      Parent::notifier(Edge()).build();
kpeter@737
   324
      Parent::notifier(Arc()).build();
kpeter@737
   325
    }
kpeter@737
   326
kpeter@365
   327
    /// \brief The number of dimensions.
kpeter@364
   328
    ///
kpeter@365
   329
    /// Gives back the number of dimensions.
kpeter@364
   330
    int dimension() const {
kpeter@364
   331
      return Parent::dimension();
kpeter@364
   332
    }
kpeter@364
   333
kpeter@365
   334
    /// \brief Returns \c true if the n'th bit of the node is one.
kpeter@364
   335
    ///
kpeter@365
   336
    /// Returns \c true if the n'th bit of the node is one.
kpeter@364
   337
    bool projection(Node node, int n) const {
kpeter@364
   338
      return Parent::projection(node, n);
kpeter@364
   339
    }
kpeter@364
   340
kpeter@365
   341
    /// \brief The dimension id of an edge.
kpeter@364
   342
    ///
kpeter@365
   343
    /// Gives back the dimension id of the given edge.
kpeter@735
   344
    /// It is in the range <tt>[0..dim-1]</tt>.
kpeter@365
   345
    int dimension(Edge edge) const {
kpeter@365
   346
      return Parent::dimension(edge);
kpeter@365
   347
    }
kpeter@365
   348
kpeter@365
   349
    /// \brief The dimension id of an arc.
kpeter@365
   350
    ///
kpeter@365
   351
    /// Gives back the dimension id of the given arc.
kpeter@735
   352
    /// It is in the range <tt>[0..dim-1]</tt>.
kpeter@364
   353
    int dimension(Arc arc) const {
kpeter@364
   354
      return Parent::dimension(arc);
kpeter@364
   355
    }
kpeter@364
   356
kpeter@365
   357
    /// \brief The index of a node.
kpeter@364
   358
    ///
kpeter@365
   359
    /// Gives back the index of the given node.
kpeter@365
   360
    /// The lower bits of the integer describes the node.
kpeter@778
   361
    static int index(Node node) {
kpeter@364
   362
      return Parent::index(node);
kpeter@364
   363
    }
kpeter@364
   364
kpeter@365
   365
    /// \brief Gives back a node by its index.
kpeter@364
   366
    ///
kpeter@365
   367
    /// Gives back a node by its index.
kpeter@364
   368
    Node operator()(int ix) const {
kpeter@364
   369
      return Parent::operator()(ix);
kpeter@364
   370
    }
kpeter@364
   371
kpeter@364
   372
    /// \brief Number of nodes.
kpeter@364
   373
    int nodeNum() const { return Parent::nodeNum(); }
kpeter@365
   374
    /// \brief Number of edges.
kpeter@365
   375
    int edgeNum() const { return Parent::edgeNum(); }
kpeter@364
   376
    /// \brief Number of arcs.
kpeter@364
   377
    int arcNum() const { return Parent::arcNum(); }
kpeter@364
   378
kpeter@364
   379
    /// \brief Linear combination map.
kpeter@364
   380
    ///
kpeter@365
   381
    /// This map makes possible to give back a linear combination
kpeter@365
   382
    /// for each node. It works like the \c std::accumulate function,
kpeter@365
   383
    /// so it accumulates the \c bf binary function with the \c fv first
kpeter@365
   384
    /// value. The map accumulates only on that positions (dimensions)
kpeter@365
   385
    /// where the index of the node is one. The values that have to be
kpeter@365
   386
    /// accumulated should be given by the \c begin and \c end iterators
kpeter@365
   387
    /// and the length of this range should be equal to the dimension
kpeter@365
   388
    /// number of the graph.
kpeter@364
   389
    ///
kpeter@364
   390
    ///\code
kpeter@364
   391
    /// const int DIM = 3;
kpeter@365
   392
    /// HypercubeGraph graph(DIM);
kpeter@364
   393
    /// dim2::Point<double> base[DIM];
kpeter@364
   394
    /// for (int k = 0; k < DIM; ++k) {
kpeter@364
   395
    ///   base[k].x = rnd();
kpeter@364
   396
    ///   base[k].y = rnd();
kpeter@364
   397
    /// }
kpeter@365
   398
    /// HypercubeGraph::HyperMap<dim2::Point<double> >
kpeter@365
   399
    ///   pos(graph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
kpeter@364
   400
    ///\endcode
kpeter@364
   401
    ///
kpeter@365
   402
    /// \see HypercubeGraph
kpeter@364
   403
    template <typename T, typename BF = std::plus<T> >
kpeter@364
   404
    class HyperMap {
kpeter@364
   405
    public:
kpeter@364
   406
kpeter@365
   407
      /// \brief The key type of the map
kpeter@364
   408
      typedef Node Key;
kpeter@365
   409
      /// \brief The value type of the map
kpeter@364
   410
      typedef T Value;
kpeter@364
   411
kpeter@364
   412
      /// \brief Constructor for HyperMap.
kpeter@364
   413
      ///
kpeter@365
   414
      /// Construct a HyperMap for the given graph. The values that have
kpeter@365
   415
      /// to be accumulated should be given by the \c begin and \c end
kpeter@365
   416
      /// iterators and the length of this range should be equal to the
kpeter@365
   417
      /// dimension number of the graph.
kpeter@364
   418
      ///
kpeter@365
   419
      /// This map accumulates the \c bf binary function with the \c fv
kpeter@365
   420
      /// first value on that positions (dimensions) where the index of
kpeter@365
   421
      /// the node is one.
kpeter@364
   422
      template <typename It>
kpeter@365
   423
      HyperMap(const Graph& graph, It begin, It end,
kpeter@365
   424
               T fv = 0, const BF& bf = BF())
kpeter@365
   425
        : _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf)
kpeter@364
   426
      {
kpeter@365
   427
        LEMON_ASSERT(_values.size() == graph.dimension(),
kpeter@365
   428
                     "Wrong size of range");
kpeter@364
   429
      }
kpeter@364
   430
kpeter@365
   431
      /// \brief The partial accumulated value.
kpeter@364
   432
      ///
kpeter@364
   433
      /// Gives back the partial accumulated value.
kpeter@365
   434
      Value operator[](const Key& k) const {
kpeter@364
   435
        Value val = _first_value;
kpeter@364
   436
        int id = _graph.index(k);
kpeter@364
   437
        int n = 0;
kpeter@364
   438
        while (id != 0) {
kpeter@364
   439
          if (id & 1) {
kpeter@364
   440
            val = _bin_func(val, _values[n]);
kpeter@364
   441
          }
kpeter@364
   442
          id >>= 1;
kpeter@364
   443
          ++n;
kpeter@364
   444
        }
kpeter@364
   445
        return val;
kpeter@364
   446
      }
kpeter@364
   447
kpeter@364
   448
    private:
kpeter@365
   449
      const Graph& _graph;
kpeter@364
   450
      std::vector<T> _values;
kpeter@364
   451
      T _first_value;
kpeter@364
   452
      BF _bin_func;
kpeter@364
   453
    };
kpeter@364
   454
kpeter@364
   455
  };
kpeter@364
   456
kpeter@364
   457
}
kpeter@364
   458
kpeter@364
   459
#endif