Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
hit_bshape.h
Go to the documentation of this file.
1 
13 /*
14  * <license>
15  *
16  * Hitmap v1.2
17  *
18  * This software is provided to enhance knowledge and encourage progress in the scientific
19  * community. It should be used only for research and educational purposes. Any reproduction
20  * or use for commercial purpose, public redistribution, in source or binary forms, with or
21  * without modifications, is NOT ALLOWED without the previous authorization of the copyright
22  * holder. The origin of this software must not be misrepresented; you must not claim that you
23  * wrote the original software. If you use this software for any purpose (e.g. publication),
24  * a reference to the software package and the authors must be included.
25  *
26  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS "AS IS" AND ANY
27  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
28  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
29  * THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
33  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
34  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35  *
36  * Copyright (c) 2007-2015, Trasgo Group, Universidad de Valladolid.
37  * All rights reserved.
38  *
39  * More information on http://trasgo.infor.uva.es/
40  *
41  * </license>
42 */
43 
44 #ifndef _HitBShape_
45 #define _HitBShape_
46 
47 
48 #include "hit_shape.h"
49 
51 #define HIT_BSHAPE_MATRIX 0
52 
53 #define HIT_BSHAPE_GRAPH 1
54 
59 // @cond INTERNAL
63 #define HIT_BITMAP_SHAPE_INTERNAL_NULL_STATIC { {0, 0}, 0, NULL, {HIT_NAMELIST_NULL_STATIC,HIT_NAMELIST_NULL_STATIC} }
64 
65 // @author javfres: C++ do not support this kind of struct initialization.
66 // @author arturo: Solution, do the initialization in two assignments in the .c file. Done.
67 #ifdef __cplusplus
68 #else
69 #define HIT_BITMAP_SHAPE_NULL_STATIC { HIT_BITMAP_SHAPE, { .bitmap = HIT_BITMAP_SHAPE_INTERNAL_NULL_STATIC } }
70 #endif
71 // @endcond
72 
73 // @cond INTERNAL
75 #define hit_bitmapShapeIndex(b) (((size_t)(b))/HIT_BITMAP_SIZE)
76 
77 #define hit_bitmapShapeOffset(b) (((size_t)(b))%HIT_BITMAP_SIZE)
78 // @endcond
79 
80 // @cond INTERNAL
82 #define HIT_BITMAP_1 (((HIT_BITMAP_TYPE) 1) << (HIT_BITMAP_SIZE-1))
83 
86 static inline const char * hit_bitmap_tostring(HIT_BITMAP_TYPE element){
87 
88  static char buffer[HIT_BITMAP_SIZE+1];
89  buffer[HIT_BITMAP_SIZE] = '\0';
90 
91  HIT_BITMAP_TYPE mask = HIT_BITMAP_1;
92  HIT_BITMAP_TYPE i;
93  for(i=0;i<HIT_BITMAP_SIZE;i++){
94 
95  if( (mask & element) == 0 ){
96  buffer[i] = '0';
97  } else{
98  buffer[i] = '1';
99  }
100  mask = mask >> 1;
101  }
102  return buffer;
103 }
104 // @endcond
105 
106 /* 1. Hit Bitmap Shape generating functions */
114 HitShape hit_bitmapShape(int nvertices);
115 
123 HitShape hit_bitmapShapeMatrix(int n, int m);
124 
131 
132 
133 
134 
135 
136 
137 /* 2 Hit Bitmap Shape access macros */
144 #define hit_bShapeCard(shape, dim) (hit_bShapeAccess(shape).cards[(dim)])
145 
153 #define hit_bShapeNvertices(shape) (hit_bShapeCard(shape, 0))
154 
162 #define hit_bShapeNedges(shape) (hit_bShapeAccess(shape).nz)
163 
164 
171 #define hit_bShapeNameList(shape,dim) (hit_bShapeAccess((shape)).names[(dim)])
172 
180 #define hit_bShapeData(shape) (hit_bShapeAccess(shape).data)
181 
182 
183 
191 #define hit_bShapeCoordToGlobal(s,dim,elem) (hit_nameListIndex2Name(hit_bShapeNameList((s),(dim)),(elem)))
192 
193 
201 #define hit_bShapeCoordToLocal(s,dim,elem) (hit_nameListName2Index(hit_bShapeNameList((s),(dim)),(elem)))
202 
203 
204 
213 #define hit_bShapeEdgeTarget(s,edge) (edge)
214 
223 #define hit_bShapeEdgeTargetSkip(s,edge) (edge%hit_bShapeCard(s,1))
224 
225 
226 /* 3. Hit Bitmap Sparse Shape operations */
236 #define hit_bShapeGet(bitshape,i,j) \
237  (hit_bShapeData(bitshape)[hit_bitmapShapeIndex((i)*hit_bShapeCard(bitshape,1)+(j))] \
238  & \
239  ((HIT_BITMAP_1) >> hit_bitmapShapeOffset((i)*hit_bShapeCard(bitshape,1)+(j))))
240 
249 #define hit_bShapeSet(bitshape,i,j) \
250  (hit_bShapeData(bitshape)[hit_bitmapShapeIndex((i)*hit_bShapeCard(bitshape,1)+(j))] \
251  |= \
252  (HIT_BITMAP_TYPE) \
253  ((HIT_BITMAP_1) >> hit_bitmapShapeOffset((i)*hit_bShapeCard(bitshape,1)+(j))))
254 
263 #define hit_bShapeClear(bitshape,i,j) \
264  (hit_bShapeData(bitshape)[hit_bitmapShapeIndex((i)*hit_bShapeCard(bitshape,1)+(j))] \
265  &= \
266  (HIT_BITMAP_TYPE) \
267  ~((HIT_BITMAP_1) >> hit_bitmapShapeOffset((i)*hit_bShapeCard(bitshape,1)+(j))))
268 
277 #define hit_bShapeSet2(bitshape,i,j) {hit_bShapeSet(bitshape,i,j); hit_bShapeSet(bitshape,j,i);}
278 
288 #define hit_bShapeGetGlobal(bitshape,i,j) \
289  (hit_bShapeData(bitshape)[hit_bitmapShapeIndex((hit_bShapeCoordToLocal(bitshape,0, (i)))* \
290  hit_bShapeCard(bitshape,1)+(hit_bShapeCoordToLocal(bitshape,1, (j))))] \
291  & \
292  ((HIT_BITMAP_1) >> hit_bitmapShapeOffset((hit_bShapeCoordToLocal(bitshape,0, (i)))* \
293  hit_bShapeCard(bitshape,1)+(hit_bShapeCoordToLocal(bitshape,1, (j))))))
294 
303 #define hit_bShapeSetGlobal(bitshape,i,j) \
304  (hit_bShapeData(bitshape)[hit_bitmapShapeIndex((hit_bShapeCoordToLocal(bitshape,0, (i)))* \
305  hit_bShapeCard(bitshape,1)+(hit_bShapeCoordToLocal(bitshape,1, (j))))] \
306  |= \
307  (HIT_BITMAP_TYPE) \
308  ((HIT_BITMAP_1) >> hit_bitmapShapeOffset((hit_bShapeCoordToLocal(bitshape,0, (i)))* \
309  hit_bShapeCard(bitshape,1)+(hit_bShapeCoordToLocal(bitshape,1, (j))))))
310 
319 #define hit_bShapeClearGlobal(bitshape,i,j) \
320  (hit_bShapeData(bitshape)[hit_bitmapShapeIndex((hit_bShapeCoordToLocal(bitshape,0, (i)))* \
321  hit_bShapeCard(bitshape,1)+(hit_bShapeCoordToLocal(bitshape,1, (j))))] \
322  &= ~ \
323  (HIT_BITMAP_TYPE) \
324  ((HIT_BITMAP_1) >> hit_bitmapShapeOffset((hit_bShapeCoordToLocal(bitshape,0, (i)))* \
325  hit_bShapeCard(bitshape,1)+(hit_bShapeCoordToLocal(bitshape,1, (j))))))
326 
335 #define hit_bShapeSetGlobal2(bitshape,i,j) {hit_bShapeSetGlobal(bitshape,i,j); hit_bShapeSetGlobal(bitshape,j,i);}
336 
346 #define hit_bShapeVertexToGlobal(s,vertex) (hit_nameListIndex2Name(hit_bShapeNameList(s,0),vertex))
347 
355 #define hit_bShapeVertexToLocal(s,vertex) (hit_nameListName2Index(hit_bShapeNameList(s,0),vertex))
356 
357 
364 #define hit_bShapeAddVertex(shapeP, x) hit_bShapeAddEmptyRow_or_Vertex(shapeP, x, HIT_BSHAPE_GRAPH)
365 
372 void hit_bShapeAddEmptyRow_or_Vertex(HitShape * shape, int x, int mode);
373 
374 
375 
384 HitShape hit_bShapeSelect(HitShape shape, int nvertices, int * vertices);
385 
394 HitShape hit_bShapeExpand(HitShape shape, HitShape original, int amount);
395 
404 
411 //void hit_bShapeAddVertex(HitShape * shape, int x);
412 
421 #define hit_bShapeAddEdge(shapep, x, y) hit_bShapeAddElem_or_Edge(shapep, x, y, HIT_BSHAPE_GRAPH)
422 
423 
432 #define hit_bShapeAddEdge2(shape,x,y) {hit_bShapeAddEdge(shape,x,y); hit_bShapeAddEdge(shape,y,x);}
433 
434 
435 /* 4. Hit Sparse Bitmap Shape Iterators */
436 
444 #define hit_bShapeRowIterator(var,shape) \
445  for(var=0; var<hit_bShapeCard(shape, 0); var++)
446 
447 
455 #define hit_bShapeVertexIterator(var,shape) hit_bShapeRowIterator(var,shape)
456 
457 
466 #define hit_bShapeColumnIterator(var,shape,row) \
467 for(var=hit_bShapeEdgeIteratorNextInternal(shape, -1, row);var<hit_bShapeCard(shape,1);var=hit_bShapeEdgeIteratorNextInternal(shape, var, row))
468 
469 
470 
479 #define hit_bShapeColumnIteratorSkip(var,shape,row) \
480 for(var=hit_bShapeEdgeIteratorNextInternalSkip(shape, row * hit_bShapeCard(shape,1));var<(row+1) * hit_bShapeCard(shape,1);var = hit_bShapeEdgeIteratorNextInternalSkip(shape, var+1))
481 #define hit_bShapeColumnIteratorDense(var,shape,row) \
482 for(var=0;var<hit_bShapeCard(shape,1);var++)
483 
484 
485 
494 #define hit_bShapeEdgeIterator(var,shape,vertex) hit_bShapeColumnIterator(var,shape,vertex)
495 
504 #define hit_bShapeEdgeIteratorSkip(var,shape,vertex) hit_bShapeColumnIteratorSkip(var,shape,vertex)
505 
514 #define hit_bShapeEdgeIteratorDense(var,shape,vertex) hit_bShapeColumnIteratorDense(var,shape,vertex)
515 
516 
527 // @todo @javfres Possible improvement: Speedup this function comparing the whole byte.
528 static inline int hit_bShapeEdgeIteratorNextInternal(HitShape shape, int var, int vertex){
529  //printf("--- row(%d) looking for next column (%d) \n",vertex,var);
530  do{
531  var++;
532  if(var == hit_bShapeCard(shape,1)){
533  //printf("--- exit because card ended (%d) \n",hit_bShapeCard(shape,1));
534  break;
535  }
536  } while(hit_bShapeGet(shape,vertex,var)==0);
537 
538  //printf("--- next column is (%d) \n",var);
539  return var;
540 }
541 
542 
543 // This works different form the other iterator, this uses the bitmap index as var
544 static inline int hit_bShapeEdgeIteratorNextInternalSkip(HitShape shape, int var){
545 
546  size_t i;
547 
548  // 1. Get the current index of the element and the offset of the bit in the element
549  size_t xind = hit_bitmapShapeIndex(var);
550  size_t xoff = hit_bitmapShapeOffset(var);
551 
552  //printf("xind %d, xoff %d\n",xind,xoff);
553 
554  // 2. Check if there is a bit his the current element (byte, or bytes)
555  HIT_BITMAP_TYPE element = hit_bShapeData(shape)[xind];
556  //printf("Element %s\n",hit_bitmap_tostring(element));
557  HIT_BITMAP_TYPE mask = HIT_BITMAP_1 >> xoff;
558  for(i=0;i<HIT_BITMAP_SIZE-xoff;i++){
559  if( (mask & element) != 0 ){
560  return var + (int) i; //@todo maybe this should return size_t types.
561  }
562  mask >>= 1;
563  }
564 
565  // 3. There is no 1 bits in the current element, find the next element that have 1s.
566  xind ++;
567  while( hit_bShapeData(shape)[xind] == 0 ){
568  xind++;
569  }
570 
571  // 4. We do the same as 2. to get the bit location
572  element = hit_bShapeData(shape)[xind];
573  mask = HIT_BITMAP_1;
574  for(i=0;i<HIT_BITMAP_SIZE;i++){
575  if( (mask & element) != 0 ){
576  return (int) (xind * HIT_BITMAP_SIZE + i);
577  }
578  mask >>= 1;
579  }
580 
581 
582  // This cannot occur
583  return -1;
584 }
585 
586 
587 
588 
589 
590 
591 
592 
593 
594 
595 
603 void hit_bShapeAddElem_or_Edge(HitShape * shape, int x, int y, int mode);
604 
605 
612 #define hit_bShapeAddElem(shapep, x, y) hit_bShapeAddElem_or_Edge(shapep, x, y, HIT_BSHAPE_MATRIX)
613 
614 
622 HitShape hit_bShapeSelectRows(HitShape shape, int nNames, int * names);
623 
624 
631 int hit_bShapeNColsRow(HitShape shape, int row);
632 
633 
639 #define hit_bitmapShapeVertexIterator(var,shape) for(var=0; var<hit_bitmapShapeNvertices(shape); var++)
640 #ifdef __cplusplus
641 }
642 #endif
643 
644 
645 /* END OF HEADER FILE _HitBShape_ */
646 #endif
647 
648 
HitShape hit_bShapeSelectRows(HitShape shape, int nNames, int *names)
Definition: hit_bshape.c:162
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)
#define hit_bShapeCard(shape, dim)
Definition: hit_bshape.h:144
HitShape hit_bShapeExpand(HitShape shape, HitShape original, int amount)
Definition: hit_bshape.c:193
#define y(a, b, c)
HitShape hit_bitmapShape(int nvertices)
Definition: hit_bshape.c:46
#define hit_bShapeData(shape)
Definition: hit_bshape.h:180
void hit_bShapeFree(HitShape shape)
Definition: hit_bshape.c:95
#define x
#define element(mat, idx1, idx2)
HitShape hit_bitmapShapeMatrix(int n, int m)
Definition: hit_bshape.c:69
HitShape shape
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
double ** buffer
Definition: refMPIluBack.c:103
void hit_bShapeCreateInvNames(HitShape *shape)