package ModSQL;
import java.io.*;
import java.sql.*;
import java.util.*;

/* $Id: Select.java,v 1.43 2003/09/24 19:59:34 cvs Exp $
 *
 * Copyright (c) 2003 Chris Studholme <chris.studholme@utoronto.ca>
 *
 * May be copied or modified under the terms of the GNU General Public
 * License.  See COPYING for more information.
 */

/**
 * <p>Class to parse and execute an SQL SELECT statement.  This class
 * implements Table, RowConstructor and Query so that it can behave as
 * any one of these interfaces dictates, although some queries may not
 * be compatable with some of these behaviours.
 *
 * <p>In the case of Query, the constuctor does the parsing, and execute
 * will call optimize and may actually execute the query too.
 *
 * <p>In the case of RowConstructor or Table, the constructor still does
 * the parsing, but the user is expected to explicitly call optimize
 * before attempting to evaluate rows.
 *
 * @author chris.studholme@utoronto.ca
 */
final class Select implements RowConstructor, Table, FunctionProvider, Query {

  /** Constant true value as Boolean object. */
  public static final Boolean TRUE_VALUE = new Boolean(true);

  /** True if SELECT DISTINCT. */
  private boolean distinct=false;
  /** HashSet used to detect and remove duplicate rows. */
  private HashSet distinct_set=null;

  /** Array of columns to select. */
  private Function[] columns=null;
  /** Names of columns. */
  private String[] column_names=null;
  /** Column values for current row. */
  private Object[] column_values=null;
   
  /** List of tables from which rows are read. */
  private DatabaseTable[] table_list=null;
  /** Alternate names for tables (aliases). */
  private String[] table_aliases=null;

  /** WHERE clause used to select rows of interest. */
  private Function where=null;

  /** Functions to GROUP BY. */
  private Function[] group_by=null;
  /** Names of columns to GROUP BY. */
  private String[] group_by_names=null;
  /** HAVING clause used to select groups of interest. */
  private Function having=null;

  /** List of functions to ORDER BY. */
  private Function[] order_by=null;
  /** ORDER BY order: true for ascending, false for decending. */
  private boolean[] order_by_dir=null;  
  /** Indices into columns array. */
  private int[] order_by_indices=null;  
  /** Flag indicating that order_by entry is dup of columns entry. */
  private boolean[] order_by_dup=null;

  /** Index in columns of start of ORDER BY. */
  private int start_order;
  /** Index in columns of start of HAVING. */
  private int start_having; 
  /** Index in columns of start of GROUP BY. */
  private int start_group;
  /** Index in columns of start of WHERE. */
  private int start_where;

  /** Table manager used to open tables. */
  private transient DatabaseManager manager;
  /** Reader to get database rows from. */
  private transient TableReader reader;

  /** Are we grouping or aggregating? */
  private boolean aggregate=false;
  /** Has optimize been called? */
  private boolean optimized=false;

  /** Cached rows. */
  private List rows=null;
  /** Current row in cached rows. */
  private int current_row=-1;
  /** Array of null references to return as a null row. */
  private Object[] null_row=null; 


  /**
   * Contructor to parse query.
   *
   * @param tokenizer StreamTokenizer that SQL tokens should be read from
   * @param manager manager to use when looking up tables
   * @throws SQLException if an error occurs
   * @throws IOException if there is a problem reading the query
   */
  protected Select(StreamTokenizer tokenizer, DatabaseManager manager) 
    throws SQLException, IOException {
    this.manager = manager;
    reader=null;
    parseSelect(tokenizer);
  }

  /**
   * Close all tables.
   */
  public void close() {
    if (table_list!=null)
      for (int i=0; i<table_list.length; ++i) {
	try {
	  table_list[i].close();
	}
	catch (Exception e) {
	}
      }
    table_list=null;
    distinct_set=null;
  }

  /**
   * Close all tables.
   */
  protected void finalize() {
    close();
  }


  /****************  parsing methods  ****************/

