lemon/bits/lp_id.h
changeset 458 7afc121e0689
equal deleted inserted replaced
-1:000000000000 0:52c82ad0c48f
       
     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_LP_SOLVER_ID_H
       
    20 #define LEMON_BITS_LP_SOLVER_ID_H
       
    21 
       
    22 namespace lemon {
       
    23 
       
    24   namespace _lp_bits {
       
    25 
       
    26     struct LpIdImpl {
       
    27       std::vector<int> index;
       
    28       std::vector<int> cross;
       
    29       int first_index;
       
    30       int first_free;
       
    31     };
       
    32 
       
    33     class LpId {
       
    34     public:
       
    35 
       
    36       class IdHandler {
       
    37       public:
       
    38         virtual ~IdHandler() {}
       
    39         virtual int addId(LpIdImpl&) = 0;
       
    40         virtual void eraseId(LpIdImpl&, int xn) = 0;
       
    41       };
       
    42 
       
    43       LpId(int min_index = 0) {
       
    44         id_handler = 0;
       
    45         impl.first_free = -1;
       
    46         impl.first_index = min_index;
       
    47         impl.cross.resize(impl.first_index);
       
    48       }
       
    49 
       
    50       LpId(const LpId& li) {
       
    51         id_handler = 0;
       
    52         impl = li.impl;
       
    53       }
       
    54 
       
    55       LpId& operator=(const LpId& li) {
       
    56         id_handler = 0;
       
    57         impl = li.impl;
       
    58         return *this;
       
    59       }
       
    60 
       
    61       void setIdHandler(IdHandler& ih) {
       
    62         id_handler = &ih;
       
    63       }
       
    64 
       
    65       int fixId(int fn) const {return impl.cross[fn];}
       
    66       int floatingId(int xn) const {return impl.index[xn];}
       
    67 
       
    68       int addId() {
       
    69         if (id_handler == 0) {
       
    70           int xn, fn = impl.cross.size();
       
    71           if (impl.first_free == -1) {
       
    72             xn = impl.index.size();
       
    73             impl.index.push_back(fn);
       
    74           } else {
       
    75             xn = impl.first_free;
       
    76             impl.first_free = impl.index[impl.first_free];
       
    77             impl.index[xn] = fn;
       
    78           }
       
    79           impl.cross.push_back(xn);
       
    80           return xn;
       
    81         } else {
       
    82           return id_handler->addId(impl);
       
    83         }
       
    84       }
       
    85 
       
    86       void eraseId(int xn) {
       
    87         if (id_handler == 0) {
       
    88           int fn = impl.index[xn];
       
    89           impl.index[xn] = impl.first_free;
       
    90           impl.first_free = xn;
       
    91           for(int i = fn + 1; i < int(impl.cross.size()); ++i) {
       
    92             impl.cross[i - 1] = impl.cross[i];
       
    93             impl.index[impl.cross[i]]--;
       
    94           }
       
    95           impl.cross.pop_back();
       
    96         } else {
       
    97           id_handler->eraseId(impl, xn);
       
    98         }
       
    99       }
       
   100 
       
   101       void firstFloating(int& fn) const {
       
   102         fn = impl.first_index;
       
   103         if (fn == int(impl.cross.size())) fn = -1;
       
   104       }
       
   105 
       
   106       void nextFloating(int& fn) const {
       
   107         ++fn;
       
   108         if (fn == int(impl.cross.size())) fn = -1;
       
   109       }
       
   110 
       
   111       void firstFix(int& xn) const {
       
   112         int fn;
       
   113         firstFloating(fn);
       
   114         xn = fn != -1 ? fixId(fn) : -1;
       
   115       }
       
   116 
       
   117       void nextFix(int& xn) const {
       
   118         int fn = floatingId(xn);
       
   119         nextFloating(fn);
       
   120         xn = fn != -1 ? fixId(fn) : -1;
       
   121       }
       
   122 
       
   123     protected:
       
   124       LpIdImpl impl;
       
   125       IdHandler *id_handler;
       
   126     };
       
   127 
       
   128     class RelocateIdHandler : public LpId::IdHandler {
       
   129     public:
       
   130 
       
   131       virtual int addId(LpIdImpl& impl) {
       
   132         int xn, fn = impl.cross.size();
       
   133         if (impl.first_free == -1) {
       
   134           xn = impl.index.size();
       
   135           impl.index.push_back(fn);
       
   136         } else {
       
   137           xn = impl.first_free;
       
   138           impl.first_free = impl.index[impl.first_free];
       
   139           impl.index[xn] = fn;
       
   140         }
       
   141         impl.cross.push_back(xn);
       
   142         return xn;
       
   143       }
       
   144 
       
   145       virtual void eraseId(LpIdImpl& impl, int xn) {
       
   146         int fn = impl.index[xn];
       
   147         impl.index[xn] = impl.first_free;
       
   148         impl.first_free = xn;
       
   149         impl.cross[fn] = impl.cross.back();
       
   150         impl.index[impl.cross.back()] = fn;
       
   151         impl.cross.pop_back();
       
   152       }
       
   153     };
       
   154   }
       
   155 }
       
   156 
       
   157 #endif