home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 1 / RISC_DISC_1.iso / pd_share / code / smalltalk / !GNUst / st / LinkedList < prev    next >
Encoding:
Text File  |  1991-09-13  |  4.1 KB  |  160 lines
  1. "======================================================================
  2. |
  3. |   LinkedList Method Definitions
  4. |
  5.  ======================================================================"
  6.  
  7.  
  8. "======================================================================
  9. |
  10. | Copyright (C) 1990, 1991 Free Software Foundation, Inc.
  11. | Written by Steve Byrne.
  12. |
  13. | This file is part of GNU Smalltalk.
  14. |
  15. | GNU Smalltalk is free software; you can redistribute it and/or modify it
  16. | under the terms of the GNU General Public License as published by the Free
  17. | Software Foundation; either version 1, or (at your option) any later version.
  18. | 
  19. | GNU Smalltalk is distributed in the hope that it will be useful, but WITHOUT
  20. | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  21. | FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  22. | details.
  23. | 
  24. | You should have received a copy of the GNU General Public License along with
  25. | GNU Smalltalk; see the file COPYING.  If not, write to the Free Software
  26. | Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  
  27. |
  28.  ======================================================================"
  29.  
  30.  
  31. "
  32. |     Change Log
  33. | ============================================================================
  34. | Author       Date       Change 
  35. | sbyrne     25 Apr 89      created.
  36. |
  37. "
  38.  
  39. SequenceableCollection subclass: #LinkedList
  40.                instanceVariableNames: 'firstLink lastLink'
  41.                classVariableNames: ''
  42.                poolDictionaries: ''
  43.                category: nil.
  44.  
  45. LinkedList comment:
  46. 'I provide methods that access and manipulate linked lists.  I assume that 
  47. the elements of the linked list are subclasses of Link, because I use 
  48. the methods that class Link supplies to implement my methods.' !
  49.  
  50. !LinkedList methodsFor: 'accessing'!
  51.  
  52. at: index
  53.     "Return the element that is index into the linked list."
  54.     | i element |
  55.     i _ 1.
  56.     element _ firstLink.
  57.     [element isNil] whileFalse:
  58.         [ i = index ifTrue: [ ^element ].
  59.       i _ i + 1.
  60.       element _ element nextLink ].
  61.     ^self error: 'index out of bounds in linked list'
  62. !
  63.  
  64. at: index put: object
  65.     self error: 'Do not store into a LinkedList using at:put:'
  66. !!
  67.  
  68.  
  69.  
  70. !LinkedList methodsFor: 'adding'!
  71.  
  72. add: aLink
  73.     "Add aLink at the end of the list; return aLink."
  74.     self addLast: aLink.
  75.     ^aLink
  76. !
  77.  
  78. addFirst: aLink
  79.     "Add aLink at the head of the list; return aLink."
  80.     lastLink isNil ifTrue: [ lastLink _ aLink ].
  81.     aLink nextLink: firstLink.
  82.     firstLink _ aLink.
  83.     ^aLink
  84. !
  85.  
  86. addLast: aLink
  87.     "Add aLink at then end of the list; return aLink."
  88.     firstLink isNil ifTrue: [ firstLink _ aLink ].
  89.     lastLink notNil ifTrue: [ lastLink nextLink: aLink ].
  90.     lastLink _ aLink.
  91.     ^aLink
  92. !
  93.  
  94. removeFirst
  95.     "Remove the first element from the list and return it, or error if the
  96.     list is empty."
  97.  
  98.     ^self remove: firstLink
  99.           ifAbsent: [ ^self error: 'attempted to remove from an empty list' ]
  100. !    
  101.  
  102. removeLast
  103.     "Remove the final element from the list and return it, or error if the
  104.     list is empty."
  105.  
  106.     ^self remove: lastLink
  107.           ifAbsent: [ ^self error: 'attempted to remove from an empty list' ]
  108. !
  109.  
  110. remove: aLink ifAbsent: aBlock
  111.     "Remove aLink from the list and return it, or invoke aBlock if it's not
  112.     found in the list."
  113.     | temp |
  114.     aLink == firstLink
  115.         ifTrue: [ firstLink _ firstLink nextLink.
  116.               firstLink isNil ifTrue: [ lastLink _ nil ] ]
  117.     ifFalse: [ temp _ firstLink.
  118.                [ temp isNil ifTrue: [ ^aBlock value ].
  119.              temp nextLink == aLink ] whileFalse:
  120.                  [ temp _ temp nextLink ].
  121.            temp nextLink: aLink nextLink.
  122.            aLink == lastLink ifTrue: [ lastLink _ temp ] ].
  123.     aLink nextLink: nil.
  124.     ^aLink
  125. !!
  126.  
  127.  
  128.  
  129. !LinkedList methodsFor: 'enumerating'!
  130.  
  131. do: aBlock
  132.     | aLink |
  133.     aLink _ firstLink.
  134.     [ aLink notNil] whileTrue:
  135.         [ aBlock value: aLink.
  136.       aLink _ aLink nextLink]
  137. !!
  138.  
  139.  
  140.  
  141. !LinkedList methodsFor: 'testing'!
  142.  
  143. isEmpty
  144.     "Returns true if the list contains no members"
  145.     ^firstLink isNil
  146. !!
  147.  
  148.  
  149.  
  150. !LinkedList methodsFor: 'printing'!
  151.  
  152. printOn: aStream
  153.     aStream nextPutAll: self classNameString.
  154. !!
  155.  
  156.  
  157.  
  158. !LinkedList methodsFor: 'storing'!!
  159.  
  160.