Solved

Using binary search in javascript

Posted on 2014-12-15
8
127 Views
Last Modified: 2015-02-11
Using a binary search in javascript

Currently I have a script that reads in text entered into a free text field.
The free text field is a certain height and I want it to resize depending on how much text is entered into it - i.e. it starts off large and will reduce in height if the text doesn't fill it.

At the moment I am iterating through each character in a for loop...
if (myText !== "") {
        for (var i = 0; i < myText.length; ++i) {
			//focus on one character at a time
            var currentChar = myText.charAt(i);
			//set the current field text to the accumulated characters iterated through so far, including the current
            currentField.setText(currentText + currentChar);
            var stringHeight = currentField.getStringHeight();
			//check the current height of all the text is less than the maximum field height
            if (stringHeight < maxHeight) {
                myText += currentChar;
            }
	} else {
		//check for last full word and append it to the next field
	}
}

Open in new window


where myText is the string contents of the free text field.
as I iterate through I check the stringheight of that the text so far in a custom function I have written. This function is however very expensive so rather than checking every character I would like to use
a binary search to find the point at which the stringHeight becomes greater than the field height.
0
Comment
Question by:Al4ddin2
8 Comments
 
LVL 53

Expert Comment

by:COBOLdinosaur
ID: 40501005
What do you mean by "free text field"?

If it is in a web page the I presume it is in a block element like a div. If that is the case define the width and not the height and it will default to height:auto which causes the div to size itself to the content.

Cd&
0
 
LVL 42

Expert Comment

by:Rob Jurd, EE MVE
ID: 40501777
This just checks the scrollWidth of the text element and adjusts the font size so that the string will fit: http://jsbin.com/fabido/1/edit?js,output
0
 

Author Comment

by:Al4ddin2
ID: 40506729
Hi

No it's not on a webpage. It's on a PDF. If it was on a webpage then it would be very straight forward. Anyway my approach is not the issue, I would like to turn my process of iterating through each character in a for loop into a binary search to improve performance. Not sure where is best to start.

Thanks
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 

Author Comment

by:Al4ddin2
ID: 40569068
Hi,

I still need assistance with this please?
This is my script at the moment....
Letter is the name of the text field I am targeting initially, Letter P2 is the overflow, as is Letter P3 & P4.
var field, maxHeight, targetField, currentField, origText, testText, cleanText, fieldY;
var offSet = 10;
var footer = Document.getField("Caveat And Footer");
var signOff = Document.getField("Valediction");
var pageCount = Document.getNumberOfPages();

function fieldArrayCreate(){
	var array = [];
	field = Document.getField("Letter");
	array.push(field);
	for (var i = 2; i <= pageCount; ++i){
		field = Document.getField("Letter P" + i);
		array.push(field);
	}
	return array;
}

function checkTextforLastWord(text){
	var lastWordText = "";
	for (var i = text.length - 1; text.length >= 0; --i){		
		if (text[i] == "\t" || text[i] == "\n" || text[i] == " "){
			return lastWordText;
		} else {
			lastWordText.concat(text[i]);
		}
	} return lastWordText;
}

function splitText() {
	var fieldArray = fieldArrayCreate();
	alert("We are working with: " + fieldArray.length + " fields");
	var constantArray = fieldArray;
	var previousField = "";
	var globalVariable = Document.getGlobalTextVariable("LetterText");
	currentField = fieldArray.shift();
    maxHeight = currentField.getHeight();
    origText = globalVariable.getValue();
    cleanText = origText.replace(/\[(.*?)\]/g, '');
	alert("The text we are looking at: " + cleanText);
	
// here I check what the height would be for 3 lines of text and reduce the field height by that so that it would pass the three lines of text into the overflow fields.
	var testHeightText = "A\nA\nA";
	currentField.setText(testHeightText);
	var removeLinesHeight = currentField.getStringHeight();
	alert("We have calculated we remove for 3 lines: " + removeLinesHeight);
	
	currentField.setText("");
	maxHeight = maxHeight - removeLinesHeight;
	var currentText = "";
    if (cleanText !== "") {
		
        for (var i = 0; i < cleanText.length; ++i) {
			//focus on one character at a time
            var currentChar = cleanText.charAt(i);
			//set the current field text to the accumulated characters iterated through so far, including the current
            currentField.setText(currentText + currentChar);
            var stringHeight = currentField.getStringHeight();
			//check the current height of all the text is less than the maximum field height
            if (stringHeight < maxHeight) {
                currentText += currentChar;
            } else {
                var lastWord = checkTextforLastWord(currentText);
				if (lastWord != ""){
					alert(lastWord);
					var removeCount = lastWord.length;
					currentText = currentText.substring(0, currentText.length - removeCount);
					currentField.setText(currentText);
				}
				previousField = currentField;
				currentField = fieldArray.shift();
				if (currentField){
					maxHeight = currentField.getHeight();
					maxHeight = maxHeight - removeLinesHeight;
					currentField.setText(lastWord + currentChar);
					currentText = "";
				}
				else {
					break;
				}
            }
			//No need: cleanText = cleanText.slice(i)
        }
		if(currentText != "" && currentField != null) {
			currentField.setText(currentText);
		}
		else if(currentText != "" && currentField == null) {
			alert("You have too much text for the available fields");
		}
        
		if (currentField) {
			var contentHeight = currentField.getStringHeight() + 20;
			var height = currentField.getHeight();
			var Y = currentField.getY();
			var signOffHeight = signOff.getHeight();
			var page = currentField.getPage();
			signOff.setPage(page);
			signOff.setY(Y + (height - contentHeight) - signOffHeight);
			footer.setPage(page);
		}
    }
}

splitText();

Open in new window



Although it seems to do what it should, it is very very slow and sometimes times out so I need to modify the way it checks the height by using a binary search of sorts. I need to get the cleantText.length then halve it, check the height, if it fits then put it in and then split the second half, check if it fits in - if it does continue etc.

Can anyone assist?

Thanks
0
 
LVL 29

Accepted Solution

by:
fibo earned 500 total points
ID: 40572762
I must confess I do not understand really what you want to achieve.

Since you are more or less trying to find a number of text "chunks" (whether lines or pages) the length of which is not totally known; I would probably explore the idea to start with a guesstimate of some parameters (length or number of chunks) based on some simple rules of thumb. eg, min and max length of chunk and min and max number of chunks
You would then start your exploration at min-length AND record end of words in an array: I would then be able to re-use the information I have painfully collected.

Does that make sense for your problem?
0
 
LVL 29

Expert Comment

by:fibo
ID: 40602858
B-) glad we could help. Thx for the grade and points
0

Featured Post

Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

Join & Write a Comment

Suggested Solutions

*Adobe Acrobat 9 was used for this article. Particular steps may vary depending on software versions. 1. Create a framework of your form in Word, leaving space where you’d ultimately like the Adobe fields to appear.  (Note: I use the blank lines …
International Data Corporation (IDC) prognosticates that before the current the year gets over disbursing on IT framework products to be sent in cloud environs will be $37.1B.
In this first video of the three-part Xpdf series, we introduce and describe Xpdf, a library containing nine command line utilities that perform various functions on PDF files. We show where the library is located and how to download it, discuss its…
The viewer will learn how to dynamically set the form action using jQuery.

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now