string

   1 // vi:ft=cpp
   2 #ifndef _STL_STRING_H
   3 #define _STL_STRING_H
   4
   5 #include "ios"
   6 #include "algorithm"
   7 #include "memory"
   8 #include "iterator"
   9 #include "cstdio" // for EOF
  10
  11 namespace std {
  12
  13 template <class T>
  14 struct char_traits;
  15
  16 template <class T, class Spc>
  17 struct __basic_char_traits: public Spc {
  18     typedef T char_type;
  19     typedef streamoff off_type;
  20     typedef streampos pos_type;
  21     typedef mbstate_t state_type;
  22     static void assign(char_type &c1, const char_type &c2){ c1 = c2; }
  23     static bool eq(const char_type &c1, const char_type &c2){ return c1 == c2; }
  24     static bool lt(const char_type &c1, const char_type &c2){ return c1 < c2; }
  25
  26     static int compare(const char_type *s1, const char_type *s2, size_t n)
  27     {
  28         for (size_t i=0; i<n; ++i){
  29             if (lt(s1[i], s2[i])){
  30                 return -1;
  31             } else if (lt(s2[i], s1[i])){
  32                 return 1;
  33             }
  34         }
  35         return 0;
  36     }
  37
  38     static size_t length(const char_type *s)
  39     {
  40         size_t len = 0;
  41         while (s[len]){
  42             ++len;
  43         }
  44         return len;
  45     }
  46
  47     static const char_type find(const char_type *s, size_t n, const char_type &a)
  48     {
  49         for (size_t i=0; i<n; ++i){
  50             if (eq(s[i], a)){
  51                 return s + i;
  52             }
  53         }
  54         return 0;
  55     }
  56
  57     static char_type *move(char_type *s1, const char_type *s2, size_t n)
  58     {
  59         return static_cast<char_type *>(__builtin_memmove(s1, s2, n * sizeof(char_type)));
  60     }
  61
  62     static char_type *copy(char_type *s1, const char_type *s2, size_t n)
  63     {
  64         std::copy(s2, s2 + n, s1);
  65         return s1;
  66     }
  67
  68     static char_type *assign(char_type *s, size_t n, char_type a)
  69     {
  70         std::fill_n(s, n, a);
  71         return s;
  72     }
  73
  74     static char_type to_char_type(const typename Spc::int_type &c)
  75     {
  76         return char_type(c);
  77     }
  78
  79     static typename Spc::int_type to_int_type(const char_type &c)
  80     {
  81         return typename Spc::int_type(c);
  82     }
  83
  84     static bool eq_int_type(const typename Spc::int_type &c1, const typename Spc::int_type &c2)
  85     {
  86         return c1 == c2;
  87     }
  88
  89     static typename Spc::int_type not_eof(const typename Spc::int_type &c)
  90     {
  91         return eq_int_type(c, Spc::eof()) ? 0 : c;
  92     }
  93 };
  94
  95 template <class T>
  96 struct __spc_char_traits;
  97
  98 template <>
  99 struct __spc_char_traits<char> {
 100     typedef int int_type;
 101
 102     static int_type eof()
 103     {
 104         return EOF;
 105     }
 106 };
 107
 108 template <>
 109 struct __spc_char_traits<wchar_t> {
 110     typedef wint_t int_type;
 111
 112     static int_type eof()
 113     {
 114         return WEOF;
 115     }
 116 };
 117
 118
 119 template <>
 120 struct char_traits<char>: public __basic_char_traits<char, __spc_char_traits<char> > { };
 121
 122 template <>
 123 struct char_traits<wchar_t>: public __basic_char_traits<wchar_t, __spc_char_traits<wchar_t> > { };
 124
 125 template <class T>
 126 class basic_string {
 127 private:
 128     typedef char_traits<T> traits;
 129     typedef allocator<T> allocator_type;
 130     T *data_;
 131     size_t size_;
 132     size_t capacity_;
 133     allocator_type allocator_;
 134
 135     void init_()
 136     {
 137         data_ = NULL;
 138         size_ = 0;
 139         capacity_ = 0;
 140     }
 141
 142     void shift_(size_t pos, size_t n)
 143     {
 144         // 0            0
 145         // 1            1
 146         // 2 <pos       a <pos
 147         // 3            b
 148         // 4 <pos+n     2 <pos+n
 149         // 5            3
 150         //   <size      4
 151         //              5
 152         reserve(size_ + n);
 153         std::copy_backward(data_ + pos, data_ + size_, data_ + size_ + n);
 154         size_ += n;
 155     }
 156
 157     void unshift_(size_t pos, size_t n)
 158     {
 159         // 0            0
 160         // 1            1
 161         // a <pos       2 <pos
 162         // b            3
 163         // 2 <pos+n     4 <pos+n
 164         // 3            5
 165         // 4              <size
 166         // 5
 167         std::copy(data_ + pos + n, data_ + size_, data_ + pos);
 168         size_ -= n;
 169     }
 170
 171     void bcheck_(const basic_string &str, size_t pos, size_t n)
 172     {
 173         if (pos + n > str.size()){
 174             throw_exc();
 175         }
 176     }
 177
 178     static void throw_exc();
 179
 180 public:
 181     static const size_t npos = -1; // O_o
 182     typedef T *iterator;
 183     typedef const T *const_iterator;
 184     typedef std::reverse_iterator<iterator> reverse_iterator;
 185     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 186
 187     explicit basic_string()
 188     {
 189         init_();
 190     }
 191
 192     basic_string(const basic_string &str)
 193     {
 194         init_();
 195         assign(str);
 196     }
 197
 198     basic_string(const basic_string &str, size_t pos, size_t n = npos)
 199     {
 200         init_();
 201         assign(str, pos, n);
 202     }
 203
 204     basic_string(const T *s, size_t n)
 205     {
 206         init_();
 207         assign(s, n);
 208     }
 209
 210     basic_string(const T *s)
 211     {
 212         init_();
 213         assign(s);
 214     }
 215
 216     basic_string(size_t n, T c)
 217     {
 218         init_();
 219         assign(n, c);
 220     }
 221
 222     template <class InputIterator>
 223     basic_string(InputIterator begin, InputIterator end)
 224     {
 225         init_();
 226         assign(begin, end);
 227     }
 228
 229     ~basic_string()
 230     {
 231         allocator_.deallocate(data_, capacity_);
 232     }
 233
 234     basic_string &operator = (const basic_string &str)
 235     {
 236         return assign(str);
 237     }
 238
 239     basic_string &operator = (const T *s)
 240     {
 241         return assign(s);
 242     }
 243
 244     basic_string &operator = (T c)
 245     {
 246         return assign(1, c);
 247     }
 248
 249     iterator begin(){ return data_; }
 250     iterator end(){ return data_ + size_; }
 251     reverse_iterator rbegin(){ return reverse_iterator(end()); }
 252     reverse_iterator rend(){ return reverse_iterator(begin()); }
 253
 254     const_iterator begin() const { return data_; }
 255     const_iterator end() const { return data_ + size_; }
 256     const_reverse_iterator rbegin() const { return reverse_iterator(end()); }
 257     const_reverse_iterator rend() const { return reverse_iterator(begin()); }
 258
 259     size_t size() const { return size_; }
 260     size_t length() const { return size_; }
 261     size_t max_size() const { return numeric_limits<size_t>::max() / sizeof(T); }
 262     size_t capacity() const { return capacity_; }
 263     bool empty() const { return size_ == 0; }
 264
 265     void reserve(size_t res_arg = 0)
 266     {
 267         if (res_arg > capacity_){
 268             T *new_data = allocator_.allocate(res_arg + 1, data_);
 269             std::copy(data_, data_ + size_, new_data);
 270             new_data[res_arg] = T();
 271             allocator_.deallocate(data_, capacity_);
 272             data_ = new_data;
 273             capacity_ = res_arg;
 274         }
 275     }
 276
 277     void resize(size_t n, T c)
 278     {
 279         if (n > size_){
 280             // expand
 281             reserve(n);
 282             std::fill_n(data_ + size_, n - size_, c);
 283             size_ = n;
 284         } else {
 285             // contract
 286             size_ = n;
 287         }
 288     }
 289
 290     void resize(size_t n)
 291     {
 292         resize(n, T());
 293     }
 294
 295     void clear()
 296     {
 297         resize(0);
 298     }
 299
 300     const T &operator [] (size_t pos) const
 301     {
 302         return data_[pos];
 303     }
 304
 305     T &operator [] (size_t pos)
 306     {
 307         return data_[pos];
 308     }
 309
 310     const char &at(size_t pos) const
 311     {
 312         if (pos >= 0 && pos < size_){
 313             return data_[pos];
 314         } else {
 315             throw_exc();
 316         }
 317     }
 318
 319     basic_string &operator += (const basic_string &str)
 320     {
 321         return append(str);
 322     }
 323
 324     basic_string &operator += (const T *s)
 325     {
 326         return append(s);
 327     }
 328
 329     basic_string &operator += (T c)
 330     {
 331         return append(1, c);
 332     }
 333
 334     // string operations - iterator forms
 335
 336     template <class InputIterator>
 337     basic_string &append(InputIterator first, InputIterator last)
 338     {
 339         size_t n = distance(first, last);
 340         reserve(size_ + n);
 341         std::copy(first, last, data_ + size_);
 342         size_ += n;
 343         return *this;
 344     }
 345
 346     template <class InputIterator>
 347     basic_string &assign(InputIterator begin, InputIterator end)
 348     {
 349         size_t s_len = distance(begin, end);
 350         reserve(s_len);
 351         std::copy(begin, end, data_);
 352         size_ = s_len;
 353         return *this;
 354     }
 355
 356     template <class InputIterator>
 357     void insert(iterator p, InputIterator first, InputIterator last)
 358     {
 359         size_t pos = p - begin();
 360         shift_(pos, distance(first, last));
 361         std::copy(first, last, data_ + pos);
 362     }
 363
 364     iterator erase(iterator first, iterator last)
 365     {
 366         size_t pos = first = begin();
 367         unshift_(pos, distance(first, last));
 368         return begin() + pos;
 369     }
 370
 371     template <class InputIterator>
 372     basic_string &replace(iterator i1, iterator i2, InputIterator j1, InputIterator j2)
 373     {
 374         size_t i_len = distance(i1, i2),
 375                j_len = distance(j1, j2),
 376                i1_pos = i1 - begin(),
 377                i2_pos = i2 - begin();
 378         if (j_len > i_len){
 379             // grow
 380             shift_(i2_pos, j_len - i_len);
 381         } else {
 382             // shrink
 383             unshift_(i1_pos + j_len, i_len - j_len);
 384         }
 385         std::copy(j1, j2, data_ + i1_pos);
 386         return *this;
 387     }
 388
 389     // other forms of the same operations
 390
 391     basic_string &append(const basic_string &str)
 392     {
 393         return append(str.begin(), str.end());
 394     }
 395
 396     basic_string &append(const basic_string &str, size_t pos, size_t n)
 397     {
 398         bcheck_(str, pos, n);
 399         return append(str.begin() + pos, str.begin() + pos + n);
 400     }
 401
 402     basic_string &append(const T *s, size_t n)
 403     {
 404         return append(s, s + n);
 405     }
 406
 407     basic_string &append(const T *s)
 408     {
 409         return append(s, s + traits::length(s));
 410     }
 411
 412     basic_string &append(size_t n, char c)
 413     {
 414         return append(value_iterator<T>(c, 0), value_iterator<T>(c, n));
 415     }
 416
 417     void push_back(T c)
 418     {
 419         append(1, c);
 420     }
 421
 422     basic_string &assign(const basic_string &str)
 423     {
 424         return assign(str.begin(), str.end());
 425     }
 426
 427     basic_string &assign(const basic_string &str, size_t pos, size_t n)
 428     {
 429         bcheck_(str, pos, n);
 430         return assign(str.begin() + pos, str.begin() + pos + n);
 431     }
 432
 433     basic_string &assign(const T *s, size_t n)
 434     {
 435         return assign(s, s + n);
 436     }
 437
 438     basic_string &assign(const T *s)
 439     {
 440         return assign(s, s + traits::length(s));
 441     }
 442
 443     basic_string &assign(size_t n, T c)
 444     {
 445         return assign(value_iterator<T>(c, 0), value_iterator<T>(c, n));
 446     }
 447
 448     basic_string &insert(size_t pos, const basic_string &str)
 449     {
 450         insert(begin() + pos, str.begin(), str.end());
 451         return *this;
 452     }
 453
 454     basic_string &insert(size_t pos, const basic_string &str, size_t pos2, size_t n)
 455     {
 456         bcheck_(str, pos2, n);
 457         insert(begin() + pos, str.begin() + pos2, str.begin() + pos2 + n);
 458         return *this;
 459     }
 460
 461     basic_string &insert(size_t pos, const T *s, size_t n)
 462     {
 463         insert(begin() + pos, s, s + n);
 464         return *this;
 465     }
 466
 467     basic_string &insert(size_t pos, const T *s)
 468     {
 469         insert(begin() + pos, s, s + traits::length(s));
 470         return *this;
 471     }
 472
 473     basic_string &insert(size_t pos, size_t n, T c)
 474     {
 475         insert(begin() + pos, value_iterator<T>(c, 0), value_iterator<T>(c, n));
 476         return *this;
 477     }
 478
 479     iterator insert(iterator p, char c)
 480     {
 481         size_t pos = p - begin();
 482         insert(p, value_iterator<T>(c, 0), value_iterator<T>(c, 1));
 483         return begin() + pos;
 484     }
 485
 486     void insert(iterator p, size_t n, char c)
 487     {
 488         insert(p, value_iterator<T>(c, 0), value_iterator<T>(c, n));
 489     }
 490
 491     basic_string &erase(size_t pos = 0, size_t n = npos)
 492     {
 493         if (n == npos){
 494             n = size_ - pos;
 495         }
 496         erase(begin() + pos, begin() + pos + n);
 497         return *this;
 498     }
 499
 500     iterator erase(iterator position)
 501     {
 502         size_t pos = position - begin();
 503         erase(position, position + 1);
 504         return begin() + pos;
 505     }
 506
 507     basic_string &replace(size_t pos1, size_t n1, const basic_string &str)
 508     {
 509         return replace(begin() + pos1, begin() + pos1 + n1, str.begin(), str.end());
 510     }
 511
 512     basic_string &replace(iterator i1, iterator i2, const basic_string &str)
 513     {
 514         return replace(i1, i2, str.begin(), str.end());
 515     }
 516
 517     basic_string &replace(size_t pos1, size_t n1, const basic_string &str, size_t pos2, size_t n2)
 518     {
 519         bcheck_(str, pos2, n2);
 520         return replace(begin() + pos1, begin() + pos1 + n1, str.begin() + pos2, str.begin() + pos2 + n2);
 521     }
 522
 523     basic_string &replace(size_t pos1, size_t n1, const T *s, size_t n2)
 524     {
 525         return replace(begin() + pos1, begin() + pos1 + n1, s, s + n2);
 526     }
 527
 528     basic_string &replace(iterator i1, iterator i2, const T *s, size_t n2)
 529     {
 530         return replace(i1, i2, s, s + n2);
 531     }
 532
 533     basic_string &replace(size_t pos1, size_t n1, const T *s)
 534     {
 535         return replace(begin() + pos1, begin() + pos1 + n1, s, s + traits::length(s));
 536     }
 537
 538     basic_string &replace(iterator i1, iterator i2, const T *s)
 539     {
 540         return replace(i1, i2, s, s + traits::length(s));
 541     }
 542
 543     basic_string &replace(size_t pos1, size_t n1, size_t n2, T c)
 544     {
 545         return replace(begin() + pos1, begin() + pos1 + n1,
 546           value_iterator<T>(c, 0), value_iterator<T>(c, n2));
 547     }
 548
 549     basic_string &replace(iterator i1, iterator i2, size_t n2, T c)
 550     {
 551         return replace(i1, i2, value_iterator<T>(c, 0), value_iterator<T>(c, n2));
 552     }
 553
 554     size_t copy(T *s, size_t n, size_t pos = 0) const
 555     {
 556         if (n > size_ - pos){
 557             n = size_ - pos;
 558         }
 559         std::copy(begin() + pos, begin() + pos + n, s);
 560         return n;
 561     }
 562
 563     void swap(basic_string &str)
 564     {
 565         T *data_copy = data_;
 566         size_t size_copy = size_;
 567         size_t capacity_copy = capacity_;
 568
 569         data_ = str.data_;
 570         size_ = str.size_;
 571         capacity_ = str.capacity_;
 572
 573         str.data_ = data_copy;
 574         str.size_ = size_copy;
 575         str.capacity_ = capacity_copy;
 576     }
 577
 578     const T *c_str() const
 579     {
 580         // NOTE: string is always
 581         // kept null-terminated anyway
 582         return data_;
 583     }
 584
 585     const T *data() const
 586     {
 587         return data_;
 588     }
 589
 590     allocator<T> get_allocator() const
 591     {
 592         return allocator_;
 593     }
 594
 595     // TODO: find, substr, etc. etc.
 596
 597 };
 598
 599 typedef basic_string<char> string;
 600
 601 }
 602
 603 #endif