gistfile1.cpp

#define _SECURE_SCL 0
#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <algorithm>
#include <numeric>
#include <windows.h>

namespace details {

	// compute position of the leading bit in binary representation
	inline size_t leadBitPos(size_t value) {
		size_t r = 0; // result of log2(v) will go here
		if (value & 0xFFFF0000)
		{
			value >>= 16;
			r |= 16;
		} 
		if (value & 0xFF00)
		{
			value >>= 8;
			r |= 8;
		} 
		if (value & 0xF0)
		{
			value >>= 4;
			r |= 4;
		} 
		if (value & 0xC)
		{
			value >>= 2;
			r |= 2;
		} 
		if (value & 0x2)
		{
			value >>= 1;
			r |= 1;
		} 
		return r;
	}

	// compute q = ceil(x/y)
	inline size_t div_ceil(size_t x, size_t y) {
		return (x + y - 1)/y;
	}

	static const size_t rightMasks[] = {
		0x00000000,
		0x00000001,
		0x00000003,
		0x00000007,
		0x0000000F,
		0x0000001F,
		0x0000003F,
		0x0000007F,
		0x000000FF,
		0x000001FF,
		0x000003FF,
		0x000007FF,
		0x00000FFF,
		0x00001FFF,
		0x00003FFF,
		0x00007FFF,
		0x0000FFFF,
		0x0001FFFF,
		0x0003FFFF,
		0x0007FFFF,
		0x000FFFFF,
		0x001FFFFF,
		0x003FFFFF,
		0x007FFFFF,
		0x00FFFFFF,
		0x01FFFFFF,
		0x03FFFFFF,
		0x07FFFFFF,
		0x0FFFFFFF,
		0x1FFFFFFF,
		0x3FFFFFFF,
		0x7FFFFFFF,
		0xFFFFFFFF
	};
}

template<typename T, typename Alloc = std::allocator<T>>
class ResizableArray
{
	struct Datablock {
		T* content;
		int length;
		int ocupancy;

		bool full() const {
			return length == ocupancy;
		}
	};

	// datablocks
	std::vector<Datablock, Alloc> index_;

	inline
	T* locate(size_t index) {
		auto r = index + 1;
		auto k = details::leadBitPos(r);
		auto mask = (1 << k) - 1;
		auto dbindex = r & mask;
		return index_[k].content + dbindex;
	}

	inline
	void append(T const& value) {
		Datablock& block = index_.back();
		if (block.full()) {
			auto blockIndex = index_.size();
			auto blockSize = 1 << blockIndex;
			Datablock datablock;
			datablock.length = blockSize;
			datablock.ocupancy = 1;
			datablock.content = new T[blockSize];
			datablock.content[0] = value;
			index_.push_back(datablock);
		}
		else {
			block.content[block.ocupancy] = value;
			block.ocupancy++;
		}
	}

public:

	T operator [] (size_t index) {
		return *locate(index);
	}

	void push_back(T const& value) {
		append(value);
	}

	ResizableArray() 
	{
		Datablock db;
		db.length = 1;
		db.ocupancy = 0;
		db.content = new T[1];
		index_.push_back(db);
	}

};

template<typename T, typename Alloc = std::allocator<T>>
class ResizableArrayV2 
{
	struct Datablock {
		T* content;
		int length;
		int ocupancy;

		bool full() const {
			return length == ocupancy;
		}
	};

	// NOTE: superblocks are implicit

	// datablocks
	std::vector<Datablock, Alloc> index_;
	// number of datablocks per index
	std::vector<int> numdatablocks_;
	// number of superblocks
	size_t numsb_;
	// number of datablocks
	size_t numdb_;
	// occupancy of the last superblock
	size_t last_SB_occupancy_;
	// number of data blocks in last superblock
	size_t sbsize_;
	// number of elements in last datablock
	size_t dbsize_;

	inline
	T* locate(size_t index) {
		auto r = index + 1;
		auto k = details::leadBitPos(r);
		auto prevBlocks = numdatablocks_[k];
		auto bitsc = details::div_ceil(k, 2);
		auto elemIndex = r & details::rightMasks[bitsc];
		auto mask = (1 << k) - 1;
		auto dbIndex = (r & mask) >> bitsc;
		return index_[prevBlocks + dbIndex].content + elemIndex;
	}

