function AutoCompleteDB()
{
	// set the initial values.
	this.bEnd = false;
	this.nCount = 0;
	this.aStr = new Object;
}

AutoCompleteDB.prototype.add = function(str)
{
	// increment the count value.
	this.nCount++;

	// if at the end of the string, flag this node as an end point.
	if ( str == "" )
		this.bEnd = true;
	else
	{
		// otherwise, pull the first letter off the string
		var letter = str.substring(0,1);
		var rest = str.substring(1,str.length);
		
		// and either create a child node for it or reuse an old one.
		if ( !this.aStr[letter] ) this.aStr[letter] = new AutoCompleteDB();
		this.aStr[letter].add(rest);
	}
}

AutoCompleteDB.prototype.getCount = function(str, bExact)
{
	// if end of search string, return number
	if ( str == "" )
		if ( this.bEnd && bExact && (this.nCount == 1) ) return 0;
		else return this.nCount;
	
	// otherwise, pull the first letter off the string
	var letter = str.substring(0,1);
	var rest = str.substring(1,str.length);
	
	// and look for case-insensitive matches
	var nCount = 0;
	var lLetter = letter.toLowerCase();
	if ( this.aStr[lLetter] )
		nCount += this.aStr[lLetter].getCount(rest, bExact && (letter == lLetter));
	
	var uLetter = letter.toUpperCase();
	if ( this.aStr[uLetter] )
		nCount += this.aStr[uLetter].getCount(rest, bExact && (letter == uLetter));
	
	return nCount;	
}

AutoCompleteDB.prototype.getStrings = function(str1, str2, outStr)
{
	if ( str1 == "" )
	{
		// add matching strings to the array
		if ( this.bEnd ) 
			outStr.push(str2);

		// get strings for each child node
		for ( var i in this.aStr )
			this.aStr[i].getStrings(str1, str2 + i, outStr);
	}
	else
	{
		// pull the first letter off the string
		var letter = str1.substring(0,1);
		var rest = str1.substring(1,str1.length);
		
		// and get the case-insensitive matches.
		var lLetter = letter.toLowerCase();
		if ( this.aStr[lLetter] )
			this.aStr[lLetter].getStrings(rest, str2 + lLetter, outStr);

		var uLetter = letter.toUpperCase();
		if ( this.aStr[uLetter] )
			this.aStr[uLetter].getStrings(rest, str2 + uLetter, outStr);
	}
}


function AutoComplete(aStr, oText, oDiv, nMaxSize)
{
	// initialize member variables
	this.oText = oText;
	this.oDiv = oDiv;
	this.nMaxSize = nMaxSize;
	
	// preprocess the texts for fast access
	this.db = new AutoCompleteDB();
	var i, n = aStr.length;
	for ( i = 0; i < n; i++ )
	{
		this.db.add(aStr[i]);
	}
			
	// attach handlers to the text-box
	oText.AutoComplete = this;
	oText.onkeyup = AutoComplete.prototype.onTextChange;
	oText.onblur = AutoComplete.prototype.onTextBlur;
}

AutoComplete.prototype.onTextBlur = function()
{
	this.AutoComplete.onblur();
}

AutoComplete.prototype.onblur = function()
{
	this.oDiv.style.visibility = "hidden";
}

AutoComplete.prototype.onTextChange = function()
{
	this.AutoComplete.onchange();
}

AutoComplete.prototype.onDivMouseDown = function()
{
	this.AutoComplete.oText.value = this.innerHTML;
}

AutoComplete.prototype.onDivMouseOver = function()
{
	this.className = "AutoCompleteHighlight";
}

AutoComplete.prototype.onDivMouseOut = function()
{
	this.className = "AutoCompleteBackground";
}

