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
|
//------------------------------------------------------------------------------
// GB_bracket.h: definitions for GB_bracket
//------------------------------------------------------------------------------
// SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2022, All Rights Reserved.
// SPDX-License-Identifier: Apache-2.0
//------------------------------------------------------------------------------
#ifndef GB_BRACKET_H
#define GB_BRACKET_H
#include "GB.h"
//------------------------------------------------------------------------------
// GB_bracket_left
//------------------------------------------------------------------------------
// Given a sorted list X [kleft:kright], and a range imin:..., modify kleft so
// that the smaller sublist X [kleft:kright] contains the range imin:...
#if 0
// This method is no longer used but is kept here in case it is needed in
// the future.
static inline void GB_bracket_left
(
const int64_t imin,
const int64_t *restrict X, // input list is in X [kleft:kright]
int64_t *kleft,
const int64_t kright
)
{
// tighten kleft
int64_t len = kright - (*kleft) + 1 ;
if (len > 0 && X [(*kleft)] < imin)
{
// search for imin in X [kleft:kright]
int64_t pleft = (*kleft) ;
int64_t pright = kright ;
GB_TRIM_BINARY_SEARCH (imin, X, pleft, pright) ;
(*kleft) = pleft ;
}
}
#endif
//------------------------------------------------------------------------------
// GB_bracket_right
//------------------------------------------------------------------------------
// Given a sorted list X [kleft:kright], and a range ...:imax, modify kright so
// that the smaller sublist X [kleft:kright] contains the range ...:imax.
static inline void GB_bracket_right
(
const int64_t imax,
const int64_t *restrict X, // input list is in X [kleft:kright]
const int64_t kleft,
int64_t *kright
)
{
// tighten kright
int64_t len = (*kright) - kleft + 1 ;
if (len > 0 && imax < X [(*kright)])
{
// search for imax in X [kleft:kright]
int64_t pleft = kleft ;
int64_t pright = (*kright) ;
GB_TRIM_BINARY_SEARCH (imax, X, pleft, pright) ;
(*kright) = pleft ;
}
}
//------------------------------------------------------------------------------
// GB_bracket
//------------------------------------------------------------------------------
// Given a sorted list X [kleft:kright], and a range imin:imax, find the
// kleft_new and kright_new so that the smaller sublist X
// [kleft_new:kright_new] contains the range imin:imax.
// Zombies are not tolerated.
// This method is no longer used but is kept here in case it is needed in
// the future.
#if 0
static inline void GB_bracket
(
const int64_t imin, // search for entries in the range imin:imax
const int64_t imax,
const int64_t *restrict X, // input list is in X [kleft:kright]
const int64_t kleft_in,
const int64_t kright_in,
int64_t *kleft_new, // output list is in X [kleft_new:kright_new]
int64_t *kright_new
)
{
int64_t kleft = kleft_in ;
int64_t kright = kright_in ;
if (imin > imax)
{
// imin:imax is empty, make X [kleft:kright] empty
(*kleft_new ) = kleft ;
(*kright_new) = kleft-1 ;
return ;
}
// Find kleft and kright so that X [kleft:kright] contains all of imin:imax
// tighten kleft
GB_bracket_left (imin, X, &kleft, kright) ;
// tighten kright
GB_bracket_right (imax, X, kleft, &kright) ;
// list has been trimmed
ASSERT (GB_IMPLIES (kleft > kleft_in, X [kleft-1] < imin)) ;
ASSERT (GB_IMPLIES (kright < kright_in, imax < X [kright+1])) ;
// return result
(*kleft_new ) = kleft ;
(*kright_new) = kright ;
}
#endif
#endif
|
