ascend/utilities/set.h

/*
 *  Set module
 *  by Karl Westerberg
 *  Created: 6/90
 *  Version: $Revision: 1.4 $
 *  Version control file: $RCSfile: set.h,v $
 *  Date last modified: $Date: 1997/07/18 12:04:30 $
 *  Last modified by: $Author: mthomas $
 *
 *  This file is part of the Ascend Language Interpreter.
 *
 *  Copyright (C) 1997 Carnegie Mellon University
 *
 *  The Ascend Language Interpreter is free software; you can redistribute
 *  it and/or modify it under the terms of the GNU General Public License as
 *  published by the Free Software Foundation; either version 2 of the
 *  License, or (at your option) any later version.
 *
 *  The Ascend Language Interpreter is distributed in hope that it will be
 *  useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with the program; if not, write to the Free Software Foundation,
 *  Inc., 675 Mass Ave, Cambridge, MA 02139 USA.  Check the file named
 *  COPYING.  COPYING is in ../compiler.
 */

/*
 *  Contents:     Set module
 *
 *  Authors:      Karl Westerberg
 *
 *  Dates:        06/90 - original version
 *
 *  Description:  This module is responsible for primitive manipulation
 *                of sets of integers (using a binary bit map technique).
 *                In particular, the set variables have domain
 *                {k in N | k < n}, where n is a fixed constant, which
 *                we will call the (bit-)size of the set.  The sets are
 *                actually arrays of unsigned of appropriate length,
 *                and pointers to such arrays can actually be used in
 *                place of pointers returned by set_create() (although
 *                one must be careful not to destroy such sets with
 *                set_destroy()).
 */

/** @file
 *  Integer set module.
 *  This module supports primitive manipulation of sets of positive
 *  integers.  It provides functions for creating, adding to, removing
 *  from, querying, and destroying such sets.  Note that much of the
 *  module's functionality is not used by ASCEND and is deprecated.
 *  <pre>
 *  Requires:     #include "utilities/ascConfig.h"
 *                #include "utilities/ascMalloc.h"
 *  </pre>
 */

#ifndef _set_h_seen
#define _set_h_seen

#define set_size(n) \
   (((n)+((int)WORDSIZE-1))/(int)WORDSIZE)
/**<
 *  Returns the number of unsigned ints required to store a set of n bits.
 *  WORDSIZE is computed in ascConfig.h.  Clients should not need to use
 *  this function directly.  It is needed for other macro definitions in
 *  this file.
 *
 *  @param n int, the number of bits (or ints) to store.
 *  @return The number of unsigned ints needed as an int.
 */

#define set_create(n) ( set_size(n)>0 ? ASC_NEW_ARRAY(unsigned,set_size(n)) : NULL )
/**<
 *  Creates a new set of size n.
 *  The size indicates the maximum integer that the set can hold.
 *  The initial contents are garbage.  The caller is responsible for
 *  deallocating the returned set using set_destroy().
 *
 *  @param n int, the size for the new set.
 *  @return A pointer to the newly-created set (as an unsigned *), or NULL
 *          if (n <= 0) or memory could not be allocated.
 */

#define set_destroy(set) \
   (ascfree((POINTER)set))
/**<
 *  Destroys a set.
 *  The set should have been created using set_create().
 *
 *  @param set unsigned *, the set to destroy.
 *  @return No return value.
 */

#define set_ndx(k) \
   ((k)/(int)WORDSIZE)
/**<
 *  Index into array of unsigned where element k's status is found.
 *  Clients should not need to use this function directly.  It is
 *  needed for other macro definitions in this file.
 *
 *  @param k int, the element whose index is needed.
 *  @return The index of k as an int.
 */

/*
 *  previous definition: trying to get rid of mask.h
 *
 *#define   set_mask(k) \
 *   mask_I_E((k)%WORDSIZE)
 */
#define set_mask(k) \
   (((unsigned)1) << ((k)%WORDSIZE))
/**<
 *  Returns an integer with the bit corresponding to element k turned on.
 *  Clients should not need to use this function directly.  It is
 *  needed for other macro definitions in this file.
 *
 *  @param k int, the element for which to turn on a bit.
 *  @return The bitmask for k as an unsigned int.
 */

#define set_is_member(set,k) \
   ((set[set_ndx(k)] & set_mask(k)) != 0)
