Tree.hh

Go to the documentation of this file.

// 
// Copyright (C) 2009 Tero Pulkkinen
// Released under LGPL License.
//
// This file is part of Polygon.
//
// Polygon is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Polygon 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 General Public License for more details.
//
// You should have received a copy of the GNU Library General Public License
// along with Polygon.  If not, see <http://www.gnu.org/licenses/>.
//
 
 
#ifndef TREE_HH
#define TREE_HH
 
#include "Effect.hh"
#include "Event.hh"
#include <assert.h>
#include "VolumeObjects.hh"
#include <typeinfo>
#include <vector>
 
#if 0
 
template<class T>
class Tree
{
public:
  virtual int NumberOfLevels() const=0;
  virtual const Array<int, T> *TreeChilds(const Array<int, int> &path) const=0;
};
 
class TimeChange
{
public:
  virtual float Time(float time) const = 0;
};
class EmptyTimeChange : public TimeChange
{
public:
  virtual float Time(float time) const { return time; }
};
 
struct TreeNode
{
  mutable Matrix matrix;
  const BoxableFaceCollection *faces;
  bool quads; // false = triangles, true = quads
  mutable ShaderParameters *params;
  TimeChange *timechange;
  friend std::ostream &operator<<(std::ostream &o, const TreeNode &tn);
};
TreeNode matrix_treenode(Matrix m);
TreeNode faces_treenode(Matrix m, const BoxableFaceCollection *faces);
 
struct TreeNodeInternal
{
  mutable Matrix matrix;
  BoxableFaceCollection *faces;
  bool quads;
  ShaderParameters *params;
  Matrix current_level_matrix;
  friend std::ostream &operator<<(std::ostream &o, const TreeNodeInternal &tn);
  friend bool operator==(const TreeNodeInternal &n1, const TreeNodeInternal &n2);
};
class ModifyTree
{
public:
  virtual void Modify(float time)=0;
};
 
class TreeNodeCollection : public Array<int, TreeNode>, public ModifyTree
{
public:
};
 
 
class EventNodes : public TreeNodeCollection
{
public:
};
class MatrixFacesNodes : public TreeNodeCollection
{
public:
  MatrixFacesNodes(BoxCollection &coll, BoxableFaceCollection &faces) : coll(coll), faces(faces) { }
  int Size() const { return coll.Size(); }
  TreeNode Index(int i) const
  {
    TreeNode n = faces_treenode(coll.Index(i), &faces);
    return n;
  }
  void Modify(float time)
  {
  }
private:
  BoxCollection &coll;
  BoxableFaceCollection &faces;
};
 
class MatrixNodes : public TreeNodeCollection
{
public:
  MatrixNodes(BoxCollection &coll) : coll(coll) { }
  int Size() const { return coll.Size(); }
  TreeNode Index(int i) const
  {
    TreeNode n = matrix_treenode(coll.Index(i));
    return n;
  }
  void Modify(float time)
  {
  }
private:
  BoxCollection &coll;
};
class TimedMatrixNodes : public TreeNodeCollection
{
public:
  TimedMatrixNodes(TimedMatrixPaths &paths) : paths(paths) { }
  int Size() const { return paths.Size(); }
  TreeNode Index(int i) const
  {
    TreeNode n = matrix_treenode(paths.Index(t, i));
    return n;
  }
  void Modify(float time)
  {
    t = time;
  }
 
private:
  mutable float t;
  TimedMatrixPaths &paths;
};
 
class EmptyTreeNodeCollection : public TreeNodeCollection
{
public:
  int Size() const { return 0; }
  TreeNode Index(int a) const { TreeNode n; n.faces = 0;  return n; }
  void Modify(float time) { }
};
 
class MatrixTreeNodeCollection : public TreeNodeCollection
{
public:
  MatrixTreeNodeCollection(TreeNodeCollection &coll) : coll(coll) { }
  int Size() const { return coll.Size(); }
  TreeNode Index(int i) const 
  { 
    TreeNode n = matrix_treenode(coll.Index(i).matrix); 
    return n; 
  }
  void Modify(float time) 
  {
    coll.Modify(time);
  }
private:
  TreeNodeCollection &coll;
};
 
