source: GTP/trunk/Lib/Vis/Preprocessing/src/MxHeap.cxx @ 1097

Revision 1097, 2.5 KB checked in by mattausch, 18 years ago (diff)
Line 
1/************************************************************************
2
3  Heap data structure
4
5  Copyright (C) 1998 Michael Garland.  See "COPYING.txt" for details.
6 
7  $Id: MxHeap.cxx,v 1.1 2002/09/24 16:53:54 wimmer Exp $
8
9 ************************************************************************/
10
11//#include "stdmix.h"
12#include "MxHeap.h"
13
14
15////////////////////////////////////////////////////////////////////////
16//
17// Internal functions for manipulating the heap
18
19inline void MxHeap::place(MxHeapable *x, unsigned int i)
20{
21    ref(i) = x;
22    x->set_heap_pos(i);
23}
24
25void MxHeap::swap(unsigned int i, unsigned int j)
26{
27    MxHeapable *tmp = ref(i);
28
29    place(ref(j), i);
30    place(tmp, j);
31}
32
33void MxHeap::upheap(unsigned int i)
34{
35    MxHeapable *moving = ref(i);
36    uint index = i;
37    uint p = parent(i);
38
39    while( index>0 && moving->heap_key() > ref(p)->heap_key() )
40    {
41        place(ref(p), index);
42        index = p;
43        p = parent(p);
44    }
45
46    if( index != i )
47        place(moving, index);
48}
49
50void MxHeap::downheap(unsigned int i)
51{
52    MxHeapable *moving = ref(i);
53    uint index = i;
54    uint l = left(i);
55    uint r = right(i);
56    uint largest;
57
58    while( l<length() )
59    {
60        if( r<length() && ref(l)->heap_key() < ref(r)->heap_key() )
61            largest = r;
62        else
63            largest = l;
64
65        if( moving->heap_key() < ref(largest)->heap_key() )
66        {
67            place(ref(largest), index);
68            index = largest;
69            l = left(index);
70            r = right(index);
71        }
72        else
73            break;
74    }
75
76    if( index != i )
77        place(moving, index);
78}
79
80////////////////////////////////////////////////////////////////////////
81//
82// Exported interface to the heap
83//
84
85void MxHeap::insert(MxHeapable *t, float v)
86{
87    t->heap_key(v);
88
89    unsigned int i = add(t);
90    t->set_heap_pos(i);
91
92    upheap(i);
93}
94
95void MxHeap::update(MxHeapable *t, float v)
96{
97    SanityCheck( t->is_in_heap() );
98    t->heap_key(v);
99
100    unsigned int i = t->get_heap_pos();
101
102    if( i>0 && v>ref(parent(i))->heap_key() )
103        upheap(i);
104    else
105        downheap(i);
106}
107
108MxHeapable *MxHeap::extract()
109{
110    if( length() < 1 ) return NULL;
111
112    swap(0, length()-1);
113    MxHeapable *dead=drop();
114
115    downheap(0);
116    dead->not_in_heap();
117    return dead;
118}
119
120MxHeapable *MxHeap::remove(MxHeapable *t)
121{
122    if( !t->is_in_heap() ) return NULL;
123
124    int i = t->get_heap_pos();
125    swap(i, length()-1);
126    drop();
127    t->not_in_heap();
128
129    if( ref(i)->heap_key() < t->heap_key() )
130        downheap(i);
131    else
132        upheap(i);
133
134    return t;
135}
Note: See TracBrowser for help on using the repository browser.