source: lemon/lemon/bits/solver_bits.h @ 969:6dd226d3dcba

/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2010
 * 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

#include <vector>

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