lemon/bits/solver_bits.h
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 06 Aug 2013 05:38:49 +0200
changeset 1080 c5cd8960df74
parent 877 141f9c0db4a3
parent 988 8d281761dea4
child 1092 dceba191c00d
permissions -rw-r--r--
Use m instead of e for denoting the number of arcs/edges (#463)
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
 *
alpar@877
     5
 * Copyright (C) 2003-2010
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;
alpar@988
    47
        last_item = -1;
deba@459
    48
        first_free_item = -1;
deba@459
    49
        items.clear();
deba@459
    50
        cross.clear();
deba@459
    51
      }
deba@459
    52
deba@459
    53
      int addIndex(int idx) {
deba@459
    54
        int n;
deba@459
    55
        if (first_free_item == -1) {
deba@459
    56
          n = items.size();
deba@459
    57
          items.push_back(ItemT());
deba@459
    58
        } else {
deba@459
    59
          n = first_free_item;
deba@459
    60
          first_free_item = items[n].next;
deba@459
    61
          if (first_free_item != -1) {
deba@459
    62
            items[first_free_item].prev = -1;
deba@459
    63
          }
deba@459
    64
        }
deba@459
    65
        items[n].index = idx;
deba@459
    66
        if (static_cast<int>(cross.size()) <= idx) {
deba@459
    67
          cross.resize(idx + 1, -1);
deba@459
    68
        }
deba@459
    69
        cross[idx] = n;
deba@459
    70
deba@459
    71
        items[n].prev = last_item;
deba@459
    72
        items[n].next = -1;
deba@459
    73
        if (last_item != -1) {
deba@459
    74
          items[last_item].next = n;
deba@459
    75
        } else {
deba@459
    76
          first_item = n;
deba@459
    77
        }
deba@459
    78
        last_item = n;
deba@459
    79
deba@459
    80
        return n;
deba@459
    81
      }
deba@459
    82
deba@459
    83
      int addIndex(int idx, int n) {
deba@459
    84
        while (n >= static_cast<int>(items.size())) {
deba@459
    85
          items.push_back(ItemT());
deba@459
    86
          items.back().prev = -1;
deba@459
    87
          items.back().next = first_free_item;
deba@459
    88
          if (first_free_item != -1) {
deba@459
    89
            items[first_free_item].prev = items.size() - 1;
deba@459
    90
          }
deba@459
    91
          first_free_item = items.size() - 1;
deba@459
    92
        }
deba@459
    93
        if (items[n].next != -1) {
deba@459
    94
          items[items[n].next].prev = items[n].prev;
deba@459
    95
        }
deba@459
    96
        if (items[n].prev != -1) {
deba@459
    97
          items[items[n].prev].next = items[n].next;
deba@459
    98
        } else {
deba@459
    99
          first_free_item = items[n].next;
deba@459
   100
        }
deba@459
   101
deba@459
   102
        items[n].index = idx;
deba@459
   103
        if (static_cast<int>(cross.size()) <= idx) {
deba@459
   104
          cross.resize(idx + 1, -1);
deba@459
   105
        }
deba@459
   106
        cross[idx] = n;
deba@459
   107
deba@459
   108
        items[n].prev = last_item;
deba@459
   109
        items[n].next = -1;
deba@459
   110
        if (last_item != -1) {
deba@459
   111
          items[last_item].next = n;
deba@459
   112
        } else {
deba@459
   113
          first_item = n;
deba@459
   114
        }
deba@459
   115
        last_item = n;
deba@459
   116
deba@459
   117
        return n;
deba@459
   118
      }
deba@459
   119
deba@459
   120
      void eraseIndex(int idx) {
deba@459
   121
        int n = cross[idx];
deba@459
   122
deba@459
   123
        if (items[n].prev != -1) {
deba@459
   124
          items[items[n].prev].next = items[n].next;
deba@459
   125
        } else {
deba@459
   126
          first_item = items[n].next;
deba@459
   127
        }
deba@459
   128
        if (items[n].next != -1) {
deba@459
   129
          items[items[n].next].prev = items[n].prev;
deba@459
   130
        } else {
deba@459
   131
          last_item = items[n].prev;
deba@459
   132
        }
deba@459
   133
deba@459
   134
        if (first_free_item != -1) {
deba@459
   135
          items[first_free_item].prev = n;
deba@459
   136
        }
deba@459
   137
        items[n].next = first_free_item;
deba@459
   138
        items[n].prev = -1;
deba@459
   139
        first_free_item = n;
deba@459
   140
deba@459
   141
        while (!cross.empty() && cross.back() == -1) {
deba@459
   142
          cross.pop_back();
deba@459
   143
        }
deba@459
   144
      }
deba@459
   145
deba@459
   146
      int maxIndex() const {
deba@459
   147
        return cross.size() - 1;
deba@459
   148
      }
deba@459
   149
deba@459
   150
      void shiftIndices(int idx) {
deba@459
   151
        for (int i = idx + 1; i < static_cast<int>(cross.size()); ++i) {
deba@459
   152
          cross[i - 1] = cross[i];
deba@459
   153
          if (cross[i] != -1) {
deba@459
   154
            --items[cross[i]].index;
deba@459
   155
          }
deba@459
   156
        }
deba@459
   157
        cross.back() = -1;
deba@459
   158
        cross.pop_back();
deba@459
   159
        while (!cross.empty() && cross.back() == -1) {
deba@459
   160
          cross.pop_back();
deba@459
   161
        }
deba@459
   162
      }
deba@459
   163
deba@459
   164
      void relocateIndex(int idx, int jdx) {
deba@459
   165
        cross[idx] = cross[jdx];
deba@459
   166
        items[cross[jdx]].index = idx;
deba@459
   167
        cross[jdx] = -1;
deba@459
   168
deba@459
   169
        while (!cross.empty() && cross.back() == -1) {
deba@459
   170
          cross.pop_back();
deba@459
   171
        }
deba@459
   172
      }
deba@459
   173
deba@459
   174
      int operator[](int idx) const {
deba@459
   175
        return cross[idx];
deba@459
   176
      }
deba@459
   177
deba@459
   178
      int operator()(int fdx) const {
deba@459
   179
        return items[fdx].index;
deba@459
   180
      }
deba@459
   181
deba@459
   182
      void firstItem(int& fdx) const {
deba@459
   183
        fdx = first_item;
deba@459
   184
      }
deba@459
   185
deba@459
   186
      void nextItem(int& fdx) const {
deba@459
   187
        fdx = items[fdx].next;
deba@459
   188
      }
deba@459
   189
deba@459
   190
    };
deba@459
   191
  }
deba@459
   192
}
deba@459
   193
deba@459
   194
#endif