jQuery.autocomplete = function(input, options) {
    // Create a link to self
    var me = this;

    // Create jQuery object for input element
    var $input = jQuery(input).attr("autocomplete", "off");
    var iHeight = 30;

    // Apply inputClass if necessary
    if (options.inputClass) $input.addClass(options.inputClass);

    // Create results
    var results = document.createElement("div");
    // Create jQuery object for results
    var $results = jQuery(results);
    $results.hide().addClass(options.resultsClass).css("position", options.position);
    if( options.width > 0 ) $results.css("width", options.width);

    // Add to body element
    //jQuery("body").append(results);
    jQuery(input).parent().append(results);

    input.autocompleter = me;

    var timeout = null;
    var prev = "";
    var active = -1;
    var cache = {};
    var keyb = false;
    var hasFocus = false;
    var lastKeyPressCode = null;
    var tpl = '';

    // flush cache
    function flushCache(){
        cache = {};
        cache.data = {};
        cache.length = 0;
    };

    // flush cache
    flushCache();

    // if there is a data array supplied
    if( options.data != null ){
        var sFirstChar = "", stMatchSets = {}, row = [];

        // no url was specified, we need to adjust the cache length to make sure it fits the local data store
        if( typeof options.url != "string" ) options.cacheLength = 1;

        // loop through the array and create a lookup structure
        for( var i=0; i < options.data.length; i++ ){
            // if row is a string, make an array otherwise just reference the array
            row = ((typeof options.data[i] == "string") ? [options.data[i]] : options.data[i]);

            // if the length is zero, don't add to list
            if( row[0].length > 0 ){
                // get the first character
                sFirstChar = row[0].substring(0, 1).toLowerCase();
                // if no lookup array for this character exists, look it up now
                if( !stMatchSets[sFirstChar] ) stMatchSets[sFirstChar] = [];
                // if the match is a string
                stMatchSets[sFirstChar].push(row);
            }
        }

        // add the data items to the cache
        for( var k in stMatchSets ){
            // increase the cache size
            options.cacheLength++;
            // add to the cache
            addToCache(k, stMatchSets[k]);
        }
    }

    $input.keydown(function(e) {
        // track last key pressed
        lastKeyPressCode = e.keyCode;
        switch(e.keyCode) {
        case 38: // up
            e.preventDefault();
            showResults();
            moveSelect(-1);
            break;
        case 40: // down
            e.preventDefault();
            showResults();
            moveSelect(1);
            break;
        case 9:      // tab
        case 13: // return
            if (options.showOnReturn) {
                e.preventDefault();
                showResults();
            }else{
                if( selectCurrent() ){
                    // make sure to blur off the current field
                    $input.get(0).blur();
                    e.preventDefault();
                }
            }
            break;
        default:
            active = -1;
            if (timeout) clearTimeout(timeout);
            timeout = setTimeout(function(){onChange();}, options.delay);
            break;
        }
    })
    .focus(function(){
        // track whether the field has focus, we shouldn't process any results if the field no longer has focus
        hasFocus = true;
        if (options.showOnFocus) showResults();
    })
    .blur(function() {
        // track whether the field has focus
        hasFocus = false;
        if (options.hideOnBlur) hideResults();
    });
    jQuery(document).keyup (function (e) {
        if (e.keyCode == 27) {
            var val = $input.val();
            if (val.length>0) {
                $input.val('').focus().addClass(options.emptyClass + " " + options.searchClass);
            } else $input.blur();
        }
    });

    jQuery('.'+options.resetClass).click (function(e){
        $input.val("").focus().addClass(options.emptyClass + " " + options.searchClass);
        $results.hide();
        setTimeout(function(){onChange();}, options.delay);
    });

    hideResultsNow();

    function onChange() {
        // ignore if the following keys are pressed: [del] [shift] [capslock]
        if( lastKeyPressCode == 46 || (lastKeyPressCode > 8 && lastKeyPressCode < 32) ) return $results.hide();
        var v = $input.val();
        // Insert reset button if enabled
        if (options.reset && $input.next('span.'+options.resetClass)) {
            $input.append ("<span class='"+options.resetClass+"'></span>");
        }
        if (v == prev) return;
        prev = v;
        if (v.length >= options.minChars) {
            $input.addClass(options.loadingClass).addClass(options.emptyClass).removeClass(options.searchClass);
            requestData(v);
        } else if (v.length > 0) {
            $input.removeClass(options.loadingClass + " " + options.searchClass + " " + options.emptyClass);
        } else {
            $input.removeClass(options.loadingClass).addClass(options.emptyClass + " " + options.searchClass);
            $results.hide();
        }
    };

    function moveSelect(step) {
        var lis = jQuery("li", results);
        var list = $results;
        // var cats = jQuery("li.ac_cat", results);
        if (!lis) return;

        active += step;
        if (jQuery(lis[active]).hasClass('ac_cat') && (active > 0 && active < lis.size()-1)) active += step;

        if (active <= 0) {
            active = jQuery(lis[active]).hasClass('ac_cat') ? 1 : 0;
            // active = lis.size() - 1;
        } else if (active >= lis.size()-1) {
            active = jQuery(lis[active]).hasClass('ac_cat') ? lis.size() - 2 : lis.size() - 1;
            // active = 0;
        }
        lis.removeClass("ac_over");

        jQuery(lis[active]).addClass("ac_over");

        if(options.scroll) {
            var offset = 0;
            lis.slice(0, active).each(function() {
                offset += this.offsetHeight;
            });
            if((offset + lis[active].offsetHeight - list.scrollTop()) > list[0].clientHeight) {
                list.scrollTop(offset + lis[active].offsetHeight - list.innerHeight());
            } else if(offset < list.scrollTop()) {
                list.scrollTop(offset);
            }
        }

        // Weird behaviour in IE
        // if (lis[active] && lis[active].scrollIntoView) {
        //      lis[active].scrollIntoView(false);
        // }

    };

    function selectCurrent() {
        var li = jQuery("li.ac_over", results)[0];
        if (!li) {
            var $li = jQuery("li", results);
            if (options.selectOnly) {
                if ($li.length == 1) li = $li[0];
            } else if (options.selectFirst) {
                li = $li[0];
            }
        }
        if (li) {
            selectItem(li);
            return true;
        } else {
            return false;
        }
    };

    function selectItem(li) {
        if (!li) {
            li = document.createElement("li");
            li.extra = [];
            li.selectValue = "";
        }
        if (jQuery(li).attr('rel')) {
            document.location.href = jQuery(li).attr('rel');
            return true;
        }
        var v = jQuery.trim(li.selectValue ? li.selectValue : li.innerHTML);
        input.lastSelected = v;
        prev = v;
        $results.html("");
        $input.val(v);
        if (options.hideOnSelect) hideResultsNow();
        if (options.onItemSelect) setTimeout(function() { if (options.target) {options.onItemSelect(li,options.target);}else{ options.onItemSelect(li);} }, 1);
    };

    // selects a portion of the input string
    function createSelection(start, end){
        // get a reference to the input element
        var field = $input.get(0);
        if( field.createTextRange ){
            var selRange = field.createTextRange();
            selRange.collapse(true);
            selRange.moveStart("character", start);
            selRange.moveEnd("character", end);
            selRange.select();
        } else if( field.setSelectionRange ){
            field.setSelectionRange(start, end);
        } else {
            if( field.selectionStart ){
                field.selectionStart = start;
                field.selectionEnd = end;
            }
        }
        field.focus();
    };

    // fills in the input box w/the first match (assumed to be the best match)
    function autoFill(sValue){
        // if the last user key pressed was backspace, don't autofill
        if( lastKeyPressCode != 8 ){
            // fill in the value (keep the case the user has typed)
            $input.val($input.val() + sValue.substring(prev.length));
            // select the portion of the value not typed by the user (so the next character will erase)
            createSelection(prev.length, sValue.length);
        }
    };

    function showResults() {
        if (!loadFromCache($input.val())) return;
        // get the position of the input field right now (in case the DOM is shifted)
        var pos = findPos(input);
        // either use the specified width, or autocalculate based on form element
        var iWidth = (options.width > 0) ? options.width : $input.width();
        var overflow = options.scroll?"auto":"hidden";
        // reposition
        $results.css({
            width: parseInt(iWidth) + "px",
            // top: (pos.y - $results.height()) + "px",
            // bottom: iHeight + "px",
            left: options.left || 0,
            // 'max-height': (window.innerHeight - $input.height()) + "px",
            'overflow-y': overflow
        }).show();
        if (options.direction == 'bottom') {
            $results.css(options.direction, options.bottom || iHeight+"px");
        }else{
            //$results.css(options.direction, (pos.y+$input.outerHeight())+"px");
            $results.css (options.direction, options.top || $input.outerHeight());
        }
        if (options.scroll) {
            var list = jQuery('ul', results);
            if (jQuery.browser.msie){
                var listHeight = 0;
                var listItems = jQuery('li', results);
                listItems.each(function() {
                    if (jQuery(this).not('.ac_cat')) listHeight += this.offsetHeight;
                });
                var scrollbarsVisible = listHeight > document.body.offsetHeight - iHeight;
                $results.css('height', scrollbarsVisible ? document.body.offsetHeight - iHeight : listHeight );
                if (!scrollbarsVisible) {
                    // IE doesn't recalculate width when scrollbar disappears
                    listItems.width( $results.width() - parseInt(listItems.css("padding-left")) - parseInt(listItems.css("padding-right")) );
                }
            } else {
                var listHeight = 0;
                jQuery('li',results).each(function(){
                    if (jQuery(this).not('.ac_cat')) listHeight += this.offsetHeight;
                });
                $results.css({
                    height: (window.innerHeight - iHeight)>listHeight?listHeight:(window.innerHeight-iHeight) + "px",
                    maxHeight: (window.innerHeight - iHeight) + "px"
                });
            }
            //$results.overscroll({direction:'vertical'});
        }
    };

    function hideResults() {
        if (timeout) clearTimeout(timeout);
        timeout = setTimeout(hideResultsNow, 200);
    };

    function hideResultsNow() {
        if (hasFocus) return;
        if (timeout) clearTimeout(timeout);
        $input.removeClass(options.loadingClass);
        if ($results.is(":visible")) {
            $results.hide();
        }
        if (options.mustMatch) {
            var v = $input.val();
            if (v != input.lastSelected) {
                selectItem(null);
            }
        }
    };

    function receiveData(q, data) {
        if (data) {
            $input.removeClass(options.loadingClass).removeClass(options.emptyClass);
            results.innerHTML = "";

            // if the field no longer has focus or if there are no matches, do not display the drop down
            if( !hasFocus || data.length == 0 ) return hideResultsNow();

            if (jQuery.browser.msie) {
                // we put a styled iframe behind the calendar so HTML SELECT elements don't show through
                // $results.append(document.createElement('iframe'));
            }
            if (!jQuery.isEmptyObject(data)) {
                results.appendChild(dataToDom(data));
                // autofill in the complete box w/the first match as long as the user hasn't entered in more data
                if( options.autoFill && ($input.val().toLowerCase() == q.toLowerCase()) ) autoFill(data[0][0]);
                showResults();
            }
        } else {
            hideResultsNow();
        }
    };

    function parseData(data) {
        if (!data) return null;
        data = jQuery.parseJSON(data);
        if (options.jstpl) return data;
        var parsed = {};
        for (var o in data) {
            parsed[o] = [];
            var rows = data[o].split(options.lineSeparator);
            for (var i=0; i < rows.length; i++) {
                var row = jQuery.trim(rows[i]);
                if (row) {
                    parsed[o][parsed[o].length] = row.split (options.cellSeparator);
                }
            }
        }
        return parsed;
    };

    function dataToDom(data) {
        var ul = document.createElement("ul");
        if (options.jstpl) {
            var html = TrimPath.parseTemplate (tpl).process (data, {throwExceptions:true});
            jQuery(ul).html(html);
            jQuery('li.ac_even,li.ac_odd').live('mouseenter mouseleave', function(event){
                if (event.type == 'mouseenter') {
                    jQuery('li', ul).removeClass('ac_over');
                    jQuery(this).addClass("ac_over"); active = jQuery("li", ul).indexOf(jQuery(this).get(0));
                }else if (event.type == 'mouseleave') {
                    jQuery(this).removeClass('ac_over');
                }
            });
            return ul
        }
        var num = 0;
        for (var h in data) {
            if (options.subcat && h != options.subcat) continue;
            num = data[h].length;

            // limited results to a max number
            if( (options.maxItemsToShow > 0) && (options.maxItemsToShow < num) ) num = options.maxItemsToShow;

            if (!options.noHeader) {
                var header = document.createElement("li");
                ul.appendChild (header);
                jQuery(header).addClass('prod_group ac_cat').html(h);
            }
            for (var i=0; i < num; i++) {
                var row = data[h][i];
                if (!row) continue;
                var li = document.createElement("li");
                if (options.formatItem) {
                    li.innerHTML = options.formatItem(row, i, num);
                    li.selectValue = row[0];
                } else {
                    li.innerHTML = row[0];
                    li.selectValue = row[0];
                }
                var extra = null;
                if (row.length > 1) {
                    extra = [];
                    for (var j=1; j < row.length; j++) {
                        extra[extra.length] = row[j];
                    }
                }
                li.extra = extra;
                li.className = i%2?'ac_odd':'ac_even';
                ul.appendChild(li);
                jQuery(li).hover(
                    function() { jQuery("li", ul).removeClass("ac_over"); jQuery(this).addClass("ac_over"); active = jQuery("li", ul).indexOf(jQuery(this).get(0)); },
                    function() { jQuery(this).removeClass("ac_over"); }
                ).click(function(e) { /*e.preventDefault();*/ e.stopPropagation(); /*selectItem(this)*/ });
            }
        }

        return ul;
    };

    function requestData(q) {
        if (!options.matchCase) q = q.toLowerCase();
        var data = options.cacheLength ? loadFromCache(q) : null;
        // recieve the cached data
        if (data) {
            if (options.jstpl) requestTpl(function(){receiveData(q, data);});
            else receiveData(q, data);
            // if an AJAX url has been supplied, try loading the data now
        } else if( (typeof options.url == "string") && (options.url.length > 0) ){
            jQuery.get(makeUrl(q), function(data) {
                if (options.jstpl) {
                    requestTpl(function(){
                        data = parseData(data);
                        addToCache(q, data);
                        receiveData(q, data);
                    });
                } else {
                    data = parseData(data);
                    addToCache(q, data);
                    receiveData(q, data);
                }
            });
            // if there's been no data found, remove the loading class
        } else {
            $input.removeClass(options.loadingClass).removeClass(options.emptyClass + " " + options.searchClass);
        }
    };

    function requestTpl(cb) {
        if (tpl == '') {
            jQuery.get(options.jstpl, function(tplstr){
                tpl = tplstr;
                if (cb) cb();
            });
        } else {
            if (cb) cb();
        }
    }

    function makeUrl(q) {
        var url = options.url + "?q=" + encodeURI(q);
        for (var i in options.extraParams) {
            url += "&" + i + "=" + encodeURI(options.extraParams[i]);
        }
        return url;
    };

    function loadFromCache(q) {
        if (!q) return null;
        if (cache.data[q]) return cache.data[q];
        if (options.matchSubset) {
            for (var h in cache.data[q]) {
                for (var i = q.length - 1; i >= options.minChars; i--) {
                    var qs = q.substr(0, i);
                    var c = cache.data[h][qs];
                    if (c) {
                        var csub = [];
                        for (var j = 0; j < c.length; j++) {
                            var x = c[j];
                            var x0 = x[0];
                            if (matchSubset(x0, q)) {
                                csub[csub.length] = x;
                            }
                        }
                        return csub;
                    }
                }
            }
        }
        return null;
    };

    function matchSubset(s, sub) {
        if (!options.matchCase) s = s.toLowerCase();
        var i = s.indexOf(sub);
        if (i == -1) return false;
        return i == 0 || options.matchContains;
    };

    this.flushCache = function() {
        flushCache();
    };

    this.setExtraParams = function(p) {
        options.extraParams = p;
    };

    this.setUrl = function (url) {
        options.url = url;
    }

    this.findValue = function(){
        var q = $input.val();

        if (!options.matchCase) q = q.toLowerCase();
        var data = options.cacheLength ? loadFromCache(q) : null;
        if (data) {
            findValueCallback(q, data);
        } else if( (typeof options.url == "string") && (options.url.length > 0) ){
            jQuery.get(makeUrl(q), function(data) {
                data = parseData(data)
                addToCache(q, data);
                findValueCallback(q, data);
            });
        } else {
            // no matches
            findValueCallback(q, null);
        }
    }

    function findValueCallback(q, data){
        if (data) $input.removeClass(options.loadingClass);

        var num = (data) ? data.length : 0;
        var li = null;

        for (var i=0; i < num; i++) {
            var row = data[i];

            if( row[0].toLowerCase() == q.toLowerCase() ){
                li = document.createElement("li");
                if (options.formatItem) {
                    li.innerHTML = options.formatItem(row, i, num);
                    li.selectValue = row[0];
                } else {
                    li.innerHTML = row[0];
                    li.selectValue = row[0];
                }
                var extra = null;
                if( row.length > 1 ){
                    extra = [];
                    for (var j=1; j < row.length; j++) {
                        extra[extra.length] = row[j];
                    }
                }
                li.extra = extra;
            }
        }

        if( options.onFindValue ) setTimeout(function() { options.onFindValue(li) }, 1);
    }

    function addToCache(q, data) {
        if (!data || !q || !options.cacheLength) return;
        if (!cache.length || cache.length > options.cacheLength) {
            flushCache();
            cache.length++;
        } else if (!cache[q]) {
            cache.length++;
        }
        cache.data[q] = data;
    };

    function findPos(obj) {
        var curleft = obj.offsetLeft || 0;
        var curtop = obj.offsetTop || 0;
        while (obj = obj.offsetParent) {
            curleft += obj.offsetLeft
            curtop += obj.offsetTop
        }
        return {x:curleft,y:curtop};
    }
}

