Solved

Using binary search in javascript

Posted on 2014-12-15
8
136 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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 43

Expert Comment

by:Rob
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
Increase Agility with Enabled Toolchains

Connect your existing build, deployment, management, monitoring, and collaboration platforms. From Puppet to Chef, HipChat to Slack, ServiceNow to JIRA, Splunk to New Relic and beyond, hand off data between systems to engage the right people.

Connect with xMatters.

 

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

Quiz: What Do These Organizations Have In Common?

Hint: Their teams ended up taking quizzes, too.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

PaperPort is a popular document imaging/management product from Nuance Communications (http://www.nuance.com/). It is in widespread use by both individuals (http://www.nuance.com/for-individuals/by-product/paperport/index.htm) and businesses (http:/…
*Adobe Acrobat 9 was used for this article.  Particular steps may vary depending on software versions. Adobe Acrobat has many, many variables that my be utilized to customize your forms for clarity and ease of use. The Form Editing Tool will be y…
The viewer will learn how to dynamically set the form action using jQuery.
In this sixth video of the Xpdf series, we discuss and demonstrate the PDFtoPNG utility, which converts a multi-page PDF file to separate color, grayscale, or monochrome PNG files, creating one PNG file for each page in the PDF. It does this via a c…

691 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