parse_tree.h

这是linux下的进化计算的源代码。 === === === === === === === === === === === ===== check latest news at http:

		}

        adopt();
        updateAfterInsert();
		return *this;
    }

	void disown(void)
	{
		switch(arity())
		{
		case 3 : args[2].parent = 0; // no break!
		case 2 : args[1].parent = 0;
		case 1 : args[0].parent = 0; break;
		case 0 : break;
		default :
			{
				for (iterator it = begin(); it != end(); ++it)
				{
					it->parent = 0;
				}
			}
		}

	}

    void adopt(void)
    {
		switch(arity())
		{
		case 3 : args[2].parent = this; // no break!
		case 2 : args[1].parent = this;
		case 1 : args[0].parent = this; break;
		case 0 : break;
		default :
			{
				for (iterator it = begin(); it != end(); ++it)
				{
					it->parent = this;
				}
			}
		}
    }

    template <class It>
    void init(It b, It& last)
    {
        *this = *last;

#ifndef NDEBUG
        if (last == b && arity() > 0)
        {
            throw "subtree::init()";
        }
#endif

        for (int i = 0; i < arity(); ++i)
        {
            args[i].parent = 0;
            args[i].init(b, --last);
            args[i].parent = this;
        }

        updateAfterInsert();
    }

    T* content;
    subtree*			args;
    subtree*			parent;

	size_t _cumulative_size;
    size_t _depth;
    size_t _size;
};