jQuery.fn.autocomplete = function(url, options, data) {
    // Make sure options exists
    options = options || {};
    // Set url as option
    options.url = url;
    // set some bulk local data
    options.data = ((typeof data == "object") && (data.constructor == Array)) ? data : null;

    // Set default values for required options
    options.inputClass = options.inputClass || "ac_input";
    options.resultsClass = options.resultsClass || "ac_results";
    options.lineSeparator = options.lineSeparator || "\n";
    options.cellSeparator = options.cellSeparator || "|";
    options.minChars = options.minChars || 1;
    options.delay = options.delay || 400;
    options.matchCase = options.matchCase || 0;
    options.matchSubset = options.matchSubset || 1;
    options.matchContains = options.matchContains || 0;
    options.cacheLength = options.cacheLength || 1;
    options.mustMatch = options.mustMatch || 0;
    options.extraParams = options.extraParams || {};
    options.loadingClass = options.loadingClass || "ac_loading";
    options.searchClass = options.searchClass || "ac_search";
    options.resetClass = options.resetClass || "ac_reset";
    options.emptyClass = options.emptyClass || "empty";
    options.selectFirst = options.selectFirst || false;
    options.selectOnly = options.selectOnly || false;
    options.maxItemsToShow = options.maxItemsToShow || -1;
    options.autoFill = options.autoFill || false;
    options.width = parseInt(options.width, 10) || 0;
    options.scroll = options.scroll || false;
    options.showall = options.showall || false;
    // Add reset button
    options.reset = options.reset || 0;
    options.position = options.position || 'fixed';
    options.direction = options.direction || 'bottom';
    options.hideOnBlur = options.hideOnBlur || false;
    options.showOnFocus = options.showOnFocus || false;
    options.noHeader = options.noHeader || false;
    options.hideOnSelect = options.hideOnSelect || false;
    options.showOnReturn = options.showOnReturn || false;
    options.jstpl = options.jstpl || false;

    this.each(function() {
        var input = this;
        new jQuery.autocomplete(input, options);
    });

    // Don't break the chain
    return this;
}

jQuery.fn.autocompleteArray = function(data, options) {
    return this.autocomplete(null, options, data);
}

jQuery.fn.indexOf = function(e){
    for( var i=0; i<this.length; i++ ){
        if( this[i] == e ) return i;
    }
    return -1;
};