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)
     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-2010
     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         last_item = -1;
    48         first_free_item = -1;
    49         items.clear();
    50         cross.clear();
    51       }
    52 
    53       int addIndex(int idx) {
    54         int n;
    55         if (first_free_item == -1) {
    56           n = items.size();
    57           items.push_back(ItemT());
    58         } else {
    59           n = first_free_item;
    60           first_free_item = items[n].next;
    61           if (first_free_item != -1) {
    62             items[first_free_item].prev = -1;
    63           }
    64         }
    65         items[n].index = idx;
    66         if (static_cast<int>(cross.size()) <= idx) {
    67           cross.resize(idx + 1, -1);
    68         }
    69         cross[idx] = n;
    70 
    71         items[n].prev = last_item;
    72         items[n].next = -1;
    73         if (last_item != -1) {
    74           items[last_item].next = n;
    75         } else {
    76           first_item = n;
    77         }
    78         last_item = n;
    79 
    80         return n;
    81       }
    82 
    83       int addIndex(int idx, int n) {
    84         while (n >= static_cast<int>(items.size())) {
    85           items.push_back(ItemT());
    86           items.back().prev = -1;
    87           items.back().next = first_free_item;
    88           if (first_free_item != -1) {
    89             items[first_free_item].prev = items.size() - 1;
    90           }
    91           first_free_item = items.size() - 1;
    92         }
    93         if (items[n].next != -1) {
    94           items[items[n].next].prev = items[n].prev;
    95         }
    96         if (items[n].prev != -1) {
    97           items[items[n].prev].next = items[n].next;
    98         } else {
    99           first_free_item = items[n].next;
   100         }
   101 
   102         items[n].index = idx;
   103         if (static_cast<int>(cross.size()) <= idx) {
   104           cross.resize(idx + 1, -1);
   105         }
   106         cross[idx] = n;
   107 
   108         items[n].prev = last_item;
   109         items[n].next = -1;
   110         if (last_item != -1) {
   111           items[last_item].next = n;
   112         } else {
   113           first_item = n;
   114         }
   115         last_item = n;
   116 
   117         return n;
   118       }
   119 
   120       void eraseIndex(int idx) {
   121         int n = cross[idx];
   122 
   123         if (items[n].prev != -1) {
   124           items[items[n].prev].next = items[n].next;
   125         } else {
   126           first_item = items[n].next;
   127         }
   128         if (items[n].next != -1) {
   129           items[items[n].next].prev = items[n].prev;
   130         } else {
   131           last_item = items[n].prev;
   132         }
   133 
   134         if (first_free_item != -1) {
   135           items[first_free_item].prev = n;
   136         }
   137         items[n].next = first_free_item;
   138         items[n].prev = -1;
   139         first_free_item = n;
   140 
   141         while (!cross.empty() && cross.back() == -1) {
   142           cross.pop_back();
   143         }
   144       }
   145 
   146       int maxIndex() const {
   147         return cross.size() - 1;
   148       }
   149 
   150       void shiftIndices(int idx) {
   151         for (int i = idx + 1; i < static_cast<int>(cross.size()); ++i) {
   152           cross[i - 1] = cross[i];
   153           if (cross[i] != -1) {
   154             --items[cross[i]].index;
   155           }
   156         }
   157         cross.back() = -1;
   158         cross.pop_back();
   159         while (!cross.empty() && cross.back() == -1) {
   160           cross.pop_back();
   161         }
   162       }
   163 
   164       void relocateIndex(int idx, int jdx) {
   165         cross[idx] = cross[jdx];
   166         items[cross[jdx]].index = idx;
   167         cross[jdx] = -1;
   168 
   169         while (!cross.empty() && cross.back() == -1) {
   170           cross.pop_back();
   171         }
   172       }
   173 
   174       int operator[](int idx) const {
   175         return cross[idx];
   176       }
   177 
   178       int operator()(int fdx) const {
   179         return items[fdx].index;
   180       }
   181 
   182       void firstItem(int& fdx) const {
   183         fdx = first_item;
   184       }
   185 
   186       void nextItem(int& fdx) const {
   187         fdx = items[fdx].next;
   188       }
   189 
   190     };
   191   }
   192 }
   193 
   194 #endif