% 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

                % <Fill this in.>

	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)

                % <Fill this in.>

	end Concatenate


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

	body function Size : int

                % <Fill this in.>

	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)

                % <Fill this in.>

	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)

                % <Fill this in.>

	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

                % <Fill this in.>

	end SubRope


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

	body function Height : int

                % <Fill this in.>

	end Height

end internalNode