/*
 *
 *  ComboBox class:
 *
 *      Replaces contents of a FIELDSET of class 'combo-box' with
 *      a combo box widget.
 *
 *  other implimentations:
 *      http://particletree.com/features/upgrade-your-select-element-to-a-combo-box/
 *
 */
 
function ComboBox() {
    var self   = this;
    
	self.regex = /\bcombo_box\b/;

    self.instantiate = function () {
        var elementList = document.getElementsByTagName('fieldset');
        for (var i = elementList.length-1; i >= 0; i--) {
            if (elementList[i].className.match(self.regex)) {
                self.process(elementList[i]);
            }
        }
    }
    
    self.process = function (obj) {
        /*
            We're looking for the two LABEL containers that hold
            the lo-fi ComboBox.  We'll grab them with the useful
            `getElementsByTagName` method.
         */
        var labels = obj.getElementsByTagName('label');
        if (labels.length != 2) {
            /*
                It's probably not the correct format if there 
                aren't two and only two LABELs, so run away 
                before we break something important
             */
            return;
        }
        
        /*
            We're using the DIV that contains the combo box
            to hold some values that we're going to need
            later on.  This is both simply convinient for us
            while writing the code, but also allows us to
            talk to the SELECT element from the INPUT element's
            event handlers, which will come in handy later on.
        */
        obj.labelText = labels[0].childNodes[0].nodeValue;
        obj.select          = labels[0].childNodes[1];
        obj.input           = labels[1].childNodes[1];
         
        /*
            The SELECT's OPTION list probably isn't sorted, so
            we're going to create a sorted cache that will allow
            us to use a speedy binary search later on when we add 
            the type-ahead functionality.
        */
        self.buildSelectCache(obj);
    
        /*
            That pretty much does it for data collection.  Now
            comes the more interesting part where we build the 
            new structure that provides the exciting combo box
            functionality.
            
            The basic idea is to use the INPUT box that we've 
            already got lying around as the input source for the
            user, and to change the dropdown SELECT box into
            a list SELECT, and hide/show it as appropriate.
        */
        self.reformStructure(obj)
    }
    
    self.reformStructure = function(comboBoxContainer) {
        /*
            For efficiency (and readability), we'll store a 
            reference to the container LABELs.
            
            Here is where it starts to really come in handy to hang
            the various necessary bits of data on the DIV: we can 
            pass a reference to the DIV around everywhere, and 
            automatically have a way to talk about each of the
            elements we need to touch.
        */
        var select          = comboBoxContainer.select;
        var selectContainer = select.parentNode;
        var input           = comboBoxContainer.input;
        var inputContainer  = input.parentNode;

        /*
            We need to kill autocomplete on the INPUT element
            or it'll do nasty things to our SELECT box
        */
        input.setAttribute('autocomplete', 'off');

        /*
            Next, we'll change the label of the INPUT element so that
            it's using whatever the SELECT element used, and also set
            it's default value to the selected value in the SELECT (if
            the INPUT's value is empty, that is).  DOM references
            make this fairly trivial.
        */
        inputContainer.childNodes[0].nodeValue = selectContainer.childNodes[0].nodeValue;
        if (input.value == "") {
            input.value = select.options[select.selectedIndex].text;
        }

		/*
			We'll remove the SELECT and it's LABEL from the DOM
			now in order to make sure that the positioning info
			we put together below works properly.
		*/
        select.style.display          = "none";
        selectContainer.removeChild(select);
        selectContainer.parentNode.removeChild(selectContainer);
        addEvent(select, 'click', self.selectClickHandler);

        /*
            To replicate the functionality of a combo box, we'll need
            some way of toggling the SELECT on and off when the selection
            process is happening.
            
            We'll add a button (down arrow), and a keyup handler for
            the INPUT to capture the up and down arrow keys (as well
            as enabling the typeahead search portion of the box).
        */
        addEvent(input, 'keyup',   self.inputKeyUpHandler);
        input.style.paddingRight = "14px"; // give the INPUT some padding so the image fits

        var toggle = document.createElement('input');
        toggle.setAttribute('type', 'image');
        toggle.setAttribute('src',  'arrow.png');
        toggle.setAttribute('alt',  'Toggle Combo Box');
        addEvent(toggle, 'click', self.toggleClickHandler);

        toggle.style.position    = 'absolute';
		toggle.style.margin      = '0';
		toggle.style.padding     = '0';
        toggle.style.left        = (findPosX(input) + input.offsetWidth - 14) + "px";	// image is 12 pixels wide   
        toggle.style.top         = (findPosY(input) + 5) + "px";                        // image is 7 pixels high
        inputContainer.appendChild(toggle);

        /*
            That done, we'll remove the SELECT from it's current
            location, and jam it into the INPUT container which
            leaves it in the DOM where we can manipulate it, and 
            where it will still be submitted with the form.
            
            We'll also add a click handler to the SELECT to 
			provide some selection options for the user, and
			align the SELECT with the bottom, left-hand corner 
			of the INPUT, and match the widths so that everything
            looks right when the SELECT is shown.  Finally, we'll
			give the SELECT a `size` attribute to open it up
			into a list format.
        */            

        select.style.position = 'absolute';
        select.setAttribute('size', 4);
        select.style.width    = input.scrollWidth + "px";
        inputContainer.appendChild(select);
    }
    
    self.selectClickHandler = function(e) {
        /*
            If we click on the SELECT, set the INPUT to the text
            value of the selected OPTION, hide the SELECT, and 
            focus on the input box.
        */
        var container = this.parentNode.parentNode;
        container.input.value = this.options[this.selectedIndex].text;
        this.style.display = 'none';
        container.input.focus();
        return false;
    }
    
    self.toggleClickHandler = function (e) {
        /*
            If we click on the toggle INPUT, then toggle the 
            display value of the SELECT, focus on the INPUT
            text field, and stop the event from propagating 
            so that the form doesn't submit.
        */
        if (window.event) { e = window.event; }
        container = this.parentNode.parentNode;
        container.select.style.display = (container.select.style.display == 'none')?'block':'none';
        container.input.focus();
        return stopEvent(e);
    }
    
    self.inputKeyUpHandler = function (e) {
        if (window.event) {
            e = window.event;
        }
        var container = this.parentNode.parentNode;
        var input     = this;
        var select    = container.select;

        var keycode = e.keyCode;

        switch (keycode) {
            case 38: // up arrow
                /*
                    If the select is hidden, unhide it
                */
                select.style.display = 'block';
                
                /*
                    We want to respond to the up arrow by moving the current 
                    value up one in our list.  But we don't want to run off 
                    the top of the list, so we get the maximum value: 0, or 
                    the currentIndex - 1.  So if we're at the 8th value, 
                    we'll move to the 7th, but if we're already at the top, 
                    we'll stay at the 0th (numbering starts at 0 in JavaScript)
                */
                var newIndex = Math.max(0, select.selectedIndex-1);
                select.selectedIndex = newIndex;
                
                /*
                    Now that we've got a new selection, we should populate the 
                    INPUT with the selection's value
                */
                input.value = select.options[select.selectedIndex].text;
                
                /*
                    We'll also need to clear out our current filter, since 
                    we've messed with the position in the list.  If we didn't
                    do this, some of our later optimizations would die horribly.
                */
                container.select.currentFilter = "";
                return stopEvent(e);
                
            case 40: // down arrow
                /*
                    Same thing as the up arrow here, except we want to get 
                    the minimum value between the last element in the list, 
                    and the selectedIndex + 1 to make sure we don't run off
                    the end.
                */
                select.style.display = 'block';
                var newIndex = Math.min(select.options.length-1, select.selectedIndex+1);
                select.selectedIndex = newIndex;
                input.value = select.options[select.selectedIndex].text;
                select.currentFilter = "";
                return stopEvent(e);

            case 13: // enter
            case 27: // escape
                /*
                    If we hit enter or escape, tell our SELECT to hide itself
                */
				select.blur();
                select.style.display = "none";
				input.focus();
                break;

            default:
                /*
                    If it's not the up/down arrow, escape, or the enter key, then process
                    it by telling the SELECT box to set itself to the correct value.
                    We'll talk about telling the SELECT element how to do that in 
                    a few moments.
                    
                    The timeout code is here in order to deal with fast typists: we
                    don't want to tell the SELECT box to filter itself for every keypress
                    if we're in the middle of typing a word.  That would slow things 
                    and potentially cause problems if the value of the INPUT field 
                    changed during the middle of an event.  So we store a timer that
                    waits 50 milliseconds before telling the SELECT object to select
                    the element best corresponding to the currently typed-in text.
                    
                    Every time a key is pressed, we clear out that timer, and reset it
                    for another 50 milliseconds.  That solves our problem.
                */
        		clearTimeout(input.timer);
                input.timer = setTimeout(
                                function () {
                                    self.search(container);
                                },
                                50
                );
                break;
        }
    }
    
    self.search = function (container) {
        /*
            We're going to use the cacheArray that we built earlier in order
            to speed up the search process.  We can use a binary search
            (O(log n)) instead of a sequential search  (O(n)), which is 
            substantially faster for vaguely large data sets.
            
            The algorithm is well explained here:
                http://en.wikipedia.org/wiki/Binary_search
        */
        var select = container.select;
        select.style.display = 'block';
        var input  = container.input;
        var cache  = container.cacheArray;
        var lo = -1, hi = cache.length -1, theIndex = "", cachedIndex = "";

        var needle = input.value;
                
        for (;(hi-lo) > 1;) {
            var mid = Math.floor((hi+lo)/2);
            if (needle <= cache[mid].text.substring(0,needle.length)) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        
        if (needle.substring(0, cache[hi].text.length) == cache[hi].text.substring(0,needle.length)) {
            theIndex = hi;
        } else {
            theIndex = lo;
        }


                
        /*
            If theIndex is -1, then we've got nothing, so set the currentIndex to
            0.  Else, if we've found the value, set the currentIndex to theIndex.
            Else, we ended up somewhere in the middle of the list, but didn't find
            the value we were looking for.  In that case, set the selectedIndex to 
            the value just after the one we ended up on.
        */        
        if (
            theIndex == -1
            ||
            needle.substring(0,cache[theIndex].text.length) == cache[theIndex].text.substring(0, needle.length)
        ) {
            select.selectedIndex = cache[Math.max(theIndex, 0)].index;
        } else {
            select.selectedIndex = cache[Math.max(theIndex, 0)].index + 1;
        }
        
        
    }
    
    self.buildSelectCache = function(obj) {
        obj.cacheArray          = new Array();
        var selectObj           = obj.select;
        /*
            Store all the OPTIONs in a cache, keeping the
            text, value, and position on an object
         */
		var length = selectObj.options.length;
        for (i=0; i<length; i++) {
            // Build cache array
            var tempObj = new Object();
            
            tempObj.text  = selectObj.options[i].text;
            tempObj.value = selectObj.options[i].value;
            tempObj.index = i;
            obj.cacheArray.push(tempObj);
        }

        self.quicksort(obj.cacheArray);
    }
    
        /* 
            Quicksort: smart people have explained this here: 
                http://en.wikipedia.org/wiki/Quicksort
        */
            self.quicksort  = function(obj) {
                self._quicksort(obj, 0, obj.length - 1);
            }
            self._quicksort = function(a, lo, hi) {
                var i = lo, j=hi, temp;
                var x = a[Math.floor((lo+hi)/2)];
                do {
                    while (a[i].text < x.text) i++;
                    while (a[j].text > x.text) j--;
                    
                    if (i<=j) {
                        temp = a[i];
                        a[i] = a[j];
                        a[j] = temp;
                        i++;
                        j--;
                    }
                } while (i<=j);
                if (lo < j) self._quicksort(a, lo, j);
                if (hi > i) self._quicksort(a, i,  hi);
            }
        /* END QUICKSORT */

    addEvent(window, 'load', self.instantiate);
}

/*
 * Helper Functions
 */
	/* 
		A basic `addEvent` function.  This could be easily
		replaced with something more interestingly functional,
		like Yahoo!'s Event utility:
			
			http://developer.yahoo.com/yui/event/index.html
	*/
	function addEvent(obj, event, func) {
	    try {
	        obj.addEventListener(event, func, false);
	    } catch (e) {
	        if (typeof eval("obj.on"+event) == "function") {
	            var existing = obj['on'+event];
	            obj['on'+event] = function () { existing(); func(); };
	        } else {
	            obj['on'+event] = func;                        
	        }
	    }
	} 
	
	/*
		A basic `stopEvent` function.  Again, this could
		be easily replaced with Yahoo!'s Event utility.
	*/
	function stopEvent(e) {
		if (e.stopPropagation)
	        e.stopPropagation();
	    if (e.preventDefault) 
			e.preventDefault();

	    e.cancelBubble = true;
		e.returnValue  = false;
	    return false;
	}
	
	/*
		Positional Functions, see PPK's:
	 		http://www.quirksmode.org/js/findpos.html 
	*/
    function findPosX(obj)
    {
        var curleft = 0;
        if (obj.offsetParent)
        {
            while (obj.offsetParent)
            {
                curleft += obj.offsetLeft;
                obj = obj.offsetParent;
            }
            curleft += obj.offsetLeft;
        }
        else if (obj.x)
            curleft += obj.x;

        return curleft;
    }

    function findPosY(obj)
    {
        var curtop = 0;
        if (obj.offsetParent)
        {
            while (obj.offsetParent)
            {
                curtop += obj.offsetTop;
                obj = obj.offsetParent;
            }
            curtop += obj.offsetTop;
        }
        else if (obj.y)
            curtop += obj.y;
        return curtop;
    }
    function findCenterY(obj) {
        return findPosY(obj) + Math.floor(obj.offsetHeight / 2);
    }
    function findRightX(obj) {
        return findPosX(obj) + obj.scrollWidth;
    }
/* 
	END HELPER FUNCTIONS 
*/

var ComboBoxFactory = new ComboBox();