| /************************************************************** |
| * |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, |
| * software distributed under the License is distributed on an |
| * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| * KIND, either express or implied. See the License for the |
| * specific language governing permissions and limitations |
| * under the License. |
| * |
| *************************************************************/ |
| |
| |
| |
| #include <string.h> |
| #include "heap.hxx" |
| |
| |
| #include <iostream> |
| #include <stdlib.h> |
| #define AssertionOf(x) {if (!(x)) {std::cerr << "Assertion failed: " << #x << __FILE__ << __LINE__ << std::endl; exit(3); }} |
| |
| #ifdef UNX |
| #define stricmp strcasecmp |
| #endif |
| |
| |
| |
| Heap::Heap(unsigned i_nWidth) |
| : dpColumnsArray(new Column[i_nWidth]), |
| nColumnsArraySize(i_nWidth), |
| nActiveColumn(nColumnsArraySize-1) |
| { |
| for ( unsigned i = 0; i < nColumnsArraySize; i++) |
| { |
| dpColumnsArray[i] = 0; |
| } // end for |
| } |
| |
| Heap::~Heap() |
| { |
| for ( unsigned i = 0; i < nColumnsArraySize; i++) |
| { |
| HeapItem * & rColumn = dpColumnsArray[i]; |
| for ( HeapItem * pValue = rColumn; pValue != 0; pValue = rColumn ) |
| { |
| rColumn = rColumn->Next(); |
| delete pValue; |
| } |
| } // end for |
| |
| delete [] dpColumnsArray; |
| } |
| |
| void |
| Heap::InsertValue( const char * i_sKey, |
| const char * i_sValue ) |
| { |
| HeapItem * pSearch1 = 0; |
| HeapItem * pSearch2 = 0; |
| HeapItem * pNew = new HeapItem(i_sKey, i_sValue); |
| |
| IncColumn(); |
| pSearch1 = ActiveColumn(); |
| |
| if ( pSearch1 != 0 ? *pNew < *pSearch1 : true ) |
| { |
| pNew->SetNext( pSearch1 ); |
| ActiveColumn() = pNew; |
| |
| if ( pNew->Next() != 0) |
| { |
| AssertionOf( *pNew <= *pNew->Next() ); |
| } |
| |
| return; |
| } |
| |
| do |
| { |
| pSearch2 = pSearch1; |
| pSearch1 = pSearch1->Next(); |
| |
| if ( pSearch1 != 0 ? *pNew < *pSearch1 : true ) |
| { |
| pNew->SetNext( pSearch1 ); |
| pSearch2->SetNext(pNew); |
| |
| |
| AssertionOf( *pSearch2 <= *pNew ); |
| if ( pNew->Next() != 0) |
| { |
| AssertionOf( *pNew <= *pNew->Next() ); |
| } |
| |
| } |
| } while (pSearch2->Next() != pNew); |
| } |
| |
| |
| Simstr sKey1; |
| Simstr sValue1; |
| Simstr sKey2; |
| Simstr sValue2; |
| int nCol1 = 0; |
| int nCol2 = 0; |
| |
| |
| HeapItem * |
| Heap::ReleaseTop() |
| { |
| unsigned nRetColumn = 0; |
| HeapItem * ret = dpColumnsArray[0]; |
| HeapItem * pSearch = 0; |
| |
| for ( unsigned i = 1; i < nColumnsArraySize; ++i ) |
| { |
| pSearch = dpColumnsArray[i]; |
| if (pSearch != 0) |
| { |
| if ( ret == 0 ? true : *pSearch < *ret) |
| { |
| ret = pSearch; |
| nRetColumn = i; |
| } |
| } |
| } // for |
| |
| if (ret != 0) |
| { |
| dpColumnsArray[nRetColumn] = ret->Next(); |
| } |
| return ret; |
| } |
| |
| void |
| Heap::IncColumn() |
| { |
| if (++nActiveColumn >= nColumnsArraySize) |
| nActiveColumn = 0; |
| } |
| |
| |
| |
| HeapItem::HeapItem( const char * i_sKey, |
| const char * i_sValue ) |
| : sValue(i_sValue), |
| sKey(i_sKey), |
| pNext(0) |
| { |
| } |
| |
| HeapItem::~HeapItem() |
| { |
| } |
| |
| bool |
| HeapItem::operator<( const HeapItem & i_rOther ) const |
| { |
| int ret = stricmp(sKey.str(), i_rOther.sKey.str()); |
| if (ret == 0) |
| ret = strcmp(sKey.str(), i_rOther.sKey.str()); |
| if (ret == 0) |
| ret = stricmp(sValue.str(), i_rOther.sValue.str()); |
| if (ret == 0) |
| ret = strcmp(sValue.str(), i_rOther.sValue.str()); |
| return ret < 0; |
| } |
| |
| const Simstr & |
| HeapItem::Value() const |
| { |
| return sValue; |
| } |
| |
| const Simstr & |
| HeapItem::Key() const |
| { |
| return sKey; |
| } |
| |
| HeapItem * |
| HeapItem::Next() const |
| { |
| return pNext; |
| } |
| |
| void |
| HeapItem::SetNext( HeapItem * i_pNext ) |
| { |
| pNext = i_pNext; |
| } |
| |
| |