arraylist.h

/* MLPACK 0.2
 *
 * Copyright (c) 2008, 2009 Alexander Gray,
 *                          Garry Boyer,
 *                          Ryan Riegel,
 *                          Nikolaos Vasiloglou,
 *                          Dongryeol Lee,
 *                          Chip Mappus, 
 *                          Nishant Mehta,
 *                          Hua Ouyang,
 *                          Parikshit Ram,
 *                          Long Tran,
 *                          Wee Chin Wong
 *
 * Copyright (c) 2008, 2009 Georgia Institute of Technology
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA.
 */
#ifndef COL_ARRAYLIST_H
#define COL_ARRAYLIST_H

#include "fastlib/base/base.h"

#define ARRAYLIST__DEBUG_INIT_OK(who, size, cap) \
    DEBUG_INIT_OK(who); \
    DEBUG_ASSERT(size >= 0); \
    DEBUG_ASSERT(size <= cap);

#define ARRAYLIST__DEBUG_PUSH_BACK_OK(who, inc) \
    DEBUG_MODIFY_OK(who); \
    DEBUG_ASSERT(inc >= 0);

#define ARRAYLIST__DEBUG_POP_BACK_OK(who, dec) \
    DEBUG_MODIFY_OK(who); \
    DEBUG_BOUNDS_INCLUSIVE(dec, who->size());

#define ARRAYLIST__DEBUG_INSERT_OK(who, pos, inc) \
    DEBUG_MODIFY_OK(who); \
    DEBUG_BOUNDS_INCLUSIVE(pos, who->size()); \
    DEBUG_ASSERT(inc >= 0);

#define ARRAYLIST__DEBUG_REMOVE_OK(who, pos, dec) \
    DEBUG_MODIFY_OK(who); \
    DEBUG_BOUNDS_INCLUSIVE(pos, who->size()); \
    DEBUG_BOUNDS_INCLUSIVE(dec, who->size() - pos);

template<typename TElem>
class ArrayList {
 public:
  typedef TElem Elem;

 private:
  Elem *ptr_;    // the stored or aliased array
  index_t size_; // number of active objects
  index_t cap_;  // allocated size of the array; -1 if alias

  OBJECT_TRAVERSAL_DEPRECATED_COPIES(ArrayList) {
    // note that only the active objects are copied, etc.
    OT_OBJ(size_);
    OT_ALLOC_EXPERT(ptr_, size_, false,
        i, OT_OBJ(ptr_[i]));
  }
  OT_DEFAULT_CONSTRUCT(ArrayList) {
    Reset_();
    OT__BecomeAlias_();
  }

  OT_TRANSIENTS(ArrayList) {
    OT_OBJ(cap_);
  }
  OT_REFILL_TRANSIENTS(ArrayList) {
    // after copy, array is truncated; also unsets aliasing
    cap_ = size_;
  }

  OT_BECOME_ALIAS(ArrayList) {
    cap_ = -1;
  }
  OT_IS_ALIAS(ArrayList) {
    return cap_ == -1;
  }
  OT_ALIAS_METHODS(ArrayList);

 private:
  /* Allocates more space; unlikely, so not inlined. */
  void IncreaseCap_(index_t cap);

  /* Brings the ArrayList to a default empty state. */
  void Reset_() {
    ptr_ = NULL;
    size_ = 0;
    cap_ = 0;
  }

 public:
  Elem *InitRaw(index_t size, index_t cap) {
    ARRAYLIST__DEBUG_INIT_OK(this, size, cap);
    ptr_ = mem::Alloc<Elem>(size);
    size_ = size;
    cap_ = cap;
    return ptr_;
  }
  Elem *InitRaw(index_t size) {
    return InitRaw(size, size);
  }

  void Init() {
    DEBUG_INIT_OK(this);
    Reset_();
  }

