Home

CompressedStacks.cpp: Basics

The CompressedStacks.cpp module/library implements the compressed stack structure. This data structure behaves like a usual stack with the usual push and pop operations but has the additional advantage that it uses less memory. Intuitively, when large blocks of information are pushed into the stack it compresses the bottom part (only stores partial information). This information is recomputed whenever it is needed afterward. See the paper of Barba et al. for more details on this structure. More information about the implementation can be found in Baffier et al.

Description of Stack Algorithms

This structure works mostly as a normal stack (handling push and pop operations, as well as being able to access the top k elements of the stack, for some small k). Note that this structure can only be used with sequential deterministic algorithms. We model these algorithms with the template StackAlgo whose only implemented function implemented is the run operation in which we scan the whole input (see code below).

template <class T, class D, class I> void StackAlgo<T, D, I>::run() {
  initStack();
  while (notEndOfFile()) {
    D data = readInput(line);
    while (notEmptystack()) {
      if (popCondition(data)) {
        prePop(data);
        elt = pop();
        postPop(elt,data);
      } else {
        noPop(data);
      }
    }
    if (pushCondition(data)) {
      prePush(data);
      push(data);
      postPush(data);
    } else {
      noPush(data);
    }
  }
  reportStack();
}

Use case

Concrete examples such as a basic test run and the upper hull problem can be found in the example section of this wiki.

Abstract example : Instance<T, D, I>

An instance of a Stack Algorithm is described by a set of templates parameters T, D, and I and a set of methods used in the run function above.

// T is the type of the context, D is the type of the input data and I is the type of your integer indexes.

class Instance: public StackAlgo<T, D, I>{
public:
  Instance(std::string filePath) : StackAlgo<T, D, I>(filePath) {}
private:
  // Methods to implement according to the problem and input structure
  // Some of those methods might be left empty
  D readInput(std::vector<std::string> line);
  std::shared_ptr<T> initStack();

  bool popCondition(D data);
  void prePop(D data);
  void postPop(D data, Data<T, D, I> elt);
  void noPop(D data);

  bool pushCondition(D data);
  void prePush(Data<T, D, I> elt);
  void postPush(Data<T, D, I> elt);
  void noPush(D data);

  void reportStack();
};

How to run your problem

Suppose the class Instance implements the interface StackAlgo<T, D, I>. You can run an instance of your problem described in the input located at filepath. The last command just prints an output in the console of your compressed stack after the run.

Instance stack(filePath);
stack.run();
stack.println();