Subversion Repositories openrisc

// This file is part of the uSTL library, an STL implementation.

//

// Copyright (c) 2005-2009 by Mike Sharov <msharov@users.sourceforge.net>

// This file is free software, distributed under the MIT License.

#include "stdtest.h"

static void HeapSize (size_t nElements, size_t& layerWidth, size_t& nLayers)

{

    layerWidth = 0;

    nLayers = 0;

    for (size_t fts = 0; nElements > fts; fts += layerWidth) {

        layerWidth *= 2;

        if (!layerWidth)

            ++ layerWidth;

        ++ nLayers;

    }

}

static void PrintSpace (size_t n)

{

    for (uoff_t s = 0; s < n; ++ s)

        cout << ' ';

}

static void PrintHeap (const vector<int>& v)

{

    size_t maxWidth, nLayers;

    HeapSize (v.size(), maxWidth, nLayers);

    vector<int>::const_iterator src (v.begin());

    cout << ios::width(3);

    maxWidth *= 3;

    for (uoff_t i = 0; i < nLayers; ++ i) {

        const size_t w = 1 << i;

        const size_t spacing = max (0, int(maxWidth / w) - 3);

        PrintSpace (spacing / 2);

        for (uoff_t j = 0; j < w && src != v.end(); ++ j) {

            cout << *src++;

            if (j < w - 1 && src != v.end() - 1)

                PrintSpace (spacing);

        }

        cout << endl;

    }

}

void TestHeapOperations (void)

{

    static const int c_Values [31] = {  // 31 values make a full 4-layer tree

        93, 92, 90, 86, 83, 86, 77, 40, 72, 36, 68, 82, 62, 67, 63, 15,

        26, 26, 49, 21, 11, 62, 67, 27, 29, 30, 35, 23, 59, 35, 29

    };

    vector<int> v;

    v.reserve (VectorSize(c_Values));

    for (uoff_t i = 0; i < VectorSize(c_Values); ++ i) {

        v.push_back (c_Values[i]);

        push_heap (v.begin(), v.end());

        cout << "------------------------------------------------\n";

        if (!is_heap (v.begin(), v.end()))

            cout << "Is NOT a heap\n";

        PrintHeap (v);

    }

    cout << "------------------------------------------------\n";

    cout << "make_heap on the full range:\n";

    v.resize (VectorSize (c_Values));

    copy (VectorRange(c_Values), v.begin());

    make_heap (v.begin(), v.end());

    PrintHeap (v);

    if (!is_heap (v.begin(), v.end()))

        cout << "Is NOT a heap\n";

    cout << "------------------------------------------------\n";

    cout << "pop_heap:\n";

    pop_heap (v.begin(), v.end());

    v.pop_back();

    PrintHeap (v);

    if (!is_heap (v.begin(), v.end()))

        cout << "Is NOT a heap\n";

    cout << "------------------------------------------------\n";

    cout << "sort_heap:\n";

    v.resize (VectorSize (c_Values));

    copy (VectorRange(c_Values), v.begin());

    make_heap (v.begin(), v.end());

    sort_heap (v.begin(), v.end());

    foreach (vector<int>::const_iterator, i, v)

        cout << *i;

    cout << endl;

    cout << "------------------------------------------------\n";

    cout << "priority_queue push and pop:\n";

    priority_queue<int> q;

    for (uoff_t i = 0; i < VectorSize(c_Values); ++ i)

        q.push (c_Values[i]);

    while (!q.empty()) {

        cout << q.top();

        q.pop();

    }

    cout << endl;

}

StdBvtMain (TestHeapOperations)