B-Tree Assignment
This assignment has to write a B-tree roughly following the API or a std::map. Note that you will need to keep a free list of the nodes that are no longer being used when data has been deleted. Only types that don't include pointers can be written to the file.
The value t in the book is the third template parameter for the class. Making it a template parameter allows you to have your internal struct for the nodes that are stored to file use it as a size for the arrays.
Your code should be in BTree.h for your submission.
template<typename K,typename V,int T>
class BTree {
// TODO: Your Node type.
// TODO: B-Tree data
// Placed here to prevent copies.
BTree(const BTree<K,V,T> &that);
BTree<K,V,T> &operator=(const BTree<K,V,T> &that);
// TODO: Helper functions recommended
public:
typedef K key_type;
typedef V mapped_type;
typedef std::pair<K,V> value_type;
class const_iterator {
// TODO: iterator data you are allowed to store a Node here if you want.
public:
// TODO: constructors
bool operator==(const const_iterator &i) const { return /* TODO*/; }
bool operator!=(const const_iterator &i) const { return !(*this==i); }
const std::pair<K,V> operator*() const {
// TODO
}
const_iterator &operator++() {
// TODO
return *this;
}
const_iterator operator++(int) {
const_iterator tmp(*this);
++(*this);
return tmp;
}
};
BTree(const std::string &fname):/* TODO */ {
if(file==nullptr) {
// open with w+b and set up the file
} else {
// read header information
}
}
~BTree() {
// close the file
}
bool empty() const;
unsigned size() const;
const_iterator find(const key_type& k) const;
int count(const key_type& k) const;
std::pair<const_iterator,bool> insert(const value_type& val);
template <class InputIterator>
void insert(InputIterator first, InputIterator last) {
for(auto iter = first; iter!=last; ++iter) {
insert(*iter);
}
}
const_iterator erase(const_iterator position);
int erase(const key_type& k);
void clear();
const mapped_type operator[](const K &key) const;
const_iterator set(const value_type &val);
bool operator==(const BTree<K,V,T>& rhs) const;
bool operator!=(const BTree<K,V,T>& rhs) const;
const_iterator begin() const { return /* TODO */; }
const_iterator end() const { return /* TODO */; }
const_iterator cbegin() const { return /* TODO */; }
const_iterator cend() const { return /* TODO */; }
void printTree() {
printRecur(rootNum);
std::cout << std::endl;
}
private:
// Private helper methods
void printRecur(int x) {
Node node = readNode(x);
std::cout << "(x=" << x << ", n=" << node.n << ", leaf=" << node.leaf << ", p=" << node.parent << ": ";
for(int i=0; i<node.n; ++i) {
if(!node.leaf) printRecur(node.children[i]);
std::cout << " " << node.data[i].first << " ";
}
if(!node.leaf) printRecur(node.children[node.n]);
std::cout << ")";
}
};