  void Init(index_t size, index_t cap) {
    ARRAYLIST__DEBUG_INIT_OK(this, size, cap);
    ot::Construct(InitRaw(size, cap), size);
  }
  void Init(index_t size) {
    Init(size, size);
  }

  void InitRepeat(const Elem &elem, index_t size, index_t cap) {
    ARRAYLIST__DEBUG_INIT_OK(this, size, cap);
    ot::RepeatConstruct(InitRaw(size, cap), elem, size);
  }
  void InitRepeat(const Elem &elem, index_t size) {
    InitRepeat(elem, size, size);
  }

  void InitCopy(const Elem *src, index_t size, index_t cap) {
    ARRAYLIST__DEBUG_INIT_OK(this, size, cap);
    ot::CopyConstruct(InitRaw(size, cap), src, size);
  }
  void InitCopy(const Elem *src, index_t size) {
    InitCopy(src, size, size);
  }

  void InitCopy(const ArrayList &src, index_t cap) {
    ARRAYLIST__DEBUG_INIT_OK(this, src.size(), cap);
    InitCopy(src.begin(), src.size(), cap);
  }

  void InitSubCopy(const ArrayList &src, index_t pos, index_t size,
                   index_t cap) {
    ARRAYLIST__DEBUG_INIT_OK(this, size, cap);
    DEBUG_BOUNDS_INCLUSIVE(pos, src.size());
    DEBUG_BOUNDS_INCLUSIVE(size, src.size() - pos);
    InitCopy(src.begin() + pos, size, capacity);
  }
  void InitSubCopy(const ArrayList &src, index_t pos, index_t size) {
    InitSubCopy(src, pos, size, size);
  }

  void InitAlias(Elem *ptr, index_t size) {
    DEBUG_INIT_OK(this);
    ptr_ = ptr;
    size_ = size;
    cap_ = -1;
  }

  void InitSubAlias(const ArrayList &src, index_t pos, index_t size) {
    DEBUG_INIT_OK(this);
    DEBUG_BOUNDS_INCLUSIVE(pos, src.size());
    DEBUG_BOUNDS_INCLUSIVE(size, src.size() - pos);
    InitAlias(src.begin() + pos, size);
  }

  void InitSteal(Elem *ptr, index_t size, index_t cap) {
    ARRAYLIST__DEBUG_INIT_OK(this, size, cap);
    ptr_ = ptr;
    size_ = size;
    cap_ = cap;
  }
  void InitSteal(Elem *ptr, index_t size) {
    InitSteal(ptr, size, size);
  }



  Elem *ReleasePtr() {
    DEBUG_MODIFY_OK(this);
    cap_ = -1;
    return ptr_;
  }

  void Swap(ArrayList *other) {
    // note absense of DEBUG_MODIFY_OK => can swap aliases
    mem::Swap(this, other);
  }



  void GrowTo(index_t size) {
    DEBUG_MODIFY_OK(this);
    DEBUG_ASSERT(size >= size_);
    if (unlikely(size > cap_)) {
      IncreaseCap_(size + cap_);
    }
    ot::Construct(ptr_ + size_, size - size_);
    size_ = size;
  }

  void ShrinkTo(index_t size) {
    DEBUG_MODIFY_OK(this);
    DEBUG_BOUNDS_INCLUSIVE(size, size_);
    ot::Destruct(ptr_ + size, size_ - size);
    size_ = size;
  }

  void Resize(index_t size) {
    DEBUG_MODIFY_OK(this);
    DEBUG_ASSERT(size >= 0);
    if (unlikely(size > size_)) {
      GrowTo(size);
    } else {
      ShrinkTo(size);
    }
  }

  void SizeAtLeast(index_t size) {
    DEBUG_MODIFY_OK(this);
    DEBUG_ASSERT(size >= 0);
    if (unlikely(size > size_)) {
      GrowTo(size);
    }
  }

