xref: /trunk/main/xml2cmp/source/support/heap.cxx (revision ab595ff6)
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