  /**
   * Parse entire SELECT query.
   *
   * @param tokenizer StreamTokenizer that SQL tokens should be read from
   * @throws SQLException if an error occurs
   * @throws IOException if there is a problem reading the query
   */   
  private void parseSelect(StreamTokenizer tokenizer)
    throws SQLException, IOException {
    
    if ((tokenizer.ttype!=tokenizer.TT_WORD)||
	(!tokenizer.sval.equals("select")))
      throw new SQLException("'SELECT' expected");

    if (tokenizer.nextToken()==tokenizer.TT_WORD) {
      if (tokenizer.sval.equals("distinct")) {
	distinct=true;
	tokenizer.nextToken();
      }
      else if (tokenizer.sval.equals("all")) 
	tokenizer.nextToken();
    }
    
    // parse SELECT list
    ArrayList columns_array = new ArrayList();
    ArrayList column_names_array = new ArrayList();
    while (true) {

      Function value=null;
      if (tokenizer.ttype=='*') {
	value = new IndirectFunction("*");
	tokenizer.nextToken();
      }
      else
	value = Expression.parseExpression(tokenizer,manager);
      columns_array.add(value);

      // check for 'AS' keyword
      if (tokenizer.ttype==tokenizer.TT_WORD &&
	  tokenizer.sval.equals("as"))
	tokenizer.nextToken();

      // check for column name
      switch (tokenizer.ttype) {
      case '\'':
      case '"':
	column_names_array.add(tokenizer.sval);
	tokenizer.nextToken();
	break;

      case StreamTokenizer.TT_WORD:
	if (!Expression.isKeyword(tokenizer.sval)) {
	  StringBuffer buf = new StringBuffer(tokenizer.sval);
	  while (tokenizer.nextToken()==tokenizer.TT_WORD &&
		 !Expression.isKeyword(tokenizer.sval))
	    buf.append(" ").append(tokenizer.sval);
	  column_names_array.add(buf.toString());
	  break;
	}

      default:
	column_names_array.add(null);
      }

      if (tokenizer.ttype!=',') 
	break;
      tokenizer.nextToken();
    } 
    
    // parse FROM list
    if (tokenizer.ttype!=tokenizer.TT_WORD ||
	!tokenizer.sval.equals("from"))
      throw new SQLException("'FROM' expected at or before "+tokenizer);
    ArrayList table_names = new ArrayList();
    ArrayList table_alias = new ArrayList();
    ArrayList table_value = new ArrayList();
    Function join = null;    // conjunct to add to where
    String join_with = null; // name or alias of table to join with
    tokenizer.nextToken();

    while (true) {
      String table_name = null;

      // table subquery
      if (tokenizer.ttype=='(') {
	Table t = Expression.parseTableExpression(tokenizer,manager);
	table_name = "#"+(table_names.size()+1);
	table_names.add(table_name);
	table_value.add(t);
      }
      
      else if (tokenizer.ttype!=tokenizer.TT_WORD)
	throw new SQLException("table name expected at or before "+tokenizer);
      
      else {
	table_name = tokenizer.sval;
	table_names.add(table_name);
	table_value.add(null);
	tokenizer.nextToken();
      }

      // skip over 'AS' if present
      if (tokenizer.ttype==tokenizer.TT_WORD &&
	  tokenizer.sval.equals("as"))
	tokenizer.nextToken();

      // check for alias
      if ((tokenizer.ttype==tokenizer.TT_WORD)&&
	  (!Expression.isKeyword(tokenizer.sval))) {
	table_name = tokenizer.sval;
	table_alias.add(table_name);
	tokenizer.nextToken();
      }
      else
	table_alias.add(null);

      // finish join with previous table
      if (join_with!=null) {
	if (tokenizer.ttype!=tokenizer.TT_WORD)
	  throw new SQLException("'ON' or 'USING' expected at or before "+
				 tokenizer);
	if (tokenizer.sval.equals("on")) {
	  tokenizer.nextToken();
	  Function v = 
	    Expression.parseExpression(tokenizer,manager);
	  if (join==null)
	    join = v;
	  else {
	    Function f = new Operator_Logical(true);
	    f.addParameter(join);
	    f.addParameter(v);
	    join = f;
	  }
	}
	else if (tokenizer.sval.equals("using")) {
	  if (tokenizer.nextToken()!='(')
	    throw new SQLException("'(' expected at or before "+tokenizer);
	  do {
	    tokenizer.nextToken();
	    if (tokenizer.ttype!=StreamTokenizer.TT_WORD)
	      throw new SQLException("column name expected at or before "+
				     tokenizer);
	    Function v = new Operator_Compare(Operator_Compare.EQU);
	    v.addParameter(new IndirectFunction(join_with+'.'+tokenizer.sval));
	    v.addParameter(new IndirectFunction(table_name+'.'+tokenizer.sval));
	    if (join==null)
	      join = v;
	    else {
	      Function f = new Operator_Logical(true);
	      f.addParameter(join);
	      f.addParameter(v);
	      join = f;
	    }
	  } while (tokenizer.nextToken()==',');
	  if (tokenizer.ttype!=')')
	    throw new SQLException("')' expected at or before "+tokenizer);
	  tokenizer.nextToken();
	}
	else
	  throw new SQLException("'ON' or 'USING' expected at or before "+
				 tokenizer);
	join_with = null;
      }

      // check for join with next table
      if (tokenizer.ttype==StreamTokenizer.TT_WORD && 
	  tokenizer.sval.equals("join")) {
	join_with = table_name;
      }
      else if (tokenizer.ttype!=',') 
	break;
      tokenizer.nextToken();
    }

    // lookup tables using the DatabaseManager
    table_list = new DatabaseTable[table_names.size()];
    table_aliases = new String[table_names.size()];

    for (int i=0; i<table_names.size(); ++i) {
      DatabaseTable table=null;
      String table_name = (String)table_names.get(i);
      Table tv = (Table)table_value.get(i);
      if (tv!=null) {
	// setup SelectTable
	tv.optimize();
	table = new SelectTable(tv,table_name);
      }
      else {
	// just open the table
	table = manager.openTable(table_name);
      }
      if (table==null)
	throw new SQLException("table '"+table_name+"' not found");
      table_list[i] = table;
      table_aliases[i] = (String)table_alias.get(i);
    }


    // expand *'s in SELECT columns
    for (int i=0; i<columns_array.size(); ++i) {
      Object v = columns_array.get(i);
      if (v instanceof IndirectFunction) {
	String description = ((IndirectFunction)v).getDescription();
	if (description.endsWith("*")) {
	  int lastdot = description.lastIndexOf('.');
	  String tablename = lastdot>0 ? 
	    description.substring(0,lastdot) : null;
	  String columnname = lastdot>0 ? 
	    description.substring(lastdot+1) : description;
	  
	  // don't think this ever happens, but just in case
	  if (!columnname.equals("*"))
	    throw new SQLException("invalid column name '"+
				   description+"'");
	  
	  /* '*' is only allowed with one table selected, 
	   * otherwise must use tablename.*
	   */ 
	  if (tablename==null && table_list.length>1)
	    throw new SQLException("cannot use '*' with multiple tables");
	  
	  DatabaseTable table=null;
	  if (tablename!=null) {
	    for (int j=0; j<table_list.length; ++j) {
	      if (table_aliases[j]!=null) {
		if (tablename.equalsIgnoreCase(table_aliases[j])) {
		  table=table_list[j];
		  break;
		}
	      }
	      else if (tablename.
		       equalsIgnoreCase(table_list[j].getTableName())) {
		table=table_list[j];
		break;
	      }
	    }	      
	    if (table==null)
	      throw new SQLException("table '"+tablename+"' not found");
	  }
	  else {
	    table=table_list[0];
	    if (table==null)
	      throw new SQLException("table not found");
	    tablename=table_aliases[0]!=null ? 
	      table_aliases[0] : table.getTableName();
	  }

	  columns_array.remove(i);
	  column_names_array.remove(i);
	  
	  int j=0;
	  while ((columnname=table.getColumnName(++j))!=null) {
	    columns_array.add(i+j-1,
			      new IndirectFunction(tablename+"."+columnname));
	    column_names_array.add(i+j-1,null);
	  }
	}
      }
    }

    // create static arrays for SELECT columns
    columns = new Function[columns_array.size()];
    columns = (Function[])columns_array.toArray(columns);
    column_names = new String[column_names_array.size()];
    column_names = (String[])column_names_array.toArray(column_names);


    // parse remaining optional sections
    while (tokenizer.ttype==tokenizer.TT_WORD) {
      
      if (tokenizer.sval.equals("where")) {
	tokenizer.nextToken();
	where = Expression.parseExpression(tokenizer,manager);
      }

      else if (tokenizer.sval.equals("group")) {
	if (tokenizer.nextToken()!=tokenizer.TT_WORD ||
	    !tokenizer.sval.equals("by"))
	  throw new SQLException("'BY' expected at or before "+tokenizer);
	ArrayList group_by_array = new ArrayList();
	do {
	  if (tokenizer.nextToken()!=tokenizer.TT_WORD)
	    throw new SQLException("column name expected at or before "+
				   tokenizer);
	  group_by_array.add(tokenizer.sval);
	} while (tokenizer.nextToken()==',');
	group_by_names = new String[group_by_array.size()];
	group_by_names = (String[])group_by_array.toArray(group_by_names);
	group_by = new Function[group_by_names.length];
	for (int i=0; i<group_by_names.length; ++i)
	  group_by[i] = new IndirectFunction(group_by_names[i]);
      }
      
      else if (tokenizer.sval.equals("having")) {
	tokenizer.nextToken();
	having = Expression.parseExpression(tokenizer,manager);
      }

      else if (tokenizer.sval.equals("order")) {
	if (tokenizer.nextToken()!=tokenizer.TT_WORD ||
	    !tokenizer.sval.equals("by"))
	  throw new SQLException("'BY' expected at or before "+tokenizer);
	ArrayList order_by_array = new ArrayList();
	ArrayList direction = new ArrayList();
	do {
	  tokenizer.nextToken();
	  Function value =
	    Expression.parseExpression(tokenizer,manager);
	  order_by_array.add(value);
	  
	  // check for direction
	  if (tokenizer.ttype==tokenizer.TT_WORD) {
	    if (tokenizer.sval.equals("desc")) {
	      direction.add(new Boolean(false));
	      tokenizer.nextToken();
	    }

	    else if (tokenizer.sval.equals("asc")) {
	      direction.add(null);
	      tokenizer.nextToken();
	    }

	    else
	      direction.add(null);
	  }
	  else
	    direction.add(null);

	} while (tokenizer.ttype==',');

	order_by = new Function[order_by_array.size()];
	order_by = (Function[])order_by_array.toArray(order_by);
	order_by_dir = new boolean[direction.size()];
	for (int i=0; i<order_by_dir.length; ++i)
	  order_by_dir[i] = direction.get(i)==null;
      }
      
      else 
	break;
    } 

    // combine Join and where
    if (join!=null) {
      if (where==null)
	where=join;
      else {
	Function f = new Operator_Logical(true);
	f.addParameter(join);
	f.addParameter(where);
	where = f;
      }
    }

    // make sure GROUP BY goes with HAVING
    if (group_by==null && having!=null)
      throw new SQLException("HAVING requires GROUP BY");
  }

