Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
hit_bshape.c
Go to the documentation of this file.
1 
10 /*
11  * <license>
12  *
13  * Hitmap v1.2
14  *
15  * This software is provided to enhance knowledge and encourage progress in the scientific
16  * community. It should be used only for research and educational purposes. Any reproduction
17  * or use for commercial purpose, public redistribution, in source or binary forms, with or
18  * without modifications, is NOT ALLOWED without the previous authorization of the copyright
19  * holder. The origin of this software must not be misrepresented; you must not claim that you
20  * wrote the original software. If you use this software for any purpose (e.g. publication),
21  * a reference to the software package and the authors must be included.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS "AS IS" AND ANY
24  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
25  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
26  * THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
27  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
28  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32  *
33  * Copyright (c) 2007-2015, Trasgo Group, Universidad de Valladolid.
34  * All rights reserved.
35  *
36  * More information on http://trasgo.infor.uva.es/
37  *
38  * </license>
39 */
40 
41 #include <hit_bshape.h>
42 #include <hit_allocP.h>
43 #include <hit_funcop.h>
44 
45 
46 HitShape hit_bitmapShape(int nvertices){
47 
48  // 1. Init the Bitmap struct
50  hit_bShapeCard(s,0) = nvertices;
51  hit_bShapeCard(s,1) = nvertices;
52 
53  // 2. Allocate the square adyacency matrix
54  int nbits = nvertices*nvertices;
55  size_t ndata = (size_t) (hit_bitmapShapeIndex(nbits) + (hit_bitmapShapeOffset(nbits)==0 ? 0 : 1));
56  // @arturo Ago 2015: New allocP interface
57  // hit_calloc(hit_bShapeData(s),sizeof(HIT_BITMAP_TYPE),HIT_BITMAP_TYPE*);
58  hit_calloc(hit_bShapeData(s),HIT_BITMAP_TYPE,ndata);
59 
60  // 3. Allocate and fill the global names array
61  hit_nameListCreate(&hit_bShapeNameList(s,0),nvertices);
63 
64  // 4. Return the struct
65  return s;
66 }
67 
68 
70 
72 
73  // Cardinalities.
74  hit_bShapeCard(s,0) = n;
75  hit_bShapeCard(s,1) = m;
76 
77  // Allocate the arrays.
78  int nbits = n * m;
79  size_t ndata = (size_t) (hit_bitmapShapeIndex(nbits) + (hit_bitmapShapeOffset(nbits)==0 ? 0 : 1));
80  // @arturo Ago 2015: New allocP interface
81  // hit_calloc(hit_bShapeData(s),ndata+1,sizeof(HIT_BITMAP_TYPE),HIT_BITMAP_TYPE*);
82  hit_calloc(hit_bShapeData(s),HIT_BITMAP_TYPE,ndata+1);
83 
84  // This allows the bitmap iterator to stop at the end if the last bits are 0.
85  hit_bShapeData(s)[ndata] = 1;
86 
89 
90  // Return the shape
91  return s;
92 }
93 
94 
96 
97  hit_free(hit_bShapeData(shape));
99 
100  if(hit_bShapeNameList(shape,0).names != hit_bShapeNameList(shape,1).names)
102 }
103 
104 
112 
113  int i,j;
114 
115  for(i=0; i < hit_bShapeCard(dst,0); i++){
116  for(j=0; j < hit_bShapeCard(dst,1); j++){
117 
118  // For each element of the bitmap we get the global names
119  int g_i = hit_nameListIndex2Name( hit_bShapeNameList(dst,0), i);
120  int g_j = hit_nameListIndex2Name( hit_bShapeNameList(dst,1), j);
121 
122  // Check if the source shape has those elements.
123  if(hit_bShapeGetGlobal(src,g_i,g_j)){
124 
125  hit_bShapeSet(dst,i,j);
126  hit_bShapeNedges(dst)++;
127  }
128  }
129  }
130 }
131 
132 
133 
134 HitShape hit_bShapeSelect(HitShape shape, int nvertices, int * vertices){
135 
136  if(nvertices < 1) return HIT_BITMAP_SHAPE_NULL;
137 
138  // 1. If vertices is NULL we use the name vector (a.k.a. n first vertices)
139  if(vertices == NULL){
140  vertices = hit_bShapeNameList(shape,0).names;
141  }
142 
143  // 2. Create a new graph with edge array as big as the original.
144  HitShape res = hit_bitmapShape(nvertices);
145 
146  // 3. Duplicate vertices array as globalNames.
147  memcpy(hit_bShapeNameList(res,0).names, vertices, sizeof(int) * (size_t) nvertices );
148  hit_bShapeNameList(res,0).nNames = nvertices;
149  hit_bShapeNameList(res,0).flagNames = HIT_SHAPE_NAMES_NOARRAY;
150  hit_bShapeNameList(res,1) = hit_bShapeNameList(res,0);
151 
152  // Copy the Elements from the original shape to the result shape.
154 
155  // 8. Return
156  return res;
157 }
158 
159 
160 
161 
162 HitShape hit_bShapeSelectRows(HitShape shape, int nNames, int * names){
163 
164  // Select cardinalities: matrix of n x m
165  int n = nNames;
166  int m = hit_bShapeCard(shape,1);
167 
168  // Create the matrix
169  HitShape res = hit_bitmapShapeMatrix(n,m);
170 
171  // Create the name lists
172  memcpy(hit_bShapeNameList(res,0).names, names, (size_t) n *sizeof(idxtype) );
173  hit_bShapeNameList(res,0).flagNames = HIT_SHAPE_NAMES_NOARRAY;
176 
177  // Copy the values to the new shape
179 
180  return res;
181 }
182 
183 
184 
185 
186 
187 
188 
189 
190 
191 
192 
194 
195  if( hit_bShapeNvertices(shape) < 1) return HIT_BITMAP_SHAPE_NULL;
196 
197  // 1. Create a vertex list
198  int orig_nvertices = hit_bShapeNvertices(original);
199  int * vertices;
200  // @arturo Ago 2015: New allocP interface
201  // hit_calloc(vertices, (size_t)orig_nvertices, sizeof(int),int*);
202  hit_calloc(vertices, int, orig_nvertices);
203 
204 #define VLOCAL 1 // (....0001)
205 #define VEXPAND 2 // (....0010)
206 
207  // 2. Set the local vertices in the vector.
208  int vertex;
209 
210  hit_bShapeVertexIterator(vertex,shape){
211 
212  int global_vertex = hit_bShapeVertexToGlobal(shape,vertex);
213  int local_orig_vertex = hit_bShapeVertexToLocal(original,global_vertex);
214 
215  vertices[local_orig_vertex] = VLOCAL;
216  }
217 
218  // 3. Expand the list.
219  int new_vertices = 0;
220  int a;
221  for(a=0; a<amount; a++){
222 
223  int vertex_i, vertex_j;
224 
225  // Complete the local vertices and the number of vertices.
226  for(vertex_i=0; vertex_i<orig_nvertices; vertex_i++){
227 
228  for(vertex_j=0; vertex_j<orig_nvertices; vertex_j++){
229 
230  if(hit_bShapeGet(original,vertex_i,vertex_j) == 0) continue;
231 
232  // TO
233  if((vertices[vertex_i] & VLOCAL) && (! vertices[vertex_j] & VLOCAL)){
234  vertices[vertex_j] = VEXPAND;
235  new_vertices++;
236  }
237 
238  // @javfres @todo The hit_bShapeExpand function expand the shape
239  // following the edges from source to target. I call this TO direction.
240  // It can be interesting to add a FROM option, or maybe several functions
241  // with TO/FROM/TOFROM.
242  }
243 
244  }
245 
246  // Set the expanded vertices as local for the next loop.
247  if(a<amount-1){
248  for(vertex=0; vertex<orig_nvertices; vertex++){
249  if(vertices[vertex] == VEXPAND) vertices[vertex] |= VLOCAL;
250  }
251  }
252 
253  }
254 
255  // 3. Create selection list
256  int * vlist;
257  int nvlist = new_vertices + hit_bShapeNvertices(shape);
258  // @arturo Ago 2015: New allocP interface
259  // hit_malloc(vlist,sizeof(int) * (size_t) nvlist,int*);
260  hit_malloc(vlist, int, nvlist);
261 
262  // 4. The first vertices of the old and new shape are the same.
263  memcpy(vlist,hit_bShapeNameList(shape,0).names, sizeof(int) * (size_t) hit_bShapeNvertices(shape));
264 
265  // 5. Complete the selection list.
266  int vertex_index = hit_bShapeNvertices(shape);
267  for(vertex=0; vertex<orig_nvertices; vertex++){
268 
269  if(vertices[vertex] > VLOCAL){
270  vlist[vertex_index] = hit_bShapeVertexToGlobal(original,vertex);
271  vertex_index++;
272  }
273  }
274 
275  // 6. Select
276  HitShape res = hit_bShapeSelect(original,nvlist,vlist);
277 
278 
279  // 7. Free resources.
280  hit_free(vertices);
281  hit_free(vlist);
282 
283 
284 #undef VLOCAL
285 #undef VEXPAND
286 
287  return res;
288 
289 }
290 
291 
292 
294 
295 #define s (*shape)
296 
297  int local_x;
298 
299  local_x = hit_bShapeCoordToLocal(s,0,x);
300 
301  if( local_x != -1 ) return;
302  local_x = hit_bShapeCard(s, 0);
303 
304  // A. Create the sparse shape.
305  if(local_x == 0){
306 
307  // A.1 Create new bitmap shape.
308  if(mode == HIT_BSHAPE_GRAPH){
309  s = hit_bitmapShape(1);
310  } else {
311  s = hit_bitmapShapeMatrix(1,0);
312  }
313  hit_bShapeNameList(s,0).names[0] = x;
314 
315 
316  // B. The given sparse shape is not empty.
317  } else {
318 
319  // B.1 Create new bitmap shape.
320  int nelems_x = hit_bShapeCard(s,0) + 1;
321  int nelems_y = hit_bShapeCard(s,1);
322  HitShape newShp;
323 
324  if (mode == HIT_BSHAPE_GRAPH){
325  newShp = hit_bitmapShape(nelems_x);
326  } else {
327  newShp = hit_bitmapShapeMatrix(nelems_x,nelems_y);
328  }
329 
330  // B.2 Copy the data
331  int i,j;
332  for(i=0; i<(nelems_x-1); i++){
333  for(j=0; j<(nelems_y); j++){
334  if(hit_bShapeGet(s,i,j)){
335  hit_bShapeSet(newShp,i,j);
336  }
337  }
338  }
339 
340  // B.3 Free the previous data and copy the new to the previous shape.
342  hit_bShapeData(s) = hit_bShapeData(newShp);
343 
344  // B.4 Update the cardinalities.
345  hit_bShapeCard(s,0) = hit_bShapeCard(newShp,0);
346  hit_bShapeCard(s,1) = hit_bShapeCard(newShp,1);
347 
348  // B.5 Free the new name vectors
350  if (mode != HIT_BSHAPE_GRAPH){
352  }
353 
354  // B.6 Update the name vectors
356  if (mode == HIT_BSHAPE_GRAPH){
358  }
359  }
360 
361 
362 #undef s
363 
364 }
365 
366 
367 
368 
370 
371 #define s (*shape)
372 
373 
375 
376  // 1 Create new bitmap shape.
377  int nelems_x = hit_bShapeCard(s,0);
378  int nelems_y = hit_bShapeCard(s,1) + 1;
379  HitShape newShp = hit_bitmapShapeMatrix(nelems_x,nelems_y);
380 
381  // 2 Copy the data
382  int i,j;
383  for(i=0; i<(nelems_x); i++){
384  for(j=0; j<(nelems_y-1); j++){
385  if(hit_bShapeGet(s,i,j)){
386  hit_bShapeSet(newShp,i,j);
387  }
388  }
389  }
390 
391  // 3 Free the previous data and copy the new to the previous shape.
393  hit_bShapeData(s) = hit_bShapeData(newShp);
394 
395  // 4 Update the cardinalities.
396  hit_bShapeCard(s,1)++;
397 
398  // 5 Free the new name vectors
401 
402  // 6 Update the name vectors
404  }
405 
406 #undef s
407 
408 }
409 
410 
411 
412 
413 void hit_bShapeAddElem_or_Edge(HitShape * shape, int x, int y, int mode){
414 
415  // 1. Add the vertices
416  hit_bShapeAddEmptyRow_or_Vertex(shape, x, mode);
417  if(mode == HIT_BSHAPE_GRAPH){
418  hit_bShapeAddEmptyRow_or_Vertex(shape, y, mode);
419  } else {
420  hit_bShapeAddColumn(shape, y);
421  }
422 
423  // 2. Add the edge
424  if(hit_bShapeGetGlobal(*shape,x,y) == 0){
425  hit_bShapeSetGlobal(*shape,x,y);
426  hit_bShapeNedges(*shape)++;
427  }
428 
429 }
430 
431 
432 
433 
435 
436  int ncols = 0;
437  int j;
438 
439  hit_bShapeColumnIterator(j,shape,row){
440  ncols++;
441  }
442 
443  return ncols;
444 }
445 
446 
447 
#define hit_bShapeSet(bitshape, i, j)
#define hit_bShapeColumnIterator(var, shape, row)
Definition: hit_bshape.h:466
#define hit_free(ptr)
Definition: hit_allocP.h:152
HitShape hit_bShapeSelectRows(HitShape shape, int nNames, int *names)
Definition: hit_bshape.c:162
void hit_nameListClone(HitNameList *dst, HitNameList *src)
Definition: hit_shape.c:318
HitShape hit_bShapeSelect(HitShape shape, int nvertices, int *vertices)
Definition: hit_bshape.c:134
void hit_bShapeAddEmptyRow_or_Vertex(HitShape *shape, int x, int mode)
Definition: hit_bshape.c:293
int hit_bShapeNColsRow(HitShape shape, int row)
Definition: hit_bshape.c:434
#define hit_bShapeGet(bitshape, i, j)
void hit_nameListAdd(HitNameList *list, int x)
Definition: hit_shape.c:337
#define hit_bShapeCard(shape, dim)
Definition: hit_bshape.h:144
HitShape hit_bShapeExpand(HitShape shape, HitShape original, int amount)
Definition: hit_bshape.c:193
int hit_nameListName2Index(HitNameList list, int name)
Definition: hit_shape.c:262
#define hit_bShapeNameList(shape, dim)
Definition: hit_bshape.h:171
#define y(a, b, c)
#define hit_bShapeGetGlobal(bitshape, i, j)
#define hit_calloc(ptr, type, nmemb)
Definition: hit_allocP.h:114
HitShape hit_bitmapShape(int nvertices)
Definition: hit_bshape.c:46
void hit_nameListFree(HitNameList list)
Definition: hit_shape.c:291
#define VLOCAL
#define hit_bShapeData(shape)
Definition: hit_bshape.h:180
#define hit_bShapeCoordToLocal(s, dim, elem)
Definition: hit_bshape.h:201
int idxtype
Definition: struct.h:19
void hit_nameListCreate(HitNameList *list, int nelems)
Definition: hit_shape.c:301
void hit_bShapeFree(HitShape shape)
Definition: hit_bshape.c:95
#define hit_bShapeVertexIterator(var, shape)
Definition: hit_bshape.h:455
#define hit_bShapeNedges(shape)
void hit_bShapeCopyElementsInternal(HitShape dst, HitShape src)
Definition: hit_bshape.c:111
#define x
void hit_bShapeAddColumn(HitShape *shape, int y)
Definition: hit_bshape.c:369
#define hit_bShapeVertexToLocal(s, vertex)
Definition: hit_bshape.h:355
Hitmap functions to allocate memory.
#define hit_bShapeVertexToGlobal(s, vertex)
#define hit_malloc(ptr, type, nmemb)
Definition: hit_allocP.h:93
#define hit_bShapeSetGlobal(bitshape, i, j)
HitShape hit_bitmapShapeMatrix(int n, int m)
Definition: hit_bshape.c:69
HitShape shape
#define hit_bShapeNvertices(shape)
#define VEXPAND
#define s
void hit_bShapeAddElem_or_Edge(HitShape *shape, int x, int y, int mode)
Definition: hit_bshape.c:413
#define m(a, b, c)
HitShape HIT_BITMAP_SHAPE_NULL
Definition: hit_shape.c:71
#define HIT_BSHAPE_GRAPH
Definition: hit_bshape.h:53