1*cdf0e10cSrcweir /************************************************************************* 2*cdf0e10cSrcweir * 3*cdf0e10cSrcweir * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4*cdf0e10cSrcweir * 5*cdf0e10cSrcweir * Copyright 2000, 2010 Oracle and/or its affiliates. 6*cdf0e10cSrcweir * 7*cdf0e10cSrcweir * OpenOffice.org - a multi-platform office productivity suite 8*cdf0e10cSrcweir * 9*cdf0e10cSrcweir * This file is part of OpenOffice.org. 10*cdf0e10cSrcweir * 11*cdf0e10cSrcweir * OpenOffice.org is free software: you can redistribute it and/or modify 12*cdf0e10cSrcweir * it under the terms of the GNU Lesser General Public License version 3 13*cdf0e10cSrcweir * only, as published by the Free Software Foundation. 14*cdf0e10cSrcweir * 15*cdf0e10cSrcweir * OpenOffice.org is distributed in the hope that it will be useful, 16*cdf0e10cSrcweir * but WITHOUT ANY WARRANTY; without even the implied warranty of 17*cdf0e10cSrcweir * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18*cdf0e10cSrcweir * GNU Lesser General Public License version 3 for more details 19*cdf0e10cSrcweir * (a copy is included in the LICENSE file that accompanied this code). 20*cdf0e10cSrcweir * 21*cdf0e10cSrcweir * You should have received a copy of the GNU Lesser General Public License 22*cdf0e10cSrcweir * version 3 along with OpenOffice.org. If not, see 23*cdf0e10cSrcweir * <http://www.openoffice.org/license.html> 24*cdf0e10cSrcweir * for a copy of the LGPLv3 License. 25*cdf0e10cSrcweir * 26*cdf0e10cSrcweir ************************************************************************/ 27*cdf0e10cSrcweir 28*cdf0e10cSrcweir // MARKER(update_precomp.py): autogen include statement, do not remove 29*cdf0e10cSrcweir #include "precompiled_svl.hxx" 30*cdf0e10cSrcweir 31*cdf0e10cSrcweir #define _SVARRAY_CXX 32*cdf0e10cSrcweir 33*cdf0e10cSrcweir #define _SVSTDARR_BOOLS 34*cdf0e10cSrcweir #define _SVSTDARR_BYTES 35*cdf0e10cSrcweir #define _SVSTDARR_ULONGS 36*cdf0e10cSrcweir #define _SVSTDARR_ULONGSSORT 37*cdf0e10cSrcweir #define _SVSTDARR_USHORTS 38*cdf0e10cSrcweir #define _SVSTDARR_LONGS 39*cdf0e10cSrcweir #define _SVSTDARR_LONGSSORT 40*cdf0e10cSrcweir #define _SVSTDARR_SHORTS 41*cdf0e10cSrcweir #define _SVSTDARR_STRINGS 42*cdf0e10cSrcweir #define _SVSTDARR_STRINGSDTOR 43*cdf0e10cSrcweir #define _SVSTDARR_STRINGSSORT 44*cdf0e10cSrcweir #define _SVSTDARR_STRINGSSORTDTOR 45*cdf0e10cSrcweir #define _SVSTDARR_STRINGSISORT 46*cdf0e10cSrcweir #define _SVSTDARR_STRINGSISORTDTOR 47*cdf0e10cSrcweir #define _SVSTDARR_USHORTSSORT 48*cdf0e10cSrcweir 49*cdf0e10cSrcweir #define _SVSTDARR_BYTESTRINGS 50*cdf0e10cSrcweir #define _SVSTDARR_BYTESTRINGSDTOR 51*cdf0e10cSrcweir #define _SVSTDARR_BYTESTRINGSSORT 52*cdf0e10cSrcweir #define _SVSTDARR_BYTESTRINGSSORTDTOR 53*cdf0e10cSrcweir #define _SVSTDARR_BYTESTRINGSISORT 54*cdf0e10cSrcweir #define _SVSTDARR_BYTESTRINGSISORTDTOR 55*cdf0e10cSrcweir 56*cdf0e10cSrcweir #define _SVSTDARR_XUB_STRLEN 57*cdf0e10cSrcweir #define _SVSTDARR_XUB_STRLENSORT 58*cdf0e10cSrcweir 59*cdf0e10cSrcweir #include <svl/svstdarr.hxx> 60*cdf0e10cSrcweir #include <tools/string.hxx> 61*cdf0e10cSrcweir #include <tools/debug.hxx> 62*cdf0e10cSrcweir 63*cdf0e10cSrcweir SV_IMPL_VARARR(SvPtrarr,VoidPtr) 64*cdf0e10cSrcweir 65*cdf0e10cSrcweir sal_uInt16 SvPtrarr::GetPos( const VoidPtr& aElement ) const 66*cdf0e10cSrcweir { sal_uInt16 n; 67*cdf0e10cSrcweir for( n=0; n < nA && *(GetData()+n) != aElement; ) n++; 68*cdf0e10cSrcweir return ( n >= nA ? USHRT_MAX : n ); 69*cdf0e10cSrcweir } 70*cdf0e10cSrcweir 71*cdf0e10cSrcweir SV_IMPL_VARARR( SvULongs, sal_uLong ) 72*cdf0e10cSrcweir SV_IMPL_VARARR( SvUShorts, sal_uInt16 ) 73*cdf0e10cSrcweir SV_IMPL_VARARR( SvLongs, long) 74*cdf0e10cSrcweir 75*cdf0e10cSrcweir SV_IMPL_VARARR_SORT( SvULongsSort, sal_uLong ) 76*cdf0e10cSrcweir SV_IMPL_VARARR_SORT( SvLongsSort, long ) 77*cdf0e10cSrcweir 78*cdf0e10cSrcweir SV_IMPL_PTRARR( SvStrings, StringPtr ) 79*cdf0e10cSrcweir SV_IMPL_PTRARR( SvStringsDtor, StringPtr ) 80*cdf0e10cSrcweir SV_IMPL_OP_PTRARR_SORT( SvStringsSort, StringPtr ) 81*cdf0e10cSrcweir SV_IMPL_OP_PTRARR_SORT( SvStringsSortDtor, StringPtr ) 82*cdf0e10cSrcweir 83*cdf0e10cSrcweir SV_IMPL_PTRARR( SvByteStrings, ByteStringPtr ) 84*cdf0e10cSrcweir SV_IMPL_PTRARR( SvByteStringsDtor, ByteStringPtr ) 85*cdf0e10cSrcweir SV_IMPL_OP_PTRARR_SORT( SvByteStringsSort, ByteStringPtr ) 86*cdf0e10cSrcweir SV_IMPL_OP_PTRARR_SORT( SvByteStringsSortDtor, ByteStringPtr ) 87*cdf0e10cSrcweir 88*cdf0e10cSrcweir 89*cdf0e10cSrcweir 90*cdf0e10cSrcweir // ---------------- strings ------------------------------------- 91*cdf0e10cSrcweir 92*cdf0e10cSrcweir // Array mit anderer Seek-Methode! 93*cdf0e10cSrcweir _SV_IMPL_SORTAR_ALG( SvStringsISort, StringPtr ) 94*cdf0e10cSrcweir void SvStringsISort::DeleteAndDestroy( sal_uInt16 nP, sal_uInt16 nL ) 95*cdf0e10cSrcweir { 96*cdf0e10cSrcweir if( nL ) 97*cdf0e10cSrcweir { 98*cdf0e10cSrcweir DBG_ASSERT( nP < nA && nP + nL <= nA, "ERR_VAR_DEL" ); 99*cdf0e10cSrcweir for( sal_uInt16 n=nP; n < nP + nL; n++ ) 100*cdf0e10cSrcweir delete *((StringPtr*)pData+n); 101*cdf0e10cSrcweir SvPtrarr::Remove( nP, nL ); 102*cdf0e10cSrcweir } 103*cdf0e10cSrcweir } 104*cdf0e10cSrcweir sal_Bool SvStringsISort::Seek_Entry( const StringPtr aE, sal_uInt16* pP ) const 105*cdf0e10cSrcweir { 106*cdf0e10cSrcweir register sal_uInt16 nO = SvStringsISort_SAR::Count(), 107*cdf0e10cSrcweir nM, 108*cdf0e10cSrcweir nU = 0; 109*cdf0e10cSrcweir if( nO > 0 ) 110*cdf0e10cSrcweir { 111*cdf0e10cSrcweir nO--; 112*cdf0e10cSrcweir while( nU <= nO ) 113*cdf0e10cSrcweir { 114*cdf0e10cSrcweir nM = nU + ( nO - nU ) / 2; 115*cdf0e10cSrcweir StringCompare eCmp = (*((StringPtr*)pData + nM))-> 116*cdf0e10cSrcweir CompareIgnoreCaseToAscii( *(aE) ); 117*cdf0e10cSrcweir if( COMPARE_EQUAL == eCmp ) 118*cdf0e10cSrcweir { 119*cdf0e10cSrcweir if( pP ) *pP = nM; 120*cdf0e10cSrcweir return sal_True; 121*cdf0e10cSrcweir } 122*cdf0e10cSrcweir else if( COMPARE_LESS == eCmp ) 123*cdf0e10cSrcweir nU = nM + 1; 124*cdf0e10cSrcweir else if( nM == 0 ) 125*cdf0e10cSrcweir { 126*cdf0e10cSrcweir if( pP ) *pP = nU; 127*cdf0e10cSrcweir return sal_False; 128*cdf0e10cSrcweir } 129*cdf0e10cSrcweir else 130*cdf0e10cSrcweir nO = nM - 1; 131*cdf0e10cSrcweir } 132*cdf0e10cSrcweir } 133*cdf0e10cSrcweir if( pP ) *pP = nU; 134*cdf0e10cSrcweir return sal_False; 135*cdf0e10cSrcweir } 136*cdf0e10cSrcweir 137*cdf0e10cSrcweir // ---------------- strings ------------------------------------- 138*cdf0e10cSrcweir 139*cdf0e10cSrcweir // Array mit anderer Seek-Methode! 140*cdf0e10cSrcweir _SV_IMPL_SORTAR_ALG( SvStringsISortDtor, StringPtr ) 141*cdf0e10cSrcweir void SvStringsISortDtor::DeleteAndDestroy( sal_uInt16 nP, sal_uInt16 nL ) 142*cdf0e10cSrcweir { 143*cdf0e10cSrcweir if( nL ) 144*cdf0e10cSrcweir { 145*cdf0e10cSrcweir DBG_ASSERT( nP < nA && nP + nL <= nA, "ERR_VAR_DEL" ); 146*cdf0e10cSrcweir for( sal_uInt16 n=nP; n < nP + nL; n++ ) 147*cdf0e10cSrcweir delete *((StringPtr*)pData+n); 148*cdf0e10cSrcweir SvPtrarr::Remove( nP, nL ); 149*cdf0e10cSrcweir } 150*cdf0e10cSrcweir } 151*cdf0e10cSrcweir sal_Bool SvStringsISortDtor::Seek_Entry( const StringPtr aE, sal_uInt16* pP ) const 152*cdf0e10cSrcweir { 153*cdf0e10cSrcweir register sal_uInt16 nO = SvStringsISortDtor_SAR::Count(), 154*cdf0e10cSrcweir nM, 155*cdf0e10cSrcweir nU = 0; 156*cdf0e10cSrcweir if( nO > 0 ) 157*cdf0e10cSrcweir { 158*cdf0e10cSrcweir nO--; 159*cdf0e10cSrcweir while( nU <= nO ) 160*cdf0e10cSrcweir { 161*cdf0e10cSrcweir nM = nU + ( nO - nU ) / 2; 162*cdf0e10cSrcweir StringCompare eCmp = (*((StringPtr*)pData + nM))-> 163*cdf0e10cSrcweir CompareIgnoreCaseToAscii( *(aE) ); 164*cdf0e10cSrcweir if( COMPARE_EQUAL == eCmp ) 165*cdf0e10cSrcweir { 166*cdf0e10cSrcweir if( pP ) *pP = nM; 167*cdf0e10cSrcweir return sal_True; 168*cdf0e10cSrcweir } 169*cdf0e10cSrcweir else if( COMPARE_LESS == eCmp ) 170*cdf0e10cSrcweir nU = nM + 1; 171*cdf0e10cSrcweir else if( nM == 0 ) 172*cdf0e10cSrcweir { 173*cdf0e10cSrcweir if( pP ) *pP = nU; 174*cdf0e10cSrcweir return sal_False; 175*cdf0e10cSrcweir } 176*cdf0e10cSrcweir else 177*cdf0e10cSrcweir nO = nM - 1; 178*cdf0e10cSrcweir } 179*cdf0e10cSrcweir } 180*cdf0e10cSrcweir if( pP ) *pP = nU; 181*cdf0e10cSrcweir return sal_False; 182*cdf0e10cSrcweir } 183*cdf0e10cSrcweir 184*cdf0e10cSrcweir // ---------------- Ushorts ------------------------------------- 185*cdf0e10cSrcweir 186*cdf0e10cSrcweir /* SortArray fuer UShorts */ 187*cdf0e10cSrcweir sal_Bool SvUShortsSort::Seek_Entry( const sal_uInt16 aE, sal_uInt16* pP ) const 188*cdf0e10cSrcweir { 189*cdf0e10cSrcweir register sal_uInt16 nO = SvUShorts::Count(), 190*cdf0e10cSrcweir nM, 191*cdf0e10cSrcweir nU = 0; 192*cdf0e10cSrcweir if( nO > 0 ) 193*cdf0e10cSrcweir { 194*cdf0e10cSrcweir nO--; 195*cdf0e10cSrcweir while( nU <= nO ) 196*cdf0e10cSrcweir { 197*cdf0e10cSrcweir nM = nU + ( nO - nU ) / 2; 198*cdf0e10cSrcweir if( *(pData + nM) == aE ) 199*cdf0e10cSrcweir { 200*cdf0e10cSrcweir if( pP ) *pP = nM; 201*cdf0e10cSrcweir return sal_True; 202*cdf0e10cSrcweir } 203*cdf0e10cSrcweir else if( *(pData + nM) < aE ) 204*cdf0e10cSrcweir nU = nM + 1; 205*cdf0e10cSrcweir else if( nM == 0 ) 206*cdf0e10cSrcweir { 207*cdf0e10cSrcweir if( pP ) *pP = nU; 208*cdf0e10cSrcweir return sal_False; 209*cdf0e10cSrcweir } 210*cdf0e10cSrcweir else 211*cdf0e10cSrcweir nO = nM - 1; 212*cdf0e10cSrcweir } 213*cdf0e10cSrcweir } 214*cdf0e10cSrcweir if( pP ) *pP = nU; 215*cdf0e10cSrcweir return sal_False; 216*cdf0e10cSrcweir } 217*cdf0e10cSrcweir 218*cdf0e10cSrcweir void SvUShortsSort::Insert( const SvUShortsSort * pI, sal_uInt16 nS, sal_uInt16 nE ) 219*cdf0e10cSrcweir { 220*cdf0e10cSrcweir if( USHRT_MAX == nE ) 221*cdf0e10cSrcweir nE = pI->Count(); 222*cdf0e10cSrcweir sal_uInt16 nP; 223*cdf0e10cSrcweir const sal_uInt16 * pIArr = pI->GetData(); 224*cdf0e10cSrcweir for( ; nS < nE; ++nS ) 225*cdf0e10cSrcweir { 226*cdf0e10cSrcweir if( ! Seek_Entry( *(pIArr+nS), &nP) ) 227*cdf0e10cSrcweir SvUShorts::Insert( *(pIArr+nS), nP ); 228*cdf0e10cSrcweir if( ++nP >= Count() ) 229*cdf0e10cSrcweir { 230*cdf0e10cSrcweir SvUShorts::Insert( pI, nP, nS+1, nE ); 231*cdf0e10cSrcweir nS = nE; 232*cdf0e10cSrcweir } 233*cdf0e10cSrcweir } 234*cdf0e10cSrcweir } 235*cdf0e10cSrcweir 236*cdf0e10cSrcweir sal_Bool SvUShortsSort::Insert( const sal_uInt16 aE ) 237*cdf0e10cSrcweir { 238*cdf0e10cSrcweir sal_uInt16 nP; 239*cdf0e10cSrcweir sal_Bool bExist = Seek_Entry( aE, &nP ); 240*cdf0e10cSrcweir if( !bExist ) 241*cdf0e10cSrcweir SvUShorts::Insert( aE, nP ); 242*cdf0e10cSrcweir return !bExist; 243*cdf0e10cSrcweir } 244*cdf0e10cSrcweir 245*cdf0e10cSrcweir sal_Bool SvUShortsSort::Insert( const sal_uInt16 aE, sal_uInt16& rP ) 246*cdf0e10cSrcweir { 247*cdf0e10cSrcweir sal_Bool bExist = Seek_Entry( aE, &rP ); 248*cdf0e10cSrcweir if( !bExist ) 249*cdf0e10cSrcweir SvUShorts::Insert( aE, rP ); 250*cdf0e10cSrcweir return !bExist; 251*cdf0e10cSrcweir } 252*cdf0e10cSrcweir 253*cdf0e10cSrcweir void SvUShortsSort::Insert( const sal_uInt16* pE, sal_uInt16 nL) 254*cdf0e10cSrcweir { 255*cdf0e10cSrcweir sal_uInt16 nP; 256*cdf0e10cSrcweir for( sal_uInt16 n = 0; n < nL; ++n ) 257*cdf0e10cSrcweir if( ! Seek_Entry( *(pE+n), &nP )) 258*cdf0e10cSrcweir SvUShorts::Insert( *(pE+n), nP ); 259*cdf0e10cSrcweir } 260*cdf0e10cSrcweir 261*cdf0e10cSrcweir // remove ab Pos 262*cdf0e10cSrcweir void SvUShortsSort::RemoveAt( const sal_uInt16 nP, sal_uInt16 nL ) 263*cdf0e10cSrcweir { 264*cdf0e10cSrcweir if( nL ) 265*cdf0e10cSrcweir SvUShorts::Remove( nP, nL); 266*cdf0e10cSrcweir } 267*cdf0e10cSrcweir 268*cdf0e10cSrcweir // remove ab dem Eintrag 269*cdf0e10cSrcweir void SvUShortsSort::Remove( const sal_uInt16 aE, sal_uInt16 nL ) 270*cdf0e10cSrcweir { 271*cdf0e10cSrcweir sal_uInt16 nP; 272*cdf0e10cSrcweir if( nL && Seek_Entry( aE, &nP ) ) 273*cdf0e10cSrcweir SvUShorts::Remove( nP, nL); 274*cdf0e10cSrcweir } 275*cdf0e10cSrcweir 276*cdf0e10cSrcweir // ---------------- bytestrings ------------------------------------- 277*cdf0e10cSrcweir 278*cdf0e10cSrcweir // Array mit anderer Seek-Methode! 279*cdf0e10cSrcweir _SV_IMPL_SORTAR_ALG( SvByteStringsISort, ByteStringPtr ) 280*cdf0e10cSrcweir void SvByteStringsISort::DeleteAndDestroy( sal_uInt16 nP, sal_uInt16 nL ) 281*cdf0e10cSrcweir { 282*cdf0e10cSrcweir if( nL ) 283*cdf0e10cSrcweir { 284*cdf0e10cSrcweir DBG_ASSERT( nP < nA && nP + nL <= nA, "ERR_VAR_DEL" ); 285*cdf0e10cSrcweir for( sal_uInt16 n=nP; n < nP + nL; n++ ) 286*cdf0e10cSrcweir delete *((ByteStringPtr*)pData+n); 287*cdf0e10cSrcweir SvPtrarr::Remove( nP, nL ); 288*cdf0e10cSrcweir } 289*cdf0e10cSrcweir } 290*cdf0e10cSrcweir sal_Bool SvByteStringsISort::Seek_Entry( const ByteStringPtr aE, sal_uInt16* pP ) const 291*cdf0e10cSrcweir { 292*cdf0e10cSrcweir register sal_uInt16 nO = SvByteStringsISort_SAR::Count(), 293*cdf0e10cSrcweir nM, 294*cdf0e10cSrcweir nU = 0; 295*cdf0e10cSrcweir if( nO > 0 ) 296*cdf0e10cSrcweir { 297*cdf0e10cSrcweir nO--; 298*cdf0e10cSrcweir while( nU <= nO ) 299*cdf0e10cSrcweir { 300*cdf0e10cSrcweir nM = nU + ( nO - nU ) / 2; 301*cdf0e10cSrcweir StringCompare eCmp = (*((ByteStringPtr*)pData + nM))-> 302*cdf0e10cSrcweir CompareIgnoreCaseToAscii( *(aE) ); 303*cdf0e10cSrcweir if( COMPARE_EQUAL == eCmp ) 304*cdf0e10cSrcweir { 305*cdf0e10cSrcweir if( pP ) *pP = nM; 306*cdf0e10cSrcweir return sal_True; 307*cdf0e10cSrcweir } 308*cdf0e10cSrcweir else if( COMPARE_LESS == eCmp ) 309*cdf0e10cSrcweir nU = nM + 1; 310*cdf0e10cSrcweir else if( nM == 0 ) 311*cdf0e10cSrcweir { 312*cdf0e10cSrcweir if( pP ) *pP = nU; 313*cdf0e10cSrcweir return sal_False; 314*cdf0e10cSrcweir } 315*cdf0e10cSrcweir else 316*cdf0e10cSrcweir nO = nM - 1; 317*cdf0e10cSrcweir } 318*cdf0e10cSrcweir } 319*cdf0e10cSrcweir if( pP ) *pP = nU; 320*cdf0e10cSrcweir return sal_False; 321*cdf0e10cSrcweir } 322*cdf0e10cSrcweir 323*cdf0e10cSrcweir 324*cdf0e10cSrcweir // Array mit anderer Seek-Methode! 325*cdf0e10cSrcweir _SV_IMPL_SORTAR_ALG( SvByteStringsISortDtor, ByteStringPtr ) 326*cdf0e10cSrcweir void SvByteStringsISortDtor::DeleteAndDestroy( sal_uInt16 nP, sal_uInt16 nL ) 327*cdf0e10cSrcweir { 328*cdf0e10cSrcweir if( nL ) 329*cdf0e10cSrcweir { 330*cdf0e10cSrcweir DBG_ASSERT( nP < nA && nP + nL <= nA, "ERR_VAR_DEL" ); 331*cdf0e10cSrcweir for( sal_uInt16 n=nP; n < nP + nL; n++ ) 332*cdf0e10cSrcweir delete *((ByteStringPtr*)pData+n); 333*cdf0e10cSrcweir SvPtrarr::Remove( nP, nL ); 334*cdf0e10cSrcweir } 335*cdf0e10cSrcweir } 336*cdf0e10cSrcweir sal_Bool SvByteStringsISortDtor::Seek_Entry( const ByteStringPtr aE, sal_uInt16* pP ) const 337*cdf0e10cSrcweir { 338*cdf0e10cSrcweir register sal_uInt16 nO = SvByteStringsISortDtor_SAR::Count(), 339*cdf0e10cSrcweir nM, 340*cdf0e10cSrcweir nU = 0; 341*cdf0e10cSrcweir if( nO > 0 ) 342*cdf0e10cSrcweir { 343*cdf0e10cSrcweir nO--; 344*cdf0e10cSrcweir while( nU <= nO ) 345*cdf0e10cSrcweir { 346*cdf0e10cSrcweir nM = nU + ( nO - nU ) / 2; 347*cdf0e10cSrcweir StringCompare eCmp = (*((ByteStringPtr*)pData + nM))-> 348*cdf0e10cSrcweir CompareIgnoreCaseToAscii( *(aE) ); 349*cdf0e10cSrcweir if( COMPARE_EQUAL == eCmp ) 350*cdf0e10cSrcweir { 351*cdf0e10cSrcweir if( pP ) *pP = nM; 352*cdf0e10cSrcweir return sal_True; 353*cdf0e10cSrcweir } 354*cdf0e10cSrcweir else if( COMPARE_LESS == eCmp ) 355*cdf0e10cSrcweir nU = nM + 1; 356*cdf0e10cSrcweir else if( nM == 0 ) 357*cdf0e10cSrcweir { 358*cdf0e10cSrcweir if( pP ) *pP = nU; 359*cdf0e10cSrcweir return sal_False; 360*cdf0e10cSrcweir } 361*cdf0e10cSrcweir else 362*cdf0e10cSrcweir nO = nM - 1; 363*cdf0e10cSrcweir } 364*cdf0e10cSrcweir } 365*cdf0e10cSrcweir if( pP ) *pP = nU; 366*cdf0e10cSrcweir return sal_False; 367*cdf0e10cSrcweir } 368*cdf0e10cSrcweir 369