class FacesTreeNodeCollection : public TreeNodeCollection
{
public:
  FacesTreeNodeCollection(TreeNodeCollection &coll) : coll(coll) { }
  int Size() const { return coll.Size(); }
  TreeNode Index(int i) const 
  { 
    TreeNode n = faces_treenode(Matrix::Identity(), coll.Index(i).faces); 
    return n; 
  }
  void Modify(float time) 
  {
    coll.Modify(time);
  }
private:
  TreeNodeCollection &coll;
};
 
class SingletonTreeNodeCollection : public TreeNodeCollection
{
public: // not very useful class, only for dynamic treenode generation
  SingletonTreeNodeCollection(TreeNode n) : n(n) { }
  void Modify(float time) { }
  int Size() const { return 1; }
  TreeNode Index(int a) const 
  { 
    return n;
  }
  
private:
  TreeNode n;
};
 
class RingTreeNodes : public TreeNodeCollection
{
public:
  RingTreeNodes()
    : pvarray(array, array+4),
      pointvector(pvarray),
      ring(pointvector, 100.0, 50),
      ring1(pointvector, 150.0,50),
      ring2(pointvector, 200.0,50),
      ring3(pointvector, 250.0,50)
  {
  }
  int Size() const { return 4; }
  TreeNode Index(int i) const
  {
    TreeNode n;
    switch(i)
      {
      case 0: n = faces_treenode(m,&ring); break;
      case 1: n = faces_treenode(m1,&ring1); break;
      case 2: n = faces_treenode(m2,&ring2); break;
      case 3: n = faces_treenode(m3,&ring3); break;
      default: std::cout << "RingTreeNode: ERROR! " << i << std::endl; break;
      }
    return n;
  }
  void Modify(float time)
  {
    m = Matrix::XRotation(time/100.0);
    m1 = Matrix::ZRotation(time/75.0);
    m2 = Matrix::XRotation(time/50.0);
    m3 = Matrix::ZRotation(time/25.0);
  }
private:
  Matrix m;
  Matrix m1;
  Matrix m2;
  Matrix m3;
  VectorArray<std::pair<Point,Vector> > pvarray;
  PointVectorCollectionConvert pointvector;
  RingElem ring;
  RingElem ring1;
  RingElem ring2;
  RingElem ring3;
  static std::pair<Point,Vector> array[];
};
 
class ObjectTree
{
public:
  virtual int NumberOfLevels() const=0;
  virtual const TreeNodeCollection *TreeChilds(const Array<int, int> &path) const=0;
};
 
class ArrayObjectTreeStatic : public ObjectTree
{
public:
  ArrayObjectTreeStatic(TreeNodeCollection &coll) : coll(coll) { }
  int NumberOfLevels() const { return 1; }
  const TreeNodeCollection *TreeChilds(const Array<int, int> &path) const
  {
    if (path.Size()==0)
      {
    return &coll;
      }
    return &empty;
  }
private:
  TreeNodeCollection &coll;
  EmptyTreeNodeCollection empty;
};
 