// Continuing with parse_tree

    typedef T value_type;

	/* Constructors and Assignments */

    parse_tree(void) : _root(), pushed() {}
    parse_tree(const parse_tree& org) : _root(org._root), pushed(org.pushed) { }
    parse_tree(const subtree& sub) : _root(sub), pushed() { }

    template <class It>
        parse_tree(It b, It e) : _root(b, e), pushed() {}

    virtual ~parse_tree(void) {}

    parse_tree& operator=(const parse_tree& org) { return copy(org); }
	parse_tree& operator=(const subtree& sub)
		{ return copy(sub); }


	/* Equality and inequality */

	bool operator==(const parse_tree& other) const
	{ return _root == other._root; }

	bool operator !=(const parse_tree& other) const
	{ return !operator==(other); }

	/* Simple tree statistics */

    size_t size(void) const  { return _root.size(); }
	size_t depth(void) const { return _root.depth(); }
    void clear(void)        { _root.clear(); pushed.resize(0); }

	/* Evaluation (application), with an increasing number of user defined arguments */

	template <class RetVal>
	void apply(RetVal& v) const
		{ _root.apply(v); }

	template <class RetVal, class It>
		void apply(RetVal& v, It varValues) const
		{ _root.apply(v, varValues); }

    template <class RetVal, class It>
        void apply_mem_func(RetVal& v, It misc, void (T::* f)(RetVal&, typename subtree::iterator, It))
    {
        _root.apply_mem_func(v, misc, f);
    }

	//template <class RetVal, class It, class It2>
	//	void apply(RetVal& v, It varValues, It2 moreValues) const
	//	{ _root.apply(v, varValues, moreValues); }

	//template <class RetVal, class It, class It2, class It3>
	//	void apply(RetVal& v, It varValues, It2 moreValues, It3 evenMoreValues) const
	//	{ _root.apply(v, varValues, moreValues, evenMoreValues); }

    template <class Pred>
    void find_nodes(std::vector<subtree*>& result, Pred& p)
    {
        _root.find_nodes(result, p);
    }

    template <class Pred>
    void find_nodes(std::vector<const subtree*>& result, Pred& p) const
    {
        _root.find_nodes(p);
    }

	/* Customized Swap */
	void swap(parse_tree<T>& other)
	{
		do_the_swap(pushed, other.pushed);
		_root.swap(other._root);
	}

	/* Definitions of the iterators */

    class base_iterator
    {
    public :

        base_iterator() {}
        base_iterator(subtree* n)  { node = n; }

        base_iterator& operator=(const base_iterator& org)
        { node = org.node; return *this; }

        bool operator==(const base_iterator& org) const
        { return node == org.node; }
        bool operator!=(const base_iterator& org) const
        { return !operator==(org); }

		base_iterator operator+(size_t n) const
		{
			base_iterator tmp = *this;

			for(;n != 0; --n)
			{
				++tmp;
			}

			return tmp;
		}

		base_iterator& operator++(void)
        {
            subtree* parent = node->get_parent();

            if (parent == 0)
            {
                node = 0;
                return *this;
            }
            // else
	    typename subtree::iterator it;
            for (it = parent->begin(); it != parent->end(); ++it)
            {
                if (node == &(*it))
                    break;
            }

            if (it == parent->begin())
                node = parent;
            else
            {
                node = &(--it)->get_node(0);
            }

            return *this;
        }

        base_iterator operator++(int)
        {
            base_iterator tmp = *this;
            operator++();
            return tmp;
        }

    protected :
        subtree* node;
    };

    class iterator : public base_iterator
    {
    public:

        using base_iterator::node;

        typedef std::forward_iterator_tag iterator_category;
        typedef subtree value_type;
        typedef size_t distance_type;
        typedef size_t difference_type;
        typedef subtree* pointer;
        typedef subtree& reference;

        iterator() : base_iterator() {}
        iterator(subtree* n): base_iterator(n)  {}
        iterator& operator=(const iterator& org)
        { base_iterator::operator=(org); return *this; }

        subtree& operator*(void)  { return *node; }
        subtree* operator->(void) { return node; }
    };



    class embedded_iterator : public base_iterator
    {
    public:

        using base_iterator::node;

        typedef std::forward_iterator_tag iterator_category;
        typedef T value_type;
        typedef size_t distance_type;
        typedef size_t difference_type;
        typedef T* pointer;
        typedef T& reference;

        embedded_iterator() : base_iterator() {}
        embedded_iterator(subtree* n): base_iterator(n)  {}
        embedded_iterator& operator=(const embedded_iterator& org)
        { base_iterator::operator=(org); return *this; }

        T&  operator*(void)  { return **node; }
        T* operator->(void) { return &**node; }
    };

    class base_const_iterator
    {
    public:

        base_const_iterator() {}
        base_const_iterator(const subtree* n)  { node = n; }

        base_const_iterator& operator=(const base_const_iterator& org)
        { node = org.node; return *this; }

        bool operator==(const base_const_iterator& org) const
        { return node == org.node; }
        bool operator!=(const base_const_iterator& org) const
        { return !operator==(org); }

        base_const_iterator& operator++(void)
        {
            const subtree* parent = node->get_parent();

            if (parent == 0)
            {
                node = 0;
                return *this;
            }
            // else
	    typename subtree::const_iterator it;

            for (it = parent->begin(); it != parent->end(); ++it)
            {
                if (node == &(*it))
                    break;
            }

            if (it == parent->begin())
                node = parent;
            else
                node = &(--it)->get_node(0);
            return *this;
        }

        base_const_iterator operator++(int)
        {
            base_const_iterator tmp = *this;
            operator++();
            return tmp;
        }

    protected :

        const subtree* node;
    };

    class const_iterator : public base_const_iterator
    {
    public:

        using base_iterator::node;

        typedef std::forward_iterator_tag iterator_category;
        typedef const subtree value_type;
        typedef size_t distance_type;
        typedef size_t difference_type;
        typedef const subtree* pointer;
        typedef const subtree& reference;

        const_iterator() : base_const_iterator() {}
        const_iterator(const subtree* n): base_const_iterator(n)  {}
        const_iterator& operator=(const const_iterator& org)
        { base_const_iterator::operator=(org); return *this; }

        const subtree& operator*(void)  { return *node; }
        const subtree* operator->(void) { return node; }
    };

    class embedded_const_iterator : public base_const_iterator
    {
    public:

        using base_const_iterator::node;

		typedef std::forward_iterator_tag iterator_category;
		typedef const T value_type;
		typedef size_t distance_type;
		typedef size_t difference_type;
		typedef const T* pointer;
		typedef const T& reference;

        embedded_const_iterator() : base_const_iterator() {}
        embedded_const_iterator(const subtree* n): base_const_iterator(n)  {}
        embedded_const_iterator& operator=(const embedded_const_iterator& org)
        { base_const_iterator::operator=(org); return *this; }

		embedded_const_iterator operator+(size_t n) const
		{
			embedded_const_iterator tmp = *this;

			for(;n != 0; --n)
			{
				++tmp;
			}

			return tmp;
		}

        const T&  operator*(void)  const { return **node; }
        const T*  operator->(void) const { return node->operator->(); }
    };

	/* Iterator access */

    iterator begin(void)            { return iterator(&operator[](0)); }
    const_iterator begin(void) const { return const_iterator(&operator[](0)); }
    iterator end(void)               { return iterator(0); }
    const_iterator end(void) const   { return const_iterator(0);}

    embedded_iterator       ebegin(void)       { return embedded_iterator(&operator[](0)); }
    embedded_const_iterator ebegin(void) const { return embedded_const_iterator(&operator[](0)); }
    embedded_iterator       eend(void)         { return embedded_iterator(0); }
    embedded_const_iterator eend(void) const   { return embedded_const_iterator(0);}

    bool empty(void) const { return size() == 0; }
    bool valid(void) const { return pushed.empty(); }

	/* push_back */

	void push_back(const parse_tree<T>& tree)
	{
		if (!empty())
			pushed.push_back(_root);

		_root = tree.back();
	}

    void push_back(const T& t)
    {
        if (!empty())
            pushed.push_back(_root);

		_root = t;

        for (typename subtree::iterator it = _root.begin(); it != _root.end(); it++)
        {
			*it = pushed.back();
            pushed.pop_back();
        }

    }

	/* Access to subtrees */

    subtree& back(void)              { return _root; }
    const subtree& back(void) const  { return _root; }
    subtree& root(void)              { return _root; }
    const subtree& root(void) const  { return _root; }

    subtree& front(void)              { return _root[0]; }
    const subtree& front(void) const  { return _root[0]; }

    subtree& operator[](size_t i)
    { return const_cast<subtree&>(_root.get_node(i)); }
    const subtree& operator[](size_t i) const
    { return _root.get_node(i); }

    subtree& get_cumulative(size_t i)
    { return const_cast<subtree&>(_root.get_cumulative(i)); }
    const subtree& get_cumulative(size_t i) const
    { return get_cumulative(i); }

    private :

    parse_tree& copy(const parse_tree& org)
    {
        _root = org._root;
        pushed = org.pushed;

        return *this;
    }

	parse_tree& copy(const subtree& sub)
    { _root = sub; pushed.resize(0); return *this; }

    subtree _root;
    std::vector<subtree > pushed;
}; // end class parse_tree


} // end namespace gp_parse_tree

namespace std
{ // for use with stlport on MSVC

template <class T> inline
std::forward_iterator_tag iterator_category(typename gp_parse_tree::parse_tree<T>::embedded_iterator)
{
	return std::forward_iterator_tag();
}

template <class T> inline
ptrdiff_t*  distance_type(typename gp_parse_tree::parse_tree<T>::embedded_iterator)
{
	return 0;
}

template <class T> inline
std::forward_iterator_tag iterator_category(typename gp_parse_tree::parse_tree<T>::iterator)
{
	return std::forward_iterator_tag();
}

template <class T> inline
ptrdiff_t*  distance_type(typename gp_parse_tree::parse_tree<T>::iterator)
{
	return 0;
}

/* Put customized swaps also in std...

template<class T> inline
void swap(gp_parse_tree::parse_tree<T>& a, gp_parse_tree::parse_tree<T>& b)
{
    a.swap(b);
}

template<class T> inline
void iter_swap(std::vector<gp_parse_tree::parse_tree<T> >::iterator a, std::vector<gp_parse_tree::parse_tree<T> > b)
{
    a->swap(*b);
}*/


} // namespace std


#endif