arraylist.h

00001 /* MLPACK 0.2
00002  *
00003  * Copyright (c) 2008, 2009 Alexander Gray,
00004  *                          Garry Boyer,
00005  *                          Ryan Riegel,
00006  *                          Nikolaos Vasiloglou,
00007  *                          Dongryeol Lee,
00008  *                          Chip Mappus, 
00009  *                          Nishant Mehta,
00010  *                          Hua Ouyang,
00011  *                          Parikshit Ram,
00012  *                          Long Tran,
00013  *                          Wee Chin Wong
00014  *
00015  * Copyright (c) 2008, 2009 Georgia Institute of Technology
00016  *
00017  * This program is free software; you can redistribute it and/or
00018  * modify it under the terms of the GNU General Public License as
00019  * published by the Free Software Foundation; either version 2 of the
00020  * License, or (at your option) any later version.
00021  *
00022  * This program is distributed in the hope that it will be useful, but
00023  * WITHOUT ANY WARRANTY; without even the implied warranty of
00024  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00025  * General Public License for more details.
00026  *
00027  * You should have received a copy of the GNU General Public License
00028  * along with this program; if not, write to the Free Software
00029  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
00030  * 02110-1301, USA.
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_;    // the stored or aliased array
00091   index_t size_; // number of active objects
00092   index_t cap_;  // allocated size of the array; -1 if alias
00093 
00094   OBJECT_TRAVERSAL_DEPRECATED_COPIES(ArrayList) {
00095     // note that only the active objects are copied, etc.
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     // after copy, array is truncated; also unsets aliasing
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   /* Allocates more space; unlikely, so not inlined. */
00123   void IncreaseCap_(index_t cap);
00124 
00125   /* Brings the ArrayList to a default empty state. */
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     // note absense of DEBUG_MODIFY_OK => can swap aliases
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   // round up capcity for possible paging performance
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 /* COL_ARRAYLIST_H */
Generated on Mon Jan 24 12:04:37 2011 for FASTlib by  doxygen 1.6.3