samuelclay/radix_trie.js

## radix_trie.js
var RadixTrie = function(words) {
    this.T = {};
    this.initialize(words);
};

RadixTrie.prototype = {

    initialize: function(words) {
        var self = this;
        words = words || [];

        words.forEach(function(word) {
            self.insert(word);
        });
    },

    insert: function(word, T) {
        var self = this;
        var l = word.length;
        var prefix;
        word = word && word.toLowerCase();
        T = T || this.T;

        // Search for existing prefixes
        while (l--) {
            prefix = word.substr(0, l+1);
            if (T[prefix]) {
                // Found prefix, moving into subtrie
                if (!Object.keys(T[prefix]).length) {
                    // If one word is a pure subset of another word, the prefix
                    // should also point to the subset.
                    T[prefix][""] = {};
                }
                return this.insert(word.substr(l+1), T[prefix]);
            }
        }

        // No prefix found means insert word and check for prefix collision
        var siblings = Object.keys(T);
        l = word.length;
        var siblingFound = siblings.some(function(sibling) {
            var s = 0;
            var commonPrefix;

            do {
                if (sibling[s] != word[s]) {
                    if (s > 1) {
                        commonPrefix = sibling.substr(0, s-1);
                    }
                    break;
                }
            } while (s++ < l)

            if (commonPrefix) {
                // Rearrange trie to move word with prefix collision into new
                // common prefix subtrie
                T[commonPrefix] = {};
                self.insert(sibling.substr(s-1), T[commonPrefix]);
                T[commonPrefix][sibling.substr(s-1)] = T[sibling];
                self.insert(word.substr(s-1), T[commonPrefix]);
                delete T[sibling];

                return true;
            }
        });

        // No siblings at this level? New branch.
        if (!siblingFound) {
            T[word] = {};
        }
    },

    lookup: function(word, limit, T, matchedPrefix) {
        limit = limit || 10;
        T = T || this.T;
        matchedPrefix = matchedPrefix || "";
        word = word && word.toLowerCase();
        var self = this;
        var l = word.length;
        var matches = [];

        // Search for existing prefixes and recurseively descend
        while (l--) {
            var prefix = word.substr(0, l+1);
            if (T[prefix]) {
                var suffix = word.substr(l+1);
                return this.lookup(suffix, limit, T[prefix], matchedPrefix + prefix);
            }
        }

        // No prefixes means check siblings on this level
        l = word.length;
        var siblings = Object.keys(T);
        var siblingFound = siblings.some(function(sibling) {
            var s = l;

            // Node parent is full word, so include all children as matches
            if (!s) {
                var nodeMatches = self.names(T[sibling], limit, matchedPrefix + sibling);
                matches = matches.concat(nodeMatches);
            }

            if (matches.length > limit) return true;

            // Check all child prefixes for matches
            while (s--) {
                if (sibling.substr(0, s+1) == word.substr(0, s+1)) {
                    var siblingMatches = self.names(T[sibling], limit, matchedPrefix + sibling);
                    matches = matches.concat(siblingMatches);
                    return true;
                }
            }
        });

        // Match complete word that has no children
        if (!siblings.length && !word.length) {
            matches.push(matchedPrefix);
        }

        if (matches.length > limit) {
            matches = matches.slice(0, limit);
        }

        return matches;
    },

    // Retrieves all words below a node and helpfully adds the provided
    // prefix to each word.
    names: function(T, limit, matchedPrefix) {
        T = T || this.T;
        var self = this;
        var keys = Object.keys(T);
        var matches = [];
        matchedPrefix = matchedPrefix || "";

        // Recursively descend down to fetch all words
        if (keys.length) {
            keys.some(function(key) {
                if (Object.keys(T[key]).length) {
                    var submatches = self.names(T[key], limit, matchedPrefix + key);
                    matches = matches.concat(submatches);
                } else {
                    matches.push(matchedPrefix + key);
                }
                if (matches.length > limit) {
                    return true;
                }
            });
        } else {
            // No children, so just include self
            matches.push(matchedPrefix);
        }

        if (matches.length > limit) {
            matches = matches.slice(0, limit);
        }

        return matches;

    }

};

// Export for node.js
if (typeof module !== 'undefined') {
    module.exports = {
        RadixTrie: RadixTrie
    };
}