  /****************  parameter handling methods  ****************/

  /**
   * Get the number pf parameters currently supplied to this function.
   *
   * @return number of parameters
   */
  public int getParameterCount() {
    return 0;
  }

  /**
   * Get a particular parameter.  Always throws an exception as parameters
   * are not supported.
   *
   * @param index index of parameter to get
   * @return parameter (function)
   * @throws IndexOutOfBoundsException always
   */
  public Function getParameter(int index) {
    throw new IndexOutOfBoundsException("parameters not supported");
  }

  /**
   * Adds a value (function) to the list of parameters maintained by this
   * function.  Always throws an exception as parameters are not supported.
   *
   * @param item function to add
   * @throws SQLException always
   */
  public void addParameter(Function item) throws SQLException {
    throw new SQLException("parameters not supported");
  }

  /**
   * Specify the order in which the parameters should be evaluated.  Always
   * throws an exception as parameters are not supported.
   *
   * @param index index of parameter
   * @param order number indicating order in which parameter is evaluated
   * @throws IndexOutOfBoundsException always
   */
  public void evaluateOrder(int index, int order) {
    throw new IndexOutOfBoundsException("parameters not supported");
  }

  
  /****************  setup and optimize methods  ****************/
  
  /**
   * Lookup description in column_names array and return matching columns
   * entry if match is found.  This method returns null if no match was
   * found.
   *
   * @param description name of SELECT column to look for
   * @return Function object (possibly null)
   */
  public Function lookupFunction(String description) {
    for (int i=0; i<column_names.length; ++i)
      if (column_names[i]!=null &&
	  column_names[i].equalsIgnoreCase(description))
	return columns[i];
    return null;
  }