  void SizeAtMost(index_t size) {
    DEBUG_MODIFY_OK(this);
    DEBUG_ASSERT(size >= 0);
    if (unlikely(size < size_)) {
      ShrinkTo(size);
    }
  }

  void Reserve(index_t size) {
    DEBUG_MODIFY_OK(this);
    DEBUG_ASSERT(size >= 0);
    if (unlikely(size > cap_)) {
      ptr_ = mem::Realloc(ptr_, size);
      cap_ = size;
    }
  }

  void Trim() {
    DEBUG_MODIFY_OK(this);
    ptr_ = mem::Realloc(ptr_, size_);
    cap_ = size_;
  }

  void Clear() {
    DEBUG_MODIFY_OK(this);
    mem::Free(ot::Destruct(ptr_, size_));
    Reset_();
  }



  Elem *PushBackRaw(index_t inc = 1) {
    ARRAYLIST__DEBUG_PUSH_BACK_OK(this, inc);

    if (unlikely(size_ + inc > cap_)) {
      IncreaseCap_(size_ + inc + cap_);
    }

    Elem *elem = ptr_ + size_;
    size_ += inc;
    return elem;
  }

  void PushBack(index_t inc) {
    ARRAYLIST__DEBUG_PUSH_BACK_OK(this, inc);
    ot::Construct(PushBackRaw(inc), inc);
  }
  Elem &PushBack() {
    DEBUG_MODIFY_OK(this);
    return *ot::Construct(PushBackRaw());
  }

  Elem &PushBackCopy(const Elem &src) {
    DEBUG_MODIFY_OK(this);
    return *ot::CopyConstruct(PushBackRaw(), &src);
  }

  void AppendCopy(const Elem *src, index_t size) {
    ARRAYLIST__DEBUG_PUSH_BACK_OK(this, size);
    ot::CopyConstruct(PushBackRaw(size), src, size);
  }

  void AppendCopy(const ArrayList &src) {
    DEBUG_MODIFY_OK(this);
    AppendCopy(src.begin(), src.size());
  }

  void AppendSteal(ArrayList *src);



  void PopBackRaw(index_t dec = 1) {
    ARRAYLIST__DEBUG_POP_BACK_OK(this, dec);
    size_ -= dec;
  }

  void PopBack(index_t dec = 1) {
    ARRAYLIST__DEBUG_POP_BACK_OK(this, dec);
    ot::Destruct(ptr_ + size_ - dec, dec);
    PopBackRaw(dec);
  }

  void PopBackInit(Elem *dest) {
    DEBUG_MODIFY_OK(this);
    DEBUG_INIT_OK(dest);
    DEBUG_ASSERT(size_ > 0);
    mem::Copy(dest, ptr_ + size_ - 1);
    PopBackRaw();
  }

  void SegmentInit(index_t size, Elem *dest) {
    ARRAYLIST__DEBUG_POP_BACK_OK(this, size);
    mem::Copy(dest, ptr_ + size_ - size, size);
    PopBackRaw(size);
  }

  void SegmentInit(index_t size, ArrayList *dest);

  void SegmentAppend(index_t size, ArrayList *dest);



  Elem *InsertRaw(index_t pos, index_t inc = 1) {
    ARRAYLIST__DEBUG_INSERT_OK(this, pos, inc);

    if (unlikely(size_ + inc > cap_)) {
      IncreaseCap_(size_ + inc + cap_);
    }

    mem::Move(ptr_ + pos + inc, ptr_ + pos, size_ - pos);
    size_ += inc;
    return ptr_ + pos;
  }

  void Insert(index_t pos, index_t inc) {
    ARRAYLIST__DEBUG_INSERT_OK(this, pos, inc);
    ot::Construct(InsertRaw(pos, inc), inc);
  }
  Elem &Insert(index_t pos) {
    DEBUG_MODIFY_OK(this);
    DEBUG_BOUNDS_INCLUSIVE(pos, size_);
    return *ot::Construct(InsertRaw(pos));
  }

