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 / cse509 / Tree-MVC.st < prev   
Text File  |  2002-01-23  |  13KB  |  460 lines
  1. Object subclass: #Tree3
  2.     instanceVariableNames: 'label leftChild rightChild parent '
  3.     classVariableNames: 'NodeIcon '
  4.     poolDictionaries: ''
  5.     category: 'Tree-MVC'!
  6. !Tree3 commentStamp: '<historical>' prior: 0!
  7. Instances of this class are used to represent nodes in a binary tree.  Each instance points to its parent, children and label.
  8.  
  9. label        <a String>    This is the label on this node.
  10. leftChild    <a Tree>        This is a pointer to the left sub-tree, or nil if none.
  11. rightChild    <a Tree>        This is a pointer to the right sub-tree, or nil if none.
  12. parent        <a Tree>        This is a pointer to the parent of this node, or nil if none.!
  13.  
  14.  
  15. !Tree3 methodsFor: 'access' stamp: 'HHP 1/23/2002 13:48'!
  16. label
  17.  
  18.     ^label! !
  19.  
  20. !Tree3 methodsFor: 'access' stamp: 'HHP 1/23/2002 13:48'!
  21. label: aString
  22.  
  23.     label _ aString.! !
  24.  
  25. !Tree3 methodsFor: 'access' stamp: 'HHP 1/22/2001 14:01'!
  26. leftChild
  27.  
  28.     ^leftChild! !
  29.  
  30. !Tree3 methodsFor: 'access' stamp: 'HHP 1/22/2001 14:01'!
  31. leftChild: aTree
  32.  
  33.     leftChild _ aTree! !
  34.  
  35. !Tree3 methodsFor: 'access' stamp: 'HHP 1/22/2001 14:01'!
  36. parent
  37.  
  38.     ^parent! !
  39.  
  40. !Tree3 methodsFor: 'access' stamp: 'HHP 1/22/2001 14:01'!
  41. parent: aTree
  42.  
  43.     parent _ aTree! !
  44.  
  45. !Tree3 methodsFor: 'access' stamp: 'HHP 1/22/2001 14:01'!
  46. rightChild
  47.  
  48.     ^rightChild! !
  49.  
  50. !Tree3 methodsFor: 'access' stamp: 'HHP 1/22/2001 14:01'!
  51. rightChild: aTree
  52.  
  53.     rightChild _ aTree! !
  54.  
  55.  
  56. !Tree3 methodsFor: 'testing' stamp: 'HHP 1/22/2001 14:02'!
  57. contains: aString
  58.  
  59. "This method answers the question: Does the sub-tree rooted at the receiver contain a node labeled with aString?  It returns a boolean."
  60.  
  61.     (label = aString) ifTrue: [^true].
  62.     (rightChild isNil & leftChild isNil) ifTrue: [^false].
  63.     (leftChild isNil) ifTrue: [^rightChild contains: aString].
  64.     (rightChild isNil) ifTrue: [^leftChild contains: aString].
  65.     ^(leftChild contains: aString) | (rightChild contains: aString)! !
  66.  
  67. !Tree3 methodsFor: 'testing'!
  68. height
  69.  
  70. "Return the height of this sub-tree."
  71.  
  72.     | left right |
  73.  
  74.     left _ leftChild isNil
  75.         ifTrue: [0]
  76.         ifFalse: [leftChild height].
  77.     right _ rightChild isNil
  78.         ifTrue: [0]
  79.         ifFalse: [rightChild height].
  80.     ^ 1 + (left max: right)! !
  81.  
  82. !Tree3 methodsFor: 'testing' stamp: 'HHP 1/22/2001 14:02'!
  83. isLeaf
  84.  
  85. "Is this node a leaf?  Return true or false."
  86.  
  87.     ^ leftChild isNil & rightChild isNil! !
  88.  
  89. !Tree3 methodsFor: 'testing'!
  90. numberOfNodes
  91.  
  92. "This method returns the number of nodes in this sub-tree."
  93.  
  94.     ^ 1
  95.         + (leftChild isNil ifTrue: [0] ifFalse: [leftChild numberOfNodes])
  96.         + (rightChild isNil ifTrue: [0] ifFalse: [rightChild numberOfNodes])! !
  97.  
  98.  
  99. !Tree3 methodsFor: 'tree functions'!
  100. addLeftChild: aTree
  101.  
  102. "This method first removes aTree from whatever tree it is already in (if any) and then it adds it as the left child of the receiver."
  103.  
  104.     (leftChild notNil) ifTrue: [
  105.         leftChild remove
  106.     ].
  107.     (aTree notNil) ifTrue: [
  108.         aTree remove.
  109.         aTree parent: self
  110.     ].
  111.     leftChild _ aTree! !
  112.  
  113. !Tree3 methodsFor: 'tree functions'!
  114. addRightChild: aTree
  115.     
  116. "This method first removes aTree from whatever tree it is already in (if any) and then it adds it as the right child of the receiver."
  117.  
  118.     (rightChild notNil) ifTrue: [
  119.         rightChild remove
  120.     ].
  121.     (aTree notNil) ifTrue: [
  122.         aTree remove.
  123.         aTree parent: self
  124.     ].
  125.     rightChild _ aTree! !
  126.  
  127. !Tree3 methodsFor: 'tree functions'!
  128. remove
  129.  
  130. "This method removes the receiver from whatever tree it is in (if any)."
  131.  
  132.     (parent notNil) ifTrue: [
  133.         (parent leftChild = self) ifTrue: [
  134.             parent leftChild: nil
  135.         ].
  136.         (parent rightChild = self) ifTrue: [
  137.             parent rightChild: nil
  138.         ]
  139.     ].
  140.     parent _ nil! !
  141.  
  142. !Tree3 methodsFor: 'tree functions'!
  143. remove: aLabel
  144.  
  145. "Search the tree whose root is the receiver for a node labelled with aLabel and remove that node.  Return the modified tree's new root."
  146.  
  147.     ^ self  "Unimplemented..."! !
  148.  
  149. !Tree3 methodsFor: 'tree functions'!
  150. removeNode: aNode
  151.  
  152. "This method is passed aNode.  It searches the sub-tree self for the node and removes it.  (It does not remove the children of aNode.)  If the tree contains aNode, it returns the modified sub-tree, otherwise it returns 'false'."
  153.  
  154.     | gotIt |
  155.  
  156.     (self = aNode) ifTrue: [
  157.         ^ self removeRoot
  158.     ].
  159.     leftChild notNil ifTrue: [
  160.         gotIt _ leftChild removeNode: aNode.
  161.         (gotIt ~~ false) ifTrue: [^ self]
  162.     ].
  163.     rightChild notNil ifTrue: [
  164.         gotIt _ rightChild removeNode: aNode.
  165.         (gotIt ~~ false) ifTrue: [^ self]
  166.     ].
  167.     ^false! !
  168.  
  169. !Tree3 methodsFor: 'tree functions'!
  170. removeRoot
  171.  
  172. "This method returns a sub-tree containing all the nodes in the tree whose root is the receiver, except the root node.  If the left sub-tree is nil, it just returns the right sub-tree.  Otherwise, it adds the right sub-tree as the right child of the left sub-tree's right-most descendent and returns the modified left sub-tree."
  173.  
  174.     | newRoot |
  175.  
  176.     ((leftChild isNil) & (rightChild isNil)) ifTrue: [
  177.         self remove.
  178.         ^ nil
  179.     ].
  180.     newRoot _ (leftChild isNil)
  181.                     ifTrue: [rightChild]
  182.                     ifFalse: [leftChild rightMostDescendent addRightChild: rightChild. leftChild].
  183.     (parent isNil) ifTrue: [
  184.         ^ (newRoot parent: nil)
  185.     ].
  186.     (parent leftChild == self) ifTrue: [
  187.         parent addLeftChild: newRoot.
  188.         ^ newRoot
  189.     ].
  190.     (parent rightChild == self) ifTrue: [
  191.         parent addRightChild: newRoot.
  192.         ^ newRoot
  193.     ].
  194.     self error: 'Ill-formed tree within removeRoot'! !
  195.  
  196. !Tree3 methodsFor: 'tree functions' stamp: 'HHP 1/23/2002 10:55'!
  197. rightMostDescendent
  198.  
  199. "Return the right-most descendent of the receiver."
  200.  
  201.     | aTree |
  202.     aTree _ self.
  203.     [aTree rightChild isNil]
  204.         whileFalse: [aTree _ aTree rightChild].
  205.     ^ aTree! !
  206.  
  207.  
  208. !Tree3 methodsFor: 'printing' stamp: 'HHP 1/23/2002 13:39'!
  209. printOn: aStream
  210.  
  211. "This method prints a textual representation of the sub-tree rooted at the receiver on aStream."
  212.  
  213.     "PRINT THE CLASS NAME."
  214.     aStream nextPutAll: self class name.
  215.     aStream nextPutAll: ' '.
  216.  
  217.     "PRINT THE LABEL OF THIS NODE."
  218.     label printOn: aStream.
  219.     self isLeaf ifTrue: [^ 'xxx'].
  220.  
  221.     "PRINT THE LEFT CHILD."
  222.     aStream nextPutAll: ' ('.
  223.     (leftChild isNil) ifTrue: [
  224.         aStream nextPutAll: 'nil'
  225.     ] ifFalse: [
  226.         leftChild printOn: aStream
  227.     ].
  228.  
  229.     "PRINT THE RIGHT CHILD."
  230.     aStream nextPutAll: ', '.
  231.     (rightChild isNil) ifTrue: [
  232.         aStream nextPutAll: 'nil'
  233.     ] ifFalse: [
  234.         rightChild printOn: aStream
  235.     ].
  236.     aStream nextPutAll: ')'.
  237. ! !
  238.  
  239.  
  240. !Tree3 methodsFor: 'interface' stamp: 'HHP 1/22/2001 13:54'!
  241. openInMVC
  242.  
  243. "Open a window on this tree."
  244.  
  245.     | window subView |
  246.  
  247.     "Create a new window."
  248.     window _ (StandardSystemView new) model: self.
  249.     window borderWidth: 2.
  250.  
  251.     "Create a subview."
  252.     subView _ TreeView new.
  253.     subView model: self.
  254.     window addSubView: subView.
  255.  
  256.     window label: 'Tree'.
  257.     window minimumSize: 100@100.
  258.     window controller open.! !
  259.  
  260. "-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!
  261.  
  262. Tree3 class
  263.     instanceVariableNames: ''!
  264.  
  265. !Tree3 class methodsFor: 'instance-creation' stamp: 'HHP 1/23/2002 13:48'!
  266. withLabel: aString
  267.         "This method returns a new Tree with its label initialized to aString and with no children."
  268.         | tree |
  269.         tree _ self new.
  270.         tree label: aString copy.
  271.         ^ tree! !
  272.  
  273. !Tree3 class methodsFor: 'instance-creation' stamp: 'HHP 1/23/2002 13:48'!
  274. withLabel: aLabel withLeft: left withRight: right
  275.         "Create a node with aLabel.  Left and right should be either sub-trees or nil.  Add them as children to this node.  Return the result."
  276.         | tree |
  277.         tree _ self new.
  278.         tree label: aLabel.
  279.         tree addLeftChild: left.
  280.         tree addRightChild: right.
  281.         ^ tree! !
  282.  
  283.  
  284. !Tree3 class methodsFor: 'Initialization' stamp: 'HHP 1/13/2001 11:18'!
  285. initialize
  286.  
  287.     "This method initializes the class variable NodeIcon to contain a Form suitable for use
  288.         in displaying an individual Node."
  289.     "Tree initialize."
  290.  
  291.     | aCircle |
  292.  
  293.     NodeIcon _ Form extent: 25 @ 25.
  294.     aCircle _ Circle new.
  295.     aCircle radius: 13.
  296.     aCircle center: 12@12.
  297.     aCircle displayOn: NodeIcon.
  298. ! !
  299.  
  300.  
  301. View subclass: #TreeView
  302.     instanceVariableNames: ''
  303.     classVariableNames: 'NodeIcon '
  304.     poolDictionaries: ''
  305.     category: 'Tree-MVC'!
  306.  
  307. !TreeView methodsFor: 'displaying' stamp: 'HHP 1/23/2002 10:47'!
  308. displayNode: aTree at: aPoint clippingBox: clipBox xIncr: xIncr yIncr: yIncr
  309.  
  310. "This sub-tree is to display itself on the given Form.  It displays arcs leading down to its sub-trees and then uses itself recursively to obtain a display of its sub-trees."
  311.  
  312.     | leftPoint rightPoint bottomPoint aBitBlt tx |
  313.  
  314.     "DISPLAY THE NODE ICON."
  315.     NodeIcon
  316.         displayOn: Display
  317.         at: (aPoint x - 12) @ (aPoint y)
  318.         clippingBox: clipBox.
  319.     tx _ aTree label asDisplayText.
  320.     tx foregroundColor: Color black backgroundColor: Color transparent.
  321.     tx displayOn: Display
  322.         at: (aPoint x - 3) @ (aPoint y + 3)
  323.         clippingBox: clipBox.
  324.  
  325.     "SET UP A BITBLT FOR USE BELOW."
  326.     aBitBlt _ BitBlt
  327.         destForm: Display
  328.         sourceForm: (Form extent: 1@1) fillBlack
  329.         fillColor: Color black
  330.         combinationRule: 3
  331.         destOrigin: 0 @ 0
  332.         sourceOrigin: 0 @ 0
  333.         extent: Display computeBoundingBox extent
  334.         clipRect: clipBox.
  335.  
  336.     "DISPLAY THE LEFT SUB-TREE AND A LINE DOWN TO IT."
  337.     bottomPoint _ (aPoint x ) @ (aPoint y + 24).
  338.     leftPoint _ (aPoint x - xIncr) @ (aPoint y + yIncr).
  339.     (aTree leftChild) notNil ifTrue: [
  340.         aBitBlt drawFrom: bottomPoint to: leftPoint.
  341.         self
  342.             displayNode: aTree leftChild
  343.             at: leftPoint
  344.             clippingBox: clipBox
  345.             xIncr: xIncr//2
  346.             yIncr: yIncr
  347.     ].
  348.  
  349.     "DISPLAY THE RIGHT SUB-TREE AND A LINE DOWN TO IT."
  350.     rightPoint _ (aPoint x + xIncr) @ (aPoint y + yIncr).
  351.     (aTree rightChild) notNil ifTrue: [
  352.         aBitBlt drawFrom: bottomPoint to: rightPoint.
  353.         self
  354.             displayNode: aTree rightChild
  355.             at: rightPoint
  356.             clippingBox: clipBox
  357.             xIncr: xIncr//2
  358.             yIncr: yIncr
  359.     ]! !
  360.  
  361. !TreeView methodsFor: 'displaying' stamp: 'HHP 1/23/2002 10:51'!
  362. displayView
  363.  
  364. "This routine is called to display the tree.  It makes use of the (inherited) instance variable 'model' and of the 'insetDisplayBox' instance variable to find out what area of the screen is to be displayed on."
  365.  
  366. | tx |
  367.  
  368.     super displayView.
  369.     tx _ 'Here is the tree...' asDisplayText.
  370.     tx foregroundColor: Color black backgroundColor: Color transparent.
  371.     tx displayOn: Display
  372.         at: self insetDisplayBox origin
  373.         clippingBox: self insetDisplayBox.
  374.     self
  375.         displayNode: model
  376.         at: insetDisplayBox topCenter + (0 @ 15)
  377.         clippingBox: insetDisplayBox
  378.         xIncr: 60
  379.         yIncr: 60
  380. ! !
  381.  
  382. !TreeView methodsFor: 'displaying' stamp: 'HHP 1/22/2001 14:07'!
  383. findNodeIn: aTree containsMouse: mousePoint whenDisplayedAt: aPoint clippingBox: clipBox xIncr: xIncr yIncr: yIncr
  384.  
  385. "Imagine that we are displaying this tree, but do not display anything.  Instead, ask which node would contain mousePoint within its NodeIcon and return that node.  Return nil if no node contains mousePoint."
  386.  
  387.     | whereWouldBeDisplayed leftPoint ans rightPoint |
  388.  
  389.     "SEE WHERE WE WOULD HAVE DISPLAYED NodeIcon AND SEE IF IT CONTAINS mousePoint."
  390.     whereWouldBeDisplayed _ 
  391.                     ((aPoint x - 12) @ (aPoint y) extent: (NodeIcon extent))
  392.                             intersect: clipBox.
  393.     (whereWouldBeDisplayed containsPoint: mousePoint) ifTrue: [^self].
  394.  
  395.     "OTHERWISE, CHECK TO SEE IF THE LEFT SUB-TREE CONTAINS mousePoint."
  396.     (aTree leftChild notNil) ifTrue: [
  397.         leftPoint _ (aPoint x - xIncr) @ (aPoint y + yIncr).
  398.         ans _ self findNodeIn: aTree leftChild
  399.                 containsMouse: mousePoint
  400.                 whenDisplayedAt: leftPoint
  401.                 clippingBox: clipBox
  402.                 xIncr: xIncr//2
  403.                 yIncr: yIncr.
  404.         (ans notNil) ifTrue: [^ ans]
  405.     ].
  406.  
  407.     "OTHERWISE, CHECK TO SEE IF THE RIGHT SUB-TREE CONTAINS mousePoint."
  408.     (aTree rightChild notNil) ifTrue: [
  409.         rightPoint _ (aPoint x + xIncr) @ (aPoint y + yIncr).
  410.         ans _ self findNodeIn: aTree rightChild
  411.                 containsMouse: mousePoint
  412.                 whenDisplayedAt: rightPoint
  413.                 clippingBox: clipBox
  414.                 xIncr: xIncr//2
  415.                 yIncr: yIncr.
  416.         (ans notNil) ifTrue: [^ ans]
  417.     ].
  418.  
  419.     "OTHERWISE, RETURN nil."
  420.     ^ nil! !
  421.  
  422. "-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!
  423.  
  424. TreeView class
  425.     instanceVariableNames: ''!
  426.  
  427. !TreeView class methodsFor: 'initialization' stamp: 'HHP 1/13/2001 11:19'!
  428. initialize
  429.  
  430.     "This method initializes the class variable NodeIcon to contain a Form suitable for use
  431.         in displaying an individual Tree nodes."
  432.  
  433.     "TreeView initialize."
  434.  
  435.     | aCircle |
  436.  
  437.     NodeIcon _ Form extent: 25 @ 25.
  438.     aCircle _ Circle new.
  439.     aCircle radius: 13.
  440.     aCircle center: 12@12.
  441.     aCircle displayOn: NodeIcon.
  442. ! !
  443.  
  444.  
  445. !TreeView class methodsFor: 'examples' stamp: 'HHP 1/23/2002 13:47'!
  446. example
  447.     "TreeView example"
  448.  
  449.     | t u w v s |
  450.  
  451.     t _ Tree3 withLabel: 'ttt'.
  452.     u _ Tree3  withLabel: 'uuu'.
  453.     w _ Tree3  withLabel: 'www' withLeft: u withRight: nil.
  454.     v _ Tree3  withLabel: 'vvv' withLeft: nil withRight: w.
  455.     s _ Tree3  withLabel: 'sss' withLeft: t withRight: v.
  456.     s openInMVC.
  457. ! !
  458.  
  459. Tree3 initialize!
  460. TreeView initialize!