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