lemon-0.x: lemon/bits/lp_id.h@054566ac0934

     1 /* -*- C++ -*-

     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       void setIdHandler(IdHandler& ih) {

    51         id_handler = &ih;

    52       }

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

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

    57       int addId() {

    58         if (id_handler == 0) {

    59           int xn, fn = impl.cross.size();

    60           if (impl.first_free == -1) {

    61             xn = impl.index.size();

    62             impl.index.push_back(fn);

    63           } else {

    64             xn = impl.first_free;

    65             impl.first_free = impl.index[impl.first_free];

    66             impl.index[xn] = fn;

    67           }

    68           impl.cross.push_back(xn);

    69           return xn;

    70         } else {

    71           return id_handler->addId(impl);

    72         }

    73       }

    75       void eraseId(int xn) {

    76         if (id_handler == 0) {

    77           int fn = impl.index[xn];

    78           impl.index[xn] = impl.first_free;

    79           impl.first_free = xn;

    80           for(int i = fn + 1; i < int(impl.cross.size()); ++i) {

    81             impl.cross[i - 1] = impl.cross[i];

    82             impl.index[impl.cross[i]]--;

    83           }

    84           impl.cross.pop_back();

    85         } else {

    86           id_handler->eraseId(impl, xn);

    87         }

    88       }

    90       void firstFloating(int& fn) const {

    91         fn = impl.first_index;

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

    93       }

    95       void nextFloating(int& fn) const {

    96         ++fn;

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

    98       }

   100       void firstFix(int& xn) const {

   101         int fn;

   102         firstFloating(fn);

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

   104       }

   106       void nextFix(int& xn) const {

   107         int fn = floatingId(xn);

   108         nextFloating(fn);

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

   110       }

   112     protected:

   113       LpIdImpl impl;

   114       IdHandler *id_handler;

   115     };

   117     class RelocateIdHandler : public LpId::IdHandler {

   118     public:

   120       virtual int addId(LpIdImpl& impl) {

   121         int xn, fn = impl.cross.size();

   122         if (impl.first_free == -1) {

   123           xn = impl.index.size();

   124           impl.index.push_back(fn);

   125         } else {

   126           xn = impl.first_free;

   127           impl.first_free = impl.index[impl.first_free];

   128           impl.index[xn] = fn;

   129         }

   130         impl.cross.push_back(xn);

   131         return xn;

   132       }

   134       virtual void eraseId(LpIdImpl& impl, int xn) {

   135         int fn = impl.index[xn];

   136         impl.index[xn] = impl.first_free;

   137         impl.first_free = xn;

   138         impl.cross[fn] = impl.cross.back();

   139         impl.index[impl.cross.back()] = fn;

   140         impl.cross.pop_back();

   141       }

   142     };

   143   }

   144 }

   146 #endif

author	kpeter
	Thu, 28 Feb 2008 02:54:27 +0000
changeset 2581	054566ac0934
parent 2391	14a343be7a5a
permissions	-rw-r--r--