  /**
   * Most objects passed to this method will be passed on to all contained
   * function objects.  Two classes of objects are treated differntly.  
   * Select objects are blocked by this method, and TableReader objects
   * initiate setup of the TableReader needed by this object with the
   * passed TableReader as a parent.
   *
   * @param o object to register with
   * @throws SQLException if a database error occurs
   */
  public void registerWith(Object o) throws SQLException {
    if (o instanceof TableReader) {
      setupTableReader((TableReader)o);
    }
    else if (!(o instanceof Select)) {
      // propagate to contained Function objects
      for (int i=0; i<columns.length; ++i)
	columns[i].registerWith(o);
      if (where!=null)
	where.registerWith(o);
      if (group_by!=null)
	for (int i=0; i<group_by.length; ++i)
	  group_by[i].registerWith(o);
      if (having!=null)
	having.registerWith(o);
      if (order_by!=null)
	for (int i=0; i<order_by.length; ++i)
	  order_by[i].registerWith(o);
    }
  }

  /**
   * Create and setup TableReader object (with no parent).
   *
   * @throws SQLException if an error occurs
   */
  public void setupTableReader() throws SQLException {
    setupTableReader(null);
  }
  /**
   * Create and setup TableReader object.
   *
   * @param parent parent TableReader object
   * @throws SQLException if an error occurs
   */
  public void setupTableReader(TableReader parent) throws SQLException {
    if (reader!=null)
      throw new SQLException("reader already set up");

    // create TableReader
    reader = new TableReader(table_list,table_aliases,parent);

    // lookup column names in SELECT list
    for (int i=0; i<columns.length; ++i)
      columns[i].registerWith(reader);

    // lookup column names for ORDER BY
    start_order = reader.getColumnCount();
    if (order_by!=null)
      for (int i=0; i<order_by.length; ++i) {
	order_by[i].registerWith(this);
	order_by[i].registerWith(reader);
      }
    
    // lookup column names for HAVING
    start_having = reader.getColumnCount();
    if (having!=null) {
      having.registerWith(this);
      having.registerWith(reader);
    }

    // lookup column names for GROUP BY
    start_group = reader.getColumnCount();
    if (group_by!=null)
      for (int i=0; i<group_by.length; ++i)
	group_by[i].registerWith(reader);

    // lookup column names for WHERE
    start_where = reader.getColumnCount();
    if (where!=null)
      where.registerWith(reader);

    // mark group_by columns as aggregate in having, order_by and columns
    if (group_by!=null) {
      GroupByList list = new GroupByList();
      for (int i=0; i<columns.length; ++i)
	columns[i].registerWith(list);
      if (order_by!=null)
	for (int i=0; i<order_by.length; ++i)
	  order_by[i].registerWith(list);
      if (having!=null)
	having.registerWith(list);
    }

    // create order_by_indices and order_by_dup arrays
    if (order_by!=null) {
      order_by_indices = new int[order_by.length];
      Arrays.fill(order_by_indices,-1);
      order_by_dup = new boolean[order_by.length];
      Arrays.fill(order_by_dup,false);
      for (int i=0; i<order_by_indices.length; ++i) {
	if (order_by[i] instanceof IndirectFunction) {
	  Function f = ((IndirectFunction)order_by[i]).getFunction();
	  for (int j=0; j<columns.length; ++j) {
	    if (columns[j]==f ||
		(columns[j] instanceof IndirectFunction &&
		 ((IndirectFunction)columns[j]).getFunction()==f)) {
	      order_by_indices[i] = j;
	      order_by_dup[i] = columns[j]==f;
	      break;
	    }
	  }
	}
	if (distinct && order_by_indices[i]<0)
	  throw new SQLException("ORDER BY column must appear in SELECT");
      }
    }
  }

  /**
   * Optimize query and prepare for execution.
   *
   * @throws SQLException if an error occurs
   */
  public void optimize() throws SQLException {

    if (optimized)
      throw new SQLException("optimize called twice");

    if (reader==null)
      setupTableReader();

    if (where!=null)
      reader.optimizeParameterOrder(where);

    for (int i=0; i<columns.length; ++i)
      columns[i].optimize();
    if (order_by!=null)
      for (int i=0; i<order_by.length; ++i)
	order_by[i].optimize();
    if (having!=null)
      having.optimize();
    if (group_by!=null)
      for (int i=0; i<group_by.length; ++i)
	group_by[i].optimize();
    if (where!=null)
      where.optimize();

    // verify that WHERE does not contain aggregate functions
    if (where!=null && where.isAggregate())
      throw new SQLException("WHERE is an aggregate");

    // verify that HAVING is an aggregate function
    if (having!=null && !having.isAggregate())
      throw new SQLException("HAVING must be an aggregate");

    // figure out if we are aggregating/grouping or not
    aggregate = (group_by!=null);
    boolean non_aggregate = false;
    if (order_by!=null)
      for (int i=0; i<order_by.length; ++i) {
	if (order_by[i].isAggregate()) 
	  aggregate=true;
	else if (!order_by[i].isConstant()) 
	  non_aggregate=true;
      }
    for (int i=0; i<columns.length; ++i) {
      if (columns[i].isAggregate())
	aggregate=true;
      else if (!columns[i].isConstant())
	non_aggregate=true;
    }
    if (aggregate && non_aggregate)
      throw new SQLException("aggregate and non-aggregate functions");

    optimized=true;
  }



  /****************  information methods  ****************/

  /**
   * Returns human-readable string version of query (with surrounding 
   * brackets).
   *
   * @return String representation of query
   */
  public String toString() {
    return toString(true);
  }

