lemon/unionfind.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 16 Mar 2013 16:20:41 +0100
changeset 1070 ee9bac10f58e
parent 875 07ec2b52e53d
child 1092 dceba191c00d
permissions -rw-r--r--
Debug checking for capacity bounds in min cost flow algorithms (#454)
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@103
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@103
     4
 *
alpar@877
     5
 * Copyright (C) 2003-2010
alpar@103
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@103
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@103
     8
 *
alpar@103
     9
 * Permission to use, modify and distribute this software is granted
alpar@103
    10
 * provided that this copyright notice appears in all copies. For
alpar@103
    11
 * precise terms see the accompanying LICENSE file.
alpar@103
    12
 *
alpar@103
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@103
    14
 * express or implied, and with no claim as to its suitability for any
alpar@103
    15
 * purpose.
alpar@103
    16
 *
alpar@103
    17
 */
alpar@103
    18
alpar@103
    19
#ifndef LEMON_UNION_FIND_H
alpar@103
    20
#define LEMON_UNION_FIND_H
alpar@103
    21
alpar@103
    22
//!\ingroup auxdat
alpar@103
    23
//!\file
alpar@103
    24
//!\brief Union-Find data structures.
alpar@103
    25
//!
alpar@103
    26
alpar@103
    27
#include <vector>
alpar@103
    28
#include <list>
alpar@103
    29
#include <utility>
alpar@103
    30
#include <algorithm>
alpar@103
    31
#include <functional>
alpar@103
    32
deba@220
    33
#include <lemon/core.h>
alpar@103
    34
alpar@103
    35
namespace lemon {
alpar@103
    36
alpar@103
    37
  /// \ingroup auxdat
alpar@103
    38
  ///
alpar@103
    39
  /// \brief A \e Union-Find data structure implementation
alpar@103
    40
  ///
alpar@209
    41
  /// The class implements the \e Union-Find data structure.
alpar@103
    42
  /// The union operation uses rank heuristic, while
alpar@103
    43
  /// the find operation uses path compression.
alpar@209
    44
  /// This is a very simple but efficient implementation, providing
alpar@103
    45
  /// only four methods: join (union), find, insert and size.
kpeter@786
    46
  /// For more features, see the \ref UnionFindEnum class.
alpar@103
    47
  ///
alpar@103
    48
  /// It is primarily used in Kruskal algorithm for finding minimal
alpar@103
    49
  /// cost spanning tree in a graph.
alpar@103
    50
  /// \sa kruskal()
alpar@103
    51
  ///
alpar@103
    52
  /// \pre You need to add all the elements by the \ref insert()
alpar@209
    53
  /// method.
kpeter@559
    54
  template <typename IM>
alpar@103
    55
  class UnionFind {
alpar@103
    56
  public:
alpar@103
    57
kpeter@559
    58
    ///\e
kpeter@559
    59
    typedef IM ItemIntMap;
kpeter@559
    60
    ///\e
alpar@103
    61
    typedef typename ItemIntMap::Key Item;
alpar@103
    62
alpar@103
    63
  private:
alpar@103
    64
    // If the items vector stores negative value for an item then
alpar@103
    65
    // that item is root item and it has -items[it] component size.
alpar@103
    66
    // Else the items[it] contains the index of the parent.
alpar@103
    67
    std::vector<int> items;
alpar@103
    68
    ItemIntMap& index;
alpar@103
    69
alpar@103
    70
    bool rep(int idx) const {
alpar@103
    71
      return items[idx] < 0;
alpar@103
    72
    }
alpar@103
    73
alpar@103
    74
    int repIndex(int idx) const {
alpar@103
    75
      int k = idx;
alpar@103
    76
      while (!rep(k)) {
alpar@103
    77
        k = items[k] ;
alpar@103
    78
      }
alpar@103
    79
      while (idx != k) {
alpar@103
    80
        int next = items[idx];
alpar@103
    81
        const_cast<int&>(items[idx]) = k;
alpar@103
    82
        idx = next;
alpar@103
    83
      }
alpar@103
    84
      return k;
alpar@103
    85
    }
alpar@103
    86
alpar@103
    87
  public:
alpar@103
    88
alpar@103
    89
    /// \brief Constructor
alpar@103
    90
    ///
alpar@103
    91
    /// Constructor of the UnionFind class. You should give an item to
alpar@103
    92
    /// integer map which will be used from the data structure. If you
alpar@103
    93
    /// modify directly this map that may cause segmentation fault,
alpar@103
    94
    /// invalid data structure, or infinite loop when you use again
alpar@103
    95
    /// the union-find.
alpar@103
    96
    UnionFind(ItemIntMap& m) : index(m) {}
alpar@103
    97
alpar@103
    98
    /// \brief Returns the index of the element's component.
alpar@103
    99
    ///
alpar@103
   100
    /// The method returns the index of the element's component.
alpar@103
   101
    /// This is an integer between zero and the number of inserted elements.
alpar@103
   102
    ///
alpar@103
   103
    int find(const Item& a) {
alpar@103
   104
      return repIndex(index[a]);
alpar@103
   105
    }
alpar@103
   106
alpar@103
   107
    /// \brief Clears the union-find data structure
alpar@103
   108
    ///
alpar@103
   109
    /// Erase each item from the data structure.
alpar@103
   110
    void clear() {
alpar@103
   111
      items.clear();
alpar@103
   112
    }
alpar@103
   113
alpar@103
   114
    /// \brief Inserts a new element into the structure.
alpar@103
   115
    ///
alpar@209
   116
    /// This method inserts a new element into the data structure.
alpar@103
   117
    ///
alpar@103
   118
    /// The method returns the index of the new component.
alpar@103
   119
    int insert(const Item& a) {
alpar@103
   120
      int n = items.size();
alpar@103
   121
      items.push_back(-1);
alpar@103
   122
      index.set(a,n);
alpar@103
   123
      return n;
alpar@103
   124
    }
alpar@103
   125
alpar@103
   126
    /// \brief Joining the components of element \e a and element \e b.
alpar@103
   127
    ///
alpar@209
   128
    /// This is the \e union operation of the Union-Find structure.
alpar@103
   129
    /// Joins the component of element \e a and component of
alpar@103
   130
    /// element \e b. If \e a and \e b are in the same component then
alpar@103
   131
    /// it returns false otherwise it returns true.
alpar@103
   132
    bool join(const Item& a, const Item& b) {
alpar@103
   133
      int ka = repIndex(index[a]);
alpar@103
   134
      int kb = repIndex(index[b]);
alpar@103
   135
alpar@209
   136
      if ( ka == kb )
alpar@209
   137
        return false;
alpar@103
   138
alpar@103
   139
      if (items[ka] < items[kb]) {
alpar@209
   140
        items[ka] += items[kb];
alpar@209
   141
        items[kb] = ka;
alpar@103
   142
      } else {
alpar@209
   143
        items[kb] += items[ka];
alpar@209
   144
        items[ka] = kb;
alpar@103
   145
      }
alpar@103
   146
      return true;
alpar@103
   147
    }
alpar@103
   148
alpar@103
   149
    /// \brief Returns the size of the component of element \e a.
alpar@103
   150
    ///
alpar@103
   151
    /// Returns the size of the component of element \e a.
alpar@103
   152
    int size(const Item& a) {
alpar@103
   153
      int k = repIndex(index[a]);
alpar@103
   154
      return - items[k];
alpar@103
   155
    }
alpar@103
   156
alpar@103
   157
  };
alpar@103
   158
alpar@103
   159
  /// \ingroup auxdat
alpar@103
   160
  ///
alpar@103
   161
  /// \brief A \e Union-Find data structure implementation which
alpar@103
   162
  /// is able to enumerate the components.
alpar@103
   163
  ///
alpar@103
   164
  /// The class implements a \e Union-Find data structure
alpar@103
   165
  /// which is able to enumerate the components and the items in
alpar@103
   166
  /// a component. If you don't need this feature then perhaps it's
alpar@103
   167
  /// better to use the \ref UnionFind class which is more efficient.
alpar@103
   168
  ///
alpar@103
   169
  /// The union operation uses rank heuristic, while
alpar@103
   170
  /// the find operation uses path compression.
alpar@103
   171
  ///
alpar@103
   172
  /// \pre You need to add all the elements by the \ref insert()
alpar@103
   173
  /// method.
alpar@103
   174
  ///
kpeter@559
   175
  template <typename IM>
alpar@103
   176
  class UnionFindEnum {
alpar@103
   177
  public:
alpar@209
   178
kpeter@559
   179
    ///\e
kpeter@559
   180
    typedef IM ItemIntMap;
kpeter@559
   181
    ///\e
alpar@103
   182
    typedef typename ItemIntMap::Key Item;
alpar@103
   183
alpar@103
   184
  private:
alpar@209
   185
alpar@103
   186
    ItemIntMap& index;
alpar@103
   187
alpar@103
   188
    // If the parent stores negative value for an item then that item
alpar@103
   189
    // is root item and it has ~(items[it].parent) component id.  Else
alpar@103
   190
    // the items[it].parent contains the index of the parent.
alpar@103
   191
    //
alpar@103
   192
    // The \c next and \c prev provides the double-linked
alpar@103
   193
    // cyclic list of one component's items.
alpar@103
   194
    struct ItemT {
alpar@103
   195
      int parent;
alpar@103
   196
      Item item;
alpar@103
   197
alpar@103
   198
      int next, prev;
alpar@103
   199
    };
alpar@103
   200
alpar@103
   201
    std::vector<ItemT> items;
alpar@103
   202
    int firstFreeItem;
alpar@103
   203
alpar@103
   204
    struct ClassT {
alpar@103
   205
      int size;
alpar@103
   206
      int firstItem;
alpar@103
   207
      int next, prev;
alpar@103
   208
    };
alpar@209
   209
alpar@103
   210
    std::vector<ClassT> classes;
alpar@103
   211
    int firstClass, firstFreeClass;
alpar@103
   212
alpar@103
   213
    int newClass() {
alpar@103
   214
      if (firstFreeClass == -1) {
alpar@209
   215
        int cdx = classes.size();
alpar@209
   216
        classes.push_back(ClassT());
alpar@209
   217
        return cdx;
alpar@103
   218
      } else {
alpar@209
   219
        int cdx = firstFreeClass;
alpar@209
   220
        firstFreeClass = classes[firstFreeClass].next;
alpar@209
   221
        return cdx;
alpar@103
   222
      }
alpar@103
   223
    }
alpar@103
   224
alpar@103
   225
    int newItem() {
alpar@103
   226
      if (firstFreeItem == -1) {
alpar@209
   227
        int idx = items.size();
alpar@209
   228
        items.push_back(ItemT());
alpar@209
   229
        return idx;
alpar@103
   230
      } else {
alpar@209
   231
        int idx = firstFreeItem;
alpar@209
   232
        firstFreeItem = items[firstFreeItem].next;
alpar@209
   233
        return idx;
alpar@103
   234
      }
alpar@103
   235
    }
alpar@103
   236
alpar@103
   237
alpar@103
   238
    bool rep(int idx) const {
alpar@103
   239
      return items[idx].parent < 0;
alpar@103
   240
    }
alpar@103
   241
alpar@103
   242
    int repIndex(int idx) const {
alpar@103
   243
      int k = idx;
alpar@103
   244
      while (!rep(k)) {
alpar@103
   245
        k = items[k].parent;
alpar@103
   246
      }
alpar@103
   247
      while (idx != k) {
alpar@103
   248
        int next = items[idx].parent;
alpar@103
   249
        const_cast<int&>(items[idx].parent) = k;
alpar@103
   250
        idx = next;
alpar@103
   251
      }
alpar@103
   252
      return k;
alpar@103
   253
    }
alpar@103
   254
alpar@103
   255
    int classIndex(int idx) const {
alpar@103
   256
      return ~(items[repIndex(idx)].parent);
alpar@103
   257
    }
alpar@103
   258
alpar@103
   259
    void singletonItem(int idx) {
alpar@103
   260
      items[idx].next = idx;
alpar@103
   261
      items[idx].prev = idx;
alpar@103
   262
    }
alpar@103
   263
alpar@103
   264
    void laceItem(int idx, int rdx) {
alpar@103
   265
      items[idx].prev = rdx;
alpar@103
   266
      items[idx].next = items[rdx].next;
alpar@103
   267
      items[items[rdx].next].prev = idx;
alpar@103
   268
      items[rdx].next = idx;
alpar@103
   269
    }
alpar@103
   270
alpar@103
   271
    void unlaceItem(int idx) {
alpar@103
   272
      items[items[idx].prev].next = items[idx].next;
alpar@103
   273
      items[items[idx].next].prev = items[idx].prev;
alpar@209
   274
alpar@103
   275
      items[idx].next = firstFreeItem;
alpar@103
   276
      firstFreeItem = idx;
alpar@103
   277
    }
alpar@103
   278
alpar@103
   279
    void spliceItems(int ak, int bk) {
alpar@103
   280
      items[items[ak].prev].next = bk;
alpar@103
   281
      items[items[bk].prev].next = ak;
alpar@103
   282
      int tmp = items[ak].prev;
alpar@103
   283
      items[ak].prev = items[bk].prev;
alpar@103
   284
      items[bk].prev = tmp;
alpar@209
   285
alpar@103
   286
    }
alpar@103
   287
alpar@103
   288
    void laceClass(int cls) {
alpar@103
   289
      if (firstClass != -1) {
alpar@103
   290
        classes[firstClass].prev = cls;
alpar@103
   291
      }
alpar@103
   292
      classes[cls].next = firstClass;
alpar@103
   293
      classes[cls].prev = -1;
alpar@103
   294
      firstClass = cls;
alpar@209
   295
    }
alpar@103
   296
alpar@103
   297
    void unlaceClass(int cls) {
alpar@103
   298
      if (classes[cls].prev != -1) {
alpar@103
   299
        classes[classes[cls].prev].next = classes[cls].next;
alpar@103
   300
      } else {
alpar@103
   301
        firstClass = classes[cls].next;
alpar@103
   302
      }
alpar@103
   303
      if (classes[cls].next != -1) {
alpar@103
   304
        classes[classes[cls].next].prev = classes[cls].prev;
alpar@103
   305
      }
alpar@209
   306
alpar@103
   307
      classes[cls].next = firstFreeClass;
alpar@103
   308
      firstFreeClass = cls;
alpar@209
   309
    }
alpar@103
   310
alpar@103
   311
  public:
alpar@103
   312
alpar@209
   313
    UnionFindEnum(ItemIntMap& _index)
alpar@209
   314
      : index(_index), items(), firstFreeItem(-1),
alpar@209
   315
        firstClass(-1), firstFreeClass(-1) {}
alpar@209
   316
alpar@103
   317
    /// \brief Inserts the given element into a new component.
alpar@103
   318
    ///
alpar@103
   319
    /// This method creates a new component consisting only of the
alpar@103
   320
    /// given element.
alpar@103
   321
    ///
alpar@103
   322
    int insert(const Item& item) {
alpar@103
   323
      int idx = newItem();
alpar@103
   324
alpar@103
   325
      index.set(item, idx);
alpar@103
   326
alpar@103
   327
      singletonItem(idx);
alpar@103
   328
      items[idx].item = item;
alpar@103
   329
alpar@103
   330
      int cdx = newClass();
alpar@103
   331
alpar@103
   332
      items[idx].parent = ~cdx;
alpar@103
   333
alpar@103
   334
      laceClass(cdx);
alpar@103
   335
      classes[cdx].size = 1;
alpar@103
   336
      classes[cdx].firstItem = idx;
alpar@103
   337
alpar@103
   338
      firstClass = cdx;
alpar@209
   339
alpar@103
   340
      return cdx;
alpar@103
   341
    }
alpar@103
   342
alpar@103
   343
    /// \brief Inserts the given element into the component of the others.
alpar@103
   344
    ///
alpar@103
   345
    /// This methods inserts the element \e a into the component of the
alpar@209
   346
    /// element \e comp.
alpar@103
   347
    void insert(const Item& item, int cls) {
alpar@103
   348
      int rdx = classes[cls].firstItem;
alpar@103
   349
      int idx = newItem();
alpar@103
   350
alpar@103
   351
      index.set(item, idx);
alpar@103
   352
alpar@103
   353
      laceItem(idx, rdx);
alpar@103
   354
alpar@103
   355
      items[idx].item = item;
alpar@103
   356
      items[idx].parent = rdx;
alpar@103
   357
alpar@103
   358
      ++classes[~(items[rdx].parent)].size;
alpar@103
   359
    }
alpar@103
   360
alpar@103
   361
    /// \brief Clears the union-find data structure
alpar@103
   362
    ///
alpar@103
   363
    /// Erase each item from the data structure.
alpar@103
   364
    void clear() {
alpar@103
   365
      items.clear();
alpar@103
   366
      firstClass = -1;
alpar@103
   367
      firstFreeItem = -1;
alpar@103
   368
    }
alpar@103
   369
alpar@103
   370
    /// \brief Finds the component of the given element.
alpar@103
   371
    ///
alpar@103
   372
    /// The method returns the component id of the given element.
alpar@103
   373
    int find(const Item &item) const {
alpar@103
   374
      return ~(items[repIndex(index[item])].parent);
alpar@103
   375
    }
alpar@103
   376
alpar@103
   377
    /// \brief Joining the component of element \e a and element \e b.
alpar@103
   378
    ///
alpar@209
   379
    /// This is the \e union operation of the Union-Find structure.
alpar@103
   380
    /// Joins the component of element \e a and component of
alpar@103
   381
    /// element \e b. If \e a and \e b are in the same component then
alpar@103
   382
    /// returns -1 else returns the remaining class.
alpar@103
   383
    int join(const Item& a, const Item& b) {
alpar@103
   384
alpar@103
   385
      int ak = repIndex(index[a]);
alpar@103
   386
      int bk = repIndex(index[b]);
alpar@103
   387
alpar@103
   388
      if (ak == bk) {
alpar@209
   389
        return -1;
alpar@103
   390
      }
alpar@103
   391
alpar@103
   392
      int acx = ~(items[ak].parent);
alpar@103
   393
      int bcx = ~(items[bk].parent);
alpar@103
   394
alpar@103
   395
      int rcx;
alpar@103
   396
alpar@103
   397
      if (classes[acx].size > classes[bcx].size) {
alpar@209
   398
        classes[acx].size += classes[bcx].size;
alpar@209
   399
        items[bk].parent = ak;
alpar@103
   400
        unlaceClass(bcx);
alpar@209
   401
        rcx = acx;
alpar@103
   402
      } else {
alpar@209
   403
        classes[bcx].size += classes[acx].size;
alpar@209
   404
        items[ak].parent = bk;
alpar@103
   405
        unlaceClass(acx);
alpar@209
   406
        rcx = bcx;
alpar@103
   407
      }
alpar@103
   408
      spliceItems(ak, bk);
alpar@103
   409
alpar@103
   410
      return rcx;
alpar@103
   411
    }
alpar@103
   412
alpar@103
   413
    /// \brief Returns the size of the class.
alpar@103
   414
    ///
alpar@103
   415
    /// Returns the size of the class.
alpar@103
   416
    int size(int cls) const {
alpar@103
   417
      return classes[cls].size;
alpar@103
   418
    }
alpar@103
   419
alpar@209
   420
    /// \brief Splits up the component.
alpar@103
   421
    ///
alpar@103
   422
    /// Splitting the component into singleton components (component
alpar@103
   423
    /// of size one).
alpar@103
   424
    void split(int cls) {
alpar@103
   425
      int fdx = classes[cls].firstItem;
alpar@103
   426
      int idx = items[fdx].next;
alpar@103
   427
      while (idx != fdx) {
alpar@103
   428
        int next = items[idx].next;
alpar@103
   429
alpar@209
   430
        singletonItem(idx);
alpar@103
   431
alpar@209
   432
        int cdx = newClass();
alpar@103
   433
        items[idx].parent = ~cdx;
alpar@103
   434
alpar@209
   435
        laceClass(cdx);
alpar@209
   436
        classes[cdx].size = 1;
alpar@209
   437
        classes[cdx].firstItem = idx;
alpar@209
   438
alpar@103
   439
        idx = next;
alpar@103
   440
      }
alpar@103
   441
alpar@103
   442
      items[idx].prev = idx;
alpar@103
   443
      items[idx].next = idx;
alpar@103
   444
alpar@103
   445
      classes[~(items[idx].parent)].size = 1;
alpar@209
   446
alpar@103
   447
    }
alpar@103
   448
alpar@103
   449
    /// \brief Removes the given element from the structure.
alpar@103
   450
    ///
alpar@103
   451
    /// Removes the element from its component and if the component becomes
alpar@103
   452
    /// empty then removes that component from the component list.
alpar@103
   453
    ///
alpar@103
   454
    /// \warning It is an error to remove an element which is not in
alpar@103
   455
    /// the structure.
alpar@103
   456
    /// \warning This running time of this operation is proportional to the
alpar@103
   457
    /// number of the items in this class.
alpar@103
   458
    void erase(const Item& item) {
alpar@103
   459
      int idx = index[item];
alpar@103
   460
      int fdx = items[idx].next;
alpar@103
   461
alpar@103
   462
      int cdx = classIndex(idx);
alpar@103
   463
      if (idx == fdx) {
alpar@209
   464
        unlaceClass(cdx);
alpar@209
   465
        items[idx].next = firstFreeItem;
alpar@209
   466
        firstFreeItem = idx;
alpar@209
   467
        return;
alpar@103
   468
      } else {
alpar@209
   469
        classes[cdx].firstItem = fdx;
alpar@209
   470
        --classes[cdx].size;
alpar@209
   471
        items[fdx].parent = ~cdx;
alpar@103
   472
alpar@209
   473
        unlaceItem(idx);
alpar@209
   474
        idx = items[fdx].next;
alpar@209
   475
        while (idx != fdx) {
alpar@209
   476
          items[idx].parent = fdx;
alpar@209
   477
          idx = items[idx].next;
alpar@209
   478
        }
alpar@209
   479
alpar@103
   480
      }
alpar@103
   481
alpar@103
   482
    }
alpar@103
   483
alpar@103
   484
    /// \brief Gives back a representant item of the component.
alpar@103
   485
    ///
alpar@103
   486
    /// Gives back a representant item of the component.
alpar@103
   487
    Item item(int cls) const {
alpar@103
   488
      return items[classes[cls].firstItem].item;
alpar@103
   489
    }
alpar@103
   490
alpar@103
   491
    /// \brief Removes the component of the given element from the structure.
alpar@103
   492
    ///
alpar@103
   493
    /// Removes the component of the given element from the structure.
alpar@103
   494
    ///
alpar@103
   495
    /// \warning It is an error to give an element which is not in the
alpar@103
   496
    /// structure.
alpar@103
   497
    void eraseClass(int cls) {
alpar@103
   498
      int fdx = classes[cls].firstItem;
alpar@103
   499
      unlaceClass(cls);
alpar@103
   500
      items[items[fdx].prev].next = firstFreeItem;
alpar@103
   501
      firstFreeItem = fdx;
alpar@103
   502
    }
alpar@103
   503
ladanyi@236
   504
    /// \brief LEMON style iterator for the representant items.
alpar@103
   505
    ///
alpar@103
   506
    /// ClassIt is a lemon style iterator for the components. It iterates
alpar@103
   507
    /// on the ids of the classes.
alpar@103
   508
    class ClassIt {
alpar@103
   509
    public:
alpar@103
   510
      /// \brief Constructor of the iterator
alpar@103
   511
      ///
alpar@103
   512
      /// Constructor of the iterator
alpar@103
   513
      ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
alpar@103
   514
        cdx = unionFind->firstClass;
alpar@103
   515
      }
alpar@103
   516
alpar@103
   517
      /// \brief Constructor to get invalid iterator
alpar@103
   518
      ///
alpar@103
   519
      /// Constructor to get invalid iterator
alpar@103
   520
      ClassIt(Invalid) : unionFind(0), cdx(-1) {}
alpar@209
   521
alpar@103
   522
      /// \brief Increment operator
alpar@103
   523
      ///
alpar@103
   524
      /// It steps to the next representant item.
alpar@103
   525
      ClassIt& operator++() {
alpar@103
   526
        cdx = unionFind->classes[cdx].next;
alpar@103
   527
        return *this;
alpar@103
   528
      }
alpar@209
   529
alpar@103
   530
      /// \brief Conversion operator
alpar@103
   531
      ///
alpar@103
   532
      /// It converts the iterator to the current representant item.
alpar@103
   533
      operator int() const {
alpar@103
   534
        return cdx;
alpar@103
   535
      }
alpar@103
   536
alpar@103
   537
      /// \brief Equality operator
alpar@103
   538
      ///
alpar@103
   539
      /// Equality operator
alpar@209
   540
      bool operator==(const ClassIt& i) {
alpar@103
   541
        return i.cdx == cdx;
alpar@103
   542
      }
alpar@103
   543
alpar@103
   544
      /// \brief Inequality operator
alpar@103
   545
      ///
alpar@103
   546
      /// Inequality operator
alpar@209
   547
      bool operator!=(const ClassIt& i) {
alpar@103
   548
        return i.cdx != cdx;
alpar@103
   549
      }
alpar@209
   550
alpar@103
   551
    private:
alpar@103
   552
      const UnionFindEnum* unionFind;
alpar@103
   553
      int cdx;
alpar@103
   554
    };
alpar@103
   555
ladanyi@236
   556
    /// \brief LEMON style iterator for the items of a component.
alpar@103
   557
    ///
alpar@103
   558
    /// ClassIt is a lemon style iterator for the components. It iterates
alpar@103
   559
    /// on the items of a class. By example if you want to iterate on
alpar@103
   560
    /// each items of each classes then you may write the next code.
alpar@103
   561
    ///\code
alpar@103
   562
    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
alpar@103
   563
    ///   std::cout << "Class: ";
alpar@103
   564
    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
alpar@103
   565
    ///     std::cout << toString(iit) << ' ' << std::endl;
alpar@103
   566
    ///   }
alpar@103
   567
    ///   std::cout << std::endl;
alpar@103
   568
    /// }
alpar@103
   569
    ///\endcode
alpar@103
   570
    class ItemIt {
alpar@103
   571
    public:
alpar@103
   572
      /// \brief Constructor of the iterator
alpar@103
   573
      ///
alpar@103
   574
      /// Constructor of the iterator. The iterator iterates
alpar@103
   575
      /// on the class of the \c item.
alpar@103
   576
      ItemIt(const UnionFindEnum& ufe, int cls) : unionFind(&ufe) {
alpar@103
   577
        fdx = idx = unionFind->classes[cls].firstItem;
alpar@103
   578
      }
alpar@103
   579
alpar@103
   580
      /// \brief Constructor to get invalid iterator
alpar@103
   581
      ///
alpar@103
   582
      /// Constructor to get invalid iterator
alpar@103
   583
      ItemIt(Invalid) : unionFind(0), idx(-1) {}
alpar@209
   584
alpar@103
   585
      /// \brief Increment operator
alpar@103
   586
      ///
alpar@103
   587
      /// It steps to the next item in the class.
alpar@103
   588
      ItemIt& operator++() {
alpar@103
   589
        idx = unionFind->items[idx].next;
alpar@103
   590
        if (idx == fdx) idx = -1;
alpar@103
   591
        return *this;
alpar@103
   592
      }
alpar@209
   593
alpar@103
   594
      /// \brief Conversion operator
alpar@103
   595
      ///
alpar@103
   596
      /// It converts the iterator to the current item.
alpar@103
   597
      operator const Item&() const {
alpar@103
   598
        return unionFind->items[idx].item;
alpar@103
   599
      }
alpar@103
   600
alpar@103
   601
      /// \brief Equality operator
alpar@103
   602
      ///
alpar@103
   603
      /// Equality operator
alpar@209
   604
      bool operator==(const ItemIt& i) {
alpar@103
   605
        return i.idx == idx;
alpar@103
   606
      }
alpar@103
   607
alpar@103
   608
      /// \brief Inequality operator
alpar@103
   609
      ///
alpar@103
   610
      /// Inequality operator
alpar@209
   611
      bool operator!=(const ItemIt& i) {
alpar@103
   612
        return i.idx != idx;
alpar@103
   613
      }
alpar@209
   614
alpar@103
   615
    private:
alpar@103
   616
      const UnionFindEnum* unionFind;
alpar@103
   617
      int idx, fdx;
alpar@103
   618
    };
alpar@103
   619
alpar@103
   620
  };
alpar@103
   621
alpar@103
   622
  /// \ingroup auxdat
alpar@103
   623
  ///
alpar@103
   624
  /// \brief A \e Extend-Find data structure implementation which
alpar@103
   625
  /// is able to enumerate the components.
alpar@103
   626
  ///
alpar@103
   627
  /// The class implements an \e Extend-Find data structure which is
alpar@103
   628
  /// able to enumerate the components and the items in a
alpar@103
   629
  /// component. The data structure is a simplification of the
alpar@103
   630
  /// Union-Find structure, and it does not allow to merge two components.
alpar@103
   631
  ///
alpar@103
   632
  /// \pre You need to add all the elements by the \ref insert()
alpar@103
   633
  /// method.
kpeter@559
   634
  template <typename IM>
alpar@103
   635
  class ExtendFindEnum {
alpar@103
   636
  public:
alpar@209
   637
kpeter@559
   638
    ///\e
kpeter@559
   639
    typedef IM ItemIntMap;
kpeter@559
   640
    ///\e
alpar@103
   641
    typedef typename ItemIntMap::Key Item;
alpar@103
   642
alpar@103
   643
  private:
alpar@209
   644
alpar@103
   645
    ItemIntMap& index;
alpar@103
   646
alpar@103
   647
    struct ItemT {
alpar@103
   648
      int cls;
alpar@103
   649
      Item item;
alpar@103
   650
      int next, prev;
alpar@103
   651
    };
alpar@103
   652
alpar@103
   653
    std::vector<ItemT> items;
alpar@103
   654
    int firstFreeItem;
alpar@103
   655
alpar@103
   656
    struct ClassT {
alpar@103
   657
      int firstItem;
alpar@103
   658
      int next, prev;
alpar@103
   659
    };
alpar@103
   660
alpar@103
   661
    std::vector<ClassT> classes;
alpar@103
   662
alpar@103
   663
    int firstClass, firstFreeClass;
alpar@103
   664
alpar@103
   665
    int newClass() {
alpar@103
   666
      if (firstFreeClass != -1) {
alpar@209
   667
        int cdx = firstFreeClass;
alpar@209
   668
        firstFreeClass = classes[cdx].next;
alpar@209
   669
        return cdx;
alpar@103
   670
      } else {
alpar@209
   671
        classes.push_back(ClassT());
alpar@209
   672
        return classes.size() - 1;
alpar@103
   673
      }
alpar@103
   674
    }
alpar@103
   675
alpar@103
   676
    int newItem() {
alpar@103
   677
      if (firstFreeItem != -1) {
alpar@209
   678
        int idx = firstFreeItem;
alpar@209
   679
        firstFreeItem = items[idx].next;
alpar@209
   680
        return idx;
alpar@103
   681
      } else {
alpar@209
   682
        items.push_back(ItemT());
alpar@209
   683
        return items.size() - 1;
alpar@103
   684
      }
alpar@103
   685
    }
alpar@103
   686
alpar@103
   687
  public:
alpar@103
   688
alpar@103
   689
    /// \brief Constructor
alpar@209
   690
    ExtendFindEnum(ItemIntMap& _index)
alpar@209
   691
      : index(_index), items(), firstFreeItem(-1),
alpar@209
   692
        classes(), firstClass(-1), firstFreeClass(-1) {}
alpar@209
   693
alpar@103
   694
    /// \brief Inserts the given element into a new component.
alpar@103
   695
    ///
alpar@103
   696
    /// This method creates a new component consisting only of the
alpar@103
   697
    /// given element.
alpar@103
   698
    int insert(const Item& item) {
alpar@103
   699
      int cdx = newClass();
alpar@103
   700
      classes[cdx].prev = -1;
alpar@103
   701
      classes[cdx].next = firstClass;
alpar@103
   702
      if (firstClass != -1) {
alpar@209
   703
        classes[firstClass].prev = cdx;
alpar@103
   704
      }
alpar@103
   705
      firstClass = cdx;
alpar@209
   706
alpar@103
   707
      int idx = newItem();
alpar@103
   708
      items[idx].item = item;
alpar@103
   709
      items[idx].cls = cdx;
alpar@103
   710
      items[idx].prev = idx;
alpar@103
   711
      items[idx].next = idx;
alpar@103
   712
alpar@103
   713
      classes[cdx].firstItem = idx;
alpar@103
   714
alpar@103
   715
      index.set(item, idx);
alpar@209
   716
alpar@103
   717
      return cdx;
alpar@103
   718
    }
alpar@103
   719
alpar@103
   720
    /// \brief Inserts the given element into the given component.
alpar@103
   721
    ///
alpar@103
   722
    /// This methods inserts the element \e item a into the \e cls class.
alpar@103
   723
    void insert(const Item& item, int cls) {
alpar@103
   724
      int idx = newItem();
alpar@103
   725
      int rdx = classes[cls].firstItem;
alpar@103
   726
      items[idx].item = item;
alpar@103
   727
      items[idx].cls = cls;
alpar@103
   728
alpar@103
   729
      items[idx].prev = rdx;
alpar@103
   730
      items[idx].next = items[rdx].next;
alpar@103
   731
      items[items[rdx].next].prev = idx;
alpar@103
   732
      items[rdx].next = idx;
alpar@103
   733
alpar@103
   734
      index.set(item, idx);
alpar@103
   735
    }
alpar@103
   736
alpar@103
   737
    /// \brief Clears the union-find data structure
alpar@103
   738
    ///
alpar@103
   739
    /// Erase each item from the data structure.
alpar@103
   740
    void clear() {
alpar@103
   741
      items.clear();
deba@867
   742
      classes.clear();
alpar@103
   743
      firstClass = firstFreeClass = firstFreeItem = -1;
alpar@103
   744
    }
alpar@103
   745
alpar@103
   746
    /// \brief Gives back the class of the \e item.
alpar@103
   747
    ///
alpar@103
   748
    /// Gives back the class of the \e item.
alpar@103
   749
    int find(const Item &item) const {
alpar@103
   750
      return items[index[item]].cls;
alpar@103
   751
    }
alpar@103
   752
alpar@103
   753
    /// \brief Gives back a representant item of the component.
alpar@103
   754
    ///
alpar@103
   755
    /// Gives back a representant item of the component.
alpar@103
   756
    Item item(int cls) const {
alpar@103
   757
      return items[classes[cls].firstItem].item;
alpar@103
   758
    }
alpar@209
   759
alpar@103
   760
    /// \brief Removes the given element from the structure.
alpar@103
   761
    ///
alpar@103
   762
    /// Removes the element from its component and if the component becomes
alpar@103
   763
    /// empty then removes that component from the component list.
alpar@103
   764
    ///
alpar@103
   765
    /// \warning It is an error to remove an element which is not in
alpar@103
   766
    /// the structure.
alpar@103
   767
    void erase(const Item &item) {
alpar@103
   768
      int idx = index[item];
alpar@103
   769
      int cdx = items[idx].cls;
alpar@209
   770
alpar@103
   771
      if (idx == items[idx].next) {
alpar@209
   772
        if (classes[cdx].prev != -1) {
alpar@209
   773
          classes[classes[cdx].prev].next = classes[cdx].next;
alpar@209
   774
        } else {
alpar@209
   775
          firstClass = classes[cdx].next;
alpar@209
   776
        }
alpar@209
   777
        if (classes[cdx].next != -1) {
alpar@209
   778
          classes[classes[cdx].next].prev = classes[cdx].prev;
alpar@209
   779
        }
alpar@209
   780
        classes[cdx].next = firstFreeClass;
alpar@209
   781
        firstFreeClass = cdx;
alpar@103
   782
      } else {
alpar@209
   783
        classes[cdx].firstItem = items[idx].next;
alpar@209
   784
        items[items[idx].next].prev = items[idx].prev;
alpar@209
   785
        items[items[idx].prev].next = items[idx].next;
alpar@103
   786
      }
alpar@103
   787
      items[idx].next = firstFreeItem;
alpar@103
   788
      firstFreeItem = idx;
alpar@103
   789
alpar@209
   790
    }
alpar@209
   791
alpar@209
   792
alpar@103
   793
    /// \brief Removes the component of the given element from the structure.
alpar@103
   794
    ///
alpar@103
   795
    /// Removes the component of the given element from the structure.
alpar@103
   796
    ///
alpar@103
   797
    /// \warning It is an error to give an element which is not in the
alpar@103
   798
    /// structure.
alpar@103
   799
    void eraseClass(int cdx) {
alpar@103
   800
      int idx = classes[cdx].firstItem;
alpar@103
   801
      items[items[idx].prev].next = firstFreeItem;
alpar@103
   802
      firstFreeItem = idx;
alpar@103
   803
alpar@103
   804
      if (classes[cdx].prev != -1) {
alpar@209
   805
        classes[classes[cdx].prev].next = classes[cdx].next;
alpar@103
   806
      } else {
alpar@209
   807
        firstClass = classes[cdx].next;
alpar@103
   808
      }
alpar@103
   809
      if (classes[cdx].next != -1) {
alpar@209
   810
        classes[classes[cdx].next].prev = classes[cdx].prev;
alpar@103
   811
      }
alpar@103
   812
      classes[cdx].next = firstFreeClass;
alpar@103
   813
      firstFreeClass = cdx;
alpar@103
   814
    }
alpar@103
   815
ladanyi@236
   816
    /// \brief LEMON style iterator for the classes.
alpar@103
   817
    ///
alpar@103
   818
    /// ClassIt is a lemon style iterator for the components. It iterates
alpar@103
   819
    /// on the ids of classes.
alpar@103
   820
    class ClassIt {
alpar@103
   821
    public:
alpar@103
   822
      /// \brief Constructor of the iterator
alpar@103
   823
      ///
alpar@103
   824
      /// Constructor of the iterator
alpar@103
   825
      ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) {
alpar@103
   826
        cdx = extendFind->firstClass;
alpar@103
   827
      }
alpar@103
   828
alpar@103
   829
      /// \brief Constructor to get invalid iterator
alpar@103
   830
      ///
alpar@103
   831
      /// Constructor to get invalid iterator
alpar@103
   832
      ClassIt(Invalid) : extendFind(0), cdx(-1) {}
alpar@209
   833
alpar@103
   834
      /// \brief Increment operator
alpar@103
   835
      ///
alpar@103
   836
      /// It steps to the next representant item.
alpar@103
   837
      ClassIt& operator++() {
alpar@103
   838
        cdx = extendFind->classes[cdx].next;
alpar@103
   839
        return *this;
alpar@103
   840
      }
alpar@209
   841
alpar@103
   842
      /// \brief Conversion operator
alpar@103
   843
      ///
alpar@103
   844
      /// It converts the iterator to the current class id.
alpar@103
   845
      operator int() const {
alpar@103
   846
        return cdx;
alpar@103
   847
      }
alpar@103
   848
alpar@103
   849
      /// \brief Equality operator
alpar@103
   850
      ///
alpar@103
   851
      /// Equality operator
alpar@209
   852
      bool operator==(const ClassIt& i) {
alpar@103
   853
        return i.cdx == cdx;
alpar@103
   854
      }
alpar@103
   855
alpar@103
   856
      /// \brief Inequality operator
alpar@103
   857
      ///
alpar@103
   858
      /// Inequality operator
alpar@209
   859
      bool operator!=(const ClassIt& i) {
alpar@103
   860
        return i.cdx != cdx;
alpar@103
   861
      }
alpar@209
   862
alpar@103
   863
    private:
alpar@103
   864
      const ExtendFindEnum* extendFind;
alpar@103
   865
      int cdx;
alpar@103
   866
    };
alpar@103
   867
ladanyi@236
   868
    /// \brief LEMON style iterator for the items of a component.
alpar@103
   869
    ///
alpar@103
   870
    /// ClassIt is a lemon style iterator for the components. It iterates
alpar@103
   871
    /// on the items of a class. By example if you want to iterate on
alpar@103
   872
    /// each items of each classes then you may write the next code.
alpar@103
   873
    ///\code
alpar@103
   874
    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
alpar@103
   875
    ///   std::cout << "Class: ";
alpar@103
   876
    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
alpar@103
   877
    ///     std::cout << toString(iit) << ' ' << std::endl;
alpar@103
   878
    ///   }
alpar@103
   879
    ///   std::cout << std::endl;
alpar@103
   880
    /// }
alpar@103
   881
    ///\endcode
alpar@103
   882
    class ItemIt {
alpar@103
   883
    public:
alpar@103
   884
      /// \brief Constructor of the iterator
alpar@103
   885
      ///
alpar@103
   886
      /// Constructor of the iterator. The iterator iterates
alpar@103
   887
      /// on the class of the \c item.
alpar@103
   888
      ItemIt(const ExtendFindEnum& ufe, int cls) : extendFind(&ufe) {
alpar@103
   889
        fdx = idx = extendFind->classes[cls].firstItem;
alpar@103
   890
      }
alpar@103
   891
alpar@103
   892
      /// \brief Constructor to get invalid iterator
alpar@103
   893
      ///
alpar@103
   894
      /// Constructor to get invalid iterator
alpar@103
   895
      ItemIt(Invalid) : extendFind(0), idx(-1) {}
alpar@209
   896
alpar@103
   897
      /// \brief Increment operator
alpar@103
   898
      ///
alpar@103
   899
      /// It steps to the next item in the class.
alpar@103
   900
      ItemIt& operator++() {
alpar@103
   901
        idx = extendFind->items[idx].next;
alpar@209
   902
        if (fdx == idx) idx = -1;
alpar@103
   903
        return *this;
alpar@103
   904
      }
alpar@209
   905
alpar@103
   906
      /// \brief Conversion operator
alpar@103
   907
      ///
alpar@103
   908
      /// It converts the iterator to the current item.
alpar@103
   909
      operator const Item&() const {
alpar@103
   910
        return extendFind->items[idx].item;
alpar@103
   911
      }
alpar@103
   912
alpar@103
   913
      /// \brief Equality operator
alpar@103
   914
      ///
alpar@103
   915
      /// Equality operator
alpar@209
   916
      bool operator==(const ItemIt& i) {
alpar@103
   917
        return i.idx == idx;
alpar@103
   918
      }
alpar@103
   919
alpar@103
   920
      /// \brief Inequality operator
alpar@103
   921
      ///
alpar@103
   922
      /// Inequality operator
alpar@209
   923
      bool operator!=(const ItemIt& i) {
alpar@103
   924
        return i.idx != idx;
alpar@103
   925
      }
alpar@209
   926
alpar@103
   927
    private:
alpar@103
   928
      const ExtendFindEnum* extendFind;
alpar@103
   929
      int idx, fdx;
alpar@103
   930
    };
alpar@103
   931
alpar@103
   932
  };
