/***************************************************************************
 $RCSfile: tree.h,v $
                             -------------------
    cvs         : $Id: tree.h,v 1.6 2004/06/24 21:40:24 cstim Exp $
    begin       : Sun Dec 09 2001
    copyright   : (C) 2001 by Martin Preuss
    email       : martin@aquamaniac.de

 ***************************************************************************
 *                                                                         *
 *   This library is free software; you can redistribute it and/or         *
 *   modify it under the terms of the GNU Lesser General Public            *
 *   License as published by the Free Software Foundation; either          *
 *   version 2.1 of the License, or (at your option) any later version.    *
 *                                                                         *
 *   This library is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU     *
 *   Lesser General Public License for more details.                       *
 *                                                                         *
 *   You should have received a copy of the GNU Lesser General Public      *
 *   License along with this library; if not, write to the Free Software   *
 *   Foundation, Inc., 59 Temple Place, Suite 330, Boston,                 *
 *   MA  02111-1307  USA                                                   *
 *                                                                         *
 ***************************************************************************/




/*
 */


#ifndef C_TREE_H
#define C_TREE_H

#define t_TreeNode_ptr TreeNode<T>*

namespace HBCI {

/**
 * @short This class represents a node of the Tree.
 * @author Martin Preuss<martin@aquamaniac.de>
 */
template <class T> class DLLIMPORT TreeNode {
private:
public:
    TreeNode(T d,
                t_TreeNode_ptr pa=0,
                t_TreeNode_ptr ch=0,
                t_TreeNode_ptr prev=0,
                t_TreeNode_ptr nx=0)
        : data(d),previous(prev),next(nx),parent(pa),child(ch){};
    ~TreeNode() {};
    TreeNode(const TreeNode &n)
        : data(n.data),previous(0),next(0),parent(0),child(0){};

    T data;
    t_TreeNode_ptr previous;
    t_TreeNode_ptr next;
    t_TreeNode_ptr parent;
    t_TreeNode_ptr child;
};



/**
 * @short Helper class for Config
 */
template <class T> class DLLIMPORT Tree {
public:
  /**
   * Constructor.
   * This kind of Tree has ONE root entry, which must be set when creating
   * a Tree. The root node can never be removed.
   * @author Martin Preuss<martin@aquamaniac.de>
   */
  Tree(T root):_root(root) {};

  ~Tree() {clear();};

private:
  TreeNode<T> _root;

public:
  // Forward declaration to make gcc3.2 happy
  class const_iterator;

  /**
   * @short Use this one to browse through the tree. 
   *
   * This class lets you add and remove nodes, too.
   * @author Martin Preuss<martin@aquamaniac.de>
   */
  class DLLIMPORT iterator {
    friend class Tree;
    friend class const_iterator;
  private:
    t_TreeNode_ptr _current;

    iterator(t_TreeNode_ptr n):_current(n) {
    };

    /**
     * Deletes the given node and all his brothers/children
     */
    static bool _eraseBranch(t_TreeNode_ptr n) {
      while (n) {
        // delete all children
        if (n->child)
          if (!_eraseBranch(n->child))
            return false;
        // then delete this
        t_TreeNode_ptr tmp=n->next;
        delete n;
        n=tmp;
        // ok, that's it
      }
      return true;
    };

    /**
     * Copies the given node and all his brothers and children (the whole
     * family ;-) as new children of the current node.
     * This is designed for recursion.
     */
    bool _copyBranch(t_TreeNode_ptr src, bool brothers) {
        if (!_current || !src)
            return false;
        while(src) {
            t_TreeNode_ptr tmp;
            // add src as a child to current node
            tmp=_current;
            addChild(src->data, false, true);
            // check if src has children
            if (src->child) {
                // ok, it has, so copy them, too, with all brothers
                if (!_copyBranch(src->child, true))
                    return false;
            }
            // restore destination
            _current=tmp;
            // goto next brother, if desired
            if (brothers)
                src=src->next;
            else src=0;
        }
        return true;
    }

  public:
    /**
     * Constructor.
     * Do not give the argument directly, better do it this way:<BR>
     * Tree<int>::iterator iter; <BR>
     * to create an iterator, and <BR>
     * iter=Tree.root(); <BR>
     * to start with the root.
     * @author Martin Preuss<martin@aquamaniac.de>
     */
    iterator():_current(0) {
    };

    ~iterator() {};

    /**
     * Use this to check if the current entry is valid.
     * @author Martin Preuss<martin@aquamaniac.de>
     */
    bool isValid() const {
        return _current!=0;
    };

    /**
     * Invalidates this iterator.
     * @author Martin Preuss<martin@aquamaniac.de>
     */
    void invalidate() {
      _current=0;
    }

    /**
     * Compares two iterators. Returns true if both point to the same
     * object.
     * @author Martin Preuss<martin@aquamaniac.de>
     */
    bool operator==(const iterator &i) const {
      return _current==i._current;
    };

    /**
     * Compares two iterators. Returns true if both point to different
     * object.
     * @author Martin Preuss<martin@aquamaniac.de>
     */
    bool operator!=(const iterator &i) const {
      return _current!=i._current;
    };

    /**
     * Use this to get the data of the currently selected node.
     * @author Martin Preuss<martin@aquamaniac.de>
     */
    T &operator*() {
        return _current->data;
    };

    /**
     * Advances to the next neighbour, if possible.
     * This is called by "iter++"
     * @author Martin Preuss<martin@aquamaniac.de>
     */
    T& operator++() {
        return next();
    }

    /**
     * Advances to the next neighbour, if possible
     * This is called by "++iter"
     * @author Martin Preuss<martin@aquamaniac.de>
     */
    T& operator++(int) {
        t_TreeNode_ptr tmp=_current;
        next();
        return tmp->data;
    }


    /**
     * Selects the parent of the currently selected node.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return true if new node is valid
     */
    T& parent() {
        _current=_current->parent; 
	return _current->data;
    };

    /**
     * Selects the child of the currently selected node.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return true if new node is valid
     */
    T& child() {
        _current=_current->child; 
	return _current->data;
    };

    /**
     * Selects the next neighbour of the currently selected node.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return true if new node is valid
     */
    T& next() {
        _current=_current->next; 
	return _current->data;
    };

    /**
     * Selects the previous neighbour of the currently selected node.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return true if new node is valid
     */
    T& previous() {
        _current=_current->previous; 
	return _current->data;
    };

    /**
     * Selects the first brother of the currently selected node.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return true if new node is valid
     */
    T& firstBrother() {
        t_TreeNode_ptr tmp=0;
        while(_current) {
            tmp=_current;
            _current=_current->previous;
        }
        _current=tmp;
        return _current->data;
    };

    /**
     * Selects the last brother of the currently selected node.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return true if new node is valid
     */
    T &lastBrother() {
        t_TreeNode_ptr tmp=0;
        while(_current) {
            tmp=_current;
            _current=_current->next;
        }
        _current=tmp;
        return _current->data;
    };

    /**
     * Adds a child to the currently selected node. The new node will
     * NOT be selected automatically !
     * @author Martin Preuss<martin@aquamaniac.de>
     * @param data data to be inserted into the tree
     * @param ins if true the the new node will become the first child,
     * otherwise it will become the last child.
     * @param sel if true then the new node will be selected within this
     * iterator, otherwise it will not altered.
     */
    T& addChild(T data, bool ins=false, bool sel=false) {
      t_TreeNode_ptr tmp=_current;
      T *result;

      // if current has no child, it is easy
      if (!_current->child) {
        _current->child=new TreeNode<T>(data,_current);
        result=&_current->child->data;
        if (sel)
          _current=_current->child;
        return *result;
      }
      // else we must search the last child
      _current=_current->child;
        // should we insert the new node or append it as last child ?
      if (!ins) {
        // appending is desired, make it so
        lastBrother();
        _current->next=new TreeNode<T>(data,
                                          _current->parent,
                                          0,
                                          _current);
        result=&_current->next->data;
        // restore _current
        if (sel)
          _current=_current->next;
        else
          _current=tmp;
        return *result;
      }
      else {
        // insertion is desired, so make new node the new first one
        return insertNode(data,sel);
      }
    };

    /**
     * Inserts a new node at the current position. This throws a
     * segfault if you try to insert a node before the root.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return reference to the data inserted
     * @param data data to be inserted
     * @param sel if true then the new inserted node will be selected within
     * this iterator.
     */
    T &insertNode(T data, bool sel=false){
        t_TreeNode_ptr pa=_current->parent;
        t_TreeNode_ptr pr=_current->previous;
        t_TreeNode_ptr node=new TreeNode<T>(data);

        if (!pr)
            // no previous, so we are the first, tell the parent
            pa->child=node;
        else
            // otherwise tell the previous
            pr->next=node;
        // complete linkage of the new node
        node->parent=pa;
        node->previous=pr;
        node->next=_current;
        _current->previous=node;
        if (sel)
          _current=_current->previous;
        return node->data;
    };

    /**
     * Tells you if the currently selected node has a child.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return false if there is none
     */
    bool hasChild() const {
        return _current->child!=0;
    };

    /**
     * Tells you if the currently selected node has a parent.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return false if there is none
     */
    bool hasParent() const {
        return _current->parent!=0;
    };

    /**
     * Tells you if the currently selected node has a next neighbour.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return false if there is none
     */
    bool hasNext() const {
      return _current->next!=0;
    };

    /**
     * Tells you if the currently selected node has a left neighbour.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return false if there is none
     */
    bool hasPrevious() const {
      return _current->previous!=0;
    };

    /**
     * Deletes all the children of the currently selected node, BUT NOT that
     * node itself !
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return false on error
     */
    bool clearBranch() {
      if (!_current)
        return false;
      // erase all children
      if (_current->child) {
        if (!_eraseBranch(_current->child))
          return false;
        _current->child=0;
      }
      return true;
    };

    /**
     * Deletes all the children of the currently selected node and the
     * currently selected node itself. After this method returns this
     * iterator is invalid !
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return false on error
     */
    bool eraseBranch() {
      // first delete all children
      if (!clearBranch())
        return false;

      // then unlink the currently selected node
      t_TreeNode_ptr pr=_current->previous;
      t_TreeNode_ptr nx=_current->next;
      t_TreeNode_ptr pa=_current->parent;

      // is there a predecessor ?
      if (pr)
        // yes, unlink from him
        pr->next=nx;
      else
        // else unlink from parent, since we are the first
        pa->child=nx;
      // is there a successor ?
      if (nx)
        // yes, unlink from it
        nx->previous=pr;
      // now delete _current and invalidate
      delete _current;
      _current=0;

      // ok, that's it
      return true;
    };

    /**
     * Copies the node pointed to by the given iterator and all its
     * children as a new child of the currently selected one.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return false on error
     * @param src iterator pointing to the node to copy (this node might
     * also be in any tree)
     * @param childrenOnly FIXME: add docs here
     */
    bool copyIn(Tree<T>::iterator &src, bool childrenOnly=false) {
        if (!src._current)
            // given iterator is invalid
            return false;
        if (!childrenOnly)
            // copy the full branch
            return _copyBranch(src._current, false);
        // else only copy the children
        if (!src._current->child)
            // no children, error
            return false;
        return _copyBranch(src._current->child,true);
    };

  }; // end of iterator class



  /**
   * @short Use this one to browse through the tree if you don't want to
   * modify the tree. 
   * 
   * @author Christian Stimming <stimming@tuhh.de> and Martin
   * Preuss<martin@aquamaniac.de>
   */
  class DLLIMPORT const_iterator {
    friend class Tree;
  private:
    const t_TreeNode_ptr _current;

    const_iterator(const t_TreeNode_ptr n):_current(n) {
    };
  public:
    /**
     * Constructor.
     * Do not give the argument directly, better do it this way:<BR>
     * Tree<int>::const_iterator iter; <BR>
     * to create an iterator, and <BR>
     * iter=Tree.const_root(); <BR>
     * to start with the root.
     * @author Martin Preuss<martin@aquamaniac.de>
     */
    const_iterator():_current(0) {
    };
    /** Conversion constructor from a non-const iterator. */
    const_iterator(const iterator &iter):_current(iter._current) {
    };

    ~const_iterator() {};

    /**
     * Use this to check if the current entry is valid.
     * @author Martin Preuss<martin@aquamaniac.de>
     */
    bool isValid() const {
        return _current!=0;
    };

    /**
     * Compares two iterators. Returns true if both point to the same
     * object.
     * @author Martin Preuss<martin@aquamaniac.de>
     */
    bool operator==(const const_iterator &i) const {
      return _current==i._current;
    };
    bool operator==(const iterator &i) const {
      return _current==i._current;
    };

    /**
     * Compares two iterators. Returns true if both point to different
     * object.
     * @author Martin Preuss<martin@aquamaniac.de>
     */
    bool operator!=(const const_iterator &i) const {
      return _current!=i._current;
    };
    bool operator!=(const iterator &i) const {
      return _current!=i._current;
    };

    /**
     * Use this to get the data of the currently selected node.
     * @author Martin Preuss<martin@aquamaniac.de>
     */
    const T &operator*() const {
        return _current->data;
    };

    /**
     * Advances to the next neighbour, if possible.
     * This is called by "iter++"
     * @author Martin Preuss<martin@aquamaniac.de>
     */
    const T& operator++() {
        return next();
    }

    /**
     * Advances to the next neighbour, if possible
     * This is called by "++iter"
     * @author Martin Preuss<martin@aquamaniac.de>
     */
    const T& operator++(int) {
        const t_TreeNode_ptr tmp=_current;
        next();
        return tmp->data;
    }


    /**
     * Selects the parent of the currently selected node.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return true if new node is valid
     */
    const T& parent() {
        _current=_current->parent; 
	return _current->data;
    };

    /**
     * Selects the child of the currently selected node.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return true if new node is valid
     */
    const T& child() {
        _current=_current->child; 
	return _current->data;
    };

    /**
     * Selects the next neighbour of the currently selected node.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return true if new node is valid
     */
    const T& next() {
        _current=_current->next; 
	return _current->data;
    };

    /**
     * Selects the previous neighbour of the currently selected node.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return true if new node is valid
     */
    const T& previous() {
        _current=_current->previous; 
	return _current->data;
    };

    /**
     * Selects the first brother of the currently selected node.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return true if new node is valid
     */
    const T& firstBrother() {
        const t_TreeNode_ptr tmp=0;
        while(_current) {
            tmp=_current;
            _current=_current->previous;
        }
        _current=tmp;
        return _current->data;
    };

    /**
     * Selects the last brother of the currently selected node.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return true if new node is valid
     */
    const T &lastBrother() {
        const t_TreeNode_ptr tmp=0;
        while(_current) {
            tmp=_current;
            _current=_current->next;
        }
        _current=tmp;
        return _current->data;
    };

    /**
     * Tells you if the currently selected node has a child.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return false if there is none
     */
    bool hasChild() const {
        return _current->child!=0;
    };

    /**
     * Tells you if the currently selected node has a parent.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return false if there is none
     */
    bool hasParent() const {
        return _current->parent!=0;
    };

    /**
     * Tells you if the currently selected node has a next neighbour.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return false if there is none
     */
    bool hasNext() const {
      return _current->next!=0;
    };

    /**
     * Tells you if the currently selected node has a left neighbour.
     * @author Martin Preuss<martin@aquamaniac.de>
     * @return false if there is none
     */
    bool hasPrevious() const {
      return _current->previous!=0;
    };

  }; // end of const_iterator class

  /**
   * Returns an iterator that points to the root of the tree.
   * @author Martin Preuss<martin@aquamaniac.de>
   */
  iterator root() {
      return iterator(&_root);
  };

  /**
   * Returns an const_iterator that points to the root of the tree.
   * @author Martin Preuss<martin@aquamaniac.de>
   */
  const_iterator const_root() const {
      return const_iterator(&_root);
  };

  /**
   * Clears the tree (but not the root node, of course).
   */
  bool clear() {
    return root().clearBranch();
  }

};


} /* namespace HBCI */


#endif


