LazyString

This essay is about a suggested student project in Java programming. This essay gives a rough overview of how it might work. It does not describe an actual complete program. I have no source, object, specifications, file layouts or anything else useful to implementing this project. Everything I have to say to help you with this project is written below. I am not prepared to help you implement it; I have too many other projects of my own.

I do contract work for a living, which could include writing a program such as this. However, I don’t do people’s homework for them. That just robs them of an education.

You have my full permission to implement this project any way you please.

LazyString is like a cross between String and StringBuffer especially good for processing long String s such as in-RAM copies of files. It would be particularly efficient at doing a series of bulk search and replace operations.

Why lazy?

It procrastinates the work of copying characters about. In the process, it saves considerable work copying and creating String and StringBuffer objects.
LazyString does almost no work itself. It fobs the bullwork off on its older brothers String and StringBuffer .

How does it work? It maintains the String internally as a LinkedList of String fragments. Each fragment contains a reference to a String , a starting point in the String and the ending point in the String , i.e. the parameters you would pass to String.substring to access a piece of some bigger String .

Only when you are done and use the LazyString.toString method do you collect all the fragments together contiguously and convert it to a String . You implement that with a series of StringBuffer.append s and a StringBuffer.toString . I refer to this process as collapsing . LazyString is at liberty to at any time collapse the entire String or any part of it. It might do this when the ratio of number of fragments to the total size of the fragments is greater than some magic number where the optimal value of that number is found by experiment. (It would neat to have a general purpose HotSpot-style optimiser that would tweak such constants to suit the current data. It could then apply what it had learned from previous experiments to instantly set the tweaking constants for any given set of data.) You should make the magic number optionally configurable in the constructor because it depends on just which methods you use most. By setting the number to 0, you effectively make it act like a simple String. You might use -1 as a special code to make it behave like a simple StringBuffer.

The overhead of using LazyString does not pay back unless you are handling large String s, but it should be orders of magnitude faster then.

You want to implement as many of the methods of String and StringBuffer as you have energy for. Don’t make the LazyString class final unless you provide source. Others may want to add their own convenience methods. See the StringBuffer student project.

Comparison of LazyString String and StringBuffer
Method	LazyString	String	StringBuffer	Notes
append	very fast	very slow	slow	To append, i.e. concatenate, String allocates a new StringBuffer containing an array of characters and copies character by character to the tail end of the array. LazyString just adds a node to the end of the LinkedList .
substring	fast	very fast	slow	String does not copy any characters to implement substring . LazyString has to copy the list of nodes comprising the substring, but not the characters themselves.
indexOf(char)	very slow	slow	slow	LazyString fobs the work off on String.indexOf for each fragment.
indexOf(String)	very slow	slow	slow	LazyString fobs the work off on String.indexOf for each fragment. Dealing with finding strings that span fragments is difficult, but necessary. Don’t be tempted to implement this with String.toString then use String.indexOf or you defeat the point of LazyString . If you want to get clever, use Boyer Moore.
charAt(int)	fast	very fast	very fast	LazyString fobs the work off on String.charAt for each fragment. To find the right fragment, LazyString needs to construct an array of bands to track which part of the String is covered by each fragment and pass that to java.util.Arrays.binarySearch . You can procrastinate creating the array until it is needed. Alternatively you might use a TreeMap to track the fragments and find the one corresponding to a given offset.

Rope class

	Please email your feedback for publication, errors, omissions, broken/redirected link reports and suggestions to improve this page to Roedy Green :
	Canadian Mind Products
	mindprod.com IP:[65.110.21.43]
	Your face IP:[38.103.63.59]	The information on this page is for non-military use only.
	You are visitor number 3,761.	Military use includes use by defence contractors.
	You can get a fresh copy of this page from:	or possibly from your local J: drive (Java virtual drive/mindprod.com website mirror)
	http://mindprod.com/project/lazystring.html	J:\mindprod\project\lazystring.html