alpar@103
   933
alpar@103
   934
  /// \ingroup auxdat
alpar@103
   935
  ///
alpar@103
   936
  /// \brief A \e Union-Find data structure implementation which
alpar@103
   937
  /// is able to store a priority for each item and retrieve the minimum of
alpar@103
   938
  /// each class.
alpar@103
   939
  ///
alpar@103
   940
  /// A \e Union-Find data structure implementation which is able to
alpar@103
   941
  /// store a priority for each item and retrieve the minimum of each
alpar@103
   942
  /// class. In addition, it supports the joining and splitting the
alpar@103
   943
  /// components. If you don't need this feature then you makes
alpar@103
   944
  /// better to use the \ref UnionFind class which is more efficient.
alpar@103
   945
  ///
alpar@103
   946
  /// The union-find data strcuture based on a (2, 16)-tree with a
alpar@103
   947
  /// tournament minimum selection on the internal nodes. The insert
alpar@103
   948
  /// operation takes O(1), the find, set, decrease and increase takes
alpar@103
   949
  /// O(log(n)), where n is the number of nodes in the current
alpar@103
   950
  /// component.  The complexity of join and split is O(log(n)*k),
alpar@103
   951
  /// where n is the sum of the number of the nodes and k is the
alpar@103
   952
  /// number of joined components or the number of the components
