?

Log in

aliakseis' Journal
 
[Most Recent Entries] [Calendar View] [Friends]

Below are the 20 most recent journal entries recorded in aliakseis' LiveJournal:

[ << Previous 20 ]
Tuesday, September 22nd, 2015
3:45 pm
Thursday, April 9th, 2015
12:45 pm
Напишут наши имена...
"Its ExhaustiveDfsStrategy scores 20086, which is the same score as the
winning program by Aliaksei Sanko.

20086 has to be the optimal (lowest possible) result, because it was found by
an exhaustive search. That run took 10.5 CPU hours. (see details file)"

Здесь.
Sunday, November 2nd, 2014
2:26 pm
И снова у Матрицы сбой...
Сервис music.torchbrowser.com в принципе хорош, но грешит подсовыванием случайных видео, иногда с "чувством юмора". Так, вместо "On the Road Again" он предложил это видео:

Оно мне, впрочем, знакомо. Однако я был несколько удивлён, выйдя на улицу и увидев:
Wednesday, October 29th, 2014
11:45 pm
Opus #17 (was: Facebull)
#include <stdio.h>
#include <assert.h>

#include <cstddef>
#include <iostream>
#include <queue>
#include <map>
#include <string>
#include <vector>
#include <algorithm>

using std::cerr;
using std::cout;
using std::map;
using std::string;
using std::vector;


struct Plex     // Similar to MFC CPlex
    // warning variable length structure
{
    Plex* pNext;
    int dwReserved[1];    // align on 8 byte boundary

    void* data() { return this+1; }

    // like 'calloc' but no zero fill
    // may throw memory exceptions
    static Plex* Create(Plex*& pHead, size_t nMax, size_t cbElement)
    {
        assert(nMax > 0 && cbElement > 0);
        Plex* p = (Plex*) operator new(sizeof(Plex) + nMax * cbElement);
        // may throw exception
        p->pNext = pHead;
        pHead = p;  // change head (adds in reverse order for simplicity)
        return p;
    }

    void FreeDataChain()       // free this one and links
    {
        Plex* p = this;
        while (p != 0)
        {
            void* bytes = p;
            p = p->pNext;
            operator delete(bytes);
        }
    }
};

typedef unsigned int UINT;

class FixedAlloc    // Similar to MFC CFixedAlloc
{
    // Constructors
public:
    FixedAlloc(UINT nAllocSize, UINT nBlockSize = 64);

    // Attributes
    UINT GetAllocSize() { return m_nAllocSize; }

    // Operations
public:
    void* Alloc();  // return a chunk of memory of nAllocSize
    void Free(void* p); // free chunk of memory returned from Alloc
    void FreeAll(); // free everything allocated from this allocator

    // Implementation
public:
    ~FixedAlloc();

protected:
    struct CNode
    {
        CNode* pNext;	// only valid when in free list
    };

    UINT m_nAllocSize;	// size of each block from Alloc
    UINT m_nBlockSize;	// number of blocks to get at a time
    Plex* m_pBlocks;	// linked list of blocks (is nBlocks*nAllocSize)
    CNode* m_pNodeFree;	// first free node (0 if no free nodes)
};

FixedAlloc::FixedAlloc(UINT nAllocSize, UINT nBlockSize)
{
    assert(nAllocSize >= sizeof(CNode));
    assert(nBlockSize > 1);

    if (nAllocSize < sizeof(CNode))
        nAllocSize = sizeof(CNode);
    if (nBlockSize <= 1)
        nBlockSize = 64;

    m_nAllocSize = nAllocSize;
    m_nBlockSize = nBlockSize;
    m_pNodeFree = 0;
    m_pBlocks = 0;
}

FixedAlloc::~FixedAlloc()
{
    FreeAll();
}

void FixedAlloc::FreeAll()
{
    m_pBlocks->FreeDataChain();
    m_pBlocks = 0;
    m_pNodeFree = 0;
}

void* FixedAlloc::Alloc()
{
    if (m_pNodeFree == 0)
    {
        // add another block
        Plex* pNewBlock = Plex::Create(m_pBlocks, m_nBlockSize, m_nAllocSize);

        // chain them into free list
        // free in reverse order to make it easier to debug
        char* pData = (char*) pNewBlock->data() + m_nAllocSize * (m_nBlockSize - 1);
        for (int i = m_nBlockSize; i > 0; i--, pData -= m_nAllocSize)
        {
            CNode* pNode = (CNode*) pData;
            pNode->pNext = m_pNodeFree;
            m_pNodeFree = pNode;
        }
    }
    assert(m_pNodeFree != 0);  // we must have something

    // remove the first available node from the free list
    void* pNode = m_pNodeFree;
    m_pNodeFree = m_pNodeFree->pNext;
    return pNode;
}

void FixedAlloc::Free(void* p)
{
    if (p != 0)
    {
        // simply return the node to the free list
        CNode* pNode = (CNode*)p;
        pNode->pNext = m_pNodeFree;
        m_pNodeFree = pNode;
    }
}



struct Machine
{
    unsigned int number;
    unsigned int price;
    unsigned int compound1idx;
    unsigned int compound1flg;
    unsigned int compound2idx;
    unsigned int compound2flg;
};

inline bool operator < (const Machine& m1, const Machine& m2)
{
    return m1.price < m2.price;
}

map<string, int> compoundsMapping;

int compoundIndex = 0;

int GetCompoundIndex(const char* number)
{
    int result;

    map<string, int>::iterator lb = compoundsMapping.lower_bound(number);
    if (lb != compoundsMapping.end() && !compoundsMapping.key_comp()(number, lb->first))
        result = lb->second;
    else
    {
        result = compoundIndex++;
        typedef map<string, int>::value_type MVT;
        compoundsMapping.insert(lb, MVT(number, result));
    }

    return result;
}

vector<Machine> machinesByInIdx[32];

enum { HASH_BITS = 21, HASH_SIZE = 1 << HASH_BITS };


struct VertexKey
{
    unsigned int body;
    unsigned int tails;

    int hash() const
    {
        return (unsigned int)(((body << 1) ^ tails) * 2654435769U) >> (32 - HASH_BITS);
    }
};

inline bool operator == (const VertexKey& left, const VertexKey& right)
{
    return left.body == right.body && left.tails == right.tails;
}


struct Vertex
{
    Vertex* next;
    VertexKey key;
    union
    {
        unsigned int data[2];
        const Vertex* parent;
        std::size_t projection;
    };

    bool visited() { return (projection & 1u) == 0; }
    unsigned int estimate() { return data[data[1] > data[0]]; }

    bool empty() const { return key.body == 0 && key.tails == 0; }

    void* operator new(size_t size)
    {
        assert(size == s_alloc.GetAllocSize());
        return s_alloc.Alloc();
    }
    void* operator new(size_t, void* p) { return p; }
    void operator delete(void* p) { s_alloc.Free(p); }

protected:
    static FixedAlloc s_alloc;
};

FixedAlloc Vertex::s_alloc(sizeof(Vertex), 64);

Vertex hashTable[HASH_SIZE];

unsigned int estimates[32];
unsigned int estimates2[32];

class Priority
{
friend bool operator < (const Priority& left, const Priority& right);
public:
    Vertex* vertex;
    Vertex* parent;
    unsigned int weight() { return weight_finishing >> 1; }
    bool finishing() { return !(weight_finishing & 1u); }
    Priority(Vertex* vertex_, Vertex* parent_, unsigned int weight_, bool finishing_)
        : vertex(vertex_), parent(parent_), weight_finishing((weight_ << 1) + !finishing_) {}
private:
    unsigned int weight_finishing;
};

inline bool operator < (const Priority& left, const Priority& right)
{
    return left.weight_finishing > right.weight_finishing;
}



Vertex* findItem(const VertexKey& newKey, int idx)
{
    Vertex* vertex = hashTable + idx;
    if (!vertex->empty())
    {
        do
        {
            if (vertex->key == newKey)
            {
                return vertex;
            }
            vertex = vertex->next;
        }
        while (vertex != 0);
    }

    return 0;
}

bool findSubstitute(const VertexKey& key, unsigned int estimate)
{
    if (key.tails > 1)
    {
        VertexKey newKey = { key.body & ~(key.tails - 1), 1 };

        Vertex* v = findItem(newKey, newKey.hash());
        if (v != 0)
        {
            if (v->estimate() <= estimate)
            {
                return true;
            }
        }
    }

    return false;
}

unsigned int mask;

unsigned int minFinishing = 0xFFFFFFFF;

typedef std::priority_queue<Priority> PriorityQueue;

enum Destination { notDef, tails, body, nowhere };

template<bool inBody>
bool getNextKey(const Machine& machine, const VertexKey& key, 
                const Vertex* parent, VertexKey& newKey, Destination& destination)
{
    const bool inTails = !inBody;

    const bool outBody = !(key.body & machine.compound2flg);
    if (inBody && outBody)
    {
        return false;
    }
    const bool outTails = !!(key.tails & machine.compound2flg);
    if (inBody && outTails)
    {
        return false;
    }
    if (inTails && outTails && machine.compound2flg != 1)
    {
        return false;
    }
    if (inTails && outBody && machine.compound2flg != 1)
    {
        if ((key.tails & 1) == 0)
        {
            return false;
        }

        if (parent)
        {
            bool wasOutBody = false;
            // tricky
            for (const Vertex* v = parent; v != 0; v = v->parent)
            {
                if (1 == v->key.tails)
                {
                    wasOutBody = !(v->key.body & machine.compound2flg);
                    break;
                }
            }
            if (!wasOutBody)
            {
                return false;
            }
        }
    }

    if (inBody && (key.tails & 1) != 0 && parent != 0)
    {
        const Vertex* v = parent;
        const Vertex* parent = v->parent;

        if ((v->key.tails & 1) != 0)
        {
            do 
            {
                if (parent->key.tails == 1 && v->key.tails > 1)
                {
                    if (v->key.tails < (machine.compound2flg | 1) 
                        && !(parent->key.body & machine.compound1flg))
                    {
                        return false;
                    }
                    break;
                }

                v = parent;
                parent = v->parent;
            } 
            while (parent != 0);
        }
    }

    assert(!(inBody && inTails));
    assert(!(outBody && outTails));

    newKey = key;
    if (inBody)
    {
        assert(!outBody && !outTails);
        newKey.tails |= machine.compound2flg;
    }
    else
    {
        newKey.body &= ~machine.compound1flg;
        newKey.tails &= ~machine.compound1flg;
        if (!outBody)
        {
            newKey.tails |= machine.compound2flg;
        }
    }

    assert(0 == (~newKey.body & newKey.tails));

    destination = outBody? body: (outTails? tails : nowhere);

    return true;
}


