home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / opendc12.zip / od124os2.exe / od12osr1.exe / src / LinkList.cpp < prev    next >
C/C++ Source or Header  |  1997-03-21  |  19KB  |  709 lines
  1. //====START_GENERATED_PROLOG======================================
  2. //
  3. //
  4. //   COMPONENT_NAME: odutils
  5. //
  6. //   CLASSES: none
  7. //
  8. //   ORIGINS: 82,27
  9. //
  10. //
  11. //   (C) COPYRIGHT International Business Machines Corp. 1995,1996
  12. //   All Rights Reserved
  13. //   Licensed Materials - Property of IBM
  14. //   US Government Users Restricted Rights - Use, duplication or
  15. //   disclosure restricted by GSA ADP Schedule Contract with IBM Corp.
  16. //       
  17. //   IBM DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  18. //   ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  19. //   PURPOSE. IN NO EVENT SHALL IBM BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  20. //   CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
  21. //   USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
  22. //   OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
  23. //   OR PERFORMANCE OF THIS SOFTWARE.
  24. //
  25. //====END_GENERATED_PROLOG========================================
  26. //
  27. // @(#) 1.5 com/src/utils/LinkList.cpp, odutils, od96os2, odos29712d 7/15/96 17:58:27 [ 3/21/97 17:20:53 ]
  28. /*
  29.     File:        LinkList.cpp
  30.  
  31.     Contains:    Primitive linked list class
  32.  
  33.     Owned by:    Richard Rodseth, Jens Alfke
  34.  
  35.     Copyright:    ⌐ 1993 - 1995 by Apple Computer, Inc., all rights reserved.
  36.  
  37. */
  38.  
  39. #ifndef _LINKLIST_
  40. #include "LinkList.h"
  41. #endif
  42.  
  43. #ifndef _ODEXCEPT_
  44. #include "ODExcept.h"
  45. #endif
  46.  
  47. #ifndef __ERRORS__
  48. #include <Errors.h>
  49. #endif
  50.  
  51. #ifndef _ODDEBUG_
  52. #include "ODDebug.h"
  53. #endif
  54.  
  55. #ifndef _UTILERRS_
  56. #include "UtilErrs.h"
  57. #endif
  58.  
  59. #pragma segment ODLinkedList
  60.  
  61. //==============================================================================
  62. // Constants
  63. //==============================================================================
  64.  
  65. //==============================================================================
  66. // Scalar Types
  67. //==============================================================================
  68.  
  69. //==============================================================================
  70. // Local Classes
  71. //==============================================================================
  72.  
  73. //==============================================================================
  74. // Global Variables
  75. //==============================================================================
  76.  
  77. //==============================================================================
  78. // Function Prototype
  79. //==============================================================================
  80.  
  81.  
  82. //==============================================================================
  83. // Link
  84. //==============================================================================
  85.  
  86.  
  87.  
  88. // Many of the simple link methods are inlines; see List.h for implementations.
  89.  
  90.  
  91. //------------------------------------------------------------------------------
  92. // Link::Link
  93. //
  94. // Constructor for Link
  95. //------------------------------------------------------------------------------
  96.  
  97. Link::Link()                            
  98. { 
  99.     fNext = kODNULL; 
  100.     fPrevious = kODNULL;
  101. }
  102.  
  103. //------------------------------------------------------------------------------
  104. // Link::Link
  105. //
  106. // Constructor for Link
  107. //------------------------------------------------------------------------------
  108.  
  109. Link::Link(Link* next, Link* previous)                            
  110. { 
  111.     fNext = next; 
  112.     fPrevious = previous;
  113. }
  114.  
  115. //------------------------------------------------------------------------------
  116. // Link::Link
  117. //
  118. // Copy constructor for Link
  119. //------------------------------------------------------------------------------
  120.  
  121. Link::Link( const Link &link )                            
  122. { 
  123.     fNext = link.fNext; 
  124.     fPrevious = link.fPrevious;
  125. }
  126.  
  127. //------------------------------------------------------------------------------
  128. // Link::Link
  129. //
  130. // Destructor for Link
  131. //------------------------------------------------------------------------------
  132.  
  133. Link::~Link()                                            
  134. {
  135. }
  136.  
  137. //------------------------------------------------------------------------------
  138. // Link::Remove
  139. //
  140. // Remove a link from its list (if any). DO NOT call this directly if there are
  141. // any iterators active on the list; use LinkedList::Remove instead.
  142. //------------------------------------------------------------------------------
  143.  
  144. void    Link::Remove( )
  145. {
  146.     if( fPrevious )
  147.         fPrevious->SetNext(fNext);
  148.     if( fNext )
  149.         fNext->SetPrevious(fPrevious);
  150.     fNext = kODNULL;
  151.     fPrevious = kODNULL;
  152. }
  153.  
  154. //------------------------------------------------------------------------------
  155. // Link::AddBefore
  156. //
  157. // Add a link to a list before another link. It must not already be on any list.
  158. // DO NOT call this directly if there are any iterators active on the list;
  159. // use LinkedList::Remove instead.
  160. //------------------------------------------------------------------------------
  161.  
  162. void    Link::AddBefore( Link *link )
  163. {
  164.     ASSERT(link!=kODNULL,paramErr);
  165.     WASSERT(fNext==kODNULL);
  166.     WASSERT(fPrevious==kODNULL);
  167.     fNext = link;
  168.     fPrevious = link->GetPrevious();
  169.     fPrevious->SetNext(this);
  170.     fNext->SetPrevious(this);
  171. }
  172.  
  173. //------------------------------------------------------------------------------
  174. // Link::AddAfter
  175. //
  176. // Add a link to a list after another link. It must not already be on any list.
  177. // DO NOT call this directly if there are any iterators active on the list;
  178. // use LinkedList::Remove instead.
  179. //------------------------------------------------------------------------------
  180.  
  181. void    Link::AddAfter( Link *link )
  182. {
  183.     ASSERT(link!=kODNULL,paramErr);
  184.     WASSERT(fNext==kODNULL);
  185.     WASSERT(fPrevious==kODNULL);
  186.     fPrevious = link;
  187.     fNext = link->GetNext();
  188.     fPrevious->SetNext(this);
  189.     fNext->SetPrevious(this);
  190. }
  191.  
  192. //======================================================================================
  193. // Class LinkedList
  194. //======================================================================================
  195.  
  196. //------------------------------------------------------------------------------
  197. // LinkedList::LinkedList
  198. //
  199. // Constructor for LinkedList
  200. //------------------------------------------------------------------------------
  201.  
  202. LinkedList::LinkedList()
  203.     :fSentinel(&fSentinel,&fSentinel),
  204.      fSeed(0)
  205. {
  206. }
  207.  
  208. //------------------------------------------------------------------------------
  209. // LinkedList::~LinkedList
  210. //
  211. // Destructor for LinkedList
  212. //------------------------------------------------------------------------------
  213.  
  214. LinkedList::~LinkedList()
  215. {
  216.     // The list does NOT delete all its links!
  217. }
  218.  
  219. //------------------------------------------------------------------------------
  220. // LinkedList::IsEmpty
  221. //
  222. // Description
  223. //------------------------------------------------------------------------------
  224.  
  225. ODBoolean LinkedList::IsEmpty() const
  226. {
  227.     return this->IsSentinel( fSentinel.GetNext() );
  228. }
  229.  
  230. //------------------------------------------------------------------------------
  231. // LinkedList::Count
  232. //
  233. // Description
  234. //------------------------------------------------------------------------------
  235.  
  236. ODULong LinkedList::Count() const
  237. {
  238.     Link* l = fSentinel.GetNext();
  239.     ODULong count = 0;
  240.     while (this->NotSentinel(l))
  241.     {
  242.         count++;
  243.         l = l->GetNext();
  244.         ASSERT(l!=kODNULL,kODErrAssertionFailed);
  245.     }
  246.     return count;
  247. }
  248.  
  249. //------------------------------------------------------------------------------
  250. // LinkedList::Includes
  251. //
  252. // Does the list include a particular link?
  253. //------------------------------------------------------------------------------
  254.  
  255. ODBoolean LinkedList::Includes( const Link *link ) const
  256. {
  257.     Link* l = fSentinel.GetNext();
  258.     while (this->NotSentinel(l))
  259.     {
  260.         if( l == link )
  261.             return kODTrue;
  262.         else
  263.             l = l->GetNext();
  264.     }
  265.     return kODFalse;
  266. }
  267.  
  268. //------------------------------------------------------------------------------
  269. // LinkedList::DeleteAllLinks
  270. //
  271. // Description
  272. //------------------------------------------------------------------------------
  273.  
  274. void    LinkedList::DeleteAllLinks()
  275. {
  276.  
  277.     Link* l = fSentinel.GetNext();
  278.     Link* n = l;
  279.     while (this->NotSentinel(n))
  280.     {
  281.         n = l->GetNext();
  282.         delete l;    
  283.         l = n;
  284.     }
  285.     fSentinel.SetNext(&fSentinel);
  286.     fSentinel.SetPrevious(&fSentinel);
  287.     fSeed++;
  288. }
  289.  
  290. //------------------------------------------------------------------------------
  291. // LinkedList::RemoveAll
  292. //
  293. // Description
  294. //------------------------------------------------------------------------------
  295.  
  296. void    LinkedList::RemoveAll()
  297. {
  298.  
  299.     Link* l = fSentinel.GetNext();
  300.     Link* n = l;
  301.     while (this->NotSentinel(l))
  302.     {
  303.         n = l->GetNext();
  304.         l->SetNext(kODNULL);
  305.         l->SetPrevious(kODNULL);
  306.         l = n;
  307.     }
  308.     fSentinel.SetNext(&fSentinel);
  309.     fSentinel.SetPrevious(&fSentinel);
  310. }
  311.  
  312. //------------------------------------------------------------------------------
  313. // LinkedList::Remove
  314. //
  315. // Description
  316. //------------------------------------------------------------------------------
  317.  
  318. void    LinkedList::Remove(Link& aLink)
  319. {
  320.     fSeed++;
  321.     aLink.Remove();
  322. }
  323.  
  324. //------------------------------------------------------------------------------
  325. // LinkedList::RemoveFirst
  326. //
  327. // Description
  328. //------------------------------------------------------------------------------
  329.  
  330. Link* LinkedList::RemoveFirst()
  331. {
  332.     Link* old = fSentinel.GetNext();
  333.     if (this->NotSentinel(old))
  334.     {
  335.         fSeed++;
  336.         old->Remove();
  337.         return old;
  338.     }
  339.     else
  340.     {
  341.         return kODNULL;
  342.     }
  343. }
  344.  
  345. //------------------------------------------------------------------------------
  346. // LinkedList::RemoveLast
  347. //
  348. // Description
  349. //------------------------------------------------------------------------------
  350.  
  351. Link* LinkedList::RemoveLast()
  352. {
  353.     Link* old = fSentinel.GetPrevious();
  354.     if (this->NotSentinel(old))
  355.     {
  356.         fSeed++;
  357.         old->Remove();
  358.         return old;
  359.     }
  360.     else
  361.     {
  362.         return kODNULL;
  363.     }
  364. }
  365.  
  366. //------------------------------------------------------------------------------
  367. // LinkedList::AddFirst
  368. //
  369. // Description
  370. //------------------------------------------------------------------------------
  371.  
  372. void    LinkedList::AddFirst(Link* link)
  373. {
  374.     link->AddAfter(this->GetSentinel());
  375.     fSeed++;
  376. }
  377.  
  378. //------------------------------------------------------------------------------
  379. // LinkedList::AddLast( Link )
  380. //
  381. // Description
  382. //------------------------------------------------------------------------------
  383.  
  384. void    LinkedList::AddLast(Link* link)
  385. {
  386.     link->AddBefore(this->GetSentinel());
  387.     fSeed++;
  388. }
  389.  
  390. //------------------------------------------------------------------------------
  391. // LinkedList::AddLast( LinkedList )
  392. //
  393. // Append contents of another list to my end. (Other list becomes empty.)
  394. //------------------------------------------------------------------------------
  395.  
  396. void    LinkedList::AddLast( LinkedList &list )
  397. {
  398.     if( !list.IsEmpty() ) {
  399.         Link *myLast = fSentinel.GetPrevious();
  400.         Link *itsFirst = list.First();
  401.         myLast->SetNext(itsFirst);
  402.         itsFirst->SetPrevious(myLast);
  403.         
  404.         Link *itsLast = list.Last();
  405.         itsLast->SetNext(this->GetSentinel());
  406.         fSentinel.SetPrevious(itsLast);
  407.         
  408.         list.fSentinel.SetNext(this->GetSentinel());
  409.         list.fSentinel.SetPrevious(this->GetSentinel());
  410.  
  411.         fSeed++;
  412.         list.fSeed++;
  413.     }
  414. }
  415.  
  416. //------------------------------------------------------------------------------
  417. // LinkedList::AddLastUnique( LinkedList )
  418. //
  419. // Append contents of another list (w/o duplication) to my end.
  420. //------------------------------------------------------------------------------
  421.  
  422. void    LinkedList::AddLastUnique( LinkedList &list )
  423. {
  424.     for( Link *link = fSentinel.GetNext(); this->NotSentinel(link); link=link->GetNext() )
  425.         if( list.Includes(link) )
  426.             list.Remove(*link);
  427.     this->AddLast(list);
  428. }
  429.  
  430. //------------------------------------------------------------------------------
  431. // LinkedList::AddBefore
  432. //
  433. // Description
  434. //------------------------------------------------------------------------------
  435.  
  436. void LinkedList::AddBefore(Link& existing, Link* link)
  437. {
  438.     link->AddBefore(&existing);
  439.     fSeed++;
  440. }
  441.  
  442. //------------------------------------------------------------------------------
  443. // LinkedList::AddAfter
  444. //
  445. // Description
  446. //------------------------------------------------------------------------------
  447.  
  448. void LinkedList::AddAfter(Link& existing, Link* link)
  449. {
  450.     link->AddAfter(&existing);
  451.     fSeed++;
  452. }
  453.  
  454. //------------------------------------------------------------------------------
  455. // LinkedList::After
  456. //
  457. // Description
  458. //------------------------------------------------------------------------------
  459.  
  460. Link* LinkedList::After(const Link& link) const
  461. {
  462.     Link *next = link.GetNext();
  463.     if( this->IsSentinel(next) )
  464.         return kODNULL;
  465.     else
  466.         return next;
  467. }
  468.  
  469. //------------------------------------------------------------------------------
  470. // LinkedList::Before
  471. //
  472. // Description
  473. //------------------------------------------------------------------------------
  474.  
  475. Link* LinkedList::Before(const Link& link) const
  476. {
  477.     Link *prev = link.GetPrevious();
  478.     if( this->IsSentinel(prev) )
  479.         return kODNULL;
  480.     else
  481.         return prev;
  482. }
  483.  
  484. //------------------------------------------------------------------------------
  485. // LinkedList::First
  486. //
  487. // Description
  488. //------------------------------------------------------------------------------
  489.  
  490. Link*    LinkedList::First()  const
  491. {
  492.     return this->NotSentinel(fSentinel.GetNext()) ? fSentinel.GetNext() : (Link*) kODNULL;
  493. }
  494.  
  495. //------------------------------------------------------------------------------
  496. // LinkedList::Last
  497. //
  498. // Description
  499. //------------------------------------------------------------------------------
  500.  
  501. Link* LinkedList::Last() const
  502. {
  503.     return this->NotSentinel(fSentinel.GetPrevious()) ? fSentinel.GetPrevious() : (Link*) kODNULL;
  504. }
  505.  
  506.  
  507. //======================================================================================
  508. // Class LinkedListIterator
  509. //======================================================================================
  510.  
  511. //------------------------------------------------------------------------------
  512. // LinkedListIterator::LinkedListIterator
  513. //
  514. // Constructor for LinkedListIterator
  515. //------------------------------------------------------------------------------
  516.  
  517. LinkedListIterator::LinkedListIterator(LinkedList* list)
  518. {
  519.     fList = list;
  520.     fCurrent = kODNULL;
  521.     fNext = kODNULL;
  522.     fPrevious = kODNULL;
  523.     fSentinel = &list->fSentinel;
  524.     fSeed = fList->fSeed;    
  525. }
  526.  
  527. //------------------------------------------------------------------------------
  528. // LinkedListIterator::~LinkedListIterator
  529. //
  530. // Destructor for LinkedListIterator
  531. //------------------------------------------------------------------------------
  532.  
  533. LinkedListIterator::~LinkedListIterator()
  534. {
  535. }
  536.  
  537. //------------------------------------------------------------------------------
  538. // LinkedListIterator::First
  539. //
  540. // Description
  541. //------------------------------------------------------------------------------
  542.  
  543. Link* LinkedListIterator::First()
  544. {
  545.     if (fList == kODNULL)
  546.         return kODNULL;
  547.     
  548. #ifdef _PLATFORM_MACINTOSH_    
  549.     if (fSeed != fList->fSeed)
  550.         THROW(kODErrIteratorOutOfSync);
  551. #else
  552.     // re-initialize for a new run
  553.     fNext = kODNULL;
  554.     fPrevious = kODNULL;
  555.     fSentinel = &fList->fSentinel;
  556.     fSeed = fList->fSeed;
  557. #endif    
  558.         
  559.     fCurrent = fList->First();
  560.     if (fCurrent == fSentinel)
  561.         fCurrent = kODNULL;
  562.     return fCurrent;
  563. }
  564.  
  565. //------------------------------------------------------------------------------
  566. // LinkedListIterator::Next
  567. //
  568. // Description
  569. //------------------------------------------------------------------------------
  570.  
  571. Link* LinkedListIterator::Next()
  572. {
  573.     if (fList == kODNULL)
  574.         return kODNULL;
  575.  
  576.     if (fSeed != fList->fSeed)
  577.         THROW(kODErrIteratorOutOfSync);
  578.  
  579.     if (fCurrent == kODNULL)
  580.     {
  581.         if ((fNext == kODNULL) && (fPrevious == kODNULL))    // Just starting out
  582.         {
  583.             return this->First();
  584.         }
  585.         else    // Just deleted
  586.         {
  587.             fCurrent = fNext;
  588.             fPrevious = kODNULL;
  589.             fNext = kODNULL;
  590.         }
  591.     }
  592.     else
  593.         fCurrent = fCurrent->GetNext();
  594.     
  595.     if (fCurrent == fSentinel)
  596.         fCurrent = kODNULL;
  597.     return fCurrent;
  598. }
  599.  
  600. //------------------------------------------------------------------------------
  601. // LinkedListIterator::Last
  602. //
  603. // Description
  604. //------------------------------------------------------------------------------
  605.  
  606. Link* LinkedListIterator::Last()
  607. {
  608.     if (fList == kODNULL)
  609.         return kODNULL;
  610.  
  611. #ifdef _PLATFORM_MACINTOSH_    
  612.     if (fSeed != fList->fSeed)
  613.         THROW(kODErrIteratorOutOfSync);
  614. #else
  615.     // re-initialize for a new run
  616.     fNext = kODNULL;
  617.     fPrevious = kODNULL;
  618.     fSentinel = &fList->fSentinel;
  619.     fSeed = fList->fSeed;
  620. #endif    
  621.  
  622.     fCurrent = fList->Last();
  623.     if (fCurrent == fSentinel)
  624.         fCurrent = kODNULL;
  625.     return fCurrent;
  626. }
  627.  
  628. //------------------------------------------------------------------------------
  629. // LinkedListIterator::Previous
  630. //
  631. // Description
  632. //------------------------------------------------------------------------------
  633.  
  634. Link* LinkedListIterator::Previous()
  635. {
  636.     if (fList == kODNULL)
  637.         return kODNULL;
  638.  
  639.     if (fSeed != fList->fSeed)
  640.         THROW(kODErrIteratorOutOfSync);
  641.  
  642.     if (fCurrent == kODNULL)
  643.     {
  644.         if ((fNext == kODNULL) && (fPrevious == kODNULL))    // Just starting out
  645.         {
  646.             return this->Last();
  647.         }
  648.         else    // Just deleted
  649.         {
  650.             fCurrent = fPrevious;
  651.             fPrevious = kODNULL;
  652.             fNext = kODNULL;
  653.         }
  654.     }
  655.     else
  656.         fCurrent = fCurrent->GetPrevious();
  657.  
  658.     if (fCurrent == fSentinel)
  659.         fCurrent = kODNULL;
  660.     return fCurrent;
  661. }
  662.  
  663. //------------------------------------------------------------------------------
  664. // LinkedListIterator::Current
  665. //
  666. // Description
  667. //------------------------------------------------------------------------------
  668.  
  669. Link* LinkedListIterator::Current()
  670. {
  671.     return fCurrent;
  672. }
  673.  
  674. //------------------------------------------------------------------------------
  675. // LinkedListIterator::IsNotComplete
  676. //
  677. // Description
  678. //------------------------------------------------------------------------------
  679.  
  680. ODBoolean LinkedListIterator::IsNotComplete()
  681. {
  682.     return (fCurrent != kODNULL);
  683. }
  684.  
  685. //------------------------------------------------------------------------------
  686. // LinkedListIterator::RemoveCurrent
  687. //
  688. // Description
  689. //------------------------------------------------------------------------------
  690.  
  691. void  LinkedListIterator::RemoveCurrent()
  692. {
  693.     if (fList == kODNULL)
  694.         return;
  695.         
  696.     if (fSeed != fList->fSeed)
  697.         THROW(kODErrIteratorOutOfSync);
  698.          
  699.     if (fCurrent != kODNULL)
  700.     {
  701.         fNext = fCurrent->GetNext();
  702.         fPrevious = fCurrent->GetPrevious();
  703.             
  704.         fList->Remove(*fCurrent);
  705.         fCurrent = kODNULL;
  706.         fSeed = fList->fSeed;
  707.     }
  708. }
  709.