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