box_heap.c
Go to the documentation of this file.
1 #include "box_heap.h"
2 
3 #include "interval.h"
4 
5 #include "boolean.h"
6 #include "defines.h"
7 
8 #include <stdio.h>
9 #include <stdlib.h>
10 #include <string.h>
11 
21 void InitHeapOfBoxes(boolean (* LessThan)(void *,void*,void*),void *userData,Theap *h)
22 {
23  InitHeap(sizeof(Tbox),CopyBox,DeleteBox,LessThan,userData,FALSE,INIT_NUM_BOXES_IN_HEAP,h);
24 }
25 
27 {
28  AddElement2Heap(NO_UINT,(void *)b,h);
29 }
30 
31 double HeapOfBoxesVolume(boolean *used,Theap *h)
32 {
33  unsigned int i,n;
34  double v;
35 
36  n=HeapSize(h);
37 
38  v=0;
39  for(i=0;i<n;i++)
40  v+=GetBoxVolume(used,(Tbox *)GetHeapElement(i,h));
41 
42  return(v);
43 }
44 
45 double HeapOfBoxesMaxDiagonal(boolean *used,Theap *h)
46 {
47  unsigned int i,n;
48  double d,md;
49 
50  n=HeapSize(h);
51 
52  md=0;
53  for(i=0;i<n;i++)
54  {
55  d=GetBoxDiagonal(used,(Tbox *)GetHeapElement(i,h));
56  if (d>md)
57  md=d;
58  }
59 
60  return(md);
61 }
62 
63 double HeapOfBoxesMaxSize(boolean *used,Theap *h)
64 {
65  unsigned int i,n;
66  double s,ms;
67 
68  n=HeapSize(h);
69 
70  ms=0;
71  for(i=0;i<n;i++)
72  {
73  s=GetBoxSize(used,(Tbox *)GetHeapElement(i,h));
74  if (s>ms)
75  ms=s;
76  }
77 
78  return(ms);
79 }
80 
81 
82 void Heap2List(Tlist *l,Theap *h)
83 {
84  unsigned int i,n;
85  Tbox b;
86 
87  InitListOfBoxes(l);
88 
89  n=HeapSize(h);
90  for(i=0;i<n;i++)
91  {
92  CopyBox(&b,GetHeapElement(i,h));
93  AddLastElement(&b,l);
94  }
95 }
96 
98 {
99  Titerator i;
100 
101  InitIterator(&i,l);
102  First(&i);
103  while(!EndOfList(&i))
104  {
106  Advance(&i);
107  }
108 }
109 
110 void PrintHeapOfBoxes(FILE *f,boolean *used,char *heading,Theap *h)
111 {
112  unsigned int i,n;
113 
114  n=HeapSize(h);
115  for(i=0;i<n;i++)
116  {
117  if (heading!=NULL) fprintf(f,"%s ",heading);
118  fprintf(f,"%u : ",i);
119  PrintBoxSubset(f,used,NULL,(Tbox *)GetHeapElement(i,h));
120  }
121  fflush(f);
122 }
123 
124 
Definition of the boolean type.
void First(Titerator *i)
Moves an iterator to the first position of its associated list.
Definition: list.c:356
#define FALSE
FALSE.
Definition: boolean.h:30
double GetBoxSize(boolean *used, Tbox *b)
Computes the size of the box.
Definition: box.c:607
Collection of methods to work on Theap of boxes.
void AddBox2HeapOfBoxes(Tbox *b, Theap *h)
Adds a box to a heap of boxes.
Definition: box_heap.c:26
double HeapOfBoxesVolume(boolean *used, Theap *h)
Computes the volume of a heap.
Definition: box_heap.c:31
double HeapOfBoxesMaxSize(boolean *used, Theap *h)
Computes the maximum size for all boxes in a heap.
Definition: box_heap.c:63
void AddElement2Heap(unsigned int id, void *e, Theap *heap)
Adds an element to the heap.
Definition: heap.c:294
void AddLastElement(void *Info, Tlist *list)
Adds an element at the tail of the list.
Definition: list.c:206
void * GetHeapElement(unsigned int i, Theap *heap)
Returns a pointer to a heap element.
Definition: heap.c:331
unsigned int HeapSize(Theap *heap)
Gets the number of elements in a heap.
Definition: heap.c:284
boolean EndOfList(Titerator *i)
Checks if an iterator is pointing at the end of the list.
Definition: list.c:445
Definitions of constants and macros used in several parts of the cuik library.
A generic list.
Definition: list.h:46
void InitIterator(Titerator *i, Tlist *list)
Constructor.
Definition: list.c:284
void CopyBox(void *b_out, void *b_in)
Box copy operator.
Definition: box.c:160
double GetBoxDiagonal(boolean *used, Tbox *b)
Computes the diagonal of a (sub-)box.
Definition: box.c:654
#define INIT_NUM_BOXES_IN_HEAP
Initial room for boxes in a heap of boxes.
Definition: box_heap.h:27
void InitHeap(unsigned int ele_size, void(*Copy)(void *, void *), void(*Delete)(void *), boolean(*LessThan)(void *, void *, void *), void *userData, boolean hasIDs, unsigned int max_ele, Theap *heap)
Constructor.
Definition: heap.c:237
A box.
Definition: box.h:83
void InitListOfBoxes(Tlist *l)
Constructor.
Definition: box_list.c:24
void PrintHeapOfBoxes(FILE *f, boolean *used, char *heading, Theap *h)
Prints a heap of boxes.
Definition: box_heap.c:110
void * GetCurrent(Titerator *i)
Gets the element pointed by the iterator.
Definition: list.c:299
#define NO_UINT
Used to denote an identifier that has not been initialized.
Definition: defines.h:435
void DeleteBox(void *b)
Destructor.
Definition: box.c:1259
void PrintBoxSubset(FILE *f, boolean *used, char **varNames, Tbox *b)
Prints a (sub-)box.
Definition: box.c:1138
double HeapOfBoxesMaxDiagonal(boolean *used, Theap *h)
Computes the maximum diagonal for all boxes in a heap.
Definition: box_heap.c:45
A generic binary heap.
Definition: heap.h:105
List iterator.
Definition: list.h:61
void InitHeapOfBoxes(boolean(*LessThan)(void *, void *, void *), void *userData, Theap *h)
Constructor.
Definition: box_heap.c:21
void Heap2List(Tlist *l, Theap *h)
Converts a heap of boxes into a list.
Definition: box_heap.c:82
double GetBoxVolume(boolean *used, Tbox *b)
Computes the volume of the box.
Definition: box.c:956
boolean Advance(Titerator *i)
Moves an iterator to the next position of its associated list.
Definition: list.c:373
void AddList2Heap(Tlist *l, Theap *h)
Adds a list of boxes into a heap.
Definition: box_heap.c:97
Definition of the Tinterval type and the associated functions.