xref: /trunk/main/xml2cmp/source/support/heap.cxx (revision cdf0e10c)
1 /*************************************************************************
2  *
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * Copyright 2000, 2010 Oracle and/or its affiliates.
6  *
7  * OpenOffice.org - a multi-platform office productivity suite
8  *
9  * This file is part of OpenOffice.org.
10  *
11  * OpenOffice.org is free software: you can redistribute it and/or modify
12  * it under the terms of the GNU Lesser General Public License version 3
13  * only, as published by the Free Software Foundation.
14  *
15  * OpenOffice.org is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18  * GNU Lesser General Public License version 3 for more details
19  * (a copy is included in the LICENSE file that accompanied this code).
20  *
21  * You should have received a copy of the GNU Lesser General Public License
22  * version 3 along with OpenOffice.org.  If not, see
23  * <http://www.openoffice.org/license.html>
24  * for a copy of the LGPLv3 License.
25  *
26  ************************************************************************/
27 
28 #include <string.h>
29 #include "heap.hxx"
30 
31 
32 #include <iostream>
33 #include <stdlib.h>
34 #define AssertionOf(x)	{if (!(x)) {std::cerr << "Assertion failed: " << #x << __FILE__ << __LINE__ << std::endl; exit(3); }}
35 
36 #ifdef UNX
37 #define stricmp strcasecmp
38 #endif
39 
40 
41 
42 Heap::Heap(unsigned	i_nWidth)
43 	:	dpColumnsArray(new Column[i_nWidth]),
44 		nColumnsArraySize(i_nWidth),
45 		nActiveColumn(nColumnsArraySize-1)
46 {
47 	for ( unsigned i = 0; i < nColumnsArraySize; i++)
48 	{
49 		dpColumnsArray[i] = 0;
50 	}  // end for
51 }
52 
53 Heap::~Heap()
54 {
55 	for ( unsigned i = 0; i < nColumnsArraySize; i++)
56 	{
57 		HeapItem * & rColumn = dpColumnsArray[i];
58 		for ( HeapItem * pValue = rColumn; pValue != 0; pValue = rColumn )
59 		{
60 			rColumn = rColumn->Next();
61 			delete pValue;
62 		}
63 	}  // end for
64 
65 	delete [] dpColumnsArray;
66 }
67 
68 void
69 Heap::InsertValue( const char *		i_sKey,
70 				   const char *	   	i_sValue )
71 {
72 	HeapItem * pSearch1 = 0;
73 	HeapItem * pSearch2 = 0;
74 	HeapItem * pNew = new HeapItem(i_sKey, i_sValue);
75 
76 	IncColumn();
77 	pSearch1 = ActiveColumn();
78 
79 	if ( pSearch1 != 0 ? *pNew < *pSearch1 : true )
80 	{
81 		pNew->SetNext( pSearch1 );
82 		ActiveColumn() = pNew;
83 
84 		if ( pNew->Next() != 0)
85 		{
86 			AssertionOf( *pNew <= *pNew->Next() );
87 		}
88 
89 		return;
90 	}
91 
92 	do
93 	{
94 		pSearch2 = pSearch1;
95 		pSearch1 = pSearch1->Next();
96 
97 		if ( pSearch1 != 0 ? *pNew < *pSearch1 : true )
98 		{
99 			pNew->SetNext( pSearch1 );
100 			pSearch2->SetNext(pNew);
101 
102 
103 		AssertionOf( *pSearch2 <= *pNew );
104 		if ( pNew->Next() != 0)
105 		{
106 			AssertionOf( *pNew <= *pNew->Next() );
107 		}
108 
109 		}
110 	} while (pSearch2->Next() != pNew);
111 }
112 
113 
114 Simstr sKey1;
115 Simstr sValue1;
116 Simstr sKey2;
117 Simstr sValue2;
118 int nCol1 = 0;
119 int nCol2 = 0;
120 
121 
122 HeapItem *
123 Heap::ReleaseTop()
124 {
125 	unsigned nRetColumn = 0;
126 	HeapItem * ret = dpColumnsArray[0];
127 	HeapItem * pSearch = 0;
128 
129 	for ( unsigned i = 1; i < nColumnsArraySize; ++i )
130 	{
131 		pSearch = dpColumnsArray[i];
132 		if (pSearch != 0)
133 		{
134 			if ( ret == 0 ? true : *pSearch < *ret)
135 			{
136 				ret = pSearch;
137 				nRetColumn = i;
138 			}
139 		}
140 	}	// for
141 
142 	if (ret != 0)
143 	{
144 		dpColumnsArray[nRetColumn] = ret->Next();
145 	}
146 	return ret;
147 }
148 
149 void
150 Heap::IncColumn()
151 {
152 	if (++nActiveColumn >= nColumnsArraySize)
153 		nActiveColumn = 0;
154 }
155 
156 
157 
158 HeapItem::HeapItem( const char *		i_sKey,
159 					const char *	   	i_sValue )
160 	:	sValue(i_sValue),
161 		sKey(i_sKey),
162 		pNext(0)
163 {
164 }
165 
166 HeapItem::~HeapItem()
167 {
168 }
169 
170 bool
171 HeapItem::operator<( const HeapItem & i_rOther ) const
172 {
173 	int ret = stricmp(sKey.str(), i_rOther.sKey.str());
174 	if (ret == 0)
175 		ret = strcmp(sKey.str(), i_rOther.sKey.str());
176 	if (ret == 0)
177 		ret = stricmp(sValue.str(), i_rOther.sValue.str());
178 	if (ret == 0)
179 		ret = strcmp(sValue.str(), i_rOther.sValue.str());
180 	return ret < 0;
181 }
182 
183 const Simstr &
184 HeapItem::Value() const
185 {
186 	return sValue;
187 }
188 
189 const Simstr &
190 HeapItem::Key() const
191 {
192 	return sKey;
193 }
194 
195 HeapItem *
196 HeapItem::Next() const
197 {
198 	return pNext;
199 }
200 
201 void
202 HeapItem::SetNext( HeapItem * i_pNext )
203 {
204 	pNext = i_pNext;
205 }
206 
207 
208