Repository files navigation

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 itcompresses the bottom part (only stores partial information). This information is recomputed whenever it is needed afterwards. See the paper ofBarbaet al. for more details on this structure. More information about the implementation can be found inBaffieret al.

Please consult thewiki of this project for further details such as : speed and memory consumption tests, more details about installation, examples, and more.

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<classT,classD>void StackAlgo<T, D>::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();}

Concrete examples such as a basic test run and the upper hull problems can be found in thewiki.

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.classInstance:publicStackAlgo<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  DreadInput(std::vector<std::string> line);  std::shared_ptr<T>initStack();boolpopCondition(D data);voidprePop(D data);voidpostPop(D data, Data<T, D, I> elt);voidnoPop(D data);boolpushCondition(D data);voidprePush(Data<T, D, I> elt);voidpostPush(Data<T, D, I> elt);voidnoPush(D data);voidreportStack();};

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

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

This project is far from being complete and would benefit greatly from future contributions. Commented code, following the existing file structure is strongly preferred. Please contact one of the author (or create an issue) in case of need. Here is a short sample of possible contributions :

• Use CI (continuous integration). Definitively the most wanted feature
• Extends the compressed stack structure to a dequeue structure (push and pop from top and bottom)
• Add other problems to the examples folder (following, if possible a similar structure)
• Extends the compressed stack structure to a compressed tree search structure
• Dynamic size compressed stack.

Although this project is a joint work, based on the theoretical work inBarbaet al., credits belong to specific authors for part of the implementation. The work covering the implementation of the Stack Algorithm framework, the Compressed Stack structure and extras functionalities (include andextras repositories) has been done byJean-Francois Baffier. All the examples and their generating algorithms, along with all the test have been implemented byYago Diez. The class design and project overview was done byMatias Korman

This project is an open source software under the MIT license. Please check theLICENSE file for further information.