00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00038 #ifndef COL_ARRAYLIST_H
00039 #define COL_ARRAYLIST_H
00040
00041 #include "fastlib/base/base.h"
00042
00043 #define ARRAYLIST__DEBUG_INIT_OK(who, size, cap) \
00044 DEBUG_INIT_OK(who); \
00045 DEBUG_ASSERT(size >= 0); \
00046 DEBUG_ASSERT(size <= cap);
00047
00048 #define ARRAYLIST__DEBUG_PUSH_BACK_OK(who, inc) \
00049 DEBUG_MODIFY_OK(who); \
00050 DEBUG_ASSERT(inc >= 0);
00051
00052 #define ARRAYLIST__DEBUG_POP_BACK_OK(who, dec) \
00053 DEBUG_MODIFY_OK(who); \
00054 DEBUG_BOUNDS_INCLUSIVE(dec, who->size());
00055
00056 #define ARRAYLIST__DEBUG_INSERT_OK(who, pos, inc) \
00057 DEBUG_MODIFY_OK(who); \
00058 DEBUG_BOUNDS_INCLUSIVE(pos, who->size()); \
00059 DEBUG_ASSERT(inc >= 0);
00060
00061 #define ARRAYLIST__DEBUG_REMOVE_OK(who, pos, dec) \
00062 DEBUG_MODIFY_OK(who); \
00063 DEBUG_BOUNDS_INCLUSIVE(pos, who->size()); \
00064 DEBUG_BOUNDS_INCLUSIVE(dec, who->size() - pos);
00065
00083 template<typename TElem>
00084 class ArrayList {
00085 public:
00087 typedef TElem Elem;
00088
00089 private:
00090 Elem *ptr_;
00091 index_t size_;
00092 index_t cap_;
00093
00094 OBJECT_TRAVERSAL_DEPRECATED_COPIES(ArrayList) {
00095
00096 OT_OBJ(size_);
00097 OT_ALLOC_EXPERT(ptr_, size_, false,
00098 i, OT_OBJ(ptr_[i]));
00099 }
00100 OT_DEFAULT_CONSTRUCT(ArrayList) {
00101 Reset_();
00102 OT__BecomeAlias_();
00103 }
00104
00105 OT_TRANSIENTS(ArrayList) {
00106 OT_OBJ(cap_);
00107 }
00108 OT_REFILL_TRANSIENTS(ArrayList) {
00109
00110 cap_ = size_;
00111 }
00112
00113 OT_BECOME_ALIAS(ArrayList) {
00114 cap_ = -1;
00115 }
00116 OT_IS_ALIAS(ArrayList) {
00117 return cap_ == -1;
00118 }
00119 OT_ALIAS_METHODS(ArrayList);
00120
00121 private:
00122
00123 void IncreaseCap_(index_t cap);
00124
00125
00126 void Reset_() {
00127 ptr_ = NULL;
00128 size_ = 0;
00129 cap_ = 0;
00130 }
00131
00132 public:
00153 Elem *InitRaw(index_t size, index_t cap) {
00154 ARRAYLIST__DEBUG_INIT_OK(this, size, cap);
00155 ptr_ = mem::Alloc<Elem>(size);
00156 size_ = size;
00157 cap_ = cap;
00158 return ptr_;
00159 }
00160 Elem *InitRaw(index_t size) {
00161 return InitRaw(size, size);
00162 }
00163
00169 void Init() {
00170 DEBUG_INIT_OK(this);
00171 Reset_();
00172 }
00173
00183 void Init(index_t size, index_t cap) {
00184 ARRAYLIST__DEBUG_INIT_OK(this, size, cap);
00185 ot::Construct(InitRaw(size, cap), size);
00186 }
00187 void Init(index_t size) {
00188 Init(size, size);
00189 }
00190
00202 void InitRepeat(const Elem &elem, index_t size, index_t cap) {
00203 ARRAYLIST__DEBUG_INIT_OK(this, size, cap);
00204 ot::RepeatConstruct(InitRaw(size, cap), elem, size);
00205 }
00206 void InitRepeat(const Elem &elem, index_t size) {
00207 InitRepeat(elem, size, size);
00208 }
00209
00221 void InitCopy(const Elem *src, index_t size, index_t cap) {
00222 ARRAYLIST__DEBUG_INIT_OK(this, size, cap);
00223 ot::CopyConstruct(InitRaw(size, cap), src, size);
00224 }
00225 void InitCopy(const Elem *src, index_t size) {
00226 InitCopy(src, size, size);
00227 }
00228
00238 void InitCopy(const ArrayList &src, index_t cap) {
00239 ARRAYLIST__DEBUG_INIT_OK(this, src.size(), cap);
00240 InitCopy(src.begin(), src.size(), cap);
00241 }
00242
00255 void InitSubCopy(const ArrayList &src, index_t pos, index_t size,
00256 index_t cap) {
00257 ARRAYLIST__DEBUG_INIT_OK(this, size, cap);
00258 DEBUG_BOUNDS_INCLUSIVE(pos, src.size());
00259 DEBUG_BOUNDS_INCLUSIVE(size, src.size() - pos);
00260 InitCopy(src.begin() + pos, size, capacity);
00261 }
00262 void InitSubCopy(const ArrayList &src, index_t pos, index_t size) {
00263 InitSubCopy(src, pos, size, size);
00264 }
00265
00279 void InitAlias(Elem *ptr, index_t size) {
00280 DEBUG_INIT_OK(this);
00281 ptr_ = ptr;
00282 size_ = size;
00283 cap_ = -1;
00284 }
00285
00296 void InitSubAlias(const ArrayList &src, index_t pos, index_t size) {
00297 DEBUG_INIT_OK(this);
00298 DEBUG_BOUNDS_INCLUSIVE(pos, src.size());
00299 DEBUG_BOUNDS_INCLUSIVE(size, src.size() - pos);
00300 InitAlias(src.begin() + pos, size);
00301 }
00302
00320 void InitSteal(Elem *ptr, index_t size, index_t cap) {
00321 ARRAYLIST__DEBUG_INIT_OK(this, size, cap);
00322 ptr_ = ptr;
00323 size_ = size;
00324 cap_ = cap;
00325 }
00326 void InitSteal(Elem *ptr, index_t size) {
00327 InitSteal(ptr, size, size);
00328 }
00329
00330
00331
00343 Elem *ReleasePtr() {
00344 DEBUG_MODIFY_OK(this);
00345 cap_ = -1;
00346 return ptr_;
00347 }
00348
00361 void Swap(ArrayList *other) {
00362
00363 mem::Swap(this, other);
00364 }
00365
00366
00367
00381 void GrowTo(index_t size) {
00382 DEBUG_MODIFY_OK(this);
00383 DEBUG_ASSERT(size >= size_);
00384 if (unlikely(size > cap_)) {
00385 IncreaseCap_(size + cap_);
00386 }
00387 ot::Construct(ptr_ + size_, size - size_);
00388 size_ = size;
00389 }
00390
00403 void ShrinkTo(index_t size) {
00404 DEBUG_MODIFY_OK(this);
00405 DEBUG_BOUNDS_INCLUSIVE(size, size_);
00406 ot::Destruct(ptr_ + size, size_ - size);
00407 size_ = size;
00408 }
00409
00423 void Resize(index_t size) {
00424 DEBUG_MODIFY_OK(this);
00425 DEBUG_ASSERT(size >= 0);
00426 if (unlikely(size > size_)) {
00427 GrowTo(size);
00428 } else {
00429 ShrinkTo(size);
00430 }
00431 }
00432
00446 void SizeAtLeast(index_t size) {
00447 DEBUG_MODIFY_OK(this);
00448 DEBUG_ASSERT(size >= 0);
00449 if (unlikely(size > size_)) {
00450 GrowTo(size);
00451 }
00452 }
00453
00462 void SizeAtMost(index_t size) {
00463 DEBUG_MODIFY_OK(this);
00464 DEBUG_ASSERT(size >= 0);
00465 if (unlikely(size < size_)) {
00466 ShrinkTo(size);
00467 }
00468 }
00469
00487 void Reserve(index_t size) {
00488 DEBUG_MODIFY_OK(this);
00489 DEBUG_ASSERT(size >= 0);
00490 if (unlikely(size > cap_)) {
00491 ptr_ = mem::Realloc(ptr_, size);
00492 cap_ = size;
00493 }
00494 }
00495
00509 void Trim() {
00510 DEBUG_MODIFY_OK(this);
00511 ptr_ = mem::Realloc(ptr_, size_);
00512 cap_ = size_;
00513 }
00514
00525 void Clear() {
00526 DEBUG_MODIFY_OK(this);
00527 mem::Free(ot::Destruct(ptr_, size_));
00528 Reset_();
00529 }
00530
00531
00532
00554 Elem *PushBackRaw(index_t inc = 1) {
00555 ARRAYLIST__DEBUG_PUSH_BACK_OK(this, inc);
00556
00557 if (unlikely(size_ + inc > cap_)) {
00558 IncreaseCap_(size_ + inc + cap_);
00559 }
00560
00561 Elem *elem = ptr_ + size_;
00562 size_ += inc;
00563 return elem;
00564 }
00565
00582 void PushBack(index_t inc) {
00583 ARRAYLIST__DEBUG_PUSH_BACK_OK(this, inc);
00584 ot::Construct(PushBackRaw(inc), inc);
00585 }
00586 Elem &PushBack() {
00587 DEBUG_MODIFY_OK(this);
00588 return *ot::Construct(PushBackRaw());
00589 }
00590
00603 Elem &PushBackCopy(const Elem &src) {
00604 DEBUG_MODIFY_OK(this);
00605 return *ot::CopyConstruct(PushBackRaw(), &src);
00606 }
00607
00622 void AppendCopy(const Elem *src, index_t size) {
00623 ARRAYLIST__DEBUG_PUSH_BACK_OK(this, size);
00624 ot::CopyConstruct(PushBackRaw(size), src, size);
00625 }
00626
00640 void AppendCopy(const ArrayList &src) {
00641 DEBUG_MODIFY_OK(this);
00642 AppendCopy(src.begin(), src.size());
00643 }
00644
00662 void AppendSteal(ArrayList *src);
00663
00664
00665
00683 void PopBackRaw(index_t dec = 1) {
00684 ARRAYLIST__DEBUG_POP_BACK_OK(this, dec);
00685 size_ -= dec;
00686 }
00687
00699 void PopBack(index_t dec = 1) {
00700 ARRAYLIST__DEBUG_POP_BACK_OK(this, dec);
00701 ot::Destruct(ptr_ + size_ - dec, dec);
00702 PopBackRaw(dec);
00703 }
00704
00719 void PopBackInit(Elem *dest) {
00720 DEBUG_MODIFY_OK(this);
00721 DEBUG_INIT_OK(dest);
00722 DEBUG_ASSERT(size_ > 0);
00723 mem::Copy(dest, ptr_ + size_ - 1);
00724 PopBackRaw();
00725 }
00726
00744 void SegmentInit(index_t size, Elem *dest) {
00745 ARRAYLIST__DEBUG_POP_BACK_OK(this, size);
00746 mem::Copy(dest, ptr_ + size_ - size, size);
00747 PopBackRaw(size);
00748 }
00749
00759 void SegmentInit(index_t size, ArrayList *dest);
00760
00770 void SegmentAppend(index_t size, ArrayList *dest);
00771
00772
00773
00796 Elem *InsertRaw(index_t pos, index_t inc = 1) {
00797 ARRAYLIST__DEBUG_INSERT_OK(this, pos, inc);
00798
00799 if (unlikely(size_ + inc > cap_)) {
00800 IncreaseCap_(size_ + inc + cap_);
00801 }
00802
00803 mem::Move(ptr_ + pos + inc, ptr_ + pos, size_ - pos);
00804 size_ += inc;
00805 return ptr_ + pos;
00806 }
00807
00822 void Insert(index_t pos, index_t inc) {
00823 ARRAYLIST__DEBUG_INSERT_OK(this, pos, inc);
00824 ot::Construct(InsertRaw(pos, inc), inc);
00825 }
00826 Elem &Insert(index_t pos) {
00827 DEBUG_MODIFY_OK(this);
00828 DEBUG_BOUNDS_INCLUSIVE(pos, size_);
00829 return *ot::Construct(InsertRaw(pos));
00830 }
00831
00845 Elem &InsertCopy(index_t pos, const Elem &src) {
00846 DEBUG_MODIFY_OK(this);
00847 DEBUG_BOUNDS_INCLUSIVE(pos, size_);
00848 return *ot::CopyConstruct(InsertRaw(pos), &src);
00849 }
00850
00866 void InfixCopy(index_t pos, const Elem *src, index_t size) {
00867 ARRAYLIST__DEBUG_INSERT_OK(this, pos, size);
00868 ot::CopyConstruct(InsertRaw(pos, size), src, size);
00869 }
00870
00885 void InfixCopy(index_t pos, const ArrayList &src) {
00886 DEBUG_MODIFY_OK(this);
00887 DEBUG_BOUNDS_INCLUSIVE(pos, size_);
00888 InfixCopy(pos, src.begin(), src.size());
00889 }
00890
00910 void InfixSteal(index_t pos, ArrayList *src);
00911
00912
00913
00930 void RemoveRaw(index_t pos, index_t dec = 1) {
00931 ARRAYLIST__DEBUG_REMOVE_OK(this, pos, dec);
00932 mem::Move(ptr_ + pos, ptr_ + pos + dec, size_ - dec - pos);
00933 size_ -= dec;
00934 }
00935
00945 void Remove(index_t pos, index_t dec = 1) {
00946 ARRAYLIST__DEBUG_REMOVE_OK(this, pos, dec);
00947 ot::Destruct(ptr_ + pos, dec);
00948 RemoveRaw(pos, dec);
00949 }
00950
00967 void RemoveInit(index_t pos, Elem *dest) {
00968 DEBUG_MODIFY_OK(this);
00969 DEBUG_INIT_OK(dest);
00970 DEBUG_BOUNDS(pos, size_);
00971 mem::Copy(dest, ptr_ + pos);
00972 RemoveRaw(pos);
00973 }
00974
00993 void ExtractInit(index_t pos, index_t size, Elem *dest) {
00994 ARRAYLIST__DEBUG_REMOVE_OK(this, pos, size);
00995 mem::Copy(dest, ptr_ + pos, size);
00996 RemoveRaw(pos, size);
00997 }
00998
01009 void ExtractInit(index_t pos, index_t size, ArrayList *dest);
01010
01021 void ExtractAppend(index_t pos, index_t size, ArrayList *dest);
01022
01023
01024
01026 index_t size() const {
01027 return size_;
01028 }
01032 index_t length() const {
01033 return this->size();
01034 }
01035
01037 index_t capacity() const {
01038 return cap_;
01039 }
01041 bool empty() const {
01042 return size_ == 0;
01043 }
01044
01046 const Elem &operator[] (index_t i) const {
01047 DEBUG_BOUNDS(i, size_);
01048 return ptr_[i];
01049 }
01050 Elem &operator[] (index_t i) {
01051 DEBUG_BOUNDS(i, size_);
01052 return ptr_[i];
01053 }
01054
01056 const Elem *begin() const {
01057 return ptr_;
01058 }
01059 Elem* begin() {
01060 return ptr_;
01061 }
01062
01064 const Elem *end() const {
01065 return ptr_ + size_;
01066 }
01067 Elem *end() {
01068 return ptr_ + size_;
01069 }
01070
01072 const Elem &front() const {
01073 return *ptr_;
01074 }
01075 Elem &front() {
01076 return *ptr_;
01077 }
01078
01080 const Elem &back() const {
01081 return ptr_[size_ - 1];
01082 }
01083 Elem &back() {
01084 return ptr_[size_ - 1];
01085 }
01086
01088
01089 COMPILER_DEPRECATED_MSG("Renamed InitCopy")
01090 void Copy(const Elem *src, index_t size) {
01091 InitCopy(src, size);
01092 }
01093 COMPILER_DEPRECATED_MSG("Renamed InitSteal")
01094 void Steal(const Elem *src, index_t size) {
01095 InitSteal(src, size);
01096 }
01097 COMPILER_DEPRECATED_MSG("Renamed InitSteal; other will alias")
01098 void Steal(ArrayList *other) {
01099 InitSteal(other);
01100 other->Reset_();
01101 }
01102
01103 COMPILER_DEPRECATED_MSG("Renamed ReleasePtr; will become alias")
01104 Elem *ReleasePointer() {
01105 Elem *retval = ReleasePtr();
01106 Reset_();
01107 return retval;
01108 }
01109 COMPILER_DEPRECATED_MSG("Renamed Renew")
01110 void Destruct() {
01111 Renew();
01112 }
01113
01114 COMPILER_DEPRECATED_MSG("Renamed SizeAtLeast")
01115 void EnsureSizeAtLeast(index_t size) {
01116 SizeAtLeast(size);
01117 }
01118
01119 COMPILER_DEPRECATED_MSG("Renamed PushBack; no longer returns pointer")
01120 Elem *AddBack(index_t inc = 1) {
01121 index_t offset = size_;
01122 PushBack(inc);
01123 return ptr_ + offset;
01124 }
01125 COMPILER_DEPRECATED_MSG("Renamed PushBackRaw")
01126 Elem *AddBackUnconstructed(index_t inc = 1) {
01127 return PushBackRaw(inc);
01128 }
01129 COMPILER_DEPRECATED_MSG("Renamed PushBackCopy")
01130 Elem *AddBackItem(const Elem &elem) {
01131 return &PushBackCopy(elem);
01132 }
01133
01134 COMPILER_DEPRECATED_MSG("Use PopBackInit instead")
01135 Elem *PopBackPtr() {
01136 PopBackRaw();
01137 return end();
01138 }
01139 };
01140
01141 template<typename TElem>
01142 void ArrayList<TElem>::IncreaseCap_(index_t cap) {
01143
01144 cap = (cap + sizeof(long) - 1) & ~(sizeof(long) - 1);
01145 ptr_ = mem::Realloc(ptr_, cap);
01146 cap_ = cap;
01147 }
01148
01149 template<typename TElem>
01150 void ArrayList<TElem>::AppendSteal(ArrayList *src) {
01151 DEBUG_MODIFY_OK(this);
01152 DEBUG_MODIFY_OK(src);
01153
01154 Elem *elem = PushBackRaw(src->size());
01155 mem::Copy(elem, src->begin(), src->size());
01156
01157 mem::Free(src->ptr_);
01158 src->ptr_ = elem;
01159 src->cap_ = -1;
01160 }
01161
01162 template<typename TElem>
01163 void ArrayList<TElem>::SegmentInit(index_t size, ArrayList *dest) {
01164 ARRAYLIST__DEBUG_POP_BACK_OK(this, size);
01165 DEBUG_INIT_OK(dest);
01166 SegmentInit(size, dest->InitRaw(size));
01167 }
01168
01169 template<typename TElem>
01170 void ArrayList<TElem>::SegmentAppend(index_t size, ArrayList *dest) {
01171 ARRAYLIST__DEBUG_POP_BACK_OK(this, size);
01172 DEBUG_MODIFY_OK(dest);
01173 SegmentInit(size, dest->PushBackRaw(size));
01174 }
01175
01176 template<typename TElem>
01177 void ArrayList<TElem>::InfixSteal(index_t pos, ArrayList *src) {
01178 DEBUG_MODIFY_OK(this);
01179 DEBUG_MODIFY_OK(src);
01180 DEBUG_BOUNDS_INCLUSIVE(pos, size_);
01181
01182 Elem *elem = InsertRaw(pos, src->size());
01183 mem::Copy(elem, src->begin(), src->size());
01184
01185 mem::Free(src->ptr_);
01186 src->ptr_ = elem;
01187 src->cap_ = -1;
01188 }
01189
01190 template<typename TElem>
01191 void ArrayList<TElem>::ExtractInit(index_t pos, index_t size,
01192 ArrayList *dest) {
01193 ARRAYLIST__DEBUG_REMOVE_OK(this, pos, size);
01194 DEBUG_INIT_OK(dest);
01195 ExtractInit(pos, size, dest->InitRaw(size));
01196 }
01197
01198 template<typename TElem>
01199 void ArrayList<TElem>::ExtractAppend(index_t pos, index_t size,
01200 ArrayList *dest) {
01201 ARRAYLIST__DEBUG_REMOVE_OK(this, pos, size);
01202 DEBUG_MODIFY_OK(dest);
01203 ExtractInit(pos, size, dest->PushBackRaw(size));
01204 }
01205
01206 #undef ARRAYLIST__DEBUG_REMOVE_OK
01207 #undef ARRAYLIST__DEBUG_INSERT_OK
01208 #undef ARRAYLIST__DEBUG_POP_BACK_OK
01209 #undef ARRAYLIST__DEBUG_PUSH_BACK_OK
01210 #undef ARRAYLIST__DEBUG_INIT_OK
01211
01212 #endif