1 /**************************************************************
2 *
3 * Licensed to the Apache Software Foundation (ASF) under one
4 * or more contributor license agreements. See the NOTICE file
5 * distributed with this work for additional information
6 * regarding copyright ownership. The ASF licenses this file
7 * to you under the Apache License, Version 2.0 (the
8 * "License"); you may not use this file except in compliance
9 * with the License. You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing,
14 * software distributed under the License is distributed on an
15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16 * KIND, either express or implied. See the License for the
17 * specific language governing permissions and limitations
18 * under the License.
19 *
20 *************************************************************/
21
22
23
24 #include <string.h>
25 #include "heap.hxx"
26
27
28 #include <iostream>
29 #include <stdlib.h>
30 #define AssertionOf(x) {if (!(x)) {std::cerr << "Assertion failed: " << #x << __FILE__ << __LINE__ << std::endl; exit(3); }}
31
32 #ifdef UNX
33 #define stricmp strcasecmp
34 #endif
35
36
37
Heap(unsigned i_nWidth)38 Heap::Heap(unsigned i_nWidth)
39 : dpColumnsArray(new Column[i_nWidth]),
40 nColumnsArraySize(i_nWidth),
41 nActiveColumn(nColumnsArraySize-1)
42 {
43 for ( unsigned i = 0; i < nColumnsArraySize; i++)
44 {
45 dpColumnsArray[i] = 0;
46 } // end for
47 }
48
~Heap()49 Heap::~Heap()
50 {
51 for ( unsigned i = 0; i < nColumnsArraySize; i++)
52 {
53 HeapItem * & rColumn = dpColumnsArray[i];
54 for ( HeapItem * pValue = rColumn; pValue != 0; pValue = rColumn )
55 {
56 rColumn = rColumn->Next();
57 delete pValue;
58 }
59 } // end for
60
61 delete [] dpColumnsArray;
62 }
63
64 void
InsertValue(const char * i_sKey,const char * i_sValue)65 Heap::InsertValue( const char * i_sKey,
66 const char * i_sValue )
67 {
68 HeapItem * pSearch1 = 0;
69 HeapItem * pSearch2 = 0;
70 HeapItem * pNew = new HeapItem(i_sKey, i_sValue);
71
72 IncColumn();
73 pSearch1 = ActiveColumn();
74
75 if ( pSearch1 != 0 ? *pNew < *pSearch1 : true )
76 {
77 pNew->SetNext( pSearch1 );
78 ActiveColumn() = pNew;
79
80 if ( pNew->Next() != 0)
81 {
82 AssertionOf( *pNew <= *pNew->Next() );
83 }
84
85 return;
86 }
87
88 do
89 {
90 pSearch2 = pSearch1;
91 pSearch1 = pSearch1->Next();
92
93 if ( pSearch1 != 0 ? *pNew < *pSearch1 : true )
94 {
95 pNew->SetNext( pSearch1 );
96 pSearch2->SetNext(pNew);
97
98
99 AssertionOf( *pSearch2 <= *pNew );
100 if ( pNew->Next() != 0)
101 {
102 AssertionOf( *pNew <= *pNew->Next() );
103 }
104
105 }
106 } while (pSearch2->Next() != pNew);
107 }
108
109
110 Simstr sKey1;
111 Simstr sValue1;
112 Simstr sKey2;
113 Simstr sValue2;
114 int nCol1 = 0;
115 int nCol2 = 0;
116
117
118 HeapItem *
ReleaseTop()119 Heap::ReleaseTop()
120 {
121 unsigned nRetColumn = 0;
122 HeapItem * ret = dpColumnsArray[0];
123 HeapItem * pSearch = 0;
124
125 for ( unsigned i = 1; i < nColumnsArraySize; ++i )
126 {
127 pSearch = dpColumnsArray[i];
128 if (pSearch != 0)
129 {
130 if ( ret == 0 ? true : *pSearch < *ret)
131 {
132 ret = pSearch;
133 nRetColumn = i;
134 }
135 }
136 } // for
137
138 if (ret != 0)
139 {
140 dpColumnsArray[nRetColumn] = ret->Next();
141 }
142 return ret;
143 }
144
145 void
IncColumn()146 Heap::IncColumn()
147 {
148 if (++nActiveColumn >= nColumnsArraySize)
149 nActiveColumn = 0;
150 }
151
152
153
HeapItem(const char * i_sKey,const char * i_sValue)154 HeapItem::HeapItem( const char * i_sKey,
155 const char * i_sValue )
156 : sValue(i_sValue),
157 sKey(i_sKey),
158 pNext(0)
159 {
160 }
161
~HeapItem()162 HeapItem::~HeapItem()
163 {
164 }
165
166 bool
operator <(const HeapItem & i_rOther) const167 HeapItem::operator<( const HeapItem & i_rOther ) const
168 {
169 int ret = stricmp(sKey.str(), i_rOther.sKey.str());
170 if (ret == 0)
171 ret = strcmp(sKey.str(), i_rOther.sKey.str());
172 if (ret == 0)
173 ret = stricmp(sValue.str(), i_rOther.sValue.str());
174 if (ret == 0)
175 ret = strcmp(sValue.str(), i_rOther.sValue.str());
176 return ret < 0;
177 }
178
179 const Simstr &
Value() const180 HeapItem::Value() const
181 {
182 return sValue;
183 }
184
185 const Simstr &
Key() const186 HeapItem::Key() const
187 {
188 return sKey;
189 }
190
191 HeapItem *
Next() const192 HeapItem::Next() const
193 {
194 return pNext;
195 }
196
197 void
SetNext(HeapItem * i_pNext)198 HeapItem::SetNext( HeapItem * i_pNext )
199 {
200 pNext = i_pNext;
201 }
202
203
204