class ArrayObjectTreeDynamic : public ObjectTree
{
public:
  ArrayObjectTreeDynamic(TreeNodeCollection &coll) : /*coll(coll),*/ matrix(coll), faces(coll), singleton(0) { }
  int NumberOfLevels() const { return 2; }
  const TreeNodeCollection *TreeChilds(const Array<int, int> &path) const
  {
    int size = path.Size();
    if (size==0)
      {
    return &matrix;
      }
    if (size==1)
      {
    delete singleton;
    int index = path.Index(0);
    TreeNode n = faces.Index(index);
    singleton = new SingletonTreeNodeCollection(n);
    return singleton;
      }
 
    return &empty;
  }
  ~ArrayObjectTreeDynamic() { delete singleton; }
private:
  //TreeNodeCollection &coll;
  EmptyTreeNodeCollection empty;
  MatrixTreeNodeCollection matrix;
  FacesTreeNodeCollection faces;
  mutable SingletonTreeNodeCollection *singleton;
};
 
 
class ObjectTreeForest : public Array<int, ObjectTree*>
{
public:
};
typedef ArrayConvert<ObjectTreeForest, int, ObjectTree*> ObjectTreeForestConvert;
 
 
class ForestToTree : public ObjectTree
{
public:
  // Forest and nodes array sizes must match
  ForestToTree(ObjectTreeForest &forest, TreeNodeCollection &nodes) : forest(forest), nodes(nodes) { }
  virtual int NumberOfLevels() const 
  {
    int size = forest.Size();
    int count =0;
    for(int i=0;i<size;i++)
      {
    count = std::max(count, forest.Index(i)->NumberOfLevels());
      }
    return count;
  }
  virtual const TreeNodeCollection *TreeChilds(const Array<int, int> &path) const
  {
    int size = path.Size();
    if (size==0)
      {
    return &nodes;
      }
    int index = path.Index(0);
    ObjectTree *tree = forest.Index(index);
    SubArray<int,int> path2(path, 1, path.Size()-1);
    return tree->TreeChilds(path2);
  }
private:
  ObjectTreeForest &forest;
  TreeNodeCollection &nodes;
};
 
class AppendArray : public Array<int,int>
{
public:
  AppendArray(const Array<int,int> &arr, int i) : arr(arr), i(i) { }
  int Size() const { return arr.Size()+1; }
  int Index(int ii) const
  {
    if (ii==0) return i;
    return arr.Index(ii-1);
  }
private:
  const Array<int,int> &arr;
  int i;
};
 
class ObjectSubTree : public ObjectTree
{
public:
  ObjectSubTree(ObjectTree &tree, int index) : tree(tree), index(index) { }
  int NumberOfLevels() const { return tree.NumberOfLevels()-1; }
  const TreeNodeCollection *TreeChilds(const Array<int, int> &path) const
  {
    AppendArray arr(path, index);
    return tree.TreeChilds(arr);
  }
private:
  ObjectTree &tree;
  int index;
};
 
class TreeSize
{
public:
  virtual int SubTreeSize(VectorArray<int> &path) const=0;
};
 
class TreeSizeImpl : public TreeSize
{
public:
  TreeSizeImpl(ObjectTree &tree): tree(tree) { }
  int SubTreeSize(VectorArray<int> &path) const
  {
    const TreeNodeCollection *coll = tree.TreeChilds(path);
    int count = 0;
    int num = coll->Size();
    count += num;
    
    for(int i=0;i<num;i++)
      {
    path.push_back(i);
    count += SubTreeSize(path);
    path.pop_back();
      }
    return count;
  }
private:
  ObjectTree &tree;
};
 
class ObjectRanges
{
public:
  virtual int NumObjects() const=0;
  virtual int StartRange(int obj) const=0;
  virtual int EndRange(int obj) const=0;
  virtual Matrix Transform(int obj) const =0;
};
template<class T>
class RangeFaceCollectionArray : public Array<int, T>
{
public:
  RangeFaceCollectionArray(ObjectRanges &ranges, Array<int,T> &arr, int obj) : ranges(ranges), arr(arr), obj(obj) { }
  int Size() const { return ranges.EndRange(obj)-ranges.StartRange(obj); }
  T Index(int i) const
  {
    int startindex = ranges.StartRange(obj);
    return arr.Index(startindex+i);
  }
private:
  ObjectRanges &ranges;
  Array<int, T> &arr;
  int obj;
};
class SelectFaceCollection : public Array<int,std::pair<const FaceCollection*, bool> >
{
public:
  SelectFaceCollection(Array<int, TreeNodeInternal> &arr) : arr(arr) { }
  int Size() const { return arr.Size(); }
  std::pair<const FaceCollection *, bool> Index(int i) const
  {
    TreeNodeInternal n = arr.Index(i);
    return std::make_pair(n.faces, n.quads);
  }
private:
  Array<int, TreeNodeInternal> &arr;
};
 
