home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / nihcl-3.0 / lib / OrderedCltn.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-19  |  7.7 KB  |  346 lines
  1. /* OrderedCltn.c -- implementation of abstract ordered collections
  2.  
  3.     THIS SOFTWARE FITS THE DESCRIPTION IN THE U.S. COPYRIGHT ACT OF A
  4.     "UNITED STATES GOVERNMENT WORK".  IT WAS WRITTEN AS A PART OF THE
  5.     AUTHOR'S OFFICIAL DUTIES AS A GOVERNMENT EMPLOYEE.  THIS MEANS IT
  6.     CANNOT BE COPYRIGHTED.  THIS SOFTWARE IS FREELY AVAILABLE TO THE
  7.     PUBLIC FOR USE WITHOUT A COPYRIGHT NOTICE, AND THERE ARE NO
  8.     RESTRICTIONS ON ITS USE, NOW OR SUBSEQUENTLY.
  9.  
  10. Author:
  11.     K. E. Gorlen
  12.     Bg. 12A, Rm. 2033
  13.     Computer Systems Laboratory
  14.     Division of Computer Research and Technology
  15.     National Institutes of Health
  16.     Bethesda, Maryland 20892
  17.     Phone: (301) 496-1111
  18.     uucp: uunet!nih-csl!kgorlen
  19.     Internet: kgorlen@alw.nih.gov
  20.     September, 1985
  21.  
  22. Function:
  23.     
  24. OrderedCltns are ordered by the sequence in which objects are added and removed
  25. from them.  Object elements are accessible by index.
  26.  
  27. $Log:    OrderedCltn.c,v $
  28.  * Revision 3.0  90/05/20  00:20:42  kgorlen
  29.  * Release for 1st edition.
  30.  * 
  31. */
  32.  
  33. #include <libc.h>
  34. #include "OrderedCltn.h"
  35. #include "nihclIO.h"
  36.  
  37. #define    THIS    OrderedCltn
  38. #define    BASE    SeqCltn
  39. #define BASE_CLASSES BASE::desc()
  40. #define MEMBER_CLASSES ArrayOb::desc()
  41. #define VIRTUAL_BASE_CLASSES
  42.  
  43. DEFINE_CLASS(OrderedCltn,1,"$Header: /afs/alw.nih.gov/unix/sun4_40c/usr/local/src/nihcl-3.0/share/lib/RCS/OrderedCltn.c,v 3.0 90/05/20 00:20:42 kgorlen Rel $",NULL,NULL);
  44.  
  45. extern const int NIHCL_CLTNEMPTY,NIHCL_OBNOTFOUND;
  46.  
  47. OrderedCltn::OrderedCltn(unsigned size) : contents(size)
  48. {
  49.     endIndex = 0;
  50. }
  51.  
  52. #ifndef BUG_TOOBIG
  53. // yacc stack overflow
  54.  
  55. OrderedCltn::OrderedCltn(const OrderedCltn& c) : contents(c.contents)
  56. {
  57.     endIndex = c.endIndex;
  58. }
  59.  
  60. #endif
  61.  
  62. void OrderedCltn::operator=(const OrderedCltn& c)
  63. {
  64.     endIndex = c.endIndex;
  65.     contents = c.contents;
  66. }
  67.  
  68. bool OrderedCltn::operator==(const OrderedCltn& a) const
  69. {
  70.     if (endIndex != a.endIndex) return NO;
  71.     else {
  72.         register int i = endIndex;
  73.         register const Object** vv = &contents.elem(0);
  74.         register const Object** av = &a.at(0);
  75.         while (i--) if (!((*vv++)->isEqual(**av++))) return NO;
  76.     }
  77.     return YES;
  78. }
  79.  
  80. OrderedCltn OrderedCltn::operator&(const SeqCltn& cltn) const
  81. {
  82.     OrderedCltn c(size()+cltn.size());
  83.     addContentsTo(c);
  84.     cltn.addContentsTo(c);
  85.     return c;
  86. }
  87.  
  88. void OrderedCltn::operator&=(const SeqCltn& cltn)
  89. {
  90.     cltn.addContentsTo(*this);
  91. }
  92.  
  93. Object* OrderedCltn::addAtIndex(int i, Object& ob)
  94. {
  95.     if (endIndex == capacity()) contents.reSize(capacity()+EXPANSION_INCREMENT);
  96.     for (register int j=endIndex; j>i; j--) contents[j] = contents[j-1];
  97.     contents[i] = &ob;
  98.     endIndex++;
  99.     return &ob;
  100. }
  101.  
  102. Object* OrderedCltn::removeAtIndex(int i)
  103. {
  104.     register Object* obrem = contents[i];
  105.     for (register int j=i+1; j<endIndex; j++) contents[j-1] = contents[j];
  106.     contents[--endIndex] = nil;
  107.     return obrem;
  108. }
  109.  
  110. Object* OrderedCltn::add(Object& ob)
  111. {
  112.     addAtIndex(endIndex,ob);
  113.     return &ob;
  114. }
  115.  
  116. Object* OrderedCltn::addAfter(const Object& ob, Object& newob)
  117. {
  118.     register int i = indexOf(ob);
  119.     if (i < 0) errNotFound("addAfter",ob);
  120.     return addAtIndex(i+1,newob);
  121. }
  122.  
  123. Object* OrderedCltn::addAllLast(const OrderedCltn& cltn)
  124. {
  125.     if (endIndex+cltn.size() >= capacity())
  126.         contents.reSize(endIndex+cltn.size()+EXPANSION_INCREMENT);
  127.     for (register int i=0; i<cltn.size(); i++)
  128.         contents[endIndex++] = (Object*)cltn.contents[i];
  129.     return (Object*) &cltn;
  130. }
  131.  
  132. Object* OrderedCltn::addBefore(const Object& ob, Object& newob)
  133. {
  134.     register int i = indexOf(ob);
  135.     if (i < 0) errNotFound("addBefore",ob);
  136.     return addAtIndex(i,newob);
  137. }
  138.  
  139. Collection& OrderedCltn::addContentsTo(Collection& cltn) const
  140. {
  141.     for (register int i=0; i<size(); i++) cltn.add(*(Object*)contents[i]);
  142.     return cltn;
  143. }
  144.  
  145. Object* OrderedCltn::addLast(Object& ob) { return add(ob); }
  146.  
  147. Object* OrderedCltn::after(const Object& ob) const
  148. {
  149.     register int i=indexOf(ob);
  150.     if (i<0) errNotFound("after",ob);
  151.     if (++i == endIndex) return nil;
  152.     return (Object*)contents[i];
  153. }
  154.  
  155. Object*& OrderedCltn::at(int i)                { return (*this)[i]; }
  156.  
  157. const Object *const& OrderedCltn::at(int i) const    { return (*this)[i]; }
  158.  
  159. void OrderedCltn::atAllPut(Object& ob)
  160. {
  161.     for (register int i=0; i<endIndex; i++) contents[i] = &ob;
  162. }
  163.  
  164. Object* OrderedCltn::before(const Object& ob) const
  165. {
  166.     register int i = indexOf(ob);
  167.     if (i < 0) errNotFound("before",ob);
  168.     if (--i < 0) return nil;
  169.     return (Object*)contents[i];
  170. }
  171.  
  172. unsigned OrderedCltn::capacity() const    { return contents.capacity(); }
  173.  
  174. void OrderedCltn::deepenShallowCopy()
  175. {
  176.     BASE::deepenShallowCopy();
  177.     register int i = endIndex;
  178.     register Object** vv = &contents.elem(0);
  179.     while (i--) {
  180.         *vv = (*vv)->deepCopy();
  181.         vv++;
  182.     }
  183. }
  184.  
  185. Object* OrderedCltn::first() const
  186. {
  187.     if (endIndex==0) errEmpty("first");
  188.     else return (Object*)contents.elem(0);
  189. }
  190.  
  191. unsigned OrderedCltn::hash() const
  192. {
  193.     register unsigned h = endIndex;
  194.     register int i = endIndex;
  195.     register const Object** vv = &contents.elem(0);
  196.     while (i--) h^=(*vv++)->hash();
  197.     return h;
  198. }
  199.  
  200. int OrderedCltn::indexOf(const Object& ob) const
  201. {
  202.     for (register int i=0; i<endIndex; i++)
  203.         if (contents[i]->isEqual(ob)) return i;
  204.     return -1;
  205. }
  206.  
  207. int OrderedCltn::indexOfSubCollection(const SeqCltn& cltn, int start) const
  208. {
  209.     int subsize = cltn.size();
  210.     for (register int i=start; i<(endIndex-subsize); i++) {
  211.         for (register int j=0; j<subsize; j++)
  212.             if (!(contents[i+j]->isEqual(*cltn.at(j)))) goto next;
  213.         return i;
  214. next:;    }
  215.     return -1;
  216. }
  217.  
  218. bool OrderedCltn::isEmpty() const { return endIndex==0; }
  219.     
  220. Object* OrderedCltn::last() const
  221. {
  222.     if (endIndex==0) errEmpty("last");
  223.     else return (Object*)contents.elem(endIndex-1);
  224. }
  225.  
  226. unsigned OrderedCltn::occurrencesOf(const Object& ob) const
  227. {
  228.     register unsigned n=0;
  229.     for (register int i=0; i<endIndex; i++)
  230.         if (contents[i]->isEqual(ob)) n++;
  231.     return n;
  232. }
  233.  
  234. Object* OrderedCltn::remove(const Object& ob)
  235. {
  236.     for (register int i=0; i<endIndex; i++) {
  237.         if (contents[i]->isEqual(ob)) {
  238.             return removeAtIndex(i);
  239.         }
  240.     }
  241.     return nil;
  242. }
  243.  
  244. void OrderedCltn::removeAll()
  245. {
  246.     for (register int i=0; i<endIndex; i++) contents[i] = nil;
  247.     endIndex = 0;
  248. }
  249.  
  250. Object* OrderedCltn::removeId(const Object& ob)
  251. {
  252.     for (register int i=0; i<endIndex; i++) {
  253.         if (contents[i] == &ob) return removeAtIndex(i);
  254.     }
  255.     return nil;
  256. }
  257.  
  258. Object* OrderedCltn::removeLast()
  259. {
  260.     if (endIndex==0) errEmpty("removeLast");
  261.     else return removeAtIndex(endIndex-1);
  262. }
  263.  
  264. void OrderedCltn::reSize(unsigned newSize)
  265. {
  266.     if (newSize > size()) contents.reSize(newSize);
  267. }
  268.  
  269. void OrderedCltn::replaceFrom(int start, int stop, const SeqCltn& replacement, int startAt)
  270. {
  271.     register int j=startAt;
  272.     for (register int i=start; i<=stop; i++,j++)
  273.         contents[i] = ((SeqCltn&)replacement).at(j);
  274. }
  275.  
  276. static int compare_ob(const void* a, const void* b)
  277. {
  278.     return (*(const Object**)a)->compare(**(const Object**)b);
  279. }
  280.  
  281. unsigned OrderedCltn::size() const        { return endIndex; }
  282.  
  283. void OrderedCltn::sort()
  284. {
  285.      qsort(&contents.elem(0),size(),sizeof(Object*),compare_ob);
  286. }
  287.  
  288. void OrderedCltn::errEmpty(const char* fn) const
  289. {
  290.     setError(NIHCL_CLTNEMPTY,DEFAULT,this,className(),fn);
  291. }
  292.  
  293. void OrderedCltn::errNotFound(const char* fn, const Object& ob) const
  294. {
  295.     setError(NIHCL_OBNOTFOUND,DEFAULT,this,className(),fn,ob.className(),&ob);
  296. }
  297.  
  298. OrderedCltn Collection::asOrderedCltn() const
  299. {
  300.     OrderedCltn cltn(MAX(size(),DEFAULT_CAPACITY));
  301.     addContentsTo(cltn);
  302.     return cltn;
  303. }
  304.  
  305. static unsigned orderedcltn_capacity;
  306.  
  307. OrderedCltn::OrderedCltn(OIOin& strm)
  308. :
  309. #ifdef MI
  310.     Object(strm),
  311. #endif
  312.     BASE(strm),
  313.     contents((strm >> orderedcltn_capacity, orderedcltn_capacity))
  314. {
  315.     endIndex = 0;
  316.     unsigned n;
  317.     strm >> n;        // read collection capacity 
  318.     while (n--) add(*Object::readFrom(strm));
  319. }
  320.  
  321. OrderedCltn::OrderedCltn(OIOifd& fd)
  322. :
  323. #ifdef MI
  324.     Object(fd),
  325. #endif
  326.     BASE(fd),
  327.     contents((fd >> orderedcltn_capacity, orderedcltn_capacity))
  328. {
  329.     endIndex = 0;
  330.     unsigned n;
  331.     fd >> n;
  332.     while (n--) add(*Object::readFrom(fd));
  333. }
  334.  
  335. void OrderedCltn::storer(OIOofd& fd) const
  336. {
  337.     BASE::storer(fd);
  338.     _storer(fd);
  339. }
  340.  
  341. void OrderedCltn::storer(OIOout& strm) const
  342. {
  343.     BASE::storer(strm);
  344.     _storer(strm);
  345. }
  346.