deba@2363: /* -*- C++ -*-
deba@2363:  *
deba@2363:  * This file is a part of LEMON, a generic C++ optimization library
deba@2363:  *
deba@2363:  * Copyright (C) 2003-2006
deba@2363:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@2363:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@2363:  *
deba@2363:  * Permission to use, modify and distribute this software is granted
deba@2363:  * provided that this copyright notice appears in all copies. For
deba@2363:  * precise terms see the accompanying LICENSE file.
deba@2363:  *
deba@2363:  * This software is provided "AS IS" with no warranty of any kind,
deba@2363:  * express or implied, and with no claim as to its suitability for any
deba@2363:  * purpose.
deba@2363:  *
deba@2363:  */
deba@2363: 
deba@2363: #ifndef LEMON_BITS_LP_SOLVER_ID_H
deba@2363: #define LEMON_BITS_LP_SOLVER_ID_H
deba@2363: 
deba@2363: namespace lemon {
deba@2363:   
deba@2363:   namespace _lp_bits {
deba@2363: 
deba@2363:     struct LpIdImpl {
deba@2363:       std::vector<int> index;
deba@2363:       std::vector<int> cross;
deba@2363:       int first_index;
deba@2363:       int first_free;      
deba@2363:     };
deba@2363: 
deba@2363:     class LpId {
deba@2363:     public:
deba@2363:       
deba@2363:       class IdHandler {
deba@2363:       public:
deba@2363:         virtual ~IdHandler() {}
deba@2363:         virtual int addId(LpIdImpl&) = 0;
deba@2363:         virtual void eraseId(LpIdImpl&, int xn) = 0;
deba@2363:       };
deba@2363:       
deba@2363:       LpId(int min_index = 0) {
deba@2363:         id_handler = 0;
deba@2363:         impl.first_free = -1;
deba@2363:         impl.first_index = min_index;
deba@2363:         impl.cross.resize(impl.first_index);
deba@2363:       }
deba@2363: 
deba@2363:       void setIdHandler(IdHandler& ih) {
deba@2363:         id_handler = &ih;
deba@2363:       }
deba@2363:       
deba@2363:       int fixId(int fn) const {return impl.cross[fn];}
deba@2363:       int floatingId(int xn) const {return impl.index[xn];}
deba@2363:       
deba@2363:       int addId() {
deba@2363:         if (id_handler == 0) {
deba@2363:           int xn, fn = impl.cross.size();
deba@2363:           if (impl.first_free == -1) {
deba@2363:             xn = impl.index.size();
deba@2363:             impl.index.push_back(fn);
deba@2363:           } else {
deba@2363:             xn = impl.first_free;
deba@2363:             impl.first_free = impl.index[impl.first_free];
deba@2363:             impl.index[xn] = fn;
deba@2363:           }
deba@2363:           impl.cross.push_back(xn);
deba@2363:           return xn;
deba@2363:         } else {
deba@2363:           return id_handler->addId(impl);
deba@2363:         }
deba@2363:       }
deba@2363: 
deba@2363:       void eraseId(int xn) {
deba@2363:         if (id_handler == 0) {
deba@2363:           int fn = impl.index[xn];
deba@2363:           impl.index[xn] = impl.first_free;
deba@2363:           impl.first_free = xn;
deba@2386:           for(int i = fn + 1; i < int(impl.cross.size()); ++i) {
deba@2363:             impl.cross[i - 1] = impl.cross[i];
deba@2363:             impl.index[impl.cross[i]]--;
deba@2363:           }
deba@2363:           impl.cross.pop_back();
deba@2363:         } else {
deba@2363:           id_handler->eraseId(impl, xn);
deba@2363:         }
deba@2363:       }
deba@2363: 
deba@2363:       void firstFloating(int& fn) const {
deba@2363:         fn = impl.first_index;
deba@2386:         if (fn == int(impl.cross.size())) fn = -1;
deba@2363:       }
deba@2363: 
deba@2363:       void nextFloating(int& fn) const {
deba@2363:         ++fn;
deba@2386:         if (fn == int(impl.cross.size())) fn = -1;
deba@2363:       }
deba@2363: 
deba@2363:       void firstFix(int& xn) const {
deba@2363:         int fn;
deba@2363:         firstFloating(fn);
deba@2363:         xn = fn != -1 ? fixId(fn) : -1;
deba@2363:       }
deba@2363:       
deba@2363:       void nextFix(int& xn) const {
deba@2363:         int fn = floatingId(xn);
deba@2363:         nextFloating(fn);
deba@2363:         xn = fn != -1 ? fixId(fn) : -1;    
deba@2363:       }
deba@2363: 
deba@2363:     protected:
deba@2363:       LpIdImpl impl;
deba@2363:       IdHandler *id_handler;
deba@2363:     };
deba@2363:   
deba@2363:     class RelocateIdHandler : public LpId::IdHandler {
deba@2363:     public:
deba@2363: 
deba@2363:       virtual int addId(LpIdImpl& impl) {
deba@2363:         int xn, fn = impl.cross.size();
deba@2363:         if (impl.first_free == -1) {
deba@2363:           xn = impl.index.size();
deba@2363:           impl.index.push_back(fn);
deba@2363:         } else {
deba@2363:           xn = impl.first_free;
deba@2363:           impl.first_free = impl.index[impl.first_free];
deba@2363:           impl.index[xn] = fn;
deba@2363:         }
deba@2363:         impl.cross.push_back(xn);
deba@2363:         return xn;
deba@2363:       }
deba@2363: 
deba@2363:       virtual void eraseId(LpIdImpl& impl, int xn) {
deba@2363:         int fn = impl.index[xn];
deba@2363:         impl.index[xn] = impl.first_free;
deba@2363:         impl.first_free = xn;
deba@2363:         impl.cross[fn] = impl.cross.back();
deba@2363:         impl.index[impl.cross.back()] = fn;
deba@2363:         impl.cross.pop_back();
deba@2363:       }
deba@2363:     };
deba@2363:   }  
deba@2363: }
deba@2363: 
deba@2363: #endif