Thursday 16 February 2012

LIBSVM tutorial


What is SVM?

A Support Vector Machine is a learning algorithm typically used for classification
problems (Weather prediction, text categorization, handwritten character recognition, image
classification,Facial expression classification etc.). ie, if we have some sets of things classified
But we  know nothing about how we classified it, or we don't know the rules used for classification),
when a new data comes, SVM can PREDICT which set the data should belong to.

Suppose we have to differentiate a square from rectangle. how can we do it?
we know the logic is

if length=breadth then it is a square
else
it is a rectangle.

this is the logic we want to cluster using the SVM, we would have to give the have data in following format:

1 1:2 2:2
1 1:4 2:4
1 1:9 2:9
1 1:10 2:10
..........
..........
-1 1:5 2:6
-1 1:3 2:4
-1 1:6 2:9
-1 1:4 2:1
..........
..........

The above example is a TWO-class classification with labels +1 and -1 . +1 represents square and -1 represents rectangle.

Consider the 4 th line in the above format ie 1 1:10 2:10

1 represents this is a square.
For the second column (eg: 1:10) 1: represents the index value and 10 represents the length.
For the third column (eg: 2:10) 2: represents the index value and 10 represents the bredth.

Consider the 8 th line in the above format ie -1 1:4 2:1

-1 represents this is a rectangle.
For the second column (eg: 1:4) 1: represents the index value and 4 represents the length.
For the third column (eg: 2:1) 2: represents the index value and 1 represents the bredth.

This is the input file format of SVM.

[label] [index1]:[value1] [index2]:[value2] ...
[label] [index1]:[value1] [index2]:[value2] ...

label
Sometimes referred to as 'class', the class (or set) of your classification. Usually we put integers here.

index
Ordered indexes. usually continuous integers.

value
The data for training. Usually lots of real (floating point) numbers.

Why value, value2, ...?

The reason is usually the input data to the problem you were trying to solve involves lots of 'features'
or say 'attributes', so the input will be a set (or say vector/array).

For the above example we have 2 features lenght and breadth.

Installing Libsvm

We can download the libsvm from http://www.csie.ntu.edu.tw/~cjlin/libsvm/
libsvm.zip or libsvm.tar.gz

Contents in the .zip and .tar.gz are the same.
For windows users unzip the file. libsvm folder will be created.
UNIX users mostly prefer .tar.gz.

What is Libsvm?
Libsvm is a library for support vector machines.

How to Use Libsvm

We must follow the below procedure :
 1. Data Preparation for SVM
 2. Convert data into SVM format
 3. Conduct simple scaling on the data
 4. Consider the RBF kernel K(x; y) = e
 5. Use cross-validation to find the best parameter C and gamma
 6. Use the best parameter C and gamma to train the whole training set
 7. Test

We discuss this procedure in detail in the following sections

1. Data Preparation for SVM
We need to collect maximum data as possible. data set should contains both positive and negative data.
if it contains only one type of data(ie either positive or negative), it will shows wrong accuracy.
The selection of a negative data set is essential to the reliability of the prediction model.
we need to split the data set into two, one for training and other for testing.
After collecting the data , we need to convert both the training set and testing set into SVM format.

2.  Convert the data into SVM format
The SVM algorithm operates on numeric attributes.
So we need to convert the data into libsvm format which contains only numerical values.

For example , If we have imaginary data records like this:

man voice:low figure:big income:good
woman voice:high figure:slim income:fare

1. Convert the feature values to its numeric representation.
   Let's say, that best salary would be 5 and worst salary 1 (or no salary = 0), the same with other enumarated variables.
2. We have 2 classes, man and women . convert the classes to numeric values: man = 1, woman = -1
3. Save it in libsvm data format:

[class/target] 1:[firstFeatureValue] 2:[secondFeatureValue] etc.
ex.:
a women with great salary, low voice and small figure would be encoded like:
-1 1:5 2:1.5 3:1.8

In general the input file format of SVM is

[label] [index1]:[value1] [index2]:[value2] ...
[label] [index1]:[value1] [index2]:[value2] ...

label
Sometimes referred to as 'class', the class (or set) of your classification. Usually we put integers here.

index
Ordered indexes. usually continuous integers.

value
The data for training. Usually lots of real (floating point) numbers.


Is there a program to check if my data are in the correct format?
yes.
we can use the python script libsvm-3.11/tools /checkdata.py

Before doing that you need to install Python.
put checkdata.py in the Python folder. open a command prompt and type python checkdata.py filename.






3. Conduct simple scaling on the data

The original data maybe too huge or small in range, thus we can
rescale them to the proper range so that training and predicting will be faster.
The main advantage of scaling is to avoid attributes in greater numeric
ranges dominating those in smaller numeric ranges. Another advantage is to avoid
numerical difficulties during the calculation.

We recommend linearly scaling each attribute to the range [1; +1] or [0; 1].
we have to use the same method to scale both training and testing
data.

svm-scale is a tool for scaling input data file.
It is available at libsvm-3.11\windows

The syntax of svm-scale is
svm-scale [options] data_filename.

For options please refer README file in libsvm.






Running the above command generates 2 files. training.scale and range file.
In the above example we scale the file training.txt and scale each attribute/feature to the range [-1 +1].

The output of scaling is training.scale file, which is used for creating the model.
(model will be discussed later).
here we use option -s for saving the scaling parameters to range file.
Scaling factors are stored in the file range and that file is used for scaling the
test data.


we should scale the testing and scaling data in same range.
so for scaling the testing file we can use the range file .





Above example uses the range file for scaling the testing data. It generates the output testing.scale.

note: we can scale training and testing data in a similar way.
> svm-scale -s scaling_parameters train_data > scaled_train_data
> svm-scale -r scaling_parameters test_data > scaled_test_data

But using the same scaling factors for training and testing sets, we obtain much better
accuracy


4. Model Selection

After scaling the data set , we have to choose a kernel function for creating the model.
4 basic kernels are

  1. linear
  2. polynomial
  3. radial basis function
  4. sigmoid

