% File "internal.tu"
% This file defines the internalNode class.
% 	An internal node constitutes the root of a tree or subtree.  It is 
% implemented by pointers to two children. and an integer that denotes 
% the length of the rope represented by the tree of which it is root.
%  	The string represented by an internal node is simply 
% the string that results from concatenating the two strings represented by
% its two children.  
% 	An internalNode is a specialization of a general Node.  


unit
class internalNode

	% Parent class
	% ------------------------------------------------------------------
	% An internalNode is a specialization of a general Node.
	% It inherits the constant and the subprogram headers from the Node
	% class.

	inherit Node in "node.tu"


	% Imports and exports
        % ------------------------------------------------------------------
        % In addition to the imports and exports of its parent class, Node,
	% the internalNode class uses the leafNode class.

	import leafNode in "leaf.tu"


        % Instance variables
        % ------------------------------------------------------------------
	% These are the variables that store the actual node information.
	% Every instance of the class internalNode has its own instance of 
        % these variables.
	%	`left' and `right' are pointers to the two children of this
	% internal node.  Their initial value is nil, since there are not
	% any until routines like Get are called to create them.
	%	`mySize' stores the number of characters in the string 
	% represented by this node.  Its initial value is zero, also because
	% there are not yet any children, and hence this node represents
	% the null string.

	var mySize : int := 0
	var left, right : ^Node := nil


	% Deallocate
        % ------------------------------------------------------------------
	% Frees up the memory used by the subtree rooted at this node
	% by freeing up the memory used by its children.

	body procedure Deallocate
		left->Deallocate
		free left
		right->Deallocate
		free right
	end Deallocate


        % Concatenate
        % ------------------------------------------------------------------
	% Sets this node to the concatenation of the two given nodes.
        % No new memory is used; the existing subtrees are merely joined 
	% together.

	body procedure Concatenate(s1, s2 : ^Node)
		left := s1
		right := s2
		mySize := s1->Size + s2->Size
	end Concatenate


        % Size
        % ------------------------------------------------------------------
        % Returns the number of characters in the rope rooted at this node.

	body function Size : int
		result mySize
	end Size


        % Get
        % ------------------------------------------------------------------
        % Sets this node to the root of the tree obtained by reading `numChars' 
	% characters from the given stream.  The stream number -2 denotes 
	% input from the the standard input.
        %       Carriage returns in the input are ignored.  (Thus the user
        % is able to break long strings up into separate lines of input.)
	%	`numCharsToRead' is used to allow us to build a balanced
	% tree.
	%	Hint: Divide in half and conquer.

	body procedure Get(inStream : int, numCharsToRead : int)
		assert numCharsToRead > MaxLeafSize

		const firstHalf := numCharsToRead div 2
		const secondHalf := numCharsToRead - firstHalf

		% Busy work. Allocate the appropriate types of nodes.

		if firstHalf <= MaxLeafSize then
			var leftTmp : ^leafNode
			new leftTmp
			assert leftTmp not= nil
			left := leftTmp
		else
			var leftTmp : ^internalNode
			new leftTmp
			assert leftTmp not= nil
			left := leftTmp
		end if

		if secondHalf <= MaxLeafSize then
			var rightTmp : ^leafNode
			new rightTmp
			assert rightTmp not= nil
			right := rightTmp
		else
			var rightTmp : ^internalNode
			new rightTmp
			assert rightTmp not= nil
			right := rightTmp
		end if

		left->Get(inStream, firstHalf)
		right->Get(inStream, secondHalf)

		mySize := numCharsToRead
			
	end Get


        % Put
        % ------------------------------------------------------------------
        % Prints the rope represented by the tree rooted at this node
	% to the given stream.  (The special stream number
        % -1 denotes output to the standard output.)  For readability, line
        % breaks are printed every `lineWidth' characters.  Zero is a special
        % case; if `lineWidth' is zero, no line breaks are printed.

	body procedure Put(outStream: int, var linePos : int, 
				lineWidth : int)
		left->Put(outStream, linePos, lineWidth)
		right->Put(outStream, linePos, lineWidth)
	end Put


	% SubRope
        % ------------------------------------------------------------------
        % Extracts the subrope between positions `pos1' and `pos2' in
        % the rope represented by the tree rooted at this node.  
	% This function behaves like S(pos1..pos2) in OOT,
        % except that it operates on ropes rather than strings.
        %       All boundary and error cases (e.g., first > last) are
        % handled in the same way that the OOT substring operation does.
	%	Hint: if the whole subrope is contained in the left child
	% of this node, or if it is contained in the right child, the task
	% is relatively easy.  If it straddles the children, pull out an 
	% appropriate piece from each side and stick them together.

	body function SubRope(pos1, pos2 : int) : ^Node
		const leftSize := left->Size

		if pos1 > leftSize then

			% The whole subrope is on the right.
			const newpos1 := pos1 - leftSize
			const newpos2 := pos2 - leftSize
			result right->SubRope(newpos1, newpos2)

		elsif pos2 <= leftSize then

			% The whole subrope is on the left.
			result left->SubRope(pos1, pos2)

		else
		
			% The subrope straddles both sides.
			var newNode : ^internalNode
			new newNode
			assert newNode not= nil

			const newpos2 := pos2 - leftSize
			newNode->Concatenate( left->SubRope(pos1, leftSize),
				         right->SubRope(1, newpos2))

			result newNode

		end if
	end SubRope


        % Height
        % ------------------------------------------------------------------
        % Returns the height of the tree rooted at this node.

	body function Height : int
		result 1 + max(left->Height, right->Height)
	end Height

end internalNode