dcdd144598 2011-02-23        kinaba: #ifndef _KILIB_KTL_GAP_H_
dcdd144598 2011-02-23        kinaba: #define _KILIB_KTL_GAP_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: //	( 下の図で言うと、gap_startへの挿入/削除にはデータの移動が必要ない )
dcdd144598 2011-02-23        kinaba: //	<pre>
dcdd144598 2011-02-23        kinaba: //@@  D  <--0
dcdd144598 2011-02-23        kinaba: //@@  D
dcdd144598 2011-02-23        kinaba: //@@  |  <--gap_start
dcdd144598 2011-02-23        kinaba: //@@  |
dcdd144598 2011-02-23        kinaba: //@@  D  <--gap_end
dcdd144598 2011-02-23        kinaba: //@@  D
dcdd144598 2011-02-23        kinaba: //@@     <--array_end
dcdd144598 2011-02-23        kinaba: //	</pre>
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<class T>
dcdd144598 2011-02-23        kinaba: class gapbuf : 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: 	//	@param alloc_size
dcdd144598 2011-02-23        kinaba: 	//		最初に確保する"メモリの"サイズ。
dcdd144598 2011-02-23        kinaba: 	//		"配列の"サイズではないことに注意。
dcdd144598 2011-02-23        kinaba: 	//@}
dcdd144598 2011-02-23        kinaba: 	explicit gapbuf( ulong alloc_size=40 )
dcdd144598 2011-02-23        kinaba: 		: alen_( Max(alloc_size, 10UL) )
dcdd144598 2011-02-23        kinaba: 		, gs_  ( 0 )
dcdd144598 2011-02-23        kinaba: 		, ge_  ( alen_ )
dcdd144598 2011-02-23        kinaba: 		, buf_ ( new T[alen_] )
dcdd144598 2011-02-23        kinaba: 		{}
dcdd144598 2011-02-23        kinaba: 	~gapbuf()
dcdd144598 2011-02-23        kinaba: 		{ delete [] buf_; }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	//@{ 要素挿入 //@}
dcdd144598 2011-02-23        kinaba: 	void InsertAt( ulong i, const T& x )
dcdd144598 2011-02-23        kinaba: 		{
dcdd144598 2011-02-23        kinaba: 			MakeGapAt( i );
dcdd144598 2011-02-23        kinaba: 			buf_[gs_++] = x;
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 			if( gs_==ge_ )
dcdd144598 2011-02-23        kinaba: 				Reallocate( alen_<<1 );
dcdd144598 2011-02-23        kinaba: 		}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	//@{ 要素挿入(複数) //@}
dcdd144598 2011-02-23        kinaba: 	void InsertAt( ulong i, const T* x, ulong len )
dcdd144598 2011-02-23        kinaba: 		{
dcdd144598 2011-02-23        kinaba: 			MakeGapAt( size() );
dcdd144598 2011-02-23        kinaba: 			MakeGapAt( i );
dcdd144598 2011-02-23        kinaba: 			if( ge_-gs_ <= len )
dcdd144598 2011-02-23        kinaba: 				Reallocate( Max(alen_+len+1, alen_<<1) );
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 			memmove( buf_+gs_, x, len*sizeof(T) );
dcdd144598 2011-02-23        kinaba: 			gs_ += len;
dcdd144598 2011-02-23        kinaba: 		}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	//@{ 末尾に要素を追加 //@}
dcdd144598 2011-02-23        kinaba: 	void Add( const T& x )
dcdd144598 2011-02-23        kinaba: 		{ InsertAt( size(), x ); }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	//@{ 末尾に要素を追加(複数) //@}
dcdd144598 2011-02-23        kinaba: 	void Add( const T* x, ulong len )
dcdd144598 2011-02-23        kinaba: 		{ InsertAt( size(), x, len ); }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	//@{ 要素削除 //@}
dcdd144598 2011-02-23        kinaba: 	void RemoveAt( ulong i, ulong len=1 )
dcdd144598 2011-02-23        kinaba: 		{
dcdd144598 2011-02-23        kinaba: 			if( i <= gs_ && gs_ <= i+len )
dcdd144598 2011-02-23        kinaba: 			{
dcdd144598 2011-02-23        kinaba: 				// この場合はメモリ移動の必要がない
dcdd144598 2011-02-23        kinaba: 				// まず前半を削除
dcdd144598 2011-02-23        kinaba: 				len -= (gs_-i);
dcdd144598 2011-02-23        kinaba: 				gs_ = i;
dcdd144598 2011-02-23        kinaba: 			}
dcdd144598 2011-02-23        kinaba: 			else
dcdd144598 2011-02-23        kinaba: 			{
dcdd144598 2011-02-23        kinaba: 				MakeGapAt( i );
dcdd144598 2011-02-23        kinaba: 			}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 			// 後半を削除
dcdd144598 2011-02-23        kinaba: 			ge_ += len;
dcdd144598 2011-02-23        kinaba: 		}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	//@{ 要素削除(全部) //@}
dcdd144598 2011-02-23        kinaba: 	void RemoveAll()
dcdd144598 2011-02-23        kinaba: 		{ RemoveAt( 0, size() ); }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	//@{ 要素削除(指定index以降全部) //@}
dcdd144598 2011-02-23        kinaba: 	void RemoveToTail( ulong i )
dcdd144598 2011-02-23        kinaba: 		{ RemoveAt( i, size()-i ); }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	//@{ 要素コピー(指定index以降全部) //@}
dcdd144598 2011-02-23        kinaba: 	ulong CopyToTail( ulong i, T* x )
dcdd144598 2011-02-23        kinaba: 		{ return CopyAt( i, size()-i, x ); }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	//@{ 要素コピー //@}
dcdd144598 2011-02-23        kinaba: 	ulong CopyAt( ulong i, ulong len, T* x )
dcdd144598 2011-02-23        kinaba: 		{
dcdd144598 2011-02-23        kinaba: 			ulong copyed=0;
dcdd144598 2011-02-23        kinaba: 			if( i < gs_ )
dcdd144598 2011-02-23        kinaba: 			{
dcdd144598 2011-02-23        kinaba: 				// 前半
dcdd144598 2011-02-23        kinaba: 				copyed += Min( len, gs_-i );
dcdd144598 2011-02-23        kinaba: 				memmove( x, buf_+i, copyed*sizeof(T) );
dcdd144598 2011-02-23        kinaba: 				x   += copyed;
dcdd144598 2011-02-23        kinaba: 				len -= copyed;
dcdd144598 2011-02-23        kinaba: 				i   += copyed;
dcdd144598 2011-02-23        kinaba: 			}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 			// 後半
dcdd144598 2011-02-23        kinaba: 			memmove( x, buf_+(i-gs_)+ge_, len*sizeof(T) );
dcdd144598 2011-02-23        kinaba: 			return copyed + len;
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 alen_ - (ge_-gs_); }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	//@{ 要素取得 //@}
dcdd144598 2011-02-23        kinaba: 	T& operator[]( ulong i )
dcdd144598 2011-02-23        kinaba: 		{ return buf_[ ( i<gs_ ) ? i : i+(ge_-gs_) ]; }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	//@{ 要素取得(const) //@}
dcdd144598 2011-02-23        kinaba: 	const T& operator[]( ulong i ) const
dcdd144598 2011-02-23        kinaba: 		{ return buf_[ ( i<gs_ ) ? i : i+(ge_-gs_) ]; }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: protected:
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	ulong alen_;
dcdd144598 2011-02-23        kinaba: 	ulong gs_;
dcdd144598 2011-02-23        kinaba: 	ulong ge_;
dcdd144598 2011-02-23        kinaba: 	T*    buf_;
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: protected:
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	void MakeGapAt( ulong i )
dcdd144598 2011-02-23        kinaba: 		{
dcdd144598 2011-02-23        kinaba: 			if( i<gs_ )
dcdd144598 2011-02-23        kinaba: 			{
dcdd144598 2011-02-23        kinaba: 				ge_ -= (gs_-i);
dcdd144598 2011-02-23        kinaba: 				memmove( buf_+ge_, buf_+i, (gs_-i)*sizeof(T) );
dcdd144598 2011-02-23        kinaba: 			}
dcdd144598 2011-02-23        kinaba: 			else if( i>gs_ )
dcdd144598 2011-02-23        kinaba: 			{
dcdd144598 2011-02-23        kinaba: 				int j = i+(ge_-gs_);
dcdd144598 2011-02-23        kinaba: 				memmove( buf_+gs_, buf_+ge_, (j-ge_)*sizeof(T) );
dcdd144598 2011-02-23        kinaba: 				ge_ = j;
dcdd144598 2011-02-23        kinaba: 			}
dcdd144598 2011-02-23        kinaba: 			gs_ = i;
dcdd144598 2011-02-23        kinaba: 		}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	void Reallocate( ulong newalen )
dcdd144598 2011-02-23        kinaba: 		{
dcdd144598 2011-02-23        kinaba: 			T *tmp = new T[newalen], *old=buf_;
dcdd144598 2011-02-23        kinaba: 			const ulong tail = alen_-ge_;
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 			memmove( tmp, old, gs_*sizeof(T) );
dcdd144598 2011-02-23        kinaba: 			memmove( tmp+newalen-tail, old+ge_, tail*sizeof(T) );
dcdd144598 2011-02-23        kinaba: 			delete [] old;
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 			buf_  = tmp;
dcdd144598 2011-02-23        kinaba: 			ge_   = newalen-tail;
dcdd144598 2011-02-23        kinaba: 			alen_ = newalen;
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: 	NOCOPY(gapbuf<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: //	gapbuf + smartptr のふり
dcdd144598 2011-02-23        kinaba: //
dcdd144598 2011-02-23        kinaba: //	要素削除時にdeleteを実行しっちゃったりするバージョン。
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<class T>
dcdd144598 2011-02-23        kinaba: class gapbufobj : public gapbuf<T*>
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: public:
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	explicit gapbufobj( ulong alloc_size=40 )
dcdd144598 2011-02-23        kinaba: 		: gapbuf<T*>( alloc_size )
dcdd144598 2011-02-23        kinaba: 		{ }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	void RemoveAt( ulong i, ulong len=1 )
dcdd144598 2011-02-23        kinaba: 		{
dcdd144598 2011-02-23        kinaba: 			ulong& gs_ = gapbuf<T*>::gs_;
dcdd144598 2011-02-23        kinaba: 			ulong& ge_ = gapbuf<T*>::ge_;
dcdd144598 2011-02-23        kinaba: 			T**&   buf_= gapbuf<T*>::buf_;
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 			if( i <= gs_ && gs_ <= i+len )
dcdd144598 2011-02-23        kinaba: 			{
dcdd144598 2011-02-23        kinaba: 				// 前半を削除
dcdd144598 2011-02-23        kinaba: 				for( ulong j=i, ed=gs_; j<ed; ++j )
dcdd144598 2011-02-23        kinaba: 					delete buf_[j];
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 				len -= (gs_-i);
dcdd144598 2011-02-23        kinaba: 				gs_  = i;
dcdd144598 2011-02-23        kinaba: 			}
dcdd144598 2011-02-23        kinaba: 			else
dcdd144598 2011-02-23        kinaba: 			{
dcdd144598 2011-02-23        kinaba: 				gapbuf<T*>::MakeGapAt( i );
dcdd144598 2011-02-23        kinaba: 			}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 			// 後半を削除
dcdd144598 2011-02-23        kinaba: 			for( ulong j=ge_, ed=ge_+len; j<ed; ++j )
dcdd144598 2011-02-23        kinaba: 				delete buf_[j];
dcdd144598 2011-02-23        kinaba: 			ge_ = ge_+len;
dcdd144598 2011-02-23        kinaba: 		}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	~gapbufobj()
dcdd144598 2011-02-23        kinaba: 		{ RemoveAt( 0, gapbuf<T*>::size() ); }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	void RemoveAll( ulong i )
dcdd144598 2011-02-23        kinaba: 		{ RemoveAt( 0, gapbuf<T*>::size() ); }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	void RemoveToTail( ulong i )
dcdd144598 2011-02-23        kinaba: 		{ RemoveAt( i, gapbuf<T*>::size()-i ); }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: public:
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	T& operator[]( ulong i )
dcdd144598 2011-02-23        kinaba: 		{ return *gapbuf<T*>::operator[](i); }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	const T& operator[]( ulong i ) const
dcdd144598 2011-02-23        kinaba: 		{ return *gapbuf<T*>::operator[](i); }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: private:
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	NOCOPY(gapbufobj<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_GAP_H_