bool checkVertex(const VertexKey& key, const Vertex* parent)
{
    const unsigned int flag = key.tails & ~1;

    const int idx = ((unsigned int)(flag * 0x077CB531U)) >> 27;

    for (vector<Machine>::iterator it(machinesByInIdx[idx].begin()), itEnd(machinesByInIdx[idx].end()); it != itEnd; ++it)
    {
        const Machine& machine = *it;
        VertexKey newKey;
        Destination destination;
        if (!getNextKey<false>(machine, key, parent, newKey, destination))
        {
            continue;
        }

        if (newKey.tails == 1) // in body
        {
            return true;
        }

        Vertex link;
        link.key = key;
        link.parent = parent;
        if (checkVertex(newKey, &link))
        {
            return true;
        }
    }

    return false;
}


template<bool inBody>
bool evaluateVertex(const VertexKey& key, const unsigned int data[2], const Vertex* parent)
{
    bool result = false;

    const bool inTails = !inBody;
    unsigned int inFlags = inBody ? (mask ^ key.body) : (key.tails & ~1);
    while (inFlags)
    {
        const unsigned int buffer = inFlags & (inFlags - 1);
        const unsigned int flag = inFlags - buffer;
        inFlags = buffer;

        const int idx = ((unsigned int)(flag * 0x077CB531U)) >> 27;

        for (vector<Machine>::iterator it(machinesByInIdx[idx].begin()), itEnd(machinesByInIdx[idx].end())
            ; it != itEnd
            ; ++it)
        {
            const Machine& machine = *it;
            VertexKey newKey;
            Destination destination;
            if (!getNextKey<inBody>(machine, key, parent, newKey, destination))
            {
                continue;
            }


            unsigned int data0 = data[0] + machine.price;
            if (inTails)
            {
                data0 -= estimates[machine.compound1idx];
            }
            unsigned int data1 = data[1] + machine.price;
            if (nowhere == destination)
            {
                data1 -= estimates2[machine.compound2idx];
            }

            const bool finishing = 1 == newKey.body && 1 == newKey.tails;

            const unsigned int estimate = std::max(data0, data1);
            if (estimate >= minFinishing)
            {
                continue;
            }

            if (finishing)
            {
                if (minFinishing > estimate)
                {
                    result = true;
                    minFinishing = estimate;
                }
                continue;
            }


            unsigned int newData[2];
            newData[0] = data0;
            newData[1] = data1;

            Vertex link;
            link.key = key;
            link.parent = parent;

            bool ok = (newKey.tails == 1) // in body
                ? evaluateVertex<true>(newKey, newData, &link)
                : evaluateVertex<false>(newKey, newData, &link);

            result = result || ok;
        }
    }

    return result;
}

void reportSolution(const Vertex* vertex, const Vertex* parent, unsigned int extraMachine = 0xFFFFFFFF)
{
    vector<unsigned int> bestPath;

    if (extraMachine != 0xFFFFFFFF)
        bestPath.push_back(extraMachine);

    do 
    {
        unsigned int number;
        unsigned int price = 0xFFFFFFFF;

        const bool inBody = parent->key.tails == 1;


        const VertexKey& key = parent->key;
        unsigned int inFlags = inBody ? (mask ^ key.body) : (key.tails & ~1);
        while (inFlags)
        {
            const unsigned int buffer = inFlags & (inFlags - 1);
            const unsigned int flag = inFlags - buffer;
            inFlags = buffer;

            const int idx = ((unsigned int)(flag * 0x077CB531U)) >> 27;

            for (vector<Machine>::iterator it(machinesByInIdx[idx].begin()), itEnd(machinesByInIdx[idx].end())
                ; it != itEnd
                ; ++it)
            {
                const Machine& machine = *it;
                VertexKey newKey;
                Destination destination;
                const bool ok = inBody
                    ? getNextKey<true>(machine, key, parent->parent, newKey, destination)
                    : getNextKey<false>(machine, key, parent->parent, newKey, destination);
                if (!ok)
                {
                    continue;
                }

                if (newKey == vertex->key && machine.price < price)
                {
                    price = machine.price;
                    number = machine.number;
                }
            }
        }

        bestPath.push_back(number);

        vertex = parent;
        parent = vertex->parent;
    } 
    while (parent != 0);

    std::sort(bestPath.begin(), bestPath.end());
    cout << bestPath[0];
    for (unsigned int i = 1; i < bestPath.size(); ++i)
        cout << ' ' << bestPath[i];
    cout << '\n';
}


inline bool reachedEstimation(unsigned int body)
{
    unsigned int temp = ((body - 1) & (body - 2));
    unsigned int temp2 = (temp & (temp - 1));
    return 0 == (temp2 & (temp2 - 1));
}


template<bool inBody>
void handleVertex(const Priority& priority, PriorityQueue& queue)
{
    const VertexKey& key = priority.vertex->key;
    const bool inTails = !inBody;
    unsigned int inFlags = inBody ? (mask ^ key.body) : (key.tails & ~1);
    while (inFlags)
    {
        const unsigned int buffer = inFlags & (inFlags - 1);
        const unsigned int flag = inFlags - buffer;
        inFlags = buffer;

        const int idx = ((unsigned int)(flag * 0x077CB531U)) >> 27;

        for (vector<Machine>::iterator it(machinesByInIdx[idx].begin()), itEnd(machinesByInIdx[idx].end()); it != itEnd; ++it)
        {
            const Machine& machine = *it;
            VertexKey newKey;
            Destination destination;
            if (!getNextKey<inBody>(machine, key, priority.parent, newKey, destination))
            {
                continue;
            }

            unsigned int data[] = 
            {
                priority.vertex->data[0] + machine.price,
                priority.vertex->data[1] + machine.price,
            };
            if (inTails)
            {
                data[0] -= estimates[machine.compound1idx];
            }
            if (nowhere == destination)
            {
                data[1] -= estimates2[machine.compound2idx];
            }

            const bool finishing = 1 == newKey.body && 1 == newKey.tails;

            const unsigned int estimate = std::max(data[0], data[1]);
            if (estimate > minFinishing)
            {
                continue;
            }

            const int idx = newKey.hash();
            Vertex* v = findItem(newKey, idx);
            if (v && v->visited())
            {
                continue;
            }
            if (v && v->estimate() <= estimate)
            {
                continue;
            }
            if (findSubstitute(newKey, estimate))
            {
                continue;
            }

            if (finishing && minFinishing > estimate)
            {
                minFinishing = estimate;
            }

            if (!inBody && newKey.tails != 1)
            {
                // check if it reaches body
                if (!checkVertex(newKey, priority.parent))
                {
                    continue;
                }
            }

            if (reachedEstimation(newKey.body) && !reachedEstimation(key.body) && !finishing)
            {
                Vertex link;
                link.key = key;
                link.parent = priority.parent;

                (newKey.tails == 1) // in body
                    ? evaluateVertex<true>(newKey, data, &link)
                    : evaluateVertex<false>(newKey, data, &link);
            }

            if (!v)
            {
                if (hashTable[idx].empty())
                {
                    v = hashTable + idx;
                }
                else
                {
                    v = new Vertex();
                    v->next = hashTable[idx].next;
                    hashTable[idx].next = v;
                }
                v->key = newKey;
            }

            v->data[0] = data[0];
            v->data[1] = data[1];
            queue.push(Priority(v, priority.vertex, estimate, finishing));
        }
    }
}



int main(int argc, char* argv[])
{
    if (argc != 2)
    {
        cerr << "Usage: " << argv[0] << " input_file\n";
        return 1;
    }
    FILE* f = fopen(argv[1], "r");

    Machine machine;
    char compound1[1024];
    char compound2[1024];

    for (unsigned int i = 0; i < sizeof(estimates) / sizeof(estimates[0]); ++i)
    {
        estimates[i] = 0x7FFFFFFF;
    }
    for (unsigned int i = 0; i < sizeof(estimates2) / sizeof(estimates2[0]); ++i)
    {
        estimates2[i] = 0x7FFFFFFF;
    }

    int numMachines = 0;
    while (4 == fscanf(f, "M%d %s %s %d\n", &machine.number, compound1, compound2, &machine.price))
    {
        machine.price *= 2;

        int compound1idx = GetCompoundIndex(compound1);
        if (0 == compound1idx)
        {
            compound1idx = 31;
        }
        machine.compound1idx = compound1idx;
        machine.compound1flg = 1u << compound1idx;
        machine.compound2idx = GetCompoundIndex(compound2);
        machine.compound2flg = 1u << machine.compound2idx;

        if (estimates[compound1idx] > machine.price)
        {
            estimates[compound1idx] = machine.price;
        }

        if (estimates2[machine.compound2idx] > machine.price)
        {
            estimates2[machine.compound2idx] = machine.price;
        }

        const int idx = ((unsigned int)(machine.compound1flg * 0x077CB531U)) >> 27;

        bool found = false;
        for (vector<Machine>::iterator it(machinesByInIdx[idx].begin()), itEnd(machinesByInIdx[idx].end())
            ; it != itEnd
            ; ++it)
        {
            if (it->compound1flg == machine.compound1flg && it->compound2flg == machine.compound2flg)
            {
                found = true;
                if (it->price > machine.price)
                {
                    it->price = machine.price;
                    it->number = machine.number;
                }

                break;
            }
        }

        if (!found)
        {
            machinesByInIdx[idx].push_back(machine);
            ++numMachines;
        }
    }

    fclose(f);

    for (int i = 0; i < sizeof(machinesByInIdx) / sizeof(machinesByInIdx[0]); ++i)
    {
        std::sort(machinesByInIdx[i].begin(), machinesByInIdx[i].end());
    }

    unsigned int totalEstimate = estimates[31];
    unsigned int totalEstimate2 = estimates2[0];
    for (int i = 1; i < compoundIndex; ++i)
    {
        totalEstimate += estimates[i];
        totalEstimate2 += estimates2[i];
    }

    PriorityQueue queue;

    mask = ((1 << compoundIndex) - 1) | 0x80000000;

    VertexKey initialKey = { mask, 0x80000000 };
    int initialIdx = initialKey.hash();
    Vertex* v = hashTable + initialIdx;
    v->next = 0;
    v->key = initialKey;
    v->data[0] = totalEstimate + 1;
    v->data[1] = totalEstimate2 + 1;
    queue.push(Priority(v, 0, std::max(totalEstimate, totalEstimate2), false));

    do
    {
        Priority priority = queue.top();
        if (priority.finishing())
        {
            cout 
                << (priority.weight() / 2) << '\n';

            reportSolution(priority.vertex, priority.parent);
            break;
        }

        queue.pop();

        if (priority.vertex->visited())
        {
            continue;
        }

        const bool inBody = priority.vertex->key.tails == 1;
        if (inBody)
            handleVertex<true>(priority, queue);
        else
            handleVertex<false>(priority, queue);

        // visited
        priority.vertex->parent = priority.parent;
    }
    while (!queue.empty());

	return 0;
}
Saturday, October 4th, 2014
1:54 pm
Friday, November 1st, 2013
7:24 pm
Opus #16
#include <string>
#include <map>
#include <vector>
#include <memory>

