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