COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/solver_bits.h @ 1140:8d281761dea4

Last change on this file since 1140:8d281761dea4 was 1140:8d281761dea4, checked in by Alpar Juttner <alpar@…>, 12 years ago

Fix buggy reinitialization in _solver_bits::VarIndex::clear() (#441)

  • In addition, rows.clear() and cols.clear() are moved up to LpBase::clear()
File size: 4.6 KB
Line 
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 */
18
19#ifndef LEMON_BITS_SOLVER_BITS_H
20#define LEMON_BITS_SOLVER_BITS_H
21
22#include <vector>
23
24namespace lemon {
25
26  namespace _solver_bits {
27
28    class VarIndex {
29    private:
30      struct ItemT {
31        int prev, next;
32        int index;
33      };
34      std::vector<ItemT> items;
35      int first_item, last_item, first_free_item;
36
37      std::vector<int> cross;
38
39    public:
40
41      VarIndex()
42        : first_item(-1), last_item(-1), first_free_item(-1) {
43      }
44
45      void clear() {
46        first_item = -1;
47        last_item = -1;
48        first_free_item = -1;
49        items.clear();
50        cross.clear();
51      }
52
53      int addIndex(int idx) {
54        int n;
55        if (first_free_item == -1) {
56          n = items.size();
57          items.push_back(ItemT());
58        } else {
59          n = first_free_item;
60          first_free_item = items[n].next;
61          if (first_free_item != -1) {
62            items[first_free_item].prev = -1;
63          }
64        }
65        items[n].index = idx;
66        if (static_cast<int>(cross.size()) <= idx) {
67          cross.resize(idx + 1, -1);
68        }
69        cross[idx] = n;
70
71        items[n].prev = last_item;
72        items[n].next = -1;
73        if (last_item != -1) {
74          items[last_item].next = n;
75        } else {
76          first_item = n;
77        }
78        last_item = n;
79
80        return n;
81      }
82
83      int addIndex(int idx, int n) {
84        while (n >= static_cast<int>(items.size())) {
85          items.push_back(ItemT());
86          items.back().prev = -1;
87          items.back().next = first_free_item;
88          if (first_free_item != -1) {
89            items[first_free_item].prev = items.size() - 1;
90          }
91          first_free_item = items.size() - 1;
92        }
93        if (items[n].next != -1) {
94          items[items[n].next].prev = items[n].prev;
95        }
96        if (items[n].prev != -1) {
97          items[items[n].prev].next = items[n].next;
98        } else {
99          first_free_item = items[n].next;
100        }
101
102        items[n].index = idx;
103        if (static_cast<int>(cross.size()) <= idx) {
104          cross.resize(idx + 1, -1);
105        }
106        cross[idx] = n;
107
108        items[n].prev = last_item;
109        items[n].next = -1;
110        if (last_item != -1) {
111          items[last_item].next = n;
112        } else {
113          first_item = n;
114        }
115        last_item = n;
116
117        return n;
118      }
119
120      void eraseIndex(int idx) {
121        int n = cross[idx];
122
123        if (items[n].prev != -1) {
124          items[items[n].prev].next = items[n].next;
125        } else {
126          first_item = items[n].next;
127        }
128        if (items[n].next != -1) {
129          items[items[n].next].prev = items[n].prev;
130        } else {
131          last_item = items[n].prev;
132        }
133
134        if (first_free_item != -1) {
135          items[first_free_item].prev = n;
136        }
137        items[n].next = first_free_item;
138        items[n].prev = -1;
139        first_free_item = n;
140
141        while (!cross.empty() && cross.back() == -1) {
142          cross.pop_back();
143        }
144      }
145
146      int maxIndex() const {
147        return cross.size() - 1;
148      }
149
150      void shiftIndices(int idx) {
151        for (int i = idx + 1; i < static_cast<int>(cross.size()); ++i) {
152          cross[i - 1] = cross[i];
153          if (cross[i] != -1) {
154            --items[cross[i]].index;
155          }
156        }
157        cross.back() = -1;
158        cross.pop_back();
159        while (!cross.empty() && cross.back() == -1) {
160          cross.pop_back();
161        }
162      }
163
164      void relocateIndex(int idx, int jdx) {
165        cross[idx] = cross[jdx];
166        items[cross[jdx]].index = idx;
167        cross[jdx] = -1;
168
169        while (!cross.empty() && cross.back() == -1) {
170          cross.pop_back();
171        }
172      }
173
174      int operator[](int idx) const {
175        return cross[idx];
176      }
177
178      int operator()(int fdx) const {
179        return items[fdx].index;
180      }
181
182      void firstItem(int& fdx) const {
183        fdx = first_item;
184      }
185
186      void nextItem(int& fdx) const {
187        fdx = items[fdx].next;
188      }
189
190    };
191  }
192}
193
194#endif
Note: See TracBrowser for help on using the repository browser.