BTree implementation - take 2

[Nobody]

I took the advice from the group and got rid of the node accessor functions
and arrived at this definition. I have not added the copy
constructor/assignment operators to this class yet.

template <class TYPE, class ARG_TYPE = const TYPE&>
class CBTree : public CObject
{
// Constructors
public:
CBTree();
// Attributes
public:
int GetCount() const;
// Operations
public:
BOOL Insert(ARG_TYPE newElement);
BOOL Remove(ARG_TYPE element);
void RemoveAll();
BOOL Find(ARG_TYPE element);
// Implementation
public:
virtual ~CBTree();
};

I think this looks a little bit better then last time, but a question about
the "Find" function and the iterator stuff. I know the STL and OO devotees
will probably recommend I have the iterator as a seperate object, but as
this is an MFC class, I am being pushed into wrapping everything into one
simple to use class. Looking at other examples of template/MFC classes, they
use a POSITION object which is essentially a, yes, you guessed it, arbitrary
position pointer variable.

So I might change the Find method to:

POSITION Find(ARG_TYPE element) const;

where POSITION would be NULL if the element is not found. Otherwise it would
be an internal representation of the position, such as the pointer to the
node, similarly I could have a function:

POSITION GetRoot() const;

Now several of you suggested hiding the implementation from the user, so
does it make sense to have functions like:

POSITION GetNext(POSITION& pos, left/right);

or maybe something that returns the element at the same time? such as:

POSITION GetNext(POSITION& pos, left/right, ARG_TYPE element);

or maybe a

ARG_TYPE GetElement(POSITION& pos);

type function instead?

ie, how can I phrase the navigation functions while hiding the node details
from the user? Have GetLeft and GetRight and GetParent functions seem to be
exposing details of the implementation.

 

[Thomas Matthews]

I took the advice from the group and got rid of the node accessor functions
and arrived at this definition. I have not added the copy
constructor/assignment operators to this class yet.

template <class TYPE, class ARG_TYPE = const TYPE&>
class CBTree : public CObject
{
// Constructors
public:
CBTree();
// Attributes
public:
int GetCount() const;
// Operations
public:
BOOL Insert(ARG_TYPE newElement);
BOOL Remove(ARG_TYPE element);
void RemoveAll();
BOOL Find(ARG_TYPE element);
// Implementation
public:
virtual ~CBTree();
};

I think this looks a little bit better then last time, but a question about
the "Find" function and the iterator stuff. I know the STL and OO devotees
will probably recommend I have the iterator as a seperate object, but as
this is an MFC class, I am being pushed into wrapping everything into one
simple to use class. Looking at other examples of template/MFC classes, they
use a POSITION object which is essentially a, yes, you guessed it, arbitrary
position pointer variable.

So I might change the Find method to:

POSITION Find(ARG_TYPE element) const;

where POSITION would be NULL if the element is not found. Otherwise it would
be an internal representation of the position, such as the pointer to the
node, similarly I could have a function:

POSITION GetRoot() const;

Now several of you suggested hiding the implementation from the user, so
does it make sense to have functions like:

POSITION GetNext(POSITION& pos, left/right);

or maybe something that returns the element at the same time? such as:

POSITION GetNext(POSITION& pos, left/right, ARG_TYPE element);

or maybe a

ARG_TYPE GetElement(POSITION& pos);

type function instead?

ie, how can I phrase the navigation functions while hiding the node details
from the user? Have GetLeft and GetRight and GetParent functions seem to be
exposing details of the implementation.

How about iterators?
A "for_each" method.
Check out the SGI STL website and read the definitions
of containers.


--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book
http://www.sgi.com/tech/stl -- Standard Template Library

 

[John Harrison]

[snip]

Now several of you suggested hiding the implementation from the user, so
does it make sense to have functions like:

POSITION GetNext(POSITION& pos, left/right);

or maybe something that returns the element at the same time? such as:

POSITION GetNext(POSITION& pos, left/right, ARG_TYPE element);

or maybe a

ARG_TYPE GetElement(POSITION& pos);

type function instead?

ie, how can I phrase the navigation functions while hiding the node details
from the user? Have GetLeft and GetRight and GetParent functions seem to be
exposing details of the implementation.

Separate methods for separate concepts. I would have

POSITION GetNext(const POSITION& pos);

POSITION GetPrevious(const POSITION& pos);

ARG_TYPE GetElement(const POSITION& pos);

john