COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/solver_bits.h @ 969:6dd226d3dcba

Last change on this file since 969:6dd226d3dcba was 956:141f9c0db4a3, checked in by Alpar Juttner <alpar@…>, 15 years ago

Unify the sources (#339)

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-2010
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        first_free_item = -1;
48        items.clear();
49        cross.clear();
50      }
51
52      int addIndex(int idx) {
53        int n;
54        if (first_free_item == -1) {
55          n = items.size();
56          items.push_back(ItemT());
57        } else {
58          n = first_free_item;
59          first_free_item = items[n].next;
60          if (first_free_item != -1) {
61            items[first_free_item].prev = -1;
62          }
63        }
64        items[n].index = idx;
65        if (static_cast<int>(cross.size()) <= idx) {
66          cross.resize(idx + 1, -1);
67        }
68        cross[idx] = n;
69
70        items[n].prev = last_item;
71        items[n].next = -1;
72        if (last_item != -1) {
73          items[last_item].next = n;
74        } else {
75          first_item = n;
76        }
77        last_item = n;
78
79        return n;
80      }
81
82      int addIndex(int idx, int n) {
83        while (n >= static_cast<int>(items.size())) {
84          items.push_back(ItemT());
85          items.back().prev = -1;
86          items.back().next = first_free_item;
87          if (first_free_item != -1) {
88            items[first_free_item].prev = items.size() - 1;
89          }
90          first_free_item = items.size() - 1;
91        }
92        if (items[n].next != -1) {
93          items[items[n].next].prev = items[n].prev;
94        }
95        if (items[n].prev != -1) {
96          items[items[n].prev].next = items[n].next;
97        } else {
98          first_free_item = items[n].next;
99        }
100
101        items[n].index = idx;
102        if (static_cast<int>(cross.size()) <= idx) {
103          cross.resize(idx + 1, -1);
104        }
105        cross[idx] = n;
106
107        items[n].prev = last_item;
108        items[n].next = -1;
109        if (last_item != -1) {
110          items[last_item].next = n;
111        } else {
112          first_item = n;
113        }
114        last_item = n;
115
116        return n;
117      }
118
119      void eraseIndex(int idx) {
120        int n = cross[idx];
121
122        if (items[n].prev != -1) {
123          items[items[n].prev].next = items[n].next;
124        } else {
125          first_item = items[n].next;
126        }
127        if (items[n].next != -1) {
128          items[items[n].next].prev = items[n].prev;
129        } else {
130          last_item = items[n].prev;
131        }
132
133        if (first_free_item != -1) {
134          items[first_free_item].prev = n;
135        }
136        items[n].next = first_free_item;
137        items[n].prev = -1;
138        first_free_item = n;
139
140        while (!cross.empty() && cross.back() == -1) {
141          cross.pop_back();
142        }
143      }
144
145      int maxIndex() const {
146        return cross.size() - 1;
147      }
148
149      void shiftIndices(int idx) {
150        for (int i = idx + 1; i < static_cast<int>(cross.size()); ++i) {
151          cross[i - 1] = cross[i];
152          if (cross[i] != -1) {
153            --items[cross[i]].index;
154          }
155        }
156        cross.back() = -1;
157        cross.pop_back();
158        while (!cross.empty() && cross.back() == -1) {
159          cross.pop_back();
160        }
161      }
162
163      void relocateIndex(int idx, int jdx) {
164        cross[idx] = cross[jdx];
165        items[cross[jdx]].index = idx;
166        cross[jdx] = -1;
167
168        while (!cross.empty() && cross.back() == -1) {
169          cross.pop_back();
170        }
171      }
172
173      int operator[](int idx) const {
174        return cross[idx];
175      }
176
177      int operator()(int fdx) const {
178        return items[fdx].index;
179      }
180
181      void firstItem(int& fdx) const {
182        fdx = first_item;
183      }
184
185      void nextItem(int& fdx) const {
186        fdx = items[fdx].next;
187      }
188
189    };
190  }
191}
192
193#endif
Note: See TracBrowser for help on using the repository browser.