AutoComplete.prototype.onchange = function()
{
	var txt = this.oText.value;
	
	// count the number of strings that match the text-box value
	var nCount = this.db.getCount(txt, true);
	
	// if a suitable number then show the popup-div
	if ( (this.nMaxSize == -1 ) || ((nCount < this.nMaxSize) && (nCount > 0)) )
	{
		// clear the popup-div.
		while ( this.oDiv.hasChildNodes() )
			this.oDiv.removeChild(this.oDiv.firstChild);
			
		// get all the matching strings from the AutoCompleteDB
		var aStr = new Array();
		this.db.getStrings(txt, "", aStr);
		
		// add each string to the popup-div
		var i, n = aStr.length;
		for ( i = 0; i < n; i++ )
		{
			var oDiv = document.createElement('div');
			this.oDiv.appendChild(oDiv);
			oDiv.innerHTML = aStr[i];
			oDiv.onmousedown = AutoComplete.prototype.onDivMouseDown;
			oDiv.onmouseover = AutoComplete.prototype.onDivMouseOver;
			oDiv.onmouseout = AutoComplete.prototype.onDivMouseOut;
			oDiv.AutoComplete = this;			
		}
		this.oDiv.style.visibility = "visible";
	}
	else // hide the popup-div
	{
		this.oDiv.innerHTML = "";
		this.oDiv.style.visibility = "hidden";
	}
}