In general, the RBF kernel is a reasonable first choice.
A recent result shows that if RBF is used with model selection, then there is no need to consider the linear kernel. The kernel matrix using sigmoid may not be positive definite and in general it's accuracy is not better than RBF.  Polynomial kernels are ok but if a high degree is used, numerical difficulties tend to happen.

In some cases RBF kernel is not used.
case 1: Number of instances < number of features/attributes

(instance means each entry in the txt file)

Consider an example1 .
we have 2 data sets one for training and other for testing
training set contains 38 instance and testing set contains 34 instance. number of features:7,129.

If you use RBF kernel the accuracy is 71.05
and for linear kernel accuracy is 94.73 (please see below)

In such cases linear kernel have more accuracy than RBF kernel.

There are two parameters for an RBF kernel: C and gamma
linear kernel has a penalty parameter C.
It is not known beforehand which C and gamma are best for a given problem; consequently some kind of model selection(parameter search) must be done. The goal is to identify good (C , gamma) so that the
classifier can accurately predict unknown data (i.e. testing data).

For selecting the best parameter value , we can use grid.py in the libsvm-3.11\tools directory.

grid.py is a parameter selection tool for C-SVM classification using
the RBF (radial basis function) kernel. It uses cross validation (CV) (will discuss later)
technique to estimate the accuracy of each parameter combination in
the specified range and helps you to decide the best parameters for
your problem.
grid.py directly executes libsvm binaries (so no python binding is needed)
for cross validation and then draw contour of CV accuracy using gnuplot.

Before using the grid.py , we should edit grid.py for setting the path of svmtrain_exe and gnuplot_exe

grid.py

if not is_win32:
       svmtrain_exe = "../svm-train"
       gnuplot_exe = "/usr/bin/gnuplot"
else:
       # example for windows
       svmtrain_exe = r"F:\lekshmi\libsvm-3.11\windows\svm-train.exe"
       # svmtrain_exe = r"c:\Program Files\libsvm\windows\svm-train.exe"
       gnuplot_exe = r"F:\lekshmi\gp444win32\gnuplot\binary\gnuplot.exe"

you should install python and gnuplot before running grid.py.
After installing python set the environment variable "PYTHONPATH" as C:\Python27(in my system python is installed in C directory)
put the grid.py in the python folder. open the command promt and change directory to the folder contains grid.py.

Consider the above example1 (Number of instances < number of features/attributes)

for linear kernel







for RBF kernel






now we can discuss the grid.py in detail
The syntax for grid.py is


grid.py [-log2c begin,end,step] [-log2g begin,end,step] [-v fold]
       [-svmtrain pathname] [-gnuplot pathname] [-out pathname] [-png pathname]
       [additional parameters for svm-train] dataset









Monday 9 January 2012

Connecting MySQL in xampp with java

phpMyAdmin in xampp server is used  to manage MySQL database.We can connecting java with mysql xampp using the below code:

Prerequisite
Xampp should be installed.


In the java code 
  String url = "jdbc:mysql://localhost:3306/"; ( MySQL server in xampp is installed in port 3306)
  String dbName = "test";
  String driver = "com.mysql.jdbc.Driver";
  String userName = "root";
  String password = "";
  try {
      Class.forName(driver).newInstance();
      Connection con =DriverManager.getConnection(url+dbName,userName,password);

  }
We need to put mysql-connector-java-5.1.18-bin.jar in the classpath.





Sunday 11 December 2011

table.css

table.example {
    border:1px solid black;
    border-collapse:collapse;
}
table.example th, table.example td {
    border:1px solid #aaaaaa;
    padding: 17px 15px 2px 15px;
}
table.example thead th {
    background-color:#ccccff;
}
table.example tfoot td {
    background-color:#ffccff;
}

table.example tr.tbody_header {
    font-weight:bold;
    text-align:center;
    background-color:#dddddd;
}

table.example a.pagelink {
    padding-left:5px;
    padding-right:5px;
    border:1px solid #666666;
    margin:0px 5px 0px 5px;
}
table.example a.currentpage {
    background-color:yellow;
}
/* Striping */
tr.alternate {
    background-color:#ffffcc;
}

/* Sorting */
th.table-sortable {
    cursor:pointer;
    background-image:url("../images/sortable.gif");
    background-position:center left;
    background-repeat:no-repeat;
    padding-left:12px;
}
th.table-sorted-asc {
    background-image:url("../images/sorted_up.gif");
    background-position:center left;
    background-repeat:no-repeat;
}
th.table-sorted-desc {
    background-image:url("../images/sorted_down.gif");
    background-position:center left;
    background-repeat:no-repeat;
}
th.table-filtered {
    background-image:url("filter.gif");
    background-position:center left;
    background-repeat:no-repeat;
}
select.table-autofilter {
    font-size:smaller;
}

/* Examples which stray from the default */
table.altstripe tr.alternate2 {
    background-color:#ccffff;
}

/* Sort Icon Styles */
table.sort01 th.table-sortable { background-image:url("../images/01_unsorted.gif"); }
table.sort01 th.table-sorted-asc { background-image:url("../images/01_ascending.gif"); }
table.sort01 th.table-sorted-desc { background-image:url("../images/01_descending.gif"); }

table.sort02 th.table-sortable { background-image:none; padding-left:16px; }
table.sort02 th.table-sorted-asc { background-image:url("../images/icons/02_ascending.gif"); }
table.sort02 th.table-sorted-desc { background-image:url("../images/icons/02_descending.gif"); }

table.sort03 th.table-sortable { background-image:none; }
table.sort03 th.table-sorted-asc { background-image:url("../images/icons/03_ascending.gif"); }
table.sort03 th.table-sorted-desc { background-image:url("../images/icons/03_descending.gif"); }

table.sort04 th.table-sortable { background-image:none; }
table.sort04 th.table-sorted-asc { background-image:url("../images/icons/04_ascending.gif"); }
table.sort04 th.table-sorted-desc { background-image:url("../images/icons/04_descending.gif"); }

table.sort05 th.table-sortable { background-image:url("05_unsorted.gif"); padding-left:16px;}
table.sort05 th.table-sorted-asc { background-image:url("05_ascending.gif"); }
table.sort05 th.table-sorted-desc { background-image:url("05_descending.gif"); }

