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 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 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 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 * 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 146 Heap::IncColumn() 147 { 148 if (++nActiveColumn >= nColumnsArraySize) 149 nActiveColumn = 0; 150 } 151 152 153 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 162 HeapItem::~HeapItem() 163 { 164 } 165 166 bool 167 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 & 180 HeapItem::Value() const 181 { 182 return sValue; 183 } 184 185 const Simstr & 186 HeapItem::Key() const 187 { 188 return sKey; 189 } 190 191 HeapItem * 192 HeapItem::Next() const 193 { 194 return pNext; 195 } 196 197 void 198 HeapItem::SetNext( HeapItem * i_pNext ) 199 { 200 pNext = i_pNext; 201 } 202 203 204