blob: 318ba0a7fa85ab7ff257e56c4d0da4b367bab28e (
plain)
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
|
/*
*
* Copyright (c) 2008--2012
* String Matching Group, Lab for Intelligent Information Processing Technology,
* Institute of Information Engineering, Chinese Academy of Sciences (IIE-CAS).
* All rights reserved.
*
* Written by: LIU YANBING ([email protected])
* Last modification: 2012-07-10
*
* This code is the exclusive and proprietary property of IIE-CAS. Usage for direct
* or indirect commercial advantage is not allowed without written permission from
* the authors.
*
*/
#ifndef H_INTERVAL_TREE_CPP_H
#define H_INTERVAL_TREE_CPP_H
#include "IntervalIndex.h"
class CIntervalTree : public CIntervalIndex
{
public:
struct stIntervalNode
{
bool isleaf;
unsigned int seperator;
std::vector<unsigned int> ids;
stIntervalNode * lchild;
stIntervalNode * rchild;
};
public:
CIntervalTree();
virtual ~CIntervalTree();
virtual long long PreProcessing(const std::vector<unsigned int>& a, const std::vector<unsigned int>& b);
virtual int Find(unsigned int key, unsigned int * result, unsigned int size);
private:
stIntervalNode * BuildBalancedTree(unsigned int a[], unsigned int n);
void AddInterval(stIntervalNode * pstCurrNode, unsigned int inf, unsigned int sup,
unsigned int a, unsigned int b, unsigned int id);
private:
stIntervalNode * m_pstRoot;
unsigned int m_uiNodeNum;
long long m_iMemBytes;
std::vector<unsigned int> m_IndexForMaxInt;
};
#endif
|
