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-2013
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 
24 namespace 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 
VarIndex()41       VarIndex()
42         : first_item(-1), last_item(-1), first_free_item(-1) {
43       }
44 
clear()45       void clear() {
46         first_item = -1;
47         last_item = -1;
48         first_free_item = -1;
49         items.clear();
50         cross.clear();
51       }
52 
addIndex(int idx)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 
addIndex(int idx,int n)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 
eraseIndex(int idx)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 
maxIndex()146       int maxIndex() const {
147         return cross.size() - 1;
148       }
149 
shiftIndices(int idx)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 
relocateIndex(int idx,int jdx)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 
operator()178       int operator()(int fdx) const {
179         return items[fdx].index;
180       }
181 
firstItem(int & fdx)182       void firstItem(int& fdx) const {
183         fdx = first_item;
184       }
185 
nextItem(int & fdx)186       void nextItem(int& fdx) const {
187         fdx = items[fdx].next;
188       }
189 
190     };
191   }
192 }
193 
194 #endif
195