function createAutoComplete()
{
	var aNames =
	[
	   "Judging in a Government by Consent", "Keeping Life Human: Science, Religion, and the Soul", "Europe and America: Yesterday, Today, and Tomorrow", 
	"What Colleges Forget to Teach", "Western Warfare in the Postmodern Age", "Slow Undoing: What is at Stake in the Assault on Nationality", "Balance of Power That Favors Freedom", 
	"New Double Consciousness: Prospectives for the New Black Ideology", "Life, Liberty, and the Pursuit of Happiness", "Political Principles of the Telecosm", 
	"Equality and Justice versus Freedom", "On Interpreting the Constitution", "Czech Republic and Europe at the Turn of the Century", 
	"Culture Wars In Perspective", "From Welfare Reform To Character Development", "America's Cities: Can We Save Them?", "Where the Hope Is", "Why Government Is the Problem", "Our Universal Civilization", 
	"Publishing Revolution: A View from the Inside", "Fact and Fiction in the New York of the Eighties", "The Technological Vision", "Can Genes Explain Our Politics", "Christians, Jews & Israel", "War and the Mass Media", 
	"Why Is America More Religious than Europe?", "Can Muslim Nations Acquire Liberal Democracies?", "Who Becomes a Terrorist?", "Religion and Freedom", "Why Is Marriage in Trouble?", "Making Justice Swifter", 
	"Public Policy and the Media: Do We Get the Whole Story?", "Why Is Any Nation a Democracy?", "Topic: Connections Among Television, Guns and Violence", "Hayek vs. The Development Experts", "Hayek on Spontaneous Order and the Mirage of Social Justice", 
	"Road to Serfdom Revisited", "Islam Tests Democracy", "Project FDA", "City Journal", "Urban Innovator Award", "Social Entrepreneurship Award", "Hayek Lecture", "Wilson Lecture", "Wriston Lecture", "Hamilton Award", 
     "Alexander Hamilton Award", "Brian Anderson", "Anderson", "John Avlon", "Avlon", "Herman Badillo", "Badillo", "Hope Cohen", "Cohen", "James Copland", "Copland", "Theodore Dalrymple",  "Dalrymple", "Richard Epstein", "Epstein", "Diana Furchtgott-Roth", "Furchtgott-Roth", "Nicole Gelinas", "Gelinas", "Edward Glaeser", 
      "Glaeser", "David Gratzer", "Gratzer", "Jay P Greene", "Greene", "Richard Greenwald", "Greenwald", "Marie Gryphon", "Gryphon", "Regina Herzlinger", "Herzlinger", "Stephanie Hessler", "Hessler", "Paul Howard", "Howard", "Peter Huber", "Huber", "Howard Husock", "Husock", "Kay Hymowitz", "Hymowitz", 
       "Stefan Kanfer", "Kanfer", "George Kelling", "Kelling", "Andrew Klavan", "Klavan", "John Leo", "Leo", "Heather Mac Donald", "Mac Donald", "Myron Magnet", "Magnet", 
       "Steve Malanga", "Malanga", "James Manzi", "Manzi", "Edmund J McMahon", "McMahon", "John McWhorter", "McWhorter", "Judith Miller", "Miller", "Walter Olson", "Olson", "James Piereson", "Piereson", "Peter Salins", "Salins", "Max Schulz", 
       "Schulz", "Fred Siegel", "Siegel", "Guy Sorman", "Sorman",  "Harry Stein", "Stein", "Sol Stern", "William Stern", "Stern", "Thomas Stossel", "Stossel", "Julia Vitullo-Martin", "Vitullo-Martin", "Marcus Winters", "Winters", "Economics Does Not Lie", 
       "Not with a Bang But a Whimper", "Manifesto for Media Freedom", "All About the Beat", "Empire of Lies", "Immigration Solution", "Democratic Capitalism and Its Discontents", "Who Killed Health Care?", "One Nation, One Standard", "Marriage and Caste in America", "The Cure", 
        "Winning the Race", "Romancing Opiates", "Education Myths", "New New Left", "Our Culture, What's Left of It", "South Park Conservatives", "Government 2.0", "Bottomless Well", 
        "Consumer-Driven Health Care", "Reinventing the Melting Pot", "Breaking Free", "Are Cops Racist?", "Authentically Black", "Rule of Lawyers", "Democracy by Decree", "Liberation's Children", 
        "No Excuses", "America's Trillion-Dollar Housing Mistake", "Beyond the Color Line", "By Their Bootstraps", "Life at the Bottom", "Modern Sex", "Coloring the News", "Burden of Bad Ideas", 
        "What Makes Charity Work?", "Millennial City", "How We Got Here", "Hard Green",  "Ready or Not", "Entrepreneurial City", "Someone Else's House", "Twenty-First Century City", 
        "America in Black and White", "Excuse Factory", "Excuse Factory", "Judging Science", "Law and Disorder in Cyberspace", "Fixing Broken Windows", "Assimilation, American Style", "Orwell's Revenge", 
        "Miracle in East Harlem", "Phantom Risk", "Dream and the Nightmare", "Dream and the Nightmare", "Second Thoughts", "Scarcity by Design", "Twilight of Sovereignty", "Out of the Barrio", "Galileo's Revenge", 
        "Litigation Explosion", "Health, Lifestyle and Environment", "Growth Experiment", "Free Banking and Monetary Reform", "New York Unbound", "In Pursuit Of Happiness and Good Government", 
        "Liability Legal Revolution and Its Consequences", "New Directions in Liability Law", "Privatization The Key to Better Government", "How NATO Weakens the West", 
        "From Adam Smith to the Wealth of America", "Rise and Fall of New York City", "Losing Ground American Social Policy 1950-1980", "Secrets of the Tax Revolt", "Power and Privilege Labor Unions in America", 
        "Supply-Side Solution", "State Against Blacks", "Regulation by Prosecution", "Economy in Mind", "Development Without Aid", "Privatizing the Public Sector", "Governing of Agriculture", 
        "Markets and Minorities", "Ecology of Housing Destruction", "Wealth and Poverty", "U.S. Balance of Payments and the Sinking Dollar", "New Protectionism", "How Much Are Public School Teachers Paid?", 
        "NYC Teacher Pay-for-Performance Program Early Evidence from a Randomized Trial", "Grading New York An Evaluation of New York City's Progress Reports Program", 
        "Building on the Basics The Impact of High-Stakes Testing on Student Proficiency in Low- Stakes Subjects", "Measuring Immigrant Assimilation in the United States", 
        "Effect of Special Education Vouchers on Public School Achievement Evidence", "What's in a Name? The Decline in The Civic Mission of School Names", "Getting Farther Ahead by Staying Behind A Second-Year Evaluation of Florida's Policy to end Social Promotion", 
         "Leaving Boys Behind Public High School Graduation Rates", 
        "Pricing the 'Luxury Product' New York City Taxes Under Mayor Bloomberg", "Mayor Bloomberg & The Limits of Pragmatism", "Cost of Their Intentions 2005", "Child Poverty and Welfare Reform Stay the Course", 
         "36 Billion Bonus New York's Gains from Federal Tax Cuts", "No Strings Attached? Ensuring that 'CFE' Funds are Spent Effectively", "Private Competition for Public Services Unfinished Agenda in New York State", 
        "Defusing the Pension Bomb", "Why Is Manhattan So Expensive?", "Vouchers for Special Education Students", "Rent Control and Housing Investment", "What Parents Think of New York's Charter Schools", "Gaining Ground, Moving Up", 
        "Testing High Stakes Tests", "Who Really Benefits from New York City's Rent Regulation System?", "Effects of Funding Incentives on Special Education Enrollment", 
        "Public School Graduation Rates in the United States", "Competitive Contracting of Bus Services", "Deja Vu All Over Again", "What Do Teachers Teach?", "High School Graduation Rates in Washington State", 
        "Show Me the Money", "Do Police Matter?", "State of the New York City Public Schools 2002", "New York City's Housing Gap Revisited", "2001 Education Freedom Index", 
        "Tax-and-Spend, Boom-and-Bust", "High School Graduation Rates in the United States", "Cost of Their Intentions", "What New York Has Gained From Tax Cuts", 
         "New York's Savings from the New Tax Law", "Gaining Ground?", "Tip of the Iceberg", "An Evaluation of the Florida A-Plus Accountability", "Campaign 2000 Tax Proposals", "Education Freedom Index", 
         "Effect of School Choice", "State of the New York City Public Schools", "Survey of Results from Voucher Experiments", "Transforming Probation Through Leadership", 
        "Does Charter School Competition Improve Traditional Public Schools?", "School Finance Reform", "Right-Sizing Justice", "Broken Windows Probation", "New York City's Housing Gap", 
        "New York City Teachers' Union Contract", "Debt & New York's Public Authorities", 
        "Whitman Tax Cuts", "What's Working?", "Politics and Public Pension Funds", "Effects of Rent Deregulation in Massachusetts", "New Jersey Income Tax Cut Led to Savings, Not Rise in Local Taxes", 
         "A Proposal to Expand Consumer Choice and Economic Opportunities", "Faith-based Outreach to At-Risk Youth in Washington, D.C.", "Living Faith The Black Church Outreach Tradition", 
         "Religion The Forgotten Factor in Cutting Youth Crime and Saving At-Risk Urban Youth", "Greater Justice, Lower Cost How a 'Loser Pays' Rule Would Improve the American Legal System", 
         "Medical Malpractice Awards, Insurance, and Negligence Which Are Related?", "What We Know and What We Don't Know about Modern Class Actions", "One Small Step for a County Court One Giant Calamity for the National Legal System", 
         "Anatomy of a Madison County Class Actions A Study of Pathology", "Class Action Magnet Courts The Allure Intensifies", "Class Actions The Need for a Hard Second Look", 
         "They're Making a Federal Case Out of It In State Court", "Reflections of a Survivor of State Judicial Election Warfare", "New American Rule A First Amendment to the Client's Bill of Rights", 
         "Forging a New Plan For Health Care Principles and Priorities for Sustainable Reform", "HSA Health-Insurance Plans After Four Years What Have We Learned?", 
         "Alive and Working How Access to New Drugs has Slowed the Growth in America's Disability Rates", "Truth About Drug Innovation Thirty-Five Summary Case Histories on Private Sector Contributions to Pharmaceutical Science", 
         "Comparing Public and Private Health Insurance Would a Single-Payer System Save Enough to Cover the Uninsured?", "Why Has Longevity Increased More in Some States than in Others?", 
         "Human Cost of Federal Price Negotiations The Medicare Prescription Drug Benefit", "Prescription for Progress The Critical Path To Drug Development", 
         "Older Drugs, Shorter Lives?", "Are Drug Price Controls Good for Your Health?", "Neighborly Substation", "Raise the Roof, Lower the Costs Construction Costs and Housing Affordability in New York City", 
         "Rethinking Environmental Review A Handbook on What Can Be Done", "Battling Traffic What New Yorkers Think About Road Pricing", "Up From the Ruins Why Rezoning New York City's Manufacturing Areas for Housing Makes Sense", 
         "New York City's Housing Gap The Road to Recovery", "Transit Security", "Million-Volt Answer to Oil", "New Paradigm? Merging Law Enforcement and Counterterrorism Strategies", "Policing Terrorism in the United States", 
          "Problem-Solving Principles for Local Police", "How Police Fight Terrorism in the United Kingdom", "Firefighters' Developing Role in Counterterrorism", "State Fusion Center Processes and Procedures Best Practices and Recommendations", 
          "Convergence of Crime and Terror Law Enforcement Opportunities and Perils", "Energy & the Environment Myths & Facts", "Energy Policy & the Environment Report April 2009", "Taxing Energy in the United States Which Fuels Does the Tax Code Favor?", 
          "Nuclear Power The Investment Outlook", "Energy and the Environment Myths and Facts", "Rx NY A Prescription for More Accessible Health Care in NY", "Taylor Made The Cost and Consequences of New York's Public-Sector Labor Laws", 
          "NY Unplugged? Building Energy Capacity and Curbing Energy Rates in the Empire State", "Defusing New York's Pension Bomb", "Taxing and Spending in the Empire State Overview of the 2006-07 Executive Budget", 
          "Ready for Change A Statewide New York Voter Survey", "Taxes and Consequences The Gotham STAMP 2006 Computable General Equilibrium Model", "Helping Kids, Saving Money How to Reform New York's Special Education System", 
          "Another Middle-Class Tax? How the Federal AMT Hits New Yorkers", "What Works Comparing the Effectiveness of Welfare-to-Work Programs in Los Angeles", 
          "InnerChange Freedom Initiative A Preliminary Evaluation of a Faith-Based Prison Program", "Working Faith How Religious Organizations Provide Welfare-to-Work Services", 
           "Objective Hope Assessing the Effectiveness of Faith-Based Organizations A Review of the Literature", "Good Dads Religion, Civic Engagement, Paternal Involvement in Low-Income Communitites", 
          "Role of African-American Churches in Reducing Crime Among Black Youth", "Better Kind of High How Religious Commitment Reduces Drug Use Among Poor Urban Teens", 
          "Preventing Crime, Saving Children Monitoring, Mentoring & Ministering", "State of Violent Crime in America", "Moving Men into the Mainstream Best Practices in Prisoner Reentry Assistance", 
          "You Say Tomato, I Say Tomato", "Science of Reading Instruction and No Child Left Behind", "Building Support Systems to Reduce Recidivism", "Preserving Affordable Housing", 
          "Moving Men into the Mainstream", "Policing Terrorism", "Making Cities Skilled", "Pre-K Shaping the System That Shapes Children", "Iowa Charter Agencies Streamlining State Government", 
          "Going to Scale A New Era for Funding Nonprofits", "Do Charter Schools Help Their Students?", "Miami Renaissance A Road Map for Urban Leadership", "This Works Crime Prevention and the Future of Broken Windows Policing", 
          "This Works Expanding Urban Housing, This Works Improving Urban Education", "This Works Encouraging Economic Growth, This Works Preventing and Reducing Crime", 
          "This Works Managing City Finances", "Cost of Good Intentions", "Unleashing the Private Sector How Government Policy Can Facilitate Private Solutions", 
           "America Works' Criminal Justice Program Providing Second Chances Through Work", "Rising to the Challenge The Effect of School Choice on Public Schools in Milwaukee and San Antonio", 
            "New York City's Public Schools The Facts About Spending and Performance", "School Choice and Government Reform Pillars of Urban Renaissance", "Making Welfare to Work Fly", 
          "Charter Schools in New York A New Era", "Achievement and Opportunity Keys to Quality Education", "Neighborhood Guidance Offices A New Model For Helping the Less Fortunate", 
           "Why School Vouchers Can Help Inner City Children", "Transforming American Education", "Transforming America's Cities", "Making America's Cities Great Places To Live", "Saving Public Schools", 
           "Wealth of Cities", "Let's Break Up the Big Cities", "Landmark Preservation For A Growing City", "How To Fix New York's Heavy Handed Zoning Laws", "Fixing the Civil Service Mess", "Help For the Disabled?", 
           "Why It's Time To Abolish County Government", "Stagnation By Regulation The Sad Tale of the Three Family House", "Competition vs. Corruption Reforming New York's Garbage Industry", 
            "How to Make Sure the New Welfare to Work Really Works", "New Hope for Cities", "Why Business Improvement Districts Work", "Is it Time to Let the Private Sector Run Our Airports?", 
            "Taxes, Flat and Otherwise", "Capital Gains A Tax on the Middle Class", "How Government Can Do More With Less Massachusetts Leads the Way", "Tax Code for the Future The Growth Experiment Revisited", 
           "Best Christmas Present Washington Could Give New York", "From the Broad Brush to the Fine Point How to Enable Personalized Medicine", "Eliminating the Suffering and Death Due to Cancer by 2015" 
        
              
	];
	new AutoComplete(
		aNames, 
		document.getElementById('q'), 
		document.getElementById('theDiv'), 
		60
	);
}