2
\$\begingroup\$

Given a stack with N elements and a query Q, we need to find all elements of stack for which Q returns a specific value.

Time complexity should be less than \$O(N)\$.

Let's preprocess an element when we add it to cache.

The query will be represented by a static class, which has two members:

  • getGroup - a function which accepts an element of a stack and returns a query result
  • size - the query returns integers in range [0;size-1]

Input is from test.in and output goes to test.out.

#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
//Creates a class `className`, whcih stores elements of `elementType`, supports `numQueries` queries.
//Queries are represented by variadic arguments
#define MAKE_PREPROCESSING_STACK(className,elementType,numQueries, ...) \
class className\
{\
private:\
    /*A regular stack inside preprocessing stack*/\
    vector< elementType > * elements = new vector< elementType >();\
    /*Create a cache which stores all elements, those belong to a given (query,value) tuple*/\
    FOR##numQueries##CARRY1(NEW_QUERY_CACHE,elementType,__VA_ARGS__)\
public:\
    className () \
    { \
        /*Initiallize our cache with empty vectors*/\
        FOR##numQueries##CARRY1(INITIALIZE_QUERY_CACHE,elementType,__VA_ARGS__)\
    } \
    void push( elementType element ) \
    { \
        /*For each query we find, what value it returns for a new element and store the element in the cache for a given (query,value) tuple*/\
        elements->push_back(element); \
        FOR##numQueries##CARRY1(PUSH_ELEMENT_TO_CACHE,_,__VA_ARGS__)\
    } \
    void pop()\
    {\
        int lastIndex = elements->size()-1; \
        /*We find, what was the last added element. This was the purpose of elements vector*/\
        elementType element = (*elements)[lastIndex];\
        elements->pop_back();\
        /*So now we remove it from cache*/\
        FOR##numQueries##CARRY1(POP_ELEMENT_FROM_CACHE,_,__VA_ARGS__)\
    }\
    FOR##numQueries##CARRY1(MAKE_QUERY_API,elementType,__VA_ARGS__)\
    virtual ~ className () \
    { \
        delete elements;\
        /*Free resources used by cache*/\
        FOR##numQueries##CARRY1(DELETE_QUERY_CACHE,_,__VA_ARGS__)\
    } \
};
#define NEW_QUERY_CACHE(elementType,query) \
    vector< vector< elementType > >* elementsBy##query = new vector< vector< elementType > > ( query :: size );
