This file is indexed.

/usr/include/terralib/kernel/TeRTree.h is in libterralib-dev 4.0.0-5ubuntu1.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
/************************************************************************************
TerraLib - a library for developing GIS applications.
Copyright � 2001-2007 INPE and Tecgraf/PUC-Rio.

This code is part of the TerraLib library.
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.

You should have received a copy of the GNU Lesser General Public
License along with this library.

The authors reassure the license terms regarding the warranties.
They specifically disclaim any warranties, including, but not limited to,
the implied warranties of merchantability and fitness for a particular purpose.
The library provided hereunder is on an "as is" basis, and the authors have no
obligation to provide maintenance, support, updates, enhancements, or modifications.
In no event shall INPE and Tecgraf / PUC-Rio be held liable to any party for direct,
indirect, special, incidental, or consequential damages arising out of the use
of this library and its documentation.
*************************************************************************************/
/*! \file   TeRTree.h
    \brief  This file contains an implementation of rtree data structures in main memory for two dimensions.
	\note   These data structures and algorithms MUST BE USED ONLY BY TerraLib kernel and should NOT be used by anyone because
	        THIS IS FOR INTERNAL USE ONLY.
    \author Gilberto Ribeiro de Queiroz <gribeiro@dpi.inpe.br>
*/

#ifndef  __TERRALIB_INTERNAL_RTREE_H
#define  __TERRALIB_INTERNAL_RTREE_H

#include "TeGeometry.h"
#include "TeGeometryAlgorithms.h"

/*! \brief This namespace contain the definitions of various Spatial Data Structures,
           like K-d-Tree and R-Tree, ONLY FOR INTERNAL USE (must NOT be used by anyone).
*/
namespace TeSAM
{
//! Class that represents a node of a TeRTree
/*!
	If level is 0 so this is a leaf node otherwise this is a internal node.

	WARNING:

	1. A branch is a union, so be carefull with the types used here!
	
 */
template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>
class TeRTreeNode
{
	public:

		//! Struct that represents a node-branch of a TeRTree
		/*!
			May be data or may be another subtree, if parents level is 0 so this is a data in a leaf node.

		*/
		struct TeRTreeBranch
		{
			TeBox rect_;	//!<	Bounding box for branch or object (if this is a leaf).

			union
			{
				TeRTreeNode* child_;		//!< Child node pointer.
				DATATYPE data_;				//!< Data Id or Ptr.
			};
		};

	public:

		int count_;			//!< Count.

		int level_;			//!< Leaf is zero, others positive.

		TeRTreeBranch branch_[MAXNODES];	//!< Branch.

		//! Constructor.


		TeRTreeNode()
			: count_(0), level_(-1)
		{
		}

		//! Returns true if this is a internal node.
        bool isInternalNode() const
		{
			return (level_ > 0);
		}

		//! Returns true if this is a leaf node.
        bool isLeaf() const
		{
			return (level_ == 0);
		}

		//! This method is used by split, when a node is re-filled.
		void init()
		{
			count_ = 0;

			level_ = -1;
		}

	private:

		//! No copy allowed
		TeRTreeNode(const TeRTreeNode& other);

		//! No copy allowed
		TeRTreeNode& operator=(const TeRTreeNode& other);

};	// end of class TeRTreeNode

//! A class that represents a two dimensional R-Tree
/*!	
	This implementation is based on:
	Antonin Guttman. R-Trees: A Dynamic Index Structure for Spatial Searching. ACM SIGMOD: International Conference on Management of Data, 1984, pp. 47-57.	

	and in his original source code. <BR>

	WARNING: <BR>

	1. Don't use this class! It is for TerraLib internal use. <BR>

	2. Only the basic methods for inserting and searching were implemented. <BR>

	3. In future we will implement: <BR>
		- the delete method. <BR>
		- the near query <BR>
		- point query <BR>
 */
template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>
class TeRTree
{
	public:

		//! Export this typename.
		typedef TeRTreeNode<DATATYPE, MAXNODES, MINNODES> TeRTreeNodeType;

		//! Export this typename.
		typedef typename TeRTreeNodeType::TeRTreeBranch TeRTreeBranch;

