% File "rope.tu"
% This file defines the rope class.
%      A rope is an extended precision string.  Rope length is limited only
% by available memory.  Ropes are implemented as trees.  


unit
class rope

        % Imports and exports
        % ------------------------------------------------------------------
        % The rope class uses these other classes:

	import Node in "node.tu",
       		internalNode in "internal.tu",
	       	leafNode in "leaf.tu"


        % These are the subprograms that can be used from outside 
        % the Rope class.  
	% 	SetDataValue and GetDataValue must be exported because
	% other instances of a rope may need access to the `data' instance
	% variable within this rope.  No other classes should need to
	% call SetDataValue or GetDataValue.

	export SetDataValue, GetDataValue,
		Get, Put, Size, Concatenate, SetValue, 
		SubRope, Height, Deallocate


	% Instance variables
        % ------------------------------------------------------------------
        % This is the variable that stores the actual rope data structure.
	% Every instance of the class rope has its own instance of this 
	% variable to store its rope.
	%	Throughout this file, when we say "this rope", we mean
	% the rope associated with the present instance of the class.
	% This rope is, as stated above, stored using the variable `data'.
      	%      `data' is a pointer to a tree node.  The `Node' class itself
 	% "knows" how to do everything that one needs to do with a tree
	% node, so the rope operations use Node subprograms to do their
	% work.
	%      The initial value for `data' is nil, because the rope
	% begins as empty.

	var data : ^Node := nil


        % SetDataValue
        % ------------------------------------------------------------------
	% Sets the value of this rope to be the rope stored by `n', i.e.,
	% the rope represented by the tree rooted at node `n'.  Unlike the
	% `setValue' procedure below, `setDataValue' does not create a copy 
	% of the rope in newly-allocated memory; instead, it merely points to 
	% the existing tree rooted at `n'.
	% 	This is accomplished by setting the `data' instance variable 
	% to the given Node pointer.
	% 	This procedure is intended for "internal" use only; no class
	% other than rope should use it.

	procedure SetDataValue(n : ^Node)
		data := n
	end SetDataValue


        % GetDataValue
        % ------------------------------------------------------------------
	% Returns the instance variable `data' that stores this rope.
	% 	This procedure is intended for "internal" use only; no class
	% other than rope should use it.

	function GetDataValue : ^Node
		result data
	end GetDataValue


        % Get
        % ------------------------------------------------------------------
	% Sets this rope to the rope 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.)
	%	Hint: depending on the number of characters to be read,
	% we may need to create only a leaf node, or a subtree rooted at
	% (of course) an internal node.

	procedure Get(inStream : int, numChars : int)

		if numChars <= Node.MaxLeafSize then
			var newNode : ^leafNode
			new newNode
			assert newNode not= nil

			newNode->Get(inStream, numChars)

			data := newNode
		elsif numChars > Node.MaxLeafSize then

			var newNode : ^internalNode
			new newNode
			assert newNode not= nil

			newNode->Get(inStream, numChars)

			data := newNode
		end if
	end Get


        % Put
        % ------------------------------------------------------------------
	% Prints this rope 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.

	procedure Put(outStream : int, lineWidth : int)
		var linePos : int := 1

		if data not= nil then

			data->Put(outStream, linePos, lineWidth)
			put ""

		end if
	end Put

		
        % Size
        % ------------------------------------------------------------------
	% Returns the number of characters in this rope.
	%	Hint: What if data is nil because no rope has been created
	% yet?  Give a sensible answer and don't crash.

	function Size : int
		if data = nil then
			result 0
		else
			result data->Size
		end if
	end Size


        % Concatenate
        % ------------------------------------------------------------------
	% Sets this rope to the concatenation of the two given ropes.
	% No new memory is used; the existing trees for the two ropes are 
	% merely joined together.
	% 	Hint: Either s1 or s2 or even both could be nil.

	procedure Concatenate(s1, s2 : ^rope)

		if s1 = nil and s2 not= nil then
			data := s2->GetDataValue
		elsif s2 = nil and s1 not= nil then
			data := s1->GetDataValue
		elsif s1 not= nil and s2 not= nil then
			var tmp : ^internalNode
			new tmp
			assert tmp not= nil

			tmp->Concatenate(s1->GetDataValue, s2->GetDataValue)
			data := tmp
		else
			data := nil
		end if
	end Concatenate


        % SetValue
        % ------------------------------------------------------------------
	% Sets this rope's value to that of the string `s' --- an ordinary 
	% OOT string.  This is logically analogous to an assignment statement 
	% ending in `:= s'.  Thus, we are copying the value of `s' into the
	% rope.
	%     	Because we are copying the value of `s', a small tree must 
	% be built in which to store the copied value.  
	%  	Hint: Since we are only copying something the size of an
	% ordinary OOT string, we only need a leaf node to hold it.

	procedure SetValue(s : string)
		if s not= "" then
			var tmp : ^leafNode
			new tmp
			assert tmp not= nil

			tmp->SetLeafValue(s)
			data := tmp
		end if
	end SetValue


        % SubRope
        % ------------------------------------------------------------------
	% Extracts the subrope between positions `pos1' and `pos2' in 
	% this rope.  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.

	function SubRope(pos1, pos2 : int) : ^rope
		
		% Note that, if pos1 = pos2 + 1,
		% we will simply create the empty string.
		% (Consistent with OOT's substring function.)
		assert pos1 >= 1 and pos1 <= pos2 + 1

		assert pos2 <= data->Size

		var newRope : ^rope
		new newRope
		assert newRope not= nil

		if pos1 = pos2 + 1 then
			% We need to return the null rope as the subrope.
			% So make a leaf node and store the null string in it.
			var newNode : ^leafNode
			new newNode
			assert newNode not=nil
			newNode -> SetLeafValue("")

			% Now make our subrope point to that leaf node.
			newRope->SetDataValue(newNode)

		elsif data not= nil then
			newRope->SetDataValue(data->SubRope(pos1, pos2))
		end if

		result newRope
	end SubRope


	% Height
	% ------------------------------------------------------------------
	% Returns the height of the tree that represents this rope.
	% Such a procedure would not normally be exported from the rope
	% class because it relates only to internal details of the data
	% structure.  However, it is helpful for demonstrating that the
	% trees built by Get are indeed balanced.
        %       Hint: What if data is nil because no rope has been created
        % yet?  Give a sensible answer and don't crash.

	function Height : int
		if data = nil then
			result 0
		else
			result data->Height
		end if
	end Height


        % Deallocate
        % ------------------------------------------------------------------
	% Frees up all memory used by this rope.  Upon completion, the
	% instance variable `data' is set to nil.
	%	Hint: Once we deallocate all the descendents of the root 
	% node, we should free up the root node itself.
	%	Hint: Again, What if data is nil because no rope has been 
        % created yet?  Don't crash.

	procedure Deallocate
		if data not= nil then
			data->Deallocate
			free data
			data := nil
		end if
	end Deallocate


end rope