#define INITIALIZE_QUERY_CACHE(elementType,query) \
    for (int i = 0; i < query :: size ; ++ i) \
        { \
            ( * elementsBy##query ) [i] = vector< elementType > (); \
        } 
#define PUSH_ELEMENT_TO_CACHE(_,query) (* elementsBy##query )[ query :: getGroup(element) ].push_back(element); 
#define POP_ELEMENT_FROM_CACHE(_,query) (* elementsBy##query )[ query :: getGroup(element) ].pop_back();    
#define MAKE_QUERY_API(elementType,query) \
    vector< elementType > * where##query (int groupNum) \
    { \
        return &((* elementsBy##query )[ groupNum ] ); \
    }
#define DELETE_QUERY_CACHE(_,query) delete elementsBy##query ;
#define FOR4CARRY1(processor,processorArg,e1,e2,e3,e4) processor (processorArg,e1) FOR3CARRY1( processor ,processorArg,e2,e3,e4)
#define FOR3CARRY1(processor,processorArg,e1,e2,e3) processor (processorArg,e1) FOR2CARRY1( processor ,processorArg,e2,e3)
#define FOR2CARRY1(processor,processorArg,e1,e2) processor (processorArg,e1) FOR1CARRY1( processor ,processorArg,e2)
#define FOR1CARRY1(processor,processorArg,e1) processor (processorArg,e1)
//---------------------------------------------------------------
// Below is example usage
//---------------------------------------------------------------

class DivisionBySevenRemainder
{
public:
    static const int size=7;
    static int getGroup(int x)
    {
        return x%7;
    }
};
class IsPrime
{
public:
    static const int size=2;
    static int getGroup(int x)
    {
        if(x<=1)
        {
            return 0;
        }
        if(x==2)
        {
            return 1;
        }
        float limit = sqrt((float)x)+1;
        for(int i = 2; i< limit; ++i)
        {
            if(x%i==0)
            {
                return 0;
            }
        }
        return 1;
    }
};
MAKE_PREPROCESSING_STACK(IntStack,int,2,DivisionBySevenRemainder,IsPrime)
void printStats(IntStack* integers)
{
    vector<int> primes = *(integers->whereIsPrime(1));
    vector<int> divisibleBySeven = *(integers->whereDivisionBySevenRemainder(0));
    for(vector<int>::iterator i = primes.begin(); i!= primes.end(); ++i)
    {
        printf("%d is prime\n",*i);
    }
    for(vector<int>::iterator i = divisibleBySeven.begin(); i!= divisibleBySeven.end(); ++i)
    {
        printf("%d is divisible by seven\n",*i);
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
#endif
    IntStack* integers=new IntStack();
    for(int i =0 ; i< 50 ;++ i)
    {
        integers->push(i);
    }
    printStats(integers);
    for(int i =0 ; i< 25 ;++ i)
    {
        integers->pop();
    }
    printf("\nPopped last 25\n\n");
    printStats(integers);
    delete integers;
    return 0;
}

It may introduce overhead in this example, but the closer size of a particular query to N, the more effective it becomes.

It's possible to get rid of the size parameter by introducing resizable vectors. And to redesign the class and specify that for some queries, the range of possible values is too big, and the cache for them should be an std::set inside of std::vector. And to implement preprocessing for min, map and other types of queries.

Personally I don't like the implementation with macro, but I think it's possible to make a data structure by specifying only which queries will be performed on it regularly.

\$\endgroup\$
2
\$\begingroup\$

Given a stack with N elements and a query Q, we need to find all elements of stack for which Q returns a specific value.

first couple of comments:

  1. this is a partition, not a filter: even when you're filtering primes, you still want optional access to non-prime values. Filters exclude values that don't match.
  2. your problem statement suggests a single, known query. You actually have an arbitrary number of partition criteria

Time complexity should be less than O(N).

You mean time complexity of lookups, for a given partition and value, right? Because all your other usually-cheap queue operations just became really expensive.

The query will be represented by a static class

That's not really a thing, although your examples make it clear what you mean.


Now, onto the code!

My first thought was that you could replace a lot of the preprocessor code with templates, much more cleanly. You might still have a top-level wrapper type using token pasting for the get##QUERYNAME methods, but it could defer all the actual meat to a templated container class exposing getByQuery(unsigned query, QueryKeyType key) methods.

My second thought is that Boost.MultiIndex can do all this for you already, so I'd focus on just writing the preprocessor wrapper for that if you really want the nicely-named accessors.

\$\endgroup\$
1
\$\begingroup\$

Not an answer to the question!

What the macro from the sample code unfolds into:

class IntStack {
    private:
        vector < int > * elements = new vector < int > ();
    vector < vector < int >> * elementsByDivisionBySevenRemainder = new vector < vector < int >> (DivisionBySevenRemainder::size);
    vector < vector < int >> * elementsByIsPrime = new vector < vector < int >> (IsPrime::size);
    public:
        IntStack() {
            for (int i = 0; i < DivisionBySevenRemainder::size; ++i) {
                ( * elementsByDivisionBySevenRemainder)[i] = vector < int > ();
            }
            for (int i = 0; i < IsPrime::size; ++i) {
                ( * elementsByIsPrime)[i] = vector < int > ();
            }
        }
    void push(int element) {
        elements - > push_back(element);
        ( * elementsByDivisionBySevenRemainder)[DivisionBySevenRemainder::getGroup(element)].push_back(element);
        ( * elementsByIsPrime)[IsPrime::getGroup(element)].push_back(element);
    }
    void pop() {
        int lastIndex = elements - > size() - 1;
        int element = ( * elements)[lastIndex];
        elements - > pop_back();
        ( * elementsByDivisionBySevenRemainder)[DivisionBySevenRemainder::getGroup(element)].pop_back();
        ( * elementsByIsPrime)[IsPrime::getGroup(element)].pop_back();
    }
    vector < int > * whereDivisionBySevenRemainder(int groupNum) {
        return &(( * elementsByDivisionBySevenRemainder)[groupNum]);
    }
    vector < int > * whereIsPrime(int groupNum) {
        return &(( * elementsByIsPrime)[groupNum]);
    }
    virtual~IntStack() {
        delete elements;
        delete elementsByDivisionBySevenRemainder;
        delete elementsByIsPrime;
    }
};

Note: Appears to work only with CLANG and gcc. Visual Studio e.g. fails to handle __VA_ARGS__ correctly.

Obviously the preprocessor output isn't even remotely that nicely formatted, so good luck debugging that!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.