src/support/lyxstring.C

   1 /* This file is part of
   2  * ======================================================
   3  *
   4  *           LyX, The Document Processor
   5  *
   6  *          Copyright (C) 1995 Matthias Ettrich
   7  *          Copyright (C) 1995-1999 The LyX Team.
   8  *
   9  * ======================================================*/
  10
  11 #ifdef HAVE_CONFIG_H
  12 #include <config.h>
  13 #endif
  14
  15 // If we use STL string, there is no need to compile this class.
  16 #ifdef USE_INCLUDED_STRING
  17
  18 #ifdef __GNUG__
  19 #pragma implementation "lyxstring.h"
  20 #endif
  21
  22 #include "lyxstring.h"
  23 #include <cstdlib>
  24 #include <cctype>
  25 #include <algorithm>
  26
  27 #include "LAssert.h"
  28
  29 using std::min;
  30
  31 // Reference count has been checked, empty_rep removed and
  32 // introduced again in a similar guise. Where is empty_rep _really_
  33 // needed?
  34
  35 // Insertion and replace is implemented, as far as I can see everything
  36 // works, but could perhaps be done smarter.
  37
  38 // All the different find functions need a good look over.
  39 // I have so far not tested them extensively and would be
  40 // happy if others took the time to have a peek.
  41
  42 #ifdef WITH_WARNINGS
  43 #warning temporarily here for debugging purposes only
  44 #endif
  45 lyxstring::size_type lyxstring::size() const
  46 {
  47         return rep->sz;
  48 }
  49
  50
  51 //--------------------------------------------------------------------------
  52 // lyxstringInvariant
  53 #ifdef DEVEL_VERSION
  54
  55 /** Testing of the lyxstring invariant
  56  * By creating an object that tests the lyxstring invariant during its
  57  * construction *and* its deconstruction we greatly simplify our code.
  58  * Calling TestlyxstringInvariant() upon entry to an lyxstring method
  59  * will test the invariant upon entry to the code.  If the Asserts fail
  60  * then we know from the stack trace that the corruption occurred *before*
  61  * entry to this method.  We can also be sure it didn't happen in any of
  62  * the tested lyxstring methods.  It is therefore likely to be due to some
  63  * other external force.
  64  * Several lyxstring methods have multiple exit points which would otherwise
  65  * require us to insert a separate test before each return.  But since we
  66  * created an object its destructor will be called upon exit (any exit!).
  67  * We thus get testing at both start and end of a method with one line of
  68  * code at the head of a method.  More importantly,  we get good testing
  69  * everytime we run the code.
  70  * NOTE:  just because we test the invariant doesn't mean we can forget
  71  * about testing pre and post conditions specific to any given method.
  72  * This test simply proves that the lyxstring/Srep is in a valid state it
  73  * does *not* prove that the method did what it was supposed to.
  74  */
  75 class lyxstringInvariant
  76 {
  77 public:
  78         lyxstringInvariant(lyxstring const *);
  79         ~lyxstringInvariant();
  80 private:
  81         void helper() const;
  82         lyxstring const * object;
  83 };
  84
  85 // To test if this scheme works "as advertised" uncomment the printf's in
  86 // the constructor and destructor below and then uncomment the printf and the
  87 // call to TestlyxstringInvariant() in lyxstring::operator=(char const *).
  88 // The correct output when LyX has been recompiled and run is:
  89 //     lyxstringInvariant constructor
  90 //     lyxstring::operator=(char const *)
  91 //     lyxstringInvariant constructor
  92 //     lyxstringInvariant destructor completed
  93 //     lyxstringInvariant destructor completed
  94 // NOTE: The easiest way to catch this snippet of the output is to wait for
  95 //       the splash screen to disappear and then open and close Help->Credits
  96 //
  97 lyxstringInvariant::lyxstringInvariant(lyxstring const * ls) : object(ls)
  98 {
  99 //      printf("lyxstringInvariant constructor\n");
 100         helper();
 101 }
 102
 103 lyxstringInvariant::~lyxstringInvariant()
 104 {
 105         helper();
 106 //      printf("lyxstringInvariant destructor completed\n");
 107 }
 108
 109 void lyxstringInvariant::helper() const
 110 {
 111         // Some of these tests might look pointless but they are
 112         // all part of the invariant and if we want to make sure
 113         // we have a bullet proof implementation then we need to
 114         // test every last little thing we *know* should be true.
 115         // I may have missed a test or two, so feel free to fill
 116         // in the gaps.  ARRae.
 117         // NOTE:  Don't put TestlyxstringInvariant() in any of the
 118         // lyxstring methods used below otherwise you'll get an
 119         // infinite recursion and a crash.
 120         Assert(object);
 121         Assert(object->rep);
 122         Assert(object->rep->s);    // s is never 0
 123         Assert(object->rep->res);  // always some space allocated
 124         Assert(object->size() <= object->rep->res);
 125         Assert(object->rep->ref >= 1);  // its in use so it must be referenced
 126         Assert(object->rep->ref < (1 << 8*sizeof(lyxstring::Srep::ref)) - 1);
 127         // if it does ever == then we should be generating a new copy
 128         // and starting again.  (Is char always 8-bits?)
 129 }
 130 #define TestlyxstringInvariant(s) lyxstringInvariant lyxstring_invariant(s);
 131 #else
 132 #define TestlyxstringInvariant(s)
 133 #endif //DEVEL_VERSION
 134 //-------------------------------------------------------------------------
 135
 136 ///////////////////////////////////////
 137 // Constructors and Deconstructors.
 138 ///////////////////////////////////////
 139
 140
 141 lyxstring::Srep::Srep(lyxstring::size_type nsz, const value_type * p)
 142 {
 143 // can be called with p==0 by lyxstring::assign(const value_type *, size_type)
 144
 145         sz = nsz;
 146         ref = 1;
 147         res = sz + xtra;
 148         s = new value_type[res + 1]; // add space for terminator
 149         if (p && sz) {
 150                 // if sz = 0 nothing gets copied and we have an error
 151                 memcpy(s, p, sz);
 152         } else {
 153                 // possibly allows for large but empty string
 154                 sz = 0;  // this line should be redundant
 155                 s[0] = '\0';
 156         }
 157 }
 158
 159
 160 lyxstring::Srep::Srep(lyxstring::size_type nsz, value_type ch)
 161 {
 162         sz = nsz;
 163         ref = 1;
 164         res = sz + xtra;
 165         s = new value_type[res + 1]; // add space for terminator
 166         memset(s, ch, sz);
 167         if (!ch) {
 168                 // if ch == '\0' strlen(lyxstring.c_str()) == 0 so sz = 0
 169                 // allows for large but empty string
 170                 sz = 0;
 171         }
 172 }
 173
 174
 175 void lyxstring::Srep::assign(lyxstring::size_type nsz, const value_type * p)
 176 {
 177 // can be called with p==0 by lyxstring::assign(const value_type *, size_type)
 178
 179         if (res < nsz) {
 180                 delete[] s;
 181                 sz = nsz;
 182                 res = sz + xtra;
 183                 s = new value_type[res + 1]; // add space for terminator
 184         } else {
 185                 sz = nsz;
 186         }
 187         if (p && sz) {
 188                 // if sz = 0 nothing gets copied and we have an error
 189                 memcpy(s, p, sz);
 190         } else {
 191                 // stops segfaults
 192                 sz = 0;  // this line should be redundant
 193                 s[0] = '\0';
 194         }
 195 }
 196
 197
 198 void lyxstring::Srep::assign(lyxstring::size_type nsz, value_type ch)
 199 {
 200         sz = nsz;
 201         if (res < nsz) {
 202                 delete[] s;
 203                 res = sz + xtra;
 204                 s = new value_type[res + 1]; // add space for terminator
 205         }
 206         memset(s, ch, sz);
 207         if (!ch) {
 208                 // if ch == '\0' strlen(lyxstring.c_str()) == 0 so sz = 0
 209                 // allows for a large empty string
 210                 sz = 0;
 211         }
 212 }
 213
 214
 215 void lyxstring::Srep::append(lyxstring::size_type asz, const value_type * p)
 216 {
 217         register unsigned int const len = sz + asz;
 218         if (res < len) {
 219                 res = len + xtra;
 220                 value_type * tmp = new value_type[res + 1];
 221                 memcpy(tmp, s, sz);
 222                 memcpy(tmp + sz, p, asz);
 223                 sz += asz;
 224                 delete[] s;
 225                 s = tmp;
 226         } else {
 227                 memcpy(s + sz, p, asz);
 228                 sz += asz;
 229         }
 230 }
 231
 232
 233 void lyxstring::Srep::push_back(value_type c)
 234 {
 235         s[sz] = c; // it is always room to put a value_type at the end
 236         ++sz;
 237         if (res < sz) {
 238                 res = sz + xtra;
 239                 value_type * tmp = new value_type[res + 1];
 240                 memcpy(tmp, s, sz);
 241                 delete[] s;
 242                 s = tmp;
 243         }
 244 }
 245
 246
 247 void lyxstring::Srep::insert(lyxstring::size_type pos, const value_type * p,
 248                            lyxstring::size_type n)
 249 {
 250         Assert(pos <= sz);
 251         if (res < n + sz) {
 252                 res = sz + n + xtra;
 253                 value_type * tmp = new value_type[res + 1];
 254                 memcpy(tmp, s, pos);
 255                 memcpy(tmp + pos, p, n);
 256                 memcpy(tmp + pos + n, & s[pos], sz - pos);
 257                 sz += n;
 258                 delete[] s;
 259                 s = tmp;
 260         } else {
 261                 memmove(s + pos + n, & s[pos], sz - pos);
 262                 memcpy(s + pos, p, n);
 263                 sz += n;
 264         }
 265 }
 266
 267
 268 void lyxstring::Srep::resize(size_type n, value_type c)
 269 {
 270         Assert(n < npos);
 271         // This resets sz to res_arg
 272         res = min(n, npos - 2); // We keep no xtra when we resize
 273         value_type * tmp = new value_type[res + 1];
 274         memcpy(tmp, s, min(sz, res));
 275         if (res > sz)
 276                 memset(tmp + sz, c, res - sz);
 277         delete[] s;
 278         sz = res;
 279         s = tmp;
 280 }
 281
 282
 283 void lyxstring::Srep::reserve(lyxstring::size_type res_arg)
 284 {
 285         // This keeps the old sz, but
 286         // increases res with res_arg
 287         res += res_arg;
 288         value_type * tmp = new value_type[res + 1];
 289         memcpy(tmp, s, sz);
 290         delete[] s;
 291         s = tmp;
 292 }
 293
 294
 295 void lyxstring::Srep::replace(lyxstring::size_type i, lyxstring::size_type n,
 296                             value_type const * p, size_type n2)
 297 {
 298 // can be called with p=0 and n2=0
 299         Assert(i < sz && ((!p && !n2) || p));
 300         n = min(sz - i, n);
 301         sz -= n;
 302         if (res >= n2 + sz) {
 303                 memmove(s + i + n2, &s[i + n], sz - i);
 304                 memcpy(s + i, p, n2);
 305                 sz += n2;
 306         } else {
 307                 res = sz + n2 + xtra;
 308                 value_type * tmp = new value_type[res + 1];
 309                 memcpy(tmp, s, i);
 310                 memcpy(tmp + i, p, n2);
 311                 memcpy(tmp + i + n2, &s[i + n], sz - i);
 312                 delete[] s;
 313                 s = tmp;
 314                 sz += n2;
 315         }
 316 }
 317
 318
 319 lyxstring::size_type const lyxstring::npos = static_cast<lyxstring::size_type>(-1);
 320
 321 lyxstring::lyxstring()
 322 {
 323         static Srep empty_rep(0, "");
 324         ++empty_rep.ref;
 325         rep = &empty_rep;
 326 }
 327
 328
 329 lyxstring::lyxstring(lyxstring const & x, size_type pos, size_type n)
 330 {
 331         Assert(pos < x.rep->sz || pos == 0);
 332         if (pos == 0 && n >= x.length()) { // this is the default
 333                 x.rep->ref++;
 334                 rep = x.rep;
 335         } else {
 336                 rep = new Srep(min(n, x.rep->sz - pos), &(x.rep->s[pos]));
 337         }
 338 }
 339
 340
 341 lyxstring::lyxstring(value_type const * s, size_type n)
 342 {
 343         Assert(s); // we don't allow null pointers
 344         static Srep empty_rep(0, "");
 345         if (s && *s && n) { // s is not empty string and n > 0
 346                 rep = new Srep(min(strlen(s), n), s);
 347         } else {
 348                 ++empty_rep.ref;
 349                 rep = &empty_rep;
 350         }
 351 }
 352
 353
 354 lyxstring::lyxstring(value_type const * s)
 355 {
 356         // yes we allow them just don't initalize them
 357         // Assert(s); // we don't allow null pointers
 358         static Srep empty_rep(0, "");
 359         if (s && *s) { // s is not empty string
 360                 rep = new Srep(strlen(s), s);
 361         } else {
 362                 ++empty_rep.ref;
 363                 rep = &empty_rep;
 364         }
 365 }
 366
 367
 368 lyxstring::lyxstring(size_type n, value_type c)
 369 {
 370         rep = new Srep(n, c);
 371 }
 372
 373
 374 lyxstring::lyxstring(iterator first, iterator last)
 375 {
 376         rep = new Srep(last - first, first);
 377 }
 378
 379
 380 ///////////////////////
 381 // Iterators
 382 ///////////////////////
 383
 384 lyxstring::iterator lyxstring::begin()
 385 {
 386         return rep->s;
 387 }
 388
 389
 390 lyxstring::const_iterator lyxstring::begin() const
 391 {
 392         return rep->s;
 393 }
 394
 395
 396 lyxstring::iterator lyxstring::end()
 397 {
 398         return rep->s + rep->sz;
 399 }
 400
 401
 402 lyxstring::const_iterator lyxstring::end() const
 403 {
 404         return rep->s + rep->sz;
 405 }
 406
 407 #if 0
 408 reverse_iterator lyxstring::rbegin()
 409 {
 410         return reverse_iterator( end() );
 411 }
 412
 413
 414 const_reverse_iterator lyxstring::rbegin() const
 415 {
 416         return const_reverse_iterator( end() );
 417 }
 418
 419
 420 reverse_iterator lyxstring::rend()
 421 {
 422         return reverse_iterator( begin() );
 423 }
 424
 425
 426 const_reverse_iterator lyxstring::rend() const
 427 {
 428         return const_reverse_iterator( begin() );
 429 }
 430 #endif
 431
 432 ///////////////////////
 433 // Size and Capacity
 434 ///////////////////////
 435
 436 void lyxstring::resize(size_type n, value_type c)
 437 {
 438         TestlyxstringInvariant(this);
 439
 440         // This resets sz to res_arg
 441         rep = rep->get_own_copy();
 442         rep->resize(n, c);
 443 }
 444
 445
 446 lyxstring::size_type lyxstring::capacity() const
 447 {
 448         return rep->res;
 449 }
 450
 451
 452 void lyxstring::reserve(size_type res_arg)
 453 {
 454         TestlyxstringInvariant(this);
 455
 456         rep = rep->get_own_copy();
 457         rep->reserve(res_arg);
 458 }
 459
 460
 461 ////////////////
 462 // Assignment
 463 ////////////////
 464
 465 lyxstring & lyxstring::operator=(lyxstring const & x)
 466 {
 467         TestlyxstringInvariant(this);
 468
 469         return assign(x);
 470 }
 471
 472
 473 lyxstring & lyxstring::operator=(value_type const * s)
 474 {
 475         Assert(s);
 476         TestlyxstringInvariant(this);
 477 //      printf("lyxstring::operator=(value_type const *)\n");
 478
 479         return assign(s);
 480 }
 481
 482
 483 lyxstring & lyxstring::operator=(value_type c)
 484 {
 485         TestlyxstringInvariant(this);
 486
 487         value_type s[1];
 488         s[0] = c;
 489         if (rep->ref == 1) // recycle rep
 490                 rep->assign(1, s);
 491         else {
 492                 rep->ref--;
 493                 rep = new Srep(1, s);
 494         }
 495         return *this;
 496 }
 497
 498
 499 lyxstring & lyxstring::assign(lyxstring const & x)
 500 {
 501         TestlyxstringInvariant(this);
 502
 503         x.rep->ref++; // protect against ``st = st''
 504         if (--rep->ref == 0) delete rep;
 505         rep = x.rep; // share representation
 506         return *this;
 507 }
 508
 509
 510 lyxstring & lyxstring::assign(lyxstring const & x, size_type pos, size_type n)
 511 {
 512         TestlyxstringInvariant(this);
 513
 514         return assign(x.substr(pos, n));
 515 }
 516
 517
 518 lyxstring & lyxstring::assign(value_type const * s, size_type n)
 519 {
 520         Assert(s);
 521         TestlyxstringInvariant(this);
 522
 523         n = min(strlen(s), n);
 524         if (rep->ref == 1) // recycle rep
 525                 rep->assign(n, s);
 526         else {
 527                 rep->ref--;
 528                 rep = new Srep(n, s);
 529         }
 530         return *this;
 531 }
 532
 533
 534 lyxstring & lyxstring::assign(value_type const * s)
 535 {
 536         Assert(s);
 537         TestlyxstringInvariant(this);
 538
 539         return assign(s, strlen(s));
 540 }
 541
 542
 543 lyxstring & lyxstring::assign(size_type n, value_type ch)
 544 {
 545         TestlyxstringInvariant(this);
 546
 547         rep = rep->get_own_copy();
 548         rep->assign(n, ch);
 549         return *this;
 550 }
 551
 552
 553 lyxstring & lyxstring::assign(iterator first, iterator last)
 554 {
 555         TestlyxstringInvariant(this);
 556
 557         rep = rep->get_own_copy();
 558         rep->assign(last - first, first);
 559         return *this;
 560 }
 561
 562
 563 ////////////////////
 564 // Element Access
 565 ////////////////////
 566
 567 lyxstring::const_reference lyxstring::operator[](size_type pos) const
 568 {
 569         Assert(pos < rep->sz);
 570
 571         return rep->s[pos];
 572 }
 573
 574
 575 lyxstring::reference lyxstring::operator[](size_type pos)
 576 {
 577         Assert(pos < rep->sz);
 578         TestlyxstringInvariant(this);
 579
 580         rep = rep->get_own_copy();
 581         return rep->s[pos];
 582 }
 583
 584
 585 lyxstring::const_reference lyxstring::at(size_type n) const
 586 {
 587         Assert(n < rep->sz);
 588
 589         return rep->s[n];
 590 }
 591
 592
 593 lyxstring::reference lyxstring::at(size_type n)
 594 {
 595         Assert(n < rep->sz);
 596         TestlyxstringInvariant(this);
 597
 598         rep = rep->get_own_copy();
 599         return rep->s[n];
 600 }
 601
 602
 603 /////////////
 604 // Insert
 605 /////////////
 606
 607 lyxstring & lyxstring::operator+=(lyxstring const & x)
 608 {
 609         TestlyxstringInvariant(this);
 610
 611         return append(x);
 612 }
 613
 614
 615 lyxstring & lyxstring::operator+=(value_type const * x)
 616 {
 617         Assert(x);
 618         TestlyxstringInvariant(this);
 619
 620         return append(x);
 621 }
 622
 623
 624 lyxstring & lyxstring::operator+=(value_type c)
 625 {
 626         TestlyxstringInvariant(this);
 627
 628         push_back(c);
 629         return *this;
 630 }
 631
 632
 633 void lyxstring::push_back(value_type c)
 634 {
 635         TestlyxstringInvariant(this);
 636
 637         rep = rep->get_own_copy();
 638         rep->push_back(c);
 639 }
 640
 641
 642 lyxstring & lyxstring::append(lyxstring const & x)
 643 {
 644         TestlyxstringInvariant(this);
 645
 646         if (x.empty()) return *this;
 647         rep = rep->get_own_copy();
 648         rep->append(x.length(), x.rep->s);
 649         return *this;
 650 }
 651
 652
 653 lyxstring & lyxstring::append(lyxstring const & x, size_type pos, size_type n)
 654 {
 655         TestlyxstringInvariant(this);
 656
 657         return append(x.substr(pos, n));
 658 }
 659
 660
 661 lyxstring & lyxstring::append(value_type const * p, size_type n)
 662 {
 663         Assert(p);
 664         TestlyxstringInvariant(this);
 665
 666         if (!*p || !n) return *this;
 667         rep = rep->get_own_copy();
 668         rep->append(min(n, strlen(p)), p);
 669         return *this;
 670 }
 671
 672
 673 lyxstring & lyxstring::append(value_type const * p)
 674 {
 675         Assert(p);
 676         TestlyxstringInvariant(this);
 677
 678         if (!*p) return *this;
 679         rep = rep->get_own_copy();
 680         rep->append(strlen(p), p);
 681         return *this;
 682 }
 683
 684
 685 lyxstring & lyxstring::append(size_type n, value_type c)
 686 {
 687         TestlyxstringInvariant(this);
 688
 689         value_type * tmp = new value_type[n];
 690         memset(tmp, c, n);
 691         rep = rep->get_own_copy();
 692         rep->assign(n, tmp);
 693         delete[] tmp;
 694         return *this;
 695 }
 696
 697
 698 lyxstring & lyxstring::append(iterator first, iterator last)
 699 {
 700         TestlyxstringInvariant(this);
 701
 702         rep = rep->get_own_copy();
 703         rep->append(last - first, first);
 704         return *this;
 705 }
 706
 707 // insert value_typeacters before (*this)[pos]
 708
 709 lyxstring & lyxstring::insert(size_type pos, lyxstring const & x)
 710 {
 711         TestlyxstringInvariant(this);
 712
 713         return insert(pos, x, 0, x.rep->sz);
 714 }
 715
 716
 717 lyxstring & lyxstring::insert(size_type pos, lyxstring const & x,
 718                           size_type pos2, size_type n)
 719 {
 720         TestlyxstringInvariant(this);
 721
 722         rep = rep->get_own_copy();
 723         rep->insert(pos, &(x.rep->s[pos2]), min(n, x.rep->sz));
 724         return *this;
 725 }
 726
 727
 728 lyxstring & lyxstring::insert(size_type pos, value_type const * p, size_type n)
 729 {
 730         Assert(p);
 731         TestlyxstringInvariant(this);
 732
 733         if (*p && n) {
 734                 // insert nothing and you change nothing
 735                 rep = rep->get_own_copy();
 736                 rep->insert(pos, p, min(n, strlen(p)));
 737         }
 738         return *this;
 739 }
 740
 741
 742 lyxstring & lyxstring::insert(size_type pos, value_type const * p)
 743 {
 744         Assert(p);
 745         TestlyxstringInvariant(this);
 746
 747         if (*p) {
 748                 // insert nothing and you change nothing
 749                 rep = rep->get_own_copy();
 750                 rep->insert(pos, p, strlen(p));
 751         }
 752         return *this;
 753 }
 754
 755
 756 lyxstring & lyxstring::insert(size_type pos, size_type n, value_type c)
 757 {
 758         TestlyxstringInvariant(this);
 759
 760         rep = rep->get_own_copy();
 761         value_type * tmp = new value_type[n];
 762         memset(tmp, c, n);
 763         rep->insert(pos, tmp, n);
 764         delete[] tmp;
 765         return *this;
 766 }
 767
 768
 769 lyxstring::iterator lyxstring::insert(iterator p, value_type c)
 770 {
 771         TestlyxstringInvariant(this);
 772
 773         // what iterator is this supposed to return??
 774         size_type tmp = p - begin();
 775         insert(p - begin(), 1, c);
 776         return begin() + tmp + 1; // ??
 777 }
 778
 779
 780 void lyxstring::insert(iterator p, size_type n , value_type c)
 781 {
 782         TestlyxstringInvariant(this);
 783
 784         insert(p - begin(), n , c);
 785 }
 786
 787
 788 void lyxstring::insert(iterator p, iterator first, iterator last)
 789 {
 790         TestlyxstringInvariant(this);
 791
 792         insert(p - begin(), first, last - first);
 793 }
 794
 795
 796 ////////////////
 797 // Find
 798 ////////////////
 799
 800          // All the below find functions should be verified,
 801          // it is very likely that I have mixed up or interpreted
 802          // some of the parameters wrong, also some of the funcs can surely
 803          // be written more effectively.
 804
 805 lyxstring::size_type lyxstring::find(lyxstring const & a, size_type i) const
 806 {
 807         if (!rep->sz) return npos;
 808
 809         Assert(i < rep->sz);
 810         TestlyxstringInvariant(this);
 811
 812         for (size_type t = i; rep->sz - t >= a.length(); ++t) {
 813                 // search until (*this)[i] == a[0]
 814                 if (rep->s[t] == a[0]) {
 815                         // check if the rest of the value_types match
 816                         bool equal = true;
 817                         for (size_type j = 0; j < a.length(); ++j) {
 818                                 if (rep->s[t + j] != a[j]) {
 819                                         equal = false;
 820                                         break;
 821                                 }
 822                         }
 823                         if (equal) return t;
 824                 }
 825         }
 826         return npos;
 827 }
 828
 829
 830 lyxstring::size_type lyxstring::find(value_type const * ptr, size_type i,
 831                                  size_type n) const
 832 {
 833         Assert(ptr);
 834         if (!rep->sz || !*ptr) return npos;
 835
 836         Assert(i < rep->sz);
 837         TestlyxstringInvariant(this);
 838
 839         // What is "n" here? is it the number of value_types to use in ptr
 840         // or does "i" and "n" togeter form a substring to search
 841         // for ptr in? For now I will assume that "n" tells the length
 842         // of ptr. (Lgb)
 843         n = min(n, strlen(ptr));
 844         for (size_type t = i; length() - t >= n; ++t) {
 845                 // search until (*this)[i] == a[0]
 846                 if (rep->s[t] == ptr[0]) {
 847                         // check if the rest of the value_types match
 848                         bool equal = true;
 849                         for (size_type j = 0; j < n; ++j) {
 850                                 if (rep->s[t + j] != ptr[j]) {
 851                                         equal = false;
 852                                         break;
 853                                 }
 854                         }
 855                         if (equal) return t;
 856                 }
 857         }
 858         return npos;
 859 }
 860
 861
 862 lyxstring::size_type lyxstring::find(value_type const * s, size_type i) const
 863 {
 864         Assert(s);
 865         if (!rep->sz) return npos;
 866
 867         Assert(i < rep->sz);
 868         TestlyxstringInvariant(this);
 869
 870         if (!s || !*s) return npos;
 871         return find(s, i, strlen(s));
 872 }
 873
 874
 875 lyxstring::size_type lyxstring::find(value_type c, size_type i) const
 876 {
 877         if (!rep->sz) return npos;
 878
 879         Assert(i < rep->sz);
 880         TestlyxstringInvariant(this);
 881
 882         for (size_type t = 0; t + i < length(); ++t) {
 883                 if (rep->s[t + i] == c) return t + i;
 884         }
 885         return npos;
 886 }
 887
 888
 889 lyxstring::size_type lyxstring::rfind(lyxstring const & a, size_type i) const
 890 {
 891         TestlyxstringInvariant(this);
 892
 893         size_type ii = min(length() - 1, i);
 894         do {
 895                 if (a[a.length() - 1] == rep->s[ii]) {
 896                         int t = length() - 2;
 897                         size_type l = ii - 1;
 898                         for (; t >= 0; --t, --l) {
 899                                 if (a[t] != rep->s[l]) break;
 900                         }
 901                         if (a[t] == rep->s[l]) return l;
 902                 }
 903         } while(ii-- > 0);
 904         return npos;
 905 }
 906
 907
 908 lyxstring::size_type lyxstring::rfind(value_type const * ptr, size_type i,
 909                                   size_type n) const
 910 {
 911         Assert(ptr);
 912         TestlyxstringInvariant(this);
 913         if (!*ptr) return npos;
 914
 915         size_type ii = min(length() - 1, i);
 916         do {
 917                 if (ptr[n - 1] == rep->s[ii]) {
 918                         int t = n - 2;
 919                         size_type l = ii - 1;
 920                         for (; t >= 0; --t, --l) {
 921                                 if (ptr[t] != rep->s[l]) break;
 922                         }
 923                         if (ptr[t] == rep->s[l]) return l;
 924                 }
 925         } while (ii-- > 0);
 926         return npos;
 927 }
 928
 929
 930 lyxstring::size_type lyxstring::rfind(value_type const * ptr, size_type i) const
 931 {
 932         Assert(ptr);
 933         TestlyxstringInvariant(this);
 934         if (!*ptr) return npos;
 935
 936         size_type ii = min(length() - 1, i);
 937         do {
 938                 if (ptr[strlen(ptr) - 1] == rep->s[ii]) {
 939                         int t = strlen(ptr) - 2;
 940                         size_type l = ii - 1;
 941                         for (; t >= 0; --t, --l) {
 942                                 if (ptr[t] != rep->s[l]) break;
 943                         }
 944                         if (ptr[t] == rep->s[l]) return l;
 945                 }
 946         } while (ii-- > 0);
 947         return npos;
 948 }
 949
 950
 951 lyxstring::size_type lyxstring::rfind(value_type c, size_type i) const
 952 {
 953         TestlyxstringInvariant(this);
 954
 955         size_type ii = min(length() - 1, i);
 956         for (size_type t = ii; t != 0; --t) {
 957                 if (rep->s[t] == c) return t;
 958         }
 959         return npos;
 960 }
 961
 962
 963 lyxstring::size_type lyxstring::find_first_of(lyxstring const & a,
 964                                           size_type i) const
 965 {
 966         Assert(i < rep->sz);
 967         TestlyxstringInvariant(this);
 968
 969         for (size_type t = i; t < length(); ++t) {
 970                 if (a.find(rep->s[t]) != npos) return t;
 971         }
 972         return npos;
 973 }
 974
 975
 976 lyxstring::size_type lyxstring::find_first_of(value_type const * ptr, size_type i,
 977                                           size_type n) const
 978 {
 979         Assert(ptr && i < rep->sz);
 980         TestlyxstringInvariant(this);
 981         if (!n) return npos;
 982
 983         for (size_type t = i; t < length(); ++t) {
 984                 if(memchr(ptr, rep->s[t], n) != 0) return t;
 985         }
 986         return npos;
 987 }
 988
 989
 990 lyxstring::size_type lyxstring::find_first_of(value_type const * ptr,
 991                                           size_type i) const
 992 {
 993         Assert(ptr && i < rep->sz);
 994         TestlyxstringInvariant(this);
 995
 996         for (size_type t = i; t < length(); ++t) {
 997                 if (strchr(ptr, rep->s[t]) != 0) return t;
 998         }
 999         return npos;
1000 }
1001
1002
1003 lyxstring::size_type lyxstring::find_first_of(value_type c, size_type i) const
1004 {
1005         Assert(i < rep->sz);
1006         TestlyxstringInvariant(this);
1007
1008         for (size_type t = i; t < length(); ++t) {
1009                 if (rep->s[t] == c) return t;
1010         }
1011         return npos;
1012 }
1013
1014
1015 lyxstring::size_type lyxstring::find_last_of(lyxstring const & a,
1016                                          size_type i) const
1017 {
1018         TestlyxstringInvariant(this);
1019
1020         size_type ii = min(length() - 1, i);
1021         for (int t = ii; t >= 0; --t) {
1022                 if (a.find(rep->s[t]) != npos) return t;
1023         }
1024         return npos;
1025 }
1026
1027 lyxstring::size_type lyxstring::find_last_of(value_type const * ptr, size_type i,
1028                                          size_type n) const
1029 {
1030         Assert(ptr);
1031         TestlyxstringInvariant(this);
1032         if (!n) return npos;
1033
1034         size_type ii = min(length() - 1, i);
1035         for (int t = ii; t >= 0; --t) {
1036                 if(memchr(ptr, rep->s[t], n) != 0) return t;
1037         }
1038         return npos;
1039 }
1040
1041
1042 lyxstring::size_type lyxstring::find_last_of(value_type const * ptr,
1043                                          size_type i) const
1044 {
1045         Assert(ptr);
1046         TestlyxstringInvariant(this);
1047
1048         size_type ii = min(length() - 1, i);
1049         for (int t = ii; t >= 0; --t) {
1050                 if (strchr(ptr, rep->s[t]) != 0) return t;
1051         }
1052         return npos;
1053 }
1054
1055
1056 lyxstring::size_type lyxstring::find_last_of(value_type c, size_type i) const
1057 {
1058         TestlyxstringInvariant(this);
1059
1060         if (!rep->sz) return npos;
1061         size_type ii = min(length() - 1, i);
1062         for (int t = ii; t >= 0; --t) {
1063                 if (rep->s[t] == c) return t;
1064         }
1065         return npos;
1066 }
1067
1068
1069 lyxstring::size_type lyxstring::find_first_not_of(lyxstring const & a,
1070                                               size_type i) const
1071 {
1072         TestlyxstringInvariant(this);
1073
1074         if (!rep->sz) return npos;
1075         Assert(i < rep->sz);
1076         for (size_type t = i; t < length(); ++t) {
1077                 if (a.find(rep->s[t]) == npos) return t;
1078         }
1079         return npos;
1080 }
1081
1082
1083 lyxstring::size_type lyxstring::find_first_not_of(value_type const * ptr, size_type i,
1084                                               size_type n) const
1085 {
1086         Assert(ptr && i < rep->sz);
1087         TestlyxstringInvariant(this);
1088
1089         if (!n) return (i < length()) ? i : npos;
1090         for (size_type t = i; t < length(); ++t) {
1091                 if(memchr(ptr, rep->s[t], n) == 0) return t;
1092         }
1093         return npos;
1094 }
1095
1096
1097 lyxstring::size_type lyxstring::find_first_not_of(value_type const * ptr,
1098                                               size_type i) const
1099 {
1100         Assert(ptr && i < rep->sz);
1101         TestlyxstringInvariant(this);
1102
1103         for (size_type t = i; t < length(); ++t) {
1104                 if (strchr(ptr, rep->s[t]) == 0) return t;
1105         }
1106         return npos;
1107 }
1108
1109
1110 lyxstring::size_type lyxstring::find_first_not_of(value_type c, size_type i) const
1111 {
1112         if (!rep->sz) return npos;
1113         Assert(i < rep->sz);
1114         TestlyxstringInvariant(this);
1115
1116         for (size_type t = i; t < length(); ++t) {
1117                 if (rep->s[t] != c) return t;
1118         }
1119         return npos;
1120 }
1121
1122
1123 lyxstring::size_type lyxstring::find_last_not_of(lyxstring const & a,
1124                                              size_type i) const
1125 {
1126         TestlyxstringInvariant(this);
1127
1128         size_type ii = min(length() - 1, i);
1129         for (int t = ii; t >= 0; --t) {
1130                 if (a.find(rep->s[t]) == npos) return t;
1131         }
1132         return npos;
1133 }
1134
1135
1136 lyxstring::size_type lyxstring::find_last_not_of(value_type const * ptr, size_type i,
1137                                              size_type n) const
1138 {
1139         Assert(ptr);
1140         TestlyxstringInvariant(this);
1141
1142         size_type ii = min(length() - 1, i);
1143         if (!n) return (ii >= 0) ? ii : npos;
1144         for (int t = ii; t >= 0; --t) {
1145                 if(memchr(ptr, rep->s[t], n) == 0) return t;
1146         }
1147         return npos;
1148 }
1149
1150
1151 lyxstring::size_type lyxstring::find_last_not_of(value_type const * ptr,
1152                                              size_type i) const
1153 {
1154         Assert(ptr);
1155         TestlyxstringInvariant(this);
1156
1157         size_type ii = min(length() - 1, i);
1158         for (int t = ii; t >= 0; --t) {
1159                 if (strchr(ptr, rep->s[t]) == 0) return t;
1160         }
1161         return npos;
1162 }
1163
1164
1165 lyxstring::size_type lyxstring::find_last_not_of(value_type c, size_type i) const
1166 {
1167         TestlyxstringInvariant(this);
1168
1169         size_type ii = min(length() - 1, i);
1170         for (int t = ii; t >= 0; --t) {
1171                 if (rep->s[t] != c) return t;
1172         }
1173         return npos;
1174 }
1175
1176
1177 /////////////////
1178 // Replace
1179 /////////////////
1180
1181 lyxstring & lyxstring::replace(size_type i, size_type n, lyxstring const & x)
1182 {
1183         Assert(i < rep->sz || i == 0);
1184         TestlyxstringInvariant(this);
1185
1186         return replace(i, n, x, 0, x.length());
1187 }
1188
1189
1190 lyxstring &  lyxstring::replace(size_type i,size_type n, lyxstring const & x,
1191                             size_type i2, size_type n2)
1192 {
1193         Assert((i < rep->sz || i == 0) && (i2 < x.rep->sz || i2 == 0));
1194         TestlyxstringInvariant(this);
1195
1196         rep = rep->get_own_copy();
1197         rep->replace(i, min(n, rep->sz), &(x.rep->s[i2]), min(n2, x.rep->sz));
1198         return *this;
1199 }
1200
1201
1202 lyxstring & lyxstring::replace(size_type i, size_type n, value_type const * p,
1203                            size_type n2)
1204 {
1205         Assert(p && i < rep->sz);
1206         TestlyxstringInvariant(this);
1207
1208         rep = rep->get_own_copy();
1209         rep->replace(i, min(n, rep->sz), p, min(n2, strlen(p)));
1210         return *this;
1211 }
1212
1213
1214 lyxstring & lyxstring::replace(size_type i, size_type n, value_type const * p)
1215 {
1216         Assert(p && i < rep->sz);
1217         TestlyxstringInvariant(this);
1218
1219         return replace(i, min(n, rep->sz), p, (!p) ? 0 : strlen(p));
1220 }
1221
1222
1223 lyxstring & lyxstring::replace(size_type i, size_type n, size_type n2, value_type c)
1224 {
1225         Assert(i < rep->sz);
1226         TestlyxstringInvariant(this);
1227
1228         rep = rep->get_own_copy();
1229         value_type * tmp = new value_type[n2];
1230         memset(tmp, c, n2);
1231         rep->replace(i, min(n, rep->sz), tmp, n2);
1232         delete[] tmp;
1233         return *this;
1234 }
1235
1236
1237 lyxstring & lyxstring::replace(iterator i, iterator i2, const lyxstring & str)
1238 {
1239         TestlyxstringInvariant(this);
1240
1241         return replace(i - begin(), i2 - i, str);
1242 }
1243
1244
1245 lyxstring & lyxstring::replace(iterator i, iterator i2,
1246                            value_type const * p, size_type n)
1247 {
1248         Assert(p);
1249         TestlyxstringInvariant(this);
1250
1251         return replace(i - begin(), i2 - i, p, n);
1252 }
1253
1254
1255 lyxstring & lyxstring::replace(iterator i, iterator i2, value_type const * p)
1256 {
1257         Assert(p);
1258         TestlyxstringInvariant(this);
1259
1260         return replace(i - begin(), i2 - i, p);
1261 }
1262
1263
1264 lyxstring & lyxstring::replace(iterator i, iterator i2, size_type n , value_type c)
1265 {
1266         TestlyxstringInvariant(this);
1267
1268         return replace(i - begin(), i2 - i, n, c);
1269 }
1270
1271
1272 lyxstring & lyxstring::replace(iterator i, iterator i2, iterator j, iterator j2)
1273 {
1274         TestlyxstringInvariant(this);
1275
1276         return replace(i - begin(), i2 - i, j, j2 - j);
1277 }
1278
1279
1280 lyxstring & lyxstring::erase(size_type i, size_type n)
1281 {
1282         Assert(i < rep->sz || i == 0);
1283         TestlyxstringInvariant(this);
1284
1285         rep = rep->get_own_copy();
1286         if (i == 0 && n >= rep->sz) {
1287                 rep->sz = 0;
1288         } else {
1289                 n = min(n, rep->sz - i);
1290                 memmove(&(rep->s[i]), &(rep->s[i + n]), rep->sz - i - n);
1291                 rep->sz -= n;
1292         }
1293         return *this;
1294 }
1295
1296
1297 lyxstring::iterator lyxstring::erase(iterator i)
1298 {
1299         TestlyxstringInvariant(this);
1300
1301         // what iterator is this supposed to return?
1302         // the iterator after the one erased
1303         erase(i - begin(), 1);
1304         return begin(); // BUG
1305 }
1306
1307
1308 lyxstring::iterator lyxstring::erase(iterator first, iterator last)
1309 {
1310         TestlyxstringInvariant(this);
1311
1312         erase(first - begin(), last - first);
1313         return begin(); // BUG
1314 }
1315
1316
1317 /////////////////////////////////////
1318 // Conversion to C-style Strings
1319 /////////////////////////////////////
1320
1321 lyxstring::value_type const * lyxstring::c_str() const
1322 {
1323         rep->s[length()] = '\0';
1324         return rep->s;
1325 }
1326
1327
1328 lyxstring::value_type const * lyxstring::data() const
1329 {
1330         return rep->s;
1331 }
1332
1333
1334 lyxstring::size_type lyxstring::copy(value_type * buf, size_type len, size_type pos) const
1335 {
1336         Assert(buf);
1337         TestlyxstringInvariant(this);
1338
1339         register int nn = min(len, length() - pos);
1340         memcpy(buf, &(rep->s[pos]), nn);
1341         return nn;
1342 }
1343
1344
1345 ////////////////////
1346 // Comparisons
1347 ////////////////////
1348
1349 // Compare funcs should be verified.
1350 // Should we try to make them work with '\0' value_types?
1351 // An STL string can usually contain '\0' value_types.
1352
1353 int lyxstring::compare(lyxstring const & str) const
1354 {
1355         TestlyxstringInvariant(this);
1356
1357         return compare(0, rep->sz, str.rep->s, str.rep->sz);
1358 }
1359
1360
1361 int lyxstring::compare(value_type const * s) const
1362 {
1363         Assert(s);
1364         TestlyxstringInvariant(this);
1365
1366         return compare(0, rep->sz, s, (!s) ? 0 : strlen(s));
1367 }
1368
1369
1370 int lyxstring::compare(size_type pos, size_type n, lyxstring const & str) const
1371 {
1372         TestlyxstringInvariant(this);
1373
1374         return compare(pos, n, str.rep->s, str.rep->sz);
1375 }
1376
1377
1378 int lyxstring::compare(size_type pos, size_type n, lyxstring const & str,
1379                      size_type pos2, size_type n2) const
1380 {
1381         TestlyxstringInvariant(this);
1382
1383         return compare(pos, n, str.rep->s + pos2, n2);
1384 }
1385
1386
1387 int lyxstring::compare(size_type pos, size_type n, value_type const * s,
1388                      size_type n2) const
1389 {
1390         Assert(s && (pos < rep->sz || pos == 0));
1391         TestlyxstringInvariant(this);
1392
1393         if ((rep->sz == 0 || n == 0) && (!*s || n2 == 0)) return 0;
1394         if (!*s) return 1;
1395         // since n > n2, min(n,n2) == 0, c == 0 (stops segfault also)
1396
1397         // remember that n can very well be a lot larger than rep->sz
1398         // so we have to ensure that n is no larger than rep->sz
1399         n = min(n, rep->sz);
1400         n2 = min(n2, strlen(s));
1401         if (n == n2)
1402                 return memcmp(&(rep->s[pos]), s, n);
1403         int c = memcmp(&(rep->s[pos]), s, min(n,n2));
1404         if (c)
1405                 return c;
1406         if (n < n2)
1407                 return -1;
1408         return 1;
1409 }
1410
1411
1412 /////////////////
1413 // Substrings
1414 /////////////////
1415
1416 // i = index, n = length
1417 lyxstring lyxstring::substr(size_type i, size_type n) const
1418 {
1419         Assert(i < rep->sz || i == 0);
1420         TestlyxstringInvariant(this);
1421
1422         return lyxstring(*this, i, n);
1423 }
1424
1425
1426
1427 /////////////////////////////////////////////
1428 // String operators, non member functions
1429 /////////////////////////////////////////////
1430
1431 bool operator==(lyxstring const & a, lyxstring const & b)
1432 {
1433         return a.compare(b) == 0;
1434 }
1435
1436
1437 bool operator==(lyxstring::value_type const * a, lyxstring const & b)
1438 {
1439         Assert(a);
1440         return b.compare(a) == 0;
1441 }
1442
1443
1444 bool operator==(lyxstring const & a, lyxstring::value_type const * b)
1445 {
1446         Assert(b);
1447         return a.compare(b) == 0;
1448 }
1449
1450
1451 bool operator!=(lyxstring const & a, lyxstring const & b)
1452 {
1453         return a.compare(b) != 0;
1454 }
1455
1456
1457 bool operator!=(lyxstring::value_type const * a, lyxstring const & b)
1458 {
1459         Assert(a);
1460         return b.compare(a) != 0;
1461 }
1462
1463
1464 bool operator!=(lyxstring const & a, lyxstring::value_type const * b)
1465 {
1466         Assert(b);
1467         return a.compare(b) != 0;
1468 }
1469
1470
1471 bool operator>(lyxstring const & a, lyxstring const & b)
1472 {
1473         return a.compare(b) > 0;
1474 }
1475
1476
1477 bool operator>(lyxstring::value_type const * a, lyxstring const & b)
1478 {
1479         Assert(a);
1480         return b.compare(a) < 0; // since we reverse the parameters
1481 }
1482
1483
1484 bool operator>(lyxstring const & a, lyxstring::value_type const * b)
1485 {
1486         Assert(b);
1487         return a.compare(b) > 0;
1488 }
1489
1490
1491 bool operator<(lyxstring const & a, lyxstring const & b)
1492 {
1493         return a.compare(b) < 0;
1494 }
1495
1496
1497 bool operator<(lyxstring::value_type const * a, lyxstring const & b)
1498 {
1499         Assert(a);
1500         return b.compare(a) > 0; // since we reverse the parameters
1501 }
1502
1503
1504 bool operator<(lyxstring const & a, lyxstring::value_type const * b)
1505 {
1506         Assert(b);
1507         return a.compare(b) < 0;
1508 }
1509
1510
1511 bool operator>=(lyxstring const & a, lyxstring const & b)
1512 {
1513         return a.compare(b) >= 0;
1514 }
1515
1516
1517 bool operator>=(lyxstring::value_type const * a, lyxstring const & b)
1518 {
1519         Assert(a);
1520         return b.compare(a) <= 0; // since we reverse the parameters
1521 }
1522
1523
1524 bool operator>=(lyxstring const & a, lyxstring::value_type const * b)
1525 {
1526         Assert(b);
1527         return a.compare(b) >= 0;
1528 }
1529
1530
1531 bool operator<=(lyxstring const & a, lyxstring const & b)
1532 {
1533         return a.compare(b) <= 0;
1534 }
1535
1536
1537 bool operator<=(lyxstring::value_type const * a, lyxstring const & b)
1538 {
1539         Assert(a);
1540         return b.compare(a) >= 0; // since we reverse the parameters
1541 }
1542
1543
1544 bool operator<=(lyxstring const & a, lyxstring::value_type const * b)
1545 {
1546         Assert(b);
1547         return a.compare(b) <= 0;
1548 }
1549
1550
1551 lyxstring operator+(lyxstring const & a, lyxstring const & b)
1552 {
1553         lyxstring tmp(a);
1554         tmp += b;
1555         return tmp;
1556 }
1557
1558
1559 lyxstring operator+(lyxstring::value_type const * a, lyxstring const & b)
1560 {
1561         Assert(a);
1562         lyxstring tmp(a);
1563         tmp += b;
1564         return tmp;
1565 }
1566
1567
1568 lyxstring operator+(lyxstring::value_type a, lyxstring const & b)
1569 {
1570         lyxstring tmp;
1571         tmp += a;
1572         tmp += b;
1573         return tmp;
1574 }
1575
1576
1577 lyxstring operator+(lyxstring const & a, lyxstring::value_type const * b)
1578 {
1579         Assert(b);
1580         lyxstring tmp(a);
1581         tmp += b;
1582         return tmp;
1583 }
1584
1585
1586 lyxstring operator+(lyxstring const & a, lyxstring::value_type b)
1587 {
1588         lyxstring tmp(a);
1589         tmp += b;
1590         return tmp;
1591 }
1592
1593 #include <iostream>
1594
1595 istream & operator>>(istream & is, lyxstring & s)
1596 {
1597         // very bad solution
1598         char nome[1024];
1599         is >> nome;
1600         lyxstring tmp(nome);
1601         if (!tmp.empty()) s = tmp;
1602         return is;
1603 }
1604
1605 ostream & operator<<(ostream & o, lyxstring const & s)
1606 {
1607         return o.write(s.data(), s.length());
1608 }
1609
1610 istream & getline(istream & is, lyxstring & s,
1611                   lyxstring::value_type delim)
1612 {
1613         // very bad solution
1614         char tmp;
1615         s.erase();
1616         while(is) {
1617                 is >> tmp;
1618                 if (tmp != delim) {
1619                         s += tmp;
1620                 } else {
1621                         break;
1622                 }
1623         }
1624         return is;
1625 }
1626
1627 #endif /* USE_INCLUDED_STRING */