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
}
};