  Elem &InsertCopy(index_t pos, const Elem &src) {
    DEBUG_MODIFY_OK(this);
    DEBUG_BOUNDS_INCLUSIVE(pos, size_);
    return *ot::CopyConstruct(InsertRaw(pos), &src);
  }

  void InfixCopy(index_t pos, const Elem *src, index_t size) {
    ARRAYLIST__DEBUG_INSERT_OK(this, pos, size);
    ot::CopyConstruct(InsertRaw(pos, size), src, size);
  }

  void InfixCopy(index_t pos, const ArrayList &src) {
    DEBUG_MODIFY_OK(this);
    DEBUG_BOUNDS_INCLUSIVE(pos, size_);
    InfixCopy(pos, src.begin(), src.size());
  }

  void InfixSteal(index_t pos, ArrayList *src);



  void RemoveRaw(index_t pos, index_t dec = 1) {
    ARRAYLIST__DEBUG_REMOVE_OK(this, pos, dec);
    mem::Move(ptr_ + pos, ptr_ + pos + dec, size_ - dec - pos);
    size_ -= dec;
  }

  void Remove(index_t pos, index_t dec = 1) {
    ARRAYLIST__DEBUG_REMOVE_OK(this, pos, dec);
    ot::Destruct(ptr_ + pos, dec);
    RemoveRaw(pos, dec);
  }

  void RemoveInit(index_t pos, Elem *dest) {
    DEBUG_MODIFY_OK(this);
    DEBUG_INIT_OK(dest);
    DEBUG_BOUNDS(pos, size_);
    mem::Copy(dest, ptr_ + pos);
    RemoveRaw(pos);
  }

  void ExtractInit(index_t pos, index_t size, Elem *dest) {
    ARRAYLIST__DEBUG_REMOVE_OK(this, pos, size);
    mem::Copy(dest, ptr_ + pos, size);
    RemoveRaw(pos, size);
  }

  void ExtractInit(index_t pos, index_t size, ArrayList *dest);

  void ExtractAppend(index_t pos, index_t size, ArrayList *dest);



  index_t size() const {
    return size_;
  }
  index_t length() const {
    return this->size();
  }

  index_t capacity() const {
    return cap_;
  }
  bool empty() const {
    return size_ == 0;
  }

  const Elem &operator[] (index_t i) const {
    DEBUG_BOUNDS(i, size_);
    return ptr_[i];
  }
  Elem &operator[] (index_t i) {
    DEBUG_BOUNDS(i, size_);
    return ptr_[i];
  }

  const Elem *begin() const {
    return ptr_;
  }
  Elem* begin() {
    return ptr_;
  }

  const Elem *end() const {
    return ptr_ + size_;
  }
  Elem *end() {
    return ptr_ + size_;
  }

  const Elem &front() const {
    return *ptr_;
  }
  Elem &front() {
    return *ptr_;
  }

  const Elem &back() const {
    return ptr_[size_ - 1];
  }
  Elem &back() {
    return ptr_[size_ - 1];
  }


  COMPILER_DEPRECATED_MSG("Renamed InitCopy")
  void Copy(const Elem *src, index_t size) {
    InitCopy(src, size);
  }
  COMPILER_DEPRECATED_MSG("Renamed InitSteal")
  void Steal(const Elem *src, index_t size) {
    InitSteal(src, size);
  }
  COMPILER_DEPRECATED_MSG("Renamed InitSteal; other will alias")
  void Steal(ArrayList *other) {
    InitSteal(other);
    other->Reset_();
  }

  COMPILER_DEPRECATED_MSG("Renamed ReleasePtr; will become alias")
  Elem *ReleasePointer() {
    Elem *retval = ReleasePtr();
    Reset_();
    return retval;
  }
  COMPILER_DEPRECATED_MSG("Renamed Renew")
  void Destruct() {
    Renew();
  }