window.ProperNames = [
"Aaron", "Adam", "Adlai", "Adrian", "Agatha", "Ahmed", "Ahmet", "Aimee", "Al", "Alain", "Alan",
"Alastair", "Albert", "Alberto", "Alejandro", "Alex", "Alexander", "Alexis", "Alf", "Alfred", "Alison", "Allan",
"Allen", "Alvin", "Amanda", "Amarth", "Amedeo", "Ami", "Amigo", "Amir", "Amos", "Amy", "Anatole",
"Anatoly", "Anderson", "Andre", "Andrea", "Andreas", "Andrew", "Andries", "Andy", "Angela", "Angus", "Anita",
"Ann", "Anna", "Annard", "Anne", "Annie", "Anthony", "Anton", "Antonella", "Antonio", "Antony", "Archie",
"Ariel", "Arlene", "Arne", "Arnold", "Art", "Arthur", "Audrey", "Avery", "Axel", "Barbara", "Barbra",
"Barney", "Barrett", "Barrio", "Barry", "Bart", "Barton", "Bea", "Beckie", "Becky", "Belinda", "Ben",
"Benjamin", "Benson", "Bernard", "Bernie", "Bert", "Bertrand", "Beth", "Betsy", "Betty", "Beverly", "Bill",
"Billie", "Billy", "Bjorne", "Blaine", "Blair", "Blake", "Blayne", "Bob", "Bobbie", "Bobby", "Bonnie",
"Boyce", "Boyd", "Brad", "Bradford", "Bradley", "Brandi", "Brandon", "Brandy", "Brenda", "Brendan", "Brender",
"Brent", "Bret", "Brett", "Brian", "Briggs", "Brodie", "Brooke", "Bruce", "Bruno", "Bryan", "Bryce",
"Bucky", "Bud", "Butler", "Byron", "Caleb", "Calvin", "Carisa", "Carl", "Carlo", "Carlos", "Carol",
"Carole", "Caroline", "Carolyn", "Carsten", "Carter", "Cary", "Case", "Casey", "Casper", "Catherine", "Cathrin",
"Cathryn", "Cathy", "Cecilia", "Celeste", "Celia", "Charleen", "Charlene", "Charles", "Charley", "Charlie", "Chet",
"Chip", "Chris", "Christian", "Christie", "Christina", "Christofer", "Christophe", "Christopher", "Chuck", "Cindie", "Cindy",
"Claire", "Clara", "Clare", "Clarence", "Clarissa", "Clark", "Claude", "Claudia", "Claudio", "Clay", "Clayton",
"Clem", "Cliff", "Clifford", "Clyde", "Cole", "Coleen", "Colin", "Collin", "Connie", "Conrad", "Corey",
"Cory", "Courtney", "Craig", "Cris", "Cristi", "Cristina", "Cristopher", "Curt", "Curtis", "Cynthia", "Cyrus",
"Dale", "Dalton", "Damon", "Damone", "Dan", "Dana", "Dani", "Daniel", "Daniele", "Danielle", "Dannie",
"Danny", "Darci", "Daren", "Darin", "Darrell", "Darren", "Darryl", "Daryl", "Dave", "David", "Dawn",
"Dawson", "Dean", "Deb", "Debbie", "Debi", "Deborah", "Deirdre", "Del", "Delbert", "Denis", "Dennis",
"Derek", "Devon", "Dewey", "Diana", "Diane", "Dick", "Dieter", "Dimetry", "Dimitry", "Dion", "Dirk",
"Dominic", "Dominick", "Don", "Donal", "Donald", "Donn", "Donna", "Donne", "Donnie", "Donovan", "Dori",
"Dorian", "Dorothy", "Dory", "Doug", "Douglas", "Doyle", "Drew", "Duane", "Duke", "Duncan", "Dustin",
"Dwayne", "Dwight", "Dylan", "Earl", "Earle", "Earnie", "Ed", "Eddie", "Eddy", "Edgar", "Edith",
"Edmond", "Edmund", "Eduardo", "Edward", "Edwin", "Eileen", "Elaine", "Eli", "Elias", "Elijah", "Eliot",
"Elisabeth", "Elizabeth", "Ellen", "Elliot", "Elliott", "Elric", "Elsa", "Elvis", "Elwood", "Emil", "Emily",
"Emma", "Emmett", "Eric", "Erick", "Erik", "Ernest", "Ernie", "Ernst", "Erwin", "Ethan", "Eugene",
"Eva", "Evan", "Evelyn", "Everett", "Farouk", "Fay", "Felix", "Fletcher", "Floria", "Florian", "Floyd",
"Frances", "Francis", "Francisco", "Francois", "Frank", "Franklin", "Fred", "Frederic", "Frederick", "Fritz", "Gabriel",
"Gail", "Gale", "Galen", "Gary", "Gene", "Geoff", "Geoffrey", "George", "Gerald", "Gerard", "Gideon",
"Gigi", "Gil", "Giles", "Gill", "Gilles", "Ginny", "Giovanni", "Glen", "Glenn", "Glynn", "Gordon",
"Grace", "Graeme", "Graham", "Grant", "Granville", "Greg", "Gregg", "Gregge", "Gregor", "Gregory", "Gretchen",
"Griff", "Guido", "Guillermo", "Gunnar", "Gunter", "Guy", "Gypsy", "Hal", "Hamilton", "Hank", "Hans",
"Harmon", "Harold", "Harris", "Harry", "Hartmann", "Harv", "Harvey", "Hazel", "Heather", "Hector", "Heidi",
"Hein", "Heinrich", "Heinz", "Helen", "Helge", "Henry", "Herb", "Herbert", "Herman", "Herve", "Hienz",
"Hilda", "Hillary", "Hillel", "Himawan", "Hirofumi", "Hirotoshi", "Hiroyuki", "Hitoshi", "Hohn", "Holly", "Hon",
"Honzo", "Horst", "Hotta", "Howard", "Hsi", "Hsuan", "Huashi", "Hubert", "Huey", "Hugh", "Hughes",
"Hui", "Hume", "Hunter", "Hurf", "Hwa", "Hy", "Ian", "Ilya", "Ima", "Indra", "Ira",
"Irfan", "Irvin", "Irving", "Irwin", "Isaac", "Isabelle", "Isidore", "Israel", "Izchak", "Izumi", "Izzy",
"Jack", "Jackye", "Jacob", "Jacobson", "Jacques", "Jagath", "Jaime", "Jakob", "James", "Jamie", "Jan",
"Jane", "Janet", "Janice", "Janos", "Jared", "Jarl", "Jarmo", "Jarvis", "Jason", "Jay", "Jayant",
"Jayesh", "Jean", "Jean-Christophe", "Jean-Pierre", "Jeanette", "Jeanne", "Jeannette", "Jeannie", "Jeany", "Jef", "Jeff",
"Jeffery", "Jeffie", "Jeffrey", "Jelske", "Jem", "Jenine", "Jennie", "Jennifer", "Jerald", "Jeremy", "Jerome",
"Jerrie", "Jerry", "Jesper", "Jess", "Jesse", "Jesus", "Ji", "Jianyun", "Jill", "Jim", "Jimmy",
"Jin", "Jinchao", "Jingbai", "Jinny", "Jiri", "Jisheng", "Jitendra", "Joachim", "Joanne", "Jochen", "Jock",
"Joe", "Joel", "Johan", "Johann", "John", "Johnathan", "Johnnie", "Johnny", "Jon", "Jonathan", "Jones",
"Jong", "Joni", "Joon", "Jordan", "Jorge", "Jos", "Jose", "Joseph", "Josh", "Joshua", "Josip",
"Joubert", "Joyce", "Juan", "Judge", "Judith", "Judy", "Juergen", "Juha", "Julia", "Julian", "Juliane",
"Julianto", "Julie", "Juliet", "Julius", "Jun", "June", "Jurevis", "Juri", "Jussi", "Justin", "Jwahar",
"Kaj", "Kamel", "Kamiya", "Kanthan", "Karen", "Kari", "Karl", "Kate", "Kathleen", "Kathryn", "Kathy",
"Kay", "Kayvan", "Kazuhiro", "Kee", "Kees", "Keith", "Kelly", "Kelvin", "Kemal", "Ken", "Kenn",
"Kenneth", "Kent", "Kenton", "Kerri", "Kerry", "Kevan", "Kevin", "Kevyn", "Kieran", "Kiki", "Kikki",
"Kim", "Kimberly", "Kimmo", "Kinch", "King", "Kirk", "Kirsten", "Kit", "Kitty", "Klaudia", "Klaus",
"Knapper", "Knudsen", "Knut", "Knute", "Kolkka", "Konrad", "Konstantinos", "Kory", "Kris", "Kristen", "Kristi",
"Kristian", "Kristin", "Kriton", "Krzysztof", "Kuldip", "Kurt", "Kusum", "Kyle", "Kylo", "Kyu", "Kyung",
"Lana", "Lance", "Lanny", "Lar", "Larry", "Lars", "Laura", "Laurel", "Laurence", "Laurent", "Laurianne",
"Laurie", "Lawrence", "Lea", "Leads", "Lee", "Leif", "Leigh", "Leila", "Leith", "Len", "Lenny",
"Lenora", "Leo", "Leon", "Leonard", "Leora", "Les", "Leslie", "Lester", "Leung", "Lewis", "Lex",
"Liber", "Lievaart", "Lila", "Lin", "Linda", "Linder", "Lindsay", "Lindsey", "Linley", "Lisa", "List",
"Liyuan", "Liz", "Liza", "Lloyd", "Lois", "Lonhyn", "Lord", "Loren", "Lorenzo", "Lori", "Lorien",
"Lorraine", "Lou", "Louie", "Louiqa", "Louis", "Louise", "Loukas", "Lowell", "Loyd", "Luc", "Lucifer",
"Lucius", "Lui", "Luis", "Lukas", "Luke", "Lum", "Lyndon", "Lynn", "Lynne", "Lynnette", "Maarten",
"Mac", "Magnus", "Mah", "Mahesh", "Mahmoud", "Major", "Malaclypse", "Malcolm", "Malloy", "Malus", "Manavendra",
"Manjeri", "Mann", "Manny", "Manolis", "Manuel", "Mara", "Marc", "Marcel", "Marci", "Marcia", "Marco",
"Marcos", "Marek", "Margaret", "Margie", "Margot", "Marguerite", "Maria", "Marian", "Marie", "Marilyn", "Mario",
"Marion", "Mariou", "Mark", "Markus", "Marla", "Marlena", "Marnix", "Marsh", "Marsha", "Marshall", "Martha",
"Martin", "Marty", "Martyn", "Marvin", "Mary", "Masanao", "Masanobu", "Mason", "Mat", "Mats", "Matt",
"Matthew", "Matthias", "Matthieu", "Matti", "Maureen", "Maurice", "Max", "Mayo", "Mechael", "Meehan", "Meeks",
"Mehrdad", "Melinda", "Merat", "Merril", "Merton", "Metin", "Micah", "Michael", "Micheal", "Michel", "Michelle",
"Michiel", "Mick", "Mickey", "Micky", "Miek", "Mikael", "Mike", "Mikey", "Miki", "Miles", "Milner",
"Milo", "Miltos", "Miriam", "Miriamne", "Mitch", "Mitchell", "Moe", "Mohammad", "Molly", "Mongo", "Monica",
"Monty", "Moore", "Moran", "Morgan", "Morris", "Morton", "Moses", "Mosur", "Mott", "Murat", "Murph",
"Murray", "Murthy", "Mwa", "Myrick", "Myron", "Mysore", "Nadeem", "Naim", "Nancy", "Nanda", "Naomi",
"Naoto", "Naren", "Narendra", "Naresh", "Nate", "Nathan", "Nathaniel", "Natraj", "Neal", "Ned", "Neil",
"Nelken", "Neville", "Nguyen", "Nhan", "Niall", "Nichael", "Nicholas", "Nici", "Nick", "Nicolas", "Nicolette",
"Nicolo", "Niels", "Nigel", "Nikolai", "Nils", "Ning", "Ninja", "No", "Noam", "Noemi", "Nora",
"Norbert", "Norm", "Norma", "Norman", "Nou", "Novo", "Novorolsky", "Ofer", "Olaf", "Old", "Ole",
"Oleg", "Oliver", "Olivier", "Olof", "Olson", "Omar", "Orville", "Oscar", "Oskar", "Owen", "Ozan",
"Pablo", "Page", "Pam", "Pamela", "Panacea", "Pandora", "Panos", "Pantelis", "Panzer", "Paola", "Part",
"Pascal", "Pat", "Patrice", "Patricia", "Patricio", "Patrick", "Patty", "Paul", "Paula", "Pedro", "Peggy",
"Penny", "Per", "Perry", "Pete", "Peter", "Petr", "Phil", "Philip", "Philippe", "Phill", "Phillip",
"Phiroze", "Pia", "Piercarlo", "Pierce", "Pierette", "Pierre", "Piet", "Piete", "Pieter", "Pilar", "Pilot",
"Pim", "Ping", "Piotr", "Pitawas", "Plastic", "Po", "Polly", "Pontus", "Pradeep", "Prakash", "Pratap",
"Pratapwant", "Pratt", "Pravin", "Presley", "Pria", "Price", "Raanan", "Rabin", "Radek", "Rafael", "Rafik",
"Raghu", "Ragnar", "Rahul", "Raif", "Rainer", "Raj", "Raja", "Rajarshi", "Rajeev", "Rajendra", "Rajesh",
"Rajiv", "Rakhal", "Ralf", "Ralph", "Ram", "Ramadoss", "Raman", "Ramanan", "Ramesh", "Ramiro", "Ramneek",
"Ramon", "Ramsey", "Rand", "Randal", "Randall", "Randell", "Randolph", "Randy", "Ranjit", "Raphael", "Rathnakumar",
"Raul", "Ravi", "Ravindran", "Ravindranath", "Ray", "Rayan", "Raymond", "Real", "Rebecca", "Rees", "Reid",
"Reiner", "Reinhard", "Renu", "Revised", "Rex", "Rhonda", "Ric", "Ricardo", "Rich", "Richard", "Rick",
"Ricky", "Rik", "Ritalynne", "Ritchey", "Ro", "Rob", "Robbin", "Robert", "Roberta", "Roberto", "Robin",
"Rod", "Rodent", "Roderick", "Rodger", "Rodney", "Roger", "Rogue", "Roland", "Rolf", "Rolfe", "Romain",
"Roman", "Ron", "Ronald", "Ronni", "Root", "Ross", "Roxana", "Roxane", "Roxanne", "Roxie", "Roy",
"Rudolf", "Rudolph", "Rudy", "Rupert", "Russ", "Russell", "Rusty", "Ruth", "Saad", "Sabrina", "Saify",
"Saiid", "Sal", "Sally", "Sam", "Samir", "Samuel", "Sanand", "Sanche", "Sandeep", "Sandip", "Sandra",
"Sandy", "Sanford", "Sangho", "Sanity", "Sanjay", "Sanjeev", "Sanjib", "Santa", "Saqib", "Sarah", "Sassan",
"Saul", "Saumya", "Scot", "Scott", "Sean", "Sedat", "Sedovic", "Seenu", "Sehyo", "Sekar", "Serdar",
"Sergeant", "Sergei", "Sergio", "Sergiu", "Seth", "Seymour", "Shadow", "Shahid", "Shai", "Shakil", "Shamim",
"Shane", "Shankar", "Shannon", "Sharada", "Sharan", "Shari", "Sharon", "Shatter", "Shaw", "Shawn", "Shean",
"Sheila", "Shel", "Sherman", "Sherri", "Shirley", "Sho", "Shutoku", "Shuvra", "Shyam", "Sid", "Sidney",
"Siegurd", "Sigurd", "Simon", "Siping", "Sir", "Sjaak", "Sjouke", "Skeeter", "Skef", "Skip", "Slartibartfast",
"Socorrito", "Sofia", "Sofoklis", "Son", "Sonja", "Sonny", "Soohong", "Sorrel", "Space", "Spass", "Spencer",
"Spike", "Spock", "Spudboy", "Spy", "Spyros", "Sri", "Sridhar", "Sridharan", "Srikanth", "Srinivas", "Srinivasan",
"Sriram", "Srivatsan", "Ssi", "Stacey", "Stacy", "Stagger", "Stan", "Stanislaw", "Stanley", "Stanly", "Starbuck",
"Steen", "Stefan", "Stephan", "Stephanie", "Stephe", "Stephen", "Stevan", "Steve", "Steven", "Stewart", "Straka",
"Stu", "Stuart", "Subra", "Sue", "Sugih", "Sumitro", "Sundar", "Sundaresan", "Sunil", "Suresh", "Surya",
"Susan", "Susanne", "Susumu", "Suu", "Suwandi", "Suyog", "Suzan", "Suzanne", "Svante", "Swamy", "Syd",
"Syed", "Sylvan", "Syun", "Tad", "Tahsin", "Tai", "Tait", "Takao", "Takayuki", "Takeuchi", "Tal",
"Tammy", "Tanaka", "Tandy", "Tanya", "Tao", "Tareq", "Tarmi", "Taurus", "Ted", "Teresa", "Teri",
"Teriann", "Terrance", "Terrence", "Terri", "Terry", "Teruyuki", "Thad", "Tharen", "The", "Theo", "Theodore",
"Thierry", "Think", "Thomas", "Those", "Thuan", "Ti", "Tiefenthal", "Tigger", "Tim", "Timo", "Timothy",
"Tobias", "Toby", "Todd", "Toerless", "Toft", "Tolerant", "Tollefsen", "Tom", "Tomas", "Tommy", "Tony",
"Tor", "Torsten", "Toufic", "Tovah", "Tracey", "Tracy", "Tran", "Travis", "Trent", "Trevor", "Trey",
"Triantaphyllos", "Tricia", "Troy", "Trying", "Tuan", "Tuna", "Turkeer", "Tyler", "Uri", "Urs", "Vadim",
"Val", "Valentin", "Valeria", "Valerie", "Van", "Vance", "Varda", "Vassos", "Vaughn", "Venkata", "Vern",
"Vernon", "Vic", "Vice", "Vick", "Vicki", "Vickie", "Vicky", "Victor", "Victoria", "Vidhyanath", "Vijay",
"Vilhelm", "Vince", "Vincent", "Vincenzo", "Vinod", "Vishal", "Vistlik", "Vivek", "Vladimir", "Vladislav", "Wade",
"Walt", "Walter", "Warren", "Wayne", "Wendell", "Wendi", "Wendy", "Werner", "Wes", "Will", "William",
"Willie", "Wilmer", "Wilson", "Win", "Winnie", "Winston", "Wolf", "Wolfgang", "Woody", "Yvonne"
];


