c++ - 順序付けされたマップでのシーリング/フロア/ロウワー/ハイアーエントリの実装

Question

カスタムオーダーマップクラスのシーリング/フロア/ローワー/ハイアーエントリ関数を実装しようとしています。現在、2 つの構文エラーが発生しています。

">> ネストされたテンプレート内に > > ある必要があります"、この方法で修正しましたが、まだこのエラーが発生します。
「BSIterator は型に名前を付けません」。

ceilingEntry の実行方法を教えてください ( k以上の最小のキー値を持つエントリにイテレータを返すか、そのようなエントリがないかマップが空の場合は end() を返すことになっています)? コードを最小限に抑えようとしましたが、理解できることを願っています。

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

編集：簡単にコンパイルできるようにコードを拡張しました。最小化しようとしましたが、多くの依存関係があるため、まだかなり大きいです。ほとんどのスペースはテンプレートによって占められていますが、これで問題ないことを願っています。

c++ - 順序付けされたマップでのシーリング/フロア/ロウワー/ハイアーエントリの実装

BT.h

BST.h

OrderedMap.h

0 に答える 0

Related

Reference