class Variant
{
    struct Concept
    {
        virtual ~Concept() {}
        virtual void throwPtr() = 0;
    };

    template<typename T>
    struct Model : Concept
    {
        Model(T value) : m_data(std::move(value)) {}
        virtual void throwPtr() 
        {
            throw &m_data;
        }

        T m_data;
    };

public:

    Variant() {}

    template<typename T> Variant(T value) : m_self(std::make_shared<Model<T> >(std::move(value)))
    {
    }

    template<typename T> Variant& operator= (T value)
    {
        Variant temp(std::move(value));
        std::swap(*this, temp);
        return *this;
    }

    void clear() { m_self.reset(); }
    bool isNull() const { return m_self.get() == 0; }

    template<typename T>
    T* get()
    {
        if (!isNull())
        {
            try
            {
                m_self->throwPtr();
            }
            catch(T* p)
            {
                return p;
            }
            catch(...)
            {
                return 0;
            }
        }
        return 0;
    }

private:
    std::shared_ptr<Concept> m_self;
};


class JsonParser
{
public:
    JsonParser(const std::string& input);
    ~JsonParser();

    bool parse(Variant& result);

private:
    template<typename T> struct Traits {};

    Variant parseValue(bool skipError = false);

    bool error(const char* description)const;
    bool scan(const std::string& expression);
    bool scan(char ch);
    bool skip(char ch); // trims white space on both sides; for delimiters only
    void trimSpace();

    template<typename T>
    bool parseInstance(Variant& result);

    bool parseMember(std::map<std::string, Variant>& object);
    bool parseMember(std::vector<Variant>& array);

    template<typename T>
    bool parseString(T& result);
    bool parseNumber(Variant& result);
    bool parseKeyword(Variant& result);

    bool parseStringContent(std::string& contents);
    bool parseStringEscape(std::string& contents);

private:
    std::string m_input;
    std::string m_matched;
}; // class JsonParser


Variant parseJson(const std::string& data)
{
    Variant result;
    JsonParser(data).parse(result);
    return result;
}



#include <iostream>
#include <regex>
#include <cctype>
#include <climits>
#include <assert.h>


template<> struct JsonParser::Traits<std::map<std::string, Variant> >
{
    enum { OPENING = '{', CLOSING = '}' };
};
template<> struct JsonParser::Traits<std::vector<Variant> >
{
    enum { OPENING = '[', CLOSING = ']' };
};



JsonParser::JsonParser(const std::string& input)
    : m_input(input)
{
}


JsonParser::~JsonParser()
{
}

bool JsonParser::parse(Variant& result)
{
    try
    {
        result = parseValue();
    }
    catch (const char* errorDescription)
    {
        std::cerr << "JSON parse error: " << errorDescription << " at: " << m_input << '\n';
        return false;
    }
    if (!m_input.empty())
    {
        result.clear();
        return false;
    }
    return true;
}

template<typename T>
bool JsonParser::parseInstance(Variant& result)
{
    if (!skip(Traits<T>::OPENING))
    {
        return false;
    }

    T object;
    bool moreMembers = false;
    while (parseMember(object))
    {
        moreMembers = skip(',');
        if (!moreMembers)
        {
            break;
        }
    }
    if (moreMembers)
    {
        error("Missing member");
    }
    skip(Traits<T>::CLOSING) || error("Unclosed instance");

    result = object;
    return true;
}

bool JsonParser::parseMember(std::map<std::string, Variant>& object)
{
    std::string key;
    if (!parseString(key))
    {
        return false;
    }
    skip(':') || error("Expecting object separator");
    object[key] = parseValue();
    return true;
}

bool JsonParser::parseMember(std::vector<Variant>& array)
{
    Variant value = parseValue(true);
    if (value.isNull())
    {
        return false;
    }
    array.push_back(value);
    return true;
}

template<typename T>
bool JsonParser::parseString(T& result)
{
    if (!scan('"'))
    {
        return false;
    }

    std::string value;
    std::string contents;
    while (parseStringContent(contents) || parseStringEscape(contents))
    {
        value += contents;
    }
    scan('"') || error("Unclosed string");
    result = value;
    return true;
}

Variant JsonParser::parseValue(bool skipError)
{
    Variant result;
    trimSpace();

    parseInstance<std::map<std::string, Variant> >(result) // object
    || parseInstance<std::vector<Variant> >(result) // array
    || parseString(result)
    || parseNumber(result)
    || parseKeyword(result)
    || skipError
    || error("Illegal JSON value");

    trimSpace();
    return result;
}


bool JsonParser::scan(const std::string& expression)
{
    std::regex re(expression);
    std::smatch m;
    if (std::regex_search(m_input, m, re, std::regex_constants::match_continuous))
    {
        assert(0 == m.position());
        if (!m.empty())
        {
            m_matched = m.str();
            m_input = m.suffix();
            return true;
        }
    }

    return false;
}

bool JsonParser::scan(char ch)
{
    if (!m_input.empty() && m_input.at(0) == ch)
    {
        m_input = std::string(++m_input.begin(), m_input.end());
        return true;
    }
    return false;
}

bool JsonParser::skip(char ch)
{
    trimSpace();
    if (scan(ch))
    {
        trimSpace();
        return true;
    }
    return false;
}


void JsonParser::trimSpace()
{
    auto end = std::find_if_not(m_input.rbegin(), m_input.rend(), static_cast<int(*)(int)>(std::isspace)).base();
    auto begin = std::find_if_not(m_input.begin(), end, static_cast<int(*)(int)>(std::isspace));
    m_input = std::string(begin, end);
}

bool JsonParser::parseNumber(Variant& result)
{
    size_t pos(0);
    try
    {
        double value = std::stod(m_input, &pos);
        int intValue;
        if (value >= INT_MIN && value <= INT_MAX
            && ((intValue = static_cast<int>(value)) == value))
        {
            result = intValue;
        }
        else
        {
            result = value;
        }
    }
    catch (std::exception&)
    {
        return false;
    }
    m_input = std::string(m_input.begin() + pos, m_input.end());
    return true;
}

bool JsonParser::parseKeyword(Variant& result)
{
    if (!scan("\\b(?:true|false|null)\\b"))
    {
        return false;
    }

    if ("true" == m_matched)
    {
        result = true;
    }
    else if ("false" == m_matched)
    {
        result = false;
    }
    else if ("null" == m_matched)
    {
        result.clear();
    }
    else
    {
        error("Unexpected keyword");
    }

    return true;
}

bool JsonParser::parseStringContent(std::string& contents)
{
    if (!scan("[^\\\\\"]+"))
    {
        return false;
    }

    contents = m_matched;
    return true;
}

bool JsonParser::parseStringEscape(std::string& contents)
{
    if (scan("\\\\[\"\\\\/]"))
    {
        contents = std::string(++m_matched.begin(), m_matched.end());
    }
    else if (scan("\\\\[abfnrtv]"))
    {
        char c = m_matched.at(1);
        switch (c)
        {
        case 'a': contents = '\a'; break;
        case 'b': contents = '\b'; break;
        case 'f': contents = '\f'; break;
        case 'n': contents = '\n'; break;
        case 'r': contents = '\r'; break;
        case 't': contents = '\t'; break;
        case 'v': contents = '\v'; break;
        default: error("Unexpected escape symbol");
        }
    }
    else if (scan("\\\\u[0-9a-fA-F]{4}"))
    {
        try
        {
            // TODO handle unicode value
            contents = (char) std::strtol(m_matched.c_str() + 2, 0, 16);
        }
        catch (std::exception&)
        {
            error("Failed to parse Unicode value");
        }
    }
    else
    {
        return false;
    }

    return true;
}

bool JsonParser::error(const char* description)const
{
    throw description;
}
Thursday, June 7th, 2012
11:29 am
google schmoogle
google заботливо добавляет ролики youtube в результаты поиска, а когда на них кликаешь, оно же (youtube) периодически сообщает: А вот фиг тебе: The uploader has not made this video available in your country.
Не надо напоминать мне, что я не в той стране живу.
Thursday, February 16th, 2012
11:19 pm
Yet another condvar exercise
Here it is.. Briefly, there is no need to wake up a thread just to check a condition. And keyed events are quite handy here.
Monday, February 13th, 2012
11:43 pm
Fast Levenshtein distance (was: Facebook Breathalyzer)
#include <iostream>
#include <fstream>
#include <exception>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iterator>

#include <climits>

#include <stdio.h>

//#include <assert.h>
#define assert(x)	((void)0)

#include <fcntl.h>
#include <string.h>

#include <omp.h>

#ifdef _WIN32
#include <io.h>
#define open _open
#define lseek _lseek
#define read _read
#define close _close
#else
#undef _O_BINARY
#define _O_BINARY 0
#endif

