1 //------------------------------------------------------------------------------
2 // GB_bracket.h: definitions for GB_bracket
3 //------------------------------------------------------------------------------
4
5 // SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2021, All Rights Reserved.
6 // SPDX-License-Identifier: Apache-2.0
7
8 //------------------------------------------------------------------------------
9
10 #ifndef GB_BRACKET_H
11 #define GB_BRACKET_H
12 #include "GB.h"
13
14 //------------------------------------------------------------------------------
15 // GB_bracket_left
16 //------------------------------------------------------------------------------
17
18 // Given a sorted list X [kleft:kright], and a range imin:..., modify kleft so
19 // that the smaller sublist X [kleft:kright] contains the range imin:...
20
21 #if 0
22
23 // This method is no longer used but is kept here in case it is needed in
24 // the future.
25
26 static inline void GB_bracket_left
27 (
28 const int64_t imin,
29 const int64_t *restrict X, // input list is in X [kleft:kright]
30 int64_t *kleft,
31 const int64_t kright
32 )
33 {
34 // tighten kleft
35 int64_t len = kright - (*kleft) + 1 ;
36 if (len > 0 && X [(*kleft)] < imin)
37 {
38 // search for imin in X [kleft:kright]
39 int64_t pleft = (*kleft) ;
40 int64_t pright = kright ;
41 GB_TRIM_BINARY_SEARCH (imin, X, pleft, pright) ;
42 (*kleft) = pleft ;
43 }
44 }
45
46 #endif
47
48 //------------------------------------------------------------------------------
49 // GB_bracket_right
50 //------------------------------------------------------------------------------
51
52 // Given a sorted list X [kleft:kright], and a range ...:imax, modify kright so
53 // that the smaller sublist X [kleft:kright] contains the range ...:imax.
54
GB_bracket_right(const int64_t imax,const int64_t * restrict X,const int64_t kleft,int64_t * kright)55 static inline void GB_bracket_right
56 (
57 const int64_t imax,
58 const int64_t *restrict X, // input list is in X [kleft:kright]
59 const int64_t kleft,
60 int64_t *kright
61 )
62 {
63 // tighten kright
64 int64_t len = (*kright) - kleft + 1 ;
65 if (len > 0 && imax < X [(*kright)])
66 {
67 // search for imax in X [kleft:kright]
68 int64_t pleft = kleft ;
69 int64_t pright = (*kright) ;
70 GB_TRIM_BINARY_SEARCH (imax, X, pleft, pright) ;
71 (*kright) = pleft ;
72 }
73 }
74
75 //------------------------------------------------------------------------------
76 // GB_bracket
77 //------------------------------------------------------------------------------
78
79 // Given a sorted list X [kleft:kright], and a range imin:imax, find the
80 // kleft_new and kright_new so that the smaller sublist X
81 // [kleft_new:kright_new] contains the range imin:imax.
82
83 // Zombies are not tolerated.
84
85 // This method is no longer used but is kept here in case it is needed in
86 // the future.
87
88 #if 0
89
90 static inline void GB_bracket
91 (
92 const int64_t imin, // search for entries in the range imin:imax
93 const int64_t imax,
94 const int64_t *restrict X, // input list is in X [kleft:kright]
95 const int64_t kleft_in,
96 const int64_t kright_in,
97 int64_t *kleft_new, // output list is in X [kleft_new:kright_new]
98 int64_t *kright_new
99 )
100 {
101 int64_t kleft = kleft_in ;
102 int64_t kright = kright_in ;
103
104 if (imin > imax)
105 {
106 // imin:imax is empty, make X [kleft:kright] empty
107 (*kleft_new ) = kleft ;
108 (*kright_new) = kleft-1 ;
109 return ;
110 }
111
112 // Find kleft and kright so that X [kleft:kright] contains all of imin:imax
113
114 // tighten kleft
115 GB_bracket_left (imin, X, &kleft, kright) ;
116
117 // tighten kright
118 GB_bracket_right (imax, X, kleft, &kright) ;
119
120 // list has been trimmed
121 ASSERT (GB_IMPLIES (kleft > kleft_in, X [kleft-1] < imin)) ;
122 ASSERT (GB_IMPLIES (kright < kright_in, imax < X [kright+1])) ;
123
124 // return result
125 (*kleft_new ) = kleft ;
126 (*kright_new) = kright ;
127 }
128 #endif
129
130 #endif
131