	protected:

		//! Structure of auxiliary variables for finding a split partition.
		struct TePartitionVars
		{
			int partition_[MAXNODES + 1];	//!< Auxiliary partition vector.
			int taken_[MAXNODES + 1];		//!< Flag to indicate that entry is ok.
			int count_[2];					//!< Number of entries in each new page.
			TeBox cover_[2];				//!< Auxiliary box of each new page.
			double area_[2];				//!< Auxiliary area of each new page.

			TeRTreeBranch branchBuf_[MAXNODES + 1];	//!< Auxiliary branch buffer.
			TeBox coverSplit_;						//!< Auxiliary box covering branchBuf.

			//! Initializes partition vars.
			void init()
			{
				count_[0] = 0;
				count_[1] = 0;

                for(int i = 0; i <= MAXNODES; ++i)
                {
                    taken_[i] = 0;
                    partition_[i] = -1;
                }
			}
		};		
		
		TeRTreeNodeType* root_;		//!< Pointer to root node

		TeBox mbr_;					//!< Bounding box of the tree
        		
		mutable unsigned int size_;			//!< The size of R-Tree (number of nodes)		

	public:

		//! Construtor
		TeRTree(const TeBox& mbr)
			: root_(0), mbr_(mbr), size_(0)
		{
			++size_;
			root_ = new TeRTreeNodeType();
            root_->level_ = 0;
		}

		//! Destructor
		~TeRTree()
		{
			clear();

			if(root_)
				delete root_;
		}

		//! The number of elements of the tree
		const unsigned int& size(void) const
		{
			return size_;
		}
		
		//! Return true if the tree is empty
		bool isEmpty(void) const
		{
			return (root_->count_ == 0);
		}

		//! Clear all tree nodes
		void clear(void)
		{
			if(root_)
			{
				erase(root_);
				root_ = 0;
				
				size_ = 1;
				root_ = new TeRTreeNodeType();
				root_->level_ = 0;
			}
		}

		//! Inserts item into the tree
		void insert(const TeBox& rect, const DATATYPE& data)
		{
			insert(rect, data, &root_, 0);
		}

		//! Removes item from tree
		bool remove(const TeBox& rect, const DATATYPE& data)
		{
			return remove(rect, data, &root_);
		}

		//! Range search query
		int search(const TeBox& rect, vector<DATATYPE>& report) const
		{
			int foundObjs = 0;

			if(root_)
				search(rect, root_, report, foundObjs);

			return foundObjs;
		}

		//! Sets the bounding box of all elements in the tree
		void setBox(const TeBox& mbr)
		{
			mbr_ = mbr;
		}

		//! Gets the bounding box of all elements in the tree
		const TeBox& getBox(void) const
		{
			return mbr_;
		}

	protected:

		//! Insert a data rectangle into an index structure.
		/*!
			Insert provides for splitting the root. <BR>
			Returns true if root was split, false if it was not. <BR>
			The level argument specifies the number of steps up from the leaf
			level to insert; e.g. a data rectangle goes in at level = 0. <BR>
			chooseLeaf does the recursion.
		*/
		inline bool insert(const TeBox& rect, const DATATYPE& data, TeRTreeNodeType** root, int level);

		//! Delete a data rectangle from an index structure.		   
		/*!
			Pass in a pointer to a Rect, the tid of the record, ptr to ptr to root node. <BR>
			Returns 1 if record not found, 0 if success. <BR>
			DeleteRect provides for eliminating the root.
		*/
		inline bool remove(const TeBox& rect, const DATATYPE& data, TeRTreeNodeType** root);

		//! Delete a rectangle from non-root part of an index structure.		   
		/*!
			Called by DeleteRect. <BR>
			Descends tree recursively,
			merges branches on the way back up.
		*/
		inline bool remove2(const TeBox& rect, const DATATYPE& data, TeRTreeNodeType* n, vector<TeRTreeNodeType*>& ee);

		//! Disconnect a dependent node.
		inline void disconBranch(TeRTreeNodeType* n, int i);

