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