home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1998 / MacHack 1998.toast / Papers / C++ Exceptions / µShell / Array Classes / (Hidden) / LinkedList.cp < prev    next >
Encoding:
Text File  |  1998-06-01  |  5.7 KB  |  296 lines  |  [TEXT/CWIE]
  1. /*
  2.     File:        LinkedList.cp
  3.  
  4.     Contains:    A linked list
  5.     Written by: Steve Sisak
  6.     Copyright:    © 1995 by Steve Sisak, all rights reserved.
  7.  */
  8.  
  9. #include "LinkedList.h"
  10. #include "ListLink.h"
  11. #include "LinkedListIterator.h"
  12. #include "Exceptions.h"
  13.  
  14.  
  15. #pragma segment Main
  16. //--------------------------------------------------------------------------------
  17. // Initialize all local variables
  18. // This method is in the segment Main so LinkedList's may be in static constructors
  19. LinkedList::LinkedList(ListLink* first, ListLink* last)
  20. {
  21.     if (first == nil)
  22.         first = last;
  23.     if (last == nil)
  24.         last = first;
  25.  
  26.     long        count    = 0;
  27.     ListLink*    link    = first;
  28.  
  29.     while (link != nil)    // Count the number of links passed in
  30.     {
  31.         link->SetLinkedList(this);
  32.  
  33.         count += 1;
  34.  
  35.         ListLink* next = link->GetNextLink();
  36.     
  37.         if (next == nil)
  38.         {
  39.             if (last == nil)
  40.             {
  41.                 last = link;
  42.             }
  43.             else if (qDebug && last != link)
  44.             {
  45.                 Debugger();
  46.             }
  47.         }
  48.         
  49.         link = next;
  50.     }
  51.  
  52.     fFirstLink        = first;
  53.     fLastLink        = last;
  54.     fIteratorList    = nil;
  55.     fElementCount    = count;
  56. }
  57.  
  58.  
  59. #pragma segment AppMain
  60. //--------------------------------------------------------------------------------
  61. LinkedList::~LinkedList()
  62. {
  63.     RemoveAllLinks();
  64. }
  65.  
  66.  
  67. #pragma segment AppMain
  68. //--------------------------------------------------------------------------------
  69. ListLink* LinkedList::GetNthLink(long index)
  70. {
  71.     LinkedListIterator iter(*this);
  72.  
  73.     if (index > 0)
  74.     {
  75.         if (index <= fElementCount)        // Don't waste time
  76.         {
  77.             for (ListLink* link = iter.FirstLink(); link; link = iter.NextLink())
  78.             {
  79.                 if (--index <= 0)
  80.                 {
  81.                     return link;
  82.                 }    
  83.             }
  84.         }
  85.     }
  86.     else if (index < 0)                // Negative is relative to last link
  87.     {
  88.         if (fElementCount + index >= 0)
  89.         {
  90.             for (ListLink* link = iter.LastLink(); link; link = iter.PrevLink())
  91.             {
  92.                 if (++index >= 0)
  93.                 {
  94.                     return link;
  95.                 }    
  96.             }
  97.         }
  98.     }
  99.     
  100.     return nil;
  101. }
  102.  
  103.  
  104. #pragma segment Main
  105. //--------------------------------------------------------------------------------
  106. // This method is in the segment Main so LinkedList's may be in static constructors
  107. void LinkedList::AppendLink(ListLink& link)
  108. {
  109.     InsertLink(link, fLastLink, nil);
  110. }
  111.  
  112.  
  113. #pragma segment Main
  114. //--------------------------------------------------------------------------------
  115. // This method is in the segment Main so LinkedList's may be in static constructors
  116. void LinkedList::PrependLink(ListLink& link)
  117. {
  118.     InsertLink(link, nil, fLastLink);
  119. }
  120.  
  121.  
  122. #pragma segment Main
  123. //--------------------------------------------------------------------------------
  124. // This method is in the segment Main so LinkedList's may be in static constructors
  125. void LinkedList::InsertBefore(ListLink& link, ListLink& before)
  126. {
  127.     InsertLink(link, before.GetPrevLink(), &before);
  128. }
  129.  
  130.  
  131. #pragma segment Main
  132. //--------------------------------------------------------------------------------
  133. // This method is in the segment Main so LinkedList's may be in static constructors
  134. void LinkedList::InsertAfter(ListLink& link, ListLink& after)
  135. {
  136.     InsertLink(link, &after, after.GetNextLink());
  137. }
  138.  
  139.  
  140. #pragma segment AppMain
  141. //--------------------------------------------------------------------------------
  142. ListLink* LinkedList::RemoveFirstLink()
  143. {
  144.     ListLink* link = fFirstLink;
  145.     
  146.     if (link)
  147.     {
  148.         RemoveLink(*link);
  149.     }
  150.     
  151.     return link;
  152. }
  153.  
  154.  
  155. //--------------------------------------------------------------------------------
  156. ListLink* LinkedList::RemoveLastLink()
  157. {
  158.     ListLink* link = fLastLink;
  159.     
  160.     if (link)
  161.     {
  162.         RemoveLink(*link);
  163.     }
  164.     
  165.     return link;
  166. }
  167.  
  168.  
  169. //--------------------------------------------------------------------------------
  170. void LinkedList::RemoveAllLinks(void)
  171. {
  172.     if (fIteratorList)
  173.         fIteratorList->RemovingAllLinks();
  174.     
  175.     ListLink* link = fFirstLink;
  176.  
  177.     fFirstLink        = nil;
  178.     fLastLink        = nil;
  179.  
  180.     while ( link != nil )
  181.     {
  182.         ListLink *next = link->GetNextLink();
  183.  
  184. #if qDebug
  185.         if (next)
  186.             Assert(next->GetPrevLink() == link);
  187. #endif        
  188.         link->SetPrevLink(nil);
  189.         link->SetNextLink(nil);
  190.             
  191.         link = next;
  192.     }
  193. }
  194.  
  195.  
  196. //--------------------------------------------------------------------------------
  197. void LinkedList::RemoveLink(ListLink& link)
  198. {
  199.     ListLink* next = link.GetNextLink();
  200.     ListLink* prev = link.GetPrevLink();
  201.     
  202. #if qDebug // Perform consistancy checks
  203.     if (next)
  204.     {
  205.         Assert(next->GetPrevLink() == &link);
  206.     }
  207.     else
  208.     {
  209.         Assert(fLastLink = &link);
  210.     }
  211.  
  212.     if (prev)
  213.     {
  214.         Assert(prev->GetNextLink() == &link);
  215.     }
  216.     else
  217.     {
  218.         Assert(fFirstLink = &link);
  219.     }
  220. #endif
  221.     
  222.     if (fIteratorList)
  223.         fIteratorList->RemovingLink(link);
  224.  
  225.     // Get the link out of the list
  226.     
  227.     if (next)
  228.         next->SetPrevLink(prev);
  229.     else
  230.         fLastLink = prev;
  231.  
  232.     if (prev)
  233.         prev->SetNextLink(next);
  234.     else
  235.         fFirstLink = next;
  236.  
  237.     fElementCount--;
  238.  
  239.     link.SetPrevLink(nil);
  240.     link.SetNextLink(nil);
  241. }
  242.  
  243. void LinkedList::LinkRemoved(ListLink& /*link*/)
  244. {
  245.     fElementCount--;
  246. }
  247.  
  248. void LinkedList::LinkInserted(ListLink& link)
  249. {
  250.     fElementCount++;
  251.  
  252.     if (fIteratorList)
  253.     {
  254.         fIteratorList->LinkInserted(link);
  255.     }
  256. }
  257.  
  258. //--------------------------------------------------------------------------------
  259. // InsertLink - insert a link in the list
  260. // This method is in the segment Main so LinkedList's may be in static constructors
  261. //--------------------------------------------------------------------------------
  262. #pragma segment Main
  263.  
  264. void LinkedList::InsertLink(
  265.     ListLink& link,        // the link we're inserting
  266.     ListLink* after,    // the link we're inserting after
  267.     ListLink* before)    // the link we're inserting before
  268. {
  269. #if qDebug // Perform consistancy checks
  270.  
  271.     Assert(link.GetPrevLink() == nil);
  272.     Assert(link.GetNextLink() == nil);
  273.  
  274.     if (!before)        // end of list, or empty
  275.     {
  276.         Assert(fLastLink == after);
  277.     }
  278.     
  279.     if (!after)            // Beginning of list, or empty
  280.     {
  281.         Assert(fFirstLink == before);
  282.     }
  283.     else if (before)    // Middle of list
  284.     {
  285.         Assert(after == before->GetPrevLink());
  286.         Assert(after->GetNextLink() == before);
  287.     }
  288.     
  289. #endif
  290.  
  291.     link.Link(after, before, this);
  292. }
  293.  
  294. #pragma segment AppMain
  295.  
  296.