悪名高き車輪再開発屋d金魚作品No1 gapbuffer改
関連：
d:id:studiokingyo:20040606
d:id:soleil:20040603#p6
http://www.kmonos.net/wlog/39.php#_1735040529
更新版や機能追加版はCVSリポリトジにて。
http://cvs.sourceforge.jp/cgi-bin/viewcvs.cgi/dkingyoutility/
追記：DKUT11ディレクトリで御願いします。
追記：2005/08/24 まだアップロードしていません。スミマセンです。
以下のソースはバグ持ちです。使わないでおいてください。
/*!
@file gapbuffer.h
@brief ギャップ・バッファ
@auther Original: Takty Reconstruct : d金魚
@since reconstruct : 2004/06/06
@note
http://aiwww.main.eng.hokudai.ac.jp/~takty/
感謝 m(_ _)mいわいる、ギャップバッファーって奴です。
「ギャップバッファー」で検索しても１件も検索に引っかからないです＾＾；@section licence
Takty氏に肖りましてこのソースはNYSLって事で・・・。@todo
バグチェック ( オィ
template<class InputIterator>insert をVC6で通す<s>const_iteratorを実装できない (´Д⊂グスン
誰か助けて〜（C++何年やっているんだよ！！オレ</s>
@bug
VC6ではtemplate<class InputIterator>insertでエラる。
オーイ。どうにかしてよMSさん。というか、私の頭がバグっているのか？
*/#ifndef _GAPBUFFER_H_
#define _GAPBUFFER_H_#include <vector>
#include <iterator>
#include <dkutil/dktl/traits.h>//#include <boost/iterator/counting_iterator.hpp>
namespace dkutil{
/*!
reconstruct by d金魚
STL風味に直してみました。list
*/
template<class T,typename A=std::allocator<T> >
class gapbuffer : protected std::vector<T,A>
{
public:typedef std::vector<T,A> base_type;
typedef base_type::size_type size_type;
typedef base_type::value_type value_type;typedef base_type::reference reference;
typedef base_type::const_reference const_reference;typedef base_type::pointer pointer;
typedef base_type::const_pointer const_pointer;
typedef base_type::iterator base_iterator;
typedef gapbuffer<T,A> self_type;
private:
//unsigned int -> size_type;
size_type gb_, ge_;
const size_type initGapSize_;
public:template<class T,class Traits,class Boss>
//template<class Traits,class Boss>
class iterator_base : public std::random_access_iterator_tag {
public:typedef T value_type;
//typedef typename Traits::value_type value_type;
typedef typename Traits::pointer pointer;
typedef typename Traits::reference reference;typedef typename iterator_base<
T,
policy::non_const_traits<T>
,Boss
> iterator;
typedef typename iterator_base<
T,
policy::const_traits<T> ,
Boss
> const_iterator;
typedef typename iterator_base<
T,
Traits,
Boss
> self_type;typedef std::random_access_iterator_tag iterator_category;
typedef std::size_t size_type;
typedef ptrdiff_t difference_type;
typedef typename Boss::pointer boss_pointer;
typedef typename Boss::reference boss_reference;friend iterator;
friend const_iterator;
iterator_base(size_type s,boss_pointer x){//mediator...?
mc = s;
mx = x;
}
iterator_base(){
mc = UINT_MAX;
mx = NULL;
}
iterator_base(const iterator &x){
mc = x.mc;
mx = x.mx;
}reference operator*()const{
return mx->operator[](mc);
}
pointer operator->() const {
return &(operator*());
}
self_type &operator++(){
mc++;
return (*this);
}
self_type &operator--(){
mc--;
return (*this);
}
//使えない。コスト高すぎ！
self_type operator++(int){
self_type t = *this;
operator++();
return t;
}
self_type operator--(int){
self_type t = *this;
operator--();
return t;
}//ここの引数、self_typeではなく、
//iteratorにしないとconst_iterator時 に使えない。
bool operator==(const iterator &x)const{
return (mc == x.mc && mx == x.mx);
}
bool operator!=(const iterator &x)const{
return self_type::operator==(x);
}private:
size_type mc;
boss_pointer mx;
};typedef iterator_base<
value_type,
policy::non_const_traits<value_type>,
policy::non_const_traits<self_type>
> iterator;
typedef iterator_base<
value_type,
policy::const_traits<value_type>,
policy::non_const_traits<self_type>
//policy::const_traits<self_type>
> const_iterator;const_iterator begin()const{
return const_iterator(0,this);
}
const_iterator end()const{
return const_iterator(size(),this);
}
iterator begin(){
return iterator(0,this);
}
iterator end(){
return iterator(size(),this);
}
private:
// ギャップ開始点をインデックス指定した位置まで移動する
void moveGap(size_type index) {if(index < gb_) {
//for(int i = 0; i < gb_ - index; i++)
for(size_type i = 0; i < gb_ - index; i++)
{
base_type::operator[]( ge_ - 1 - i) =
base_type::operator[]( gb_ - 1 - i);
}
ge_ -= (gb_ - index);
}
else if(index > gb_)
{
//for(int i = 0; i < index - gb_; i++)
for(size_type i = 0; i < index - gb_; i++)
{
base_type::operator[]( gb_ + i) =
base_type::operator[]( ge_ + i);
}
ge_ += (index - gb_);
}
gb_ = index;
}
// ギャップを少なくともsize確保する
void allocGap(size_type size) {
T val;base_type::insert(base_type::begin() + gb_, size, val);
ge_ += size;
}/// 補正オフセット取得
size_type getReviseOffset(size_type i)const{
return (i < gb_) ? i : i + (ge_ - gb_);
}public:
gapbuffer() : initGapSize_(64)
{
base_type::resize(initGapSize_);
gb_ = 0;
ge_ = initGapSize_;
}
gap_buffer(const self_type &x){
*this = x;
}~gapbuffer() {}
size_type size() const {
return (int)base_type::size() - ((int)ge_ - (int)gb_);
}
size_type capacity() const{
return base_type::capacity();
}
void reserve(size_type i){
base_type::reserve(i);
}
void clear() {
gb_ = 0;
ge_ = base_type::size();
}
void insert(size_type index, size_type len, const_reference x) {
moveGap(index);
if((int)ge_ - (int)gb_ <= (int)len){
allocGap(initGapSize_ + len);
}
for(int i = 0; i < (int)len; i++){
base_type::operator[]( gb_ + i) = x;
}
gb_ += len;
}
#if defined(_MSC_VER) && _MSC_VER != 1200
template<class InputIterator>
void insert(size_type index, InputIterator begin__, InputIterator end__) {
int len = end__ - begin__;moveGap(index);
if((int)ge_ - (int)gb_ <= len){
allocGap(initGapSize_ + len);
}
for(int i = 0; begin__ != end__; i++, ++begin__){
base_type::operator[]( gb_ + i) = *begin__;
//ins(i,begin__);
//setObj(i,*begin__);
}
gb_ += len;
}
#endif
void insert(size_type index, const_reference x) {
insert(index, 1, x);
}void erase(size_type begin, size_type end)
{
size_type len = end - begin;if(begin <= gb_ && gb_ < end) {
len -= ((int)gb_ - (int)begin);
gb_ = begin;
} else {
moveGap(begin);
}
ge_ += len;
}
void erase(size_type index) {if(index <= gb_ && gb_ <= index + 1) {
len -= (gb_ - index);
gb_ = index;
} else {
moveGap(index);
}
ge_ += 1;
}void push_back(const_reference x) {
if(ge_ == base_type::size()) {
insert(size(), x);
} else {
base_type::push_back(x);
}
}reference at(size_type i){
return base_type::at(getReviseOffset(i));
}
const_reference at(size_type i) const {
return base_type::at(getReviseOffset(i));
}reference operator[](size_type i) {
# ifdef NDEBUG
return base_type::operator[]( getReviseOffset() );
# else
return self_type::at(i);
# endif
//return base_type::operator[]( getReviseOffset(i) );
}const_reference operator[](size_type i) const {
# ifdef NDEBUG
return base_type::operator[]( getReviseOffset() );
# else
return self_type::at(i);
# endif
//return base_type::operator[]( getReviseOffset(i) );
}
//多分、これでOK
reference operator =(const self_type &x){
resize(x.size());
for(size_t i=0;i<size();i++)
{
base_type::operator[i] = x[i];
}
return *this;
}
};
}//end of dkutil namespace
#endif