  /**
   * Returns human-readable string version of query.
   *
   * @param with_brackets true to include surrounding brackets
   * @return String representation of query
   */
  public String toString(boolean with_brackets) {
    StringBuffer result = new StringBuffer();

    if (with_brackets)
      result.append('(');

    result.append("SELECT ");

    if (distinct)
      result.append("DISTINCT ");

    for (int i=0; i<columns.length; ++i) {
      if (i>0)
	result.append(",");
      result.append(columns[i]);
      if (column_names[i]!=null)
	result.append(" AS ").append(column_names[i]);
    }
    
    result.append(" FROM ");
    for (int i=0; i<table_list.length; ++i) {
      if (i>0)
	result.append(",");
      try {
	DatabaseTable table = table_list[i];
	if (table instanceof SelectTable) {
	  result.append("("+table+")");
	  if (table_aliases[i]==null)
	    result.append(' ').append(table.getTableName());
	}
	else
	  result.append(table.getTableName());
      }
      catch (Exception e) {
	result.append("<UNKNOWN>");
      }
      if (table_aliases[i]!=null)
	result.append(' ').append(table_aliases[i]);
    }

    if (where!=null) 
      result.append(" WHERE ").append(where);

    if (group_by!=null) {
      result.append(" GROUP BY ");
      result.append(group_by[0]);
      for (int i=1; i<group_by.length; ++i) {
	result.append(",");
	result.append(group_by[i]);
      }
      if (having!=null)
	result.append(" HAVING ").append(having);
    }

    if (order_by!=null) {
      result.append(" ORDER BY ");
      for (int i=0; i<order_by.length; ++i) {
	if (i>0)
	  result.append(",");
	result.append(order_by[i]);
	result.append(order_by_dir[i]?" ASC":" DESC");
      }
    }
    
    if (with_brackets)
      result.append(')');
    return result.toString();
  }
  
  /**
   * Select queries are never aggregate.
   *
   * @return false
   */
  public boolean isAggregate() {
    return false;
  }

  /**
   * A query is non-constant if it is a subquery that references columns
   * from its parent.
   *
   * @return true if the query results do not depend on a parent TableReader
   */
  public boolean isConstant() {
    return !reader.parentReferenced();
  }

  /**
   * Returns the number of columns in the table.  This value should be greater
   * than zero.
   *
   * @return number of columns in table
   */
  public int getColumnCount() {
    return columns.length;
  }

  /**
   * Return number of rows if known.
   *
   * @return number of rows or -1 if count is not known
   */
  public long getRowCount() throws SQLException {
    return rows==null ? -1 : rows.size();
  }

  /**
   * Get the name of a column.  This name is its given name, or the fully
   * qualified name of a table column is the column is simple that.
   * 
   * @param column column number (starting from zero)
   * @return name of column (or null if column has no name)
   */
  public String getColumnName(int column) {
    if (column_names[column]!=null)
      return column_names[column];
    if (columns[column] instanceof IndirectFunction)
      return columns[column].toString();
    return null;
  }

  /**
   * Return the SQL type of the specified column.
   *
   * @param column column number (starting from zero)
   * @return SQL type of data to be returned
   * @throws SQLException if an error occurs
   */
  public int getSQLType(int column) throws SQLException {
    return columns[column].getSQLType();
  }

  /**
   * This version of getSQLType() can only be used if the query returns
   * only one column.  In this case, calling this method is equivalent to
   * calling getSQLType(0).
   *
   * @return SQL type of data to be returned
   * @throws SQLException if an error occurs
   */
  public int getSQLType() throws SQLException {
    if (columns.length!=1)
      throw new SQLException("subquery returns more than one column");
    return columns[0].getSQLType();
  }

  /**
   * Return the maximum number of characters String values in the specified
   * column will have.  If the column is not of String type or if the maximum
   * length is not known, -1 should be returned.
   *
   * @param column column number (starting from zero)
   * @return maximum size of String returned or -1 if unknown
   * @throws SQLException if an error occurs
   */
  public int getMaxResultSize(int column) throws SQLException {
    return columns[column].getMaxResultSize();
  }

  /**
   * This version of getMaxResultSize() can only be used if the query returns
   * only one column.  In this case, calling this method is equivalent to
   * calling getMaxResultSize(0).
   *
   * @return maximum size of String returned or -1 if unknown
   * @throws SQLException if an error occurs
   */
  public int getMaxResultSize() throws SQLException {
    if (columns.length!=1)
      throw new SQLException("subquery returns more than one column");
    return columns[0].getMaxResultSize();
  }

  
  /****************  evaluate and results methods  ****************/

  /**
   * Execute simple aggregate query.  That is, SELECT columns are aggregates,
   * there is no GROUP BY, and neither ORDER BY nor DISTINCT have an effect.
   *
   * @throws SQLException if an error occurs
   * @throws EndOfTable if the table is advanced beyond that last row
   */
  protected void executeAggregate() throws SQLException, EndOfTable {
    // reset aggregates
    for (int i=0; i<columns.length; ++i)
      columns[i].reset();
    // read all rows, updating aggregate columns as we go
    while (true) {
      try {
	Object result;
	// advance to next row
	do {
	  reader.next();
	  if (where==null) break;
	  result = where.evaluate(Function.MATCH_EQU,TRUE_VALUE);
	} while (result==null || ((Boolean)result).booleanValue()!=true);
	reader.readColumns(start_where);  // might open a table by index
	reader.readAllTables(); // make's sure all tables are open
      }
      catch (EndOfTable e) {
	if (reader!=e.getReader())
	  throw e;
	if (reader.finishTable())
	  break;
	continue;
      }
      try {
	// evaluate SELECT columns to update aggregates (no EndOfTable here)
	for (int i=0; i<columns.length; ++i)
	  columns[i].evaluate(false);
      }
      catch (EndOfTable e) {
	if (reader!=e.getReader())
	  throw e;
	if (DriverConfig.debugLevel>0)
	  e.printStackTrace();
	throw new SQLExceptionWithCause("SOFTWARE BUG",e);
      }
    }
    Object[] row = new Object[columns.length];
    for (int i=0; i<columns.length; ++i)
      row[i] = columns[i].evaluate(true);
    rows = new ArrayList();
    rows.add(row);
    if (DriverConfig.debugLevel>0)
      System.err.println("ModSQL.Select: query complete (1 row)");
  }

