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