xml2cmp/source/support/heap.cxx

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