/**<
 *  Tests whether element k belongs to a given set.
 *  It is assumed that 0 <= k < n, where n is the size of the set.
 *
 *  @param set  unsigned *, the set to check for k.
 *  @param k    int, the element to evaluate.
 *  @return TRUE if k belongs to the given set, FALSE otherwise.
 */

#define set_chk_is_member(set,k,n) \
   ((k)>=0 && (k)<(n) && set_is_member(set,k))
/**<
 *  Tests whether element k belongs to a given set with validation.
 *  This is the same as set_is_member(), except that validation is
 *  first done to ensure k is within the range of set.
 *
 *  @param set  unsigned *, the set to check for k (non-NULL).
 *  @param k    int, the element to validate and evaluate.
 *  @param n    int, the size of the set.
 *  @return TRUE if k belongs to the given set, FALSE otherwise.
 */

ASC_DLLSPEC unsigned int *set_null(unsigned int *set, int n);
/**<
 *  Clears a set so that it has no elements.
 *  The size of the set must be indicated.
 *  set may not be NULL (checked by assertion).
 *
 *  @param set The set to clear (non-NULL).
 *  @param n   The size of the set.
 *  @return Returns a pointer to the set.
 */

ASC_DLLSPEC void set_change_member(unsigned int *set, int k, boolean value);
/**<
 *  Adds or removes an element from a set.
 *  If value==TRUE, then k is added to the set.  Otherwise k 
 *  is taken out of the set.  It is assumed that 0 <= k < n.
 *  set may not be NULL (checked by assertion).
 *
 *  @param set  The set to modify (non-NULL).
 *  @param k    The element to add or remove.
 *  @param value Flag for action:  TRUE -> k is added, FALSE -> k is removed.
 */

#ifdef THIS_IS_DEAD_CODE

extern unsigned int *set_copy(unsigned int *set, unsigned int *target,
                              int n, int n2);
/**<
 *  Copies one set to another.  The bit size of the source and
 *  target must be given.  If the size of the target is less
 *  than the source, then the set is truncated.  If the size of
 *  the target is more than the source, then the set is extended
 *  with 0's.  It is assumed that the target has already been
 *  created. Returns the pointer to target.
 *  @deprecated This function is not in use or supported.
 */

extern void set_change_member_rng(unsigned int *set,
                                  int k1, int k2, boolean value);
/**<
 *  Changes the membership status for all elements
 *  in k1..k2 (see set_change_member).  It is assumed
 *  that 0 <= k1,k2 < n.
 *  @deprecated This function is not in use or supported.
 */

extern int set_find_next(unsigned int *set, int k, int n);
/**<
 *  Returns the first member of set greater than k.
 *  If k=-1 upon entering, the minimum of the set is
 *  returned.  If return>=n upon exiting, then there is no
 *  member in the set greater than k.
 *  @deprecated This function is not in use or supported.
 */

extern int set_count(unsigned int *set, int n);
/**<
 *  Returns the cardinality of the set.
 *  @deprecated This function is not in use or supported.
 */

extern unsigned *set_complement(unsigned int *set, int n);
/**<
 *  Removes all elements which are currently in the
 *  set and adds all elements which were not.
 *  Returns pointer to set.
 *  @deprecated This function is not in use or supported.
 */

extern unsigned *set_intersect(unsigned int *set1,
                               unsigned int *set2,
                               int n, int n2);
/**<
 *  Replaces set with the intersection of set and set2.
 *  The bit-sizes of each set must be given (if they are
 *  different, then set2 is effectively extended or truncated
 *  for purposes of computing intersection, although the
 *  size change does not actually occur).
 *  Returns the pointer to set, which has been modified.
 *  @deprecated This function is not in use or supported.
 */

extern unsigned *set_union(unsigned int *set,
                           unsigned int *set2,
                           int n, int n2);
/**<
 *  Replaces set with the union of set and set2.
 *  Size mismatch handled as for intersection.
 *  Returns the pointer to set, which has been modified.
 *  @deprecated This function is not in use or supported.
 */

#endif /* THIS_IS_DEAD_CODE */

#endif  /* _set_h_seen  */

