deba@482: /* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@482:  *
deba@482:  * This file is a part of LEMON, a generic C++ optimization library.
deba@482:  *
alpar@1270:  * Copyright (C) 2003-2013
deba@482:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@482:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@482:  *
deba@482:  * Permission to use, modify and distribute this software is granted
deba@482:  * provided that this copyright notice appears in all copies. For
deba@482:  * precise terms see the accompanying LICENSE file.
deba@482:  *
deba@482:  * This software is provided "AS IS" with no warranty of any kind,
deba@482:  * express or implied, and with no claim as to its suitability for any
deba@482:  * purpose.
deba@482:  *
deba@482:  */
deba@482: 
deba@482: #ifndef LEMON_BITS_SOLVER_BITS_H
deba@482: #define LEMON_BITS_SOLVER_BITS_H
deba@482: 
deba@566: #include <vector>
deba@566: 
deba@482: namespace lemon {
deba@482: 
deba@482:   namespace _solver_bits {
deba@482: 
deba@482:     class VarIndex {
deba@482:     private:
deba@482:       struct ItemT {
deba@482:         int prev, next;
deba@482:         int index;
deba@482:       };
deba@482:       std::vector<ItemT> items;
deba@482:       int first_item, last_item, first_free_item;
deba@482: 
deba@482:       std::vector<int> cross;
deba@482: 
deba@482:     public:
deba@482: 
deba@482:       VarIndex()
deba@482:         : first_item(-1), last_item(-1), first_free_item(-1) {
deba@482:       }
deba@482: 
deba@482:       void clear() {
deba@482:         first_item = -1;
alpar@1140:         last_item = -1;
deba@482:         first_free_item = -1;
deba@482:         items.clear();
deba@482:         cross.clear();
deba@482:       }
deba@482: 
deba@482:       int addIndex(int idx) {
deba@482:         int n;
deba@482:         if (first_free_item == -1) {
deba@482:           n = items.size();
deba@482:           items.push_back(ItemT());
deba@482:         } else {
deba@482:           n = first_free_item;
deba@482:           first_free_item = items[n].next;
deba@482:           if (first_free_item != -1) {
deba@482:             items[first_free_item].prev = -1;
deba@482:           }
deba@482:         }
deba@482:         items[n].index = idx;
deba@482:         if (static_cast<int>(cross.size()) <= idx) {
deba@482:           cross.resize(idx + 1, -1);
deba@482:         }
deba@482:         cross[idx] = n;
deba@482: 
deba@482:         items[n].prev = last_item;
deba@482:         items[n].next = -1;
deba@482:         if (last_item != -1) {
deba@482:           items[last_item].next = n;
deba@482:         } else {
deba@482:           first_item = n;
deba@482:         }
deba@482:         last_item = n;
deba@482: 
deba@482:         return n;
deba@482:       }
deba@482: 
deba@482:       int addIndex(int idx, int n) {
deba@482:         while (n >= static_cast<int>(items.size())) {
deba@482:           items.push_back(ItemT());
deba@482:           items.back().prev = -1;
deba@482:           items.back().next = first_free_item;
deba@482:           if (first_free_item != -1) {
deba@482:             items[first_free_item].prev = items.size() - 1;
deba@482:           }
deba@482:           first_free_item = items.size() - 1;
deba@482:         }
deba@482:         if (items[n].next != -1) {
deba@482:           items[items[n].next].prev = items[n].prev;
deba@482:         }
deba@482:         if (items[n].prev != -1) {
deba@482:           items[items[n].prev].next = items[n].next;
deba@482:         } else {
deba@482:           first_free_item = items[n].next;
deba@482:         }
deba@482: 
deba@482:         items[n].index = idx;
deba@482:         if (static_cast<int>(cross.size()) <= idx) {
deba@482:           cross.resize(idx + 1, -1);
deba@482:         }
deba@482:         cross[idx] = n;
deba@482: 
deba@482:         items[n].prev = last_item;
deba@482:         items[n].next = -1;
deba@482:         if (last_item != -1) {
deba@482:           items[last_item].next = n;
deba@482:         } else {
deba@482:           first_item = n;
deba@482:         }
deba@482:         last_item = n;
deba@482: 
deba@482:         return n;
deba@482:       }
deba@482: 
deba@482:       void eraseIndex(int idx) {
deba@482:         int n = cross[idx];
deba@482: 
deba@482:         if (items[n].prev != -1) {
deba@482:           items[items[n].prev].next = items[n].next;
deba@482:         } else {
deba@482:           first_item = items[n].next;
deba@482:         }
deba@482:         if (items[n].next != -1) {
deba@482:           items[items[n].next].prev = items[n].prev;
deba@482:         } else {
deba@482:           last_item = items[n].prev;
deba@482:         }
deba@482: 
deba@482:         if (first_free_item != -1) {
deba@482:           items[first_free_item].prev = n;
deba@482:         }
deba@482:         items[n].next = first_free_item;
deba@482:         items[n].prev = -1;
deba@482:         first_free_item = n;
deba@482: 
deba@482:         while (!cross.empty() && cross.back() == -1) {
deba@482:           cross.pop_back();
deba@482:         }
deba@482:       }
deba@482: 
deba@482:       int maxIndex() const {
deba@482:         return cross.size() - 1;
deba@482:       }
deba@482: 
deba@482:       void shiftIndices(int idx) {
deba@482:         for (int i = idx + 1; i < static_cast<int>(cross.size()); ++i) {
deba@482:           cross[i - 1] = cross[i];
deba@482:           if (cross[i] != -1) {
deba@482:             --items[cross[i]].index;
deba@482:           }
deba@482:         }
deba@482:         cross.back() = -1;
deba@482:         cross.pop_back();
deba@482:         while (!cross.empty() && cross.back() == -1) {
deba@482:           cross.pop_back();
deba@482:         }
deba@482:       }
deba@482: 
deba@482:       void relocateIndex(int idx, int jdx) {
deba@482:         cross[idx] = cross[jdx];
deba@482:         items[cross[jdx]].index = idx;
deba@482:         cross[jdx] = -1;
deba@482: 
deba@482:         while (!cross.empty() && cross.back() == -1) {
deba@482:           cross.pop_back();
deba@482:         }
deba@482:       }
deba@482: 
deba@482:       int operator[](int idx) const {
deba@482:         return cross[idx];
deba@482:       }
deba@482: 
deba@482:       int operator()(int fdx) const {
deba@482:         return items[fdx].index;
deba@482:       }
deba@482: 
deba@482:       void firstItem(int& fdx) const {
deba@482:         fdx = first_item;
deba@482:       }
deba@482: 
deba@482:       void nextItem(int& fdx) const {
deba@482:         fdx = items[fdx].next;
deba@482:       }
deba@482: 
deba@482:     };
deba@482:   }
deba@482: }
deba@482: 
deba@482: #endif