← Back to branch summary

~ubuntu-branches/ubuntu/wily/grass/wily

« back to all changes in this revision

Viewing changes to lib/vector/rtree/index.h

Tags: 7.0.0~rc1+ds1-1~exp1
http://bugs.debian.org/776349
* New upstream release candidate.
* Repack upstream tarball, remove precompiled Python objects.
* Add upstream metadata.
* Update gbp.conf and Vcs-Git URL to use the experimental branch.
* Update watch file for GRASS 7.0.
* Drop build dependencies for Tcl/Tk, add build dependencies:
  python-numpy, libnetcdf-dev, netcdf-bin, libblas-dev, liblapack-dev
* Update Vcs-Browser URL to use cgit instead of gitweb.
* Update paths to use grass70.
* Add configure options: --with-netcdf, --with-blas, --with-lapack,
  remove --with-tcltk-includes.
* Update patches for GRASS 7.
* Update copyright file, changes:
  - Update copyright years
  - Group files by license
  - Remove unused license sections
* Add patches for various typos.
* Fix desktop file with patch instead of d/rules.
* Use minimal dh rules.
* Bump Standards-Version to 3.9.6, no changes.
* Use dpkg-maintscript-helper to replace directories with symlinks.
  (closes: #776349)
* Update my email to use @debian.org address.

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/vector/rtree/index.h
5
5
* AUTHOR(S):    Antonin Guttman - original code
6
6
*               Daniel Green (green@superliminal.com) - major clean-up
7
7
*                               and implementation of bounding spheres
 
8
*               Markus Metz - file-based and memory-based R*-tree
8
9
*               
9
10
* PURPOSE:      Multidimensional index
10
11
*
11
 
* COPYRIGHT:    (C) 2001 by the GRASS Development Team
 
12
* COPYRIGHT:    (C) 2010 by the GRASS Development Team
12
13
*
13
14
*               This program is free software under the GNU General Public
14
15
*               License (>=v2). Read the file COPYING that comes with GRASS
15
16
*               for details.
16
17
*****************************************************************************/
17
 
#ifndef _INDEX_
18
 
#define _INDEX_
 
18
#ifndef _R_TREE_INDEX_H_
 
19
#define _R_TREE_INDEX_H_
 
20
 
 
21
#include "rtree.h"
 
22
 
 
23
/* internal definitions and functions */
19
24
 
20
25
/* PGSIZE is normally the natural page size of the machine */
21
26
#define PGSIZE  512
22
 
#define NUMDIMS 3               /* number of dimensions */
23
 
 
24
 
/* typedef float RectReal; */
25
 
typedef double RectReal;
 
27
 
 
28
/* R*-tree: number of branches to be force-reinserted when adding a branch */
 
29
#define FORCECARD 3
 
30
 
 
31
#define NODETYPE(l, fd) ((l) == 0 ? 0 : ((fd) < 0 ? 1 : 2))
 
32
 
 
33
 
 
34
struct RTree_ListNode
 
35
{
 
36
    struct RTree_ListNode *next;
 
37
    struct RTree_Node *node;
 
38
};
 
39
 
 
40
struct RTree_ListFNode
 
41
{
 
42
    struct RTree_ListFNode *next;
 
43
    off_t node_pos;
 
44
};
 
45
 
 
46
struct RTree_ListBranch
 
47
{
 
48
    struct RTree_ListBranch *next;
 
49
    struct RTree_Branch b;
 
50
    int level;
 
51
};
 
52
 
 
53
/* functions */
 
54
 
 
55
/* index.c */
 
56
struct RTree_ListNode *RTreeNewListNode(void);
 
57
void RTreeFreeListNode(struct RTree_ListNode *);
 
58
void RTreeReInsertNode(struct RTree_Node *, struct RTree_ListNode **);
 
59
void RTreeFreeListBranch(struct RTree_ListBranch *);
 
60
 
 
61
/* indexm.c */
 
62
int RTreeSearchM(struct RTree *, struct RTree_Rect *,
 
63
                 SearchHitCallback *, void *);
 
64
int RTreeInsertRectM(struct RTree_Rect *, union RTree_Child, int, struct RTree *);
 
65
int RTreeDeleteRectM(struct RTree_Rect *, union RTree_Child, struct RTree *);
 
66
int RTreeValidChildM(union RTree_Child *child);
 
67
 
 
68
/* indexf.c */
 
69
int RTreeSearchF(struct RTree *, struct RTree_Rect *,
 
70
                 SearchHitCallback *, void *);
 
71
int RTreeInsertRectF(struct RTree_Rect *, union RTree_Child, int, struct RTree *);
 
72
int RTreeDeleteRectF(struct RTree_Rect *, union RTree_Child, struct RTree *);
 
73
int RTreeValidChildF(union RTree_Child *);
 
74
 
 
75
/* node.c */
 
76
void RTreeNodeCover(struct RTree_Node *, struct RTree_Rect *, struct RTree *);
 
77
int RTreeAddBranch(struct RTree_Branch *, struct RTree_Node *, struct RTree_Node **, 
 
78
            struct RTree_ListBranch **, struct RTree_Rect *, char *, struct RTree *);
 
79
int RTreePickBranch(struct RTree_Rect *, struct RTree_Node *, struct RTree *);
 
80
void RTreeDisconnectBranch(struct RTree_Node *, int, struct RTree *);
 
81
void RTreePrintNode(struct RTree_Node *, int, struct RTree *);
 
82
void RTreeTabIn(int);
 
83
void RTreeCopyBranch(struct RTree_Branch *, struct RTree_Branch *, struct RTree *);
 
84
 
 
85
/* rect.c */
 
86
void RTreeInitRect(struct RTree_Rect *, struct RTree *);
 
87
void RTreeNullRect(struct RTree_Rect *, struct RTree *);
 
88
RectReal RTreeRectArea(struct RTree_Rect *, struct RTree *);
 
89
RectReal RTreeRectSphericalVolume(struct RTree_Rect *, struct RTree *);
 
90
RectReal RTreeRectVolume(struct RTree_Rect *, struct RTree *);
 
91
RectReal RTreeRectMargin(struct RTree_Rect *, struct RTree *);
 
92
void RTreeCombineRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
 
93
int RTreeExpandRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
 
94
int RTreeCompareRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
26
95
 
27
96
/*-----------------------------------------------------------------------------
28
 
| Global definitions.
 
97
| Copy second rectangle to first rectangle.
29
98
-----------------------------------------------------------------------------*/
30
 
 
31
 
#ifndef TRUE
32
 
#define TRUE 1
33
 
#endif
34
 
#ifndef FALSE
35
 
#define FALSE 0
36
 
#endif
37
 
 
38
 
#define NUMSIDES 2*NUMDIMS
39
 
 
40
 
struct Rect
41
 
{
42
 
    RectReal boundary[NUMSIDES];        /* xmin,ymin,...,xmax,ymax,... */
43
 
};
44
 
 
45
 
struct Node;
46
 
 
47
 
struct Branch
48
 
{
49
 
    struct Rect rect;
50
 
    struct Node *child;
51
 
};
52
 
 
53
 
/* max branching factor of a node */
54
 
#define MAXCARD (int)((PGSIZE-(2*sizeof(int))) / sizeof(struct Branch))
55
 
 
56
 
struct Node
57
 
{
58
 
    int count;
59
 
    int level;                  /* 0 is leaf, others positive */
60
 
    struct Branch branch[MAXCARD];
61
 
};
62
 
 
63
 
struct ListNode
64
 
{
65
 
    struct ListNode *next;
66
 
    struct Node *node;
67
 
};
68
 
 
69
 
/*
70
 
 * If passed to a tree search, this callback function will be called
71
 
 * with the ID of each data rect that overlaps the search rect
72
 
 * plus whatever user specific pointer was passed to the search.
73
 
 * It can terminate the search early by returning 0 in which case
74
 
 * the search will return the number of hits found up to that point.
75
 
 */
76
 
typedef int (*SearchHitCallback) (int id, void *arg);
77
 
 
78
 
 
79
 
extern int RTreeSearch(struct Node *, struct Rect *, SearchHitCallback,
80
 
                       void *);
81
 
extern int RTreeInsertRect(struct Rect *, int, struct Node **, int depth);
82
 
extern int RTreeInsertRect1(struct Rect *, struct Node *, struct Node **, int depth);
83
 
extern int RTreeDeleteRect(struct Rect *, int, struct Node **);
84
 
extern int RTreeDeleteRect1(struct Rect *, struct Node *, struct Node **);
85
 
extern struct Node *RTreeNewIndex(void);
86
 
extern struct Node *RTreeNewNode(void);
87
 
extern void RTreeInitNode(struct Node *);
88
 
extern void RTreeFreeNode(struct Node *);
89
 
extern void RTreeDestroyNode(struct Node *);
90
 
extern void RTreePrintNode(struct Node *, int);
91
 
extern void RTreeTabIn(int);
92
 
extern struct Rect RTreeNodeCover(struct Node *);
93
 
extern void RTreeInitRect(struct Rect *);
94
 
extern struct Rect RTreeNullRect(void);
95
 
extern RectReal RTreeRectArea(struct Rect *);
96
 
extern RectReal RTreeRectSphericalVolume(struct Rect *R);
97
 
extern RectReal RTreeRectVolume(struct Rect *R);
98
 
extern struct Rect RTreeCombineRect(struct Rect *, struct Rect *);
99
 
extern int RTreeOverlap(struct Rect *, struct Rect *);
100
 
extern void RTreePrintRect(struct Rect *, int);
101
 
extern int RTreeAddBranch(struct Branch *, struct Node *, struct Node **);
102
 
extern int RTreePickBranch(struct Rect *, struct Node *);
103
 
extern void RTreeDisconnectBranch(struct Node *, int);
104
 
extern void RTreeSplitNode(struct Node *, struct Branch *, struct Node **);
105
 
 
106
 
extern int RTreeSetNodeMax(int);
107
 
extern int RTreeSetLeafMax(int);
108
 
extern int RTreeGetNodeMax(void);
109
 
extern int RTreeGetLeafMax(void);
 
99
#define RTreeCopyRect(r1, r2, t) memcpy((r1)->boundary, (r2)->boundary, (t)->rectsize)
 
100
 
 
101
 
 
102
/* split.c */
 
103
void RTreeSplitNode(struct RTree_Node *, struct RTree_Branch *, struct RTree_Node *, struct RTree *);
 
104
 
 
105
/* card.c */
 
106
int RTreeSetNodeMax(int, struct RTree *);
 
107
int RTreeSetLeafMax(int, struct RTree *);
 
108
int RTreeGetNodeMax(struct RTree *);
 
109
int RTreeGetLeafMax(struct RTree *);
 
110
 
 
111
/* io.c */
 
112
struct RTree_Node *RTreeGetNode(off_t, int, struct RTree *);
 
113
void RTreeNodeChanged(struct RTree_Node *, off_t , struct RTree *);
 
114
size_t RTreeRewriteNode(struct RTree_Node *, off_t, struct RTree *);
 
115
void RTreeAddNodePos(off_t, int, struct RTree *);
110
116
 
111
117
#endif /* _INDEX_ */