  /**
   * Execute queries involving grouping (ie. have a GROUP BY clause).
   *
   * @throws SQLException if an error occurs
   * @throws EndOfTable if the table is advanced beyond that last row
   */
  protected void executeGroupBy() throws SQLException, EndOfTable {
    HashMap map = new HashMap(DriverConfig.getHashTableSize());
    // read all rows
    while (true) {
      try {
	// advance to next row
	Object result;
	do {
	  reader.next();
	  if (where==null) break;
	  result = where.evaluate(Function.MATCH_EQU,TRUE_VALUE);
	} while (result==null || ((Boolean)result).booleanValue()!=true);
	// setup array for group key and row for columns to save
	Object[] key_array = new Object[group_by.length];
	for (int i=0; i<group_by.length; ++i)
	  key_array[i] = group_by[i].evaluate(false);
	List key = Arrays.asList(key_array);
	Object[] data = reader.getColumnValues(start_group);
	reader.readAllTables();
	// store in map
	ArrayList group = (ArrayList)map.get(key);
	if (group==null)
	  group = new ArrayList();
	group.add(data);
	map.put(key,group);
      }
      catch (EndOfTable e) {
	if (reader!=e.getReader())
	  throw e;
	if (reader.finishTable())
	  break;
      }
    }
    
    if (DriverConfig.debugLevel>0)
      System.err.println("ModSQL.Select: "+map.size()+" groups");

    // allocate necessary arrays
    rows = new ArrayList();
    Object[][][] ordering=null;
    int order_size=0;
    if (order_by!=null)
      ordering = new Object[map.size()][][];
    if (distinct) {
      if (distinct_set==null)
	distinct_set = new HashSet(map.size());
      else
	distinct_set.clear();
    }
    
    // aggregate within each group
    try {
      Iterator iter = map.values().iterator();
      while (iter.hasNext()) {
	ArrayList group=(ArrayList)iter.next();
	// reset aggregates
	for (int j=0; j<columns.length; ++j)
	  columns[j].reset();
	if (having!=null)
	  having.reset();
	// feed column values into aggregates
	for (int i=0; i<group.size(); ++i) {
	  reader.setColumnValues((Object[])group.get(i));
	  for (int j=0; j<columns.length; ++j)
	    columns[j].evaluate(false);
	  if (order_by!=null)
	    for (int j=0; j<order_by.length; ++j)
	      if (!order_by_dup[j])
		order_by[j].evaluate(false);
	  if (having!=null)
	    having.evaluate(false);
	}
	// check having condition
	if (having!=null) {
	  Boolean result = (Boolean)having.evaluate(true);
	  if (result==null || result.booleanValue()==false)
	    continue;
	}
	// evaluate row
	Object[] row = new Object[columns.length];
	for (int j=0; j<columns.length; ++j)
	  row[j] = columns[j].evaluate(true);
	if (distinct) {
	  List row_list = Arrays.asList(row);
	  if (!distinct_set.add(row_list))
	    continue; // row already in distinct_set
	}
	if (ordering!=null) {
	  // evaluate ORDER BY
	  Object[][] whole_row = new Object[2][];
	  whole_row[0] = new Object[order_by.length];
	  whole_row[1] = row;
	  for (int j=0; j<order_by.length; ++j)
	    if (order_by_indices[j]>=0)
	      whole_row[0][j] = row[order_by_indices[j]];
	    else
	      whole_row[0][j] = order_by[j].evaluate(true);
	  ordering[order_size++] = whole_row;
	}
	else
	  rows.add(row);
      }
    }
    catch (EndOfTable e) {
      if (reader!=e.getReader())
	throw e;
      if (DriverConfig.debugLevel>0)
	e.printStackTrace();
      throw new SQLExceptionWithCause("SOFTWARE BUG",e);
    }
    // cleanup
    if (distinct_set!=null)
      distinct_set.clear();
    // check for ORDER BY
    if (ordering!=null) {
      // sort rows
      if (DriverConfig.debugLevel>0)
	System.err.println("ModSQL.Select: sorting "+order_size+" rows");
      OrderByComparator c = new OrderByComparator();
      Arrays.sort(ordering,0,order_size,c);
      for (int i=0; i<order_size; ++i)
	rows.add(ordering[i][1]);
    }
    if (DriverConfig.debugLevel>0)
      System.err.println("ModSQL.Select: query complete ("+rows.size()+" rows)");
  }

  /**
   * Execute basic queries (no GROUP BY and no aggregates).
   *
   * @throws SQLException if an error occurs
   * @throws EndOfTable if the table is advanced beyond that last row
   */
  protected void executeBasic() throws SQLException, EndOfTable {
    // no grouping and no aggregate, just execute the query
    rows = new ArrayList();
    if (distinct) {
      if (distinct_set==null)
	distinct_set = new HashSet(DriverConfig.getHashTableSize());
      else
	distinct_set.clear();
    }
    // read all rows
    while (true) {
      try {
	// advance to next row
	Object result;
	do {
	  reader.next();
	  if (where==null) break;
	  result = where.evaluate(Function.MATCH_EQU,TRUE_VALUE);
	} while (result==null || ((Boolean)result).booleanValue()!=true);
	// evaluate SELECT columns
	Object[] row = new Object[columns.length];
	for (int i=0; i<columns.length; ++i)
	  row[i] = columns[i].evaluate(false);
	Object[] ordering = null;
	if (order_by!=null) {
	  // evaluate ORDER BY
	  ordering = new Object[order_by.length];
	  for (int j=0; j<order_by.length; ++j)
	    if (order_by_indices[j]>=0)
	      ordering[j] = row[order_by_indices[j]];
	    else
	      ordering[j] = order_by[j].evaluate(false);
	}
	if (distinct) {
	  // ensure that row is unique
	  List row_list = Arrays.asList(row);
	  if (!distinct_set.add(row_list))
	    continue; // row already in distinct_set
	}
	else
	  reader.readAllTables();  // only if non-distinct
	if (order_by!=null) {
	  Object[][] whole_row = new Object[2][];
	  whole_row[0] = ordering;
	  whole_row[1] = row;
	  rows.add(whole_row);
	}
	else
	  rows.add(row);
      }
      catch (EndOfTable e) {
	if (reader!=e.getReader())
	  throw e;
	if (reader.finishTable())
	  break;
      }
    }
    // cleanup
    if (distinct_set!=null)
      distinct_set.clear();
    // do sorting
    if (order_by!=null) {
      if (DriverConfig.debugLevel>0)
	System.err.println("ModSQL.Select: sorting "+rows.size()+" rows");
      Object[][] ordering = new Object[rows.size()][];
      ordering = (Object[][])rows.toArray(ordering);
      OrderByComparator c = new OrderByComparator();
      Arrays.sort(ordering,c);
      rows.clear();
      for (int i=0; i<ordering.length; ++i)
	rows.add(ordering[i][1]);
    }
    if (DriverConfig.debugLevel>0)
      System.err.println("ModSQL.Select: query complete ("+rows.size()+" rows)");
  }