#ifdef _MSC_VER
#define __inline__ __forceinline
#else
#define _fgetc_nolock fgetc_unlocked
//#define _fgetc_nolock fgetc
#endif

using std::cerr;
using std::cout;
using std::ifstream;
using std::exception;
using std::string;
using std::getline;
using std::vector;
using std::map;
using std::min;
using std::max;
using std::istream_iterator;



static const signed char LogTable256[256] =
{
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
    -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
    LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
    LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};


inline int Log(unsigned int v) // 32-bit word to find the log of
{
    int r;     // r will be lg(v)
    unsigned int t, tt; // temporaries

    if (tt = v >> 16)
    {
      r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
    }
    else
    {
      r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
    }

    return r;
}


struct Plex     // Similar to MFC CPlex
// warning variable length structure
{
    Plex* pNext;
    int dwReserved[1];    // align on 8 byte boundary

    void* data() { return this+1; }

    // like 'calloc' but no zero fill
    // may throw memory exceptions
    static Plex* Create(Plex*& pHead, size_t nMax, size_t cbElement)
    {
        assert(nMax > 0 && cbElement > 0);
        Plex* p = (Plex*) operator new(sizeof(Plex) + nMax * cbElement);
                // may throw exception
        p->pNext = pHead;
        pHead = p;  // change head (adds in reverse order for simplicity)
        return p;
    }

    void FreeDataChain()       // free this one and links
    {
        Plex* p = this;
        while (p != 0)
        {
            void* bytes = p;
            p = p->pNext;
            operator delete(bytes);
        }
    }
};

typedef unsigned int UINT;

class FixedAlloc    // Similar to MFC CFixedAlloc
{
// Constructors
public:
    FixedAlloc(UINT nAllocSize, UINT nBlockSize = 64);

// Attributes
    UINT GetAllocSize() { return m_nAllocSize; }

// Operations
public:
    void* Alloc();  // return a chunk of memory of nAllocSize
    void Free(void* p); // free chunk of memory returned from Alloc
    void FreeAll(); // free everything allocated from this allocator

// Implementation
public:
    ~FixedAlloc();

protected:
    struct CNode
    {
        CNode* pNext;	// only valid when in free list
    };

    UINT m_nAllocSize;	// size of each block from Alloc
    UINT m_nBlockSize;	// number of blocks to get at a time
    Plex* m_pBlocks;	// linked list of blocks (is nBlocks*nAllocSize)
    CNode* m_pNodeFree;	// first free node (0 if no free nodes)
};

FixedAlloc::FixedAlloc(UINT nAllocSize, UINT nBlockSize)
{
    assert(nAllocSize >= sizeof(CNode));
    assert(nBlockSize > 1);

    if (nAllocSize < sizeof(CNode))
        nAllocSize = sizeof(CNode);
    if (nBlockSize <= 1)
        nBlockSize = 64;

    m_nAllocSize = nAllocSize;
    m_nBlockSize = nBlockSize;
    m_pNodeFree = 0;
    m_pBlocks = 0;
}

FixedAlloc::~FixedAlloc()
{
    FreeAll();
}

void FixedAlloc::FreeAll()
{
    m_pBlocks->FreeDataChain();
    m_pBlocks = 0;
    m_pNodeFree = 0;
}

void* FixedAlloc::Alloc()
{
    if (m_pNodeFree == 0)
    {
        // add another block
        Plex* pNewBlock = Plex::Create(m_pBlocks, m_nBlockSize, m_nAllocSize);

        // chain them into free list
        // free in reverse order to make it easier to debug
        char* pData = (char*) pNewBlock->data() + m_nAllocSize * (m_nBlockSize - 1);
        for (int i = m_nBlockSize; i > 0; i--, pData -= m_nAllocSize)
        {
            CNode* pNode = (CNode*) pData;
            pNode->pNext = m_pNodeFree;
            m_pNodeFree = pNode;
        }
    }
    assert(m_pNodeFree != 0);  // we must have something

    // remove the first available node from the free list
    void* pNode = m_pNodeFree;
    m_pNodeFree = m_pNodeFree->pNext;
    return pNode;
}

void FixedAlloc::Free(void* p)
{
    if (p != 0)
    {
        // simply return the node to the free list
        CNode* pNode = (CNode*)p;
        pNode->pNext = m_pNodeFree;
        m_pNodeFree = pNode;
    }
}

// http://www.drdobbs.com/184410528

struct Tnode
{
   char splitchar;
   /*bool*/ char terminating;
   unsigned char maxLength, minLength;

   Tnode *eqkid, *hikid;

   Tnode(char ch)
       : splitchar(ch)
       , terminating(false)
       , maxLength(0)
       , minLength(255)
       , eqkid(0), hikid(0)
   {
   }

    void* operator new(size_t size)
    {
        assert(size == s_alloc.GetAllocSize());
        return s_alloc.Alloc();
    }
    void* operator new(size_t, void* p) { return p; }
    void operator delete(void* p) { s_alloc.Free(p); }

protected:
    static FixedAlloc s_alloc;
} ;


FixedAlloc Tnode::s_alloc(sizeof(Tnode), 64);

inline char ToLowerCase(char ch) { return ch | 0x20; }


Tnode* insert_new(FILE *stream, int ch, unsigned int& length)
{
    assert(ch & ~31);

    ch = ToLowerCase(ch);

    Tnode *p = new Tnode(ch);

    ch = _fgetc_nolock( stream );
    if (0 == (ch & ~31) || EOF == ch)
        p->terminating = true;
    else
    {
        ++length;
        p->eqkid = insert_new(stream, ch, length);
    }

    p->maxLength = length;
    p->minLength = length;

    return p;
}


Tnode* insert(Tnode *p, FILE *stream, int ch, unsigned int& length)
{
    assert(ch & ~31);

    ch = ToLowerCase(ch);

    if (p == 0) {
        p = new Tnode(ch);
    }

    assert(ch >= p->splitchar);
    if (ch == p->splitchar) {
        ch = _fgetc_nolock( stream );
        if (0 == (ch & ~31) || EOF == ch)
            p->terminating = true;
        else
        {
            ++length;
            p->eqkid = insert(p->eqkid, stream, ch, length);
        }
    } else
    {
        Tnode* temp = insert_new(stream, ch, length);
        assert(0 == temp->hikid);
        temp->hikid = p;
        temp->minLength = p->minLength;
        temp->maxLength = p->maxLength;
        p = temp;
    }

    if (p->maxLength < length)
        p->maxLength = length;

    if (p->minLength > length)
        p->minLength = length;

    assert(p->minLength <= p->maxLength);

    return p;
}


const char seps[] = "\r\n";

const unsigned int ZERO_DISTANCE = 0xFFFFFFFF;//(unsigned int)-1;

class Breathalyzer
{
private:
    enum { DISTANCE_THRESHOLD = 3 };

    Tnode* wordList;

    unsigned int minLength;// = INT_MAX;

    unsigned int wordDim;

    __inline__
    bool DoSearch(const Tnode* p, unsigned int* d, const string& s,
                  const int offset, const unsigned int maxDistance, unsigned int& distance)
    {
        int threshold = int(s.size());
        if (p->eqkid != 0)
            threshold -= p->eqkid->maxLength - offset;

        unsigned int* upLeft = d;
        unsigned int* downRight = upLeft + s.size() + 2;

        const char* i = s.data();
        const char* dataEnd = i + s.size();

        const char splitchar = p->splitchar;

        const unsigned int startDistance = distance;

        bool ok = (0 < threshold)? ((startDistance >> threshold) >= maxDistance) : (startDistance >= maxDistance);

        if (!ok)
        {
            const char* pThreshold = i + threshold - 1;

            for (; i < pThreshold; ++i, ++upLeft, ++downRight)
            {
                if (*i == splitchar)
                    distance = *upLeft;
                else
                    distance = (*upLeft | *(upLeft + 1) | distance) >> 1;

                *downRight = distance;

                if ((distance >> (pThreshold - i)) >= maxDistance)
                {
                    goto ok_loop;
                }
            }
            for (;;)
            {
                if (*i == splitchar)
                    distance = *upLeft;
                else
                    distance = (*upLeft | *(upLeft + 1) | distance) >> 1;

                *downRight = distance;

                if (distance >= maxDistance)
                {
                    goto ok_loop;
                }

                if (++i >= dataEnd)
                    return false;

                ++upLeft;
                ++downRight;
            }

            return false;
        }
        else
        {
            for (;;)
            {
                if (*i == splitchar)
                    distance = *upLeft;
                else
                    distance = (*upLeft | *(upLeft + 1) | distance) >> 1;

                *downRight = distance;
ok_loop:
                if (++i >= dataEnd)
                    return true;

                ++upLeft;
                ++downRight;
            }

            return true;
        }
    }


    bool GetDistance(const Tnode* p, unsigned int* d, const string& s, int offset, int& maxDistance)
    {
        for (; p != 0; p = p->eqkid, ++offset, d += s.size() + 1)
        {
            if (int(s.length()) - p->maxLength > maxDistance)
                return false;

            if (p->minLength - int(s.length()) > maxDistance)
                return false;

            if (GetDistance(p->hikid, d, s, offset, maxDistance))
                return true;

            if (0 == p->eqkid && !p->terminating)
                return false;

            //int distance(offset);
            unsigned int distance(ZERO_DISTANCE >> offset);
            const unsigned int expMaxDistance(ZERO_DISTANCE >> maxDistance);

            if (!DoSearch(p, d, s, offset, expMaxDistance, distance))
                return false;

            if (p->terminating)
            {
                if (distance > expMaxDistance)
                {
                    maxDistance = 31 - Log(distance);
                    if (maxDistance <= DISTANCE_THRESHOLD)
                        return true;
                }
            }
        }
        return false;
    }

    bool find0(const Tnode* p, const char* s)
    {
        for (; p != 0; p = p->eqkid)
        {
            while (p->splitchar > *s)
            {
                if (0 == p->hikid)
                {
                    return false;
                }
                p = p->hikid;
            }

            if (p->splitchar < *s)
            {
                return false;
            }

            if (0 == *(++s))
            {
                return p->terminating;
            }
        }

        return false;
    }

