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 ...