1 //------------------------------------------------------------------------------
2 // GrB_Matrix_removeElement: remove a single entry from a matrix
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 // Removes a single entry, C (row,col), from the matrix C.
11
12 #include "GB.h"
13
14 #define GB_FREE_ALL ;
15 #define GB_WHERE_STRING "GrB_Matrix_removeElement (C, row, col)"
16
17 //------------------------------------------------------------------------------
18 // GB_removeElement: remove C(i,j) if it exists
19 //------------------------------------------------------------------------------
20
GB_removeElement(GrB_Matrix C,GrB_Index i,GrB_Index j)21 static inline bool GB_removeElement
22 (
23 GrB_Matrix C,
24 GrB_Index i,
25 GrB_Index j
26 )
27 {
28
29 //--------------------------------------------------------------------------
30 // check inputs
31 //--------------------------------------------------------------------------
32
33 ASSERT (!GB_IS_FULL (C)) ;
34 int64_t cvlen = C->vlen ;
35
36 //--------------------------------------------------------------------------
37 // remove C(i,j)
38 //--------------------------------------------------------------------------
39
40 if (GB_IS_BITMAP (C))
41 {
42
43 //----------------------------------------------------------------------
44 // C is bitmap
45 //----------------------------------------------------------------------
46
47 int8_t *restrict Cb = C->b ;
48 int64_t p = i + j * cvlen ;
49 int8_t cb = Cb [p] ;
50 if (cb != 0)
51 {
52 // C(i,j) is present; remove it
53 Cb [p] = 0 ;
54 C->nvals-- ;
55 }
56 // C(i,j) is always found, whether present or not
57 return (true) ;
58
59 }
60 else
61 {
62
63 //----------------------------------------------------------------------
64 // C is sparse or hypersparse
65 //----------------------------------------------------------------------
66
67 const int64_t *restrict Cp = C->p ;
68 const int64_t *restrict Ci = C->i ;
69 bool found ;
70 int64_t k ;
71
72 if (GB_IS_HYPERSPARSE (C))
73 {
74 // binary search in C->h for vector j
75 const int64_t *restrict Ch = C->h ;
76 // find vector j as the kth vector in C
77 // look for vector j in hyperlist C->h [0 ... C->nvec-1]
78 int64_t pleft = 0 ;
79 int64_t pright = C->nvec-1 ;
80 GB_BINARY_SEARCH (j, Ch, pleft, pright, found) ;
81 if (!found)
82 {
83 // vector j is empty
84 return (false) ;
85 }
86 ASSERT (j == Ch [pleft]) ;
87 k = pleft ;
88 }
89 else
90 {
91 // C is sparse, C(:,j) is the jth vector of C
92 k = j ;
93 }
94
95 // look in C(:,k), the kth vector of C
96 int64_t pleft = Cp [k] ;
97 int64_t pright = Cp [k+1] ;
98 int64_t cknz = pright - pleft ;
99
100 bool is_zombie ;
101 if (cknz == cvlen)
102 {
103 // C(:,k) is packed so no binary search is needed to find C(i,k)
104 pleft = pleft + i ;
105 ASSERT (GB_UNFLIP (Ci [pleft]) == i) ;
106 found = true ;
107 is_zombie = GB_IS_ZOMBIE (Ci [pleft]) ;
108 }
109 else
110 {
111 // binary search for C(i,k): time is O(log(cknz))
112 int64_t nzombies = C->nzombies ;
113 pright-- ;
114 GB_BINARY_SEARCH_ZOMBIE (i, Ci, pleft, pright, found,
115 nzombies, is_zombie) ;
116 }
117
118 // remove the entry
119 if (found && !is_zombie)
120 {
121 // C(i,j) becomes a zombie
122 C->i [pleft] = GB_FLIP (i) ;
123 C->nzombies++ ;
124 }
125 return (found) ;
126 }
127 }
128
129 //------------------------------------------------------------------------------
130 // GrB_Matrix_removeElement: remove a single entry from a matrix
131 //------------------------------------------------------------------------------
132
GrB_Matrix_removeElement(GrB_Matrix C,GrB_Index row,GrB_Index col)133 GrB_Info GrB_Matrix_removeElement
134 (
135 GrB_Matrix C, // matrix to remove entry from
136 GrB_Index row, // row index
137 GrB_Index col // column index
138 )
139 {
140
141 //--------------------------------------------------------------------------
142 // check inputs
143 //--------------------------------------------------------------------------
144
145 GB_RETURN_IF_NULL_OR_FAULTY (C) ;
146
147 //--------------------------------------------------------------------------
148 // if C is jumbled, wait on the matrix first. If full, convert to nonfull
149 //--------------------------------------------------------------------------
150
151 if (C->jumbled || GB_IS_FULL (C))
152 {
153 GrB_Info info ;
154 GB_WHERE (C, GB_WHERE_STRING) ;
155 GB_BURBLE_START ("GrB_Matrix_removeElement") ;
156 if (GB_IS_FULL (C))
157 {
158 // convert C from full to sparse
159 GB_OK (GB_convert_to_nonfull (C, Context)) ;
160 }
161 else
162 {
163 // C is sparse or hypersparse, and jumbled
164 GB_OK (GB_Matrix_wait (C, "C", Context)) ;
165 }
166 ASSERT (!GB_IS_FULL (C)) ;
167 ASSERT (!GB_ZOMBIES (C)) ;
168 ASSERT (!GB_JUMBLED (C)) ;
169 ASSERT (!GB_PENDING (C)) ;
170 // remove the entry
171 info = GrB_Matrix_removeElement (C, row, col) ;
172 GB_BURBLE_END ;
173 return (info) ;
174 }
175
176 //--------------------------------------------------------------------------
177 // C is not jumbled and not full; it may have zombies and pending tuples
178 //--------------------------------------------------------------------------
179
180 ASSERT (!GB_IS_FULL (C)) ;
181 ASSERT (GB_ZOMBIES_OK (C)) ;
182 ASSERT (!GB_JUMBLED (C)) ;
183 ASSERT (GB_PENDING_OK (C)) ;
184
185 // look for index i in vector j
186 int64_t i, j, nrows, ncols ;
187 if (C->is_csc)
188 {
189 // C is stored by column
190 i = row ;
191 j = col ;
192 nrows = C->vlen ;
193 ncols = C->vdim ;
194 }
195 else
196 {
197 // C is stored by row
198 i = col ;
199 j = row ;
200 nrows = C->vdim ;
201 ncols = C->vlen ;
202 }
203
204 // check row and column indices
205 if (row >= nrows)
206 {
207 GB_WHERE (C, GB_WHERE_STRING) ;
208 GB_ERROR (GrB_INVALID_INDEX, "Row index "
209 GBu " out of range; must be < " GBd, row, nrows) ;
210 }
211 if (col >= ncols)
212 {
213 GB_WHERE (C, GB_WHERE_STRING) ;
214 GB_ERROR (GrB_INVALID_INDEX, "Column index "
215 GBu " out of range; must be < " GBd, col, ncols) ;
216 }
217
218 // if C is sparse or hyper, it may have pending tuples
219 bool C_is_pending = GB_PENDING (C) ;
220 if (C->nzmax == 0 && !C_is_pending)
221 {
222 // quick return
223 return (GrB_SUCCESS) ;
224 }
225
226 // remove the entry
227 if (GB_removeElement (C, i, j))
228 {
229 // found it; no need to assemble pending tuples
230 return (GrB_SUCCESS) ;
231 }
232
233 // assemble any pending tuples; zombies are OK
234 if (C_is_pending)
235 {
236 GrB_Info info ;
237 GB_WHERE (C, GB_WHERE_STRING) ;
238 GB_BURBLE_START ("GrB_Matrix_removeElement") ;
239 GB_OK (GB_Matrix_wait (C, "C", Context)) ;
240 ASSERT (!GB_ZOMBIES (C)) ;
241 ASSERT (!GB_JUMBLED (C)) ;
242 ASSERT (!GB_PENDING (C)) ;
243 // look again; remove the entry if it was a pending tuple
244 GB_removeElement (C, i, j) ;
245 GB_BURBLE_END ;
246 }
247
248 return (GrB_SUCCESS) ;
249 }
250
251