1 /******************************************************************************
2  * Project:  libspatialindex - A C++ library for spatial indexing
3  * Author:   Marios Hadjieleftheriou, mhadji@gmail.com
4  ******************************************************************************
5  * Copyright (c) 2002, Marios Hadjieleftheriou
6  *
7  * All rights reserved.
8  *
9  * Permission is hereby granted, free of charge, to any person obtaining a
10  * copy of this software and associated documentation files (the "Software"),
11  * to deal in the Software without restriction, including without limitation
12  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
13  * and/or sell copies of the Software, and to permit persons to whom the
14  * Software is furnished to do so, subject to the following conditions:
15  *
16  * The above copyright notice and this permission notice shall be included
17  * in all copies or substantial portions of the Software.
18  *
19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
20  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
22  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
25  * DEALINGS IN THE SOFTWARE.
26 ******************************************************************************/
27 
28 #pragma once
29 
30 namespace SpatialIndex
31 {
32 	namespace MVRTree
33 	{
34 		class Index : public Node
35 		{
36 		public:
37 			virtual ~Index();
38 
39 		private:
40 			Index(MVRTree* pTree, id_type id, uint32_t level);
41 
42 			virtual NodePtr chooseSubtree(const TimeRegion& mbr, uint32_t level, std::stack<id_type>& pathBuffer);
43 			virtual NodePtr findLeaf(const TimeRegion& mbr, id_type id, std::stack<id_type>& pathBuffer);
44 
45 			virtual void split(
46 				uint32_t dataLength, byte* pData, TimeRegion& mbr, id_type id, NodePtr& left, NodePtr& right,
47 				TimeRegion& mbr2, id_type id2, bool bInsertMbr2 = false);
48 
49 			uint32_t findLeastEnlargement(const TimeRegion&) const;
50 			uint32_t findLeastOverlap(const TimeRegion&) const;
51 
52 			void adjustTree(Node*, std::stack<id_type>&);
53 			void adjustTree(Node* n, Node* nn, std::stack<id_type>& pathBuffer);
54 
55 			class OverlapEntry
56 			{
57 			public:
58 				uint32_t m_index;
59 				double m_enlargement;
60 				TimeRegionPtr m_original;
61 				TimeRegionPtr m_combined;
62 				double m_oa;
63 				double m_ca;
64 
compareEntries(const void * pv1,const void * pv2)65 				static int compareEntries(const void* pv1, const void* pv2)
66 				{
67 					OverlapEntry* pe1 = * (OverlapEntry**) pv1;
68 					OverlapEntry* pe2 = * (OverlapEntry**) pv2;
69 
70 					if (pe1->m_enlargement < pe2->m_enlargement) return -1;
71 					if (pe1->m_enlargement > pe2->m_enlargement) return 1;
72 					return 0;
73 				}
74 			}; // OverlapEntry
75 
76 			friend class MVRTree;
77 			friend class Node;
78 		}; // Index
79 	}
80 }
81 
82