Unrolled linked list 块状链表的一种实现

看了好多文档，依然不得要领。

Argument

好像这个Unrolled Linked list和块状链表不是一个东西，就暂且认为Unrolled Linked list是一个指导意见好了。。
看了几个介绍，有关于maintain操作，只给出了sqrt(n)的理论值，我用了这个方法实现：

• 算两个初始值 BlockSize1=sqrt(n), BlockSize2=1.4*sqrt(n) 这个1.4随便猜的
• Maintain时，当相邻块合并后比BlockSize2小就合并，例如n=100避免了1,10,1,10,1,10这种问题。。

另外STL中还有更好用的Rope
还有网上有说 std::deque 是这个的，翻了翻，有空再看。。
http://llvm.org/svn/llvm-project/libcxx/trunk/include/deque

Template

#include <iostream>
#include <string>
using namespace std;

const int BLOCKSIZE1=1000, BLOCKSIZE2=1400;
struct BlockList {
    string data;
    BlockList *next=NULL;
}*head;
void showBlockList() {
    for (BlockList *b=head; b; b=b->next)
        cout<<"["<<b->data<<"] ";
    cout<<"<< ALL BLOCKS"<<endl;
}
/*
    pos: the index of the string.
        0 ... string.length()-1
    Return : Block and pos (usage: block.data[pos]).
    Special Case: the empty BlockList, data.size()==0.
*/
BlockList* getBlockId(int& pos) {
    if (pos==0)
        return head;
    for (BlockList* b=head; b; b=b->next) {
        if (pos < b->data.size()) {
            return b;
        }
        pos -= b->data.size();
    }
    return NULL;
}
/*
    Try to merge [begin] ... [end] (closed set)
    begin <= end <= NULL
*/
void maintain(BlockList *begin, BlockList *end) {
    //cout<<"Maintain] ["<<begin->data<<"] -> ["<<end->data<<"]"<<endl;
    BlockList *stopflag = (end?end->next:NULL);
    for (BlockList *it=begin; it->next!=stopflag;) {
        if (it->data.size()+it->next->data.size() <= BLOCKSIZE2) {
            //Merge these two blocks;
            it->data += it->next->data;
            BlockList *tmp=it->next->next;
            delete it->next;
            it->next = tmp;
        } else
            it = it->next;
    }
}
/*
    Create a new block and return it, Split the block before pos.
    pos : 0 ... block.size
    Intro: b -> nulBlock(return) -> data2 -> b.next();
*/
BlockList *splitNew(BlockList *b, int pos=BLOCKSIZE2) {
    BlockList *data2,*nulBlock;
    if (pos < b->data.size()) {
        data2 = new BlockList();
        data2->data = b->data.substr(pos);
        b->data = b->data.substr(0, pos);
        data2->next = b->next;
    }else
        data2 = b->next;
    if (b->data.size()) {
        nulBlock = new BlockList();
        b->next = nulBlock;
    }else
        nulBlock = b;
    nulBlock->next = data2;
    return nulBlock;
}
/* Insert a string at global position. */
void insert(int pos,const string &ss) {
    BlockList *b=getBlockId(pos);
    BlockList *mtBegin=b, *mtEnd;
    b = splitNew(b,pos);
    for (int i=0; i<ss.length(); i+=BLOCKSIZE1) {
        b = splitNew(b);
        mtEnd = b->next;
        if (i+BLOCKSIZE1 < ss.length())
            b->data = ss.substr(i, BLOCKSIZE1);
        else
            b->data = ss.substr(i);
        //showBlockList();
    }
    maintain(mtBegin, mtEnd);
}
/* Get character at position. */
char query(int pos) {
    BlockList *b=getBlockId(pos);
    return b->data[pos];
}
int main() {
    head = new BlockList();
    insert(0, "abcdefg");
    cout<<query(5)<<endl;//char 'f'.
    showBlockList();
    return 0;
}