  /**
   * Execute query and store results in rows array.
   *
   * @throws SQLException if an error occurs
   * @throws EndOfTable if the table is advanced beyond that last row
   */
  protected void executeAndCacheResults() throws SQLException, EndOfTable {
    if (DriverConfig.debugLevel>0)
      System.err.println("ModSQL.Select: executing query");
    reader.reset();

    // if subquery depends on parent, ensure we have the necessary columns
    reader.readAllParentColumns();

    try {
      if (group_by!=null)
	executeGroupBy();
      else if (aggregate)
	executeAggregate();
      else 
	executeBasic();    
    }
    catch (EndOfTable e) {
      if (DriverConfig.debugLevel>0)
	e.printStackTrace();
      throw new SQLExceptionWithCause("SOFTWARE BUG",e);
    }
  }

  /**
   * Optimizes query in preperation for calls to next().
   * May actually execute query.  From Query interface.  
   *
   * @return -1 to indicate that a result set is needed
   * @throws SQLException if a database-access error occurs
   */
  public int execute() throws SQLException {
    if (DriverConfig.debugLevel>0)
      System.err.println("ModSQL.Select: "+toString(false));
    if (aggregate || order_by!=null) {
      try {
	executeAndCacheResults();
      }
      catch (EndOfTable e) {
	if (DriverConfig.debugLevel>0)
	  e.printStackTrace();
	throw new SQLExceptionWithCause("SOFTWARE BUG",e);
      }
    }
    column_values=null;
    current_row=-1;
    return -1;
  }

  /**
   * <p>In the case of aggregate functions, this method resets the state of
   * the function to the state it was in before the first call to evaluate().
   */
  public void reset() {
    // not an aggregate, nothing to reset
    return;
  }

  /**
   * Reset the table to before the first row.  After a call to this method,
   * next() should advance to the first row in the table.
   *
   * @throws SQLException if a database-access error occurs
   */
  public void beforeFirst() throws SQLException {
    reader.reset();
    column_values=null;
    current_row=-1;
    if (distinct_set!=null)
      distinct_set.clear();
    if (reader.parentReferenced())
      rows = null;
    if (rows==null && reader.getParent()==null) {
      try {
	// this happen when we are a table subquery (not sure if this is
        // always a good idea)
	executeAndCacheResults();
      }
      catch (EndOfTable e) {
	throw new SQLExceptionWithCause("SOFTWARE BUG",e);
      }
    }
  }

  /**
   * The table is initially positioned before its first row; the
   * first call to next makes the first row the current row; the
   * second call makes the second row the current row, etc.
   *
   * @return true if the new current row is valid; false if there
   * are no more rows
   * @throws SQLException if an error occurs
   * @throws EndOfTable if thrown by a parameter
   */
  public boolean next() throws SQLException, EndOfTable {
    // execute entire query and cache results if necessary
    if (rows==null && (aggregate || order_by!=null))
      executeAndCacheResults();

    // use cached results if we have them
    if (rows!=null) {
      if (++current_row<rows.size()) {
	column_values = (Object[])rows.get(current_row);
	return true;
      }
      column_values=null;
      return false;
    }

    // execute query "on the fly" (no group_by, order_by, or aggregates)
    if (distinct && distinct_set==null)
      distinct_set = new HashSet(DriverConfig.getHashTableSize());
    column_values = new Object[columns.length];
    while (true) {
      try {
	// advance to next row
	Object result;
	do {
	  reader.next();
	  if (where==null) break;
	  result = where.evaluate(Function.MATCH_EQU,TRUE_VALUE);
	} while (result==null || ((Boolean)result).booleanValue()!=true);
	// evaluate SELECT columns
	for (int i=0; i<columns.length; ++i)
	  column_values[i] = columns[i].evaluate(false);
	if (distinct) {
	  // ensure that row is unique
	  List row_list = Arrays.asList(column_values);
	  if (!distinct_set.add(row_list))
	    continue; // row already in distinct_set
	}
	else
	  reader.readAllTables();  // only if non-distinct
	return true;
      }
      catch (EndOfTable e) {
	if (reader!=e.getReader())
	  throw e;
	if (reader.finishTable())
	  return false;
      }
    }
  }

  /**
   * Get the current row as an array of Objects.  
   *
   * @return array of objects or null if current row is not valid
   * @throws SQLException if a database-access error occurs
   */
  public Object[] getRow() throws SQLException {
    if (column_values==null)
      throw new SQLException("current row is invalid");
    return column_values;
  }

