home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / Libraries / StdSet 1.0 / ReadMe next >
Encoding:
Text File  |  1997-07-20  |  18.1 KB  |  500 lines  |  [ttro/ttxt]
  1. StdSet 1.0
  2. Operations for sets of long integers or pointers, ReadMe.
  3. Copyright (c) 1996, 1997 by John Montbriand.  All Rights Reserved.
  4. Permission hereby granted for public use.
  5. Distribute freely in areas where the laws of copyright apply.
  6. USE AT YOUR OWN RISK.
  7. DO NOT DISTRIBUTE MODIFIED COPIES.
  8. Comments/questions/postcards* to the author at the address:
  9.   John Montbriand
  10.   P.O. Box. 1133
  11.   Saskatoon Saskatchewan Canada
  12.   S7K 3N2
  13. or by email at:
  14.    tinyjohn@sk.sympatico.ca
  15. *if you mail a postcard, then I will provide you with technical support
  16. regarding questions you may have about this file.
  17.    see also: <http://www3.sk.sympatico.ca/tinyjohn>
  18.  
  19.  
  20. Contents
  21. About StdSet...
  22. Implementation Notes
  23. Materials
  24. Creating and Disposing of SetHandles
  25.     NewSet
  26.     BuildSet
  27.     DisposeSet
  28. SetHandle Information Access
  29.     SetCard 
  30.     SetEmpty
  31.     SetElement
  32.     SetMember
  33.     SetEqual
  34.     SetSubset
  35. Operations on SetHandles
  36.     ClearSet
  37.     SetCopy
  38.     SetAddElt
  39.     SetRemoveElt
  40.     SetAnd
  41.     SetOr
  42.     SetXor
  43.     SetRemove
  44. Sets and PowerSets
  45.     GeneratePowerSet
  46.     DisposePowerSet
  47.     PowerSetSize
  48.     PowerSetElt
  49. Permutations
  50.     SetPermute
  51. Sets of Pointers, an example
  52. A Set of What???
  53. Files in this package
  54. Copies for sale!
  55. NO WARRANTY
  56. Bug reports make this a better product!
  57. Further Reference
  58. Other
  59.  
  60. About StdSet...
  61.     
  62. SetHandles, and the routines defined in this package that support that data type, define a convenient and simple way to manage sets of 32 bit integers.  Although not restricted to thirty-two bit integers, SetHandles are particularly useful when used with this data type as they can be used to manage sets of pointers--with this particular generation of personal computer technology the thirty-two bit integer data type coincides with the size of the pointer data type, used to refer to machine locations.
  63.     
  64. Implementation Notes
  65.  
  66. SetHandles are stored as single contiguous blocks of memory.  They are appropriate for storage in resource files, or in data files.
  67.  
  68. These routines can operate on any data type to which the < > >= <= operators apply.  You can redefine the type TSETELT in the file StdSet.h to use a different type.  Tested with char, short, and long.
  69.  
  70. These routines are a convenience, not a workhorse.  They're not for managing huge sets, and some operations may be slow when they are used on huge sets.  If you need to work with massively sized sets, you really should be considering building some tree routines.
  71.  
  72. Do not lock a SetHandle in memory and expect these routines to work.  Always leave SetHandles unlocked.  it's best that you treat the SetHandle data type as a transparent type and use the routines provided herein to access it.
  73.  
  74. If you are using a set handle to store pointers, here's some tips:
  75. - Don't expect any particular ordering.  You have no control of the addresses returned to you by the system. You can count on the fact that each pointer will be a unique element in a set.
  76. - Don't store a SetHandle containing pointers in a file or in a resource and expect those pointers to be valid the next time you start the program and read in the SetHandle.
  77.  
  78. Materials
  79.  
  80. The SetRecord and SetHandle definition is the copyright property of John Montbriand.
  81.     
  82. The routines documented herein are the copyright property of John Montbriand.  They're fun, easy to use, and practical.  I hope all who find them will use them well.
  83.  
  84. Copyright (c) 1996, 1997 by John Montbriand.  All Rights Reserved.
  85. Permission hereby granted for public use.
  86. Distribute freely in areas where the laws of copyright apply.
  87. USE AT YOUR OWN RISK.
  88. DO NOT DISTRIBUTE MODIFIED COPIES.
  89.  
  90.  
  91. Creating and Disposing of SetHandles
  92.  
  93. NewSet
  94.  
  95. SetHandle NewSet(void);
  96.  
  97. NewSet creates a new empty set.  It returns the value NULL if an error occurs.
  98.  
  99. EXAMPLE:  
  100.  
  101. SetHandle theset;
  102.  
  103. theset = NewSet();
  104. if (theset == NULL) { err = memFullErr; goto bail; }
  105. -- theset is now {}
  106.  
  107.  
  108. BuildSet
  109.  
  110. SetHandle BuildSet(long count, TSETELT *data);
  111. BuildSet creates a new set from an unsorted array.   It returns the value NULL if an error occurs.  count indicates the number of elements stored in the array data.  Elements in the array need not be sorted.
  112.  
  113. EXAMPLE:  
  114.  
  115. SetHandle theset;
  116. TSETELT data[] = {22, 99, 12, 7, 10, 88, 77, 96, 78, 23, 22};
  117.  
  118. theset = BuildSet(sizeof(data)/sizeof(TSETELT), data);
  119. if (theset == NULL) { err = memFullErr; goto bail; }
  120. -- theset is now {7,10,12,22,23,77,78,88,96,99}
  121.  
  122.  
  123. DisposeSet
  124.  
  125. void DisposeSet(SetHandle set);
  126.  
  127. DisposeSet reclaims the storage occupied by the set.  Note, if you are storing pointers in the set, be sure to dispose of them before disposing of the set.
  128.  
  129. EXAMPLE:  
  130.  
  131. SetHandle theset;
  132.  
  133. theset = NewSet();
  134. if (theset == NULL) { err = memFullErr; goto bail; }
  135. ....
  136. DisposeSet(theset);
  137.  
  138.  
  139. SetHandle Information Access
  140.  
  141. SetCard
  142.  
  143. long SetCard(SetHandle a);
  144.  
  145. SetCard returns the number of elements in the set a.
  146.  
  147. EXAMPLE:  
  148.  
  149. SetHandle theset;
  150. TSETELT data[] = {22, 99, 12, 7, 10, 88, 77, 96, 78, 23, 22};
  151.  
  152. theset = BuildSet(sizeof(data)/sizeof(TSETELT), data);
  153. if (theset == NULL) { err = memFullErr; goto bail; }
  154. -- theset is now {7,10,12,22,23,77,78,88,96,99}
  155. printf("size = %d\n", SetCard(theset));
  156. -- prints: 'size = 10'
  157.  
  158.  
  159. SetEmpty
  160.  
  161. Boolean SetEmpty(SetHandle a);
  162.  
  163. SetEmpty returns true if a is the empty set.
  164.  
  165. EXAMPLE:  
  166.  
  167. SetHandle theset;
  168.  
  169. theset = NewSet();
  170. if (theset == NULL) { err = memFullErr; goto bail; }
  171. -- theset is now {}
  172. if (SetEmpty(theset)) {
  173.    ....
  174.  
  175.  
  176. SetElement
  177.  
  178. TSETELT SetElement(SetHandle a, long index);
  179.  
  180. SetElement returns the index'th element of the set a.
  181.  
  182. EXAMPLE:  
  183.  
  184. SetHandle theset;
  185. TSETELT data[] = {22, 99, 12, 7, 10, 88, 77, 96, 78, 23, 22};
  186. long i;
  187.  
  188. theset = BuildSet(sizeof(data)/sizeof(TSETELT), data);
  189. if (theset == NULL) { err = memFullErr; goto bail; }
  190. for (i=0; i<SetCard(theset); i++)
  191.     printf("%c%d", ((i>0) ? '.' : ' '), SetElement(theset, i));
  192. -- prints: ' 7.10.12.22.23.77.78.88.96.99'
  193.  
  194.  
  195. SetMember
  196.  
  197. Boolean SetMember(SetHandle a, TSETELT value);
  198.  
  199. SetMember returns true if value is a member of the set a.
  200.  
  201. EXAMPLE:  
  202.  
  203. SetHandle theset;
  204. TSETELT data[] = {22, 99, 12, 7, 10, 88, 77, 96, 78, 23, 22};
  205. long i;
  206.  
  207. theset = BuildSet(sizeof(data)/sizeof(TSETELT), data);
  208. if (theset == NULL) { err = memFullErr; goto bail; }
  209. if (SetMember(theset, 23)) {
  210.     printf("hasatwentythree\n");
  211. }
  212. -- prints: 'hasatwentythree'
  213.  
  214.  
  215. SetEqual
  216.  
  217. Boolean SetEqual(SetHandle a, SetHandle b);
  218.  
  219. SetEqual returns true if a and b contain the same elements.
  220.  
  221. EXAMPLE:  
  222.  
  223. SetHandle theset, otherset;
  224. TSETELT data[] = {22, 99, 12, 7, 10, 88, 77, 96, 78, 23, 22};
  225.  
  226. theset = BuildSet(sizeof(data)/sizeof(TSETELT), data);
  227. if (theset == NULL) { err = memFullErr; goto bail; }
  228. if ((otherset = NewSet()) == NULL) { err = memFullErr; goto bail; }
  229. if (SetEqual(theset, otherset))
  230.    printf("equal\n");
  231. else printf("not equal\n");
  232. -- prints: 'not equal'
  233.  
  234.  
  235. SetSubset
  236.  
  237. Boolean SetSubset(SetHandle a, SetHandle b);
  238.  
  239. SetSubset returns true if the set b is a subset of the set a.
  240.  
  241. EXAMPLE:  
  242.  
  243. SetHandle theset, otherset;
  244. TSETELT data[] = {22, 99, 12, 7, 10, 88, 77, 96, 78, 23, 22};
  245.  
  246. theset = BuildSet(sizeof(data)/sizeof(TSETELT), data);
  247. if (theset == NULL) { err = memFullErr; goto bail; }
  248. if ((otherset = NewSet()) == NULL) { err = memFullErr; goto bail; }
  249. if (SetSubset(theset, otherset))
  250.    printf("otherset is a subset of theset\n");
  251. else printf("that's not a subset of theset\n");
  252. -- prints: 'otherset is a subset of theset'
  253.  
  254.  
  255. Operations on SetHandles
  256.  
  257. ClearSet
  258.  
  259. void ClearSet(SetHandle set);
  260.  
  261. ClearSet re-initializes the set to an empty set.
  262.  
  263. EXAMPLE:  
  264.  
  265. SetHandle theset;
  266. TSETELT data[] = {22, 99, 12, 7, 10, 88, 77, 96, 78, 23, 22};
  267.  
  268. theset = BuildSet(sizeof(data)/sizeof(TSETELT), data);
  269. if (theset == NULL) { err = memFullErr; goto bail; }
  270. -- theset is now {7,10,12,22,23,77,78,88,96,99}
  271. ClearSet(theset);
  272. -- theset is now {}
  273.  
  274.  
  275. SetCopy
  276.  
  277. Boolean SetCopy(SetHandle dst, SetHandle src);
  278.  
  279. SetCopy copies the set in src to dst such that the resulting sets are identical.  it returns true if the operation was successful.  It does not create the set dst, you must call NewSet to create this set before calling SetCopy.
  280.  
  281. EXAMPLE:  
  282.  
  283. SetHandle theset, thecopy;
  284. TSETELT data[] = {22, 99, 12, 7, 10, 88, 77, 96, 78, 23, 22};
  285.  
  286. theset = BuildSet(sizeof(data)/sizeof(TSETELT), data);
  287. if (theset == NULL) { err = memFullErr; goto bail; }
  288. if ((thecopy = NewSet()) == NULL) { err = memFullErr; goto bail; }
  289. -- theset is now {7,10,12,22,23,77,78,88,96,99}
  290. -- thecopy is now {}
  291. if (CopySet(thecopy, theset)) {
  292.     -- thecopy is now {7,10,12,22,23,77,78,88,96,99}
  293. } else {
  294.     -- thecopy is now {}
  295. }
  296.  
  297.  
  298. SetAddElt
  299.  
  300. Boolean SetAddElt(SetHandle a, TSETELT value);
  301.  
  302. SetAddElt adds the element to the set.  It returns true if the element has been successfully added to the set.  note:  Sets do not contain duplicates.
  303.  
  304. EXAMPLE:  
  305.  
  306. SetHandle theset;
  307. TSETELT data[] = {22, 99, 12, 7, 10, 88, 77, 96, 78, 23, 22};
  308.  
  309. theset = BuildSet(sizeof(data)/sizeof(TSETELT), data);
  310. if (theset == NULL) { err = memFullErr; goto bail; }
  311. -- theset is now {7,10,12,22,23,77,78,88,96,99}
  312. if (SetAddElt(theset, 55)) {
  313.     -- theset is now {7,10,12,22,23,55,77,78,88,96,99}
  314. } else {
  315.     -- theset is now {7,10,12,22,23,77,78,88,96,99}
  316. }
  317.  
  318.  
  319. SetRemoveElt
  320.  
  321. void SetRemoveElt(SetHandle a, TSETELT value);
  322.  
  323. SetRemoveElt removes the element with the value 'value' from the set.  If a matching element is not in the set, then the routine does nothing.
  324.  
  325. EXAMPLE:  
  326.  
  327. SetHandle theset;
  328. TSETELT data[] = {22, 99, 12, 7, 10, 88, 77, 96, 78, 23, 22};
  329.  
  330. theset = BuildSet(sizeof(data)/sizeof(TSETELT), data);
  331. if (theset == NULL) { err = memFullErr; goto bail; }
  332. -- theset is now {7,10,12,22,23,77,78,88,96,99}
  333. SetRemoveElt(theset, 88);
  334. -- theset is now {7,10,12,22,23,77,78,96,99}
  335.  
  336.  
  337. SetAnd
  338.  
  339. SetHandle SetAnd(SetHandle a, SetHandle b);
  340.  
  341. SetAnd returns a new SetHandle containing all of the elements common to both the set a and the set b.  Other descriptions of this routine include: 'a and b', or 'set intersection'.  returns a new set.  If an error occurs, NULL is returned.
  342.  
  343. EXAMPLE:  
  344.  
  345. SetHandle a, b, c;
  346. TSETELT adata[] = {1,2,3}, bdata[] = {2,3,4};
  347.  
  348. if ((a = BuildSet(3, adata)) == NULL) { err = memFullErr; goto bail; }
  349. if ((b = BuildSet(3, bdata)) == NULL) { err = memFullErr; goto bail; }
  350. -- a is now {1,2,3}, b is {2,3,4}, c is undefior that subset before calling this routine.
  351.  
  352.  
  353. EXAMPLE:  
  354.  
  355. see PowerSetSize.
  356.  
  357.  
  358. Permutations
  359.  
  360. SetPermute
  361.  
  362. typedef Boolean (*SetPermutation)(TSETELT *elts, long nelts, long param);
  363. OSErr SetPermute(SetHandle a, SetPermutation perm, long param);
  364.  
  365. SetPermute calls the SetPermutation function, perm,  that you define,  once for each permutation of the elements in the set a.  param is defined for your own use.  if the SetPermutation function returns false, SetPermute returns immediately.
  366.  
  367. EXAMPLE:  
  368.  
  369. Boolean MyPrintPermutationFunction(TSETELT *elts, long nelts, long param) {
  370.     long i;
  371.     for (i=0; i<nelts; i++) print(" %d", elts[i]);
  372.     print("\n");
  373. }
  374. ....
  375.  
  376. SetHandle a;
  377. TSETELT adata[] = {1,2,3};
  378.  
  379. if ((a = BuildSet(3, adata)) == NULL) { err = memFullErr; goto bail; }
  380.  
  381. theset = NewSet();
  382. if (theset == NULL) { err = memFullErr; goto bail; }
  383. SetPermute(a, MyPrintPermutationFunction, 0);
  384. -- prints:
  385.  1, 2, 3
  386.  2, 1, 3
  387.  3, 1, 2
  388.  1, 3, 2
  389.  2, 3, 1
  390.  3, 2, 1
  391.  
  392.  
  393. Sets of Pointers, an example 
  394.  
  395. The following c program builds a powerset of whatever command line arguments were provided, storing them as pointers in the set.  it calls printset for each member of the powerset.
  396.  
  397. #include "StdSet.h"
  398. #include <QuickDraw.h>
  399. #include <StdIO.h>
  400.  
  401. QDGlobals qd;
  402.  
  403. static void printset(char* title, SetHandle theset) {
  404.     long i, n;
  405.     printf("%s = {", title);
  406.     n = SetCard(theset);
  407.     for (i=0;i<n;i++)
  408.         printf("%s%s", ((i > 0) ? ", " : ""), SetElement(theset, i));
  409.     printf("}\n");
  410. }
  411.  
  412. long main (long argc, char**argv) {
  413.     long i, n;
  414.     SetHandle myset;
  415.     PowerSet mypset;
  416.     char s[256];
  417.     
  418.     InitGraf(&qd.thePort);
  419.     myset = NewSet();
  420.     for (i=1; i<argc; i++)
  421.         SetAddElt(myset, (TSETELT) (argv[i]));
  422.     
  423.     if ((mypset = GeneratePowerSet(myset)) != NULL) {
  424.         n = PowerSetSize(mypset);
  425.         for (i=0;i<n;i++) {
  426.             sprintf(s, "subset[%d]", i);
  427.             printset(s, PowerSetElt(mypset, i));
  428.         }
  429.         DisposePowerSet(mypset);
  430.     }
  431.  
  432.     return 0;
  433. }
  434.  
  435. Given the command line arguments, "sets" "are" "handy", the program will print the following output:
  436.  
  437. subset[0] = {}
  438. subset[1] = {sets}
  439. subset[2] = {are}
  440. subset[3] = {handy}
  441. subset[4] = {sets, are}
  442. subset[5] = {sets, handy}
  443. subset[6] = {are, handy}
  444. subset[7] = {sets, are, handy}
  445.  
  446.  
  447. A Set of What???
  448.  
  449. - a set of windows open in your app,
  450. - a set of files open in your app,
  451. - a set of volumes mounted on the computer,
  452. - a set of strings,
  453. - a set of dialogs in your app,
  454. - a set of fonts usable in a particular document,
  455. and so on, and so on...
  456.  
  457.  
  458. Files in this package
  459.  
  460. StdSet.c -- source code for the StdSet routines' implementation
  461. StdSet.h -- header file providing interfaces to the StdSet routines
  462. ReadMe  -- this file
  463.  
  464. :Libraries: -- precompiled libraries, ready to link.  
  465. StdSet.o -- 68K version of the StdSet library
  466. StdSet.xcoff -- PowerPC version of the StdSet library
  467.  
  468.  
  469. Copies for sale!
  470.  
  471. These libraries are provided for free and you may use them in any program you make;  however, if you would like to purchase a copy of these libraries and have a legal paper trail establishing your right to use them, then send along a cheque or a money order in the amount of $25.00 for the purchase of one copy.  I'll send you a receipt.
  472.  
  473.  
  474. NO WARRANTY
  475.  
  476. No warranties are made regarding these files.  John Montbriand disclaims all warranties regarding these files, either express or implied, including but not limited to implied warranties of merchantability and fitness for any particular purpose.  These files are provided "AS IS" without any warranty of any kind.  Use them at your own risk.  Copies of these files are not for sale in areas where the law does not allow exclusion of implied warranties.
  477.  
  478.  
  479. Bug reports make this a better product!
  480.  
  481. As in all of my products, I advertise a $10.00 finder's fee for bug reports that lead to corrections.  If you find a problem here, report it!  it could be worth your while....
  482.  
  483.  
  484. Further Reference
  485.  
  486. Inside Macintosh: Memory by Apple Computer, Inc.  Addison-Wesley.
  487. A discussion of memory management, handles, what they are, and  how to use them.
  488.     
  489. The C Programming Language 2nd edition by Brian W. Kernighan and Dennis M. Ritchie.  Prentice Hall.
  490.  
  491.  
  492. Other
  493.  
  494. Have a great day!
  495.  
  496. John Montbriand
  497. Author
  498.  
  499.  
  500.