alpar@103
   953
  /// after the split.
alpar@103
   954
  ///
alpar@103
   955
  /// \pre You need to add all the elements by the \ref insert()
alpar@103
   956
  /// method.
kpeter@559
   957
  template <typename V, typename IM, typename Comp = std::less<V> >
alpar@103
   958
  class HeapUnionFind {
alpar@103
   959
  public:
alpar@209
   960
kpeter@559
   961
    ///\e
kpeter@559
   962
    typedef V Value;
kpeter@559
   963
    ///\e
kpeter@559
   964
    typedef typename IM::Key Item;
kpeter@559
   965
    ///\e
kpeter@559
   966
    typedef IM ItemIntMap;
kpeter@559
   967
    ///\e
kpeter@559
   968
    typedef Comp Compare;
alpar@103
   969
alpar@103
   970
  private:
alpar@103
   971
alpar@103
   972
    static const int cmax = 16;
alpar@103
   973
alpar@103
   974
    ItemIntMap& index;
alpar@103
   975
alpar@103
   976
    struct ClassNode {
alpar@103
   977
      int parent;
alpar@103
   978
      int depth;
alpar@103
   979
alpar@103
   980
      int left, right;
alpar@103
   981
      int next, prev;
alpar@103
   982
    };
alpar@103
   983
alpar@103
   984
    int first_class;
alpar@103
   985
    int first_free_class;
alpar@103
   986
    std::vector<ClassNode> classes;
alpar@103
   987
alpar@103
   988
    int newClass() {
alpar@103
   989
      if (first_free_class < 0) {
alpar@103
   990
        int id = classes.size();
alpar@103
   991
        classes.push_back(ClassNode());
alpar@103
   992
        return id;
alpar@103
   993
      } else {
alpar@103
   994
        int id = first_free_class;
alpar@103
   995
        first_free_class = classes[id].next;
alpar@103
   996
        return id;
alpar@103
   997
      }
alpar@103
   998
    }
alpar@103
   999
alpar@103
  1000
    void deleteClass(int id) {
alpar@103
  1001
      classes[id].next = first_free_class;
alpar@103
  1002
      first_free_class = id;
alpar@103
  1003
    }
alpar@103
  1004
alpar@103
  1005
    struct ItemNode {
alpar@103
  1006
      int parent;
alpar@103
  1007
      Item item;
alpar@103
  1008
      Value prio;
alpar@103
  1009
      int next, prev;
alpar@103
  1010
      int left, right;
alpar@103
  1011
      int size;
alpar@103
  1012
    };
alpar@103
  1013
alpar@103
  1014
    int first_free_node;
alpar@103
  1015
    std::vector<ItemNode> nodes;
alpar@103
  1016
alpar@103
  1017
    int newNode() {
alpar@103
  1018
      if (first_free_node < 0) {
alpar@103
  1019
        int id = nodes.size();
alpar@103
  1020
        nodes.push_back(ItemNode());
alpar@103
  1021
        return id;
alpar@103
  1022
      } else {
alpar@103
  1023
        int id = first_free_node;
alpar@103
  1024
        first_free_node = nodes[id].next;
alpar@103
  1025
        return id;
alpar@103
  1026
      }
alpar@103
  1027
    }
alpar@103
  1028
alpar@103
  1029
    void deleteNode(int id) {
alpar@103
  1030
      nodes[id].next = first_free_node;
alpar@103
  1031
      first_free_node = id;
alpar@103
  1032
    }
alpar@103
  1033
alpar@103
  1034
    Comp comp;
alpar@103
  1035
alpar@103
  1036
    int findClass(int id) const {
alpar@103
  1037
      int kd = id;
alpar@103
  1038
      while (kd >= 0) {
alpar@103
  1039
        kd = nodes[kd].parent;
alpar@103
  1040
      }
alpar@103
  1041
      return ~kd;
alpar@103
  1042
    }
alpar@103
  1043
alpar@103
  1044
    int leftNode(int id) const {
alpar@103
  1045
      int kd = ~(classes[id].parent);
alpar@103
  1046
      for (int i = 0; i < classes[id].depth; ++i) {
alpar@103
  1047
        kd = nodes[kd].left;
alpar@103
  1048
      }
alpar@103
  1049
      return kd;
alpar@103
  1050
    }
alpar@103
  1051
alpar@103
  1052
    int nextNode(int id) const {
alpar@103
  1053
      int depth = 0;
alpar@103
  1054
      while (id >= 0 && nodes[id].next == -1) {
alpar@103
  1055
        id = nodes[id].parent;
alpar@103
  1056
        ++depth;
alpar@103
  1057
      }
alpar@103
  1058
      if (id < 0) {
alpar@103
  1059
        return -1;
alpar@103
  1060
      }
alpar@103
  1061
      id = nodes[id].next;
alpar@103
  1062
      while (depth--) {
alpar@209
  1063
        id = nodes[id].left;
alpar@103
  1064
      }
alpar@103
  1065
      return id;
alpar@103
  1066
    }
alpar@103
  1067
alpar@103
  1068
alpar@103
  1069
    void setPrio(int id) {
alpar@103
  1070
      int jd = nodes[id].left;
alpar@103
  1071
      nodes[id].prio = nodes[jd].prio;
alpar@103
  1072
      nodes[id].item = nodes[jd].item;
alpar@103
  1073
      jd = nodes[jd].next;
alpar@103
  1074
      while (jd != -1) {
alpar@103
  1075
        if (comp(nodes[jd].prio, nodes[id].prio)) {
alpar@103
  1076
          nodes[id].prio = nodes[jd].prio;
alpar@103
  1077
          nodes[id].item = nodes[jd].item;
alpar@103
  1078
        }
alpar@103
  1079
        jd = nodes[jd].next;
alpar@103
  1080
      }
alpar@103
  1081
    }
alpar@103
  1082
alpar@103
  1083
    void push(int id, int jd) {
alpar@103
  1084
      nodes[id].size = 1;
alpar@103
  1085
      nodes[id].left = nodes[id].right = jd;
alpar@103
  1086
      nodes[jd].next = nodes[jd].prev = -1;
alpar@103
  1087
      nodes[jd].parent = id;
alpar@103
  1088
    }
alpar@103
  1089
alpar@103
  1090
    void pushAfter(int id, int jd) {
alpar@103
  1091
      int kd = nodes[id].parent;
alpar@103
  1092
      if (nodes[id].next != -1) {
alpar@103
  1093
        nodes[nodes[id].next].prev = jd;
alpar@103
  1094
        if (kd >= 0) {
alpar@103
  1095
          nodes[kd].size += 1;
alpar@103
  1096
        }
alpar@103
  1097
      } else {
alpar@103
  1098
        if (kd >= 0) {
alpar@103
  1099
          nodes[kd].right = jd;
alpar@103
  1100
          nodes[kd].size += 1;
alpar@103
  1101
        }
alpar@103
  1102
      }
alpar@103
  1103
      nodes[jd].next = nodes[id].next;
alpar@103
  1104
      nodes[jd].prev = id;
alpar@103
  1105
      nodes[id].next = jd;
alpar@103
  1106
      nodes[jd].parent = kd;
alpar@103
  1107
    }
alpar@103
  1108
alpar@103
  1109
    void pushRight(int id, int jd) {
alpar@103
  1110
      nodes[id].size += 1;
alpar@103
  1111
      nodes[jd].prev = nodes[id].right;
alpar@103
  1112
      nodes[jd].next = -1;
alpar@103
  1113
      nodes[nodes[id].right].next = jd;
alpar@103
  1114
      nodes[id].right = jd;
alpar@103
  1115
      nodes[jd].parent = id;
alpar@103
  1116
    }
alpar@103
  1117
alpar@103
  1118
    void popRight(int id) {
alpar@103
  1119
      nodes[id].size -= 1;
alpar@103
  1120
      int jd = nodes[id].right;
alpar@103
  1121
      nodes[nodes[jd].prev].next = -1;
alpar@103
  1122
      nodes[id].right = nodes[jd].prev;
alpar@103
  1123
    }
alpar@103
  1124
alpar@103
  1125
    void splice(int id, int jd) {
alpar@103
  1126
      nodes[id].size += nodes[jd].size;
alpar@103
  1127
      nodes[nodes[id].right].next = nodes[jd].left;
alpar@103
  1128
      nodes[nodes[jd].left].prev = nodes[id].right;
alpar@103
  1129
      int kd = nodes[jd].left;
alpar@103
  1130
      while (kd != -1) {
alpar@103
  1131
        nodes[kd].parent = id;
alpar@103
  1132
        kd = nodes[kd].next;
alpar@103
  1133
      }
alpar@103
  1134
      nodes[id].right = nodes[jd].right;
alpar@103
  1135
    }
alpar@103
  1136
alpar@103
  1137
    void split(int id, int jd) {
alpar@103
  1138
      int kd = nodes[id].parent;
alpar@103
  1139
      nodes[kd].right = nodes[id].prev;
alpar@103
  1140
      nodes[nodes[id].prev].next = -1;
alpar@209
  1141
alpar@103
  1142
      nodes[jd].left = id;
alpar@103
  1143
      nodes[id].prev = -1;
alpar@103
  1144
      int num = 0;
alpar@103
  1145
      while (id != -1) {
alpar@103
  1146
        nodes[id].parent = jd;
alpar@103
  1147
        nodes[jd].right = id;
alpar@103
  1148
        id = nodes[id].next;
alpar@103
  1149
        ++num;
alpar@209
  1150
      }
alpar@103
  1151
      nodes[kd].size -= num;
alpar@103
  1152
      nodes[jd].size = num;
alpar@103
  1153
    }
alpar@103
  1154
alpar@103
  1155
    void pushLeft(int id, int jd) {
alpar@103
  1156
      nodes[id].size += 1;
alpar@103
  1157
      nodes[jd].next = nodes[id].left;
alpar@103
  1158
      nodes[jd].prev = -1;
alpar@103
  1159
      nodes[nodes[id].left].prev = jd;
alpar@103
  1160
      nodes[id].left = jd;
alpar@103
  1161
      nodes[jd].parent = id;
alpar@103
  1162
    }
alpar@103
  1163
alpar@103
  1164
    void popLeft(int id) {
alpar@103
  1165
      nodes[id].size -= 1;
alpar@103
  1166
      int jd = nodes[id].left;
alpar@103
  1167
      nodes[nodes[jd].next].prev = -1;
alpar@103
  1168
      nodes[id].left = nodes[jd].next;
alpar@103
  1169
    }
alpar@103
  1170
alpar@103
  1171
    void repairLeft(int id) {
alpar@103
  1172
      int jd = ~(classes[id].parent);
alpar@103
  1173
      while (nodes[jd].left != -1) {
alpar@209
  1174
        int kd = nodes[jd].left;
alpar@209
  1175
        if (nodes[jd].size == 1) {
alpar@209
  1176
          if (nodes[jd].parent < 0) {
alpar@209
  1177
            classes[id].parent = ~kd;
alpar@209
  1178
            classes[id].depth -= 1;
alpar@209
  1179
            nodes[kd].parent = ~id;
alpar@209
  1180
            deleteNode(jd);
alpar@209
  1181
            jd = kd;
alpar@209
  1182
          } else {
alpar@209
  1183
            int pd = nodes[jd].parent;
alpar@209
  1184
            if (nodes[nodes[jd].next].size < cmax) {
alpar@209
  1185
              pushLeft(nodes[jd].next, nodes[jd].left);
deba@438
  1186
              if (less(jd, nodes[jd].next) ||
deba@438
  1187
                  nodes[jd].item == nodes[pd].item) {
deba@436
  1188
                nodes[nodes[jd].next].prio = nodes[jd].prio;
deba@436
  1189
                nodes[nodes[jd].next].item = nodes[jd].item;
alpar@209
  1190
              }
alpar@209
  1191
              popLeft(pd);
alpar@209
  1192
              deleteNode(jd);
alpar@209
  1193
              jd = pd;
alpar@209
  1194
            } else {
alpar@209
  1195
              int ld = nodes[nodes[jd].next].left;
alpar@209
  1196
              popLeft(nodes[jd].next);
alpar@209
  1197
              pushRight(jd, ld);
alpar@440
  1198
              if (less(ld, nodes[jd].left) ||
deba@436
  1199
                  nodes[ld].item == nodes[pd].item) {
alpar@209
  1200
                nodes[jd].item = nodes[ld].item;
deba@436
  1201
                nodes[jd].prio = nodes[ld].prio;
alpar@209
  1202
              }
alpar@209
  1203
              if (nodes[nodes[jd].next].item == nodes[ld].item) {
alpar@209
  1204
                setPrio(nodes[jd].next);
alpar@209
  1205
              }
alpar@209
  1206
              jd = nodes[jd].left;
alpar@209
  1207
            }
alpar@209
  1208
          }
alpar@209
  1209
        } else {
alpar@209
  1210
          jd = nodes[jd].left;
alpar@209
  1211
        }
alpar@103
  1212
      }
alpar@209
  1213
    }
alpar@103
  1214
alpar@103
  1215
    void repairRight(int id) {
alpar@103
  1216
      int jd = ~(classes[id].parent);
alpar@103
  1217
      while (nodes[jd].right != -1) {
alpar@209
  1218
        int kd = nodes[jd].right;
alpar@209
  1219
        if (nodes[jd].size == 1) {
alpar@209
  1220
          if (nodes[jd].parent < 0) {
alpar@209
  1221
            classes[id].parent = ~kd;
alpar@209
  1222
            classes[id].depth -= 1;
alpar@209
  1223
            nodes[kd].parent = ~id;
alpar@209
  1224
            deleteNode(jd);
alpar@209
  1225
            jd = kd;
alpar@209
  1226
          } else {
alpar@209
  1227
            int pd = nodes[jd].parent;
alpar@209
  1228
            if (nodes[nodes[jd].prev].size < cmax) {
alpar@209
  1229
              pushRight(nodes[jd].prev, nodes[jd].right);
deba@438
  1230
              if (less(jd, nodes[jd].prev) ||
deba@438
  1231
                  nodes[jd].item == nodes[pd].item) {
deba@436
  1232
                nodes[nodes[jd].prev].prio = nodes[jd].prio;
deba@436
  1233
                nodes[nodes[jd].prev].item = nodes[jd].item;
alpar@209
  1234
              }
alpar@209
  1235
              popRight(pd);
alpar@209
  1236
              deleteNode(jd);
alpar@209
  1237
              jd = pd;
alpar@209
  1238
            } else {
alpar@209
  1239
              int ld = nodes[nodes[jd].prev].right;
alpar@209
  1240
              popRight(nodes[jd].prev);
alpar@209
  1241
              pushLeft(jd, ld);
deba@436
  1242
              if (less(ld, nodes[jd].right) ||
deba@436
  1243
                  nodes[ld].item == nodes[pd].item) {
alpar@209
  1244
                nodes[jd].item = nodes[ld].item;
deba@436
  1245
                nodes[jd].prio = nodes[ld].prio;
alpar@209
  1246
              }
alpar@209
  1247
              if (nodes[nodes[jd].prev].item == nodes[ld].item) {
alpar@209
  1248
                setPrio(nodes[jd].prev);
alpar@209
  1249
              }
alpar@209
  1250
              jd = nodes[jd].right;
alpar@209
  1251
            }
alpar@209
  1252
          }
alpar@209
  1253
        } else {
alpar@209
  1254
          jd = nodes[jd].right;
alpar@209
  1255
        }
alpar@103
  1256
      }
alpar@103
  1257
    }
alpar@103
  1258
alpar@103
  1259
alpar@103
  1260
    bool less(int id, int jd) const {
alpar@103
  1261
      return comp(nodes[id].prio, nodes[jd].prio);
alpar@103
  1262
    }
alpar@103
  1263
alpar@103
  1264
  public:
alpar@103
  1265
alpar@103
  1266
    /// \brief Returns true when the given class is alive.
alpar@103
  1267
    ///
alpar@103
  1268
    /// Returns true when the given class is alive, ie. the class is
alpar@103
  1269
    /// not nested into other class.
alpar@103
  1270
    bool alive(int cls) const {
alpar@103
  1271
      return classes[cls].parent < 0;
alpar@103
  1272
    }
alpar@103
  1273
alpar@103
  1274
    /// \brief Returns true when the given class is trivial.
alpar@103
  1275
    ///
alpar@103
  1276
    /// Returns true when the given class is trivial, ie. the class
alpar@103
  1277
    /// contains just one item directly.
alpar@103
  1278
    bool trivial(int cls) const {
alpar@103
  1279
      return classes[cls].left == -1;
alpar@103
  1280
    }
alpar@103
  1281
alpar@103
  1282
    /// \brief Constructs the union-find.
alpar@103
  1283
    ///
alpar@209
  1284
    /// Constructs the union-find.
alpar@103
  1285
    /// \brief _index The index map of the union-find. The data
alpar@103
  1286
    /// structure uses internally for store references.
alpar@209
  1287
    HeapUnionFind(ItemIntMap& _index)
alpar@209
  1288
      : index(_index), first_class(-1),
alpar@209
  1289
        first_free_class(-1), first_free_node(-1) {}
alpar@103
  1290
deba@867
  1291
    /// \brief Clears the union-find data structure
deba@867
  1292
    ///
deba@867
  1293
    /// Erase each item from the data structure.
deba@867
  1294
    void clear() {
deba@867
  1295
      nodes.clear();
deba@867
  1296
      classes.clear();
deba@867
  1297
      first_free_node = first_free_class = first_class = -1;
deba@867
  1298
    }
deba@867
  1299
alpar@103
  1300
    /// \brief Insert a new node into a new component.
alpar@103
  1301
    ///
alpar@103
  1302
    /// Insert a new node into a new component.
alpar@103
  1303
    /// \param item The item of the new node.
alpar@103
  1304
    /// \param prio The priority of the new node.
alpar@103
  1305
    /// \return The class id of the one-item-heap.
alpar@103
  1306
    int insert(const Item& item, const Value& prio) {
alpar@103
  1307
      int id = newNode();
alpar@103
  1308
      nodes[id].item = item;
alpar@103
  1309
      nodes[id].prio = prio;
alpar@103
  1310
      nodes[id].size = 0;
alpar@103
  1311
alpar@103
  1312
      nodes[id].prev = -1;
alpar@103
  1313
      nodes[id].next = -1;
alpar@103
  1314
alpar@103
  1315
      nodes[id].left = -1;
alpar@103
  1316
      nodes[id].right = -1;
alpar@103
  1317
alpar@103
  1318
      nodes[id].item = item;
alpar@103
  1319
      index[item] = id;
alpar@209
  1320
alpar@103
  1321
      int class_id = newClass();
alpar@103
  1322
      classes[class_id].parent = ~id;
alpar@103
  1323
      classes[class_id].depth = 0;
alpar@103
  1324
alpar@103
  1325
      classes[class_id].left = -1;
alpar@103
  1326
      classes[class_id].right = -1;
alpar@209
  1327
alpar@103
  1328
      if (first_class != -1) {
alpar@103
  1329
        classes[first_class].prev = class_id;
alpar@103
  1330
      }
alpar@103
  1331
      classes[class_id].next = first_class;
alpar@103
  1332
      classes[class_id].prev = -1;
alpar@103
  1333
      first_class = class_id;
alpar@103
  1334
alpar@103
  1335
      nodes[id].parent = ~class_id;
alpar@209
  1336
alpar@103
  1337
      return class_id;
alpar@103
  1338
    }
alpar@103
  1339
alpar@103
  1340
    /// \brief The class of the item.
alpar@103
  1341
    ///
alpar@103
  1342
    /// \return The alive class id of the item, which is not nested into
alpar@103
  1343
    /// other classes.
alpar@103
  1344
    ///
alpar@103
  1345
    /// The time complexity is O(log(n)).
alpar@103
  1346
    int find(const Item& item) const {
alpar@103
  1347
      return findClass(index[item]);
alpar@103
  1348
    }
alpar@209
  1349
alpar@103
  1350
    /// \brief Joins the classes.
alpar@103
  1351
    ///
alpar@103
  1352
    /// The current function joins the given classes. The parameter is
alpar@103
  1353
    /// an STL range which should be contains valid class ids. The
alpar@103
  1354
    /// time complexity is O(log(n)*k) where n is the overall number
alpar@103
  1355
    /// of the joined nodes and k is the number of classes.
alpar@103
  1356
    /// \return The class of the joined classes.
alpar@103
  1357
    /// \pre The range should contain at least two class ids.
alpar@103
  1358
    template <typename Iterator>
alpar@103
  1359
    int join(Iterator begin, Iterator end) {
alpar@103
  1360
      std::vector<int> cs;
alpar@103
  1361
      for (Iterator it = begin; it != end; ++it) {
alpar@103
  1362
        cs.push_back(*it);
alpar@103
  1363
      }
alpar@103
  1364
alpar@103
  1365
      int class_id = newClass();
alpar@103
  1366
      { // creation union-find
alpar@103
  1367
alpar@103
  1368
        if (first_class != -1) {
alpar@103
  1369
          classes[first_class].prev = class_id;
alpar@103
  1370
        }
alpar@103
  1371
        classes[class_id].next = first_class;
alpar@103
  1372
        classes[class_id].prev = -1;
alpar@103
  1373
        first_class = class_id;
alpar@103
  1374
alpar@103
  1375
        classes[class_id].depth = classes[cs[0]].depth;
alpar@103
  1376
        classes[class_id].parent = classes[cs[0]].parent;
alpar@103
  1377
        nodes[~(classes[class_id].parent)].parent = ~class_id;
alpar@103
  1378
alpar@103
  1379
        int l = cs[0];
alpar@103
  1380
alpar@103
  1381
        classes[class_id].left = l;
alpar@103
  1382
        classes[class_id].right = l;
alpar@103
  1383
alpar@103
  1384
        if (classes[l].next != -1) {
alpar@103
  1385
          classes[classes[l].next].prev = classes[l].prev;
alpar@103
  1386
        }
alpar@103
  1387
        classes[classes[l].prev].next = classes[l].next;
alpar@209
  1388
alpar@103
  1389
        classes[l].prev = -1;
alpar@103
  1390
        classes[l].next = -1;
alpar@103
  1391
alpar@103
  1392
        classes[l].depth = leftNode(l);
alpar@103
  1393
        classes[l].parent = class_id;
alpar@209
  1394
alpar@103
  1395
      }
alpar@103
  1396
alpar@103
  1397
      { // merging of heap
alpar@103
  1398
        int l = class_id;
alpar@103
  1399
        for (int ci = 1; ci < int(cs.size()); ++ci) {
alpar@103
  1400
          int r = cs[ci];
alpar@103
  1401
          int rln = leftNode(r);
alpar@103
  1402
          if (classes[l].depth > classes[r].depth) {
alpar@103
  1403
            int id = ~(classes[l].parent);
alpar@103
  1404
            for (int i = classes[r].depth + 1; i < classes[l].depth; ++i) {
alpar@103
  1405
              id = nodes[id].right;
alpar@103
  1406
            }
alpar@103
  1407
            while (id >= 0 && nodes[id].size == cmax) {
alpar@103
  1408
              int new_id = newNode();
alpar@103
  1409
              int right_id = nodes[id].right;
alpar@103
  1410
alpar@103
  1411
              popRight(id);
alpar@103
  1412
              if (nodes[id].item == nodes[right_id].item) {
alpar@103
  1413
                setPrio(id);
alpar@103
  1414
              }
alpar@103
  1415
              push(new_id, right_id);
alpar@103
  1416
              pushRight(new_id, ~(classes[r].parent));
deba@436
  1417
deba@436
  1418
              if (less(~classes[r].parent, right_id)) {
deba@436
  1419
                nodes[new_id].item = nodes[~classes[r].parent].item;
deba@436
  1420
                nodes[new_id].prio = nodes[~classes[r].parent].prio;
deba@436
  1421
              } else {
deba@436
  1422
                nodes[new_id].item = nodes[right_id].item;
deba@436
  1423
                nodes[new_id].prio = nodes[right_id].prio;
deba@436
  1424
              }
alpar@103
  1425
alpar@103
  1426
              id = nodes[id].parent;
alpar@103
  1427
              classes[r].parent = ~new_id;
alpar@103
  1428
            }
alpar@103
  1429
            if (id < 0) {
alpar@103
  1430
              int new_parent = newNode();
alpar@103
  1431
              nodes[new_parent].next = -1;
alpar@103
  1432
              nodes[new_parent].prev = -1;
alpar@103
  1433
              nodes[new_parent].parent = ~l;
alpar@103
  1434
alpar@103
  1435
              push(new_parent, ~(classes[l].parent));
alpar@103
  1436
              pushRight(new_parent, ~(classes[r].parent));
alpar@103
  1437
              setPrio(new_parent);
alpar@103
  1438
alpar@103
  1439
              classes[l].parent = ~new_parent;
alpar@103
  1440
              classes[l].depth += 1;
alpar@103
  1441
            } else {
alpar@103
  1442
              pushRight(id, ~(classes[r].parent));
alpar@103
  1443
              while (id >= 0 && less(~(classes[r].parent), id)) {
alpar@103
  1444
                nodes[id].prio = nodes[~(classes[r].parent)].prio;
alpar@103
  1445
                nodes[id].item = nodes[~(classes[r].parent)].item;
alpar@103
  1446
                id = nodes[id].parent;
alpar@103
  1447
              }
alpar@103
  1448
            }
alpar@103
  1449
          } else if (classes[r].depth > classes[l].depth) {
alpar@103
  1450
            int id = ~(classes[r].parent);
alpar@103
  1451
            for (int i = classes[l].depth + 1; i < classes[r].depth; ++i) {
alpar@103
  1452
              id = nodes[id].left;
alpar@103
  1453
            }
alpar@103
  1454
            while (id >= 0 && nodes[id].size == cmax) {
alpar@103
  1455
              int new_id = newNode();
alpar@103
  1456
              int left_id = nodes[id].left;
alpar@103
  1457
alpar@103
  1458
              popLeft(id);
alpar@103
  1459
              if (nodes[id].prio == nodes[left_id].prio) {
alpar@103
  1460
                setPrio(id);
alpar@103
  1461
              }
alpar@103
  1462
              push(new_id, left_id);
alpar@103
  1463
              pushLeft(new_id, ~(classes[l].parent));
deba@436
  1464
deba@436
  1465
              if (less(~classes[l].parent, left_id)) {
deba@436
  1466
                nodes[new_id].item = nodes[~classes[l].parent].item;
deba@436
  1467
                nodes[new_id].prio = nodes[~classes[l].parent].prio;
deba@436
  1468
              } else {
deba@436
  1469
                nodes[new_id].item = nodes[left_id].item;
deba@436
  1470
                nodes[new_id].prio = nodes[left_id].prio;
deba@436
  1471
              }
alpar@103
  1472
alpar@103
  1473
              id = nodes[id].parent;
alpar@103
  1474
              classes[l].parent = ~new_id;
alpar@103
  1475
alpar@103
  1476
            }
alpar@103
  1477
            if (id < 0) {
alpar@103
  1478
              int new_parent = newNode();
alpar@103
  1479
              nodes[new_parent].next = -1;
alpar@103
  1480
              nodes[new_parent].prev = -1;
alpar@103
  1481
              nodes[new_parent].parent = ~l;
alpar@103
  1482
alpar@103
  1483
              push(new_parent, ~(classes[r].parent));
alpar@103
  1484
              pushLeft(new_parent, ~(classes[l].parent));
alpar@103
  1485
              setPrio(new_parent);
alpar@209
  1486
alpar@103
  1487
              classes[r].parent = ~new_parent;
alpar@103
  1488
              classes[r].depth += 1;
alpar@103
  1489
            } else {
alpar@103
  1490
              pushLeft(id, ~(classes[l].parent));
alpar@103
  1491
              while (id >= 0 && less(~(classes[l].parent), id)) {
alpar@103
  1492
                nodes[id].prio = nodes[~(classes[l].parent)].prio;
alpar@103
  1493
                nodes[id].item = nodes[~(classes[l].parent)].item;
alpar@103
  1494
                id = nodes[id].parent;
alpar@103
  1495
              }
alpar@103
  1496
            }
alpar@103
  1497
            nodes[~(classes[r].parent)].parent = ~l;
alpar@103
  1498
            classes[l].parent = classes[r].parent;
alpar@103
  1499
            classes[l].depth = classes[r].depth;
alpar@103
  1500
          } else {
alpar@209
  1501
            if (classes[l].depth != 0 &&
alpar@209
  1502
                nodes[~(classes[l].parent)].size +
alpar@103
  1503
                nodes[~(classes[r].parent)].size <= cmax) {
alpar@103
  1504
              splice(~(classes[l].parent), ~(classes[r].parent));
alpar@103
  1505
              deleteNode(~(classes[r].parent));
alpar@103
  1506
              if (less(~(classes[r].parent), ~(classes[l].parent))) {
alpar@209
  1507
                nodes[~(classes[l].parent)].prio =
alpar@103
  1508
                  nodes[~(classes[r].parent)].prio;
alpar@209
  1509
                nodes[~(classes[l].parent)].item =
alpar@103
  1510
                  nodes[~(classes[r].parent)].item;
alpar@103
  1511
              }
alpar@103
  1512
            } else {
alpar@103
  1513
              int new_parent = newNode();
alpar@103
  1514
              nodes[new_parent].next = nodes[new_parent].prev = -1;
alpar@103
  1515
              push(new_parent, ~(classes[l].parent));
alpar@103
  1516
              pushRight(new_parent, ~(classes[r].parent));
alpar@103
  1517
              setPrio(new_parent);
alpar@209
  1518
alpar@103
  1519
              classes[l].parent = ~new_parent;
alpar@103
  1520
              classes[l].depth += 1;
alpar@103
  1521
              nodes[new_parent].parent = ~l;
alpar@103
  1522
            }
alpar@103
  1523
          }
alpar@103
  1524
          if (classes[r].next != -1) {
alpar@103
  1525
            classes[classes[r].next].prev = classes[r].prev;
alpar@103
  1526
          }
alpar@103
  1527
          classes[classes[r].prev].next = classes[r].next;
alpar@103
  1528
alpar@103
  1529
          classes[r].prev = classes[l].right;
alpar@103
  1530
          classes[classes[l].right].next = r;
alpar@103
  1531
          classes[l].right = r;
alpar@103
  1532
          classes[r].parent = l;
alpar@103
  1533
alpar@103
  1534
          classes[r].next = -1;
alpar@103
  1535
          classes[r].depth = rln;
alpar@103
  1536
        }
alpar@103
  1537
      }
alpar@103
  1538
      return class_id;
alpar@103
  1539
    }
alpar@103
  1540
alpar@103
  1541
    /// \brief Split the class to subclasses.
alpar@103
  1542
    ///
alpar@103
  1543
    /// The current function splits the given class. The join, which
alpar@103
  1544
    /// made the current class, stored a reference to the
alpar@103
  1545
    /// subclasses. The \c splitClass() member restores the classes
alpar@103
  1546
    /// and creates the heaps. The parameter is an STL output iterator
alpar@103
  1547
    /// which will be filled with the subclass ids. The time
alpar@103
  1548
    /// complexity is O(log(n)*k) where n is the overall number of
alpar@103
  1549
    /// nodes in the splitted classes and k is the number of the
alpar@103
  1550
    /// classes.
alpar@103
  1551
    template <typename Iterator>
alpar@103
  1552
    void split(int cls, Iterator out) {
alpar@103
  1553
      std::vector<int> cs;
alpar@103
  1554
      { // splitting union-find
alpar@103
  1555
        int id = cls;
alpar@103
  1556
        int l = classes[id].left;
alpar@103
  1557
alpar@103
  1558
        classes[l].parent = classes[id].parent;
alpar@103
  1559
        classes[l].depth = classes[id].depth;
alpar@103
  1560
alpar@103
  1561
        nodes[~(classes[l].parent)].parent = ~l;
alpar@103
  1562
alpar@103
  1563
        *out++ = l;
alpar@103
  1564
alpar@103
  1565
        while (l != -1) {
alpar@103
  1566
          cs.push_back(l);
alpar@103
  1567
          l = classes[l].next;
alpar@103
  1568
        }
alpar@103
  1569
alpar@103
  1570
        classes[classes[id].right].next = first_class;
alpar@103
  1571
        classes[first_class].prev = classes[id].right;
alpar@103
  1572
        first_class = classes[id].left;
alpar@209
  1573
alpar@103
  1574
        if (classes[id].next != -1) {
alpar@103
  1575
          classes[classes[id].next].prev = classes[id].prev;
alpar@103
  1576
        }
alpar@103
  1577
        classes[classes[id].prev].next = classes[id].next;
alpar@209
  1578
alpar@103
  1579
        deleteClass(id);
alpar@103
  1580
      }
alpar@103
  1581
alpar@103
  1582
      {
alpar@103
  1583
        for (int i = 1; i < int(cs.size()); ++i) {
alpar@103
  1584
          int l = classes[cs[i]].depth;
alpar@103
  1585
          while (nodes[nodes[l].parent].left == l) {
alpar@103
  1586
            l = nodes[l].parent;
alpar@103
  1587
          }
alpar@209
  1588
          int r = l;
alpar@103
  1589
          while (nodes[l].parent >= 0) {
alpar@103
  1590
            l = nodes[l].parent;
alpar@103
  1591
            int new_node = newNode();
alpar@103
  1592
alpar@103
  1593
            nodes[new_node].prev = -1;
alpar@103
  1594
            nodes[new_node].next = -1;
alpar@103
  1595
alpar@103
  1596
            split(r, new_node);
alpar@103
  1597
            pushAfter(l, new_node);
alpar@103
  1598
            setPrio(l);
alpar@103
  1599
            setPrio(new_node);
alpar@103
  1600
            r = new_node;
alpar@103
  1601
          }
alpar@103
  1602
          classes[cs[i]].parent = ~r;
alpar@103
  1603
          classes[cs[i]].depth = classes[~(nodes[l].parent)].depth;
alpar@103
  1604
          nodes[r].parent = ~cs[i];
alpar@103
  1605
alpar@103
  1606
          nodes[l].next = -1;
alpar@103
  1607
          nodes[r].prev = -1;
alpar@103
  1608
alpar@103
  1609
          repairRight(~(nodes[l].parent));
alpar@103
  1610
          repairLeft(cs[i]);
alpar@209
  1611
alpar@103
  1612
          *out++ = cs[i];
alpar@103
  1613
        }
alpar@103
  1614
      }
alpar@103
  1615
    }
alpar@103
  1616
alpar@103
  1617
    /// \brief Gives back the priority of the current item.
alpar@103
  1618
    ///
kpeter@559
  1619
    /// Gives back the priority of the current item.
alpar@103
  1620
    const Value& operator[](const Item& item) const {
alpar@103
  1621
      return nodes[index[item]].prio;
alpar@103
  1622
    }
alpar@103
  1623
alpar@103
  1624
    /// \brief Sets the priority of the current item.
alpar@103
  1625
    ///
alpar@103
  1626
    /// Sets the priority of the current item.
alpar@103
  1627
    void set(const Item& item, const Value& prio) {
alpar@103
  1628
      if (comp(prio, nodes[index[item]].prio)) {
alpar@103
  1629
        decrease(item, prio);
alpar@103
  1630
      } else if (!comp(prio, nodes[index[item]].prio)) {
alpar@103
  1631
        increase(item, prio);
alpar@103
  1632
      }
alpar@103
  1633
    }
alpar@209
  1634
alpar@103
  1635
    /// \brief Increase the priority of the current item.
alpar@103
  1636
    ///
alpar@103
  1637
    /// Increase the priority of the current item.
alpar@103
  1638
    void increase(const Item& item, const Value& prio) {
alpar@103
  1639
      int id = index[item];
alpar@103
  1640
      int kd = nodes[id].parent;
alpar@103
  1641
      nodes[id].prio = prio;
alpar@103
  1642
      while (kd >= 0 && nodes[kd].item == item) {
alpar@103
  1643
        setPrio(kd);
alpar@103
  1644
        kd = nodes[kd].parent;
alpar@103
  1645
      }
alpar@103
  1646
    }
alpar@103
  1647
alpar@103
  1648
    /// \brief Increase the priority of the current item.
alpar@103
  1649
    ///
alpar@103
  1650
    /// Increase the priority of the current item.
alpar@103
  1651
    void decrease(const Item& item, const Value& prio) {
alpar@103
  1652
      int id = index[item];
alpar@103
  1653
      int kd = nodes[id].parent;
alpar@103
  1654
      nodes[id].prio = prio;
alpar@103
  1655
      while (kd >= 0 && less(id, kd)) {
alpar@103
  1656
        nodes[kd].prio = prio;
alpar@103
  1657
        nodes[kd].item = item;
alpar@103
  1658
        kd = nodes[kd].parent;
alpar@103
  1659
      }
alpar@103
  1660
    }
alpar@209
  1661
alpar@103
  1662
    /// \brief Gives back the minimum priority of the class.
alpar@103
  1663
    ///
kpeter@559
  1664
    /// Gives back the minimum priority of the class.
alpar@103
  1665
    const Value& classPrio(int cls) const {
alpar@103
  1666
      return nodes[~(classes[cls].parent)].prio;
alpar@103
  1667
    }
alpar@103
  1668
alpar@103
  1669
    /// \brief Gives back the minimum priority item of the class.
alpar@103
  1670
    ///
alpar@103
  1671
    /// \return Gives back the minimum priority item of the class.
alpar@103
  1672
    const Item& classTop(int cls) const {
alpar@103
  1673
      return nodes[~(classes[cls].parent)].item;
alpar@103
  1674
    }
alpar@103
  1675
alpar@103
  1676
    /// \brief Gives back a representant item of the class.
alpar@209
  1677
    ///
kpeter@559
  1678
    /// Gives back a representant item of the class.
alpar@103
  1679
    /// The representant is indpendent from the priorities of the
alpar@209
  1680
    /// items.
alpar@103
  1681
    const Item& classRep(int id) const {
alpar@103
  1682
      int parent = classes[id].parent;
alpar@103
  1683
      return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;
alpar@103
  1684
    }
alpar@103
  1685
ladanyi@236
  1686
    /// \brief LEMON style iterator for the items of a class.
alpar@103
  1687
    ///
alpar@103
  1688
    /// ClassIt is a lemon style iterator for the components. It iterates
alpar@103
  1689
    /// on the items of a class. By example if you want to iterate on
alpar@103
  1690
    /// each items of each classes then you may write the next code.
alpar@103
  1691
    ///\code
alpar@103
  1692
    /// for (ClassIt cit(huf); cit != INVALID; ++cit) {
alpar@103
  1693
    ///   std::cout << "Class: ";
alpar@103
  1694
    ///   for (ItemIt iit(huf, cit); iit != INVALID; ++iit) {
alpar@103
  1695
    ///     std::cout << toString(iit) << ' ' << std::endl;
alpar@103
  1696
    ///   }
alpar@103
  1697
    ///   std::cout << std::endl;
alpar@103
  1698
    /// }
alpar@103
  1699
    ///\endcode
alpar@103
  1700
    class ItemIt {
alpar@103
  1701
    private:
alpar@103
  1702
alpar@103
  1703
      const HeapUnionFind* _huf;
alpar@103
  1704
      int _id, _lid;
alpar@209
  1705
alpar@103
  1706
    public:
alpar@103
  1707
alpar@209
  1708
      /// \brief Default constructor
alpar@103
  1709
      ///
alpar@209
  1710
      /// Default constructor
alpar@103
  1711
      ItemIt() {}
alpar@103
  1712
alpar@103
  1713
      ItemIt(const HeapUnionFind& huf, int cls) : _huf(&huf) {
alpar@103
  1714
        int id = cls;
alpar@103
  1715
        int parent = _huf->classes[id].parent;
alpar@103
  1716
        if (parent >= 0) {
alpar@103
  1717
          _id = _huf->classes[id].depth;
alpar@103
  1718
          if (_huf->classes[id].next != -1) {
alpar@103
  1719
            _lid = _huf->classes[_huf->classes[id].next].depth;
alpar@103
  1720
          } else {
alpar@103
  1721
            _lid = -1;
alpar@103
  1722
          }
alpar@103
  1723
        } else {
alpar@103
  1724
          _id = _huf->leftNode(id);
alpar@103
  1725
          _lid = -1;
alpar@209
  1726
        }
alpar@103
  1727
      }
alpar@209
  1728
alpar@103
  1729
      /// \brief Increment operator
alpar@103
  1730
      ///
alpar@103
  1731
      /// It steps to the next item in the class.
alpar@103
  1732
      ItemIt& operator++() {
alpar@103
  1733
        _id = _huf->nextNode(_id);
alpar@103
  1734
        return *this;
alpar@103
  1735
      }
alpar@103
  1736
alpar@103
  1737
      /// \brief Conversion operator
alpar@103
  1738
      ///
alpar@103
  1739
      /// It converts the iterator to the current item.
alpar@103
  1740
      operator const Item&() const {
alpar@103
  1741
        return _huf->nodes[_id].item;
alpar@103
  1742
      }
alpar@209
  1743
alpar@103
  1744
      /// \brief Equality operator
alpar@103
  1745
      ///
alpar@103
  1746
      /// Equality operator
alpar@209
  1747
      bool operator==(const ItemIt& i) {
alpar@103
  1748
        return i._id == _id;
alpar@103
  1749
      }
alpar@103
  1750
alpar@103
  1751
      /// \brief Inequality operator
alpar@103
  1752
      ///
alpar@103
  1753
      /// Inequality operator
alpar@209
  1754
      bool operator!=(const ItemIt& i) {
alpar@103
  1755
        return i._id != _id;
alpar@103
  1756
      }
alpar@103
  1757
alpar@103
  1758
      /// \brief Equality operator
alpar@103
  1759
      ///
alpar@103
  1760
      /// Equality operator
alpar@209
  1761
      bool operator==(Invalid) {
alpar@103
  1762
        return _id == _lid;
alpar@103
  1763
      }
alpar@103
  1764
alpar@103
  1765
      /// \brief Inequality operator
alpar@103
  1766
      ///
alpar@103
  1767
      /// Inequality operator
alpar@209
  1768
      bool operator!=(Invalid) {
alpar@103
  1769
        return _id != _lid;
alpar@103
  1770
      }
alpar@209
  1771
alpar@103
  1772
    };
alpar@103
  1773
alpar@103
  1774
    /// \brief Class iterator
alpar@103
  1775
    ///
alpar@209
  1776
    /// The iterator stores
alpar@103
  1777
    class ClassIt {
alpar@103
  1778
    private:
alpar@103
  1779
alpar@103
  1780
      const HeapUnionFind* _huf;
alpar@103
  1781
      int _id;
alpar@103
  1782
alpar@103
  1783
    public:
alpar@103
  1784
alpar@209
  1785
      ClassIt(const HeapUnionFind& huf)
alpar@103
  1786
        : _huf(&huf), _id(huf.first_class) {}
alpar@103
  1787
alpar@209
  1788
      ClassIt(const HeapUnionFind& huf, int cls)
alpar@103
  1789
        : _huf(&huf), _id(huf.classes[cls].left) {}
alpar@103
  1790
alpar@103
  1791
      ClassIt(Invalid) : _huf(0), _id(-1) {}
alpar@209
  1792
alpar@103
  1793
      const ClassIt& operator++() {
alpar@103
  1794
        _id = _huf->classes[_id].next;
alpar@209
  1795
        return *this;
alpar@103
  1796
      }
alpar@103
  1797
alpar@103
  1798
      /// \brief Equality operator
alpar@103
  1799
      ///
alpar@103
  1800
      /// Equality operator
alpar@209
  1801
      bool operator==(const ClassIt& i) {
alpar@103
  1802
        return i._id == _id;
alpar@103
  1803
      }
alpar@103
  1804
alpar@103
  1805
      /// \brief Inequality operator
alpar@103
  1806
      ///
alpar@103
  1807
      /// Inequality operator
alpar@209
  1808
      bool operator!=(const ClassIt& i) {
alpar@103
  1809
        return i._id != _id;
alpar@209
  1810
      }
alpar@209
  1811
alpar@103
  1812
      operator int() const {
alpar@209
  1813
        return _id;
alpar@103
  1814
      }
alpar@209
  1815
alpar@103
  1816
    };
alpar@103
  1817
alpar@103
  1818
  };
alpar@103
  1819
alpar@103
  1820
  //! @}
alpar@103
  1821
alpar@103
  1822
} //namespace lemon
alpar@103
  1823
alpar@103
  1824
#endif //LEMON_UNION_FIND_H