table.sort06 th.table-sortable { background-image:none; padding-left:16px;}
table.sort06 th.table-sorted-asc { background-image:url("icons/06_ascending.gif"); }
table.sort06 th.table-sorted-desc { background-image:url("icons/06_descending.gif"); }

table.sort07 th.table-sortable { background-image:none; }
table.sort07 th.table-sorted-asc { background-image:url("07_ascending.gif"); }
table.sort07 th.table-sorted-desc { background-image:url("07_descending.gif"); }

table.sort08 th.table-sortable { background-image:none; }
table.sort08 th.table-sorted-asc { background-image:url("icons/08_ascending.gif"); }
table.sort08 th.table-sorted-desc { background-image:url("icons/08_descending.gif"); }

table.sort09 th.table-sortable { background-image:none; padding-left:30px;}
table.sort09 th.table-sorted-asc { background-image:url("icons/09_ascending.gif"); }
table.sort09 th.table-sorted-desc { background-image:url("icons/09_descending.gif"); }

table.sort10 th.table-sortable { background-image:url("icons/10_unsorted.gif"); }
table.sort10 th.table-sorted-asc { background-image:url("icons/10_ascending.gif"); }
table.sort10 th.table-sorted-desc { background-image:url("icons/10_descending.gif"); }

table.sort11 th.table-sortable { background-image:url("icons/11_unsorted.gif");padding-left:24px; }
table.sort11 th.table-sorted-asc { background-image:url("icons/11_ascending.gif"); }
table.sort11 th.table-sorted-desc { background-image:url("icons/11_descending.gif"); }

table.sort12 th.table-sortable { background-image:none; }
table.sort12 th.table-sorted-asc { background-image:url("icons/12_ascending.gif"); }
table.sort12 th.table-sorted-desc { background-image:url("icons/12_descending.gif"); }

table.sort13 th.table-sortable { background-image:none; }
table.sort13 th.table-sorted-asc { background-image:url("icons/13_ascending.gif"); }
table.sort13 th.table-sorted-desc { background-image:url("icons/13_descending.gif"); }

table.sort14 th.table-sortable { background-image:none; }
table.sort14 th.table-sorted-asc { background-image:url("icons/14_ascending.gif"); }
table.sort14 th.table-sorted-desc { background-image:url("icons/14_descending.gif"); }

table.sort15 th.table-sortable { background-image:none; }
table.sort15 th.table-sorted-asc { background-image:url("icons/15_ascending.gif"); }
table.sort15 th.table-sorted-desc { background-image:url("icons/15_descending.gif"); }

table.sort16 th.table-sortable { background-image:none; }
table.sort16 th.table-sorted-asc { background-image:url("icons/16_ascending.gif"); }
table.sort16 th.table-sorted-desc { background-image:url("icons/16_descending.gif"); }

table.sort17 th.table-sortable { background-image:none; }
table.sort17 th.table-sorted-asc { background-image:url("icons/17_ascending.gif"); }
table.sort17 th.table-sorted-desc { background-image:url("icons/17_descending.gif"); }

table.sort18 th.table-sortable { background-image:url("icons/18_unsorted.gif"); }
table.sort18 th.table-sorted-asc { background-image:url("icons/18_ascending.gif"); }
table.sort18 th.table-sorted-desc { background-image:url("icons/18_descending.gif"); }

table.sort19 th.table-sortable { background-image:url("icons/19_unsorted.gif");padding-left:24px; }
table.sort19 th.table-sorted-asc { background-image:url("icons/19_ascending.gif"); }
table.sort19 th.table-sorted-desc { background-image:url("icons/19_descending.gif"); }

/* Icons box */
.iconset {
    margin:5px;
    border:1px solid #cccccc;
    border-color:#cccccc #666666 #666666 #cccccc;
    text-align:center;
    cursor:pointer;
    width:100px;
}
.iconset img {
    margin:3px;
}

/* Documentation */
tr.doc_section {
    font-weight:bold;
    text-align:center;
    background-color:#dddddd;
}

table.js

var Sort = (function(){
    var sort = {};
    // Default alpha-numeric sort
    // --------------------------
    sort.alphanumeric = function(a,b) {
        return (a==b)?0:(a<b)?-1:1;
    };
    sort['default'] = sort.alphanumeric; // IE chokes on sort.default

    // This conversion is generalized to work for either a decimal separator of , or .
    sort.numeric_converter = function(separator) {
        return function(val) {
            if (typeof(val)=="string") {
                val = parseFloat(val.replace(/^[^\d\.]*([\d., ]+).*/g,"$1").replace(new RegExp("[^\\\d"+separator+"]","g"),'').replace(/,/,'.')) || 0;
            }
            return val || 0;
        };
    };

    // Numeric Sort   
    // ------------
    sort.numeric = function(a,b) {
        return sort.numeric.convert(a)-sort.numeric.convert(b);
    };
    sort.numeric.convert = sort.numeric_converter(".");

    // Numeric Sort    - comma decimal separator
    // --------------------------------------
    sort.numeric_comma = function(a,b) {
        return sort.numeric_comma.convert(a)-sort.numeric_comma.convert(b);
    };
    sort.numeric_comma.convert = sort.numeric_converter(",");

    // Case-insensitive Sort
    // ---------------------
    sort.ignorecase = function(a,b) {
        return sort.alphanumeric(sort.ignorecase.convert(a),sort.ignorecase.convert(b));
    };
    sort.ignorecase.convert = function(val) {
        if (val==null) { return ""; }
        return (""+val).toLowerCase();
    };

    // Currency Sort
    // -------------
    sort.currency = sort.numeric; // Just treat it as numeric!
    sort.currency_comma = sort.numeric_comma;

    // Date sort
    // ---------
    sort.date = function(a,b) {
        return sort.numeric(sort.date.convert(a),sort.date.convert(b));
    };
    // Convert 2-digit years to 4
    sort.date.fixYear=function(yr) {
        yr = +yr;
        if (yr<50) { yr += 2000; }
        else if (yr<100) { yr += 1900; }
        return yr;
    };
    sort.date.formats = [
        // YY[YY]-MM-DD
        { re:/(\d{2,4})-(\d{1,2})-(\d{1,2})/ , f:function(x){ return (new Date(sort.date.fixYear(x[1]),+x[2],+x[3])).getTime(); } }
        // MM/DD/YY[YY] or MM-DD-YY[YY]
        ,{ re:/(\d{1,2})[\/-](\d{1,2})[\/-](\d{2,4})/ , f:function(x){ return (new Date(sort.date.fixYear(x[3]),+x[1],+x[2])).getTime(); } }
        // Any catch-all format that new Date() can handle. This is not reliable except for long formats, for example: 31 Jan 2000 01:23:45 GMT
        ,{ re:/(.*\d{4}.*\d+:\d+\d+.*)/, f:function(x){ var d=new Date(x[1]); if(d){return d.getTime();} } }
    ];
    sort.date.convert = function(val) {
        var m,v, f = sort.date.formats;
        for (var i=0,L=f.length; i<L; i++) {
            if (m=val.match(f[i].re)) {
                v=f[i].f(m);
                if (typeof(v)!="undefined") { return v; }
            }
        }
        return 9999999999999; // So non-parsed dates will be last, not first
    };

    return sort;
})();

