lemon/pairing_heap.h
author Balazs Dezso <deba@inf.elte.hu>
Thu, 04 Mar 2010 15:20:59 +0100
changeset 951 41d7ac528c3a
parent 750 bb3392fe91f2
permissions -rw-r--r--
Uniforming primal scale to 2 (#314)
kpeter@750
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@748
     2
 *
kpeter@750
     3
 * This file is a part of LEMON, a generic C++ optimization library.
kpeter@748
     4
 *
kpeter@750
     5
 * Copyright (C) 2003-2009
kpeter@748
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@748
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@748
     8
 *
kpeter@748
     9
 * Permission to use, modify and distribute this software is granted
kpeter@748
    10
 * provided that this copyright notice appears in all copies. For
kpeter@748
    11
 * precise terms see the accompanying LICENSE file.
kpeter@748
    12
 *
kpeter@748
    13
 * This software is provided "AS IS" with no warranty of any kind,
kpeter@748
    14
 * express or implied, and with no claim as to its suitability for any
kpeter@748
    15
 * purpose.
kpeter@748
    16
 *
kpeter@748
    17
 */
kpeter@748
    18
kpeter@748
    19
#ifndef LEMON_PAIRING_HEAP_H
kpeter@748
    20
#define LEMON_PAIRING_HEAP_H
kpeter@748
    21
kpeter@748
    22
///\file
kpeter@750
    23
///\ingroup heaps
kpeter@750
    24
///\brief Pairing heap implementation.
kpeter@748
    25
kpeter@748
    26
#include <vector>
kpeter@750
    27
#include <utility>
kpeter@748
    28
#include <functional>
kpeter@748
    29
#include <lemon/math.h>
kpeter@748
    30
kpeter@748
    31
namespace lemon {
kpeter@748
    32
kpeter@750
    33
  /// \ingroup heaps
kpeter@748
    34
  ///
kpeter@748
    35
  ///\brief Pairing Heap.
kpeter@748
    36
  ///
kpeter@750
    37
  /// This class implements the \e pairing \e heap data structure.
kpeter@750
    38
  /// It fully conforms to the \ref concepts::Heap "heap concept".
kpeter@748
    39
  ///
kpeter@750
    40
  /// The methods \ref increase() and \ref erase() are not efficient
kpeter@750
    41
  /// in a pairing heap. In case of many calls of these operations,
kpeter@750
    42
  /// it is better to use other heap structure, e.g. \ref BinHeap
kpeter@750
    43
  /// "binary heap".
kpeter@748
    44
  ///
kpeter@750
    45
  /// \tparam PR Type of the priorities of the items.
kpeter@750
    46
  /// \tparam IM A read-writable item map with \c int values, used
kpeter@750
    47
  /// internally to handle the cross references.
kpeter@750
    48
  /// \tparam CMP A functor class for comparing the priorities.
kpeter@750
    49
  /// The default is \c std::less<PR>.
kpeter@748
    50
#ifdef DOXYGEN
kpeter@750
    51
  template <typename PR, typename IM, typename CMP>
kpeter@748
    52
#else
kpeter@750
    53
  template <typename PR, typename IM, typename CMP = std::less<PR> >
kpeter@748
    54
#endif
kpeter@748
    55
  class PairingHeap {
kpeter@748
    56
  public:
kpeter@750
    57
    /// Type of the item-int map.
kpeter@750
    58
    typedef IM ItemIntMap;
kpeter@750
    59
    /// Type of the priorities.
kpeter@750
    60
    typedef PR Prio;
kpeter@750
    61
    /// Type of the items stored in the heap.
kpeter@748
    62
    typedef typename ItemIntMap::Key Item;
kpeter@750
    63
    /// Functor type for comparing the priorities.
kpeter@750
    64
    typedef CMP Compare;
kpeter@750
    65
kpeter@750
    66
    /// \brief Type to represent the states of the items.
kpeter@750
    67
    ///
kpeter@750
    68
    /// Each item has a state associated to it. It can be "in heap",
kpeter@750
    69
    /// "pre-heap" or "post-heap". The latter two are indifferent from the
kpeter@750
    70
    /// heap's point of view, but may be useful to the user.
kpeter@750
    71
    ///
kpeter@750
    72
    /// The item-int map must be initialized in such way that it assigns
kpeter@750
    73
    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
kpeter@750
    74
    enum State {
kpeter@750
    75
      IN_HEAP = 0,    ///< = 0.
kpeter@750
    76
      PRE_HEAP = -1,  ///< = -1.
kpeter@750
    77
      POST_HEAP = -2  ///< = -2.
kpeter@750
    78
    };
kpeter@748
    79
kpeter@748
    80
  private:
kpeter@748
    81
    class store;
kpeter@748
    82
kpeter@750
    83
    std::vector<store> _data;
kpeter@750
    84
    int _min;
kpeter@750
    85
    ItemIntMap &_iim;
kpeter@750
    86
    Compare _comp;
kpeter@750
    87
    int _num_items;
kpeter@748
    88
kpeter@748
    89
  public:
kpeter@750
    90
    /// \brief Constructor.
kpeter@750
    91
    ///
kpeter@750
    92
    /// Constructor.
kpeter@750
    93
    /// \param map A map that assigns \c int values to the items.
kpeter@750
    94
    /// It is used internally to handle the cross references.
kpeter@750
    95
    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
kpeter@750
    96
    explicit PairingHeap(ItemIntMap &map)
kpeter@750
    97
      : _min(0), _iim(map), _num_items(0) {}
kpeter@748
    98
kpeter@750
    99
    /// \brief Constructor.
kpeter@748
   100
    ///
kpeter@750
   101
    /// Constructor.
kpeter@750
   102
    /// \param map A map that assigns \c int values to the items.
kpeter@750
   103
    /// It is used internally to handle the cross references.
kpeter@750
   104
    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
kpeter@750
   105
    /// \param comp The function object used for comparing the priorities.
kpeter@750
   106
    PairingHeap(ItemIntMap &map, const Compare &comp)
kpeter@750
   107
      : _min(0), _iim(map), _comp(comp), _num_items(0) {}
kpeter@748
   108
kpeter@748
   109
    /// \brief The number of items stored in the heap.
kpeter@748
   110
    ///
kpeter@750
   111
    /// This function returns the number of items stored in the heap.
kpeter@750
   112
    int size() const { return _num_items; }
kpeter@748
   113
kpeter@750
   114
    /// \brief Check if the heap is empty.
kpeter@748
   115
    ///
kpeter@750
   116
    /// This function returns \c true if the heap is empty.
kpeter@750
   117
    bool empty() const { return _num_items==0; }
kpeter@748
   118
kpeter@750
   119
    /// \brief Make the heap empty.
kpeter@748
   120
    ///
kpeter@750
   121
    /// This functon makes the heap empty.
kpeter@750
   122
    /// It does not change the cross reference map. If you want to reuse
kpeter@750
   123
    /// a heap that is not surely empty, you should first clear it and
kpeter@750
   124
    /// then you should set the cross reference map to \c PRE_HEAP
kpeter@750
   125
    /// for each item.
kpeter@748
   126
    void clear() {
kpeter@750
   127
      _data.clear();
kpeter@750
   128
      _min = 0;
kpeter@750
   129
      _num_items = 0;
kpeter@748
   130
    }
kpeter@748
   131
kpeter@750
   132
    /// \brief Set the priority of an item or insert it, if it is
kpeter@750
   133
    /// not stored in the heap.
kpeter@748
   134
    ///
kpeter@750
   135
    /// This method sets the priority of the given item if it is
kpeter@750
   136
    /// already stored in the heap. Otherwise it inserts the given
kpeter@750
   137
    /// item into the heap with the given priority.
kpeter@750
   138
    /// \param item The item.
kpeter@750
   139
    /// \param value The priority.
kpeter@748
   140
    void set (const Item& item, const Prio& value) {
kpeter@750
   141
      int i=_iim[item];
kpeter@750
   142
      if ( i>=0 && _data[i].in ) {
kpeter@750
   143
        if ( _comp(value, _data[i].prio) ) decrease(item, value);
kpeter@750
   144
        if ( _comp(_data[i].prio, value) ) increase(item, value);
kpeter@748
   145
      } else push(item, value);
kpeter@748
   146
    }
kpeter@748
   147
kpeter@750
   148
    /// \brief Insert an item into the heap with the given priority.
kpeter@748
   149
    ///
kpeter@750
   150
    /// This function inserts the given item into the heap with the
kpeter@750
   151
    /// given priority.
kpeter@750
   152
    /// \param item The item to insert.
kpeter@750
   153
    /// \param value The priority of the item.
kpeter@750
   154
    /// \pre \e item must not be stored in the heap.
kpeter@748
   155
    void push (const Item& item, const Prio& value) {
kpeter@750
   156
      int i=_iim[item];
kpeter@748
   157
      if( i<0 ) {
kpeter@750
   158
        int s=_data.size();
kpeter@750
   159
        _iim.set(item, s);
kpeter@748
   160
        store st;
kpeter@748
   161
        st.name=item;
kpeter@750
   162
        _data.push_back(st);
kpeter@748
   163
        i=s;
kpeter@748
   164
      } else {
kpeter@750
   165
        _data[i].parent=_data[i].child=-1;
kpeter@750
   166
        _data[i].left_child=false;
kpeter@750
   167
        _data[i].degree=0;
kpeter@750
   168
        _data[i].in=true;
kpeter@748
   169
      }
kpeter@748
   170
kpeter@750
   171
      _data[i].prio=value;
kpeter@748
   172
kpeter@750
   173
      if ( _num_items!=0 ) {
kpeter@750
   174
        if ( _comp( value, _data[_min].prio) ) {
kpeter@750
   175
          fuse(i,_min);
kpeter@750
   176
          _min=i;
kpeter@748
   177
        }
kpeter@750
   178
        else fuse(_min,i);
kpeter@748
   179
      }
kpeter@750
   180
      else _min=i;
kpeter@748
   181
kpeter@750
   182
      ++_num_items;
kpeter@748
   183
    }
kpeter@748
   184
kpeter@750
   185
    /// \brief Return the item having minimum priority.
kpeter@748
   186
    ///
kpeter@750
   187
    /// This function returns the item having minimum priority.
kpeter@750
   188
    /// \pre The heap must be non-empty.
kpeter@750
   189
    Item top() const { return _data[_min].name; }
kpeter@748
   190
kpeter@750
   191
    /// \brief The minimum priority.
kpeter@748
   192
    ///
kpeter@750
   193
    /// This function returns the minimum priority.
kpeter@750
   194
    /// \pre The heap must be non-empty.
kpeter@750
   195
    const Prio& prio() const { return _data[_min].prio; }
kpeter@748
   196
kpeter@750
   197
    /// \brief The priority of the given item.
kpeter@748
   198
    ///
kpeter@750
   199
    /// This function returns the priority of the given item.
kpeter@750
   200
    /// \param item The item.
kpeter@750
   201
    /// \pre \e item must be in the heap.
kpeter@748
   202
    const Prio& operator[](const Item& item) const {
kpeter@750
   203
      return _data[_iim[item]].prio;
kpeter@748
   204
    }
kpeter@748
   205
kpeter@750
   206
    /// \brief Remove the item having minimum priority.
kpeter@748
   207
    ///
kpeter@750
   208
    /// This function removes the item having minimum priority.
kpeter@748
   209
    /// \pre The heap must be non-empty.
kpeter@748
   210
    void pop() {
kpeter@752
   211
      std::vector<int> trees;
kpeter@752
   212
      int i=0, child_right = 0;
kpeter@750
   213
      _data[_min].in=false;
kpeter@748
   214
kpeter@750
   215
      if( -1!=_data[_min].child ) {
kpeter@750
   216
        i=_data[_min].child;
kpeter@752
   217
        trees.push_back(i);
kpeter@750
   218
        _data[i].parent = -1;
kpeter@750
   219
        _data[_min].child = -1;
kpeter@748
   220
kpeter@748
   221
        int ch=-1;
kpeter@750
   222
        while( _data[i].child!=-1 ) {
kpeter@750
   223
          ch=_data[i].child;
kpeter@750
   224
          if( _data[ch].left_child && i==_data[ch].parent ) {
kpeter@752
   225
            break;
kpeter@748
   226
          } else {
kpeter@750
   227
            if( _data[ch].left_child ) {
kpeter@750
   228
              child_right=_data[ch].parent;
kpeter@750
   229
              _data[ch].parent = i;
kpeter@750
   230
              --_data[i].degree;
kpeter@748
   231
            }
kpeter@748
   232
            else {
kpeter@748
   233
              child_right=ch;
kpeter@750
   234
              _data[i].child=-1;
kpeter@750
   235
              _data[i].degree=0;
kpeter@748
   236
            }
kpeter@750
   237
            _data[child_right].parent = -1;
kpeter@752
   238
            trees.push_back(child_right);
kpeter@748
   239
            i = child_right;
kpeter@748
   240
          }
kpeter@748
   241
        }
kpeter@748
   242
kpeter@752
   243
        int num_child = trees.size();
kpeter@748
   244
        int other;
kpeter@748
   245
        for( i=0; i<num_child-1; i+=2 ) {
kpeter@752
   246
          if ( !_comp(_data[trees[i]].prio, _data[trees[i+1]].prio) ) {
kpeter@752
   247
            other=trees[i];
kpeter@752
   248
            trees[i]=trees[i+1];
kpeter@752
   249
            trees[i+1]=other;
kpeter@748
   250
          }
kpeter@752
   251
          fuse( trees[i], trees[i+1] );
kpeter@748
   252
        }
kpeter@748
   253
kpeter@748
   254
        i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
kpeter@748
   255
        while(i>=2) {
kpeter@752
   256
          if ( _comp(_data[trees[i]].prio, _data[trees[i-2]].prio) ) {
kpeter@752
   257
            other=trees[i];
kpeter@752
   258
            trees[i]=trees[i-2];
kpeter@752
   259
            trees[i-2]=other;
kpeter@748
   260
          }
kpeter@752
   261
          fuse( trees[i-2], trees[i] );
kpeter@748
   262
          i-=2;
kpeter@748
   263
        }
kpeter@752
   264
        _min = trees[0];
kpeter@748
   265
      }
kpeter@752
   266
      else {
kpeter@750
   267
        _min = _data[_min].child;
kpeter@748
   268
      }
kpeter@748
   269
kpeter@750
   270
      if (_min >= 0) _data[_min].left_child = false;
kpeter@750
   271
      --_num_items;
kpeter@748
   272
    }
kpeter@748
   273
kpeter@750
   274
    /// \brief Remove the given item from the heap.
kpeter@748
   275
    ///
kpeter@750
   276
    /// This function removes the given item from the heap if it is
kpeter@750
   277
    /// already stored.
kpeter@750
   278
    /// \param item The item to delete.
kpeter@750
   279
    /// \pre \e item must be in the heap.
kpeter@748
   280
    void erase (const Item& item) {
kpeter@750
   281
      int i=_iim[item];
kpeter@750
   282
      if ( i>=0 && _data[i].in ) {
kpeter@750
   283
        decrease( item, _data[_min].prio-1 );
kpeter@748
   284
        pop();
kpeter@748
   285
      }
kpeter@748
   286
    }
kpeter@748
   287
kpeter@750
   288
    /// \brief Decrease the priority of an item to the given value.
kpeter@748
   289
    ///
kpeter@750
   290
    /// This function decreases the priority of an item to the given value.
kpeter@750
   291
    /// \param item The item.
kpeter@750
   292
    /// \param value The priority.
kpeter@750
   293
    /// \pre \e item must be stored in the heap with priority at least \e value.
kpeter@748
   294
    void decrease (Item item, const Prio& value) {
kpeter@750
   295
      int i=_iim[item];
kpeter@750
   296
      _data[i].prio=value;
kpeter@750
   297
      int p=_data[i].parent;
kpeter@748
   298
kpeter@750
   299
      if( _data[i].left_child && i!=_data[p].child ) {
kpeter@750
   300
        p=_data[p].parent;
kpeter@748
   301
      }
kpeter@748
   302
kpeter@750
   303
      if ( p!=-1 && _comp(value,_data[p].prio) ) {
kpeter@748
   304
        cut(i,p);
kpeter@750
   305
        if ( _comp(_data[_min].prio,value) ) {
kpeter@750
   306
          fuse(_min,i);
kpeter@748
   307
        } else {
kpeter@750
   308
          fuse(i,_min);
kpeter@750
   309
          _min=i;
kpeter@748
   310
        }
kpeter@748
   311
      }
kpeter@748
   312
    }
kpeter@748
   313
kpeter@750
   314
    /// \brief Increase the priority of an item to the given value.
kpeter@748
   315
    ///
kpeter@750
   316
    /// This function increases the priority of an item to the given value.
kpeter@750
   317
    /// \param item The item.
kpeter@750
   318
    /// \param value The priority.
kpeter@750
   319
    /// \pre \e item must be stored in the heap with priority at most \e value.
kpeter@748
   320
    void increase (Item item, const Prio& value) {
kpeter@748
   321
      erase(item);
kpeter@748
   322
      push(item,value);
kpeter@748
   323
    }
kpeter@748
   324
kpeter@750
   325
    /// \brief Return the state of an item.
kpeter@748
   326
    ///
kpeter@750
   327
    /// This method returns \c PRE_HEAP if the given item has never
kpeter@750
   328
    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
kpeter@750
   329
    /// and \c POST_HEAP otherwise.
kpeter@750
   330
    /// In the latter case it is possible that the item will get back
kpeter@750
   331
    /// to the heap again.
kpeter@750
   332
    /// \param item The item.
kpeter@748
   333
    State state(const Item &item) const {
kpeter@750
   334
      int i=_iim[item];
kpeter@748
   335
      if( i>=0 ) {
kpeter@750
   336
        if( _data[i].in ) i=0;
kpeter@748
   337
        else i=-2;
kpeter@748
   338
      }
kpeter@748
   339
      return State(i);
kpeter@748
   340
    }
kpeter@748
   341
kpeter@750
   342
    /// \brief Set the state of an item in the heap.
kpeter@748
   343
    ///
kpeter@750
   344
    /// This function sets the state of the given item in the heap.
kpeter@750
   345
    /// It can be used to manually clear the heap when it is important
kpeter@750
   346
    /// to achive better time complexity.
kpeter@748
   347
    /// \param i The item.
kpeter@748
   348
    /// \param st The state. It should not be \c IN_HEAP.
kpeter@748
   349
    void state(const Item& i, State st) {
kpeter@748
   350
      switch (st) {
kpeter@748
   351
      case POST_HEAP:
kpeter@748
   352
      case PRE_HEAP:
kpeter@748
   353
        if (state(i) == IN_HEAP) erase(i);
kpeter@750
   354
        _iim[i]=st;
kpeter@748
   355
        break;
kpeter@748
   356
      case IN_HEAP:
kpeter@748
   357
        break;
kpeter@748
   358
      }
kpeter@748
   359
    }
kpeter@748
   360
kpeter@748
   361
  private:
kpeter@748
   362
kpeter@748
   363
    void cut(int a, int b) {
kpeter@748
   364
      int child_a;
kpeter@750
   365
      switch (_data[a].degree) {
kpeter@748
   366
        case 2:
kpeter@750
   367
          child_a = _data[_data[a].child].parent;
kpeter@750
   368
          if( _data[a].left_child ) {
kpeter@750
   369
            _data[child_a].left_child=true;
kpeter@750
   370
            _data[b].child=child_a;
kpeter@750
   371
            _data[child_a].parent=_data[a].parent;
kpeter@748
   372
          }
kpeter@748
   373
          else {
kpeter@750
   374
            _data[child_a].left_child=false;
kpeter@750
   375
            _data[child_a].parent=b;
kpeter@750
   376
            if( a!=_data[b].child )
kpeter@750
   377
              _data[_data[b].child].parent=child_a;
kpeter@748
   378
            else
kpeter@750
   379
              _data[b].child=child_a;
kpeter@748
   380
          }
kpeter@750
   381
          --_data[a].degree;
kpeter@750
   382
          _data[_data[a].child].parent=a;
kpeter@748
   383
          break;
kpeter@748
   384
kpeter@748
   385
        case 1:
kpeter@750
   386
          child_a = _data[a].child;
kpeter@750
   387
          if( !_data[child_a].left_child ) {
kpeter@750
   388
            --_data[a].degree;
kpeter@750
   389
            if( _data[a].left_child ) {
kpeter@750
   390
              _data[child_a].left_child=true;
kpeter@750
   391
              _data[child_a].parent=_data[a].parent;
kpeter@750
   392
              _data[b].child=child_a;
kpeter@748
   393
            }
kpeter@748
   394
            else {
kpeter@750
   395
              _data[child_a].left_child=false;
kpeter@750
   396
              _data[child_a].parent=b;
kpeter@750
   397
              if( a!=_data[b].child )
kpeter@750
   398
                _data[_data[b].child].parent=child_a;
kpeter@748
   399
              else
kpeter@750
   400
                _data[b].child=child_a;
kpeter@748
   401
            }
kpeter@750
   402
            _data[a].child=-1;
kpeter@748
   403
          }
kpeter@748
   404
          else {
kpeter@750
   405
            --_data[b].degree;
kpeter@750
   406
            if( _data[a].left_child ) {
kpeter@750
   407
              _data[b].child =
kpeter@750
   408
                (1==_data[b].degree) ? _data[a].parent : -1;
kpeter@748
   409
            } else {
kpeter@750
   410
              if (1==_data[b].degree)
kpeter@750
   411
                _data[_data[b].child].parent=b;
kpeter@748
   412
              else
kpeter@750
   413
                _data[b].child=-1;
kpeter@748
   414
            }
kpeter@748
   415
          }
kpeter@748
   416
          break;
kpeter@748
   417
kpeter@748
   418
        case 0:
kpeter@750
   419
          --_data[b].degree;
kpeter@750
   420
          if( _data[a].left_child ) {
kpeter@750
   421
            _data[b].child =
kpeter@750
   422
              (0!=_data[b].degree) ? _data[a].parent : -1;
kpeter@748
   423
          } else {
kpeter@750
   424
            if( 0!=_data[b].degree )
kpeter@750
   425
              _data[_data[b].child].parent=b;
kpeter@748
   426
            else
kpeter@750
   427
              _data[b].child=-1;
kpeter@748
   428
          }
kpeter@748
   429
          break;
kpeter@748
   430
      }
kpeter@750
   431
      _data[a].parent=-1;
kpeter@750
   432
      _data[a].left_child=false;
kpeter@748
   433
    }
kpeter@748
   434
kpeter@748
   435
    void fuse(int a, int b) {
kpeter@750
   436
      int child_a = _data[a].child;
kpeter@750
   437
      int child_b = _data[b].child;
kpeter@750
   438
      _data[a].child=b;
kpeter@750
   439
      _data[b].parent=a;
kpeter@750
   440
      _data[b].left_child=true;
kpeter@748
   441
kpeter@748
   442
      if( -1!=child_a ) {
kpeter@750
   443
        _data[b].child=child_a;
kpeter@750
   444
        _data[child_a].parent=b;
kpeter@750
   445
        _data[child_a].left_child=false;
kpeter@750
   446
        ++_data[b].degree;
kpeter@748
   447
kpeter@748
   448
        if( -1!=child_b ) {
kpeter@750
   449
           _data[b].child=child_b;
kpeter@750
   450
           _data[child_b].parent=child_a;
kpeter@748
   451
        }
kpeter@748
   452
      }
kpeter@750
   453
      else { ++_data[a].degree; }
kpeter@748
   454
    }
kpeter@748
   455
kpeter@748
   456
    class store {
kpeter@748
   457
      friend class PairingHeap;
kpeter@748
   458
kpeter@748
   459
      Item name;
kpeter@748
   460
      int parent;
kpeter@748
   461
      int child;
kpeter@748
   462
      bool left_child;
kpeter@748
   463
      int degree;
kpeter@748
   464
      bool in;
kpeter@748
   465
      Prio prio;
kpeter@748
   466
kpeter@748
   467
      store() : parent(-1), child(-1), left_child(false), degree(0), in(true) {}
kpeter@748
   468
    };
kpeter@748
   469
  };
kpeter@748
   470
kpeter@748
   471
} //namespace lemon
kpeter@748
   472
kpeter@748
   473
#endif //LEMON_PAIRING_HEAP_H
kpeter@748
   474