		//! Inserts a new data rectangle into the index structure.		   
		/*!
			Recursively descends tree, propagates splits back up.
			Returns false if node was not split.  Old node updated.
			If node was split, returns true and sets the pointer pointed to by
			new to point to the new node.  Old node updated to become one of two.
			The level argument specifies the number of steps up from the leaf
			level to insert; e.g. a data rectangle goes in at level = 0.
		*/
		inline bool chooseLeaf(const TeBox& rect, const DATATYPE& data, TeRTreeNodeType* node, TeRTreeNodeType** newNode, int level);

		//! Recursive range query
		inline void search(const TeBox& rect, TeRTreeNodeType* node, vector<DATATYPE>& report, int& foundObjs) const;

		//! Find the smallest rectangle that includes all rectangles in branches of a node
		inline TeBox nodeCover(TeRTreeNodeType* n) const;

		//! Combine two rectangles into larger one containing both
		inline TeBox combineRect(const TeBox& rectA, const TeBox& rectB) const;

		//! Add a branch to a node.
		/*!
			Split the node if necessary. <BR>
			Returns false if node not split. <BR>
			Old node updated. <BR>
			Returns true if node split, sets *new to address of new node. <BR>
			Old node updated, becomes one of two.
		*/
		inline bool addBranch(TeRTreeBranch* branch, TeRTreeNodeType* node, TeRTreeNodeType** newNode) const;

		//! Pick a branch.
		/*!
			Pick the one that will need the smallest increase
			in area to accomodate the new rectangle.  This will result in the
			least total area for the covering rectangles in the current node.
			In case of a tie, pick the one which was smaller before, to get
			the best resolution when searching.
		*/
		inline int pickBranch(const TeBox& rect, TeRTreeNodeType* node) const;

		//! Split a node.
		/*!
			Divides the nodes branches and the extra one between two nodes. <BR>
			Old node is one of the new ones, and one really new one is created.
		*/
		inline void splitNode(TeRTreeNodeType* node, TeRTreeBranch* branch, TeRTreeNodeType** newNode) const;

		//! Load branch buffer with branches from full node plus the extra branch.
		inline void getBranches(TeRTreeNodeType* n, TeRTreeBranch* b, TePartitionVars& p) const;

		//! Method 0 for finding a partition.
		/*!
		   First find two seeds, one for each group, well separated.
           Then put other rects in whichever group will be smallest after addition.
	    */
		inline void methodZero(TePartitionVars& p) const;

		//! Pick two rects from set to be the first elements of the two groups.
		/*!	
		   Pick the two that are separated most along any dimension, or overlap least.
           Distance for separation or overlap is measured modulo the width of the
           space covered by the entire set along that dimension.
	     */
		inline void pickSeeds(TePartitionVars& p) const;

		//! Put a branch in one of the groups
		inline void classify(int i, int group, TePartitionVars& p) const;

		//! Put each rect that is not already in a group into a group.
		/*!	
           Process one rect at a time, using the following hierarchy of criteria.
           In case of a tie, go to the next test.<BR>
           1) If one group already has the max number of elements that will allow
              the minimum fill for the other group, put r in the other.<BR>
           2) Put r in the group whose cover will expand less.  This automatically
		      takes care of the case where one group cover contains r.<BR>
		   3) Put r in the group whose cover will be smaller.  This takes care of the
              case where r is contained in both covers.<BR>
           4) Put r in the group with fewer elements.<BR>
           5) Put in group 1 (arbitrary).<BR>

           Also update the covers for both groups.
	     */
		inline void pigeonhole(TePartitionVars& p) const;

		//! Copy branches from the buffer into two nodes according to the partition.
		inline void loadNodes(TeRTreeNodeType* n, TeRTreeNodeType* q, TePartitionVars& p) const;

		//! Calculate rect area
		double rectArea(const TeBox& b) const
		{
			return b.width() * b.height();
		}

		//! Erases a node from the tree and all nodes below it.
		void erase(TeRTreeNodeType* node)
		{
			if(node->isLeaf())
			{
				delete node;

				return;
			}

			for(int i = 0u; i < node->count_; ++i)
				erase(node->branch_[i].child_);
	
			delete node;

			return;
		}

