1:
2:
3:/*
4: * $Id: context.c,v 1.1 2002/10/15 10:06:45 koschke Exp $
5: *
6: * CONCEPTS
7: * Copyright (C) 1994 Technical University of Braunschweig, Germany
8: * Written by Christian Lindig (lindig@ips.cs.tu-bs.de)
9: *
10: * This program is free software; you can redistribute it and/or modify
11: * it under the terms of the GNU General Public License as published by
12: * the Free Software Foundation; either version 2 of the License, or
13: * (at your option) any later version.
14: *
15: * This program is distributed in the hope that it will be useful,
16: * but WITHOUT ANY WARRANTY; without even the implied warranty of
17: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18: * GNU General Public License for more details.
19: *
20: * You should have received a copy of the GNU General Public License
21: * along with this program; if not, write to the Free Software
22: * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
23: *
24: *
25: * provides high level functions to build up a context (which is really a
26: * relation) and to calculate its concepts. */
27:
28:/* requires: ConceptDelete ConceptLattice ConceptNumber
29: HashCreateEntry HashEqEntry HashFindEntry HashFirstEntry HashGetId
30: HashGetKey HashGetValue HashNextEntry HashSetValue HashTabDelete
31: HashTabInit HashToMap ListDelete ListFindEntry ListGetValue
32: ListInit ListNewEntry ListSetValue RelDelete RelNew RelRelate free
33: malloc panic strdup */
34:
35:#include "config.h"
36:#if defined(STDC_HEADERS) || defined(HAVE_STDLIB_H)
37:# include <stdlib.h>
38:#endif
39:
40:#if STDC_HEADERS || defined(HAVE_STRING_H)
41:# include <string.h>
42:#else
43:# ifndef HAVE_MEMCPY
44:# define memcpy(d, s, n) bcopy ((s), (d), (n))
45:# define memmove(d, s, n) bcopy ((s), (d), (n))
46:# endif
47:#endif
48:
49:#ifdef DBMALLOC
50:# include <malloc.h>
51:#endif
52:
53:#include "defines.h"
54:#include "panic.h"
55:#include "list.h"
56:#include "hash.h"
57:#include "set.h"
58:#include "relation.h"
59:#include "concept.h"
60:#include "context.h"
61:
62:#ifndef HAVE_STRDUP
63:# include "lib.h"
64:#endif
65:
66:
67:/*
68: * ContextNew create a new context and initialize it. A Context holds
69: * objects and attributes (both as strings) in hash tables. Attributes
70: * are related to objects by calling ContextAddAttribute for a given
71: * object. To relate objects to attributes is not possible. Each
72: * object contains a list as client, which holds pointers to
73: * HashEntries (attributes). */
74:
75:Context *
76:ContextNew ()
77:
78:{
79: Context *context ;
80:
81: context = (Context*) malloc (sizeof (Context));
82: if (!context) {
83: panic ("malloc failed in %s:%i",__FILE__,__LINE__) ;
84: }
85: HashTabInit(&context->objects);
86: HashTabInit(&context->attributes);
87:
88: return (context);
89:}
90:
91:
92:/*
93: * ContextDelete
94: * remove an existing context from memory. */
95:
96:VOID
97:ContextDelete (context)
98:
99: Context *context ;
100:
101:{
102: HashSearch search;
103: HashEntry *entry ;
104: List *list;
105:
106:
107: /* traverse all objects. Each object contains a list as
108: client, which holds pointers to HashEntries
109: (attributes). */
110:
111: entry = HashFirstEntry (&context->objects,&search);
112: while (entry) {
113: list = (List*) HashGetValue(entry);
114: ListDelete (list); /* list contents */
115: free((char*)list); /* list struct */
116: entry = HashNextEntry(&context->objects,&search);
117: }
118: HashTabDelete(&context->objects);
119:
120: /* traverse all attributes */
121:
122: entry = HashFirstEntry (&context->attributes,&search);
123: while (entry) {
124: list = (List*) HashGetValue(entry);
125: ListDelete (list); /* list contents */
126: free((char*)list); /* list struct */
127: entry = HashNextEntry(&context->attributes,&search);
128: }
129: HashTabDelete(&context->attributes);
130:
131: /* free context itself */
132:
133: free ((char*) context);
134:}
135:
136:/*
137: * ContextAddObject
138: *
139: * adds an objects <name> to a given context. Returns a handle which is
140: * needed to add attributes to that object. */
141:
142:HashEntry *
143:ContextAddObject (context,name)
144:
145: Context *context;
146: char *name;
147:
148:{
149: int new ;
150: HashEntry *obj ;
151: List *list ;
152:
153: obj = HashCreateEntry(&context->objects,name,&new);
154: if(new) {
155: /*
156: * create a list as client data
157: */
158: list = (List*) malloc (sizeof(List));
159: if (!list) {
160: panic ("malloc failed in %s:%i",__FILE__,__LINE__) ;
161: }
162: /* initialize list */
163: ListInit (list);
164: HashSetValue(obj,(char*)list);
165: } /* else nothing has to be done - there allready exists a
166: list - the object has been previously added*/
167:
168: return obj;
169:}
170:
171:/*
172: * ContextAddAttribute
173: *
174: * add an attribute to an object of a given context. Nothing is returned */
175:
176:VOID
177:ContextAddAttribute (context,obj,name)
178:
179: Context *context;
180: HashEntry *obj;
181: char *name;
182:
183:{
184:
185: List *list;
186: ListEntry *entry; /* list entry at obj, pointing at attr*/
187: HashEntry *attr; /* real location of attribute */
188: int new ;
189:
190: /* each attribute is stored in the hashtable and has an
191: associated list. The list contains pointers to the objects
192: the attribut is related to. Also each object has a list
193: with pointers to its attributes */
194:
195: attr = HashCreateEntry (&context->attributes,name,&new);
196: if(new) {
197: /*
198: * create a list as client data
199: */
200: list = (List*) malloc (sizeof(List));
201: if (!list) {
202: panic ("malloc failed in %s:%i",__FILE__,__LINE__) ;
203: }
204: /* initialize list */
205: ListInit (list);
206: HashSetValue(attr,(char*)list);
207: } else {
208: /* get list from client data */
209:
210: list = (List*) HashGetValue(attr);
211: }
212:
213: /* add a pointer to obj at the list at atr */
214: /* check for duplicate */
215:
216: entry = ListFindEntry(list,(char*)obj,
217: (int (*)_ANSI_ARGS_((char *x, char *y)))
218: HashEqEntry);
219: if (!entry) {
220: /* no entry found - create one */
221: entry = ListNewEntry(list);
222: ListSetValue(entry,(char*)obj);
223: } else
224: /* else: this attribute has been previously related to the
225: object - nothing to do */
226:
227: return ;
228:
229:
230: /* add this attr to the list of attributes at obj */
231:
232: list = (List*) HashGetValue (obj); /* get list at obj */
233: entry = ListFindEntry(list,(char*)attr,
234: (int (*)_ANSI_ARGS_((char *x, char *y)))
235: HashEqEntry);
236: if (!entry) {
237: /* not member yet - create new entry */
238: entry = ListNewEntry(list); /* create new entry in that list */
239: ListSetValue (entry,(char*)attr); /* add attr to list at obj */
240: } else {
241:
242: /* because the attribute was previously unrelated to
243: obj, there can't be an entry - we have found one,
244: so it's an internal error */
245:
246: panic ("internal error in %s:%i",__FILE__,__LINE__);
247: }
248:}
249:
250:
251:/*
252: * ContextConcepts
253: *
254: * calculate all concepts from a given context and return it in
255: * a ContextLattice struct
256: */
257:
258:ContextLattice *
259:ContextConcepts (context)
260:
261: Context *context ;
262:
263:{
264: ContextLattice *lattice;
265: Relation rel;
266: char **objstr,**atrstr; /* all names of obj and atr */
267: int obj,atr;
268: ConceptArray array; /* all concepts stored here */
269:
270: lattice = (ContextLattice*) malloc (sizeof (ContextLattice));
271: if (!lattice) {
272: panic ("malloc failed in %s:%i",__FILE__,__LINE__) ;
273: }
274:
275: /* create Relation from Context */
276:
277: ContextToRel(context,&rel,&objstr,&atrstr,&obj,&atr);
278:
279: /* assign strings and sizes to lattice */
280:
281: lattice->obj = obj ;
282: lattice->atr = atr ;
283: lattice->objects = objstr ;
284: lattice->attributes = atrstr ;
285:
286: /* calculate concepts */
287:
288: ConceptLattice(&rel,&array);
289: lattice->concepts = array.concepts ;
290: lattice->conc = array.size ;
291:
292: /* free memory */
293:
294: RelDelete (&rel);
295:
296: return lattice ;
297:}
298:
299:/*
300: * ContextNumber
301: *
302: * calculate the number of concepts from a given context and return
303: * that number */
304:
305:int
306:ContextNumber (context)
307:
308: Context *context;
309:
310:{
311: Relation rel;
312: char **objstr,**atrstr; /* all names of obj and atr */
313: int obj,atr;
314: int count ;
315: int i;
316:
317: /* create Relation from Context */
318:
319: ContextToRel(context,&rel,&objstr,&atrstr,&obj,&atr);
320:
321: /* calculate concepts */
322:
323: count = ConceptNumber(&rel);
324:
325: /* free memory */
326:
327: RelDelete (&rel);
328:
329: for (i=0;i<obj;i++) {
330: free(objstr[i]);
331: }
332: free ((char*)objstr);
333:
334: for (i=0;i<atr;i++) {
335: free(atrstr[i]);
336: }
337: free ((char*)atrstr);
338:
339: return count;
340:
341:}
342:
343:/*
344: * ContextToRel
345: *
346: * create a Relation from a Context and return it. The mapping from
347: * intergers (in Relation) and names (in Context) for objects and
348: * attributes are also returned */
349:
350:VOID
351:ContextToRel (context,rel,objstr,atrstr,objs,atrs)
352:
353: Context *context;
354: Relation *rel;
355: char ***objstr,***atrstr;
356: int *objs,*atrs; /* number of obj and atr */
357:
358:{
359:
360: int obj,atr; /* number of ... */
361: HashMap objmap,atrmap; /* maps for .. */
362: int i; /* general purpose index */
363: char **objarray,**atrarray;
364: List *list;
365: ListEntry *entry;
366:
367:
368: /* use mappings instead of the raw HashTables */
369:
370: HashToMap(&context->objects,&objmap);
371: HashToMap(&context->attributes,&atrmap);
372:
373:
374: /* create space for all strings */
375:
376: obj = objmap.size ;
377: atr = atrmap.size ;
378:
379: /* return these numbers */
380:
381: *objs = obj ;
382: *atrs = atr ;
383:
384: objarray = (char**) malloc (sizeof (char*) * obj);
385: if (!objarray) {
386: panic ("malloc failed in %s:%i",__FILE__,__LINE__) ;
387: }
388:
389: atrarray = (char**) malloc (sizeof (char*) * atr);
390: if (!atrarray) {
391: panic ("malloc failed in %s:%i",__FILE__,__LINE__) ;
392: }
393:
394: /* initialize relation for (obj,atr) relation */
395:
396: RelNew(rel,atr,obj);
397:
398: /* traverse mappings and copy all names, store them in
399: objstr,atrstr */
400:
401: for (i=0;i<objmap.size;i++) {
402: objarray[i] = strdup (HashGetKey(objmap.map[i]));
403: if (!objarray[i])
404: panic ("strdup failed in %s:%i",__FILE__,__LINE__);
405: }
406: for (i=0;i<atrmap.size;i++) {
407: atrarray[i] = strdup (HashGetKey(atrmap.map[i]));
408: if (!atrarray[i])
409: panic ("strdup failed in %s:%i",__FILE__,__LINE__);
410: }
411:
412: /* set atrstr,objstr */
413:
414: *atrstr = atrarray;
415: *objstr = objarray;
416:
417: /* enter relation to rel */
418:
419: for (i=0;i<objmap.size;i++) {
420: if (!objmap.map[i])
421: break ;
422: list = (List*) HashGetValue (objmap.map[i]);
423: entry = list->first ;
424: while (entry) {
425: RelRelate(rel,
426: HashGetId((HashEntry*)ListGetValue(entry)),
427: i);
428: entry = entry->next ;
429:
430: }
431:
432: }
433:
434: /* free space malloc()'ed by HashToMap */
435:
436: free ((char*)objmap.map);
437: free ((char*)atrmap.map);
438:
439:}
440:
441:/*
442: * ContextRelated
443: * is a given object related to a given attribute?
444: */
445:
446:
447:int
448:ContextRelated (context,obj,atr)
449:
450: Context *context;
451: char *obj;
452: char *atr;
453:
454:{
455: HashEntry *object,*attribute;
456: List *list;
457: ListEntry *entry;
458:
459: object = HashFindEntry (&context->objects,obj);
460: if (!object) {
461: /* no such object! */
462: panic ("unknown object: %s in %s:%i",obj,__FILE__,__LINE__);
463: }
464: attribute = HashFindEntry (&context->attributes,atr);
465: if (!attribute) {
466: /* no such object! */
467: panic ("unknown attribute: %s in %s:%i",atr,__FILE__,__LINE__);
468: }
469:
470: /* obj and atr are known - are they related? */
471:
472: list = (List*) HashGetValue (object);
473: entry = ListFindEntry(list,(char*)attribute,
474: (int (*)_ANSI_ARGS_((char *x, char *y)))
475: HashEqEntry);
476:
477: return (entry != (ListEntry*)0);
478:
479:}
480:
481:
482:
483:/*
484: * ContextLatticeDelete
485: *
486: * free all memory associated with a ContextLattice */
487:
488:VOID
489:ContextLatticeDelete (lattice)
490:
491: ContextLattice *lattice ;
492:
493:{
494:
495: int i;
496:
497: /* get rid of all strings */
498:
499: for (i=0;i<lattice->obj;i++) {
500: if (!lattice->objects[i])
501: break ;
502: free (lattice->objects[i]);
503: }
504: free ((char*)lattice->objects);
505:
506: for (i=0;i<lattice->atr;i++) {
507: if (!lattice->attributes[i])
508: break ;
509: free (lattice->attributes[i]);
510: }
511: free ((char*)lattice->attributes);
512:
513: /* get rid of concepts */
514:
515: for (i=0;i<lattice->conc;i++) {
516: ConceptDelete(lattice->concepts[i]);
517: free ((char*)lattice->concepts[i]); /* free Concept struct */
518: }
519: free ((char*) lattice->concepts); /* free pointer array */
520:
521: /* free ContextLattice */
522:
523: free ((char*) lattice);
524:
525:}
526:
back ...