• monkyyy (87/87) Aug 04 https://youtu.be/i-h95QIGchY?si=ZK2z2PVUp2K85dQN

monkyyy <crazymonkyyy gmail.com> writes:

https://youtu.be/i-h95QIGchY?si=ZK2z2PVUp2K85dQN

 From this talk he suggested a rare datastructure that had a 
dynmaic size but stable pointers, he called it an exponential 
array(... no, all dynamic arrays I know try to grow exponentially)

figured out the math for different chunk sizes, proof of concept:

```d
import std;

template math(int chunksize){
	import core.bitop;
	static assert(bsr(chunksize)!=bsr(chunksize-1),"pick a power of 
two");
	auto msb(T)(T i)=>bsr(i|(chunksize-1))-bsr((chunksize-1));//when 
chunksize is 2, is most signifigant bit with 0 defined to be 0, 
chunksize scales that hack
	auto msbrun(T)(T i)=>1<<bsr(i|(chunksize*2-1));//run length of 
the current chunk msb's
	auto msboffset(T)(T i)=>i%msbrun(i);//offset of the index in the 
current chunk
}
unittest{
	alias m=math!256;
	foreach(i;0..10000000){
		//writeln(i,":",m.msb(i),',',m.msboffset(i),'/',m.msbrun(i));
		assert(m.msboffset(i)<m.msbrun(i));
		if(i==0){continue;}
		if(m.msboffset(i)==0){
			assert(m.msb(i)==m.msb(i-1)+1);
		} else {
			assert(m.msb(i)==m.msb(i-1));
		}
	}
}
struct msbchunks(T,int chunksize=256){
	//--- math
	import core.bitop;
	static assert(bsr(chunksize)!=bsr(chunksize-1),"pick a power of 
two");
	auto msb(T)(T i)=>bsr(i|(chunksize-1))-bsr(chunksize-1);//when 
chunksize is 2, is most signifigant bit with 0 defined to be 0, 
chunksize scales that hack
	auto msbrun(T)(T i)=>1<<bsr(i|(chunksize*2-1));//run length of 
the current chunk msb's
	auto msboffset(T)(T i)=>i%msbrun(i);//offset of the index in the 
current chunk
	//--- store
	T[][] _chunks;
	size_t length;
	ref T opIndex(I)(I i)=>_chunks[msb(i)][msboffset(i)];
	ref opOpAssign(string s:"~")(T t){
		if(msboffset(length)==0){
			_chunks~=new T[](msbrun(length));//todo make gc listen to 
instructions
			//assert(_chunks[$-1].capacity==msbrun(length));
		}
		opIndex(length++)=t;
	}
	ref opOpAssign(string s:"~")(T[] t){
		while(_chunks.length-1<msboffset(length+t.length-1)){//todo 
check paritys of -1
			//...idk todo math
		}
		foreach(e;t){//LAZY:
			this~=e;
		}
	}
	//---range
	auto opIndex()=>_chunks.joiner.take(length);
}
unittest{
	msbchunks!(int,16) foo;
	foo~=iota(0,500).array;
	int last;
	foreach(e;foo[].map!(a=>a*2)){
		last=e;
	}
	assert(last==iota(0,500).array[$-1]*2);
	auto bar=&foo[376];
	foreach(i;0..10000){
		foo~=i;
	}
	assert(foo[4444]==4444-500);
	assert(bar==&foo[376],"static pointer check");
}
```

Im not convinced this is the best data structure but it maybe 
worth a speed check given it doesnt copy on resizing and the 
indirections are outerloop