Branch data Line data Source code
1 : : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : : /*
3 : : * This file is part of the LibreOffice project.
4 : : *
5 : : * This Source Code Form is subject to the terms of the Mozilla Public
6 : : * License, v. 2.0. If a copy of the MPL was not distributed with this
7 : : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 : : *
9 : : * This file incorporates work covered by the following license notice:
10 : : *
11 : : * Licensed to the Apache Software Foundation (ASF) under one or more
12 : : * contributor license agreements. See the NOTICE file distributed
13 : : * with this work for additional information regarding copyright
14 : : * ownership. The ASF licenses this file to you under the Apache
15 : : * License, Version 2.0 (the "License"); you may not use this file
16 : : * except in compliance with the License. You may obtain a copy of
17 : : * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 : : */
19 : :
20 : : #include <string.h>
21 : : #include "heap.hxx"
22 : :
23 : :
24 : : #include <iostream>
25 : : #include <stdlib.h>
26 : : #define AssertionOf(x) {if (!(x)) {std::cerr << "Assertion failed: " << #x << __FILE__ << __LINE__ << std::endl; exit(3); }}
27 : :
28 : : #ifdef UNX
29 : : #define stricmp strcasecmp
30 : : #endif
31 : :
32 : :
33 : :
34 : 2 : Heap::Heap(unsigned i_nWidth)
35 : 2 : : dpColumnsArray(new Column[i_nWidth]),
36 : : nColumnsArraySize(i_nWidth),
37 : 2 : nActiveColumn(nColumnsArraySize-1)
38 : : {
39 [ + + ]: 26 : for ( unsigned i = 0; i < nColumnsArraySize; i++)
40 : : {
41 : 24 : dpColumnsArray[i] = 0;
42 : : } // end for
43 : 2 : }
44 : :
45 : 2 : Heap::~Heap()
46 : : {
47 [ + + ]: 26 : for ( unsigned i = 0; i < nColumnsArraySize; i++)
48 : : {
49 : 24 : HeapItem * & rColumn = dpColumnsArray[i];
50 [ - + ]: 24 : for ( HeapItem * pValue = rColumn; pValue != 0; pValue = rColumn )
51 : : {
52 : 0 : rColumn = rColumn->Next();
53 [ # # ]: 0 : delete pValue;
54 : : }
55 : : } // end for
56 : :
57 [ + - ]: 2 : delete [] dpColumnsArray;
58 : 2 : }
59 : :
60 : : void
61 : 406 : Heap::InsertValue( const char * i_sKey,
62 : : const char * i_sValue )
63 : : {
64 : 406 : HeapItem * pSearch1 = 0;
65 : 406 : HeapItem * pSearch2 = 0;
66 [ + - ]: 406 : HeapItem * pNew = new HeapItem(i_sKey, i_sValue);
67 : :
68 : 406 : IncColumn();
69 : 406 : pSearch1 = ActiveColumn();
70 : :
71 [ + + ][ + + ]: 406 : if ( pSearch1 != 0 ? *pNew < *pSearch1 : true )
72 : : {
73 : 80 : pNew->SetNext( pSearch1 );
74 : 80 : ActiveColumn() = pNew;
75 : :
76 [ + + ]: 80 : if ( pNew->Next() != 0)
77 : : {
78 [ - + ]: 56 : AssertionOf( *pNew <= *pNew->Next() );
79 : : }
80 : :
81 : 406 : return;
82 : : }
83 : :
84 [ + + ]: 1660 : do
85 : : {
86 : 1660 : pSearch2 = pSearch1;
87 : 1660 : pSearch1 = pSearch1->Next();
88 : :
89 [ + + ][ + + ]: 1660 : if ( pSearch1 != 0 ? *pNew < *pSearch1 : true )
90 : : {
91 : 326 : pNew->SetNext( pSearch1 );
92 : 326 : pSearch2->SetNext(pNew);
93 : :
94 : :
95 [ - + ]: 326 : AssertionOf( *pSearch2 <= *pNew );
96 [ + + ]: 326 : if ( pNew->Next() != 0)
97 : : {
98 [ - + ]: 262 : AssertionOf( *pNew <= *pNew->Next() );
99 : : }
100 : :
101 : : }
102 : 1660 : } while (pSearch2->Next() != pNew);
103 : : }
104 : :
105 : :
106 : 2 : Simstr sKey1;
107 : 2 : Simstr sValue1;
108 : 2 : Simstr sKey2;
109 : 2 : Simstr sValue2;
110 : : int nCol1 = 0;
111 : : int nCol2 = 0;
112 : :
113 : :
114 : : HeapItem *
115 : 408 : Heap::ReleaseTop()
116 : : {
117 : 408 : unsigned nRetColumn = 0;
118 : 408 : HeapItem * ret = dpColumnsArray[0];
119 : 408 : HeapItem * pSearch = 0;
120 : :
121 [ + + ]: 4896 : for ( unsigned i = 1; i < nColumnsArraySize; ++i )
122 : : {
123 : 4488 : pSearch = dpColumnsArray[i];
124 [ + + ]: 4488 : if (pSearch != 0)
125 : : {
126 [ + + ][ + + ]: 4298 : if ( ret == 0 ? true : *pSearch < *ret)
127 : : {
128 : 688 : ret = pSearch;
129 : 688 : nRetColumn = i;
130 : : }
131 : : }
132 : : } // for
133 : :
134 [ + + ]: 408 : if (ret != 0)
135 : : {
136 : 406 : dpColumnsArray[nRetColumn] = ret->Next();
137 : : }
138 : 408 : return ret;
139 : : }
140 : :
141 : : void
142 : 406 : Heap::IncColumn()
143 : : {
144 [ + + ]: 406 : if (++nActiveColumn >= nColumnsArraySize)
145 : 34 : nActiveColumn = 0;
146 : 406 : }
147 : :
148 : :
149 : :
150 : 406 : HeapItem::HeapItem( const char * i_sKey,
151 : : const char * i_sValue )
152 : : : sValue(i_sValue),
153 : : sKey(i_sKey),
154 [ + - ]: 406 : pNext(0)
155 : : {
156 : 406 : }
157 : :
158 [ + - ]: 132 : HeapItem::~HeapItem()
159 : : {
160 : 132 : }
161 : :
162 : : bool
163 : 6872 : HeapItem::operator<( const HeapItem & i_rOther ) const
164 : : {
165 : 6872 : int ret = stricmp(sKey.str(), i_rOther.sKey.str());
166 [ + + ]: 6872 : if (ret == 0)
167 : 1164 : ret = strcmp(sKey.str(), i_rOther.sKey.str());
168 [ + + ]: 6872 : if (ret == 0)
169 : 1164 : ret = stricmp(sValue.str(), i_rOther.sValue.str());
170 [ + + ]: 6872 : if (ret == 0)
171 : 1164 : ret = strcmp(sValue.str(), i_rOther.sValue.str());
172 : 6872 : return ret < 0;
173 : : }
174 : :
175 : : const Simstr &
176 : 1336 : HeapItem::Key() const
177 : : {
178 : 1336 : return sKey;
179 : : }
180 : :
181 : : HeapItem *
182 : 4450 : HeapItem::Next() const
183 : : {
184 : 4450 : return pNext;
185 : : }
186 : :
187 : : void
188 : 732 : HeapItem::SetNext( HeapItem * i_pNext )
189 : : {
190 : 732 : pNext = i_pNext;
191 [ + - ][ + - ]: 738 : }
192 : :
193 : :
194 : : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