    bool find(const Tnode* p, unsigned int* d, const string& s, int offset, const int maxDistance)
    {
        for (; p != 0; p = p->eqkid, ++offset, d += s.size() + 1)
        {
            if (int(s.length()) - p->maxLength > maxDistance)
                return false;

            if (p->minLength - int(s.length()) > maxDistance)
                return false;

            if (find(p->hikid, d, s, offset, maxDistance))
                return true;

            if (0 == p->eqkid && !p->terminating)
                return false;

            //int distance(offset);
            unsigned int distance(ZERO_DISTANCE >> offset);
            const unsigned int expMaxDistance(ZERO_DISTANCE >> maxDistance);

            if (!DoSearch(p, d, s, offset, expMaxDistance, distance))
                return false;

            if (p->terminating)
            {
                if (distance >= expMaxDistance)
                    return true;
            }
        }
        return false;
    }

public:
    Breathalyzer() : wordList(0)
    {
    }

    void ReadWordList()
    {
        FILE *stream = fopen("/var/tmp/twl06.txt", "r");

        for (;;)
        {
            int ch;
            do
            {
                ch = _fgetc_nolock( stream );
            }
            while (0 == (ch & ~31));
            if (EOF == ch)
               break;

            unsigned int length(1);
            wordList = insert(wordList, stream, ch, length);
        }

        fclose(stream);

        wordDim = wordList->maxLength + 1;
        minLength = wordList->minLength;
    }

    int GetDistance(const string& s)
    {
        if (find0(wordList, s.c_str()))
            return 0;

        enum { FAST_BUFFER_SIZE = 512 };

        unsigned int sbuf[FAST_BUFFER_SIZE];

        const size_t bufSize = wordDim * (s.size() + 1);
        unsigned int* d = (bufSize > FAST_BUFFER_SIZE)? new unsigned int[bufSize] : sbuf;

        for (unsigned int i = 0; i <= s.size(); ++i)
            d[i] = ZERO_DISTANCE >> i;
        for (unsigned int i = 1; i < wordDim; ++i)
            d[i * (s.size() + 1)] = ZERO_DISTANCE >> i;


        for (int result = 1; result < DISTANCE_THRESHOLD; ++result)
            if (find(wordList, &d[0], s, 1, result))
            {
                if (d != sbuf)
                    delete[] d;
                return result;
            }

        int result = max(minLength, (unsigned int) s.size());
        GetDistance(wordList, &d[0], s, 1, result);

        if (d != sbuf)
            delete[] d;
        return result;
    }
};

int main(int argc, char* argv[])
{
    if (argc < 2)
    {
        cerr << "Usage: breathalyzer input_file\n";
        return 1;
    }

    try
    {
        Breathalyzer breathalyzer;

        typedef vector<std::pair<string, int> > Strings;
        Strings strings;

#pragma omp parallel
        {
#pragma omp sections
            {
#pragma omp section
                {
                    breathalyzer.ReadWordList();
                }
#pragma omp section
                {
                    /*
                    string path(argv[1]);
                    if (string::npos == path.find_first_of("\\/"))
                    {
                        string dir(argv[0]);
                        string::size_type pos = dir.find_last_of("\\/");
                        if (string::npos != pos)
                        {
                            path = dir.substr(0, pos + 1) + path;
                        }
                    }

                    ifstream inFile(path.c_str());
                    //*/

                    ifstream inFile(argv[1]);

                    map<string, int> counts;
                    for (istream_iterator<string> iss(inFile), issEnd
                        ; iss != issEnd
                        ; ++iss)
                    {
                        ++counts[*iss];
                    }

                    strings.assign(counts.begin(), counts.end());
                }
            }
        }

        const int numStrings = strings.size();

        int totalDistance = 0;

        int i;

#pragma omp parallel for reduction(+:totalDistance) schedule (dynamic, 10)
        for (i = 0; i < numStrings; ++i)
        {
            Strings::iterator it = strings.begin() + i;
            const int distance = breathalyzer.GetDistance(it->first);
            totalDistance += distance * it->second;
        }

        cout << totalDistance << '\n';
    }
    catch (exception& e)
    {
        cerr << e.what();
        return 1;
    }

    return 0;
}
Monday, January 30th, 2012
11:24 pm
switch вместо побитового цикла
Вдруг окажется новым и интересным - за основу для демонстрации удобно взять решение задачу про ящики отсюда. Вкрадце, есть N=20 ящиков с предопределенными весом и прочностью, и нужно посчитать, сколькими способами можно их поставить друг на друга. Типичная задачка на динамическое программирование.
Вот решение автора задачи, которое используем в качестве отправной точки:
#include <vector>
#include <iostream>

using namespace std;

long long stack_qty(vector<int> weights, vector<int> durab) {
  int combs_n = 1 << weights.size();
  vector<long long> comb(combs_n);
  comb[0] = 1;
  for(int cur_comb = 1; cur_comb < combs_n; cur_comb++) {
    int cur_comb_weight = 0, cur_box, cur_box_bit;
    for(cur_box = 0, cur_box_bit = 1;
        cur_box_bit <= cur_comb;
	cur_box++, cur_box_bit <<= 1)
      if(cur_comb & cur_box_bit)
        cur_comb_weight += weights[cur_box];

    for(cur_box = 0, cur_box_bit = 1;
        cur_box_bit <= cur_comb;
	cur_box++, cur_box_bit <<= 1) {
      int cur_comb_no_cur_box = cur_comb ^ cur_box_bit;
      if(cur_comb_no_cur_box < cur_comb
         && cur_comb_weight - weights[cur_box] <= durab[cur_box])
	 comb[cur_comb] += comb[cur_comb_no_cur_box];
    }
  } // main for
  return comb[combs_n - 1];
}

const int N = 20;

#if 0
const int weight[N] =
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
const int durab [N] =
{ 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, };
#endif

const int weight[N] =
{ 15, 10, 13, 14, 15, 8, 91, 16, 9, 33,  31,  44,  71,  76, 9, 1,  4,
3,  12, 8 };
const int durab [N] =
{ 220, 200, 170, 186, 415, 584, 813, 192, 116, 610, 99, 78, 357, 876, 79,
99, 76, 300, 654, 120 };


int main(int argc, char **argv) {
   vector<int> weight_vec(weight, weight + N);
   vector<int> durab_vec (durab , durab  + N);
   cout << "Combination=" << stack_qty(weight_vec, durab_vec) << endl;
   return 0;
}


В результате получаем примерно следующее время:
D:\solutions\boxes2\boxes2\Release>timeit boxes2.exe
Combination=424284694368

Version Number:   Windows NT 5.1 (Build 2600)
Exit Time:        10:40 pm, Monday, January 30 2012
Elapsed Time:     0:00:00.359
Process Time:     0:00:00.343
System Calls:     4664
Context Switches: 2710
Page Faults:      6318
Bytes Read:       490506
Bytes Written:    16472
Bytes Other:      161220


Сначала проведем некоторую предварительную оптимизацию:
#include <vector>
#include <iostream>

using namespace std;

long long stack_qty(const int* const weights, const int* const durab, const int num) {
  const int combs_n = 1 << num;
  vector<long long> comb(combs_n);
  comb[0] = 1;
  int cur_comb_weight = 0;
  for(int cur_comb = 0; cur_comb < combs_n; cur_comb++) {
    int cur_box, cur_box_bit;
    if (cur_comb & 1)
    {
        cur_comb_weight += weights[0];
    }
    else if (cur_comb & 2)
    {
        cur_comb_weight -= weights[0];
        cur_comb_weight += weights[1];
    }
    else
    {
        cur_comb_weight = 0;
        for(cur_box = 0, cur_box_bit = 1;
            cur_box_bit <= cur_comb;
	    cur_box++, cur_box_bit <<= 1)
          if(cur_comb & cur_box_bit)
            cur_comb_weight += weights[cur_box];
    }
    const int not_cur_comb = combs_n - 1 - cur_comb;
    for(cur_box = 0, cur_box_bit = 1;
        cur_box_bit <= not_cur_comb;
    cur_box++, cur_box_bit <<= 1) {
      if (not_cur_comb & cur_box_bit
            && cur_comb_weight <= durab[cur_box])
    	 comb[cur_comb | cur_box_bit] += comb[cur_comb];
    }

  } // main for
  return comb[combs_n - 1];
}

const int N = 20;

#if 0
const int weight[N] =
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
const int durab [N] =
{ 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, };
#endif

const int weight[N] =
{ 15, 10, 13, 14, 15, 8, 91, 16, 9, 33,  31,  44,  71,  76, 9, 1,  4,
3,  12, 8 };
const int durab [N] =
{ 220, 200, 170, 186, 415, 584, 813, 192, 116, 610, 99, 78, 357, 876, 79,
99, 76, 300, 654, 120 };


int main(int argc, char **argv) {
   vector<int> weight_vec(weight, weight + N);
   vector<int> durab_vec (durab , durab  + N);
   cout << "Combination=" << stack_qty(&weight_vec[0], &durab_vec[0], N) << endl;
   return 0;
}


В результате получаем примерно следующее время:
D:\solutions\boxes2_1\boxes2\Release>timeit boxes2.exe
Combination=424284694368

Version Number:   Windows NT 5.1 (Build 2600)
Exit Time:        10:47 pm, Monday, January 30 2012
Elapsed Time:     0:00:00.218
Process Time:     0:00:00.218
System Calls:     2339
Context Switches: 866
Page Faults:      2509
Bytes Read:       41998
Bytes Written:    1680
Bytes Other:      4258


А теперь применяем switch вместо побитового цикла:
#include <vector>
#include <iostream>

using namespace std;

#define HANDLE_GROUPS_4(a, b, c, d) \
    case (a * 64 + b * 16 + c * 4 + d): \
    { \
        enum { flags = (a * 64 + b * 16 + c * 4 + d) }; \
        HANDLE_FLAG(0); \
        HANDLE_FLAG(1); \
        HANDLE_FLAG(2); \
        HANDLE_FLAG(3); \
        HANDLE_FLAG(4); \
        HANDLE_FLAG(5); \
        HANDLE_FLAG(6); \
        HANDLE_FLAG(7); \
        break; \
    }

