1 //------------------------------------------------------------------------------
2 // GB_ij.h: definitions for I and J index lists
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_IJ_H
11 #define GB_IJ_H
12
13 #include "GB.h"
14
15 GB_PUBLIC // accessed by the MATLAB interface only
16 void GB_ijlength // get the length and kind of an index list I
17 (
18 const GrB_Index *I, // list of indices (actual or implicit)
19 const int64_t ni, // length I, or special
20 const int64_t limit, // indices must be in the range 0 to limit-1
21 int64_t *nI, // actual length of I
22 int *Ikind, // kind of I: GB_ALL, GB_RANGE, GB_STRIDE, GB_LIST
23 int64_t Icolon [3] // begin:inc:end for all but GB_LIST
24 ) ;
25
26 GrB_Info GB_ijproperties // check I and determine its properties
27 (
28 // input:
29 const GrB_Index *I, // list of indices, or special
30 const int64_t ni, // length I, or special
31 const int64_t nI, // actual length from GB_ijlength
32 const int64_t limit, // I must be in the range 0 to limit-1
33 // input/output:
34 int *Ikind, // kind of I, from GB_ijlength
35 int64_t Icolon [3], // begin:inc:end from GB_ijlength
36 // output:
37 bool *I_is_unsorted, // true if I is out of order
38 bool *I_has_dupl, // true if I has a duplicate entry (undefined
39 // if I is unsorted)
40 bool *I_is_contig, // true if I is a contiguous list, imin:imax
41 int64_t *imin_result, // min (I)
42 int64_t *imax_result, // max (I)
43 GB_Context Context
44 ) ;
45
46 GrB_Info GB_ijsort
47 (
48 const GrB_Index *restrict I, // size ni, where ni > 1 always holds
49 int64_t *restrict p_ni, // : size of I, output: # of indices in I2
50 GrB_Index *restrict *p_I2, // size ni2, where I2 [0..ni2-1]
51 // contains the sorted indices with duplicates removed.
52 size_t *I2_size_handle,
53 GrB_Index *restrict *p_I2k, // output array of size ni2
54 size_t *I2k_size_handle,
55 GB_Context Context
56 ) ;
57
58 // given k, return the kth item i = I [k] in the list
GB_ijlist(const GrB_Index * I,const int64_t k,const int Ikind,const int64_t Icolon[3])59 static inline int64_t GB_ijlist // get the kth item in a list of indices
60 (
61 const GrB_Index *I, // list of indices
62 const int64_t k, // return i = I [k], the kth item in the list
63 const int Ikind, // GB_ALL, GB_RANGE, GB_STRIDE, or GB_LIST
64 const int64_t Icolon [3] // begin:inc:end for all but GB_LIST
65 )
66 {
67 if (Ikind == GB_ALL)
68 {
69 // I is ":"
70 return (k) ;
71 }
72 else if (Ikind == GB_RANGE)
73 {
74 // I is begin:end
75 return (Icolon [GxB_BEGIN] + k) ;
76 }
77 else if (Ikind == GB_STRIDE)
78 {
79 // I is begin:inc:end
80 // note that iinc can be negative or even zero
81 return (Icolon [GxB_BEGIN] + k * Icolon [GxB_INC]) ;
82 }
83 else // Ikind == GB_LIST
84 {
85 ASSERT (Ikind == GB_LIST) ;
86 ASSERT (I != NULL) ;
87 return (I [k]) ;
88 }
89 }
90
91 // given i and I, return true there is a k so that i is the kth item in I
GB_ij_is_in_list(const GrB_Index * I,const int64_t nI,int64_t i,const int Ikind,const int64_t Icolon[3])92 static inline bool GB_ij_is_in_list // determine if i is in the list I
93 (
94 const GrB_Index *I, // list of indices for GB_LIST
95 const int64_t nI, // length of I if Ikind is GB_LIST
96 int64_t i, // find i = I [k] in the list
97 const int Ikind, // GB_ALL, GB_RANGE, GB_STRIDE, or GB_LIST
98 const int64_t Icolon [3] // begin:inc:end for all but GB_LIST
99 )
100 {
101
102 if (Ikind == GB_ALL)
103 {
104 // I is ":", all indices are in the sequence
105 return (true) ;
106 }
107 else if (Ikind == GB_RANGE)
108 {
109 // I is begin:end
110 int64_t b = Icolon [GxB_BEGIN] ;
111 int64_t e = Icolon [GxB_END] ;
112 if (i < b) return (false) ;
113 if (i > e) return (false) ;
114 return (true) ;
115 }
116 else if (Ikind == GB_STRIDE)
117 {
118 // I is begin:inc:end
119 // note that inc can be negative or even zero
120 int64_t b = Icolon [GxB_BEGIN] ;
121 int64_t inc = Icolon [GxB_INC] ;
122 int64_t e = Icolon [GxB_END] ;
123 if (inc == 0)
124 {
125 // lo:stride:hi with stride of zero.
126 // I is empty if inc is zero, so i is not in I.
127 return (false) ;
128 }
129 else if (inc > 0)
130 {
131 // forward direction, increment is positive
132 // I = b:inc:e = [b, b+inc, b+2*inc, ..., e]
133 if (i < b) return (false) ;
134 if (i > e) return (false) ;
135 // now i is in the range [b ... e]
136 ASSERT (b <= i && i <= e) ;
137 i = i - b ;
138 ASSERT (0 <= i && i <= (e-b)) ;
139 // the sequence I-b = [0, inc, 2*inc, ... e-b].
140 // i is in the sequence if i % inc == 0
141 return (i % inc == 0) ;
142 }
143 else // inc < 0
144 {
145 // backwards direction, increment is negative
146 inc = -inc ;
147 // now inc is positive
148 ASSERT (inc > 0) ;
149 // I = b:(-inc):e = [b, b-inc, b-2*inc, ... e]
150 if (i > b) return (false) ;
151 if (i < e) return (false) ;
152 // now i is in the range of the sequence, [b down to e]
153 ASSERT (e <= i && i <= b) ;
154 i = b - i ;
155 ASSERT (0 <= i && i <= (b-e)) ;
156 // b-I = 0:(inc):(b-e) = [0, inc, 2*inc, ... (b-e)]
157 // i is in the sequence if i % inc == 0
158 return (i % inc == 0) ;
159 }
160 }
161 else // Ikind == GB_LIST
162 {
163 ASSERT (Ikind == GB_LIST) ;
164 ASSERT (I != NULL) ;
165 // search for i in the sorted list I
166 bool found ;
167 int64_t pleft = 0 ;
168 int64_t pright = nI-1 ;
169 if (i < 0) return (false) ;
170 GrB_Index ui = (GrB_Index) i ;
171 GB_BINARY_SEARCH (ui, I, pleft, pright, found) ;
172 return (found) ;
173 }
174 }
175
176 #endif
177
178