/
ChemicalBurnOrderedQueue.mm
110 lines (86 loc) · 1.68 KB
/
ChemicalBurnOrderedQueue.mm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//
// ChemicalBurnOrderedQueue.m
// ChemicalBurn
//
// Created by Michael Ash on 7/11/06.
// Copyright 2006 __MyCompanyName__. All rights reserved.
//
#import "ChemicalBurnOrderedQueue.h"
#import <algorithm>
struct CBOQNode {
id obj;
unsigned val;
};
static bool NodeLessThan( struct CBOQNode &n1, struct CBOQNode &n2 )
{
if( n1.val != n2.val )
return n1.val > n2.val;
else
return (uintptr_t)n1.obj < (uintptr_t)n2.obj;
}
@implementation ChemicalBurnOrderedQueue
- init
{
if( ( self = [super init] ) )
{
mCount = 0;
mCapacity = 100;
mObjs = (struct CBOQNode *)malloc( mCapacity * sizeof( *mObjs ) );
}
return self;
}
- (void)dealloc
{
free( mObjs );
[super dealloc];
}
- (void)finalize
{
free( mObjs );
[super finalize];
}
#pragma mark -
- (void)buildheap
{
std::make_heap( mObjs, mObjs + mCount, NodeLessThan );
mHeapified = YES;
}
#pragma mark -
- (unsigned)count
{
return mCount;
}
- (void)addObject: (id)obj value: (unsigned)val
{
mCount++;
if( mCount > mCapacity )
{
mCapacity *= 2;
mObjs = (struct CBOQNode *)realloc( mObjs, mCapacity * sizeof( *mObjs ) );
}
mObjs[mCount - 1].obj = obj;
mObjs[mCount - 1].val = val;
if( mHeapified )
std::push_heap( mObjs, mObjs + mCount, NodeLessThan );
}
- (id)pop
{
if( !mHeapified )
{
[self buildheap];
}
std::pop_heap( mObjs, mObjs + mCount, NodeLessThan );
mCount--;
return mObjs[mCount].obj;
}
- (NSString *)description
{
NSMutableString *str = [NSMutableString string];
[str appendString: @"ChemicalBurnOrderedQueue = (\n"];
unsigned i;
for( i = 0; i < mCount; i++ )
[str appendFormat: @"\t%@ = %u\n", mObjs[i].obj, mObjs[i].val];
[str appendString: @")\n"];
return str;
}
@end