/[ascend]/trunk/ascend/utilities/set.h
ViewVC logotype

Diff of /trunk/ascend/utilities/set.h

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

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

Legend:
Removed from v.2038  
changed lines
  Added in v.2039

john.pye@anu.edu.au
ViewVC Help
Powered by ViewVC 1.1.22