  /**
   * Get the value of a column in the current row as a Java object.  This
   * method will throw an exception if the current row is not valid.
   *
   * @param column column number (starting from zero)
   * @return an Object holding the column value
   * @throws SQLException if an error occurs
   */
  public Object getObject(int column) throws SQLException {
    if (column_values==null)
      throw new SQLException("current row is invalid");
    return column_values[column];
  }

  /**
   * Evaluate each column of the row and return the results as an array
   * of length equal to the value returned by numColumns().  If the row
   * is the result of a subquery with no rows, the result will be an
   * array of NULL values.
   *
   * @param aggregate final evaluation of aggregates
   * @return array of objects
   * @throws SQLException if an error occurs
   * @throws EndOfTable if thrown by a parameter
   */
  public Object[] evaluateRow(boolean aggregate)
    throws SQLException, EndOfTable {
    if (reader.parentReferenced())
      rows = null;
    if (rows==null)
      executeAndCacheResults();
    if (rows.size()==1)
      return (Object[])rows.get(0);
    else if (rows.size()>1)
      throw new SQLException("row constructor returned too many rows");
    if (null_row==null)
      null_row = new Object[columns.length];
    return null_row;
  }

  /**
   * <p>Evaluate parameters and compute the function.  The parameters should be
   * evaluated in the order indicated with evaluateOrder() for optimal query
   * efficiency.
   *
   * <p>If the function is an aggregate, this method may return null to
   * indicate that the aggregate is not yet available.  The method will be
   * called later with the aggregate parameter set to true to indicate that
   * the final aggregate value is required.  If the function is non-constant
   * and non-aggregate, it may throw an exception if the aggregate parameter
   * is true.  New rows should not be read from the database if aggregate
   * is set to true.
   *
   * @param aggregate true to return final aggregate value
   * @return result object
   * @throws SQLException if an error occurs
   * @throws EndOfTable if thrown by a parameter
   */
  public Object evaluate(boolean aggregate) throws SQLException, EndOfTable {
    if (columns.length!=1)
      throw new SQLException("subquery returns more than one column");
    if (reader.parentReferenced())
      rows = null;
    if (rows==null)
      executeAndCacheResults();
    if (rows.size()==1)
      return ((Object[])rows.get(0))[0];
    else if (rows.size()>1)
      throw new SQLException("row constructor returned too many rows");
    return null;
  }

  /**
   * <p>Same as evaluate(), except that a specific result is desired.  If
   * the desired result can only be obtained when a particular parameter
   * evaluates to a particular value, the evaulate() method for that parameter
   * should be passed that particular value in the hopes that it will be
   * returned.  Otherwise, if knowledge of a desired result does not
   * sufficiently constrain the parameters, this method can simply call the
   * evaluate() method above and return what it returns.
   *
   * <p>The match_op parameter will be one of the MATCH_* constants.
   * The match condition can be considered a relation of the form:
   * <code>desired_value match_op match_value</code>.  For example,
   * <code>desired_value MATCH_LT match_value</code> implies
   * <code>desired_value &lt; match_value</code>.
   *
   * @param match_op how desired value is matched
   * @param match_value value to match to
   * @return result object
   * @throws SQLException if an error occurs
   * @throws EndOfTable if thrown by a parameter
   */
  public Object evaluate(int match_op, Object match_value)
    throws SQLException, EndOfTable {
    return evaluate(false);
  }


  /**
   * Simple list of ColumnValue's in a SELECT query's GROUP BY list.  This
   * class is necessary to set the force_aggregate property of 
   * IndirectFunction's for columns that appear in the GROUP BY list.
   */
  class GroupByList {
    
    /**
     * Check if a specific function is in the GROUP BY list.
     *
     * @param x function to check
     * @return true if the function is in the list
     */
    public boolean inList(Function x) {
      for (int i=0; i<group_by.length; ++i) {
	if (group_by[i] instanceof IndirectFunction) {
	  if (x==((IndirectFunction)group_by[i]).getFunction())
	    return true;
	}
	else if (x==group_by[i])
	  return true;
      }
      return false;
    }
  };
  

  /**
   * Comparator for sorting rows when evaluating ORDER BY.  Objects passed
   * to these methods are expected to be of the type Object[][].  The first
   * index (ie. obj[0]) should be an array of order_by.length values that
   * are to be compared.  Additional indicies (ie. obj[1], etc.) are just
   * long for the ride.
   */
  class OrderByComparator implements Comparator {

    /**
     * Compare two arrays of the type Object[][].  
     *
     * @param o1 the first object to be compared
     * @param o2 the second object to be compared
     */
    public int compare(Object o1, Object o2) {
      Object[] a1 = ((Object[][])o1)[0];
      Object[] a2 = ((Object[][])o2)[0];
      for (int i=0; i<order_by.length; ++i) {
	int result;
	// compare a1[i] and a2[i]
	if (a1[i]==null)
	  result = a2[i]==null ? 0 : 1;
	else if (a2[i]==null)
	  result = -1;
	else if (a1[i] instanceof Comparable)
	  result = ((Comparable)a1[i]).compareTo(a2[i]);
	else if (a1[i] instanceof Boolean) {
	  if (((Boolean)a1[i]).booleanValue()==((Boolean)a2[i]).booleanValue())
	    result=0;
	  else if (((Boolean)a1[i]).booleanValue())
	    result=1;
	  else
	    result=-1;
	}
	else 
	  throw new ClassCastException();
	if (result!=0)
	  return order_by_dir[i] ? result : -result;
      }
      return 0;
    }

    /**
     * Test if the two comparators are from the same Select object.
     *
     * @param obj the reference object with which to compare
     */
    public boolean equals(Object obj) {
      if (obj instanceof OrderByComparator)
	return query()==((OrderByComparator)obj).query();
      return false;
    }

    /**
     * Used in equals() above.  I can't figure out how to do this without a
     * method like this one.
     *
     * @return reference to outer object
     */
    private Select query() {
      return Select.this;
    }
  };

};