/**
 * The main Table namespace
 */
var Table = (function(){

    /**
     * Determine if a reference is defined
     */
    function def(o) {return (typeof o!="undefined");};

    /**
     * Determine if an object or class string contains a given class.
     */
    function hasClass(o,name) {
        return new RegExp("(^|\\s)"+name+"(\\s|$)").test(o.className);
    };

    /**
     * Add a class to an object
     */
    function addClass(o,name) {
        var c = o.className || "";
        if (def(c) && !hasClass(o,name)) {
            o.className += (c?" ":"") + name;
        }
    };

    /**
     * Remove a class from an object
     */
    function removeClass(o,name) {
        var c = o.className || "";
        o.className = c.replace(new RegExp("(^|\\s)"+name+"(\\s|$)"),"$1");
    };

    /**
     * For classes that match a given substring, return the rest
     */
    function classValue(o,prefix) {
        var c = o.className;
        if (c.match(new RegExp("(^|\\s)"+prefix+"([^ ]+)"))) {
            return RegExp.$2;
        }
        return null;
    };

    /**
     * Return true if an object is hidden.
     * This uses the "russian doll" technique to unwrap itself to the most efficient
     * function after the first pass. This avoids repeated feature detection that
     * would always fall into the same block of code.
     */
     function isHidden(o) {
        if (window.getComputedStyle) {
            var cs = window.getComputedStyle;
            return (isHidden = function(o) {
                return 'none'==cs(o,null).getPropertyValue('display');
            })(o);
        }
        else if (window.currentStyle) {
            return(isHidden = function(o) {
                return 'none'==o.currentStyle['display'];
            })(o);
        }
        return (isHidden = function(o) {
            return 'none'==o.style['display'];
        })(o);
    };

    /**
     * Get a parent element by tag name, or the original element if it is of the tag type
     */
    function getParent(o,a,b) {
        if (o!=null && o.nodeName) {
            if (o.nodeName==a || (b && o.nodeName==b)) {
                return o;
            }
            while (o=o.parentNode) {
                if (o.nodeName && (o.nodeName==a || (b && o.nodeName==b))) {
                    return o;
                }
            }
        }
        return null;
    };

    /**
     * Utility function to copy properties from one object to another
     */
    function copy(o1,o2) {
        for (var i=2;i<arguments.length; i++) {
            var a = arguments[i];
            if (def(o1[a])) {
                o2[a] = o1[a];
            }
        }
    }

    // The table object itself
    var table = {
        //Class names used in the code
        AutoStripeClassName:"table-autostripe",
        StripeClassNamePrefix:"table-stripeclass:",

        AutoSortClassName:"table-autosort",
        AutoSortColumnPrefix:"table-autosort:",
        AutoSortTitle:"Click to sort",
        SortedAscendingClassName:"table-sorted-asc",
        SortedDescendingClassName:"table-sorted-desc",
        SortableClassName:"table-sortable",
        SortableColumnPrefix:"table-sortable:",
        NoSortClassName:"table-nosort",

        AutoFilterClassName:"table-autofilter",
        FilteredClassName:"table-filtered",
        FilterableClassName:"table-filterable",
        FilteredRowcountPrefix:"table-filtered-rowcount:",
        RowcountPrefix:"table-rowcount:",
        FilterAllLabel:"Filter: All",

        AutoPageSizePrefix:"table-autopage:",
        AutoPageJumpPrefix:"table-page:",
        PageNumberPrefix:"table-page-number:",
        PageCountPrefix:"table-page-count:"
    };

    /**
     * A place to store misc table information, rather than in the table objects themselves
     */
    table.tabledata = {};

    /**
     * Resolve a table given an element reference, and make sure it has a unique ID
     */
    table.uniqueId=1;
    table.resolve = function(o,args) {
        if (o!=null && o.nodeName && o.nodeName!="TABLE") {
            o = getParent(o,"TABLE");
        }
        if (o==null) { return null; }
        if (!o.id) {
            var id = null;
            do { var id = "TABLE_"+(table.uniqueId++); }
                while (document.getElementById(id)!=null);
            o.id = id;
        }
        this.tabledata[o.id] = this.tabledata[o.id] || {};
        if (args) {
            copy(args,this.tabledata[o.id],"stripeclass","ignorehiddenrows","useinnertext","sorttype","col","desc","page","pagesize");
        }
        return o;
    };


    /**
     * Run a function against each cell in a table header or footer, usually
     * to add or remove css classes based on sorting, filtering, etc.
     */
    table.processTableCells = function(t, type, func, arg) {
        t = this.resolve(t);
        if (t==null) { return; }
        if (type!="TFOOT") {
            this.processCells(t.tHead, func, arg);
        }
        if (type!="THEAD") {
            this.processCells(t.tFoot, func, arg);
        }
    };

    /**
     * Internal method used to process an arbitrary collection of cells.
     * Referenced by processTableCells.
     * It's done this way to avoid getElementsByTagName() which would also return nested table cells.
     */
    table.processCells = function(section,func,arg) {
        if (section!=null) {
            if (section.rows && section.rows.length && section.rows.length>0) {
                var rows = section.rows;
                for (var j=0,L2=rows.length; j<L2; j++) {
                    var row = rows[j];
                    if (row.cells && row.cells.length && row.cells.length>0) {
                        var cells = row.cells;
                        for (var k=0,L3=cells.length; k<L3; k++) {
                            var cellsK = cells[k];
                            func.call(this,cellsK,arg);
                        }
                    }
                }
            }
        }
    };

    /**
     * Get the cellIndex value for a cell. This is only needed because of a Safari
     * bug that causes cellIndex to exist but always be 0.
     * Rather than feature-detecting each time it is called, the function will
     * re-write itself the first time it is called.
     */
    table.getCellIndex = function(td) {
        var tr = td.parentNode;
        var cells = tr.cells;
        if (cells && cells.length) {
            if (cells.length>1 && cells[cells.length-1].cellIndex>0) {
                // Define the new function, overwrite the one we're running now, and then run the new one
                (this.getCellIndex = function(td) {
                    return td.cellIndex;
                })(td);
            }
            // Safari will always go through this slower block every time. Oh well.
            for (var i=0,L=cells.length; i<L; i++) {
                if (tr.cells[i]==td) {
                    return i;
                }
            }
        }
        return 0;
    };

    /**
     * A map of node names and how to convert them into their "value" for sorting, filtering, etc.
     * These are put here so it is extensible.
     */
    table.nodeValue = {
        'INPUT':function(node) {
            if (def(node.value) && node.type && ((node.type!="checkbox" && node.type!="radio") || node.checked)) {
                return node.value;
            }
            return "";
        },
        'SELECT':function(node) {
            if (node.selectedIndex>=0 && node.options) {
                // Sort select elements by the visible text
                return node.options[node.selectedIndex].text;
            }
            return "";
        },
        'IMG':function(node) {
            return node.name || "";
        }
    };

    /**
     * Get the text value of a cell. Only use innerText if explicitly told to, because
     * otherwise we want to be able to handle sorting on inputs and other types
     */
    table.getCellValue = function(td,useInnerText) {
        if (useInnerText && def(td.innerText)) {
            return td.innerText;
        }
        if (!td.childNodes) {
            return "";
        }
        var childNodes=td.childNodes;
        var ret = "";
        for (var i=0,L=childNodes.length; i<L; i++) {
            var node = childNodes[i];
            var type = node.nodeType;
            // In order to get realistic sort results, we need to treat some elements in a special way.
            // These behaviors are defined in the nodeValue() object, keyed by node name
            if (type==1) {
                var nname = node.nodeName;
                if (this.nodeValue[nname]) {
                    ret += this.nodeValue[nname](node);
                }
                else {
                    ret += this.getCellValue(node);
                }
            }
            else if (type==3) {
                if (def(node.innerText)) {
                    ret += node.innerText;
                }
                else if (def(node.nodeValue)) {
                    ret += node.nodeValue;
                }
            }
        }
        return ret;
    };

    /**
     * Consider colspan and rowspan values in table header cells to calculate the actual cellIndex
     * of a given cell. This is necessary because if the first cell in row 0 has a rowspan of 2,
     * then the first cell in row 1 will have a cellIndex of 0 rather than 1, even though it really
     * starts in the second column rather than the first.
     * See: http://www.javascripttoolbox.com/temp/table_cellindex.html
     */
    table.tableHeaderIndexes = {};
    table.getActualCellIndex = function(tableCellObj) {
        if (!def(tableCellObj.cellIndex)) { return null; }
        var tableObj = getParent(tableCellObj,"TABLE");
        var cellCoordinates = tableCellObj.parentNode.rowIndex+"-"+this.getCellIndex(tableCellObj);

        // If it has already been computed, return the answer from the lookup table
        if (def(this.tableHeaderIndexes[tableObj.id])) {
            return this.tableHeaderIndexes[tableObj.id][cellCoordinates];     
        }

        var matrix = [];
        this.tableHeaderIndexes[tableObj.id] = {};
        var thead = getParent(tableCellObj,"THEAD");
        var trs = thead.getElementsByTagName('TR');

        // Loop thru every tr and every cell in the tr, building up a 2-d array "grid" that gets
        // populated with an "x" for each space that a cell takes up. If the first cell is colspan
        // 2, it will fill in values [0] and [1] in the first array, so that the second cell will
        // find the first empty cell in the first row (which will be [2]) and know that this is
        // where it sits, rather than its internal .cellIndex value of [1].
        for (var i=0; i<trs.length; i++) {
            var cells = trs[i].cells;
            for (var j=0; j<cells.length; j++) {
                var c = cells[j];
                var rowIndex = c.parentNode.rowIndex;
                var cellId = rowIndex+"-"+this.getCellIndex(c);
                var rowSpan = c.rowSpan || 1;
                var colSpan = c.colSpan || 1;
                var firstAvailCol;
                if(!def(matrix[rowIndex])) {
                    matrix[rowIndex] = [];
                }
                var m = matrix[rowIndex];
                // Find first available column in the first row
                for (var k=0; k<m.length+1; k++) {
                    if (!def(m[k])) {
                        firstAvailCol = k;
                        break;
                    }
                }
                this.tableHeaderIndexes[tableObj.id][cellId] = firstAvailCol;
                for (var k=rowIndex; k<rowIndex+rowSpan; k++) {
                    if(!def(matrix[k])) {
                        matrix[k] = [];
                    }
                    var matrixrow = matrix[k];
                    for (var l=firstAvailCol; l<firstAvailCol+colSpan; l++) {
                        matrixrow[l] = "x";
                    }
                }
            }
        }
        // Store the map so future lookups are fast.
        return this.tableHeaderIndexes[tableObj.id][cellCoordinates];
    };

    /**
     * Sort all rows in each TBODY (tbodies are sorted independent of each other)
     */
    table.sort = function(o,args) {
        var t, tdata, sortconvert=null;
        // Allow for a simple passing of sort type as second parameter
        if (typeof(args)=="function") {
            args={sorttype:args};
        }
        args = args || {};

        // If no col is specified, deduce it from the object sent in
        if (!def(args.col)) {
            args.col = this.getActualCellIndex(o) || 0;
        }
        // If no sort type is specified, default to the default sort
        args.sorttype = args.sorttype || Sort['default'];

        // Resolve the table
        t = this.resolve(o,args);
        tdata = this.tabledata[t.id];

        // If we are sorting on the same column as last time, flip the sort direction
        if (def(tdata.lastcol) && tdata.lastcol==tdata.col && def(tdata.lastdesc)) {
            tdata.desc = !tdata.lastdesc;
        }
        else {
            tdata.desc = !!args.desc;
        }

        // Store the last sorted column so clicking again will reverse the sort order
        tdata.lastcol=tdata.col;
        tdata.lastdesc=!!tdata.desc;

        // If a sort conversion function exists, pre-convert cell values and then use a plain alphanumeric sort
        var sorttype = tdata.sorttype;
        if (typeof(sorttype.convert)=="function") {
            sortconvert=tdata.sorttype.convert;
            sorttype=Sort.alphanumeric;
        }

        // Loop through all THEADs and remove sorted class names, then re-add them for the col
        // that is being sorted
        this.processTableCells(t,"THEAD",
            function(cell) {
                if (hasClass(cell,this.SortableClassName)) {
                    removeClass(cell,this.SortedAscendingClassName);
                    removeClass(cell,this.SortedDescendingClassName);
                    // If the computed colIndex of the cell equals the sorted colIndex, flag it as sorted
                    if (tdata.col==table.getActualCellIndex(cell) && (classValue(cell,table.SortableClassName))) {
                        addClass(cell,tdata.desc?this.SortedAscendingClassName:this.SortedDescendingClassName);
                    }
                }
            }
        );

        // Sort each tbody independently
        var bodies = t.tBodies;
        if (bodies==null || bodies.length==0) { return; }

        // Define a new sort function to be called to consider descending or not
        var newSortFunc = (tdata.desc)?
            function(a,b){return sorttype(b[0],a[0]);}
            :function(a,b){return sorttype(a[0],b[0]);};

        var useinnertext=!!tdata.useinnertext;
        var col = tdata.col;

        for (var i=0,L=bodies.length; i<L; i++) {
            var tb = bodies[i], tbrows = tb.rows, rows = [];

            // Allow tbodies to request that they not be sorted
            if(!hasClass(tb,table.NoSortClassName)) {
                // Create a separate array which will store the converted values and refs to the
                // actual rows. This is the array that will be sorted.
                var cRow, cRowIndex=0;
                if (cRow=tbrows[cRowIndex]){
                    // Funky loop style because it's considerably faster in IE
                    do {
                        if (rowCells = cRow.cells) {
                            var cellValue = (col<rowCells.length)?this.getCellValue(rowCells[col],useinnertext):null;
                            if (sortconvert) cellValue = sortconvert(cellValue);
                            rows[cRowIndex] = [cellValue,tbrows[cRowIndex]];
                        }
                    } while (cRow=tbrows[++cRowIndex])
                }

                // Do the actual sorting
                rows.sort(newSortFunc);

                // Move the rows to the correctly sorted order. Appending an existing DOM object just moves it!
                cRowIndex=0;
                var displayedCount=0;
                var f=[removeClass,addClass];
                if (cRow=rows[cRowIndex]){
                    do {
                        tb.appendChild(cRow[1]);
                    } while (cRow=rows[++cRowIndex])
                }
            }
        }

        // If paging is enabled on the table, then we need to re-page because the order of rows has changed!
        if (tdata.pagesize) {
            this.page(t); // This will internally do the striping
        }
        else {
            // Re-stripe if a class name was supplied
            if (tdata.stripeclass) {
                this.stripe(t,tdata.stripeclass,!!tdata.ignorehiddenrows);
            }
        }
    };

    /**
    * Apply a filter to rows in a table and hide those that do not match.
    */
    table.filter = function(o,filters,args) {
        var cell;
        args = args || {};

        var t = this.resolve(o,args);
        var tdata = this.tabledata[t.id];

        // If new filters were passed in, apply them to the table's list of filters
        if (!filters) {
            // If a null or blank value was sent in for 'filters' then that means reset the table to no filters
            tdata.filters = null;
        }
        else {
            // Allow for passing a select list in as the filter, since this is common design
            if (filters.nodeName=="SELECT" && filters.type=="select-one" && filters.selectedIndex>-1) {
                filters={ 'filter':filters.options[filters.selectedIndex].value };
            }
            // Also allow for a regular input
            if (filters.nodeName=="INPUT" && filters.type=="text") {
                filters={ 'filter':"/^"+filters.value+"/" };
            }
            // Force filters to be an array
            if (typeof(filters)=="object" && !filters.length) {
                filters = [filters];
            }

            // Convert regular expression strings to RegExp objects and function strings to function objects
            for (var i=0,L=filters.length; i<L; i++) {
                var filter = filters[i];
                if (typeof(filter.filter)=="string") {
                    // If a filter string is like "/expr/" then turn it into a Regex
                    if (filter.filter.match(/^\/(.*)\/$/)) {
                        filter.filter = new RegExp(RegExp.$1);
                        filter.filter.regex=true;
                    }
                    // If filter string is like "function (x) { ... }" then turn it into a function
                    else if (filter.filter.match(/^function\s*\(([^\)]*)\)\s*\{(.*)}\s*$/)) {
                        filter.filter = Function(RegExp.$1,RegExp.$2);
                    }
                }
                // If some non-table object was passed in rather than a 'col' value, resolve it
                // and assign it's column index to the filter if it doesn't have one. This way,
                // passing in a cell reference or a select object etc instead of a table object
                // will automatically set the correct column to filter.
                if (filter && !def(filter.col) && (cell=getParent(o,"TD","TH"))) {
                    filter.col = this.getCellIndex(cell);
                }

                // Apply the passed-in filters to the existing list of filters for the table, removing those that have a filter of null or ""
                if ((!filter || !filter.filter) && tdata.filters) {
                    delete tdata.filters[filter.col];
                }
                else {
                    tdata.filters = tdata.filters || {};
                    tdata.filters[filter.col] = filter.filter;
                }
            }
            // If no more filters are left, then make sure to empty out the filters object
            for (var j in tdata.filters) { var keep = true; }
            if (!keep) {
                tdata.filters = null;
            }
        }       
        // Everything's been setup, so now scrape the table rows
        return table.scrape(o);
    };

    /**
     * "Page" a table by showing only a subset of the rows
     */
    table.page = function(t,page,args) {
        args = args || {};
        if (def(page)) { args.page = page; }
        return table.scrape(t,args);
    };

    /**
     * Jump forward or back any number of pages
     */
    table.pageJump = function(t,count,args) {
        t = this.resolve(t,args);
        return this.page(t,(table.tabledata[t.id].page||0)+count,args);
    };

    /**
     * Go to the next page of a paged table
     */   
    table.pageNext = function(t,args) {
        return this.pageJump(t,1,args);
    };

    /**
     * Go to the previous page of a paged table
     */   
    table.pagePrevious = function(t,args) {
        return this.pageJump(t,-1,args);
    };

    /**
    * Scrape a table to either hide or show each row based on filters and paging
    */
    table.scrape = function(o,args) {
        var col,cell,filterList,filterReset=false,filter;
        var page,pagesize,pagestart,pageend;
        var unfilteredrows=[],unfilteredrowcount=0,totalrows=0;
        var t,tdata,row,hideRow;
        args = args || {};

        // Resolve the table object
        t = this.resolve(o,args);
        tdata = this.tabledata[t.id];

        // Setup for Paging
        var page = tdata.page;
        if (def(page)) {
            // Don't let the page go before the beginning
            if (page<0) { tdata.page=page=0; }
            pagesize = tdata.pagesize || 25; // 25=arbitrary default
            pagestart = page*pagesize+1;
            pageend = pagestart + pagesize - 1;
        }

        // Scrape each row of each tbody
        var bodies = t.tBodies;
        if (bodies==null || bodies.length==0) { return; }
        for (var i=0,L=bodies.length; i<L; i++) {
            var tb = bodies[i];
            for (var j=0,L2=tb.rows.length; j<L2; j++) {
                row = tb.rows[j];
                hideRow = false;

                // Test if filters will hide the row
                if (tdata.filters && row.cells) {
                    var cells = row.cells;
                    var cellsLength = cells.length;
                    // Test each filter
                    for (col in tdata.filters) {
                        if (!hideRow) {
                            filter = tdata.filters[col];
                            if (filter && col<cellsLength) {
                                var val = this.getCellValue(cells[col]);
                                if (filter.regex && val.search) {
                                    hideRow=(val.search(filter)<0);
                                }
                                else if (typeof(filter)=="function") {
                                    hideRow=!filter(val,cells[col]);
                                }
                                else {
                                    hideRow = (val!=filter);
                                }
                            }
                        }
                    }
                }

                // Keep track of the total rows scanned and the total runs _not_ filtered out
                totalrows++;
                if (!hideRow) {
                    unfilteredrowcount++;
                    if (def(page)) {
                        // Temporarily keep an array of unfiltered rows in case the page we're on goes past
                        // the last page and we need to back up. Don't want to filter again!
                        unfilteredrows.push(row);
                        if (unfilteredrowcount<pagestart || unfilteredrowcount>pageend) {
                            hideRow = true;
                        }
                    }
                }

                row.style.display = hideRow?"none":"";
            }
        }

        if (def(page)) {
            // Check to see if filtering has put us past the requested page index. If it has,
            // then go back to the last page and show it.
            if (pagestart>=unfilteredrowcount) {
                pagestart = unfilteredrowcount-(unfilteredrowcount%pagesize);
                tdata.page = page = pagestart/pagesize;
                for (var i=pagestart,L=unfilteredrows.length; i<L; i++) {
                    unfilteredrows[i].style.display="";
                }
            }
        }

        // Loop through all THEADs and add/remove filtered class names
        this.processTableCells(t,"THEAD",
            function(c) {
                ((tdata.filters && def(tdata.filters[table.getCellIndex(c)]) && hasClass(c,table.FilterableClassName))?addClass:removeClass)(c,table.FilteredClassName);
            }
        );

        // Stripe the table if necessary
        if (tdata.stripeclass) {
            this.stripe(t);
        }

        // Calculate some values to be returned for info and updating purposes
        var pagecount = Math.floor(unfilteredrowcount/pagesize)+1;
        if (def(page)) {
            // Update the page number/total containers if they exist
            if (tdata.container_number) {
                tdata.container_number.innerHTML = page+1;
            }
            if (tdata.container_count) {
                tdata.container_count.innerHTML = pagecount;
            }
        }

        // Update the row count containers if they exist
        if (tdata.container_filtered_count) {
            tdata.container_filtered_count.innerHTML = unfilteredrowcount;
        }
        if (tdata.container_all_count) {
            tdata.container_all_count.innerHTML = totalrows;
        }
        return { 'data':tdata, 'unfilteredcount':unfilteredrowcount, 'total':totalrows, 'pagecount':pagecount, 'page':page, 'pagesize':pagesize };
    };

    /**
     * Shade alternate rows, aka Stripe the table.
     */
    table.stripe = function(t,className,args) {
        args = args || {};
        args.stripeclass = className;

        t = this.resolve(t,args);
        var tdata = this.tabledata[t.id];

        var bodies = t.tBodies;
        if (bodies==null || bodies.length==0) {
            return;
        }

        className = tdata.stripeclass;
        // Cache a shorter, quicker reference to either the remove or add class methods
        var f=[removeClass,addClass];
        for (var i=0,L=bodies.length; i<L; i++) {
            var tb = bodies[i], tbrows = tb.rows, cRowIndex=0, cRow, displayedCount=0;
            if (cRow=tbrows[cRowIndex]){
                // The ignorehiddenrows test is pulled out of the loop for a slight speed increase.
                // Makes a bigger difference in FF than in IE.
                // In this case, speed always wins over brevity!
                if (tdata.ignoreHiddenRows) {
                    do {
                        f[displayedCount++%2](cRow,className);
                    } while (cRow=tbrows[++cRowIndex])
                }
                else {
                    do {
                        if (!isHidden(cRow)) {
                            f[displayedCount++%2](cRow,className);
                        }
                    } while (cRow=tbrows[++cRowIndex])
                }
            }
        }
    };

    /**
     * Build up a list of unique values in a table column
     */
    table.getUniqueColValues = function(t,col) {
        var values={}, bodies = this.resolve(t).tBodies;
        for (var i=0,L=bodies.length; i<L; i++) {
            var tbody = bodies[i];
            for (var r=0,L2=tbody.rows.length; r<L2; r++) {
                values[this.getCellValue(tbody.rows[r].cells[col])] = true;
            }
        }
        var valArray = [];
        for (var val in values) {
            valArray.push(val);
        }
        return valArray.sort();
    };

    /**
     * Scan the document on load and add sorting, filtering, paging etc ability automatically
     * based on existence of class names on the table and cells.
     */
    table.auto = function(args) {
        var cells = [], tables = document.getElementsByTagName("TABLE");
        var val,tdata;
        if (tables!=null) {
            for (var i=0,L=tables.length; i<L; i++) {
                var t = table.resolve(tables[i]);
                tdata = table.tabledata[t.id];
                if (val=classValue(t,table.StripeClassNamePrefix)) {
                    tdata.stripeclass=val;
                }
                // Do auto-filter if necessary
                if (hasClass(t,table.AutoFilterClassName)) {
                    table.autofilter(t);
                }
                // Do auto-page if necessary
                if (val = classValue(t,table.AutoPageSizePrefix)) {
                    table.autopage(t,{'pagesize':+val});
                }
                // Do auto-sort if necessary
                if ((val = classValue(t,table.AutoSortColumnPrefix)) || (hasClass(t,table.AutoSortClassName))) {
                    table.autosort(t,{'col':(val==null)?null:+val});
                }
                // Do auto-stripe if necessary
                if (tdata.stripeclass && hasClass(t,table.AutoStripeClassName)) {
                    table.stripe(t);
                }
            }
        }
    };

    /**
     * Add sorting functionality to a table header cell
     */
    table.autosort = function(t,args) {
        t = this.resolve(t,args);
        var tdata = this.tabledata[t.id];
        this.processTableCells(t, "THEAD", function(c) {
            var type = classValue(c,table.SortableColumnPrefix);
            if (type!=null) {
                type = type || "default";
                c.title =c.title || table.AutoSortTitle;
                addClass(c,table.SortableClassName);
                c.onclick = Function("","Table.sort(this,{'sorttype':Sort['"+type+"']})");
                // If we are going to auto sort on a column, we need to keep track of what kind of sort it will be
                if (args.col!=null) {
                    if (args.col==table.getActualCellIndex(c)) {
                        tdata.sorttype=Sort['"+type+"'];
                    }
                }
            }
        } );
        if (args.col!=null) {
            table.sort(t,args);
        }
    };

    /**
     * Add paging functionality to a table
     */
    table.autopage = function(t,args) {
        t = this.resolve(t,args);
        var tdata = this.tabledata[t.id];
        if (tdata.pagesize) {
            this.processTableCells(t, "THEAD,TFOOT", function(c) {
                var type = classValue(c,table.AutoPageJumpPrefix);
                if (type=="next") { type = 1; }
                else if (type=="previous") { type = -1; }
                if (type!=null) {
                    c.onclick = Function("","Table.pageJump(this,"+type+")");
                }
            } );
            if (val = classValue(t,table.PageNumberPrefix)) {
                tdata.container_number = document.getElementById(val);
            }
            if (val = classValue(t,table.PageCountPrefix)) {
                tdata.container_count = document.getElementById(val);
            }
            return table.page(t,0,args);
        }
    };

    /**
     * A util function to cancel bubbling of clicks on filter dropdowns
     */
    table.cancelBubble = function(e) {
        e = e || window.event;
        if (typeof(e.stopPropagation)=="function") { e.stopPropagation(); }
        if (def(e.cancelBubble)) { e.cancelBubble = true; }
    };

    /**
     * Auto-filter a table
     */
    table.autofilter = function(t,args) {
        args = args || {};
        t = this.resolve(t,args);
        var tdata = this.tabledata[t.id],val;
        table.processTableCells(t, "THEAD", function(cell) {
            if (hasClass(cell,table.FilterableClassName)) {
                var cellIndex = table.getCellIndex(cell);
                var colValues = table.getUniqueColValues(t,cellIndex);
                if (colValues.length>0) {
                    if (typeof(args.insert)=="function") {
                        func.insert(cell,colValues);
                    }
                    else {
                        var sel = '<select onchange="Table.filter(this,this)" onclick="Table.cancelBubble(event)" class="'+table.AutoFilterClassName+'"><option value="">'+table.FilterAllLabel+'</option>';
                        for (var i=0; i<colValues.length; i++) {
                            sel += '<option value="'+colValues[i]+'">'+colValues[i]+'</option>';
                        }
                        sel += '</select>';
                        cell.innerHTML += "<br>"+sel;
                    }
                }
            }
        });
        if (val = classValue(t,table.FilteredRowcountPrefix)) {
            tdata.container_filtered_count = document.getElementById(val);
        }
        if (val = classValue(t,table.RowcountPrefix)) {
            tdata.container_all_count = document.getElementById(val);
        }
    };

    /**
     * Attach the auto event so it happens on load.
     * use jQuery's ready() function if available
     */
    if (typeof(jQuery)!="undefined") {
        jQuery(table.auto);
    }
    else if (window.addEventListener) {
        window.addEventListener( "load", table.auto, false );
    }
    else if (window.attachEvent) {
        window.attachEvent( "onload", table.auto );
    }

    return table;
})();