		//! Only to determine if the two box intersects withou using an epsilon
		bool rtreeBoxIntersects(const TeBox& bx1, const TeBox& bx2) const
		{
			return ::TeIntersects(bx1, bx2);
		}		

	private:

		//! No copy allowed
		TeRTree(const TeRTree& other);

		//! No copy allowed
		TeRTree& operator=(const TeRTree& other);

};	// end of class TeRTree


//------------------- Implementation of the templates classes

template<class DATATYPE, int MAXNODES, int MINNODES>
bool TeRTree<DATATYPE, MAXNODES, MINNODES>::insert(const TeBox& rect, const DATATYPE& data, TeRTreeNodeType** root, int level)
{
// this is the algorithm insert
    TeRTreeNodeType* newRoot;
	TeRTreeNodeType* newNode;
    TeRTreeBranch    branch;

    if(chooseLeaf(rect, data, *root, &newNode, level))  // I1
    {
// I4
// if root was split
// grow a new root, make tree taller
		++size_;
        newRoot = new TeRTreeNodeType();  

        newRoot->level_ = (*root)->level_ + 1;

// first half node
        branch.rect_  = nodeCover(*root);
        branch.child_ = *root;
        addBranch(&branch, newRoot, 0);

// second half node
        branch.rect_ = nodeCover(newNode);
        branch.child_ = newNode;        
		addBranch(&branch, newRoot, 0);

        *root = newRoot;

        return true;
    }

    return false;
}

template<class DATATYPE, int MAXNODES, int MINNODES>
bool TeRTree<DATATYPE, MAXNODES, MINNODES>::remove(const TeBox& rect, const DATATYPE& data, TeRTreeNodeType** root)
{
	int i;
	TeRTreeNodeType *t;
	vector<TeRTreeNodeType*> reInsertList;
	
	if(remove2(rect, data, *root, reInsertList))
	{
// if we are here, so we have found and deleted a data item

// reinsert any branches from eliminated nodes
		while(!reInsertList.empty())
		{
			t = reInsertList[0];
			for(i = 0; i < t->count_; ++i)
				insert(t->branch_[i].rect_, t->branch_[i].data_, root, t->level_);
	
// erase node from list
			reInsertList.erase(reInsertList.begin());

// remove node card from memory
			delete t;
			--size_;
		}
		
		/* check for redundant root (not leaf, 1 child) and eliminate */
		if(((*root)->count_ == 1) && ((*root)->isInternalNode()))
		{
			t = (*root)->branch_[0].child_;

			delete (*root);
			--size_;

			*root = t;
		}
		
		return true;
	}
	
	return false;
}

template<class DATATYPE, int MAXNODES, int MINNODES>
bool TeRTree<DATATYPE, MAXNODES, MINNODES>::remove2(const TeBox& rect, const DATATYPE& data, TeRTreeNodeType* n, vector<TeRTreeNodeType*>& ee)
{
	int i;	

	if(n->isInternalNode()) /* not a leaf node */
	{
		for(i = 0; i < n->count_; ++i)
		{
			if(rtreeBoxIntersects(rect, n->branch_[i].rect_))
			{
				if(remove2(rect, data, n->branch_[i].child_, ee))
				{
					if(n->branch_[i].child_->count_ >= MINNODES)
						n->branch_[i].rect_ = nodeCover(n->branch_[i].child_);
					else
					{
						/* not enough entries in child, eliminate child node */
						ee.push_back(n->branch_[i].child_);	//reInsert(n->branch_[i].child_, ee);
						disconBranch(n, i);
					}

					return true;	// found item
				}
			}
		}

		return false;	// din't find item
	}
	else  /* a leaf node */
	{
		for(i = 0; i < n->count_; ++i)
		{
			if(n->branch_[i].data_ == data)
			{
				disconBranch(n, i);
				return true;	// found item
			}
		}

		return false;	// didn't find item
	}
}

/*template<class DATATYPE, int MAXNODES, int MINNODES> void TeRTree<DATATYPE, MAXNODES, MINNODES>::reInsert(TeRTreeNodeType* n, vector<TeRTreeNodeType*>& ee)
{
	ee.push_back(n);
}*/

template<class DATATYPE, int MAXNODES, int MINNODES>
void TeRTree<DATATYPE, MAXNODES, MINNODES>::disconBranch(TeRTreeNodeType* n, int i)
{
// remove element copying the last element in array
	n->branch_[i] = n->branch_[n->count_ - 1];

	--(n->count_);
}

// CHOOSELEAF
template<class DATATYPE, int MAXNODES, int MINNODES>
bool TeRTree<DATATYPE, MAXNODES, MINNODES>::chooseLeaf(const TeBox& rect, const DATATYPE& data, TeRTreeNodeType* node, TeRTreeNodeType** newNode, int level)
{
	TeRTreeBranch    b;
	TeRTreeNodeType* n2;	
	
	if(node->level_ > level)
	{
// Still above level for insertion, go down tree recursively
		int i = pickBranch(rect, node);		// CL3

		if(!chooseLeaf(rect, data, node->branch_[i].child_, &n2, level))
		{
// child was not split
			node->branch_[i].rect_ = combineRect(rect, node->branch_[i].rect_);

			return false;
		}
		else		
		{
// child was split
			node->branch_[i].rect_ = nodeCover(node->branch_[i].child_);

			b.child_ = n2;
			b.rect_ = nodeCover(n2);

			return addBranch(&b, node, newNode);
		}
	}
	else if (node->level_ == level)
	{
// have reached level for insertion. Add rect, split if necessary

		b.rect_ = rect;
		//b.child_ = (TeRTreeNodeType*) data;
		b.data_ = data;

// child field of leaves contains tid of data record
		return addBranch(&b, node, newNode);
	}
	else
	{
// Not supposed to happen
		throw;
		return false;
	}
}

template<class DATATYPE, int MAXNODES, int MINNODES>
void TeRTree<DATATYPE, MAXNODES, MINNODES>::search(const TeBox& rect, TeRTreeNodeType* node, vector<DATATYPE>& report, int& foundObjs) const
{
	int i;
// S1
    if(node->isInternalNode()) // This is an internal node in the tree
	{
        for(i = 0; i < node->count_; ++i)
		{
            if(rtreeBoxIntersects(rect, node->branch_[i].rect_))
                search(rect, node->branch_[i].child_, report, foundObjs);
		}
	}
// S2
	else	// This is a leaf node
	{
        for(i = 0; i < node->count_; ++i)
		{
            if(rtreeBoxIntersects(rect, node->branch_[i].rect_))
			{
                DATATYPE& id = node->branch_[i].data_;

				report.push_back(id);

                ++foundObjs;
			}
		}
	}

	return;
}

template<class DATATYPE, int MAXNODES, int MINNODES>
TeBox TeRTree<DATATYPE, MAXNODES, MINNODES>::nodeCover(TeRTreeNodeType* n) const
{
	bool flag = true;

	TeBox r;
	
	for(int i = 0; i < n->count_; ++i)
	{
        if(flag)
		{
			r = n->branch_[i].rect_;
			flag = false;
		}
		else
			r = combineRect(r, n->branch_[i].rect_);
	}

	return r;
}

template<class DATATYPE, int MAXNODES, int MINNODES>
TeBox TeRTree<DATATYPE, MAXNODES, MINNODES>::combineRect(const TeBox& rectA, const TeBox& rectB) const
{
    TeBox newRect;

	newRect.x1_ = MIN(rectA.x1_, rectB.x1_);
	newRect.y1_ = MIN(rectA.y1_, rectB.y1_);
	newRect.x2_ = MAX(rectA.x2_, rectB.x2_);
	newRect.y2_ = MAX(rectA.y2_, rectB.y2_);

	return newRect;
}

template<class DATATYPE, int MAXNODES, int MINNODES>
bool TeRTree<DATATYPE, MAXNODES, MINNODES>::addBranch(TeRTreeBranch* branch, TeRTreeNodeType* node, TeRTreeNodeType** newNode) const
{
    if(node->count_ < MAXNODES)		/* split won't be necessary */
	{
		node->branch_[node->count_] = *branch;

		++(node->count_);

		return false;
	}
	else
	{
        splitNode(node, branch, newNode);

		return true;
	}
}

template<class DATATYPE, int MAXNODES, int MINNODES>
int TeRTree<DATATYPE, MAXNODES, MINNODES>::pickBranch(const TeBox& rect, TeRTreeNodeType* node) const
{
// CL3
	bool flag = true;

	double bestIncr = -1.0;

	double bestArea = 0.;

    int best = 0;
	
	for(int i = 0; i < node->count_; ++i)
	{
		TeBox rr = node->branch_[i].rect_;
		double area = rectArea(rr);

		rr = combineRect(rect, rr);
        
		double increase = rectArea(rr) - area;

        if((increase <  bestIncr) || flag)
		{
			best = i;

            bestArea = area;
            bestIncr = increase;

            flag = false;
		}
		else if((increase == bestIncr) && (area < bestArea))
		{
			best = i;
			bestArea = area;
			bestIncr = increase;
		}
	}

	return best;
}

template<class DATATYPE, int MAXNODES, int MINNODES>
void TeRTree<DATATYPE, MAXNODES, MINNODES>::splitNode(TeRTreeNodeType* node, TeRTreeBranch* branch, TeRTreeNodeType** newNode) const
{
    TePartitionVars partitions;

// load all the branches into a buffer, initialize old node
	int level = node->level_;

	getBranches(node, branch, partitions);

// find partition
	methodZero(partitions);

// put branches from buffer into 2 nodes according to chosen partition
	++size_;

	*newNode = new TeRTreeNodeType();
	(*newNode)->level_ = node->level_ = level;

	loadNodes(node, *newNode, partitions);
}

template<class DATATYPE, int MAXNODES, int MINNODES>
void TeRTree<DATATYPE, MAXNODES, MINNODES>::getBranches(TeRTreeNodeType* n, TeRTreeBranch* b, TePartitionVars& p) const
{
	int i;
// load the branch buffer
	for(i = 0; i < MAXNODES; ++i)
	{
		p.branchBuf_[i] = n->branch_[i];
	}

	p.branchBuf_[MAXNODES] = *b;

// calculate rect containing all in the set
	p.coverSplit_ = p.branchBuf_[0].rect_;

	for(i = 1; i <= MAXNODES; ++i)
		p.coverSplit_ = combineRect(p.coverSplit_, p.branchBuf_[i].rect_);

	n->init();
}

template<class DATATYPE, int MAXNODES, int MINNODES>
void TeRTree<DATATYPE, MAXNODES, MINNODES>::methodZero(TePartitionVars& p) const
{
	p.init();
	pickSeeds(p);
	pigeonhole(p);
}

template<class DATATYPE, int MAXNODES, int MINNODES>
void TeRTree<DATATYPE, MAXNODES, MINNODES>::pickSeeds(TePartitionVars& p) const
{
	double w;
	double separation;
	double bestSep;
	double width[2];
	int leastUpper[2];
	int greatestLower[2];
	int seed0;
	int seed1;
	int i;
// LPS1
// find the rectangles farthest out in each direction along dimens "x"
	greatestLower[0] = leastUpper[0] = 0;

	for(i = 1; i <= MAXNODES; ++i)
	{
		TeBox& r = p.branchBuf_[i].rect_;

		if(r.x1_ > p.branchBuf_[greatestLower[0]].rect_.x1_)
			greatestLower[0] = i;

		if(r.x2_ < p.branchBuf_[leastUpper[0]].rect_.x2_)
			leastUpper[0] = i;
	}

// LPS2
// LPS3
// find the width of the whole collection along this dimension
	width[0] = p.coverSplit_.x2_ - p.coverSplit_.x1_;

// find the rectangles farthest out in each direction along dimens "y"
	greatestLower[1] = leastUpper[1] = 0;

	for(i = 1; i <= MAXNODES; ++i)
	{
		TeBox& r = p.branchBuf_[i].rect_;

		if(r.y1_ > p.branchBuf_[greatestLower[1]].rect_.y1_)
			greatestLower[1] = i;

		if(r.y2_ < p.branchBuf_[leastUpper[1]].rect_.y2_)
			leastUpper[1] = i;
	}

// LPS2
// LPS3
// find the width of the whole collection along this dimension
	width[1] = p.coverSplit_.y2_ - p.coverSplit_.y1_;


// pick the best separation dimension and the two seed rects

// divisor for normalizing by width

// x
	if(width[0] == 0.0)
		w = 1.0;
	else
		w = width[0];

	TeBox rlow  = p.branchBuf_[leastUpper[0]].rect_;
    TeBox rhigh = p.branchBuf_[greatestLower[0]].rect_;

    seed0 = leastUpper[0];
	seed1 = greatestLower[0];
    
	bestSep = (rhigh.x1_ - rlow.x2_) / w;

// y
	if(width[1] == 0.0)
		w = 1.0;
	else
		w = width[1];

	rlow  = p.branchBuf_[leastUpper[1]].rect_;
    rhigh = p.branchBuf_[greatestLower[1]].rect_;

    separation = (rhigh.y1_ - rlow.y2_) / w;

// LPS3
	if(separation > bestSep)
	{
		seed0 = leastUpper[1];
		seed1 = greatestLower[1];

		bestSep = separation;
	}

	if(seed0 != seed1)
	{
		classify(seed0, 0, p);
		classify(seed1, 1, p);
	}
}

template<class DATATYPE, int MAXNODES, int MINNODES>
void TeRTree<DATATYPE, MAXNODES, MINNODES>::classify(int i, int group, TePartitionVars& p) const
{
    p.partition_[i] = group;
	p.taken_[i] = 1;

	if(p.count_[group] == 0)
		p.cover_[group] = p.branchBuf_[i].rect_;
	else
		p.cover_[group] = combineRect(p.branchBuf_[i].rect_, p.cover_[group]);

	p.area_[group] = rectArea(p.cover_[group]);

	++(p.count_[group]);
}

template<class DATATYPE, int MAXNODES, int MINNODES>
void TeRTree<DATATYPE, MAXNODES, MINNODES>::pigeonhole(TePartitionVars& p) const
{
	TeBox newCover[2];
	
	double newArea[2];
	double increase[2];

	for(int i = 0; i <= MAXNODES; ++i)
	{
		if(p.taken_[i] == 0)
		{
// if one group too full, put rect in the other regardless
			if(p.count_[0] >= (MAXNODES + 1 - MINNODES))
			{
				classify(i, 1, p);

				continue;
			}
			else if(p.count_[1] >= (MAXNODES + 1 - MINNODES))
			{
				classify(i, 0, p);

				continue;
			}

// find the areas of the two groups' old and new covers
			for(int group = 0; group < 2; ++group)
			{
				if(p.count_[group] > 0)
				{
					newCover[group] = combineRect(p.branchBuf_[i].rect_, p.cover_[group]);
				}
				else
				{
					newCover[group] = p.branchBuf_[i].rect_;
				}

				newArea[group] = rectArea(newCover[group]);
				increase[group] = newArea[group] - p.area_[group];
			}

// put rect in group whose cover will need to expand less
			if(increase[0] < increase[1])
				classify(i, 0, p);
			else if(increase[1] < increase[0])
				classify(i, 1, p);
// put rect in group that will have a smaller area cover
			else if(p.area_[0] < p.area_[1])
				classify(i, 0, p);
			else if(p.area_[1] < p.area_[0])
				classify(i, 1, p);
// put rect in group with fewer elements
			else if(p.count_[0] < p.count_[1])
				classify(i, 0, p);
			else
				classify(i, 1, p);
		}
	}
}

template<class DATATYPE, int MAXNODES, int MINNODES>
void TeRTree<DATATYPE, MAXNODES, MINNODES>::loadNodes(TeRTreeNodeType* n, TeRTreeNodeType* q, TePartitionVars& p) const
{
	for(int i = 0; i <= MAXNODES; ++i)
	{
		if(p.partition_[i] == 0)
			addBranch(&(p.branchBuf_[i]), n, 0);
		else if(p.partition_[i] == 1)
			addBranch(&(p.branchBuf_[i]), q, 0);
		//else
		//	throw;	// ERROR
	}
}
};	// end namespace TeSAM


#endif	// __TERRALIB_INTERNAL_RTREE_H