home *** CD-ROM | disk | FTP | other *** search
/ ftp.ee.pdx.edu / 2014.02.ftp.ee.pdx.edu.tar / ftp.ee.pdx.edu / pub / users / harry / Blitz / OSProject / p3 / List.c < prev    next >
Text File  |  2007-09-19  |  4KB  |  140 lines
  1. code List
  2.  
  3.   -- Harry Porter  --  December 4, 2003
  4.                    --  December 11, 2003  -- Modified for Listables
  5.  
  6.   behavior List
  7.  
  8.     method AddToFront (p: ptr to T)
  9.       --
  10.       -- This method adds an item to the front of the list.  This is the
  11.       -- end from which the "Remove" method will retrieve elements.
  12.       --
  13.       -- NOTE: This method assumes the object is not already on any lists.
  14.       --
  15.         if self.IsEmpty ()
  16.           first = p
  17.           last = p
  18.         else
  19.           p.next = first
  20.           first = p
  21.         endIf
  22.       endMethod
  23.  
  24.     method AddToEnd (p: ptr to T)
  25.       --
  26.       -- This method adds an item to the tail of the list.  Using "AddToEnd"
  27.       -- and "Remove" will achieve a FIFO queue.
  28.       --
  29.       -- NOTE: This method assumes the object is not already on any lists.
  30.       --
  31.         if self.IsEmpty ()
  32.           first = p
  33.           last = p
  34.         else
  35.           last.next = p
  36.           last = p
  37.         endIf
  38.       endMethod
  39.  
  40.     method Remove () returns ptr to T
  41.       --
  42.       -- This method removes the item at the front of the list and
  43.       -- returns a ptr to it.  If the list is empty, it returns null.
  44.       --
  45.         var item: ptr to T = first
  46.         if first == null
  47.           return null
  48.         elseIf first == last
  49.           first = null
  50.           last = null
  51.         else
  52.           first = first.next asPtrTo T
  53.         endIf
  54.         item.next = null
  55.         return item
  56.       endMethod
  57.  
  58.     method IsEmpty () returns bool
  59.       --
  60.       -- Return true iff the list is empty.
  61.       --
  62.         if first
  63.           return false
  64.         else
  65.           return true
  66.         endIf
  67.       endMethod
  68.  
  69.     method ApplyToEach (f: ptr to function (ptr to T))
  70.       --
  71.       -- This method is passed a function which can be applied to a
  72.       -- list element.  This method applies this function (invokes the
  73.       -- function) on every element in the list, in order.
  74.       --
  75.         var p: ptr to T
  76.         for (p = first; p; p = p.next asPtrTo T)
  77.           f (p)
  78.         endFor
  79.       endMethod
  80.  
  81.     method SortedInsert (p: ptr to T, k: int)
  82.       --
  83.       -- This method assumes that the list is ordered by key value.
  84.       -- It inserts the element "p" into the proper place, using
  85.       -- a key of "k".  This method does a linear walk of the list
  86.       -- to determine where to add the element.
  87.       --
  88.       -- NOTE: This method assumes the object is not already on any lists.
  89.       --
  90.         var q: ptr to Listable
  91.         p.key = k
  92.         if self.IsEmpty ()        -- If the list is empty...
  93.           first = p               --    create a singleton list.
  94.           last = p
  95.         elseIf k < first.key      -- If it should go before the first...
  96.           p.next = first          --    add element to front of list.
  97.           first = p
  98.         else
  99.           for (q = first; q.next; q = q.next)
  100.             if k < q.next.key     -- If it should go after element q...
  101.               p.next = q.next     --    add element after q.
  102.               q.next = p
  103.               return
  104.             endIf
  105.           endFor                  -- If we hit the end...
  106.           last.next = p           --    add element to end of list
  107.           last = p
  108.         endIf
  109.       endMethod
  110.  
  111.     method SortedRemove (whereToStoreItsKey: ptr to int) returns ptr to T
  112.       --
  113.       -- This method removes the item at the front of the list and
  114.       -- returns a ptr to it.  If the list is empty, it returns null.
  115.       -- This method is passed "whereToStoreItsKey", a ptr to an integer
  116.       -- variable (which may be null).  This method will store the key
  117.       -- that this element had in this integer variable, unless the pointer
  118.       -- was null.
  119.       --
  120.         var item: ptr to T = first
  121.         if self.IsEmpty ()
  122.           return null
  123.         endIf
  124.         item = first
  125.         if first == last
  126.           first = null
  127.           last = null
  128.         else
  129.           first = first.next asPtrTo T
  130.         endIf
  131.         if whereToStoreItsKey != null
  132.           * whereToStoreItsKey = item.key
  133.         endIf
  134.         return item
  135.       endMethod
  136.  
  137.   endBehavior
  138.  
  139. endCode
  140.