home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / nihcl-3.0 / lib / LinkedList.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-19  |  8.8 KB  |  405 lines
  1. /* LinkedList.c -- implementation of singly-linked list
  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.     October, 1985
  21.  
  22. Function:
  23.     
  24. LinkedLists are ordered by the sequence in which objects are added and removed
  25. from them.  Object elements are accessible by index.
  26.  
  27. $Log:    LinkedList.c,v $
  28.  * Revision 3.0  90/05/20  00:20:06  kgorlen
  29.  * Release for 1st edition.
  30.  * 
  31. */
  32.  
  33. #include "LinkedList.h"
  34. #include "nihclIO.h"
  35.  
  36. #define    THIS    LinkedList
  37. #define    BASE    SeqCltn
  38. #define BASE_CLASSES BASE::desc()
  39. #define MEMBER_CLASSES
  40. #define VIRTUAL_BASE_CLASSES
  41.  
  42. DEFINE_CLASS(LinkedList,1,"$Header: /afs/alw.nih.gov/unix/sun4_40c/usr/local/src/nihcl-3.0/share/lib/RCS/LinkedList.c,v 3.0 90/05/20 00:20:06 kgorlen Rel $",NULL,NULL);
  43.  
  44. extern const int NIHCL_DBLLNK,NIHCL_CLTNEMPTY,NIHCL_MISSINGLNK,NIHCL_OBNOTFOUND,NIHCL_INDEXRANGE;
  45.  
  46. /*
  47. Derived classes must override these definitions of linkCastdown() when
  48. adding objects to a LinkedList that are multiply derived from class
  49. Link.
  50. */
  51.  
  52. Link& LinkedList::linkCastdown(Object& p) const
  53. {
  54.     return Link::castdown(p);
  55. }
  56.  
  57. LinkedList::LinkedList()
  58. {
  59.     firstLink = lastLink = Link::nilLink;
  60.     count = 0;
  61. }
  62.  
  63. #ifndef BUG_TOOBIG
  64. // yacc stack overflow
  65.  
  66. LinkedList::LinkedList(const LinkedList& l)
  67. {
  68.     firstLink = l.firstLink;
  69.     lastLink = l.lastLink;
  70.     count = l.count;
  71. }
  72.  
  73. #endif
  74.  
  75. bool LinkedList::operator==(const LinkedList& ll) const
  76. {
  77.     if (count != ll.count) return NO;
  78.     else {
  79.         register Link* p = firstLink;
  80.         register Link* q = ll.firstLink;
  81.         while (!p->isListEnd()) {
  82.             if (!(p->isEqual(*q))) return NO;
  83.             p = p->nextLink();
  84.             q = q->nextLink();
  85.         }
  86.     }
  87.     return YES;
  88. }
  89.  
  90. Object* LinkedList::add(Link& ob)
  91. {
  92.     register Link* lnk = &ob;
  93.     if (lnk->nextLink() != NULL) errDblLnk("add",*lnk);
  94.     if (count == 0) firstLink = lnk;
  95.     else lastLink->nextLink(lnk);
  96.     lastLink = lnk;
  97.     lnk->nextLink(Link::nilLink);
  98.     count++;
  99.     return &ob;
  100. }
  101.  
  102. Object* LinkedList::add(Object& ob)
  103. {
  104.     assertArgClass(ob,*Link::desc(),"add");
  105.     return add(Link::castdown(ob));
  106. }
  107.  
  108. Object* LinkedList::addAfter(Link& afterLink, Link& newLink)
  109. {
  110.     if (newLink.nextLink() != NULL) errDblLnk("addAfter",newLink);
  111.     if (afterLink.nextLink() == NULL || count == 0)
  112.         setError(NIHCL_MISSINGLNK,DEFAULT,afterLink.className(),this,className(),
  113.             afterLink.className(),&afterLink,newLink.className(),&newLink);
  114.     newLink.nextLink(afterLink.nextLink());
  115.     afterLink.nextLink(&newLink);
  116.     if (lastLink == &afterLink) lastLink = &newLink;
  117.     count++;
  118.     return &newLink;
  119. }
  120.  
  121. Object* LinkedList::addAfter(Object& afterLink, Object& newLink)
  122. {
  123.     assertArgClass(afterLink,*Link::desc(),"add");
  124.     assertArgClass(newLink,*Link::desc(),"add");
  125.     return addAfter(Link::castdown(afterLink), Link::castdown(newLink));
  126. }
  127.  
  128. Collection& LinkedList::addContentsTo(Collection& cltn) const
  129. {
  130.     register Link* p = firstLink;
  131.     while (!p->isListEnd()) {
  132.         register Link* t = linkCastdown(p->copy());
  133.         cltn.add(*t);
  134.         p = p->nextLink();
  135.     }
  136.     return cltn;
  137. }
  138.  
  139. Object* LinkedList::addFirst(Link& ob)
  140. {
  141.     assertArgClass(ob,*Link::desc(),"addFirst");
  142.     if (count == 0) return add(ob);
  143.     else {
  144.         register Link* lnk = &ob;
  145.         if (lnk->nextLink() != NULL) errDblLnk("addFirst",*lnk);
  146.         lnk->nextLink(firstLink);
  147.         firstLink = lnk;
  148.         count++;
  149.         return &ob;
  150.     }
  151. }
  152.  
  153. Object* LinkedList::addFirst(Object& ob)
  154. {
  155.     assertArgClass(ob,*Link::desc(),"addFirst");
  156.     return addFirst(Link::castdown(ob));
  157. }
  158.  
  159. Object* LinkedList::addLast(Link& ob) { return add(ob); }
  160.  
  161. Object* LinkedList::addLast(Object& ob) { return add(ob); }
  162.  
  163. Object* LinkedList::operator[](int i)
  164. /*
  165. Note that we can't return an Object*& because of MI: a Link* may need
  166. to be adjusted to become an Object*.
  167. */
  168. {
  169.     if ((unsigned)i >= count) indexRangeErr();
  170.     if (i==0) return firstLink;
  171.     else {
  172.         register Link* p = firstLink;
  173.         for (register int j=i-1; j>0; j--) p = p->nextLink();
  174.         return p->next;
  175.     }
  176. }
  177.  
  178. const Object *const LinkedList::operator[](int i) const
  179. {
  180.     if ((unsigned)i >= count) indexRangeErr();
  181.     if (i==0) return firstLink;
  182.     else {
  183.         register Link* p = firstLink;
  184.         for (register int j=i-1; j>0; j--) p = p->nextLink();
  185.         return p->next;
  186.     }
  187. }
  188.  
  189. Object*& LinkedList::at(int)
  190. // Can't implement at() because of MI -- see operator[]().
  191. {
  192.     shouldNotImplement("at");
  193.     return (Object*&)nil;
  194. }
  195.  
  196. const Object *const& LinkedList::at(int) const
  197. // Can't implement at() because of MI -- see operator[]().
  198. {
  199.     shouldNotImplement("at");
  200.     return (Object*&)nil;
  201. }
  202.  
  203. void LinkedList::atAllPut(Object&) { shouldNotImplement("atAllPut"); }
  204.  
  205. void LinkedList::deepenShallowCopy()
  206. {
  207.     BASE::deepenShallowCopy();
  208.     register Link* p = firstLink;
  209.     firstLink = lastLink = Link::nilLink;
  210.     count = 0;
  211.     while (!p->isListEnd()) {
  212.         add(*(p->deepCopy()));
  213.         p = p->nextLink();
  214.     }
  215. }
  216.  
  217. Object* LinkedList::first() const
  218. {
  219.     if (count==0) errEmpty("first");
  220.     else return firstLink;
  221. }
  222.  
  223. unsigned LinkedList::hash() const
  224. {
  225.     register unsigned h = count;
  226.     register Link* p = firstLink;
  227.     while (!p->isListEnd()) {
  228.         h^= p->hash();
  229.         p = p->nextLink();
  230.     }
  231.     return h;
  232. }
  233.  
  234. bool LinkedList::includes(const Object& ob) const
  235. {
  236.     return (indexOf(ob) != -1);
  237. }
  238.  
  239. int LinkedList::indexOf(const Object& ob) const
  240. {
  241.     register int i = 0;
  242.     register Link* p = firstLink;
  243.     while (!p->isListEnd()) {
  244.         if (p->isEqual(ob)) return i;
  245.         p = p->nextLink();
  246.         i++;
  247.     }
  248.     return -1;
  249. }
  250.  
  251. int LinkedList::indexOfSubCollection(const SeqCltn& /*cltn*/, int /*start*/) const
  252. {    shouldNotImplement("indexOfSubCollection"); return 0;    }
  253.  
  254. bool LinkedList::isEmpty() const    { return count==0; }
  255.  
  256. bool LinkedList::isEqual(const Object& a) const
  257. {
  258.     return a.isSpecies(classDesc) && *this==castdown(a);
  259. }
  260.  
  261. const Class* LinkedList::species() const { return &classDesc; }
  262.  
  263. Object* LinkedList::last() const
  264. {
  265.     if (count==0) errEmpty("last");
  266.     else return lastLink;
  267. }
  268.  
  269. Object* LinkedList::doNext(Iterator& pos) const
  270. {
  271.     if (pos.ptr == 0) {
  272.         if (count == 0) return 0;
  273.         else {
  274.             pos.ptr = firstLink;
  275.             pos.index = 1;
  276.             return firstLink;
  277.         }
  278.     }
  279. else    if (pos.ptr == lastLink) return 0;
  280. else        {
  281.         pos.ptr = linkCastdown(pos.ptr)->nextLink();
  282.         pos.index++;
  283.         return pos.ptr;
  284.     }
  285. }
  286.  
  287. unsigned LinkedList::occurrencesOf(const Object& ob) const
  288. {
  289.     register unsigned n=0;
  290.     register Link* p = firstLink;
  291.     while (!p->isListEnd()) {
  292.         if (p->isEqual(ob)) n++;
  293.         p = p->nextLink();
  294.     }
  295.     return n;
  296. }
  297.  
  298. Object* LinkedList::remove(const Link& ob)
  299. {
  300.     if (count==0) errEmpty("remove");
  301.     register Link* lnk = &(Link&)ob;
  302.     if (lnk == firstLink) {
  303.         firstLink = lnk->nextLink();
  304.         if (lnk == lastLink) lastLink = firstLink;
  305.         goto wrapup;
  306.     }
  307.     else {
  308.         register Link* p = firstLink;
  309.         while (!p->isListEnd()) {
  310.             if (lnk == p->nextLink()) {
  311.                 p->nextLink(lnk->nextLink());
  312.                 if (lnk == lastLink) lastLink = p;
  313.                 goto wrapup;
  314.             }
  315.             p = p->nextLink();
  316.         }
  317.         errNotFound("remove",ob);
  318.     }
  319. wrapup:
  320.     lnk->nextLink(NULL);
  321.     count--;
  322.     return lnk;
  323. }
  324.  
  325. Object* LinkedList::remove(const Object& ob)
  326. {
  327.     assertArgClass(ob,*Link::desc(),"remove");
  328.     return remove(Link::castdown(ob));
  329. }
  330.  
  331. void LinkedList::removeAll()
  332. {
  333.     while (count) remove(*firstLink);
  334. }
  335.  
  336. Object* LinkedList::removeFirst()    { return remove(*firstLink); }
  337.  
  338. Object* LinkedList::removeLast()    { return remove(*lastLink); }
  339.     
  340. void LinkedList::replaceFrom(int /*start*/, int /*stop*/, const SeqCltn& /*replacement*/, int /*startAt*/)
  341. {
  342.     shouldNotImplement("replaceFrom");
  343. }
  344.  
  345. void LinkedList::reSize(unsigned /*newSize*/) {}
  346.  
  347. unsigned LinkedList::size() const    { return count; }
  348.     
  349. LinkedList::LinkedList(OIOin& strm)
  350. :
  351. #ifdef MI
  352.     Object(strm),
  353. #endif
  354.     BASE(strm)
  355. {
  356.     firstLink = lastLink = Link::nilLink;
  357.     count = 0;
  358.     unsigned n;
  359.     strm >> n;
  360.     while (n--) add(*Object::readFrom(strm));
  361. }
  362.  
  363. void LinkedList::storer(OIOout& strm) const
  364. {
  365.     BASE::storer(strm);
  366.     strm << size();
  367.     DO(*this,Object,ob) ob->storeOn(strm); OD
  368. }
  369.  
  370. LinkedList::LinkedList(OIOifd& fd)
  371. :
  372. #ifdef MI
  373.     Object(fd),
  374. #endif
  375.     BASE(fd)
  376. {
  377.     firstLink = lastLink = Link::nilLink;
  378.     count = 0;
  379.     unsigned n;
  380.     fd >> n;
  381.     while (n--) add(*Object::readFrom(fd));
  382. }
  383.  
  384. void LinkedList::storer(OIOofd& fd) const
  385. {
  386.     BASE::storer(fd);
  387.     fd << size();
  388.     DO(*this,Object,ob) ob->storeOn(fd); OD
  389. }
  390.  
  391. void LinkedList::errDblLnk(const char* fn, const Link& lnk) const
  392. {
  393.     setError(NIHCL_DBLLNK,DEFAULT,lnk.className(),className(),this,className(),fn,lnk.className(),&lnk);
  394. }
  395.  
  396. void LinkedList::errEmpty(const char* fn) const
  397. {
  398.     setError(NIHCL_CLTNEMPTY,DEFAULT,this,className(),fn);
  399. }
  400.  
  401. void LinkedList::errNotFound(const char* fn, const Object& ob) const
  402. {
  403.     setError(NIHCL_OBNOTFOUND,DEFAULT,this,className(),fn,ob.className(),&ob);
  404. }
  405.