class ApplyMatrix : public Array<int, TreeNodeInternal>
{
public:
  ApplyMatrix(Array<int,TreeNodeInternal> &arr) : arr(arr), elem(0) { }
  int Size() const { return arr.Size(); }
  TreeNodeInternal Index(int i) const
  {
    
    TreeNodeInternal n = arr.Index(i);
 
    if (!elem)
      {
    elem = new MatrixElem(*n.faces, n.current_level_matrix);
      }
    //delete elem;
    elem->SetMatrix(n.current_level_matrix);
    elem->SetNext(n.faces);
 
    //elem = new MatrixElem(*n.faces, n.current_level_matrix);
    n.faces = elem;
    return n;
  }
  ~ApplyMatrix() { delete elem; }
private:
  Array<int,TreeNodeInternal> &arr;
  mutable MatrixElem *elem;
};
 
class QuadTriChooser : public Array<int, FaceCollectionTri*>
{
public:
  QuadTriChooser(Array<int, std::pair<const FaceCollection*,bool> > &arr) : arr(arr), coll(0) { }
  int Size() const { return arr.Size(); }
  FaceCollectionTri *Index(int i) const
  {
    delete coll;
    std::pair<const FaceCollection*, bool> p = arr.Index(i);
    if (p.second)
      { // quads
    coll = new QuadsToTris(*p.first);
      }
    else
      {
    coll = new TrisToTris(*p.first); 
      }
    return coll;
  }
  ~QuadTriChooser() { delete coll; }
private:
  Array<int, std::pair<const FaceCollection*, bool> > &arr;
  mutable FaceCollectionTri *coll;
};
 
class CompressFaceCollectionArrays : public Array<int, FaceCollectionTri*>
{
public:
  CompressFaceCollectionArrays(ObjectRanges &ranges, Array<int, TreeNodeInternal> &arr) : ranges(ranges), arr(arr), range_arr(0), apply_matrix(0), select(0), chooser(0), /*iter(0),*/ oa(0)
 { }
  int Size() const
  {
    return ranges.NumObjects();
  }
  FaceCollectionTri *Index(int i) const
  {
    delete oa;
    //delete iter;
    delete chooser;
    delete select;
    delete apply_matrix;
    delete range_arr;
 
    range_arr = new RangeFaceCollectionArray<TreeNodeInternal>(ranges, arr, i);
    apply_matrix = new ApplyMatrix(*range_arr);
    select = new SelectFaceCollection(*apply_matrix);
    chooser = new QuadTriChooser(*select);
    //comp = new CompressObjectTri(*chooser);
    //iter = new IteratorArray<int, FaceCollectionTri*>(*chooser);
    oa = new ObjectArray2(*chooser);
    return oa;
  }
  ~CompressFaceCollectionArrays() 
  { 
    delete oa;
    //delete iter;
    delete chooser;
    delete select;
    delete apply_matrix;
    delete range_arr;
  }
private:
  ObjectRanges &ranges;
  Array<int, TreeNodeInternal> &arr;
  mutable RangeFaceCollectionArray<TreeNodeInternal> *range_arr;
  mutable ApplyMatrix *apply_matrix;
  mutable SelectFaceCollection *select;
  mutable QuadTriChooser *chooser;
  //CompressObjectTri *comp;
  //mutable IteratorArray<int, FaceCollectionTri*> *iter;
  mutable ObjectArray2 *oa;
};
class VBOArrays : public Element<const FaceCollectionVBO*>
{
public:
  VBOArrays(Array<int, FaceCollectionTri*> &arr) : oa(arr), vbo(oa) { }
  const FaceCollectionVBO *Elem() const
  {
    return &vbo;
  }
private:
  //IteratorArray<int, FaceCollectionTri*> iter;
  ObjectArray2 oa;
  VBO vbo;
};
 
