home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / smalltalk-1.1.1 / OrderedCollection.st < prev    next >
Encoding:
Text File  |  1991-09-12  |  7.3 KB  |  264 lines
  1. "======================================================================
  2. |
  3. |   OrderedCollection 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     19 Sep 89      Converted to use real method categories.
  36. |
  37. | sbyrne     25 Apr 89      created.
  38. |
  39. "
  40.  
  41. SequenceableCollection variableSubclass: #OrderedCollection
  42.                instanceVariableNames: 'firstIndex lastIndex'
  43.                classVariableNames: ''
  44.                poolDictionaries: ''
  45.                category: nil !
  46.  
  47. OrderedCollection comment: 
  48. 'My instances represent ordered collections of arbitrary typed objects which
  49. are not directly accessible by an index.  They can be accessed indirectly
  50. through an index, and can be manipulated by adding to the end or based
  51. on content (such as add:after:)' !
  52.  
  53. !OrderedCollection class methodsFor: 'instance creation'!
  54.  
  55. new: anInteger
  56.     ^(super new: anInteger) initIndices
  57. !
  58.  
  59. new
  60.     ^self new: 16
  61.  
  62. !!
  63.  
  64.  
  65.  
  66. !OrderedCollection methodsFor: 'accessing'!
  67. at: index
  68.     index _ index + firstIndex - 1.
  69.     (index >= firstIndex and: [ index <= lastIndex ])
  70.         ifTrue: [ ^self basicAt: index ]
  71.     ifFalse: [ self error: 'index out of bounds for ordered collection' ]
  72. !
  73.  
  74. at: index put: anObject
  75.     index _ index + firstIndex - 1.
  76.     (index >= firstIndex and: [ index <= lastIndex ])
  77.         ifTrue: [ ^self basicAt: index put: anObject ]
  78.     ifFalse: [ self error: 'index out of bounds for ordered collection' ]
  79. !    
  80.  
  81. after: oldObject
  82.     "Return the element after oldObject.  Error if oldObject not found or
  83.     if no following object is available"
  84.     firstIndex to: lastIndex do:
  85.         [ :index |        "should we use '=' or '==' here?"
  86.         (self basicAt: index) = oldObject
  87.             ifTrue: [
  88.             index < lastIndex
  89.                 ifTrue: [ ^self basicAt: index + 1 ]
  90.             ifFalse: [ ^self error: 'no following object' ] ]
  91.         ].
  92.     self error: 'object not found'
  93. !
  94.  
  95. before: oldObject
  96.     "Return the element after oldObject.  Error if oldObject not found or
  97.     if no following object is available"
  98.     firstIndex to: lastIndex do:
  99.         [ :index |        "should we use '=' or '==' here?"
  100.         (self basicAt: index) = oldObject
  101.             ifTrue: [
  102.             index > firstIndex
  103.                 ifTrue: [ ^self basicAt: index - 1 ]
  104.             ifFalse: [ ^self error: 'no preceding object' ] ]
  105.         ].
  106.     self error: 'object not found'
  107. !
  108.  
  109. copyEmpty
  110.     ^self species new: self basicSize
  111. !
  112.  
  113. size
  114.     ^lastIndex - firstIndex + 1
  115. !!
  116.  
  117.  
  118.  
  119. !OrderedCollection methodsFor: 'adding'!
  120.  
  121. add: anObject
  122.     ^self addLast: anObject
  123. !
  124.  
  125. add: newObject after: oldObject
  126.     firstIndex to: lastIndex do:
  127.         [ :i | (self basicAt: i) = oldObject
  128.                 ifTrue: [ self at: i + 1 insertObject: newObject.
  129.                               ^newObject ] ].
  130.     self error: 'object not found in collection'
  131. !
  132.  
  133. add: newObject before: oldObject
  134.     firstIndex to: lastIndex do:
  135.         [ :i | (self basicAt: i) = oldObject
  136.                 ifTrue: [ self at: i - 1 insertObject: newObject.
  137.                               ^newObject ] ].
  138.     self error: 'object not found in collection'
  139. !
  140.  
  141.  
  142. addAllFirst: anOrderedCollection
  143.     anOrderedCollection reverseDo:
  144.         [ :element | self addFirst: element ].
  145.     ^anOrderedCollection
  146. !
  147.     
  148. addAllLast: anOrderedCollection
  149.     anOrderedCollection do:
  150.         [ :element | self addLast: element ].
  151.     ^anOrderedCollection
  152. !
  153.     
  154.  
  155. addFirst: newObject
  156.     firstIndex = 1
  157.         ifTrue: [ self growFirst ].
  158.     firstIndex _ firstIndex - 1.
  159.     ^self basicAt: firstIndex put: newObject
  160. !
  161.     
  162. addLast: newObject
  163.     lastIndex = self basicSize
  164.         ifTrue: [ self growLast ].
  165.     lastIndex _ lastIndex + 1.
  166.     ^self basicAt: lastIndex put: newObject
  167. !!
  168.  
  169.  
  170.  
  171. !OrderedCollection methodsFor: 'removing'!
  172. removeFirst
  173.     lastIndex < firstIndex
  174.         ifTrue: 
  175.             [ ^self error: 'attempted to remove from an empty collection' ].
  176.     firstIndex _ firstIndex + 1.
  177.     ^self basicAt: firstIndex - 1
  178. !
  179.  
  180. removeLast
  181.     lastIndex < firstIndex
  182.         ifTrue: 
  183.             [ ^self error: 'attempted to remove from an empty collection' ].
  184.     lastIndex _ lastIndex - 1.
  185.     ^self basicAt: lastIndex + 1
  186. !!
  187.  
  188.  
  189.  
  190. !OrderedCollection methodsFor: 'private methods'!
  191.  
  192. initIndices
  193.     firstIndex _ self basicSize // 2 max: 1.
  194.     lastIndex _ firstIndex - 1
  195. !
  196.  
  197. firstIndex: first lastIndex: last
  198.     firstIndex _ first.
  199.     lastIndex _ last
  200. !
  201.  
  202. growFirst
  203.     "Make growSize room at the start of the ordered collection, and copy
  204.     all the elements of the old collection into the new one starting
  205.     at the value that growSize returned."
  206.     | newOrderedCollection delta |
  207.     delta _ self growSize.
  208.     newOrderedCollection _ self growTo: self basicSize + delta.
  209.     firstIndex to: lastIndex do:
  210.         [ :index | newOrderedCollection basicAt: delta + index - 1
  211.                                     put: (self basicAt: index) ].
  212.     newOrderedCollection firstIndex: delta + firstIndex - 1
  213.                          lastIndex: delta + lastIndex - 1.
  214.     ^self become: newOrderedCollection    
  215. !
  216.  
  217. growLast
  218.     "Make growSize room at the end of the ordered collection, and copy
  219.     all the elements of the old collection into the new one starting
  220.     at firstIndex."
  221.     | newOrderedCollection |
  222.     newOrderedCollection _ self growTo: self basicSize + self growSize.
  223.     firstIndex to: lastIndex do:
  224.         [ :index | newOrderedCollection basicAt: index
  225.                                     put: (self basicAt: index) ].
  226.     newOrderedCollection firstIndex: firstIndex
  227.                          lastIndex: lastIndex.
  228.     ^self become: newOrderedCollection    
  229. !
  230.  
  231. grow
  232.     "Make growSize room in the collection, putting the old contents in the
  233.     middle."
  234.     | oldSize newSize newFirstIndex newOrderedCollection |
  235.     oldSize _ self basicSize.
  236.     newSize _ oldSize + self growSize.
  237.     newOrderedCollection _ self growTo: newSize.
  238.     newFirstIndex _ newSize - oldSize // 2 max: 1.
  239.     1 to: self size do:
  240.         [ :i | newOrderedCollection basicAt: i + newFirstIndex - 1
  241.                                 put: (self basicAt: i + firstIndex - 1) ].
  242.     newOrderedCollection firstIndex: newFirstIndex
  243.                          lastIndex: newFirstIndex + self size - 1.
  244.     ^self become: newOrderedCollection
  245. !
  246.  
  247. growTo: anInteger
  248.     ^self species new: anInteger
  249. !    
  250.  
  251. growSize
  252.     ^10                "number out of a hat"
  253. !
  254.  
  255. at: index insertObject: anObject
  256.     lastIndex = self basicSize ifTrue: [ self growLast ].
  257.     lastIndex to: index by: -1 do:
  258.         [ :i | self basicAt: i + 1
  259.                 put: (self basicAt: i) ].
  260.     self basicAt: index put: anObject.
  261.     ^anObject
  262. !!
  263.  
  264.