#pragma once
#include "basic_tree.h"
#include <set>
/************************************************************************************************
** This library was designed and developed by Mitchel Haas
** This software library is provided �as is� and any express or implied warranties, including,
** but not limited to, the implied warranties of merchantability and fitness for a particular
** purpose are disclaimed. The use of this software library is at the user's own risk.
** In no event shall the software designer/developer be liable for any direct, indirect,
** incidental, special, exemplary, or consequential damages (including, but not limited to,
** procurement of substitute goods or services; loss of use, data, or profits;
** or business interruption) however caused and on any theory of liability,
** whether in contract, strict liability (including negligence or otherwise)
** arising in any way out of the use of this software library.
**
** This library may be used freely, and redistributed,
** provided it is kept and distributed in it's entirety,
** and that all of it's contained files remain unmodified,
** in their original state, including this notice and the authors name.
*************************************************************************************************/
// forward declaration for deref comparison functor
template<typename stored_type, typename node_compare_type, typename node_order_compare_type >
class unique_tree;
// deref comparison functor, derive from binary function per Scott Meyer
template<typename stored_type, typename node_compare_type, typename node_order_compare_type >
struct unique_tree_deref_less : public std::binary_function<const unique_tree<stored_type, node_compare_type, node_order_compare_type>*, const unique_tree<stored_type, node_compare_type, node_order_compare_type>*, bool>
{
bool operator () (const unique_tree<stored_type, node_compare_type, node_order_compare_type>* lhs, const unique_tree<stored_type, node_compare_type, node_order_compare_type>* rhs) const
{
// call < on actual object
return (*lhs < *rhs);
}
};
// instanciates base_tree_type with type of container (set of unique_tree ptrs) to use for node and key comparisons
template<typename stored_type, typename node_compare_type = std::less<stored_type>, typename node_order_compare_type = node_compare_type >
class unique_tree : public basic_tree<stored_type, unique_tree<stored_type, node_compare_type, node_order_compare_type>, std::set<unique_tree<stored_type, node_compare_type, node_order_compare_type>*, unique_tree_deref_less<stored_type, node_compare_type, node_order_compare_type> > >
{
public:
// typedefs
typedef unique_tree<stored_type, node_compare_type, node_order_compare_type> tree_type;
typedef basic_tree<stored_type, unique_tree<stored_type, node_compare_type, node_order_compare_type>, std::set<unique_tree<stored_type, node_compare_type, node_order_compare_type>*, unique_tree_deref_less<stored_type, node_compare_type, node_order_compare_type> > > basic_tree_type;
typedef std::set<unique_tree<stored_type, node_compare_type, node_order_compare_type>*, unique_tree_deref_less<stored_type, node_compare_type, node_order_compare_type> > container_type;
friend class basic_tree<stored_type, unique_tree<stored_type, node_compare_type, node_order_compare_type>, std::set<unique_tree<stored_type, node_compare_type, node_order_compare_type>*, unique_tree_deref_less<stored_type, node_compare_type, node_order_compare_type> > >;
typedef typename basic_tree_type::iterator base_iterator;
typedef typename basic_tree_type::const_iterator base_const_iterator;
// constructors/destructor
unique_tree() : basic_tree_type(stored_type()), pOrphans(NULL), allowing_orphans(false) {}
unique_tree( const stored_type& stored_obj ) : basic_tree_type(stored_obj), pOrphans(NULL) {}
unique_tree( const tree_type& rhs ); // copy constructor
~unique_tree();
// less operator. since data's stored as a ptr, use a dereference less
friend bool operator < (const tree_type& lhs, const tree_type& rhs) { return node_compare_type()(*lhs.pData, *rhs.pData); }
// == operator.
friend bool operator == (const tree_type& lhs, const tree_type& rhs)
{ return (!node_compare_type()(*lhs.pData, *rhs.pData) && !node_compare_type()(*rhs.pData, *lhs.pData)); }
// deref less for find_deep
struct deref_key_compare
{
bool operator() (const tree_type* lhs, const tree_type* rhs) const { return node_compare_type()(*lhs->pData, *rhs->pData); }
};
friend struct deref_key_compare;
// deref less for ordered children set
struct deref_ordered_compare
{
bool operator() (const tree_type* lhs, const tree_type* rhs) const { return node_order_compare_type() (*lhs->pData, *rhs->pData); }
};
friend struct deref_ordered_compare;
// need to define iterators inline, because VC6 complains if not
class const_ordered_iterator : public std::iterator<std::bidirectional_iterator_tag, stored_type>
{
public:
// typedefs
typedef std::multiset<tree_type*, deref_ordered_compare> ordered_container_type;
// constructors/destructor
const_ordered_iterator() {}
const_ordered_iterator(typename ordered_container_type::const_iterator it_) : it(it_) {}
virtual ~const_ordered_iterator() {}
// overloaded operators
friend bool operator != ( const const_ordered_iterator& lhs, const const_ordered_iterator& rhs ) { return lhs.it != rhs.it; }
friend bool operator == ( const const_ordered_iterator& lhs, const const_ordered_iterator& rhs ) { return lhs.it == rhs.it; }
// public interface
const tree_type& operator*() const { return *it.operator *(); }
const tree_type* operator->() const { return *it.operator ->(); }
const_ordered_iterator& operator ++() { ++it; return *this; }
const_ordered_iterator operator ++(int) { const_ordered_iterator old(*this); ++*this; return old; }
const_ordered_iterator& operator --() { --it; return *this; }
const_ordered_iterator operator --(int) { const_ordered_iterator old(*this); --*this; return old; }
const tree_type* node() const { return *it; }
// data
protected:
typename ordered_container_type::const_iterator it;
};
friend class const_ordered_iterator;
class ordered_iterator : public const_ordered_iterator
{
public:
using const_ordered_iterator::it;
// constructors/destructor
ordered_iterator() {}
ordered_iterator(typename const_ordered_iterator::ordered_container_type::const_iterator it_) : const_ordered_iterator(it_) {}
// overloaded operators
friend bool operator != (const ordered_iterator& lhs, const ordered_iterator& rhs) { return lhs.it != rhs.it; }
friend bool operator == (const ordered_iterator& lhs, const ordered_iterator& rhs) { return lhs.it == rhs.it; }
// public interface
tree_type& operator*() { return *it.operator *(); }
tree_type* operator->() { return *it.operator ->(); }
base_iterator insert(const stored_type& stored_obj) const { return (*it)->insert(stored_obj); }
ordered_iterator& operator ++() { ++it; return *this; }
ordered_iterator operator ++(int) { ordered_iterator old(*this); ++*this; return old; }
ordered_iterator& operator --() { --it; return *this; }
ordered_iterator operator --(int) { ordered_iterator old(*this); --*this; return old; }
tree_type* node() { return *it; }
};
friend class ordered_iterator;
// public interface
public:
base_iterator insert(const stored_type& stored_obj);
base_iterator insert(const tree_type& tree_obj );
base_iterator insert( const stored_type& parent_obj, const stored_type& stored_obj);
void set(const stored_type& stored_obj) { basic_tree_type::set(stored_obj); }
void set(const tree_type& tree_obj);
base_iterator find_deep(const stored_type& stored_obj);
base_const_iterator find_deep(const stored_type& stored_obj) const;
const_ordered_iterator ordered_begin() const { return const_ordered_iterator(ordered_children.begin()); }
const_ordered_iterator ordered_end() const { return const_ordered_iterator(ordered_children.end()); }
ordered_iterator ordered_begin() { return ordered_iterator(ordered_children.begin()); }
ordered_iterator ordered_end() { return ordered_iterator(ordered_children.end()); }
const_ordered_iterator find_ordered(const stored_type& stored_obj) const;
bool erase(const stored_type& stored_obj);
template<typename key_type> bool erase(const key_type& key) { return erase( stored_type(key) ); }
void clear();
bool allow_orphans() const { return get_root()->allowing_orphans; }
void allow_orphans(bool allow) { get_root()->allowing_orphans = allow; }
const tree_type* get_orphans() const { return get_root()->pOrphans; }
bool is_orphan() const { const tree_type* root = get_root(); return (!root->empty() && root->ordered_children.empty()); }
private:
base_iterator insert(stored_type* pStored_obj);
void inform_grandparents( tree_type* pNew_child, tree_type* pParent );
bool check_for_duplicate(const stored_type& stored_obj, const tree_type* pParent) const;
const tree_type* get_root() const;
// data
private:
mutable std::set<tree_type*, deref_key_compare> descendents;
std::multiset<tree_type*, deref_ordered_compare> ordered_children;
mutable tree_type* pOrphans;
mutable bool allowing_orphans;
};
#include "unique_tree.inl"