class MemoizeRanges : public ObjectRanges
{
public:
  MemoizeRanges(ObjectRanges &ranges_) : count(ranges_.NumObjects()), ranges(ranges_), start_range(count), start_range_flag(count), end_range(count), end_range_flag(count), transform(count), transform_flag(count) 
  {
    for(int i=0;i<count;i++)
      { 
    start_range_flag[i] = 0;
    end_range_flag[i] = 0;
    transform_flag[i] = 0;
     }
  }
  virtual int NumObjects() const
  {
    return count;
  }
  virtual int StartRange(int obj) const
  {
    if (start_range_flag[obj]==0)
      {
    start_range_flag[obj]=1;
    start_range[obj]=ranges.StartRange(obj);
      }
    return start_range[obj];
  }
  virtual int EndRange(int obj) const
  {
    if (end_range_flag[obj]==0)
      {
    end_range_flag[obj]=1;
    end_range[obj]=ranges.EndRange(obj);
      }
    return end_range[obj];
 
  }
  virtual Matrix Transform(int obj) const
  {
    if (transform_flag[obj]==0)
      {
    transform_flag[obj]=1;
    transform[obj]=ranges.Transform(obj);
      }
    return transform[obj];
 
  }
 
private:
  int count;
  ObjectRanges &ranges;
  mutable std::vector<int> start_range;
  mutable std::vector<char> start_range_flag;
  mutable std::vector<int> end_range;
  mutable std::vector<char> end_range_flag;
  mutable std::vector<Matrix> transform;
  mutable std::vector<char> transform_flag;
 
};
 
class SharedArray : public Array<int, TreeNodeInternal>, public ObjectRanges
{
public:
  SharedArray(Array<int, TreeNodeInternal> &arr, ObjectRanges &ranges) : arr(arr), ranges(ranges), enabled_func(this, &SharedArray::Enabled), mapping_range_i(this, &SharedArray::MappingRangeI) { }
 
public:
  int Size() const
  {
    int c = arr.Size();
    int count = 0;
    for(int i=0;i<c;i++)
      {
    bool b = InsideEnabledRange(i);
    if (b) count++;
      }
    return count;
  }
  TreeNodeInternal Index(int i) const
  {
    return arr.Index(MappingArrayI(i));
  }
 
  int NumObjects() const
  {
    int c = ranges.NumObjects();
    int count = 0;
    for(int i=0;i<c;i++)
      {
    bool b = Enabled(i)==-1;
    if (b) count++;
      }
    return count;
  }
 
  int StartRange(int obj) const
  {
    int next = Enabled(obj);
    if (next == -1)
      {
    return MappingArray(ranges.StartRange(MappingRange(obj)));
      }
    else
      {
    return MappingArray(ranges.StartRange(MappingRange(next)));
      }
  }
  int EndRange(int obj) const
  {
    int next = Enabled(obj);
    if (next == -1)
      {
    return MappingArray(ranges.EndRange(MappingRange(obj)));
      }
    else
      {
    return MappingArray(ranges.EndRange(MappingRange(next)));
      }
  }
  Matrix Transform(int obj) const
  {
    return Matrix::Identity();
  }
public:
  // bigger -> smaller
  int MappingArray(int obj) const
  {
    int count = 0;
    int num = arr.Size();
    for(int i=0;i<num;i++)
      {
    if (i==obj) return count;
    bool b = InsideEnabledRange(i);
    if (b)
      {
        count++;
      }
      }
    return 0;
  }
 
  // smaller -> bigger
  int MappingArrayI(int obj) const
  {
    int count = 0;
    int num = arr.Size();
    for(int i=0;i<num;i++)
      {
    bool b = InsideEnabledRange(i);
    if (b)
      {
        if (count==obj) return i;
        count++;
      }
      }
    return 0;
  }
 
  
  bool InsideEnabledRange(int num) const
  {
    int size = ranges.NumObjects();
    for(int i=0;i<size;i++)
      {
    if (InsideRange(num,i))
      {
        if (Enabled(i)==-1)
          {
        return true;
          }
        else
          {
        return false;
          }
      }
      }
    return false;
  }
 
  bool InsideRange(int num, int obj) const
  {
    int start = ranges.StartRange(obj);
    int end = ranges.EndRange(obj);
    return num >=start && num < end;
  }
 
  // smaller -> bigger
  int MappingRange(int obj) const
  {
    int count = 0;
    int num = ranges.NumObjects();
    for(int i=0;i<num;i++)
      {
    bool b = Enabled(i)==-1;
    if (b)
      {
        if (count==obj) return i;
        count++;
      }
      }
    return 0;
  }
 
  // bigger -> smaller
  int MappingRangeI(int obj) const
  {
    int count = 0;
    int num = ranges.NumObjects();
    for(int i=0;i<num;i++)
      {
    if (i==obj) return count;
    bool b = Enabled(i)==-1;
    if (b)
      {
        count++;
      }
      }
    return 0;
  }
 
 
 
 
 
  // returns -1 if enabled
  // returns 0..obj-1 if disabled
  int Enabled(int obj) const
  {
    for(int i=0;i<obj;i++)
      {
    if (Equal(obj,i))
      return i;
      }
    return -1;
  }
 
  bool Equal(int obj1, int obj2) const
  {
    //if (obj1==obj2) return false;
    int start1 = ranges.StartRange(obj1);
    int end1 = ranges.EndRange(obj1);
    int start2 = ranges.StartRange(obj2);
    int end2 = ranges.EndRange(obj2);
    if (end1-start1 != end2-start2) return false;
    for(int i=0;i<end1-start1;i++)
      {
    TreeNodeInternal n1 = arr.Index(start1+i);
    TreeNodeInternal n2 = arr.Index(start2+i);
    if (n1 == n2) continue;
    return false;
      }
    return true;
  }
private:
  Array<int, TreeNodeInternal> &arr;
  ObjectRanges &ranges;
public:
  ForwardFunction<SharedArray, int, int> enabled_func;
  ForwardFunction<SharedArray, int, int> mapping_range_i;
};
 
class FlattenTree : public Array<int, TreeNodeInternal>, public ObjectRanges
{
public:
  FlattenTree(ObjectTree &tree) : tree(tree), size(sizeimpl), sizeimpl(tree) { }
  int Size() const 
  {
    VectorArray<int> vec;
    return size.SubTreeSize(vec);
  }
  int NumObjects() const
  {
    int count = 0;
    VectorArray<int> vec;
    const TreeNodeCollection *coll = tree.TreeChilds(vec);
    if (coll->Size() == 0) return 0;
    count += 1;
    int num = coll->Size();
    for(int i=0;i<num;i++)
      {
    ObjectSubTree subtree(tree, i);
    FlattenTree flat(subtree);
    count += flat.NumObjects();
      }
    return count;
  }
  Matrix Transform(int obj) const
  {
    if (obj==0) return Matrix::Identity();
    obj-=1;
    VectorArray<int> vec;
    const TreeNodeCollection *coll = tree.TreeChilds(vec);
    int num = coll->Size();
    int count = 0;
    for(int i=0;i<num;i++)
      {
    int oldcount = count;
    ObjectSubTree subtree(tree, i);
    FlattenTree flat(subtree);
    count += flat.NumObjects();
    if (count > obj)
      {
        return  flat.Transform(obj-oldcount) * coll->Index(i).matrix; 
      }
      }
    std::cout << "Flatten::Transform ERROR! " << std::endl;
    return Matrix::Identity();
  }
  int StartRange(int obj) const
  {
    if (obj==0) return 0;
    obj -= 1;
 
    VectorArray<int> vec;
    const TreeNodeCollection *coll = tree.TreeChilds(vec);
    int num = coll->Size();
    int count = 0;
    int count2 = 0;
    for(int i=0;i<num;i++)
      {
    int oldcount = count;
    int oldcount2 = count2;
    ObjectSubTree subtree(tree, i);
    FlattenTree flat(subtree);
    count += flat.NumObjects();
 
    vec.push_back(i);
    count2 += size.SubTreeSize(vec);
    vec.pop_back();
 
    if (count > obj)
      {
        int val = num + oldcount2 + flat.StartRange(obj-oldcount);
        return val;
      }
      }
    std::cout << "Flatten::Startrange ERROR! " << std::endl;
    return 0;
  }
  int EndRange(int obj) const
  {
    VectorArray<int> vec;
    const TreeNodeCollection *coll = tree.TreeChilds(vec);
    if (obj==0) return coll->Size();
    obj -= 1;
 
    int num = coll->Size();
    int count = 0;
    int count2 = 0;
    for(int i=0;i<num;i++)
      {
    int oldcount = count;
    int oldcount2 = count2;
    ObjectSubTree subtree(tree, i);
    FlattenTree flat(subtree);
    count += flat.NumObjects();
 
    vec.push_back(i);
    count2 += size.SubTreeSize(vec);
    vec.pop_back();
 
    if (count > obj)
      {
        int val = num + oldcount2 + flat.EndRange(obj-oldcount);
        return val;
      }
      }
    std::cout << "Flatten::Endrange ERROR! " << std::endl;
    return 0;
  }
  TreeNodeInternal Index(int i) const
  {
    VectorArray<int> vec;
    const TreeNodeCollection *coll = tree.TreeChilds(vec);
    if (i < coll->Size())
      {
    TreeNode n = coll->Index(i);
    TreeNodeInternal nn;
    nn.matrix = n.matrix;
    nn.faces = n.faces;
    nn.quads = n.quads;
    nn.params = n.params;
    nn.current_level_matrix = n.matrix;
    return nn;
      }
    int num = coll->Size();
    i -= num;
    int count = 0;
    for(int ii=0;ii<num;ii++)
      {
    int oldcount = count;
    vec.push_back(ii);
    count += size.SubTreeSize(vec);
    vec.pop_back();
    if (count > i)
      { // this one
        ObjectSubTree subtree(tree, ii);
        FlattenTree subtreeflat(subtree);
        TreeNodeInternal n = subtreeflat.Index(i-oldcount);
        n.matrix = coll->Index(ii).matrix * n.matrix;
        return n;
      }
      }
    std::cout << "ERROR: FlattenTree: i=" << i+num << std::endl;
    TreeNodeInternal n = { };
    return n;
  }
private:
  ObjectTree &tree;
  TreeSize &size;
  TreeSizeImpl sizeimpl;
};
 
