lemon-1.2: lemon/bits/lp_id.h@7afc121e0689

     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  */

    19 #ifndef LEMON_BITS_LP_SOLVER_ID_H

    20 #define LEMON_BITS_LP_SOLVER_ID_H

    22 namespace lemon {

    24   namespace _lp_bits {

    26     struct LpIdImpl {

    27       std::vector<int> index;

    28       std::vector<int> cross;

    29       int first_index;

    30       int first_free;

    31     };

    33     class LpId {

    34     public:

    36       class IdHandler {

    37       public:

    38         virtual ~IdHandler() {}

    39         virtual int addId(LpIdImpl&) = 0;

    40         virtual void eraseId(LpIdImpl&, int xn) = 0;

    41       };

    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       }

    50       LpId(const LpId& li) {

    51         id_handler = 0;

    52         impl = li.impl;

    53       }

    55       LpId& operator=(const LpId& li) {

    56         id_handler = 0;

    57         impl = li.impl;

    58         return *this;

    59       }

    61       void setIdHandler(IdHandler& ih) {

    62         id_handler = &ih;

    63       }

    65       int fixId(int fn) const {return impl.cross[fn];}

    66       int floatingId(int xn) const {return impl.index[xn];}

    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       }

    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       }

   101       void firstFloating(int& fn) const {

   102         fn = impl.first_index;

   103         if (fn == int(impl.cross.size())) fn = -1;

   104       }

   106       void nextFloating(int& fn) const {

   107         ++fn;

   108         if (fn == int(impl.cross.size())) fn = -1;

   109       }

   111       void firstFix(int& xn) const {

   112         int fn;

   113         firstFloating(fn);

   114         xn = fn != -1 ? fixId(fn) : -1;

   115       }

   117       void nextFix(int& xn) const {

   118         int fn = floatingId(xn);

   119         nextFloating(fn);

   120         xn = fn != -1 ? fixId(fn) : -1;

   121       }

   123     protected:

   124       LpIdImpl impl;

   125       IdHandler *id_handler;

   126     };

   128     class RelocateIdHandler : public LpId::IdHandler {

   129     public:

   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       }

   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 }

   157 #endif

author	Balazs Dezso <deba@inf.elte.hu>
	Tue, 02 Dec 2008 21:40:33 +0100
changeset 458	7afc121e0689
permissions	-rw-r--r--