//#####################################################################
// Copyright 2004-2007, Zhaosheng Bao, Ron Fedkiw, Geoffrey Irving, Sergey Koltakov, Frank Losasso, Andrew Selle, Jerry Talton.
// This file is part of PhysBAM whose distribution is governed by the license  contained in the accompanying file PHYSBAM_COPYRIGHT.txt.
//#####################################################################
#ifndef __Compute_Order_Using_KD_Tree__
#define __Compute_Order_Using_KD_Tree__

#include <Core/Arrays/ARRAY.h>
#include <Core/Vectors/VECTOR.h>
namespace PhysBAM{

/*
  A KD-tree is a binary tree.  We represent the tree as a complete binary tree.
  This allows us to represent the tree unambiguously as an array.  All rows
  (except possibly the last) are completely filled.  All nodes in the last row
  are as far to the left as possible.  The tree entries occur in the vector
  called tree in the following order.

          0
     1       2
   3   4   5   6
  7 8 9

  Note that it is possible to compute the indices for the children of a
  node from the index of the parent.  It is also possible to compute the
  index of the parent of a node from the index of a child.  Because of
  this, no pointers need to be stored.

  Note that the tree will have 2*X.m-1 entries.  The last X.m entries are the
  leaves, which have been reordered according to leaf_order.  (You can get the
  positions with X(leaf_order(i)).)  The first X.m-1 entries are not stored,
  since they are not required.
*/

// Updates leaf_order based on X.
template<class TV> void
Compute_Order_Using_KD_Tree(ARRAY<int>& leaf_order,const ARRAY<TV>& X);
}
#endif
