C++Talk.NET

David Turner · Guest

I've implement a ternary search tree after the fashion of the standard
library. I'd like to hear any comments about C++ style, consistency, etc.

The usage style is reminiscent of std::map:

string_map<int> t;
t["Hello"] = 1;
t["World"] = 2;
string_map<int>::const_iterator i = t.find("Hello");
if(i != t.end())
cout << i->key() << " has value " << i->value() << endl;

Ternary search trees are described
http://www.javaworld.com/javaworld/jw-02-2001/jw-0216-ternary.html (or you
could google for a link like I did Wink

).

No implementation yet of partial_find or anything like that; but I'd like to
hear suggestions about features that would be nice, too.

Regards
David Turner

--------------- Code paste begins ------------------
#include
template<typename CharType, typename DataType>
class basic_string_map
{
class Node
{
friend class basic_string_map;
CharType ch;
DataType* data;
Node *l, *r, *n, *p;
Node(const CharType& c, Node* parent):
ch(c), l(0), r(0), n(0), p(parent), data(0)
{
}
~Node()
{
delete l;
delete r;
delete n;
delete data;
}

public:
::std::basic_string<CharType> key() const
{
int count = 1;
const Node *i = p, *j = this;
while(i) {
if(i->n == j)
++ count;
j = i;
i = i->p;
}
::std::basic_string<CharType> result(count, 0);
for(i=this, j = n; i; j=i, i=i->p) {
if(i->n == j)
result[--count] = i->ch;
}
return result;
}
const DataType& value() const
{
return *data;
}
DataType& value()
{
return *data;
}
} *root;

Node* _Insertion(const CharType* key)
{
Node **idx = &root, *parent = 0;
if(key == 0 || *key == 0)
return 0;
while(*idx) {
if(*key < (*idx)->ch)
{
parent = *idx;
idx = &((*idx)->l);
}
else if((*idx)->ch < *key)
{
parent = *idx;
idx = &((*idx)->r);
}
else if(*(++key) == 0)
break;
else
{
parent = *idx;
idx = &((*idx)->n);
}
}
if(*idx == 0)
{
*idx = new Node(*key, parent);
while(*++key != 0)
{
(*idx)->n = new Node(*key, *idx);
idx = &((*idx)->n);
}
}
return *idx;
}

static Node* _Leftmost(Node* n)
{
while(n)
{
if(n->l)
n = n->l;
else if(n->data)
break;
else
n = n->n;
}
return n;
}

static Node* _Next(Node* n)
{
if(n->n)
return _Leftmost(n->n);
else
{
while(n)
{
if(n->p && n->p->l == n)
{
n = n->p;
if(n->data)
return n;
if(n->n)
return _Leftmost(n->n);
if(n->r)
return _Leftmost(n->r);
}
else if(n->p && n->p->n == n)
{
n = n->p;
if(n->r)
return _Leftmost(n->r);
}
else
n = n->p;
}
}

return n;
}

public:
class const_iterator;
class iterator
{
friend class basic_string_map;
friend class const_iterator;
Node* ref;
iterator(Node* n): ref(n) { }
public:
iterator(const iterator& rhs): ref(rhs.ref) { }
Node* operator ->() { return ref; }
const Node* operator ->() const { return ref; }
Node& operator *() { return *ref; }
const Node& operator *() const { return *ref; }
iterator& operator ++()
{
ref = _Next(ref);
return *this;
}
iterator operator ++(int)
{
Node* oldref = ref;
ref = _Next(ref);
return iterator(oldref);
}
bool operator == (const iterator& rhs) const
{
return ref == rhs.ref;
}
bool operator != (const iterator& rhs) const
{
return ref != rhs.ref;
}
};
class const_iterator
{
friend class basic_string_map;
Node* ref;
const_iterator(Node* n): ref(n) { }
public:
const_iterator(const const_iterator& rhs): ref(rhs.ref) { }
const_iterator(const iterator& rhs): ref(rhs.ref) { }
const Node* operator ->() const { return ref; }
const Node& operator *() const { return *ref; }
const_iterator& operator ++()
{
ref = _Next(ref);
return *this;
}
const_iterator operator ++(int)
{
Node* oldref = ref;
ref = _Next(ref);
return iterator(oldref);
}
bool operator == (const const_iterator& rhs) const
{
return ref == rhs.ref;
}
bool operator != (const const_iterator& rhs) const
{
return ref != rhs.ref;
}
};

basic_string_map(): root(0) { }
~basic_string_map()
{
delete root;
}

const_iterator find(const CharType* value) const
{
Node* idx = root;
while(idx) {
if(*value == 0)
idx = 0;
else if(*value < idx->ch)
idx = idx->l;
else if(idx->ch < *value)
idx = idx->r;
else if(*(++value) == 0)
break;
else
idx = idx->n;
}
return idx;
}

iterator find(const CharType* value)
{
Node* idx = root;
while(idx) {
if(*value == 0)
idx = 0;
else if(*value < idx->ch)
idx = idx->l;
else if(idx->ch < *value)
idx = idx->r;
else if(*(++value) == 0)
break;
else
idx = idx->n;
}
return idx;
}

const_iterator find(const ::std::basic_string<CharType>& value)
const
{
return find(value.c_str());
}

iterator find(const ::std::basic_string<CharType>& value)
{
return find(value.c_str());
}

iterator insert(const CharType* key, const DataType& data)
{
Node* idx = _Insertion(key);
delete idx->data;
idx->data = new DataType(data);
return idx;
}

iterator insert(const ::std::basic_string<CharType>& key,
const DataType& data)
{
return insert(key.c_str(), data);
}

DataType& operator [](const CharType* key)
{
Node* idx = _Insertion(key);
if(idx->data == 0)
idx->data = new DataType();
return *idx->data;
}

iterator begin()
{
if(root == 0)
return 0;
return _Leftmost(root);
}

iterator end()
{
return 0;
}
};

template<typename Data>
class string_map: public basic_string_map<char, Data>
{
};

template<typename Data>
class wstring_map: public basic_string_map<wchar_t, Data>
{
};

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Siemel Naran · Guest

"David Turner" <david (AT) firepro (DOT) co.za> wrote

David Turner · Guest

Hi Siemel

Siemel Naran · Guest

"David Turner"

David Turner · Guest

Hi

Allan Odgaard · Guest

David Turner:

Siemel Naran · Guest

"Allan Odgaard" <Duff (AT) DIKU (DOT) DK> wrote in message

Allan Odgaard · Guest

Siemel Naran: