1 /*****************************************************************************
2 FILE : $Source: /projects/higgs1/SNNS/CVS/SNNS/tools/sources/snns2clib.c,v $
3 SHORTNAME : snns2clib.c
4 SNNS VERSION : 4.2
5
6 PURPOSE : a Set Type with all needed applications
7
8 AUTHOR : Berward Kett
9 DATE : 30.01.95
10
11 CHANGED BY : Michael Vogt
12 RCS VERSION : $Revision: 1.10 $
13 LAST CHANGE : $Date: 1998/03/04 10:22:46 $
14
15 Copyright (c) 1990-1995 SNNS Group, IPVR, Univ. Stuttgart, FRG
16 Copyright (c) 1996-1998 SNNS Group, WSI, Univ. Tuebingen, FRG
17
18 ******************************************************************************/
19 #include <config.h>
20
21 #include <stdlib.h>
22 #include <string.h>
23 #include "glob_typ.h"
24
25 #ifndef NULL
26 #define NULL (void *)0
27 #endif
28
29 #define LIST_BLOCK_SIZE 10
30
31 /* Status (Error) Codes : OK = 0 (NO Error), ERR = 1, ... */
32 typedef enum { OK, ERR, CANT_ADD, CANT_LOAD, MEM_ERR,
33 WRONG_PARAM, WRONG_ACT_FUNC, CANT_OPEN,
34 ILLEGAL_CYCLES, NO_CPN} Status;
35
36 /* Recordtype for Lists (Sets) */
37 typedef struct {
38 int place; /* No of Elements wich can be hold in the list */
39 int no; /* No of actual Elements in the list */
40 int *values; /* Pointer to the Elements */
41 } tList, *pList;
42
43 #define NoOf(list) list->no
44 #define element(list, no) list->values[no]
45
46 /******************************************************************************
47 pList newList(void)
48 -----------------------------------------------------------------------------
49 makes a new, empty List
50 <- Pointer to the new list or NULL if an error occurs
51 ******************************************************************************/
newList(void)52 pList newList(void)
53 {
54 pList list;
55
56 list = (pList)malloc(sizeof(tList) );
57 if (NULL == list) {
58 return (NULL);
59 }
60 list->values = (int *)malloc(LIST_BLOCK_SIZE * sizeof(int) );
61 if (list->values == NULL) {
62 free(list);
63 return(NULL);
64 }
65 list->place = LIST_BLOCK_SIZE;
66 list->no = 0;
67 return(list);
68 }
69
70
71 /*****************************************************************************
72 void killList(pList list)
73 ----------------------------------------------------------------------------
74 kills a list and releases memory
75
76 -> pointer to the list
77 *****************************************************************************/
killList(pList list)78 void killList(pList list)
79 {
80 free(list->values);
81 free(list);
82 }
83
84
85 /*****************************************************************************
86 int copyList(pList dest, pList source)
87 ----------------------------------------------------------------------------
88 copies the sources list in the dest list
89 -> source : original List;
90 <-> dest : destination List;
91 <- (func) MEM_ERR : error occurs, dest leaves unchanged
92 OK : no problems
93 *****************************************************************************/
copyList(pList dest,pList source)94 int copyList(pList dest, pList source)
95 {
96 int *newValues;
97
98 newValues = (int *)malloc(source->place * sizeof(int) );
99 if (!newValues) return(MEM_ERR);
100 memcpy(newValues, source->values, NoOf(source) * sizeof(int) );
101
102 free(dest->values);
103
104 dest->no = source->no;
105 dest->place = source->place;
106 dest->values = newValues;
107 return(OK);
108 }
109
110
111 /******************************************************************************
112 int searchList(pList list, int member)
113 -----------------------------------------------------------------------------
114 searches an item in a list and returns the closest position.
115 e.g. if it is in the list it returns the position of the item,
116 otherwise the position where it should be inserted
117 if you only want to check if the item is member of the list use
118 isMember()
119
120 -> list : pointer to the list
121 member : item, wich is searched in the list
122 <- (func) position of the item if it exist
123 ******************************************************************************/
searchList(pList list,int member)124 int searchList(pList list, int member)
125 {
126 int low, high, pos = 0;
127 low = 0;
128 high = list->no -1;
129
130 if (list->no == 0) { /* empty list */
131 list->values[0] = ++member; /* must not be equal to member */
132 return(0);
133 }
134
135 while (high > low) {
136 pos = (high + low) / 2; /* binary search because the values are sorted */
137 if (member > list->values[pos]) {
138 low = pos + 1; /* in this order, you get the place were */
139 } /* member should be inserted if not present */
140 else if (member < list->values[pos]) {
141 high = pos;
142 }
143 else {
144 return(pos);
145 }
146 }
147 return(high);
148 }
149
150
151 /*****************************************************************************
152 int isMember(pList list, int member)
153 ----------------------------------------------------------------------------
154 checks, if member is part of a list
155
156 -> list : pointer to the list
157 member : member wich is to be removed
158 <- TRUE if it is member and FALSE otherwise
159 *****************************************************************************/
isMember(pList list,int member)160 bool isMember(pList list, int member)
161 {
162 int pos;
163 pos = searchList(list, member);
164 return(list->values[pos] == member);
165 }
166
167
168 /*****************************************************************************
169 int addList(pList list, int member)
170 ----------------------------------------------------------------------------
171 inserts a new member in a list and reserves new memory if needed
172
173 -> list : pointer to the list
174 member : new member, wich must be added
175 <- (func) (OK) no problems
176 (CANT_ADD) not enough memory for another element
177 *****************************************************************************/
addList(pList list,int member)178 int addList(pList list, int member)
179 {
180 int *oldptr, pos, j;
181 pos = searchList(list, member);
182 if (element(list, pos) == member) return(OK); /* no double entries */
183
184 if (list->no == list->place) { /* e.g. more space is needed */
185 oldptr = list->values;
186 list->place += LIST_BLOCK_SIZE;
187 list->values = (int *)realloc( list->values, list->place * sizeof (int) );
188 if (list->values == NULL) { /* no more space available */
189 list->place -= LIST_BLOCK_SIZE; /* restore old state */
190 list->values = oldptr;
191 return(CANT_ADD);
192 }
193 }
194
195 if (list->values[list->no - 1] < member) {
196 pos = list->no; /* so append at the end */
197 }
198 for (j = list->no; j > pos; j--) { /* making place for new entry */
199 list->values[j] = list->values[j-1];
200 }
201 list->values[pos] = member;
202 (list->no)++;
203
204 return (OK); /* everything all right */
205 }
206
207
208 /*****************************************************************************
209 void remList(pList list, int member)
210 ----------------------------------------------------------------------------
211 removes an item from a list if the item exists in it. Otherwise nothing
212 happens. Releases also unneeded memory.
213
214 -> list : pointer to the list
215 member : member wich is to be removed
216 *****************************************************************************/
remList(pList list,int member)217 void remList(pList list, int member)
218 {
219 int i, pos;
220 pos = searchList(list, member); /* search for (possible) position */
221 if (member == list->values[pos]) { /* really a member ? */
222 for (i = pos; i < list->no - 1; i++) { /* shift all following members */
223 list->values[i] = list->values[i+1];
224 }
225 (list->no)--; /* loosed one member */
226 }
227
228 if (list->no < list->place - LIST_BLOCK_SIZE) { /* release unneeded memory */
229 list->place -= LIST_BLOCK_SIZE;
230 list->values = (int *)realloc(list->values, list->place *sizeof(int) );
231 }
232 }
233
234
235 /*****************************************************************************
236 void intersectList(pList dest, pList source)
237 ----------------------------------------------------------------------------
238 puts the intersection of dest and sources into dest
239 -> sources : unchanged list
240 <-> dest : list wich contains the intersection after intersect list
241 *****************************************************************************/
intersectList(pList dest,pList source)242 void intersectList(pList dest, pList source)
243 {
244 int i = 0, j;
245 while (i < NoOf(dest) ) {
246 if (!isMember(source, element(dest, i) ) ) {
247 ( NoOf(dest) )--;
248 for (j = i; j < NoOf(dest); j++) { /* kill element by overwrite */
249 element(dest, j) = element(dest, j + 1);
250 } /* so the same place must be checked */
251 }
252 else {
253 i++; /* element found, so check next one */
254 }
255 }
256 }
257
258
259 /*****************************************************************************
260 int haveIntersection(pList list1, pList list2)
261 ----------------------------------------------------------------------------
262 checks if list1 and list2 have an identical member
263 -> list1, list2 : Lists wich will be checked
264 <- (func) TRUE : they have
265 FALSE : they haven't
266 *****************************************************************************/
haveIntersection(pList list1,pList list2)267 bool haveIntersection(pList list1, pList list2)
268 {
269 int i;
270 for(i = 0; i < NoOf(list1); i++) {
271 if (isMember(list2, element(list1, i) ) ) return (TRUE);
272 }
273 return (FALSE);
274 }
275
276
277 /*****************************************************************************
278 int mergeList(pList destList, pList sourcesList)
279 ----------------------------------------------------------------------------
280 puts all members of sourceList in destList
281 -> source : unchanged List
282 <-> destList : List wich contains all Elements after 'mergeList'
283 <- (func) (OK) no problems
284 (MEM_ERR) not enough memory for another element
285 *****************************************************************************/
mergeList(pList dest,pList source)286 int mergeList(pList dest, pList source)
287 {
288 int sc = 0, dc = 0, bc = 0; /* counters for source, dest, big */
289 pList big; /* list for all Elements */
290 int *old, place; /* helppointer and needed memory */
291
292 big = newList(); /* create new List */
293 if (!big) return(MEM_ERR);
294
295 /** allocate (maximum)Memory for the new List **/
296 place = NoOf(source) + NoOf(dest);
297 /* align to LIST_BLOCK_SIZE */
298 place = ( (place / LIST_BLOCK_SIZE) + 1) * LIST_BLOCK_SIZE;
299 old = big->values;
300 big->place = place;
301 big->values = (int *)realloc(big->values, place * sizeof (int) );
302 if (big->values == NULL) {
303 big->values = old; /* for killing the whole list */
304 killList(big);
305 return(MEM_ERR);
306 }
307
308 while ( (sc < NoOf(source) ) && (dc < NoOf(dest) ) )
309 {
310 if ( element(source, sc) < element(dest, dc) ) {
311 element(big, bc++) = element(source, sc++);
312 }
313 else {
314 element(big, bc++) = element(dest, dc++);
315 /* if elements of dource and dest were equal */
316 if (element(source, sc) == element(big, bc -1) ) sc++;
317 }
318
319 }
320
321 /* now only one list may have elements */
322 while (sc < NoOf(source) ) {
323 element(big, bc++) = element(source, sc++);
324 }
325 while (dc < NoOf(dest) ) {
326 element(big, bc++) = element(dest, dc++);
327 }
328
329 big->no = bc;
330
331 while (NoOf(big) + LIST_BLOCK_SIZE < big->place) {
332 big->place -= LIST_BLOCK_SIZE;
333 big->values = (int *)realloc(big->values, big->place * sizeof(int) );
334 }
335
336 /* move contens of big in dest */
337 free(dest->values);
338 dest->values = big->values;
339 dest->no = big->no;
340 dest->place = big->place;
341 free(big);
342
343 return(OK);
344 }
345
346 /****************************************************************************
347 int CompareSources( pList dest, pList source)
348 ----------------------------------------------------------------------------
349 compares two sources sets 1 = equal
350 *****************************************************************************/
351
CompareSources(pList dest,pList source)352 int CompareSources( pList dest, pList source)
353 {
354 int i = 0;
355 while (i < NoOf(dest) ){
356 if (!isMember(source, element(dest, i) ) )
357 return 0;
358 i++;
359 }
360
361 i = 0;
362 while (i < NoOf(source) ){
363 if (!isMember(dest, element(source, i) ) )
364 return 0;
365 i++;
366 }
367
368 return 1;
369 }
370