COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/lp_id.h @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 12 years ago

Happy New Year to all source files!

File size: 3.7 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
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 */
18
19#ifndef LEMON_BITS_LP_SOLVER_ID_H
20#define LEMON_BITS_LP_SOLVER_ID_H
21
22namespace lemon {
23 
24  namespace _lp_bits {
25
26    struct LpIdImpl {
27      std::vector<int> index;
28      std::vector<int> cross;
29      int first_index;
30      int first_free;     
31    };
32
33    class LpId {
34    public:
35     
36      class IdHandler {
37      public:
38        virtual ~IdHandler() {}
39        virtual int addId(LpIdImpl&) = 0;
40        virtual void eraseId(LpIdImpl&, int xn) = 0;
41      };
42     
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      }
49
50      void setIdHandler(IdHandler& ih) {
51        id_handler = &ih;
52      }
53     
54      int fixId(int fn) const {return impl.cross[fn];}
55      int floatingId(int xn) const {return impl.index[xn];}
56     
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      }
74
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      }
89
90      void firstFloating(int& fn) const {
91        fn = impl.first_index;
92        if (fn == int(impl.cross.size())) fn = -1;
93      }
94
95      void nextFloating(int& fn) const {
96        ++fn;
97        if (fn == int(impl.cross.size())) fn = -1;
98      }
99
100      void firstFix(int& xn) const {
101        int fn;
102        firstFloating(fn);
103        xn = fn != -1 ? fixId(fn) : -1;
104      }
105     
106      void nextFix(int& xn) const {
107        int fn = floatingId(xn);
108        nextFloating(fn);
109        xn = fn != -1 ? fixId(fn) : -1;   
110      }
111
112    protected:
113      LpIdImpl impl;
114      IdHandler *id_handler;
115    };
116 
117    class RelocateIdHandler : public LpId::IdHandler {
118    public:
119
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      }
133
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}
145
146#endif
Note: See TracBrowser for help on using the repository browser.