	inline
	void append(T const& value) {
		if (index_.empty()) {
			Datablock fst;
			fst.length = 1;
			fst.ocupancy = 1;
			fst.content = new T[1];
			fst.content[0] = value; // TODO: use allocator
			last_SB_occupancy_++;
			index_.push_back(fst);
			numdatablocks_.push_back(0);
			return;
		}
		Datablock& last = index_.back();
		if (last.full()) {
			if (last_SB_occupancy_ == sbsize_) {
				numdatablocks_.push_back(numdb_ + sbsize_);
				numsb_++;
				numdb_ += sbsize_;
				if (numsb_ % 2)
					sbsize_ *= 2;
				else
					dbsize_ *= 2;
				last_SB_occupancy_ = 0;
			}
			Datablock db;
			db.ocupancy = 1;
			db.length = dbsize_;
			db.content = new T[dbsize_];
			db.content[0] = value;
			last_SB_occupancy_++;
			index_.push_back(db);
		}
		else {
			last.content[last.ocupancy] = value;
			last.ocupancy++;
		}
	}

public:

	T operator [] (size_t index) {
		return *locate(index);
	}

	void push_back(T const& value) {
		append(value);
	}

	ResizableArrayV2() 
		: index_()
		, numsb_(1)
		, last_SB_occupancy_(0)
		, sbsize_(1)
		, dbsize_(1)
		, numdb_(0)
	{
	}
};

class Timer {
	std::vector<long> instants_;
	std::vector<std::string> marks_;
	std::vector<int> memusage_;
	std::vector<std::string> memusagemarks_;
public:
	void start(const char* m) {
		instants_.push_back(GetTickCount());
		marks_.push_back(m);
	}

	void checkpoint(const char* m) {
		instants_.push_back(GetTickCount());
		marks_.push_back(m);
	}

	friend std::ostream& operator << (std::ostream& out, Timer const& tm);
};

std::ostream& operator << (std::ostream& out, Timer const& tm) {
	long p = 0;;
	for(int i = 0; i < tm.instants_.size(); i++) {
		auto msg = tm.marks_[i];
		if (i == 0) {
			out << msg << std::endl;
			p = tm.instants_[i];
		}
		else {
			auto d = tm.instants_[i] - p;
			p = tm.instants_[i];
			out << msg << " : " << d << std::endl;
		}
	}
	return out;
}

template<typename T>
void runtime(T fn) {
	Timer tm;
	fn(tm);
	std::cout << tm << std::endl;
}

int main(int argc, char* argv[])
{
	runtime([](Timer& tm) {
		tm.start("ResizableArray");
		ResizableArray<int> data;
		for(int i = 0; i < 10000000; i++) {
			data.push_back(i);
		}
		tm.checkpoint("fill");
		for(int i = 0; i < 10000000; i++) {
			if (i != data[i]) {
				std::cout << "error at " << i << std::endl;
				break;
			}
		}
		tm.checkpoint("read");
	});

	runtime([](Timer& tm) {
		tm.start("ResizableArrayV2");
		ResizableArrayV2<int> data;
		for(int i = 0; i < 10000000; i++) {
			data.push_back(i);
		}
		tm.checkpoint("fill");
		for(int i = 0; i < 10000000; i++) {
			if (i != data[i]) {
				std::cout << "error at " << i << std::endl;
				break;
			}
		}
		tm.checkpoint("read");
	});

	runtime([](Timer& tm) {
		tm.start("std::vector");
		std::vector<int> data;
		for(int i = 0; i < 10000000; i++) {
			data.push_back(i);
		}
		tm.checkpoint("fill");
		for(int i = 0; i < 10000000; i++) {
			if (i != data[i]) {
				std::cout << "error at " << i << std::endl;
				break;
			}
		}
		tm.checkpoint("read");
	});

	runtime([](Timer& tm) {
		tm.start("std::deque");
		std::deque<int> data;
		for(int i = 0; i < 10000000; i++) {
			data.push_back(i);
		}
		tm.checkpoint("fill");
		for(int i = 0; i < 10000000; i++) {
			if (i != data[i]) {
				std::cout << "error at " << i << std::endl;
				break;
			}
		}
		tm.checkpoint("read");
	});

	return 0;
}