← Back to branch summary

~baltix/+junk/irrlicht-test

« back to all changes in this revision

Viewing changes to include/heapsort.h

  • Committer: Mantas Kriaučiūnas
  • Date: 2011-07-18 13:06:25 UTC
  • Revision ID: mantas@akl.lt-20110718130625-c5pvifp61e7kj1ol
Included whole irrlicht SVN libraries to work around launchpad recipe issue with quilt, see https://answers.launchpad.net/launchpad/+question/165193

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/heapsort.h
 
1
// Copyright (C) 2002-2011 Nikolaus Gebhardt
 
2
// This file is part of the "Irrlicht Engine".
 
3
// For conditions of distribution and use, see copyright notice in irrlicht.h
 
4
 
 
5
#ifndef __IRR_HEAPSORT_H_INCLUDED__
 
6
#define __IRR_HEAPSORT_H_INCLUDED__
 
7
 
 
8
#include "irrTypes.h"
 
9
 
 
10
namespace irr
 
11
{
 
12
namespace core
 
13
{
 
14
 
 
15
//! Sinks an element into the heap.
 
16
template<class T>
 
17
inline void heapsink(T*array, s32 element, s32 max)
 
18
{
 
19
        while ((element<<1) < max) // there is a left child
 
20
        {
 
21
                s32 j = (element<<1);
 
22
 
 
23
                if (j+1 < max && array[j] < array[j+1])
 
24
                        j = j+1; // take right child
 
25
 
 
26
                if (array[element] < array[j])
 
27
                {
 
28
                        T t = array[j]; // swap elements
 
29
                        array[j] = array[element];
 
30
                        array[element] = t;
 
31
                        element = j;
 
32
                }
 
33
                else
 
34
                        return;
 
35
        }
 
36
}
 
37
 
 
38
 
 
39
//! Sorts an array with size 'size' using heapsort.
 
40
template<class T>
 
41
inline void heapsort(T* array_, s32 size)
 
42
{
 
43
        // for heapsink we pretent this is not c++, where
 
44
        // arrays start with index 0. So we decrease the array pointer,
 
45
        // the maximum always +2 and the element always +1
 
46
 
 
47
        T* virtualArray = array_ - 1;
 
48
        s32 virtualSize = size + 2;
 
49
        s32 i;
 
50
 
 
51
        // build heap
 
52
 
 
53
        for (i=((size-1)/2); i>=0; --i)
 
54
                heapsink(virtualArray, i+1, virtualSize-1);
 
55
 
 
56
        // sort array, leave out the last element (0)
 
57
        for (i=size-1; i>0; --i)
 
58
        {
 
59
                T t = array_[0];
 
60
                array_[0] = array_[i];
 
61
                array_[i] = t;
 
62
                heapsink(virtualArray, 1, i + 1);
 
63
        }
 
64
}
 
65
 
 
66
} // end namespace core
 
67
} // end namespace irr
 
68
 
 
69
#endif
 
70