$(document).ready(function() {
    var trie = new RadixTrie(window.ProperNames);

    $( "input" ).autocomplete({
        source: function(req, resp) {
            console.log(["Lookup", req.term, trie.lookup(req.term)]);
            resp(trie.lookup(req.term));
        }
    });
});
	var RadixTrie = function(words) {
	this.T = {};
	this.initialize(words);
	};

	RadixTrie.prototype = {

	initialize: function(words) {
	var self = this;
	words = words \|\| [];

	words.forEach(function(word) {
	self.insert(word);
	});
	},

	insert: function(word, T) {
	var self = this;
	var l = word.length;
	var prefix;
	word = word && word.toLowerCase();
	T = T \|\| this.T;

	// Search for existing prefixes
	while (l--) {
	prefix = word.substr(0, l+1);
	if (T[prefix]) {
	// Found prefix, moving into subtrie
	if (!Object.keys(T[prefix]).length) {
	// If one word is a pure subset of another word, the prefix
	// should also point to the subset.
	T[prefix][""] = {};
	}
	return this.insert(word.substr(l+1), T[prefix]);
	}
	}

	// No prefix found means insert word and check for prefix collision
	var siblings = Object.keys(T);
	l = word.length;
	var siblingFound = siblings.some(function(sibling) {
	var s = 0;
	var commonPrefix;

	do {
	if (sibling[s] != word[s]) {
	if (s > 1) {
	commonPrefix = sibling.substr(0, s-1);
	}
	break;
	}
	} while (s++ < l)

	if (commonPrefix) {
	// Rearrange trie to move word with prefix collision into new
	// common prefix subtrie
	T[commonPrefix] = {};
	self.insert(sibling.substr(s-1), T[commonPrefix]);
	T[commonPrefix][sibling.substr(s-1)] = T[sibling];
	self.insert(word.substr(s-1), T[commonPrefix]);
	delete T[sibling];

	return true;
	}
	});

	// No siblings at this level? New branch.
	if (!siblingFound) {
	T[word] = {};
	}
	},

	lookup: function(word, limit, T, matchedPrefix) {
	limit = limit \|\| 10;
	T = T \|\| this.T;
	matchedPrefix = matchedPrefix \|\| "";
	word = word && word.toLowerCase();
	var self = this;
	var l = word.length;
	var matches = [];

	// Search for existing prefixes and recurseively descend
	while (l--) {
	var prefix = word.substr(0, l+1);
	if (T[prefix]) {
	var suffix = word.substr(l+1);
	return this.lookup(suffix, limit, T[prefix], matchedPrefix + prefix);
	}
	}

	// No prefixes means check siblings on this level
	l = word.length;
	var siblings = Object.keys(T);
	var siblingFound = siblings.some(function(sibling) {
	var s = l;

	// Node parent is full word, so include all children as matches
	if (!s) {
	var nodeMatches = self.names(T[sibling], limit, matchedPrefix + sibling);
	matches = matches.concat(nodeMatches);
	}

	if (matches.length > limit) return true;

	// Check all child prefixes for matches
	while (s--) {
	if (sibling.substr(0, s+1) == word.substr(0, s+1)) {
	var siblingMatches = self.names(T[sibling], limit, matchedPrefix + sibling);
	matches = matches.concat(siblingMatches);
	return true;
	}
	}
	});

	// Match complete word that has no children
	if (!siblings.length && !word.length) {
	matches.push(matchedPrefix);
	}

	if (matches.length > limit) {
	matches = matches.slice(0, limit);
	}

	return matches;
	},

	// Retrieves all words below a node and helpfully adds the provided
	// prefix to each word.
	names: function(T, limit, matchedPrefix) {
	T = T \|\| this.T;
	var self = this;
	var keys = Object.keys(T);
	var matches = [];
	matchedPrefix = matchedPrefix \|\| "";

	// Recursively descend down to fetch all words
	if (keys.length) {
	keys.some(function(key) {
	if (Object.keys(T[key]).length) {
	var submatches = self.names(T[key], limit, matchedPrefix + key);
	matches = matches.concat(submatches);
	} else {
	matches.push(matchedPrefix + key);
	}
	if (matches.length > limit) {
	return true;
	}
	});
	} else {
	// No children, so just include self
	matches.push(matchedPrefix);
	}

	if (matches.length > limit) {
	matches = matches.slice(0, limit);
	}

	return matches;

	}

	};

	// Export for node.js
	if (typeof module !== 'undefined') {
	module.exports = {
	RadixTrie: RadixTrie
	};
	}

	window.ProperNames = [
	"Aaron", "Adam", "Adlai", "Adrian", "Agatha", "Ahmed", "Ahmet", "Aimee", "Al", "Alain", "Alan",
	"Alastair", "Albert", "Alberto", "Alejandro", "Alex", "Alexander", "Alexis", "Alf", "Alfred", "Alison", "Allan",
	"Allen", "Alvin", "Amanda", "Amarth", "Amedeo", "Ami", "Amigo", "Amir", "Amos", "Amy", "Anatole",
	"Anatoly", "Anderson", "Andre", "Andrea", "Andreas", "Andrew", "Andries", "Andy", "Angela", "Angus", "Anita",
	"Ann", "Anna", "Annard", "Anne", "Annie", "Anthony", "Anton", "Antonella", "Antonio", "Antony", "Archie",
	"Ariel", "Arlene", "Arne", "Arnold", "Art", "Arthur", "Audrey", "Avery", "Axel", "Barbara", "Barbra",
	"Barney", "Barrett", "Barrio", "Barry", "Bart", "Barton", "Bea", "Beckie", "Becky", "Belinda", "Ben",
	"Benjamin", "Benson", "Bernard", "Bernie", "Bert", "Bertrand", "Beth", "Betsy", "Betty", "Beverly", "Bill",
	"Billie", "Billy", "Bjorne", "Blaine", "Blair", "Blake", "Blayne", "Bob", "Bobbie", "Bobby", "Bonnie",
	"Boyce", "Boyd", "Brad", "Bradford", "Bradley", "Brandi", "Brandon", "Brandy", "Brenda", "Brendan", "Brender",
	"Brent", "Bret", "Brett", "Brian", "Briggs", "Brodie", "Brooke", "Bruce", "Bruno", "Bryan", "Bryce",
	"Bucky", "Bud", "Butler", "Byron", "Caleb", "Calvin", "Carisa", "Carl", "Carlo", "Carlos", "Carol",
	"Carole", "Caroline", "Carolyn", "Carsten", "Carter", "Cary", "Case", "Casey", "Casper", "Catherine", "Cathrin",
	"Cathryn", "Cathy", "Cecilia", "Celeste", "Celia", "Charleen", "Charlene", "Charles", "Charley", "Charlie", "Chet",
	"Chip", "Chris", "Christian", "Christie", "Christina", "Christofer", "Christophe", "Christopher", "Chuck", "Cindie", "Cindy",
	"Claire", "Clara", "Clare", "Clarence", "Clarissa", "Clark", "Claude", "Claudia", "Claudio", "Clay", "Clayton",
	"Clem", "Cliff", "Clifford", "Clyde", "Cole", "Coleen", "Colin", "Collin", "Connie", "Conrad", "Corey",
	"Cory", "Courtney", "Craig", "Cris", "Cristi", "Cristina", "Cristopher", "Curt", "Curtis", "Cynthia", "Cyrus",
	"Dale", "Dalton", "Damon", "Damone", "Dan", "Dana", "Dani", "Daniel", "Daniele", "Danielle", "Dannie",
	"Danny", "Darci", "Daren", "Darin", "Darrell", "Darren", "Darryl", "Daryl", "Dave", "David", "Dawn",
	"Dawson", "Dean", "Deb", "Debbie", "Debi", "Deborah", "Deirdre", "Del", "Delbert", "Denis", "Dennis",
	"Derek", "Devon", "Dewey", "Diana", "Diane", "Dick", "Dieter", "Dimetry", "Dimitry", "Dion", "Dirk",
	"Dominic", "Dominick", "Don", "Donal", "Donald", "Donn", "Donna", "Donne", "Donnie", "Donovan", "Dori",
	"Dorian", "Dorothy", "Dory", "Doug", "Douglas", "Doyle", "Drew", "Duane", "Duke", "Duncan", "Dustin",
	"Dwayne", "Dwight", "Dylan", "Earl", "Earle", "Earnie", "Ed", "Eddie", "Eddy", "Edgar", "Edith",
	"Edmond", "Edmund", "Eduardo", "Edward", "Edwin", "Eileen", "Elaine", "Eli", "Elias", "Elijah", "Eliot",
	"Elisabeth", "Elizabeth", "Ellen", "Elliot", "Elliott", "Elric", "Elsa", "Elvis", "Elwood", "Emil", "Emily",
	"Emma", "Emmett", "Eric", "Erick", "Erik", "Ernest", "Ernie", "Ernst", "Erwin", "Ethan", "Eugene",
	"Eva", "Evan", "Evelyn", "Everett", "Farouk", "Fay", "Felix", "Fletcher", "Floria", "Florian", "Floyd",
	"Frances", "Francis", "Francisco", "Francois", "Frank", "Franklin", "Fred", "Frederic", "Frederick", "Fritz", "Gabriel",
	"Gail", "Gale", "Galen", "Gary", "Gene", "Geoff", "Geoffrey", "George", "Gerald", "Gerard", "Gideon",
	"Gigi", "Gil", "Giles", "Gill", "Gilles", "Ginny", "Giovanni", "Glen", "Glenn", "Glynn", "Gordon",
	"Grace", "Graeme", "Graham", "Grant", "Granville", "Greg", "Gregg", "Gregge", "Gregor", "Gregory", "Gretchen",
	"Griff", "Guido", "Guillermo", "Gunnar", "Gunter", "Guy", "Gypsy", "Hal", "Hamilton", "Hank", "Hans",
	"Harmon", "Harold", "Harris", "Harry", "Hartmann", "Harv", "Harvey", "Hazel", "Heather", "Hector", "Heidi",
	"Hein", "Heinrich", "Heinz", "Helen", "Helge", "Henry", "Herb", "Herbert", "Herman", "Herve", "Hienz",
	"Hilda", "Hillary", "Hillel", "Himawan", "Hirofumi", "Hirotoshi", "Hiroyuki", "Hitoshi", "Hohn", "Holly", "Hon",
	"Honzo", "Horst", "Hotta", "Howard", "Hsi", "Hsuan", "Huashi", "Hubert", "Huey", "Hugh", "Hughes",
	"Hui", "Hume", "Hunter", "Hurf", "Hwa", "Hy", "Ian", "Ilya", "Ima", "Indra", "Ira",
	"Irfan", "Irvin", "Irving", "Irwin", "Isaac", "Isabelle", "Isidore", "Israel", "Izchak", "Izumi", "Izzy",
	"Jack", "Jackye", "Jacob", "Jacobson", "Jacques", "Jagath", "Jaime", "Jakob", "James", "Jamie", "Jan",
	"Jane", "Janet", "Janice", "Janos", "Jared", "Jarl", "Jarmo", "Jarvis", "Jason", "Jay", "Jayant",
	"Jayesh", "Jean", "Jean-Christophe", "Jean-Pierre", "Jeanette", "Jeanne", "Jeannette", "Jeannie", "Jeany", "Jef", "Jeff",
	"Jeffery", "Jeffie", "Jeffrey", "Jelske", "Jem", "Jenine", "Jennie", "Jennifer", "Jerald", "Jeremy", "Jerome",
	"Jerrie", "Jerry", "Jesper", "Jess", "Jesse", "Jesus", "Ji", "Jianyun", "Jill", "Jim", "Jimmy",
	"Jin", "Jinchao", "Jingbai", "Jinny", "Jiri", "Jisheng", "Jitendra", "Joachim", "Joanne", "Jochen", "Jock",
	"Joe", "Joel", "Johan", "Johann", "John", "Johnathan", "Johnnie", "Johnny", "Jon", "Jonathan", "Jones",
	"Jong", "Joni", "Joon", "Jordan", "Jorge", "Jos", "Jose", "Joseph", "Josh", "Joshua", "Josip",
	"Joubert", "Joyce", "Juan", "Judge", "Judith", "Judy", "Juergen", "Juha", "Julia", "Julian", "Juliane",
	"Julianto", "Julie", "Juliet", "Julius", "Jun", "June", "Jurevis", "Juri", "Jussi", "Justin", "Jwahar",
	"Kaj", "Kamel", "Kamiya", "Kanthan", "Karen", "Kari", "Karl", "Kate", "Kathleen", "Kathryn", "Kathy",
	"Kay", "Kayvan", "Kazuhiro", "Kee", "Kees", "Keith", "Kelly", "Kelvin", "Kemal", "Ken", "Kenn",
	"Kenneth", "Kent", "Kenton", "Kerri", "Kerry", "Kevan", "Kevin", "Kevyn", "Kieran", "Kiki", "Kikki",
	"Kim", "Kimberly", "Kimmo", "Kinch", "King", "Kirk", "Kirsten", "Kit", "Kitty", "Klaudia", "Klaus",
	"Knapper", "Knudsen", "Knut", "Knute", "Kolkka", "Konrad", "Konstantinos", "Kory", "Kris", "Kristen", "Kristi",
	"Kristian", "Kristin", "Kriton", "Krzysztof", "Kuldip", "Kurt", "Kusum", "Kyle", "Kylo", "Kyu", "Kyung",
	"Lana", "Lance", "Lanny", "Lar", "Larry", "Lars", "Laura", "Laurel", "Laurence", "Laurent", "Laurianne",
	"Laurie", "Lawrence", "Lea", "Leads", "Lee", "Leif", "Leigh", "Leila", "Leith", "Len", "Lenny",
	"Lenora", "Leo", "Leon", "Leonard", "Leora", "Les", "Leslie", "Lester", "Leung", "Lewis", "Lex",
	"Liber", "Lievaart", "Lila", "Lin", "Linda", "Linder", "Lindsay", "Lindsey", "Linley", "Lisa", "List",
	"Liyuan", "Liz", "Liza", "Lloyd", "Lois", "Lonhyn", "Lord", "Loren", "Lorenzo", "Lori", "Lorien",
	"Lorraine", "Lou", "Louie", "Louiqa", "Louis", "Louise", "Loukas", "Lowell", "Loyd", "Luc", "Lucifer",
	"Lucius", "Lui", "Luis", "Lukas", "Luke", "Lum", "Lyndon", "Lynn", "Lynne", "Lynnette", "Maarten",
	"Mac", "Magnus", "Mah", "Mahesh", "Mahmoud", "Major", "Malaclypse", "Malcolm", "Malloy", "Malus", "Manavendra",
	"Manjeri", "Mann", "Manny", "Manolis", "Manuel", "Mara", "Marc", "Marcel", "Marci", "Marcia", "Marco",
	"Marcos", "Marek", "Margaret", "Margie", "Margot", "Marguerite", "Maria", "Marian", "Marie", "Marilyn", "Mario",
	"Marion", "Mariou", "Mark", "Markus", "Marla", "Marlena", "Marnix", "Marsh", "Marsha", "Marshall", "Martha",
	"Martin", "Marty", "Martyn", "Marvin", "Mary", "Masanao", "Masanobu", "Mason", "Mat", "Mats", "Matt",
	"Matthew", "Matthias", "Matthieu", "Matti", "Maureen", "Maurice", "Max", "Mayo", "Mechael", "Meehan", "Meeks",
	"Mehrdad", "Melinda", "Merat", "Merril", "Merton", "Metin", "Micah", "Michael", "Micheal", "Michel", "Michelle",
	"Michiel", "Mick", "Mickey", "Micky", "Miek", "Mikael", "Mike", "Mikey", "Miki", "Miles", "Milner",
	"Milo", "Miltos", "Miriam", "Miriamne", "Mitch", "Mitchell", "Moe", "Mohammad", "Molly", "Mongo", "Monica",
	"Monty", "Moore", "Moran", "Morgan", "Morris", "Morton", "Moses", "Mosur", "Mott", "Murat", "Murph",
	"Murray", "Murthy", "Mwa", "Myrick", "Myron", "Mysore", "Nadeem", "Naim", "Nancy", "Nanda", "Naomi",
	"Naoto", "Naren", "Narendra", "Naresh", "Nate", "Nathan", "Nathaniel", "Natraj", "Neal", "Ned", "Neil",
	"Nelken", "Neville", "Nguyen", "Nhan", "Niall", "Nichael", "Nicholas", "Nici", "Nick", "Nicolas", "Nicolette",
	"Nicolo", "Niels", "Nigel", "Nikolai", "Nils", "Ning", "Ninja", "No", "Noam", "Noemi", "Nora",
	"Norbert", "Norm", "Norma", "Norman", "Nou", "Novo", "Novorolsky", "Ofer", "Olaf", "Old", "Ole",
	"Oleg", "Oliver", "Olivier", "Olof", "Olson", "Omar", "Orville", "Oscar", "Oskar", "Owen", "Ozan",
	"Pablo", "Page", "Pam", "Pamela", "Panacea", "Pandora", "Panos", "Pantelis", "Panzer", "Paola", "Part",
	"Pascal", "Pat", "Patrice", "Patricia", "Patricio", "Patrick", "Patty", "Paul", "Paula", "Pedro", "Peggy",
	"Penny", "Per", "Perry", "Pete", "Peter", "Petr", "Phil", "Philip", "Philippe", "Phill", "Phillip",
	"Phiroze", "Pia", "Piercarlo", "Pierce", "Pierette", "Pierre", "Piet", "Piete", "Pieter", "Pilar", "Pilot",
	"Pim", "Ping", "Piotr", "Pitawas", "Plastic", "Po", "Polly", "Pontus", "Pradeep", "Prakash", "Pratap",
	"Pratapwant", "Pratt", "Pravin", "Presley", "Pria", "Price", "Raanan", "Rabin", "Radek", "Rafael", "Rafik",
	"Raghu", "Ragnar", "Rahul", "Raif", "Rainer", "Raj", "Raja", "Rajarshi", "Rajeev", "Rajendra", "Rajesh",
	"Rajiv", "Rakhal", "Ralf", "Ralph", "Ram", "Ramadoss", "Raman", "Ramanan", "Ramesh", "Ramiro", "Ramneek",
	"Ramon", "Ramsey", "Rand", "Randal", "Randall", "Randell", "Randolph", "Randy", "Ranjit", "Raphael", "Rathnakumar",
	"Raul", "Ravi", "Ravindran", "Ravindranath", "Ray", "Rayan", "Raymond", "Real", "Rebecca", "Rees", "Reid",
	"Reiner", "Reinhard", "Renu", "Revised", "Rex", "Rhonda", "Ric", "Ricardo", "Rich", "Richard", "Rick",
	"Ricky", "Rik", "Ritalynne", "Ritchey", "Ro", "Rob", "Robbin", "Robert", "Roberta", "Roberto", "Robin",
	"Rod", "Rodent", "Roderick", "Rodger", "Rodney", "Roger", "Rogue", "Roland", "Rolf", "Rolfe", "Romain",
	"Roman", "Ron", "Ronald", "Ronni", "Root", "Ross", "Roxana", "Roxane", "Roxanne", "Roxie", "Roy",
	"Rudolf", "Rudolph", "Rudy", "Rupert", "Russ", "Russell", "Rusty", "Ruth", "Saad", "Sabrina", "Saify",
	"Saiid", "Sal", "Sally", "Sam", "Samir", "Samuel", "Sanand", "Sanche", "Sandeep", "Sandip", "Sandra",
	"Sandy", "Sanford", "Sangho", "Sanity", "Sanjay", "Sanjeev", "Sanjib", "Santa", "Saqib", "Sarah", "Sassan",
	"Saul", "Saumya", "Scot", "Scott", "Sean", "Sedat", "Sedovic", "Seenu", "Sehyo", "Sekar", "Serdar",
	"Sergeant", "Sergei", "Sergio", "Sergiu", "Seth", "Seymour", "Shadow", "Shahid", "Shai", "Shakil", "Shamim",
	"Shane", "Shankar", "Shannon", "Sharada", "Sharan", "Shari", "Sharon", "Shatter", "Shaw", "Shawn", "Shean",
	"Sheila", "Shel", "Sherman", "Sherri", "Shirley", "Sho", "Shutoku", "Shuvra", "Shyam", "Sid", "Sidney",
	"Siegurd", "Sigurd", "Simon", "Siping", "Sir", "Sjaak", "Sjouke", "Skeeter", "Skef", "Skip", "Slartibartfast",
	"Socorrito", "Sofia", "Sofoklis", "Son", "Sonja", "Sonny", "Soohong", "Sorrel", "Space", "Spass", "Spencer",
	"Spike", "Spock", "Spudboy", "Spy", "Spyros", "Sri", "Sridhar", "Sridharan", "Srikanth", "Srinivas", "Srinivasan",
	"Sriram", "Srivatsan", "Ssi", "Stacey", "Stacy", "Stagger", "Stan", "Stanislaw", "Stanley", "Stanly", "Starbuck",
	"Steen", "Stefan", "Stephan", "Stephanie", "Stephe", "Stephen", "Stevan", "Steve", "Steven", "Stewart", "Straka",
	"Stu", "Stuart", "Subra", "Sue", "Sugih", "Sumitro", "Sundar", "Sundaresan", "Sunil", "Suresh", "Surya",
	"Susan", "Susanne", "Susumu", "Suu", "Suwandi", "Suyog", "Suzan", "Suzanne", "Svante", "Swamy", "Syd",
	"Syed", "Sylvan", "Syun", "Tad", "Tahsin", "Tai", "Tait", "Takao", "Takayuki", "Takeuchi", "Tal",
	"Tammy", "Tanaka", "Tandy", "Tanya", "Tao", "Tareq", "Tarmi", "Taurus", "Ted", "Teresa", "Teri",
	"Teriann", "Terrance", "Terrence", "Terri", "Terry", "Teruyuki", "Thad", "Tharen", "The", "Theo", "Theodore",
	"Thierry", "Think", "Thomas", "Those", "Thuan", "Ti", "Tiefenthal", "Tigger", "Tim", "Timo", "Timothy",
	"Tobias", "Toby", "Todd", "Toerless", "Toft", "Tolerant", "Tollefsen", "Tom", "Tomas", "Tommy", "Tony",
	"Tor", "Torsten", "Toufic", "Tovah", "Tracey", "Tracy", "Tran", "Travis", "Trent", "Trevor", "Trey",
	"Triantaphyllos", "Tricia", "Troy", "Trying", "Tuan", "Tuna", "Turkeer", "Tyler", "Uri", "Urs", "Vadim",
	"Val", "Valentin", "Valeria", "Valerie", "Van", "Vance", "Varda", "Vassos", "Vaughn", "Venkata", "Vern",
	"Vernon", "Vic", "Vice", "Vick", "Vicki", "Vickie", "Vicky", "Victor", "Victoria", "Vidhyanath", "Vijay",
	"Vilhelm", "Vince", "Vincent", "Vincenzo", "Vinod", "Vishal", "Vistlik", "Vivek", "Vladimir", "Vladislav", "Wade",
	"Walt", "Walter", "Warren", "Wayne", "Wendell", "Wendi", "Wendy", "Werner", "Wes", "Will", "William",
	"Willie", "Wilmer", "Wilson", "Win", "Winnie", "Winston", "Wolf", "Wolfgang", "Woody", "Yvonne"
	];


	$(document).ready(function() {
	var trie = new RadixTrie(window.ProperNames);

	$( "input" ).autocomplete({
	source: function(req, resp) {
	console.log(["Lookup", req.term, trie.lookup(req.term)]);
	resp(trie.lookup(req.term));
	}
	});
	});