class TreeObjectData : public ObjectDataArray
{
public:
  TreeObjectData(ObjectRanges &ranges, Function<int,int> &enabled, Function<int,int> &mapping_range_i) : ranges(ranges), enabled(enabled), mapping_range_i(mapping_range_i)  { }
  int Size() const { return ranges.NumObjects(); }
  ObjectData Index(int i) const
  {
    ObjectData d;
    d.matrix = ranges.Transform(i);
    int en = enabled.Index(i);
    if (en == -1) en = i;
    d.object = mapping_range_i.Index(en);
    d.params = 0; // TODO, ShaderParameters (flattentree needs to provide via ObjectRanges)
    return d;
  }
private:
  ObjectRanges &ranges;
  Function<int,int> &enabled;
  Function<int,int> &mapping_range_i;
};
class TreeStateInternal;
class TreeState
{
public:
  TreeState();
  ~TreeState();
  friend void PrepareTree(ObjectTree &tree, TreeState &treestate, VBOUpdate u);
  friend void RenderTree(ObjectTree &tree, float time, TreeState &treestate, VBOUpdate u);
private:
  TreeStateInternal *priv;
};
 
void PrepareTree(ObjectTree &tree, TreeState &treestate, VBOUpdate u=UpdateVertexNormalIndex);
void RenderTree(ObjectTree &tree, float time, TreeState &treestate, VBOUpdate u=UpdateVertexNormalIndex);
 
class RenderTreeCmds : public OpenGlCommands
{
public:
  RenderTreeCmds(ObjectTree &tree, float time) : tree(tree), time(time) { }
  void PreCalc();
  void Execute();
private:
  ObjectTree &tree;
  float time;
  TreeState treestate;
};
 
class PositionTree : public ObjectTree
{
public:
  PositionTree(ObjectTreeForest &forest, TimedMatrixPaths &positions) : nodes(positions), tree(forest, nodes) { }
  int NumberOfLevels() const { return tree.NumberOfLevels(); }
  const TreeNodeCollection *TreeChilds(const Array<int,int> &path) const
  {
    return tree.TreeChilds(path);
  }  
private:
  TimedMatrixNodes nodes;
  ForestToTree tree;
};
 
