---

tree.h

Go to the documentation of this file.

//----------------------------------------------------------------------
//               The Motion Strategy Library (MSL)
//----------------------------------------------------------------------
//
// Copyright (c) University of Illinois and Steven M. LaValle.     
// All Rights Reserved.
//
// Permission to use, copy, and distribute this software and its
// documentation is hereby granted free of charge, provided that
// (1) it is not a component of a commercial product, and
// (2) this notice appears in all copies of the software and
//     related documentation.
//
// The University of Illinois and the author make no representations
// about the suitability or fitness of this software for any purpose.
// It is provided "as is" without express or implied warranty.
//----------------------------------------------------------------------
#
#ifndef MSL_TREE_H
#define MSL_TREE_H

#include <list>
#include <string>
using namespace std;


#include "vector.h"
#include "mslio.h"

class MSLTree;

class MSLNode {
 private:
  MSLVector state;
  MSLVector input;
  MSLNode* parent;
  list<MSLNode*> children;
  double time;
  double cost;
  int id;

  void* info;

 public:
  MSLVector State() const {return state; };

  inline MSLVector Input() const {return input; };

  inline MSLNode* Parent() {return parent; };
  inline list<MSLNode*> const Children() {return children; };
  
  inline double Time() const {return time; };

  inline double Cost() const {return cost; };

  inline void SetCost(const double &x) {cost = x; };

  inline void SetID(const int &i) {id = i; };

  inline int ID() const {return id; };

  void* GetInfo() {return info; };
  
  void SetInfo(void* in) {info = in; };

  //void ClearInfo() {if (!info) delete (MSLNodeInfo *) info; };
  //NOTE: Above incorrect design - shouldn't type the void* here

  MSLNode();
  MSLNode(void* pninfo);
  MSLNode(MSLNode* pn, const MSLVector &x, const MSLVector &u);
  MSLNode(MSLNode* pn, const MSLVector &x, const MSLVector &u, double t);
  MSLNode(MSLNode* pn, const MSLVector &x, const MSLVector &u, double t, void* pninfo);
  ~MSLNode() { children.clear(); /*ClearInfo();*/ };

  inline void AddChild(MSLNode *cn) { children.push_back(cn); }

  //friend istream& operator>> (istream& is, MSLNode& n);
  friend ostream& operator<< (ostream& os, const MSLNode& n);
  //friend istream& operator>> (istream& is, list<MSLNode*> & nl);
  friend ostream& operator<< (ostream& os, const list<MSLNode*> & nl);

  friend class MSLTree;
};


class MSLNodeLess {
 public:
  bool operator() (MSLNode* p, MSLNode* q) const {
    return p->Cost() < q->Cost();
  }
};


class MSLNodeGreater {
 public:
  bool operator() (MSLNode* p, MSLNode* q) const {
    return p->Cost() > q->Cost();
  }
};


class MSLTree {
 private:
  list<MSLNode*> nodes;
  MSLNode* root;
  int size;
 public:

  MSLTree();
  MSLTree(const MSLVector &x); // Argument is state of root node
  MSLTree(const MSLVector &x, void* nodeinfo);
  ~MSLTree();

  void MakeRoot(const MSLVector &x);
  MSLNode* Extend(MSLNode *parent, const MSLVector &x, const MSLVector &u);
  MSLNode* Extend(MSLNode *parent, const MSLVector &x, const MSLVector &u, 
                  double time);
  MSLNode* Extend(MSLNode *parent, const MSLVector &x, const MSLVector &u, 
                  double time, void* pninfo);

  list<MSLNode*> PathToRoot(MSLNode *n);
  MSLNode* FindNode(int nid);
  inline list<MSLNode*> Nodes() const { return nodes; };
  inline MSLNode* Root() {return root; };
  inline int Size() {return size;}

  void Clear();

  friend istream& operator>> (istream& is, MSLTree& n);
  friend ostream& operator<< (ostream& os, const MSLTree& n);
};

#endif

---

Web page maintained by Steve LaValle