1	/*
2	* Set module
3	* by Karl Westerberg
4	* Created: 6/90
5	* Version: $Revision: 1.4 $
6	* Version control file: $RCSfile: set.h,v $
7	* Date last modified: $Date: 1997/07/18 12:04:30 $
8	* Last modified by: $Author: mthomas $
9	*
10	* This file is part of the Ascend Language Interpreter.
11	*
12	* Copyright (C) 1997 Carnegie Mellon University
13	*
14	* The Ascend Language Interpreter is free software; you can redistribute
15	* it and/or modify it under the terms of the GNU General Public License as
16	* published by the Free Software Foundation; either version 2 of the
17	* License, or (at your option) any later version.
18	*
19	* The Ascend Language Interpreter is distributed in hope that it will be
20	* useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
21	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
22	* General Public License for more details.
23	*
24	* You should have received a copy of the GNU General Public License
25	* along with the program; if not, write to the Free Software Foundation,
26	* Inc., 675 Mass Ave, Cambridge, MA 02139 USA. Check the file named
27	* COPYING. COPYING is in ../compiler.
28	*/
29
30	/*
31	* Contents: Set module
32	*
33	* Authors: Karl Westerberg
34	*
35	* Dates: 06/90 - original version
36	*
37	* Description: This module is responsible for primitive manipulation
38	* of sets of integers (using a binary bit map technique).
39	* In particular, the set variables have domain
40	* {k in N \| k < n}, where n is a fixed constant, which
41	* we will call the (bit-)size of the set. The sets are
42	* actually arrays of unsigned of appropriate length,
43	* and pointers to such arrays can actually be used in
44	* place of pointers returned by set_create() (although
45	* one must be careful not to destroy such sets with
46	* set_destroy()).
47	*/
48
49	/** @file
50	* Integer set module.
51	* This module supports primitive manipulation of sets of positive
52	* integers. It provides functions for creating, adding to, removing
53	* from, querying, and destroying such sets. Note that much of the
54	* module's functionality is not used by ASCEND and is deprecated.
55	* <pre>
56	* Requires: #include "utilities/ascConfig.h"
57	* #include "utilities/ascMalloc.h"
58	* </pre>
59	*/
60
61	#ifndef _set_h_seen
62	#define _set_h_seen
63
64	#define set_size(n) \
65	(((n)+((int)WORDSIZE-1))/(int)WORDSIZE)
66	/**<
67	* Returns the number of unsigned ints required to store a set of n bits.
68	* WORDSIZE is computed in ascConfig.h. Clients should not need to use
69	* this function directly. It is needed for other macro definitions in
70	* this file.
71	*
72	* @param n int, the number of bits (or ints) to store.
73	* @return The number of unsigned ints needed as an int.
74	*/
75
76	#define set_create(n) ( set_size(n)>0 ? ASC_NEW_ARRAY(unsigned,set_size(n)) : NULL )
77	/**<
78	* Creates a new set of size n.
79	* The size indicates the maximum integer that the set can hold.
80	* The initial contents are garbage. The caller is responsible for
81	* deallocating the returned set using set_destroy().
82	*
83	* @param n int, the size for the new set.
84	* @return A pointer to the newly-created set (as an unsigned *), or NULL
85	* if (n <= 0) or memory could not be allocated.
86	*/
87
88	#define set_destroy(set) \
89	(ascfree((POINTER)set))
90	/**<
91	* Destroys a set.
92	* The set should have been created using set_create().
93	*
94	* @param set unsigned *, the set to destroy.
95	* @return No return value.
96	*/
97
98	#define set_ndx(k) \
99	((k)/(int)WORDSIZE)
100	/**<
101	* Index into array of unsigned where element k's status is found.
102	* Clients should not need to use this function directly. It is
103	* needed for other macro definitions in this file.
104	*
105	* @param k int, the element whose index is needed.
106	* @return The index of k as an int.
107	*/
108
109	/*
110	* previous definition: trying to get rid of mask.h
111	*
112	*#define set_mask(k) \
113	* mask_I_E((k)%WORDSIZE)
114	*/
115	#define set_mask(k) \
116	(((unsigned)1) << ((k)%WORDSIZE))
117	/**<
118	* Returns an integer with the bit corresponding to element k turned on.
119	* Clients should not need to use this function directly. It is
120	* needed for other macro definitions in this file.
121	*
122	* @param k int, the element for which to turn on a bit.
123	* @return The bitmask for k as an unsigned int.
124	*/
125
126	#define set_is_member(set,k) \
127	((set[set_ndx(k)] & set_mask(k)) != 0)
128	/**<
129	* Tests whether element k belongs to a given set.
130	* It is assumed that 0 <= k < n, where n is the size of the set.
131	*
132	* @param set unsigned *, the set to check for k.
133	* @param k int, the element to evaluate.
134	* @return TRUE if k belongs to the given set, FALSE otherwise.
135	*/
136
137	#define set_chk_is_member(set,k,n) \
138	((k)>=0 && (k)<(n) && set_is_member(set,k))
139	/**<
140	* Tests whether element k belongs to a given set with validation.
141	* This is the same as set_is_member(), except that validation is
142	* first done to ensure k is within the range of set.
143	*
144	* @param set unsigned *, the set to check for k (non-NULL).
145	* @param k int, the element to validate and evaluate.
146	* @param n int, the size of the set.
147	* @return TRUE if k belongs to the given set, FALSE otherwise.
148	*/
149
150	ASC_DLLSPEC unsigned int set_null(unsigned int set, int n);
151	/**<
152	* Clears a set so that it has no elements.
153	* The size of the set must be indicated.
154	* set may not be NULL (checked by assertion).
155	*
156	* @param set The set to clear (non-NULL).
157	* @param n The size of the set.
158	* @return Returns a pointer to the set.
159	*/
160
161	ASC_DLLSPEC void set_change_member(unsigned int *set, int k, boolean value);
162	/**<
163	* Adds or removes an element from a set.
164	* If value==TRUE, then k is added to the set. Otherwise k
165	* is taken out of the set. It is assumed that 0 <= k < n.
166	* set may not be NULL (checked by assertion).
167	*
168	* @param set The set to modify (non-NULL).
169	* @param k The element to add or remove.
170	* @param value Flag for action: TRUE -> k is added, FALSE -> k is removed.
171	*/
172
173	#ifdef THIS_IS_DEAD_CODE
174
175	extern unsigned int set_copy(unsigned int set, unsigned int *target,
176	int n, int n2);
177	/**<
178	* Copies one set to another. The bit size of the source and
179	* target must be given. If the size of the target is less
180	* than the source, then the set is truncated. If the size of
181	* the target is more than the source, then the set is extended
182	* with 0's. It is assumed that the target has already been
183	* created. Returns the pointer to target.
184	* @deprecated This function is not in use or supported.
185	*/
186
187	extern void set_change_member_rng(unsigned int *set,
188	int k1, int k2, boolean value);
189	/**<
190	* Changes the membership status for all elements
191	* in k1..k2 (see set_change_member). It is assumed
192	* that 0 <= k1,k2 < n.
193	* @deprecated This function is not in use or supported.
194	*/
195
196	extern int set_find_next(unsigned int *set, int k, int n);
197	/**<
198	* Returns the first member of set greater than k.
199	* If k=-1 upon entering, the minimum of the set is
200	* returned. If return>=n upon exiting, then there is no
201	* member in the set greater than k.
202	* @deprecated This function is not in use or supported.
203	*/
204
205	extern int set_count(unsigned int *set, int n);
206	/**<
207	* Returns the cardinality of the set.
208	* @deprecated This function is not in use or supported.
209	*/
210
211	extern unsigned set_complement(unsigned int set, int n);
212	/**<
213	* Removes all elements which are currently in the
214	* set and adds all elements which were not.
215	* Returns pointer to set.
216	* @deprecated This function is not in use or supported.
217	*/
218
219	extern unsigned set_intersect(unsigned int set1,
220	unsigned int *set2,
221	int n, int n2);
222	/**<
223	* Replaces set with the intersection of set and set2.
224	* The bit-sizes of each set must be given (if they are
225	* different, then set2 is effectively extended or truncated
226	* for purposes of computing intersection, although the
227	* size change does not actually occur).
228	* Returns the pointer to set, which has been modified.
229	* @deprecated This function is not in use or supported.
230	*/
231
232	extern unsigned set_union(unsigned int set,
233	unsigned int *set2,
234	int n, int n2);
235	/**<
236	* Replaces set with the union of set and set2.
237	* Size mismatch handled as for intersection.
238	* Returns the pointer to set, which has been modified.
239	* @deprecated This function is not in use or supported.
240	*/
241
242	#endif /* THIS_IS_DEAD_CODE */
243
244	#endif /* _set_h_seen */
245