1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_BITS_LP_SOLVER_ID_H
20 #define LEMON_BITS_LP_SOLVER_ID_H
27 std::vector<int> index;
28 std::vector<int> cross;
38 virtual ~IdHandler() {}
39 virtual int addId(LpIdImpl&) = 0;
40 virtual void eraseId(LpIdImpl&, int xn) = 0;
43 LpId(int min_index = 0) {
46 impl.first_index = min_index;
47 impl.cross.resize(impl.first_index);
50 LpId(const LpId& li) {
55 LpId& operator=(const LpId& li) {
61 void setIdHandler(IdHandler& ih) {
65 int fixId(int fn) const {return impl.cross[fn];}
66 int floatingId(int xn) const {return impl.index[xn];}
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);
76 impl.first_free = impl.index[impl.first_free];
79 impl.cross.push_back(xn);
82 return id_handler->addId(impl);
86 void eraseId(int xn) {
87 if (id_handler == 0) {
88 int fn = impl.index[xn];
89 impl.index[xn] = impl.first_free;
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]]--;
95 impl.cross.pop_back();
97 id_handler->eraseId(impl, xn);
101 void firstFloating(int& fn) const {
102 fn = impl.first_index;
103 if (fn == int(impl.cross.size())) fn = -1;
106 void nextFloating(int& fn) const {
108 if (fn == int(impl.cross.size())) fn = -1;
111 void firstFix(int& xn) const {
114 xn = fn != -1 ? fixId(fn) : -1;
117 void nextFix(int& xn) const {
118 int fn = floatingId(xn);
120 xn = fn != -1 ? fixId(fn) : -1;
125 IdHandler *id_handler;
128 class RelocateIdHandler : public LpId::IdHandler {
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);
137 xn = impl.first_free;
138 impl.first_free = impl.index[impl.first_free];
141 impl.cross.push_back(xn);
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();