  COMPILER_DEPRECATED_MSG("Renamed SizeAtLeast")
  void EnsureSizeAtLeast(index_t size) {
    SizeAtLeast(size);
  }

  COMPILER_DEPRECATED_MSG("Renamed PushBack; no longer returns pointer")
  Elem *AddBack(index_t inc = 1) {
    index_t offset = size_;
    PushBack(inc);
    return ptr_ + offset;
  }
  COMPILER_DEPRECATED_MSG("Renamed PushBackRaw")
  Elem *AddBackUnconstructed(index_t inc = 1) {
    return PushBackRaw(inc);
  }
  COMPILER_DEPRECATED_MSG("Renamed PushBackCopy")
  Elem *AddBackItem(const Elem &elem) {
    return &PushBackCopy(elem);
  }

  COMPILER_DEPRECATED_MSG("Use PopBackInit instead")
  Elem *PopBackPtr() {
    PopBackRaw();
    return end();
  }
};

template<typename TElem>
void ArrayList<TElem>::IncreaseCap_(index_t cap) {
  // round up capcity for possible paging performance
  cap = (cap + sizeof(long) - 1) & ~(sizeof(long) - 1);
  ptr_ = mem::Realloc(ptr_, cap);
  cap_ = cap;
}

template<typename TElem>
void ArrayList<TElem>::AppendSteal(ArrayList *src) {
  DEBUG_MODIFY_OK(this);
  DEBUG_MODIFY_OK(src);

  Elem *elem = PushBackRaw(src->size());
  mem::Copy(elem, src->begin(), src->size());

  mem::Free(src->ptr_);
  src->ptr_ = elem;
  src->cap_ = -1;
}

template<typename TElem>
void ArrayList<TElem>::SegmentInit(index_t size, ArrayList *dest) {
  ARRAYLIST__DEBUG_POP_BACK_OK(this, size);
  DEBUG_INIT_OK(dest);
  SegmentInit(size, dest->InitRaw(size));
}

template<typename TElem>
void ArrayList<TElem>::SegmentAppend(index_t size, ArrayList *dest) {
  ARRAYLIST__DEBUG_POP_BACK_OK(this, size);
  DEBUG_MODIFY_OK(dest);
  SegmentInit(size, dest->PushBackRaw(size));
}

template<typename TElem>
void ArrayList<TElem>::InfixSteal(index_t pos, ArrayList *src) {
  DEBUG_MODIFY_OK(this);
  DEBUG_MODIFY_OK(src);
  DEBUG_BOUNDS_INCLUSIVE(pos, size_);

  Elem *elem = InsertRaw(pos, src->size());
  mem::Copy(elem, src->begin(), src->size());

  mem::Free(src->ptr_);
  src->ptr_ = elem;
  src->cap_ = -1;
}

template<typename TElem>
void ArrayList<TElem>::ExtractInit(index_t pos, index_t size,
                                   ArrayList *dest) {
  ARRAYLIST__DEBUG_REMOVE_OK(this, pos, size);
  DEBUG_INIT_OK(dest);
  ExtractInit(pos, size, dest->InitRaw(size));
}

template<typename TElem>
void ArrayList<TElem>::ExtractAppend(index_t pos, index_t size,
                                     ArrayList *dest) {
  ARRAYLIST__DEBUG_REMOVE_OK(this, pos, size);
  DEBUG_MODIFY_OK(dest);
  ExtractInit(pos, size, dest->PushBackRaw(size));
}

#undef ARRAYLIST__DEBUG_REMOVE_OK
#undef ARRAYLIST__DEBUG_INSERT_OK
#undef ARRAYLIST__DEBUG_POP_BACK_OK
#undef ARRAYLIST__DEBUG_PUSH_BACK_OK
#undef ARRAYLIST__DEBUG_INIT_OK

#endif /* COL_ARRAYLIST_H */