Write in JAVA:

Write an implementation of the Set class, with associated iterators using a Binary Search Tree. Add to each node a link to the parent node.

Stub program on C++ is in this folder. Complete ToDo-s to make program work. Students who write programs on Java and Python, consider this program as pseudo code.

#include #include #include #include #include #include

#include "BinarySearchTree.h"

template class Set { public:

typedef Key key_type; typedef Key value_type; typedef std::size_t size_type;

class iterator {

friend class Set;

public:

// TODO Define copy constructor

friend bool operator==( const iterator& lh, const iterator& rh) { return lh.node == rh.node; }

// TODO Define friend operator!=

iterator& operator++() { node = set->tree.next(node); return *this; }

const Key& operator*() { return node->element; }

private:

typedef typename BinarySearchTree::BinaryNode BinaryNode;

const Set *const set; BinaryNode * node;

iterator( const Set *const theSet, BinaryNode *const theNode ) : set(theSet), node( theNode ) {} };

iterator begin() { return iterator(this,tree.start()); } iterator end () { return iterator(this,nullptr); }

Set() {}

// Copy constructor Set( const Set &rhs ) : tree{ rhs.tree } {}

// Move constructor Set( Set &&rhs ) : tree{ std::move(rhs.tree) } {}

size_type size() const { // TODO implement method size using tree.start() and tree.next() }

// TODO Define method empty()

void clear() { tree.makeEmpty(); }

void insert( const Key &p ){ tree.insert(p); }

size_type erase( const Key& key ) {

return tree.remove(key) ? 1 : 0; }

size_type erase( const iterator& iter ) {

// TODO Implement method erase() }

iterator find( const Key &key ) const {

// TODO Implement method find() }

size_type count( const Key &key ) const {

return tree.find(key) ? 1 : 0; }

private:

BinarySearchTree tree;

template< class K> friend std::ostream operator<< ( std::ostream &os, const Set &set ) {

set.tree.printTree(os); return os; }

};