1%%%%%%%%%%%%%%%%%%%
2% XLiFE++ is an extended library of finite elements written in C++
3%     Copyright (C) 2014  Lunéville, Eric; Kielbasiewicz, Nicolas; Lafranche, Yvon; Nguyen, Manh-Ha; Chambeyron, Colin
4%
5%     This program is free software: you can redistribute it and/or modify
6%     it under the terms of the GNU General Public License as published by
7%     the Free Software Foundation, either version 3 of the License, or
8%     (at your option) any later version.
9%     This program is distributed in the hope that it will be useful,
10%     but WITHOUT ANY WARRANTY; without even the implied warranty of
11%     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12%     GNU General Public License for more details.
13%     You should have received a copy of the GNU General Public License
14%     along with this program.  If not, see <http://www.gnu.org/licenses/>.
15%%%%%%%%%%%%%%%%%%%
16
17\section{The {\classtitle KdTree} class}
18
19The {\class KdTree} class implements the well known kdtree which is a binary tree where objects are separated using component by component separation. Usually objects are points but the following implementation is templated to deal with any class T that have components that can be separated. More precisely, the T class has to provide the following:
20\vspace{.1cm}
21\begin{lstlisting}[]{}
22T::SepValueType;
23T::operator()(int);
24T::dim();
25int Tcompare(const T& t, int c, const T::SepValueType& s);
26//return  -1 (t_c<s), 1 (t_c>s) or 0 (t_c=s)
27int maxSeparator(const T& t1, const T& tT2, int &c, T::SepValueType& s);
28// find the component index c where separation is maximal, update s as the middle value and return the comparison of t1 and t2 (1,-1,0)
29\end{lstlisting}
30\vspace{.3cm}
31Such tree may find the nearest object of a given object in a fast way ($n\log\,n$ in the most cases and $n$ in worst cases).\\
32
33The {\class KdTree} class is based on the {\class KdNode} class which is in fact the main class, {\class KdTree} handling the root node. A {\class KdNode} is either a  separation line (component that separates two points and value of separation) or a terminal leaf containing a separated object.
34
35\subsection*{{\classtitle KdNode} class}
36
37\vspace{.1cm}
38\begin{lstlisting}[]{}
39template <class T>
40class KdNode
41{
42private :
43   typedef typename T::SepValueType SvType;
44   KdNode * parent_;      //!< pointer to parent node
45   KdNode * left_;        //!< pointer to left node
46   KdNode * right_;       //!< pointer to right node
47   const T * obj_;        //!< object pointer linked to node
48   int separator_;        //!< separation component
49   SvType sv_;            //!< separation value
50}
51\end{lstlisting}
52\vspace{.3cm}
53It has two basic constructors, a destructor and a node insertion function
54\vspace{.1cm}
55\begin{lstlisting}[]{}
56KdNode();
57KdNode(const T *O,int s, KdNode * p);
58~KdNode();
59void insert(const T *);
60\end{lstlisting}
61\vspace{.3cm}
62The {\cmd insert} function is the fundamental function used in building of kdtree : it travels in tree up to find a free box containing the object to be inserted; if no free box is found, the last non empty box containing object to be inserted and an other object is split in two boxes. The tree obtained by this method has not an optimal balancing !
63\begin{figure}[H]
64\centering
65\includePict[width=8cm]{kdtree.pdf}
66\caption{exemple of separation of 2d points}
67\end{figure}
68The class provides some utitilities
69\vspace{.1cm}
70\begin{lstlisting}[]{}
71Number& depth(Number &) const;      //!< return node depth
72void print(std::ostream&, std::string &) const;
73void printBoxes(std::ostream &os, Box<SvType> b) const;
74template <class S>
75friend std::ostream& operator<<(std::ostream& os,const KdNode<S> & node);
76\end{lstlisting}
77\vspace{.3cm}
78and the important function to search the nearest object of a given object:
79\vspace{.1cm}
80\begin{lstlisting}[]{}
81void searchNearest(const T *, const T *&, SvType &);
82\end{lstlisting}
83\vspace{.3cm}
84\begin{figure}[H]
85\centering
86\includePict[width=8cm]{kdtree_search.pdf}
87\end{figure}
88
89\subsection*{{\classtitle KdTree} class}
90
91As already mentioned {\class KdTree} handles the root node of tree and mainly encapsulated the {\class KdNode} functions
92\vspace{.1cm}
93\begin{lstlisting}[]{}
94template <class T>
95class KdTree
96{
97private :
98 typedef typename T::SepValueType SvType;   //separator value type
99 KdNode<T>* root;                           //rootnode of the tree
100 Dimen dimT;                                //object dimension
101 }
102\end{lstlisting}
103\vspace{.3cm}
104\vspace{.1cm}
105\begin{lstlisting}[]{}
106KdTree() {root=new KdNode<T>();dimT=0;}
107KdTree(const std::vector<T>&);
108~KdTree() {delete root;};
109bool isVoid() const;
110Dimen dim() const;
111void insert(const T&);
112void insert(const std::vector<T>&);
113Number depth() const;
114const T* searchNearest(const T &) const;
115void print(std::ostream& out) const;
116template <typename R>
117 void printBoxes(std::ostream &os, const Box<R>& rb);
118template <typename R>
119 void printBoxes(const std::string& file, const Box<R>& rb);
120template <class S>
121   friend std::ostream& operator<<(std::ostream& os,const KdTree<S>& node);
122\end{lstlisting}
123\vspace{.3cm}
124\displayInfos{library=utils, header=KdTree.hpp, implementation=KdTree.hpp,
125test=test\_KdTree.cpp, header dep={space.h, config.h, utils.h}}
126