1 //------------------------------------------------------------------------------
2 // GB_ijlength: get the length and kind of an index list I
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 // Determine the length of I, and process the colon notation I = begin:inc:end.
11 // No error checking is done.
12
13 #include "GB_ij.h"
14
15 // ensure an unsigned integer does not cause signed integer overflow
16 #define GB_LIMIT(u) (int64_t) (GB_IMIN (u, INT64_MAX))
17
GB_ijlength(const GrB_Index * I,const int64_t ni,const int64_t limit,int64_t * nI,int * Ikind,int64_t Icolon[3])18 void GB_ijlength // get the length and kind of an index list I
19 (
20 const GrB_Index *I, // list of indices (actual or implicit)
21 const int64_t ni, // length I, or special
22 const int64_t limit, // indices must be in the range 0 to limit-1
23 int64_t *nI, // actual length of I
24 int *Ikind, // kind of I: GB_ALL, GB_RANGE, GB_STRIDE, GB_LIST
25 int64_t Icolon [3] // begin:inc:end for all but GB_LIST
26 )
27 {
28
29 //--------------------------------------------------------------------------
30 // check inputs
31 //--------------------------------------------------------------------------
32
33 ASSERT (I != NULL) ;
34 ASSERT (limit >= 0) ;
35 ASSERT (limit <= GxB_INDEX_MAX) ; // GxB_INDEX_MAX is 2^60
36
37 //--------------------------------------------------------------------------
38 // determine the length of I
39 //--------------------------------------------------------------------------
40
41 if (I == GrB_ALL)
42 {
43
44 //----------------------------------------------------------------------
45 // I = ":" = 0:limit-1
46 //----------------------------------------------------------------------
47
48 (*Ikind) = GB_ALL ;
49
50 Icolon [GxB_BEGIN] = 0 ;
51 Icolon [GxB_INC ] = 1 ;
52 Icolon [GxB_END ] = limit-1 ;
53
54 (*nI) = limit ;
55
56 }
57 else if (ni == GxB_RANGE)
58 {
59
60 //----------------------------------------------------------------------
61 // I = ibegin:iend
62 //----------------------------------------------------------------------
63
64 (*Ikind) = GB_RANGE ;
65
66 // the array I must have size at least 2
67
68 int64_t ibegin = GB_LIMIT (I [GxB_BEGIN]) ;
69 int64_t iend = GB_LIMIT (I [GxB_END ]) ;
70
71 ASSERT (ibegin >= 0) ;
72
73 if (ibegin == 0 && iend == limit-1)
74 {
75 // 0:limit-1 is the same as ":"
76 (*Ikind) = GB_ALL ;
77 }
78
79 Icolon [GxB_BEGIN] = ibegin ;
80 Icolon [GxB_INC ] = 1 ;
81 Icolon [GxB_END ] = iend ;
82
83 if (ibegin > iend)
84 {
85 // the list is empty
86 (*nI) = 0 ;
87 }
88 else // ibegin <= iend
89 {
90 // list ibegin:iend is not empty
91 (*nI) = (iend - ibegin + 1) ;
92 }
93
94 }
95 else if (ni == GxB_STRIDE)
96 {
97
98 //----------------------------------------------------------------------
99 // I = ibegin:iinc:iend where iinc >= 0
100 //----------------------------------------------------------------------
101
102 (*Ikind) = GB_STRIDE ;
103
104 // The array I must have size at least 3. It is an unsigned uint64_t
105 // array, so integers must be positive.
106
107 int64_t ibegin = GB_LIMIT (I [GxB_BEGIN]) ;
108 int64_t iinc = GB_LIMIT (I [GxB_INC ]) ;
109 int64_t iend = GB_LIMIT (I [GxB_END ]) ;
110
111 ASSERT (ibegin >= 0) ;
112 ASSERT (iinc >= 0) ;
113 ASSERT (iend >= 0) ;
114
115 if (iinc == 1)
116 {
117 if (ibegin == 0 && iend == limit-1)
118 {
119 // 0:1:limit-1 is the same as ":"
120 (*Ikind) = GB_ALL ;
121 }
122 else
123 {
124 // ibegin:1:iend is the same as ibegin:iend
125 (*Ikind) = GB_RANGE ;
126 }
127 }
128
129 // an increment of 0 means the list is empty
130 if (iinc == 0)
131 {
132 (*nI) = 0 ;
133 }
134 else // iinc > 0
135 {
136 if (ibegin > iend)
137 {
138 // the list ibegin:iinc:iend is empty (for example 10:1:0)
139 (*nI) = 0 ;
140 }
141 else // ibegin <= iend
142 {
143 // the list is non-empty (for example 4:2:7 = [4 6])
144 (*nI) = ((iend - ibegin) / iinc) + 1 ;
145 }
146 }
147
148 Icolon [GxB_BEGIN] = ibegin ;
149 Icolon [GxB_INC ] = iinc ;
150 Icolon [GxB_END ] = iend ;
151
152 }
153 else if (ni == GxB_BACKWARDS)
154 {
155
156 //----------------------------------------------------------------------
157 // I = ibegin:iinc:iend where iinc <= 0
158 //----------------------------------------------------------------------
159
160 (*Ikind) = GB_STRIDE ;
161
162 // The array I must have size at least 3. It is an unsigned uint64_t
163 // array, so integers must be positive.
164
165 int64_t ibegin = GB_LIMIT (I [GxB_BEGIN]) ;
166 int64_t iinc = GB_LIMIT (I [GxB_INC ]) ;
167 int64_t iend = GB_LIMIT (I [GxB_END ]) ;
168
169 ASSERT (iinc >= 0) ;
170
171 // the stride is backwards, so negate iinc
172 iinc = -iinc ;
173
174 ASSERT (ibegin >= 0) ;
175 ASSERT (iinc <= 0) ;
176 ASSERT (iend >= 0) ;
177
178 // an increment of 0 means the list is empty
179 if (iinc == 0)
180 {
181 (*nI) = 0 ;
182 }
183 else // iinc < 0
184 {
185 if (ibegin < iend)
186 {
187 // the list ibegin:iinc:iend is empty (for example 1:-1:10)
188 (*nI) = 0 ;
189 }
190 else
191 {
192 // the list is non-empty (for example 7:-2:4 = [7 5])
193 // two positive numbers are divided here
194 (*nI) = ((ibegin - iend) / (-iinc)) + 1 ;
195 }
196 }
197
198 Icolon [GxB_BEGIN] = ibegin ;
199 Icolon [GxB_INC ] = iinc ;
200 Icolon [GxB_END ] = iend ;
201
202 }
203 else
204 {
205
206 //----------------------------------------------------------------------
207 // I is an array of indices
208 //----------------------------------------------------------------------
209
210 (*Ikind) = GB_LIST ;
211
212 // not computed
213 Icolon [GxB_BEGIN] = 0 ;
214 Icolon [GxB_INC ] = 0 ;
215 Icolon [GxB_END ] = 0 ;
216
217 (*nI) = ni ;
218 }
219 }
220
221