1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/bits/lp_id.h Tue Dec 02 21:40:33 2008 +0100
1.3 @@ -0,0 +1,157 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_BITS_LP_SOLVER_ID_H
1.23 +#define LEMON_BITS_LP_SOLVER_ID_H
1.24 +
1.25 +namespace lemon {
1.26 +
1.27 + namespace _lp_bits {
1.28 +
1.29 + struct LpIdImpl {
1.30 + std::vector<int> index;
1.31 + std::vector<int> cross;
1.32 + int first_index;
1.33 + int first_free;
1.34 + };
1.35 +
1.36 + class LpId {
1.37 + public:
1.38 +
1.39 + class IdHandler {
1.40 + public:
1.41 + virtual ~IdHandler() {}
1.42 + virtual int addId(LpIdImpl&) = 0;
1.43 + virtual void eraseId(LpIdImpl&, int xn) = 0;
1.44 + };
1.45 +
1.46 + LpId(int min_index = 0) {
1.47 + id_handler = 0;
1.48 + impl.first_free = -1;
1.49 + impl.first_index = min_index;
1.50 + impl.cross.resize(impl.first_index);
1.51 + }
1.52 +
1.53 + LpId(const LpId& li) {
1.54 + id_handler = 0;
1.55 + impl = li.impl;
1.56 + }
1.57 +
1.58 + LpId& operator=(const LpId& li) {
1.59 + id_handler = 0;
1.60 + impl = li.impl;
1.61 + return *this;
1.62 + }
1.63 +
1.64 + void setIdHandler(IdHandler& ih) {
1.65 + id_handler = &ih;
1.66 + }
1.67 +
1.68 + int fixId(int fn) const {return impl.cross[fn];}
1.69 + int floatingId(int xn) const {return impl.index[xn];}
1.70 +
1.71 + int addId() {
1.72 + if (id_handler == 0) {
1.73 + int xn, fn = impl.cross.size();
1.74 + if (impl.first_free == -1) {
1.75 + xn = impl.index.size();
1.76 + impl.index.push_back(fn);
1.77 + } else {
1.78 + xn = impl.first_free;
1.79 + impl.first_free = impl.index[impl.first_free];
1.80 + impl.index[xn] = fn;
1.81 + }
1.82 + impl.cross.push_back(xn);
1.83 + return xn;
1.84 + } else {
1.85 + return id_handler->addId(impl);
1.86 + }
1.87 + }
1.88 +
1.89 + void eraseId(int xn) {
1.90 + if (id_handler == 0) {
1.91 + int fn = impl.index[xn];
1.92 + impl.index[xn] = impl.first_free;
1.93 + impl.first_free = xn;
1.94 + for(int i = fn + 1; i < int(impl.cross.size()); ++i) {
1.95 + impl.cross[i - 1] = impl.cross[i];
1.96 + impl.index[impl.cross[i]]--;
1.97 + }
1.98 + impl.cross.pop_back();
1.99 + } else {
1.100 + id_handler->eraseId(impl, xn);
1.101 + }
1.102 + }
1.103 +
1.104 + void firstFloating(int& fn) const {
1.105 + fn = impl.first_index;
1.106 + if (fn == int(impl.cross.size())) fn = -1;
1.107 + }
1.108 +
1.109 + void nextFloating(int& fn) const {
1.110 + ++fn;
1.111 + if (fn == int(impl.cross.size())) fn = -1;
1.112 + }
1.113 +
1.114 + void firstFix(int& xn) const {
1.115 + int fn;
1.116 + firstFloating(fn);
1.117 + xn = fn != -1 ? fixId(fn) : -1;
1.118 + }
1.119 +
1.120 + void nextFix(int& xn) const {
1.121 + int fn = floatingId(xn);
1.122 + nextFloating(fn);
1.123 + xn = fn != -1 ? fixId(fn) : -1;
1.124 + }
1.125 +
1.126 + protected:
1.127 + LpIdImpl impl;
1.128 + IdHandler *id_handler;
1.129 + };
1.130 +
1.131 + class RelocateIdHandler : public LpId::IdHandler {
1.132 + public:
1.133 +
1.134 + virtual int addId(LpIdImpl& impl) {
1.135 + int xn, fn = impl.cross.size();
1.136 + if (impl.first_free == -1) {
1.137 + xn = impl.index.size();
1.138 + impl.index.push_back(fn);
1.139 + } else {
1.140 + xn = impl.first_free;
1.141 + impl.first_free = impl.index[impl.first_free];
1.142 + impl.index[xn] = fn;
1.143 + }
1.144 + impl.cross.push_back(xn);
1.145 + return xn;
1.146 + }
1.147 +
1.148 + virtual void eraseId(LpIdImpl& impl, int xn) {
1.149 + int fn = impl.index[xn];
1.150 + impl.index[xn] = impl.first_free;
1.151 + impl.first_free = xn;
1.152 + impl.cross[fn] = impl.cross.back();
1.153 + impl.index[impl.cross.back()] = fn;
1.154 + impl.cross.pop_back();
1.155 + }
1.156 + };
1.157 + }
1.158 +}
1.159 +
1.160 +#endif