-
Notifications
You must be signed in to change notification settings - Fork 1
Home
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.
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();
}
Concrete examples such as a basic test run and the upper hull problem can be found in the example section of this wiki.
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();
};
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();