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