#define HANDLE_GROUPS_3(a, b, c) \
HANDLE_GROUPS_4(a, b, c, 0) \
HANDLE_GROUPS_4(a, b, c, 1) \
HANDLE_GROUPS_4(a, b, c, 2) \
HANDLE_GROUPS_4(a, b, c, 3)

#define HANDLE_GROUPS_2(a, b) \
HANDLE_GROUPS_3(a, b, 0) \
HANDLE_GROUPS_3(a, b, 1) \
HANDLE_GROUPS_3(a, b, 2) \
HANDLE_GROUPS_3(a, b, 3)

#define HANDLE_GROUPS_1(a) \
HANDLE_GROUPS_2(a, 0) \
HANDLE_GROUPS_2(a, 1) \
HANDLE_GROUPS_2(a, 2) \
HANDLE_GROUPS_2(a, 3)


long long stack_qty(const int* const weights, const int* const durab, const int num) {
    const int combs_n = 1 << num;
    vector<long long> comb(combs_n);
    comb[0] = 1;
    int cur_comb_weight = 0;
    for(int cur_comb = 0; cur_comb < combs_n; cur_comb++) {

#define HANDLE_FLAG(curPlace) \
    if (flags & (1 << curPlace)) \
    { \
        cur_comb_weight += weights[cur_box + curPlace]; \
    }

        if (cur_comb & 1)
        {
            cur_comb_weight += weights[0];
        }
        else if (cur_comb & 2)
        {
            cur_comb_weight -= weights[0];
            cur_comb_weight += weights[1];
        }
        else
        {
            cur_comb_weight = 0;

            {
                const int cur_box = 0, cur_box_bit = 1;

                switch ((cur_comb >> cur_box) & 0xFF)
                {
                    HANDLE_GROUPS_1(0)
                    HANDLE_GROUPS_1(1)
                    HANDLE_GROUPS_1(2)
                    HANDLE_GROUPS_1(3)
                }
            }
            {
                const int cur_box = 8, cur_box_bit = 1 << 8;

                switch ((cur_comb >> cur_box) & 0xFF)
                {
                    HANDLE_GROUPS_1(0)
                    HANDLE_GROUPS_1(1)
                    HANDLE_GROUPS_1(2)
                    HANDLE_GROUPS_1(3)
                }
            }
            {
                const int cur_box = 16, cur_box_bit = 1 << 16;

                switch ((cur_comb >> cur_box) & 0xFF)
                {
                    HANDLE_GROUPS_1(0)
                    HANDLE_GROUPS_1(1)
                    HANDLE_GROUPS_1(2)
                    HANDLE_GROUPS_1(3)
                }
            }
        }

#undef HANDLE_FLAG

#define HANDLE_FLAG(curPlace) \
    if (flags & (1 << curPlace)) \
    { \
        if(cur_comb_weight <= durab[cur_box + curPlace]) { \
            comb[cur_comb | (cur_box_bit << curPlace)] += comb[cur_comb]; \
        } \
    }

        const int not_cur_comb = combs_n - 1 - cur_comb;

        {
            const int cur_box = 0, cur_box_bit = 1;

            switch ((not_cur_comb >> cur_box) & 0xFF)
            {
                HANDLE_GROUPS_1(0)
                HANDLE_GROUPS_1(1)
                HANDLE_GROUPS_1(2)
                HANDLE_GROUPS_1(3)
            }
        }
        {
            const int cur_box = 8, cur_box_bit = 1 << 8;

            switch ((not_cur_comb >> cur_box) & 0xFF)
            {
                HANDLE_GROUPS_1(0)
                HANDLE_GROUPS_1(1)
                HANDLE_GROUPS_1(2)
                HANDLE_GROUPS_1(3)
            }
        }
        {
            const int cur_box = 16, cur_box_bit = 1 << 16;

            switch ((not_cur_comb >> cur_box) & 0xFF)
            {
                HANDLE_GROUPS_1(0)
                HANDLE_GROUPS_1(1)
                HANDLE_GROUPS_1(2)
                HANDLE_GROUPS_1(3)
            }
        }

    } // main for
    return comb[combs_n - 1];
}

const int N = 20;

#if 0
const int weight[N] =
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
const int durab [N] =
{ 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, };
#endif

const int weight[N] =
{ 15, 10, 13, 14, 15, 8, 91, 16, 9, 33,  31,  44,  71,  76, 9, 1,  4,
3,  12, 8 };
const int durab [N] =
{ 220, 200, 170, 186, 415, 584, 813, 192, 116, 610, 99, 78, 357, 876, 79,
99, 76, 300, 654, 120 };


int main(int argc, char **argv) {
   vector<int> weight_vec(weight, weight + N);
   vector<int> durab_vec (durab , durab  + N);
   cout << "Combination=" << stack_qty(&weight_vec[0], &durab_vec[0], N) << endl;
   return 0;
}


В результате получаем примерно следующее время:
D:\solutions\boxes2_2\boxes2\Release>timeit boxes2.exe
Combination=424284694368

Version Number:   Windows NT 5.1 (Build 2600)
Exit Time:        10:57 pm, Monday, January 30 2012
Elapsed Time:     0:00:00.109
Process Time:     0:00:00.109
System Calls:     2518
Context Switches: 730
Page Faults:      2526
Bytes Read:       11686
Bytes Written:    2064
Bytes Other:      5926


С g++ примерно та же картина.
Sunday, February 13th, 2011
9:11 pm
Opus #15
#include <algorithm>
#include <iostream>

#include <time.h>

using std::cout;
using std::cerr;
using std::endl;


enum { MULTIPLIER = 7 };

#define ITER(stage)     \
if (stage <= curPlace)  \
{                       \
    enum { OFFSET = (1 << stage) / 2 }; \
    if (*(first + (OFFSET - 1) * MULTIPLIER) < val)    \
        first += OFFSET * MULTIPLIER;    \
}

template <int curPlace, typename I, typename V>
inline
I fast_lower_bound(I first, const V& val)
{
    ITER(28)
    ITER(27)
    ITER(26)
    ITER(25)
    ITER(24)
    ITER(23)
    ITER(22)
    ITER(21)
    ITER(20)
    ITER(19)
    ITER(18)
    ITER(17)
    ITER(16)
    ITER(15)
    ITER(14)
    ITER(13)
    ITER(12)
    ITER(11)
    ITER(10)
    ITER(9)
    ITER(8)
    ITER(7)
    ITER(6)
    ITER(5)
    ITER(4)
    ITER(3)
    ITER(2)
    ITER(1)

    if (*(first - 1) < val)
        return first;
    if (*(first - 2) < val)
        return first - 1;
    if (*(first - 3) < val)
        return first - 2;
    if (*(first - 4) < val)
        return first - 3;
    if (*(first - 5) < val)
        return first - 4;
    if (*(first - 6) < val)
        return first - 5;

    return first - 6;
}


#define HANDLE_GROUPS_3(a, b, c) \
HANDLE_GROUPS_4(a, b, c, 0) \
HANDLE_GROUPS_4(a, b, c, 1) \
HANDLE_GROUPS_4(a, b, c, 2) \
HANDLE_GROUPS_4(a, b, c, 3)

#define HANDLE_GROUPS_2(a, b) \
HANDLE_GROUPS_3(a, b, 0) \
HANDLE_GROUPS_3(a, b, 1) \
HANDLE_GROUPS_3(a, b, 2) \
HANDLE_GROUPS_3(a, b, 3)


#define HANDLE_GROUPS_1(a) \
HANDLE_GROUPS_2(a, 0) \
HANDLE_GROUPS_2(a, 1) \
HANDLE_GROUPS_2(a, 2) \
HANDLE_GROUPS_2(a, 3)


#define HANDLE_GROUPS_4(a, b, c, d) \
    case (a * 64 + b * 16 + c * 4 + d): \
    { \
        enum { flags = (a * 64 + b * 16 + c * 4 + d) }; \
        HANDLE_FLAG(6); \
        HANDLE_FLAG(5); \
        HANDLE_FLAG(4); \
        HANDLE_FLAG(3); \
        HANDLE_FLAG(2); \
        HANDLE_FLAG(1); \
        HANDLE_FLAG(0); \
        break; \
    }

#define HANDLE_FLAG(flag) \
    { \
        enum { curPlace = flag + SEGMENT * 7 }; \
        if (*(first + ((1 << curPlace) - 1) * MULTIPLIER) < val) \
            first += (1 << curPlace) * MULTIPLIER; \
        else \
            return fast_lower_bound<curPlace>(first, val); \
        if (flags & (1 << flag)) \
        { \
            if (*(first + ((1 << curPlace) - 1) * MULTIPLIER) < val) \
                first += (1 << curPlace) * MULTIPLIER; \
            else \
                return fast_lower_bound<curPlace>(first, val); \
        } \
    }


template <typename I, int SEGMENT>
struct bound_continue_helper
{
    template<typename V>
    static I lower_bound_ex(I first, unsigned int distance, const V& val)
    {
        switch ((distance >> (SEGMENT * 7)) & 127)
        {
            HANDLE_GROUPS_1(0)
            HANDLE_GROUPS_1(1)
        }

        return bound_continue_helper<I, SEGMENT - 1>::lower_bound_ex(first, distance, val);
    }
};

template <typename I>
struct bound_continue_helper<I, -1>
{
    template<typename V>
    static I lower_bound_ex(I first, unsigned int, const V&)
    {
        return first;
    }
};

#undef HANDLE_GROUPS_4
#define HANDLE_GROUPS_4(a, b, c, d) \
    case (a * 64 + b * 16 + c * 4 + d): \
    { \
        enum { flags = (a * 64 + b * 16 + c * 4 + d) }; \
        if (0 == flags) \
            return bound_entry_helper<I, SEGMENT-1>::lower_bound_ex(first, distance, val); \
        HANDLE_FLAG(6); \
        HANDLE_FLAG(5); \
        HANDLE_FLAG(4); \
        HANDLE_FLAG(3); \
        HANDLE_FLAG(2); \
        HANDLE_FLAG(1); \
        HANDLE_FLAG(0); \
        break; \
    }

