I'm trying to implement ceiling/floor/lower/higherEntry functions for a custom ordered map class. Currently I am having two syntax errors:
- ">> should be > > in a nested template", I have modified it in this manner but I am still getting this error.
- "BSTIterator does not name a type".
Could you please just show me how to do ceilingEntry (it is supposed to return an iterator to the entry with the least key value greater than or equal to k, or return end() if there is no such entry or map is empty)? I tried to cut the code to the minimum, I hope it's understandable.
BT.h
#include<iostream>
#include<list>
#include<stdio.h>
template <typename E>
class LinkedBinaryTree {
public:
struct Node{
E elt;
Node* par;
Node* left;
Node* right;
Node() : elt(), par(NULL), right(NULL), left(NULL){}
};
public:
class Position{
public:
Node* v;
public:
Position(Node* _v = NULL):v(_v){}
E& operator*()
{return v->elt;}
Position left() const
{return Position(v->left);}
Position right() const
{return Position(v->right);}
Position parent() const
{return Position(v->par);}
bool isRoot() const
{return v->par == NULL;}
bool isExternal() const
{return v->left == NULL && v->right == NULL;}
bool isInternal() const
{return !isExternal();}
const E& operator*() const {return v->elt;}
bool operator==(const Position& ppos) const { return this->v ==
ppos.v ;}
friend class LinkedBinaryTree;
};
typedef std::list<Position> PositionList;
public:
LinkedBinaryTree();
int getSize() const;
bool isEmpty() const;
Position root() const;
PositionList positions() const;
void addRoot();
void expandExternal(const Position& p);
Position removeAboveExternal(const Position& p);
protected:
void preorder(Node* v, PositionList& pl) const;
private:
Node* _root;
int n;
};
template <typename E>
LinkedBinaryTree<E>::LinkedBinaryTree()
:_root(NULL), n(0) {}
template <typename E>
int LinkedBinaryTree<E>::getSize() const
{return n;}
template <typename E>
bool LinkedBinaryTree<E>::isEmpty() const
{return getSize() == 0;}
template <typename E>
typename LinkedBinaryTree<E>::Position LinkedBinaryTree<E>::root() const
{return Position(_root);}
template <typename E>
void LinkedBinaryTree<E>::addRoot()
{_root = new Node; n = 1;}
template <typename E>
void LinkedBinaryTree<E>::expandExternal(const Position& p){
Node* v = p.v;
v->left = new Node;
v->left->par = v;
v->right = new Node;
v->right->par = v;
n += 2;
}
template <typename E>
typename LinkedBinaryTree<E>::Position
LinkedBinaryTree<E>::removeAboveExternal(const Position& p){
Node* w = p.v; Node* v = w->par;
Node* sib = (w==v->left ? v->right:v->left);
if(v == _root){
_root = sib;
sib->par = NULL;
}
else{
Node* gpar = v->par;
if(v == gpar->left) gpar->left = sib;
else gpar->right = sib;
sib->par = gpar;
}
delete w; delete v;
n -= 2;
return Position(sib);
};
template <typename E>
typename LinkedBinaryTree<E>::PositionList LinkedBinaryTree<E>::positions()
const{
PositionList pl;
preorder(_root, pl);
return PositionList(pl);
}
template <typename E>
void LinkedBinaryTree<E>::preorder(Node* v, PositionList& pl) const{
pl.push_back(Position(v));
if(v->left != NULL)
preorder(v->left, pl);
if(v->right != NULL)
preorder(v->right, pl);
}
BST.h
template<typename K, typename V>
class Entry{
public:
typedef K Key;
typedef V Value;
public:
Entry(const K& k = K(), const V& v = V())
:_key(k), _value(v) {}
const K& key() const {return _key;}
const V& value() const {return _value;}
void setKey(const K& k) {_key = k;}
void setValue(const V& v){_value = v;}
private:
K _key;
V _value;
};
//Search Tree
template <typename E>
class SearchTree{
public:
typedef typename E::Key K;
typedef typename E::Value V;
typedef LinkedBinaryTree<E> BinaryTree;
typedef typename LinkedBinaryTree<E>::Position TPos;
public:
class Iterator{
public:
TPos v;
public:
Iterator(const TPos& vv) : v(vv) {}
const E& operator*() const {return *v;}
E& operator*() {return *v;}
bool operator==(const Iterator& p) const {return v == p.v;}
Iterator& operator++();
friend class SearchTree;
};
public:
SearchTree();
int getSize() const ;
bool isEmpty() const ;
Iterator find(const K& k);
Iterator insert(const K& k, const V& x);
void erase(const K& k);
void erase(const Iterator& p);
Iterator begin();
Iterator end();
TPos root() const;
TPos finder(const K& k, const TPos& v);
TPos inserter(const K& k, const V& x);
TPos eraser(TPos& v);
TPos restructure(const TPos& v);
private:
BinaryTree T;
int n;
};
template <typename E>
int SearchTree<E>::getSize() const {return n ;}
template <typename E>
bool SearchTree<E>::isEmpty() const {return n==0; }
template <typename E>
typename SearchTree<E>::Iterator& SearchTree<E>::Iterator::operator++(){
TPos w = v.right();
if(w.isInternal()){
do{v=w; w = w.left();}
while(w.isInternal());
}
else{
w = v.parent();
while(v == w.right())
{v = w; w = w.parent();}
v = w;
}
return *this;
}
template <typename E>
SearchTree<E>::SearchTree(): T(), n(0)
{T.addRoot(); T.expandExternal(T.root());}
template <typename E>
typename SearchTree<E>::TPos SearchTree<E>::root() const
{return T.root().left();}
template <typename E>
typename SearchTree<E>::Iterator SearchTree<E>::begin(){
TPos v = root();
while (v.isInternal()) v = v.left();
return Iterator(v.parent());
}
template <typename E>
typename SearchTree<E>::Iterator SearchTree<E>::end()
{return Iterator(T.root());}
template <typename E>
typename SearchTree<E>::TPos SearchTree<E>::finder(const K& k, const TPos&
v){
if(v.isExternal()) return v;
if(k < (*v).key()) return finder(k,v.left());
else if((*v).key() < k) return finder(k,v.right());
else return v;
}
template <typename E>
typename SearchTree<E>::Iterator SearchTree<E>::find(const K& k){
TPos v = finder(k, root());
if(v.isInternal()) return Iterator(v);
else return end();
}
OrderedMap.h
#include "BST.h"
template <typename KK, typename VV>
class OrderedMap: public SearchTree<Entry<KK,VV> > {
public:
typedef SearchTree<Entry<KK,VV> > BST;
typedef typename SearchTree<Entry<KK,VV> >::Iterator BSTIterator;
typedef typename SearchTree<Entry<KK,VV> >::TPos TPos;
public:
OrderedMap(): SearchTree<Entry<KK,VV> >(){}
bool empty () const ;
BSTIterator find ( const KK& k) const {find(k);}
BSTIterator end () {return BST::end();}
BSTIterator ceilingEntry(const KK& k);
BSTIterator ceilingEntry(const KK& k, TPos & w);
//...
};
template <typename KK, typename VV>
BSTIterator OrderedMap<KK,VV>::ceilingEntry(const KK& k) {
if (OrderedMap<KK,VV>::empty()) { return OrderedMap<KK,VV>::end(); }
return ceilingEntry(k, BST.root());
}
template <typename KK, typename VV>
BSTIterator OrderedMap<KK,VV>::ceilingEntry(const KK& k, TPos & w) {
// what to write here?
}
Edit: I expanded the code so it'd be possible to compile it readily. I tried to minimize but it's still pretty large as there as many dependencies. Most of the space is taken by the templates, I hope this is fine.