Order Stat Tree Assignment

For this assignment you are implementing a sequence that uses an augmented balanced binary tree, an order-stat tree. Call your file OrderStat.h and make the following class.

template<typename T>

class OrderStat {

struct Node {

// TODO

};

// TODO: Your data for the tree.

public:

typedef T value_type;

class const_iterator;

class iterator {

// TODO: Your data for the iterator.

public:

friend class const_iterator;

// TODO: constructors

bool operator==(const iterator &i) const { /* TODO */ }

bool operator!=(const iterator &i) const { return !(*this==i); }

T &operator*() { /* TODO */ }

iterator &operator++() {

// TODO

return *this;

}

iterator &operator--() {

// TODO

return *this;

}

iterator operator++(int) {

iterator tmp(*this);

++(*this);

return tmp;

}

iterator operator--(int) {

iterator tmp(*this);

--(*this);

return tmp;

}

};

class const_iterator {

// TODO: iterator data

public:

friend class OrderStat<T>;

// TODO: constructors

bool operator==(const const_iterator &i) const { /* TODO */ }

bool operator!=(const const_iterator &i) const { return !(*this==i); }

const T &operator*() { /* TODO */ }

const_iterator &operator++() {

// TODO

return *this;

}

const_iterator &operator--() {

// TODO

return *this;

}

const_iterator operator++(int) {

const_iterator tmp(*this);

++(*this);

return tmp;

}

const_iterator operator--(int) {

const_iterator tmp(*this);

--(*this);

return tmp;

}

};

OrderStat()/* TODO */ {/* TODO */}

OrderStat(const OrderStat<T> &that) {

// TODO

}

~OrderStat() {

// TODO

}

OrderStat &operator=(const OrderStat<T> &that) {

// TODO

}

bool empty() const { /* TODO */ }

unsigned size() const { /* TODO */ }

value_type &front();

const value_type &front() const;

value_type &back();

const value_type &back() const;

iterator insert(const_iterator position,const value_type& val);

template <class InputIterator>

void insert(const_iterator position,InputIterator first, InputIterator last);

iterator erase(const_iterator position);

void clear();

value_type &operator[](int index);

void push_front(const value_type& val);

void pop_front();

void push_back(const value_type& val);

void pop_back();

bool operator==(const OrderStat<T>& rhs) const;

bool operator!=(const OrderStat<T>& rhs) const;

iterator begin() {

// TODO

}

const_iterator begin() const {

// TODO

}

iterator end() {

// TODO

}

const_iterator end() const {

// TODO

}

const_iterator cbegin() const {

// TODO

}

const_iterator cend() const {

// TODO

}

};