dcdd144598 2011-02-23 kinaba: #ifndef _KILIB_KTL_ARRAY_H_ dcdd144598 2011-02-23 kinaba: #define _KILIB_KTL_ARRAY_H_ dcdd144598 2011-02-23 kinaba: #include "types.h" dcdd144598 2011-02-23 kinaba: #include "memory.h" dcdd144598 2011-02-23 kinaba: #ifndef __ccdoc__ dcdd144598 2011-02-23 kinaba: namespace ki { dcdd144598 2011-02-23 kinaba: #endif dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //========================================================================= dcdd144598 2011-02-23 kinaba: //@{ @pkg ki.KTL //@} dcdd144598 2011-02-23 kinaba: //@{ dcdd144598 2011-02-23 kinaba: // 基本型専用の可変長配列 dcdd144598 2011-02-23 kinaba: // dcdd144598 2011-02-23 kinaba: // 非常に簡素な作りです。アクセスは好きなところへ自由に可能ですが、 dcdd144598 2011-02-23 kinaba: // 要素の追加・削除は末尾に対してのみ。ビット毎のコピーだとか、 dcdd144598 2011-02-23 kinaba: // 色々エキセントリックな作業をしてますので、そういうことをして良い dcdd144598 2011-02-23 kinaba: // 型以外には使わないでください。 dcdd144598 2011-02-23 kinaba: //@} dcdd144598 2011-02-23 kinaba: //========================================================================= dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: template <typename T> dcdd144598 2011-02-23 kinaba: class storage : public Object dcdd144598 2011-02-23 kinaba: { dcdd144598 2011-02-23 kinaba: public: dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //@{ dcdd144598 2011-02-23 kinaba: // コンストラクタ dcdd144598 2011-02-23 kinaba: // dcdd144598 2011-02-23 kinaba: // @param alloc_size dcdd144598 2011-02-23 kinaba: // 最初に確保する"メモリの"サイズ。 dcdd144598 2011-02-23 kinaba: // "配列の"サイズではないことに注意。 dcdd144598 2011-02-23 kinaba: //@} dcdd144598 2011-02-23 kinaba: explicit storage( ulong allocSize=20 ) dcdd144598 2011-02-23 kinaba: : alen_( Max( allocSize, 1UL ) ) dcdd144598 2011-02-23 kinaba: , len_ ( 0 ) dcdd144598 2011-02-23 kinaba: , buf_ ( static_cast<T*>(mem().Alloc(alen_*sizeof(T))) ) dcdd144598 2011-02-23 kinaba: {} dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: ~storage() dcdd144598 2011-02-23 kinaba: { mem().DeAlloc( buf_, alen_*sizeof(T) ); } dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //@{ 末尾に要素を追加 //@} dcdd144598 2011-02-23 kinaba: void Add( const T& obj ) dcdd144598 2011-02-23 kinaba: { dcdd144598 2011-02-23 kinaba: if( len_ >= alen_ ) dcdd144598 2011-02-23 kinaba: ReAllocate( alen_<<2 ); dcdd144598 2011-02-23 kinaba: buf_[ len_++ ] = obj; dcdd144598 2011-02-23 kinaba: } dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //@{ dcdd144598 2011-02-23 kinaba: // 配列サイズを強制変更 dcdd144598 2011-02-23 kinaba: // dcdd144598 2011-02-23 kinaba: // 縮小/拡大のどちらも可能。コンストラクタと違い、 dcdd144598 2011-02-23 kinaba: // 指定した値に基づき最大indexが変化します。 dcdd144598 2011-02-23 kinaba: // @param new_size 新しいサイズ。 dcdd144598 2011-02-23 kinaba: //@} dcdd144598 2011-02-23 kinaba: void ForceSize( ulong newSize ) dcdd144598 2011-02-23 kinaba: { dcdd144598 2011-02-23 kinaba: if( newSize > alen_ ) dcdd144598 2011-02-23 kinaba: ReAllocate( newSize ); dcdd144598 2011-02-23 kinaba: len_ = newSize; dcdd144598 2011-02-23 kinaba: } dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: public: dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //@{ 要素数 //@} dcdd144598 2011-02-23 kinaba: ulong size() const dcdd144598 2011-02-23 kinaba: { return len_; } dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //@{ 要素取得 //@} dcdd144598 2011-02-23 kinaba: T& operator[]( size_t i ) dcdd144598 2011-02-23 kinaba: { return buf_[i]; } dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //@{ 要素取得(const) //@} dcdd144598 2011-02-23 kinaba: const T& operator[]( size_t i ) const dcdd144598 2011-02-23 kinaba: { return buf_[i]; } dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //@{ 配列先頭のポインタを返す //@} dcdd144598 2011-02-23 kinaba: const T* head() const dcdd144598 2011-02-23 kinaba: { return buf_; } dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: private: dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: void ReAllocate( ulong siz ) dcdd144598 2011-02-23 kinaba: { dcdd144598 2011-02-23 kinaba: ulong p = alen_*sizeof(T); dcdd144598 2011-02-23 kinaba: T* newbuf = static_cast<T*> dcdd144598 2011-02-23 kinaba: (mem().Alloc( (alen_=siz)*sizeof(T) )); dcdd144598 2011-02-23 kinaba: memmove( newbuf, buf_, len_*sizeof(T) ); dcdd144598 2011-02-23 kinaba: mem().DeAlloc( buf_, p ); dcdd144598 2011-02-23 kinaba: buf_ = newbuf; dcdd144598 2011-02-23 kinaba: } dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: private: dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: ulong alen_; dcdd144598 2011-02-23 kinaba: ulong len_; dcdd144598 2011-02-23 kinaba: T* buf_; dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: private: dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: NOCOPY(storage<T>); dcdd144598 2011-02-23 kinaba: }; dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //========================================================================= dcdd144598 2011-02-23 kinaba: //@{ dcdd144598 2011-02-23 kinaba: // オブジェクト型にも使える単方向リスト dcdd144598 2011-02-23 kinaba: // dcdd144598 2011-02-23 kinaba: // ほとんど何も出来ません。出来るのは末尾への追加と、独自の dcdd144598 2011-02-23 kinaba: // iteratorによるシーケンシャルなアクセスのみ。 dcdd144598 2011-02-23 kinaba: //@} dcdd144598 2011-02-23 kinaba: //========================================================================= dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: template <class T> dcdd144598 2011-02-23 kinaba: class olist : public Object dcdd144598 2011-02-23 kinaba: { dcdd144598 2011-02-23 kinaba: private: dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: struct Node { dcdd144598 2011-02-23 kinaba: Node( const T& obj ) dcdd144598 2011-02-23 kinaba: : obj_ ( obj ), next_( NULL ) {} dcdd144598 2011-02-23 kinaba: ~Node() dcdd144598 2011-02-23 kinaba: { delete next_; } dcdd144598 2011-02-23 kinaba: Node* Add( Node* pN ) dcdd144598 2011-02-23 kinaba: { return next_==NULL ? next_=pN : next_->Add(pN); } dcdd144598 2011-02-23 kinaba: T obj_; dcdd144598 2011-02-23 kinaba: Node* next_; dcdd144598 2011-02-23 kinaba: }; dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: public: dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: struct iterator { dcdd144598 2011-02-23 kinaba: iterator( Node* p=NULL ) : ptr_(p) {} dcdd144598 2011-02-23 kinaba: T& operator*() { return ptr_->obj_; } dcdd144598 2011-02-23 kinaba: T* operator->() const { return &ptr_->obj_; } dcdd144598 2011-02-23 kinaba: bool operator==( const iterator& i ) { return i.ptr_==ptr_; } dcdd144598 2011-02-23 kinaba: bool operator!=( const iterator& i ) { return i.ptr_!=ptr_; } dcdd144598 2011-02-23 kinaba: iterator& operator++() { ptr_=ptr_->next_; return *this; } dcdd144598 2011-02-23 kinaba: private: dcdd144598 2011-02-23 kinaba: Node* ptr_; dcdd144598 2011-02-23 kinaba: }; dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: public: dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //@{ コンストラクタ //@} dcdd144598 2011-02-23 kinaba: olist() dcdd144598 2011-02-23 kinaba: : top_( NULL ) {} dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //@{ デストラクタ //@} dcdd144598 2011-02-23 kinaba: ~olist() dcdd144598 2011-02-23 kinaba: { empty(); } dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //@{ 空にする //@} dcdd144598 2011-02-23 kinaba: void empty() dcdd144598 2011-02-23 kinaba: { delete top_; top_ = NULL; } dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //@{ 先頭 //@} dcdd144598 2011-02-23 kinaba: iterator begin() dcdd144598 2011-02-23 kinaba: { return iterator(top_); } dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //@{ 末尾 //@} dcdd144598 2011-02-23 kinaba: iterator end() dcdd144598 2011-02-23 kinaba: { return iterator(); } dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //@{ 末尾に要素を追加 //@} dcdd144598 2011-02-23 kinaba: void Add( const T& obj ) dcdd144598 2011-02-23 kinaba: { dcdd144598 2011-02-23 kinaba: Node* pN = new Node( obj ); dcdd144598 2011-02-23 kinaba: (top_ == NULL) ? top_=pN : top_->Add( pN ); dcdd144598 2011-02-23 kinaba: } dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //@{ 指定要素を削除 //@} dcdd144598 2011-02-23 kinaba: void Del( iterator d ) dcdd144598 2011-02-23 kinaba: { dcdd144598 2011-02-23 kinaba: if( d != end() ) dcdd144598 2011-02-23 kinaba: { dcdd144598 2011-02-23 kinaba: Node *p=top_, *q=NULL; dcdd144598 2011-02-23 kinaba: for( ; p!=NULL; q=p,p=p->next_ ) dcdd144598 2011-02-23 kinaba: if( &p->obj_ == &*d ) dcdd144598 2011-02-23 kinaba: break; dcdd144598 2011-02-23 kinaba: if( q != NULL ) dcdd144598 2011-02-23 kinaba: q->next_ = p->next_; dcdd144598 2011-02-23 kinaba: else dcdd144598 2011-02-23 kinaba: top_ = p->next_; dcdd144598 2011-02-23 kinaba: p->next_ = NULL; dcdd144598 2011-02-23 kinaba: delete p; dcdd144598 2011-02-23 kinaba: } dcdd144598 2011-02-23 kinaba: } dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //@{ 指定要素以降全てを削除 //@} dcdd144598 2011-02-23 kinaba: void DelAfter( iterator d ) dcdd144598 2011-02-23 kinaba: { dcdd144598 2011-02-23 kinaba: if( d != end() ) dcdd144598 2011-02-23 kinaba: if( d == begin() ) dcdd144598 2011-02-23 kinaba: { dcdd144598 2011-02-23 kinaba: empty(); dcdd144598 2011-02-23 kinaba: } dcdd144598 2011-02-23 kinaba: else dcdd144598 2011-02-23 kinaba: { dcdd144598 2011-02-23 kinaba: Node *p=top_, *q=NULL; dcdd144598 2011-02-23 kinaba: for( ; p!=NULL; q=p,p=p->next_ ) dcdd144598 2011-02-23 kinaba: if( &p->obj_ == &*d ) dcdd144598 2011-02-23 kinaba: break; dcdd144598 2011-02-23 kinaba: delete p; dcdd144598 2011-02-23 kinaba: q->next_ = NULL; dcdd144598 2011-02-23 kinaba: } dcdd144598 2011-02-23 kinaba: } dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: private: dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: Node* top_; dcdd144598 2011-02-23 kinaba: NOCOPY(olist<T>); dcdd144598 2011-02-23 kinaba: }; dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: //========================================================================= dcdd144598 2011-02-23 kinaba: dcdd144598 2011-02-23 kinaba: } // namespace ki dcdd144598 2011-02-23 kinaba: #endif // _KILIB_KTL_ARRAY_H_