#undef HANDLE_FLAG
#define HANDLE_FLAG(flag) \
    if (flags >= (1 << (flag+1))) \
    { \
        enum { curPlace = flag + SEGMENT * 7 }; \
        if (*(first + ((1 << curPlace) - 1) * MULTIPLIER) < val) \
            first += (1 << curPlace) * MULTIPLIER; \
        else \
            return fast_lower_bound<curPlace>(first, val); \
        if (flags & (1 << flag)) \
        { \
            if (*(first + ((1 << curPlace) - 1) * MULTIPLIER) < val) \
                first += (1 << curPlace) * MULTIPLIER; \
            else \
                return fast_lower_bound<curPlace>(first, val); \
        } \
    }

template <typename I, int SEGMENT>
struct bound_entry_helper
{
    template<typename V>
    static I lower_bound_ex(I first, unsigned int distance, const V& val)
    {
        switch ((distance >> (SEGMENT * 7)) & 127)
        {
            HANDLE_GROUPS_1(0)
            HANDLE_GROUPS_1(1)
        }

        return bound_continue_helper<I, SEGMENT - 1>::lower_bound_ex(first, distance, val);
    }
};

template <typename I>
struct bound_entry_helper<I, -1>
{
    template<typename V>
    static I lower_bound_ex(I first, unsigned int, const V&)
    {
        return first;
    }
};


template<typename I, typename V>
inline I lower_bound_ex(I first, I last,
		                const V& val)
{
    unsigned int distance = (unsigned int) (last - first) / MULTIPLIER;
    unsigned int flags = distance + 1;

    I result = (flags >= 0x00004000)
        ? bound_entry_helper<I, 3>::lower_bound_ex(first + MULTIPLIER - 1, flags, val)
        : bound_entry_helper<I, 1>::lower_bound_ex(first + MULTIPLIER - 1, flags, val);

    I temp = result - (MULTIPLIER - 1);
    if (first + distance * MULTIPLIER == temp)
    {
        result = temp;
        for (; result != last; ++result)
            if (!(*result < val))
                return result;
    }

    return result;
}


unsigned int HashKey(int key)
{
	return (key * 2654435761UL) >> 11;
}



int main(int argc, char* argv[])
{
    enum { SIZE = 512 * 1024, ITERATIONS = 10 };

    int* arr = new int[SIZE];

    for (int i = 0; i <= SIZE; ++i)
        arr[i] = i;

	clock_t start = clock();

    for (int k = 0; k < ITERATIONS; ++k)
        for (int i = 0; i < SIZE; ++i)
        {
            int j = (HashKey(i) % SIZE);
            int* p = lower_bound_ex(arr, arr + SIZE - 1, j);
            if (j != *p)
            {
                cerr << "Erroneous lower_bound_ex test result: " << *p << " instead of " << j << endl;
                return 1;
            }
        }

    cout << "lower_bound_ex time: " <<
		(double)(clock() - start) / CLOCKS_PER_SEC  <<
		" seconds" << endl;



    start = clock();

    for (int k = 0; k < ITERATIONS; ++k)
        for (int i = 0; i < SIZE; ++i)
        {
            int j = (HashKey(i) % SIZE);
            int* p = std::lower_bound(arr, arr + SIZE - 1, j);
            if (j != *p)
            {
                cerr << "Erroneous std::lower_bound test result: " << *p << " instead of " << j << endl;
                return 1;
            }
        }

    cout << "std::lower_bound time: " <<
		(double)(clock() - start) / CLOCKS_PER_SEC  <<
		" seconds" << endl;


    return 0;
}
Wednesday, February 2nd, 2011
11:21 pm
Saturday, December 25th, 2010
2:54 pm
19
Из старой детской книжки:
Возьмите число, состоящее из любого количества девяток. Прибавьте к нему всего одну единицу.
Все девятки превратятся в нули, а единица станет во главе.
Friday, August 13th, 2010
7:40 pm
Opus #14

#pragma once

#include <comdef.h>


inline LPCTSTR DecorateNull(LPCTSTR psz)
{
    return psz? psz : _T("<NULL>");
}


//  ADO_LOGGED_PARAMETER(Parameters) 
//  ADO_LOGGED_PARAMETER(Fields) 
//  ADO_LOGGED_PARAMETER(SearchDirection)
//  ADO_LOGGED_PARAMETER(FieldList)


#define ADO_LOGGED_PARAMETERS \
    ADO_LOGGED_PARAMETER(CommandText) \
    ADO_LOGGED_PARAMETER(Index) \
    ADO_LOGGED_PARAMETER(Name) \
    ADO_LOGGED_PARAMETER(Type) \
    ADO_LOGGED_PARAMETER(Direction) \
    ADO_LOGGED_PARAMETER(Size) \
    ADO_LOGGED_PARAMETER(Value) \
    ADO_LOGGED_PARAMETER(pbstrName) \
    ADO_LOGGED_PARAMETER(pbstr) \
    ADO_LOGGED_PARAMETER(ConnectionString) \
    ADO_LOGGED_PARAMETER(UserID) \
    ADO_LOGGED_PARAMETER(Level) \
    ADO_LOGGED_PARAMETER(plAttr) \
    ADO_LOGGED_PARAMETER(plMode) \
    ADO_LOGGED_PARAMETER(Schema) \
    ADO_LOGGED_PARAMETER(Restrictions) \
    ADO_LOGGED_PARAMETER(SchemaID) \
    ADO_LOGGED_PARAMETER(pval) \
    ADO_LOGGED_PARAMETER(plAttributes) \
    ADO_LOGGED_PARAMETER(pl) \
    ADO_LOGGED_PARAMETER(pfPrepared) \
    ADO_LOGGED_PARAMETER(plTimeout) \
    ADO_LOGGED_PARAMETER(plCursorLoc) \
    ADO_LOGGED_PARAMETER(Source) \
    ADO_LOGGED_PARAMETER(ActiveConnection) \
    ADO_LOGGED_PARAMETER(CursorType) \
    ADO_LOGGED_PARAMETER(LockType) \
    ADO_LOGGED_PARAMETER(Options) \
    ADO_LOGGED_PARAMETER(Object) \
    ADO_LOGGED_PARAMETER(ppvObject) \
    ADO_LOGGED_PARAMETER(RecordsAffected) \
    ADO_LOGGED_PARAMETER(plCmdType) \
    ADO_LOGGED_PARAMETER(Password) \
    ADO_LOGGED_PARAMETER(pvar) \
    ADO_LOGGED_PARAMETER(pvBookmark) \
    ADO_LOGGED_PARAMETER(plLockType) \
    ADO_LOGGED_PARAMETER(plMaxRecords) \
    ADO_LOGGED_PARAMETER(pvSource) \
    ADO_LOGGED_PARAMETER(Values) \
    ADO_LOGGED_PARAMETER(AffectRecords) \
    ADO_LOGGED_PARAMETER(Rows) \
    ADO_LOGGED_PARAMETER(Start) \
    ADO_LOGGED_PARAMETER(Criteria) \
    ADO_LOGGED_PARAMETER(CursorOptions) \
    ADO_LOGGED_PARAMETER(peMarshal) \
    ADO_LOGGED_PARAMETER(SkipRecords) \
    ADO_LOGGED_PARAMETER(ppunkDataSource) \
    ADO_LOGGED_PARAMETER(FileName) \
    ADO_LOGGED_PARAMETER(PersistFormat) \
    ADO_LOGGED_PARAMETER(pbStayInSync) \
    ADO_LOGGED_PARAMETER(StringFormat) \
    ADO_LOGGED_PARAMETER(NumRows) \
    ADO_LOGGED_PARAMETER(ColumnDelimeter) \
    ADO_LOGGED_PARAMETER(RowDelimeter) \
    ADO_LOGGED_PARAMETER(NullExpr) \
    ADO_LOGGED_PARAMETER(pbstrDataMember) \
    ADO_LOGGED_PARAMETER(Bookmark1) \
    ADO_LOGGED_PARAMETER(Bookmark2) \
    ADO_LOGGED_PARAMETER(ResyncValues) \
    ADO_LOGGED_PARAMETER(KeyValues) \
    ADO_LOGGED_PARAMETER(SeekOption) \
    ADO_LOGGED_PARAMETER(pbstrIndex) \
    ADO_LOGGED_PARAMETER(Destination) \
    ADO_LOGGED_PARAMETER(DefinedSize) \
    ADO_LOGGED_PARAMETER(Attrib) \
    ADO_LOGGED_PARAMETER(FieldValue) \
    ADO_LOGGED_PARAMETER(Data) \
    ADO_LOGGED_PARAMETER(ppiDF) \
    ADO_LOGGED_PARAMETER(pbPrecision) \
    ADO_LOGGED_PARAMETER(pbNumericScale) \
    ADO_LOGGED_PARAMETER(pDataType) \
    ADO_LOGGED_PARAMETER(adReason) \
    ADO_LOGGED_PARAMETER(cFields) \
    ADO_LOGGED_PARAMETER(Val) \
    ADO_LOGGED_PARAMETER(plParmAttribs) \
    ADO_LOGGED_PARAMETER(pvStream) \
    ADO_LOGGED_PARAMETER(pbScale) \
    ADO_LOGGED_PARAMETER(psDataType) \
    ADO_LOGGED_PARAMETER(plParmDirection) \
    ADO_LOGGED_PARAMETER(pbstrDialect) \
    ADO_LOGGED_PARAMETER(pfNamedParameters) \
    ADO_LOGGED_PARAMETER(pError) \
    ADO_LOGGED_PARAMETER(adStatus) \
    ADO_LOGGED_PARAMETER(pCommand) \
    ADO_LOGGED_PARAMETER(pConnection) \
    ADO_LOGGED_PARAMETER(cRecords) \
    ADO_LOGGED_PARAMETER(fMoreData) \
    ADO_LOGGED_PARAMETER(Progress) \
    ADO_LOGGED_PARAMETER(MaxProgress) \
    ADO_LOGGED_PARAMETER(pDSO) \
    ADO_LOGGED_PARAMETER(pSession) \
    ADO_LOGGED_PARAMETER(UserName) \
    ADO_LOGGED_PARAMETER(Async) \
    ADO_LOGGED_PARAMETER(Mode) \
    ADO_LOGGED_PARAMETER(CreateOptions) \
    ADO_LOGGED_PARAMETER(pPos) \
    ADO_LOGGED_PARAMETER(ptype) \
    ADO_LOGGED_PARAMETER(pLS) \
    ADO_LOGGED_PARAMETER(pMode) \
    ADO_LOGGED_PARAMETER(pbstrCharset) \
    ADO_LOGGED_PARAMETER(NumBytes) \
    ADO_LOGGED_PARAMETER(Buffer) \
    ADO_LOGGED_PARAMETER(DestStream) \
    ADO_LOGGED_PARAMETER(CharNumber) \
    ADO_LOGGED_PARAMETER(NumChars) \
    ADO_LOGGED_PARAMETER(ppRow) \
    ADO_LOGGED_PARAMETER(_arg1) \
    ADO_LOGGED_PARAMETER(ppStm) \
    ADO_LOGGED_PARAMETER(ppOLEDBCommand) \
    ADO_LOGGED_PARAMETER(ppRowset) \
    ADO_LOGGED_PARAMETER(plChapter) \
    ADO_LOGGED_PARAMETER(ppRowPos) \
    ADO_LOGGED_PARAMETER(Length) 

