xml2cmp/source/support/heap.cxx

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