Index: lemon/bits/lp_id.h
===================================================================
--- lemon/bits/lp_id.h	(revision 481)
+++ 	(revision )
@@ -1,157 +1,0 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library.
- *
- * Copyright (C) 2003-2008
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef LEMON_BITS_LP_SOLVER_ID_H
-#define LEMON_BITS_LP_SOLVER_ID_H
-
-namespace lemon {
-
-  namespace _lp_bits {
-
-    struct LpIdImpl {
-      std::vector<int> index;
-      std::vector<int> cross;
-      int first_index;
-      int first_free;
-    };
-
-    class LpId {
-    public:
-
-      class IdHandler {
-      public:
-        virtual ~IdHandler() {}
-        virtual int addId(LpIdImpl&) = 0;
-        virtual void eraseId(LpIdImpl&, int xn) = 0;
-      };
-
-      LpId(int min_index = 0) {
-        id_handler = 0;
-        impl.first_free = -1;
-        impl.first_index = min_index;
-        impl.cross.resize(impl.first_index);
-      }
-
-      LpId(const LpId& li) {
-        id_handler = 0;
-        impl = li.impl;
-      }
-
-      LpId& operator=(const LpId& li) {
-        id_handler = 0;
-        impl = li.impl;
-        return *this;
-      }
-
-      void setIdHandler(IdHandler& ih) {
-        id_handler = &ih;
-      }
-
-      int fixId(int fn) const {return impl.cross[fn];}
-      int floatingId(int xn) const {return impl.index[xn];}
-
-      int addId() {
-        if (id_handler == 0) {
-          int xn, fn = impl.cross.size();
-          if (impl.first_free == -1) {
-            xn = impl.index.size();
-            impl.index.push_back(fn);
-          } else {
-            xn = impl.first_free;
-            impl.first_free = impl.index[impl.first_free];
-            impl.index[xn] = fn;
-          }
-          impl.cross.push_back(xn);
-          return xn;
-        } else {
-          return id_handler->addId(impl);
-        }
-      }
-
-      void eraseId(int xn) {
-        if (id_handler == 0) {
-          int fn = impl.index[xn];
-          impl.index[xn] = impl.first_free;
-          impl.first_free = xn;
-          for(int i = fn + 1; i < int(impl.cross.size()); ++i) {
-            impl.cross[i - 1] = impl.cross[i];
-            impl.index[impl.cross[i]]--;
-          }
-          impl.cross.pop_back();
-        } else {
-          id_handler->eraseId(impl, xn);
-        }
-      }
-
-      void firstFloating(int& fn) const {
-        fn = impl.first_index;
-        if (fn == int(impl.cross.size())) fn = -1;
-      }
-
-      void nextFloating(int& fn) const {
-        ++fn;
-        if (fn == int(impl.cross.size())) fn = -1;
-      }
-
-      void firstFix(int& xn) const {
-        int fn;
-        firstFloating(fn);
-        xn = fn != -1 ? fixId(fn) : -1;
-      }
-
-      void nextFix(int& xn) const {
-        int fn = floatingId(xn);
-        nextFloating(fn);
-        xn = fn != -1 ? fixId(fn) : -1;
-      }
-
-    protected:
-      LpIdImpl impl;
-      IdHandler *id_handler;
-    };
-
-    class RelocateIdHandler : public LpId::IdHandler {
-    public:
-
-      virtual int addId(LpIdImpl& impl) {
-        int xn, fn = impl.cross.size();
-        if (impl.first_free == -1) {
-          xn = impl.index.size();
-          impl.index.push_back(fn);
-        } else {
-          xn = impl.first_free;
-          impl.first_free = impl.index[impl.first_free];
-          impl.index[xn] = fn;
-        }
-        impl.cross.push_back(xn);
-        return xn;
-      }
-
-      virtual void eraseId(LpIdImpl& impl, int xn) {
-        int fn = impl.index[xn];
-        impl.index[xn] = impl.first_free;
-        impl.first_free = xn;
-        impl.cross[fn] = impl.cross.back();
-        impl.index[impl.cross.back()] = fn;
-        impl.cross.pop_back();
-      }
-    };
-  }
-}
-
-#endif
Index: lemon/bits/solver_bits.h
===================================================================
--- lemon/bits/solver_bits.h	(revision 482)
+++ lemon/bits/solver_bits.h	(revision 482)
@@ -0,0 +1,191 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2008
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_BITS_SOLVER_BITS_H
+#define LEMON_BITS_SOLVER_BITS_H
+
+namespace lemon {
+
+  namespace _solver_bits {
+
+    class VarIndex {
+    private:
+      struct ItemT {
+        int prev, next;
+        int index;
+      };
+      std::vector<ItemT> items;
+      int first_item, last_item, first_free_item;
+
+      std::vector<int> cross;
+
+    public:
+
+      VarIndex()
+        : first_item(-1), last_item(-1), first_free_item(-1) {
+      }
+
+      void clear() {
+        first_item = -1;
+        first_free_item = -1;
+        items.clear();
+        cross.clear();
+      }
+
+      int addIndex(int idx) {
+        int n;
+        if (first_free_item == -1) {
+          n = items.size();
+          items.push_back(ItemT());
+        } else {
+          n = first_free_item;
+          first_free_item = items[n].next;
+          if (first_free_item != -1) {
+            items[first_free_item].prev = -1;
+          }
+        }
+        items[n].index = idx;
+        if (static_cast<int>(cross.size()) <= idx) {
+          cross.resize(idx + 1, -1);
+        }
+        cross[idx] = n;
+
+        items[n].prev = last_item;
+        items[n].next = -1;
+        if (last_item != -1) {
+          items[last_item].next = n;
+        } else {
+          first_item = n;
+        }
+        last_item = n;
+
+        return n;
+      }
+
+      int addIndex(int idx, int n) {
+        while (n >= static_cast<int>(items.size())) {
+          items.push_back(ItemT());
+          items.back().prev = -1;
+          items.back().next = first_free_item;
+          if (first_free_item != -1) {
+            items[first_free_item].prev = items.size() - 1;
+          }
+          first_free_item = items.size() - 1;
+        }
+        if (items[n].next != -1) {
+          items[items[n].next].prev = items[n].prev;
+        }
+        if (items[n].prev != -1) {
+          items[items[n].prev].next = items[n].next;
+        } else {
+          first_free_item = items[n].next;
+        }
+
+        items[n].index = idx;
+        if (static_cast<int>(cross.size()) <= idx) {
+          cross.resize(idx + 1, -1);
+        }
+        cross[idx] = n;
+
+        items[n].prev = last_item;
+        items[n].next = -1;
+        if (last_item != -1) {
+          items[last_item].next = n;
+        } else {
+          first_item = n;
+        }
+        last_item = n;
+
+        return n;
+      }
+
+      void eraseIndex(int idx) {
+        int n = cross[idx];
+
+        if (items[n].prev != -1) {
+          items[items[n].prev].next = items[n].next;
+        } else {
+          first_item = items[n].next;
+        }
+        if (items[n].next != -1) {
+          items[items[n].next].prev = items[n].prev;
+        } else {
+          last_item = items[n].prev;
+        }
+
+        if (first_free_item != -1) {
+          items[first_free_item].prev = n;
+        }
+        items[n].next = first_free_item;
+        items[n].prev = -1;
+        first_free_item = n;
+
+        while (!cross.empty() && cross.back() == -1) {
+          cross.pop_back();
+        }
+      }
+
+      int maxIndex() const {
+        return cross.size() - 1;
+      }
+
+      void shiftIndices(int idx) {
+        for (int i = idx + 1; i < static_cast<int>(cross.size()); ++i) {
+          cross[i - 1] = cross[i];
+          if (cross[i] != -1) {
+            --items[cross[i]].index;
+          }
+        }
+        cross.back() = -1;
+        cross.pop_back();
+        while (!cross.empty() && cross.back() == -1) {
+          cross.pop_back();
+        }
+      }
+
+      void relocateIndex(int idx, int jdx) {
+        cross[idx] = cross[jdx];
+        items[cross[jdx]].index = idx;
+        cross[jdx] = -1;
+
+        while (!cross.empty() && cross.back() == -1) {
+          cross.pop_back();
+        }
+      }
+
+      int operator[](int idx) const {
+        return cross[idx];
+      }
+
+      int operator()(int fdx) const {
+        return items[fdx].index;
+      }
+
+      void firstItem(int& fdx) const {
+        fdx = first_item;
+      }
+
+      void nextItem(int& fdx) const {
+        fdx = items[fdx].next;
+      }
+
+    };
+  }
+}
+
+#endif