#define ADO_LOGGED_PARAMETER(name) name,

enum AdoMissingParameters {
    ADO_LOGGED_PARAMETERS
};

#undef ADO_LOGGED_PARAMETER


inline CString AdoLoggingParameter(LPCSTR name, const _bstr_t& value)
{
    CString result(name);
    result += ": ";
    result += DecorateNull(value);
    result += ", ";
    return result;
}

inline CString AdoLoggingParameter(LPCSTR name, const _variant_t& value)
{
    CString result(name);
    result += ": ";
    try 
    {
        result += DecorateNull((_bstr_t) value);
    }
    catch (...)
    {
        result += "<Error>";
    }
    result += ", ";
    return result;
}

inline CString AdoLoggingParameter(LPCSTR name, int value)
{
    CString result;
    result.Format("%s: %d, ", name, value);
    return result;
}

inline CString AdoLoggingParameter(LPCSTR name, long value)
{
    CString result;
    result.Format("%s: %ld, ", name, value);
    return result;
}

inline CString AdoLoggingParameter(LPCSTR name, short value)
{
    CString result;
    result.Format("%s: %d, ", name, (int) value);
    return result;
}

inline CString AdoLoggingParameter(LPCSTR name, void* value)
{
    CString result;
    result.Format("%s: 0x%x, ", name, (DWORD) value);
    return result;
}


struct Empty {};

inline Empty AdoLoggingParameter(LPCSTR, AdoMissingParameters)
{
    return Empty();
}

inline const CString& operator + (const CString& str, const Empty&)
{
    return str;
}


#define ADO_LOGGED_PARAMETER(name) + AdoLoggingParameter(#name, name)

#define _com_issue_errorex(hr, pUnk, refiid)    \
do {                                            \
    try {                                       \
        _com_issue_errorex((hr), (pUnk), (refiid)); \
    }                                           \
    catch (...) {                               \
        TRACE(CString() ADO_LOGGED_PARAMETERS + "Throwing exception ...");  \
        throw;                                  \
    }                                           \
} while (false)                                 \




#pragma warning(push)
#pragma warning(disable: 4146)
#import <C:\Program Files\Common Files\System\ado\msado15.dll> no_namespace rename( "EOF", "adoEOF" ) 
#pragma warning(pop)

#undef ADO_LOGGED_PARAMETER
#undef ADO_LOGGED_PARAMETERS
#undef _com_issue_errorex

Sunday, July 4th, 2010
3:09 pm
Вести с полей
ХозяйствоУрожайность
FaceBull21.134
Find Sophie34.877
Refrigerator Madness367.966
We Are The Swarm1423.756
Peak Traffic1825.610
Breathalyzer120.799
User Bin Crash23.988
Gattaca49.530
It's A Small World568.933


Внесены изменения за период до 7 мая 2011
Friday, June 11th, 2010
5:31 pm
Opus #13
Нельзя не согласиться,
Что нет на свете краше
Державнейшей Отчизны,
Страны Великой Нашей.
А если кто посмеет
И будет нам перечить,
Мы подлеца сумеем
Поймать и обезвредить.
Добры мы по природе,
Но нюни не разводим.
Мы сразу покараем
Такого негодяя,
Такого негодяя
На месте расстреляем.
Monday, June 7th, 2010
11:53 am
Opus #12
create or replace package data_change_stat
as
   TYPE t_nom_rec IS RECORD (
	  TABLENAME   VARCHAR2(30 BYTE),
	  FIELDNAME   VARCHAR2(30 BYTE),
	  MODIFYDATE  DATE,
	  MODIFYUID   VARCHAR2(30 BYTE),
	  ACTION      VARCHAR2(1 BYTE),
	  OLDVALUE    VARCHAR2(400 BYTE),
	  NEWVALUE    VARCHAR2(400 BYTE)
  );
  
  type master_table_t is table of t_nom_rec;

	FUNCTION AUDIT_ID_SEARCH(SCHEMA_NAME IN VARCHAR2, START_TIME IN DATE, MIN_ID_ IN NUMBER, MAX_ID_ IN NUMBER)
	RETURN NUMBER;
   
   function data_change(SCHEMA_NAME IN VARCHAR2, begin_date in DATE, end_date in DATE)
      return  master_table_t pipelined;
end data_change_stat;
/

create or replace package body data_change_stat
as

	FUNCTION AUDIT_ID_SEARCH(SCHEMA_NAME IN VARCHAR2, START_TIME IN DATE, MIN_ID_ IN NUMBER, MAX_ID_ IN NUMBER)
	RETURN NUMBER
	IS
		PROBE_ID NUMBER;
		PROBE_TIME DATE;
		
		MIN_ID NUMBER;
		MAX_ID NUMBER;
		MEDIAN_ID NUMBER;
	BEGIN
		MIN_ID := MIN_ID_;
		MAX_ID := MAX_ID_;
	
		WHILE MIN_ID <= MAX_ID LOOP
			MEDIAN_ID := MIN_ID + FLOOR((MAX_ID - MIN_ID) / 2);
			BEGIN
				EXECUTE IMMEDIATE 'SELECT AUDITID, MODIFYDATE FROM ' || SCHEMA_NAME || '.AUDIT WHERE AUDITID = :0' 
					INTO PROBE_ID, PROBE_TIME USING MEDIAN_ID;
			EXCEPTION
				WHEN NO_DATA_FOUND THEN 
					EXECUTE IMMEDIATE 'SELECT AUDITID, MODIFYDATE FROM ' || SCHEMA_NAME 
					|| '.AUDIT WHERE AUDITID = (SELECT MIN(AUDITID) FROM ' || SCHEMA_NAME || '.AUDIT WHERE AUDITID >= :0)' 
					INTO PROBE_ID, PROBE_TIME USING MEDIAN_ID;
			END;
			IF PROBE_TIME < START_TIME THEN
				MIN_ID := PROBE_ID + 1;
			ELSE
				MAX_ID := MEDIAN_ID - 1;
			END IF;
		END LOOP;
		RETURN MIN_ID;
	END AUDIT_ID_SEARCH;


   function data_change(SCHEMA_NAME IN VARCHAR2, begin_date in DATE, end_date in DATE)
      return master_table_t
      pipelined
   is
      r      t_nom_rec;
      type cur_typ is ref cursor;
      cur cur_typ;
      
		MIN_ID NUMBER;
		MAX_ID NUMBER;
		
   begin
   
		EXECUTE IMMEDIATE 'SELECT MIN(AUDITID) FROM ' || SCHEMA_NAME || '.AUDIT' INTO MIN_ID;
		EXECUTE IMMEDIATE 'SELECT MAX(AUDITID) FROM ' || SCHEMA_NAME || '.AUDIT' INTO MAX_ID;
   
		MIN_ID := AUDIT_ID_SEARCH(SCHEMA_NAME, begin_date, MIN_ID, MAX_ID);
		MAX_ID := AUDIT_ID_SEARCH(SCHEMA_NAME, end_date, MIN_ID, MAX_ID);
   
      open cur for 'select TABLENAME, FIELDNAME, MODIFYDATE, MODIFYUID, ACTION, OLDVALUE, NEWVALUE from ' 
		|| SCHEMA_NAME || '.AUDIT where auditid between ' 
		|| MIN_ID || ' and ' || MAX_ID
		|| ' ORDER BY MODIFYUID, TABLENAME, MODIFYDATE';
 
      loop
         fetch cur into r;
        
         exit when cur%notfound;
         pipe row (r);
      end loop;
 
      return;
   end data_change;
end data_change_stat;
/
Tuesday, May 18th, 2010
5:53 pm
I Believe In Cash
When I'm waking up I hope
my lucky day has come.
When I go to sleep, I weep,
because my dream has gone.
Guess, I'm not the only one,
who's feeling like I do.
But I know that Cash
'sgonna make my dream come true,
Ye-ah

Cash, I believe in Cash,
Everlasting Cash -
For every one of us to share, ye-ah
Cash, all I need is Cash,
all I'm asking for -
in every wish, in every prayer
Tuesday, April 27th, 2010
2:23 pm
Is there any sense in such an "achievement" ?
Here it is.
"А мы тут, знаете, всё плюшками балуемся ..."
Saturday, February 27th, 2010
2:12 pm
Austrian medical student hanged himself in Minsk hostel
The Office of Public Prosecutor of the Moscow area of Minsk inspects upon death of a student from Austria who was found hung up in a bathroom of a hostel of medical university, the senior assistant to the public prosecutor of Minsk Sergey Balashev told "Interfax-West".

"In a hostel of the Belarus state medical university, in a bathroom, the body of the first-year student, a citizen of Austria" was revealed, said S.Balashev.

As he said, "the body in a loop, hanging in a bathroom, was found by neighbors in a hostel. The Office of Public Prosecutor of the Moscow area carries out a check".

http://www.interfax.by/news/belarus/68380
[ << Previous 20 ]
About LiveJournal.com