lemon/bits/solver_bits.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 26 Apr 2009 16:44:53 +0200
changeset 625 029a48052c67
parent 459 ed54c0d13df0
child 877 141f9c0db4a3
child 988 8d281761dea4
permissions -rw-r--r--
Modify the interface of MinCostArborescence + improvements (#267)

- Rename arborescenceValue() to arborescenceCost().
- Rename DefXyz template named paramaters to SetXyz.
- Rearrange public functions (for better doc).
- Doc improvements.
- Extend the test file with interface checking.
deba@459
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@459
     2
 *
deba@459
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@459
     4
 *
deba@459
     5
 * Copyright (C) 2003-2008
deba@459
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@459
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@459
     8
 *
deba@459
     9
 * Permission to use, modify and distribute this software is granted
deba@459
    10
 * provided that this copyright notice appears in all copies. For
deba@459
    11
 * precise terms see the accompanying LICENSE file.
deba@459
    12
 *
deba@459
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@459
    14
 * express or implied, and with no claim as to its suitability for any
deba@459
    15
 * purpose.
deba@459
    16
 *
deba@459
    17
 */
deba@459
    18
deba@459
    19
#ifndef LEMON_BITS_SOLVER_BITS_H
deba@459
    20
#define LEMON_BITS_SOLVER_BITS_H
deba@459
    21
deba@519
    22
#include <vector>
deba@519
    23
deba@459
    24
namespace lemon {
deba@459
    25
deba@459
    26
  namespace _solver_bits {
deba@459
    27
deba@459
    28
    class VarIndex {
deba@459
    29
    private:
deba@459
    30
      struct ItemT {
deba@459
    31
        int prev, next;
deba@459
    32
        int index;
deba@459
    33
      };
deba@459
    34
      std::vector<ItemT> items;
deba@459
    35
      int first_item, last_item, first_free_item;
deba@459
    36
deba@459
    37
      std::vector<int> cross;
deba@459
    38
deba@459
    39
    public:
deba@459
    40
deba@459
    41
      VarIndex()
deba@459
    42
        : first_item(-1), last_item(-1), first_free_item(-1) {
deba@459
    43
      }
deba@459
    44
deba@459
    45
      void clear() {
deba@459
    46
        first_item = -1;
deba@459
    47
        first_free_item = -1;
deba@459
    48
        items.clear();
deba@459
    49
        cross.clear();
deba@459
    50
      }
deba@459
    51
deba@459
    52
      int addIndex(int idx) {
deba@459
    53
        int n;
deba@459
    54
        if (first_free_item == -1) {
deba@459
    55
          n = items.size();
deba@459
    56
          items.push_back(ItemT());
deba@459
    57
        } else {
deba@459
    58
          n = first_free_item;
deba@459
    59
          first_free_item = items[n].next;
deba@459
    60
          if (first_free_item != -1) {
deba@459
    61
            items[first_free_item].prev = -1;
deba@459
    62
          }
deba@459
    63
        }
deba@459
    64
        items[n].index = idx;
deba@459
    65
        if (static_cast<int>(cross.size()) <= idx) {
deba@459
    66
          cross.resize(idx + 1, -1);
deba@459
    67
        }
deba@459
    68
        cross[idx] = n;
deba@459
    69
deba@459
    70
        items[n].prev = last_item;
deba@459
    71
        items[n].next = -1;
deba@459
    72
        if (last_item != -1) {
deba@459
    73
          items[last_item].next = n;
deba@459
    74
        } else {
deba@459
    75
          first_item = n;
deba@459
    76
        }
deba@459
    77
        last_item = n;
deba@459
    78
deba@459
    79
        return n;
deba@459
    80
      }
deba@459
    81
deba@459
    82
      int addIndex(int idx, int n) {
deba@459
    83
        while (n >= static_cast<int>(items.size())) {
deba@459
    84
          items.push_back(ItemT());
deba@459
    85
          items.back().prev = -1;
deba@459
    86
          items.back().next = first_free_item;
deba@459
    87
          if (first_free_item != -1) {
deba@459
    88
            items[first_free_item].prev = items.size() - 1;
deba@459
    89
          }
deba@459
    90
          first_free_item = items.size() - 1;
deba@459
    91
        }
deba@459
    92
        if (items[n].next != -1) {
deba@459
    93
          items[items[n].next].prev = items[n].prev;
deba@459
    94
        }
deba@459
    95
        if (items[n].prev != -1) {
deba@459
    96
          items[items[n].prev].next = items[n].next;
deba@459
    97
        } else {
deba@459
    98
          first_free_item = items[n].next;
deba@459
    99
        }
deba@459
   100
deba@459
   101
        items[n].index = idx;
deba@459
   102
        if (static_cast<int>(cross.size()) <= idx) {
deba@459
   103
          cross.resize(idx + 1, -1);
deba@459
   104
        }
deba@459
   105
        cross[idx] = n;
deba@459
   106
deba@459
   107
        items[n].prev = last_item;
deba@459
   108
        items[n].next = -1;
deba@459
   109
        if (last_item != -1) {
deba@459
   110
          items[last_item].next = n;
deba@459
   111
        } else {
deba@459
   112
          first_item = n;
deba@459
   113
        }
deba@459
   114
        last_item = n;
deba@459
   115
deba@459
   116
        return n;
deba@459
   117
      }
deba@459
   118
deba@459
   119
      void eraseIndex(int idx) {
deba@459
   120
        int n = cross[idx];
deba@459
   121
deba@459
   122
        if (items[n].prev != -1) {
deba@459
   123
          items[items[n].prev].next = items[n].next;
deba@459
   124
        } else {
deba@459
   125
          first_item = items[n].next;
deba@459
   126
        }
deba@459
   127
        if (items[n].next != -1) {
deba@459
   128
          items[items[n].next].prev = items[n].prev;
deba@459
   129
        } else {
deba@459
   130
          last_item = items[n].prev;
deba@459
   131
        }
deba@459
   132
deba@459
   133
        if (first_free_item != -1) {
deba@459
   134
          items[first_free_item].prev = n;
deba@459
   135
        }
deba@459
   136
        items[n].next = first_free_item;
deba@459
   137
        items[n].prev = -1;
deba@459
   138
        first_free_item = n;
deba@459
   139
deba@459
   140
        while (!cross.empty() && cross.back() == -1) {
deba@459
   141
          cross.pop_back();
deba@459
   142
        }
deba@459
   143
      }
deba@459
   144
deba@459
   145
      int maxIndex() const {
deba@459
   146
        return cross.size() - 1;
deba@459
   147
      }
deba@459
   148
deba@459
   149
      void shiftIndices(int idx) {
deba@459
   150
        for (int i = idx + 1; i < static_cast<int>(cross.size()); ++i) {
deba@459
   151
          cross[i - 1] = cross[i];
deba@459
   152
          if (cross[i] != -1) {
deba@459
   153
            --items[cross[i]].index;
deba@459
   154
          }
deba@459
   155
        }
deba@459
   156
        cross.back() = -1;
deba@459
   157
        cross.pop_back();
deba@459
   158
        while (!cross.empty() && cross.back() == -1) {
deba@459
   159
          cross.pop_back();
deba@459
   160
        }
deba@459
   161
      }
deba@459
   162
deba@459
   163
      void relocateIndex(int idx, int jdx) {
deba@459
   164
        cross[idx] = cross[jdx];
deba@459
   165
        items[cross[jdx]].index = idx;
deba@459
   166
        cross[jdx] = -1;
deba@459
   167
deba@459
   168
        while (!cross.empty() && cross.back() == -1) {
deba@459
   169
          cross.pop_back();
deba@459
   170
        }
deba@459
   171
      }
deba@459
   172
deba@459
   173
      int operator[](int idx) const {
deba@459
   174
        return cross[idx];
deba@459
   175
      }
deba@459
   176
deba@459
   177
      int operator()(int fdx) const {
deba@459
   178
        return items[fdx].index;
deba@459
   179
      }
deba@459
   180
deba@459
   181
      void firstItem(int& fdx) const {
deba@459
   182
        fdx = first_item;
deba@459
   183
      }
deba@459
   184
deba@459
   185
      void nextItem(int& fdx) const {
deba@459
   186
        fdx = items[fdx].next;
deba@459
   187
      }
deba@459
   188
deba@459
   189
    };
deba@459
   190
  }
deba@459
   191
}
deba@459
   192
deba@459
   193
#endif