lemon/bits/solver_bits.h
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 20 Feb 2009 21:37:19 +0000
changeset 517 2b6d5d22bb23
child 519 c786cd201266
permissions -rw-r--r--
Merge
     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 namespace lemon {
    23 
    24   namespace _solver_bits {
    25 
    26     class VarIndex {
    27     private:
    28       struct ItemT {
    29         int prev, next;
    30         int index;
    31       };
    32       std::vector<ItemT> items;
    33       int first_item, last_item, first_free_item;
    34 
    35       std::vector<int> cross;
    36 
    37     public:
    38 
    39       VarIndex()
    40         : first_item(-1), last_item(-1), first_free_item(-1) {
    41       }
    42 
    43       void clear() {
    44         first_item = -1;
    45         first_free_item = -1;
    46         items.clear();
    47         cross.clear();
    48       }
    49 
    50       int addIndex(int idx) {
    51         int n;
    52         if (first_free_item == -1) {
    53           n = items.size();
    54           items.push_back(ItemT());
    55         } else {
    56           n = first_free_item;
    57           first_free_item = items[n].next;
    58           if (first_free_item != -1) {
    59             items[first_free_item].prev = -1;
    60           }
    61         }
    62         items[n].index = idx;
    63         if (static_cast<int>(cross.size()) <= idx) {
    64           cross.resize(idx + 1, -1);
    65         }
    66         cross[idx] = n;
    67 
    68         items[n].prev = last_item;
    69         items[n].next = -1;
    70         if (last_item != -1) {
    71           items[last_item].next = n;
    72         } else {
    73           first_item = n;
    74         }
    75         last_item = n;
    76 
    77         return n;
    78       }
    79 
    80       int addIndex(int idx, int n) {
    81         while (n >= static_cast<int>(items.size())) {
    82           items.push_back(ItemT());
    83           items.back().prev = -1;
    84           items.back().next = first_free_item;
    85           if (first_free_item != -1) {
    86             items[first_free_item].prev = items.size() - 1;
    87           }
    88           first_free_item = items.size() - 1;
    89         }
    90         if (items[n].next != -1) {
    91           items[items[n].next].prev = items[n].prev;
    92         }
    93         if (items[n].prev != -1) {
    94           items[items[n].prev].next = items[n].next;
    95         } else {
    96           first_free_item = items[n].next;
    97         }
    98 
    99         items[n].index = idx;
   100         if (static_cast<int>(cross.size()) <= idx) {
   101           cross.resize(idx + 1, -1);
   102         }
   103         cross[idx] = n;
   104 
   105         items[n].prev = last_item;
   106         items[n].next = -1;
   107         if (last_item != -1) {
   108           items[last_item].next = n;
   109         } else {
   110           first_item = n;
   111         }
   112         last_item = n;
   113 
   114         return n;
   115       }
   116 
   117       void eraseIndex(int idx) {
   118         int n = cross[idx];
   119 
   120         if (items[n].prev != -1) {
   121           items[items[n].prev].next = items[n].next;
   122         } else {
   123           first_item = items[n].next;
   124         }
   125         if (items[n].next != -1) {
   126           items[items[n].next].prev = items[n].prev;
   127         } else {
   128           last_item = items[n].prev;
   129         }
   130 
   131         if (first_free_item != -1) {
   132           items[first_free_item].prev = n;
   133         }
   134         items[n].next = first_free_item;
   135         items[n].prev = -1;
   136         first_free_item = n;
   137 
   138         while (!cross.empty() && cross.back() == -1) {
   139           cross.pop_back();
   140         }
   141       }
   142 
   143       int maxIndex() const {
   144         return cross.size() - 1;
   145       }
   146 
   147       void shiftIndices(int idx) {
   148         for (int i = idx + 1; i < static_cast<int>(cross.size()); ++i) {
   149           cross[i - 1] = cross[i];
   150           if (cross[i] != -1) {
   151             --items[cross[i]].index;
   152           }
   153         }
   154         cross.back() = -1;
   155         cross.pop_back();
   156         while (!cross.empty() && cross.back() == -1) {
   157           cross.pop_back();
   158         }
   159       }
   160 
   161       void relocateIndex(int idx, int jdx) {
   162         cross[idx] = cross[jdx];
   163         items[cross[jdx]].index = idx;
   164         cross[jdx] = -1;
   165 
   166         while (!cross.empty() && cross.back() == -1) {
   167           cross.pop_back();
   168         }
   169       }
   170 
   171       int operator[](int idx) const {
   172         return cross[idx];
   173       }
   174 
   175       int operator()(int fdx) const {
   176         return items[fdx].index;
   177       }
   178 
   179       void firstItem(int& fdx) const {
   180         fdx = first_item;
   181       }
   182 
   183       void nextItem(int& fdx) const {
   184         fdx = items[fdx].next;
   185       }
   186 
   187     };
   188   }
   189 }
   190 
   191 #endif