class CircleTree : public ObjectTree
{
public:
  CircleTree(ObjectTree &object_tree) : circle(400.0), sample(circle, 5), treenode(sample), forest_array(&object_tree, treenode.Size()), forest(forest_array), tree(forest, treenode) { }
  int NumberOfLevels() const { return tree.NumberOfLevels(); }
  const TreeNodeCollection *TreeChilds(const Array<int,int> &path) const
  {
    return tree.TreeChilds(path);
  }
private:
  CircleMatrixCurve circle;
  SampleMatrixCurve sample;
  MatrixNodes treenode;  
  DuplicateArray<int, ObjectTree*> forest_array;
  ObjectTreeForestConvert forest;
  ForestToTree tree;
};
 
class RingTreeEffect : public FrameAnim
{
public:
  RingTreeEffect(Render *r);
  void Init();
  bool Frame(float time);
private:
  RingTreeNodes nodes;
  ArrayObjectTreeDynamic tree;
  //CircleTree circle;
  TreeState vbostate;
 
  SingletonArray<ObjectTree*> forestarray;
  ObjectTreeForestConvert forest;
  CircleMatrixPath cpath;
  PositionTree pos;
};
class ManyCubesEffect : public FrameAnim
{
public:
  ManyCubesEffect(Render *r);
  void Init();
  bool Frame(float time);
private:
  CubeElem cube;
  MatrixElem me;
  RandomPointsInBox box;
  PointsToBoxCollection matrix;
  MatrixFacesNodes nodes;
  ArrayObjectTreeStatic tree;
  TreeState vbostate;
 
  CircleTree circle;
};
 
//
// New kind of trees
//
template<class Node, class Link>
class TTree
{
public:
  TTree(Node n) : n(n) { }
  TTree(typename std::vector<TTree<Node,Link> *> &children, 
    Node n, 
    std::vector<Link> links) 
    : children(children), n(n), links(links) { }
    
  int NumNodes() const { return children.size(); }
  Link &GetLink(int i) const { return links[i]; }
  Node &GetNode() const { return n; }
  TTree<Node,Link> *GetChildren(int i) const { }
  ~TTree() 
  {
    int s = children.size();
    for(int i=0;i<s;i++) delete children[i];
  }
private:
  std::vector<TTree*> children;
  Node n;
  std::vector<Link> links;
};
 
 
 
class TValue
{
public:
  virtual void *Value() const=0;
  virtual std::string Type() const=0;
};
template<class T>
class TTValue : public TValue
{
public:
  TTValue(T t) : t(t) { }
  void *Value() const { return &t; }
  std::string Type() const { return typeid(T).name(); }
private:
  T t;
};
 
class TFunction
{
public:
  virtual void *ret_val() const=0;
  virtual std::string ret_type() const=0;
  virtual int num_params() const=0;
  virtual void set_param(int i, void *val) const=0;
  virtual std::string param_type(int i) const=0;
  virtual void Execute()=0;
  virtual TValue *create_return_value()=0;
};
 
struct TFunctionArray
{
public:
  std::vector<TFunction*> vec;
};
 
template<class T, class R>
class TTFunction : public TFunction
{
public:
  TTFunction(Function<T,R> &f) : f(f) { }
  virtual void *ret_val() const { return ret_value; }
  virtual std::string ret_type() const { return typeid(R).name(); }
  virtual int num_params() const { return 1; }
  virtual void set_param(int i, void *val) const 
  {
    if (i==0)
      {
    param1 = val;
      }
  }
  virtual std::string param_type(int i) const { return typeid(T).name(); }
  virtual void Execute()
  {
    T t = *(T*)param1;
    r = f.Index(t);
    ret_value = (void*)&r;
  }
  virtual TValue *create_return_value() { 
    return new TTValue<R>(r);
  }
private:
  Function<T,R> &f;
  void *ret_value;
  R r;
  void *param1;
};
 
class DynamicTree : public TTree<TFunctionArray, TValue*>
{
};
 
#endif
 
#endif