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

/* $Id: TableReader.java,v 1.25 2004/01/03 17:04:38 cvs Exp $
 *
 * Copyright (c) 2004 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>Keeps track of open tables, referenced columns, and current row being
 * read from joined table.
 *
 * <p>This class implements the full outer-join of all of the tables involved
 * in a query.  The interface allows for the skipping of entire subtree's
 * of tuples and the use of indexed tables to improve query efficiency.
 *
 * @author chris.studholme@utoronto.ca
 */
final class TableReader implements FunctionProvider {

  /** Array of open tables. */
  private DatabaseTable[] tables;
  /** Aliases for open tables. */
  private String[] aliases;    
  /** Actual table or index being read. */
  private DatabaseTableBase[] table_read;
  /** If table_read entry is an index, this array holds the index of the
      indexed column (or -1 if table_read entry is not an index). */
  private int[] indexed_column;

  /** Sequence number for read tables (-1 for not read yet). */
  private int[] read_sequence;
  /** Index of last table to be read from. */
  private int last_read;
  /** If last_read>=0, then this boolean indicates that rows have been
   * read and are available for all open tables.  If last_read<0, this
   * boolean indicates if we are before the first first row (true) or
   * after the last row of the table (false). */ 
  private boolean row_available; 

  /** Array of referenced columns. */
  private ArrayList columns;

  /** Reference to parent TableReader (used in subqueries). */
  private TableReader parent;
  /** Columns from parent reader referenced in this query. */
  private ArrayList parent_columns;


  /**
   * Constructor.
   *
   * @param tables array of open database tables
   * @param aliases aliases of the database tables
   * @param parent parent reader of subquery (null if none)
   */
  public TableReader(DatabaseTable[] tables, String[] aliases,
		     TableReader parent) {
    this.tables = tables;
    this.aliases = aliases;
    table_read = new DatabaseTableBase[tables.length];
    read_sequence = new int[tables.length];
    indexed_column = new int[tables.length];
    Arrays.fill(table_read,null);
    Arrays.fill(read_sequence,-1);
    last_read = -1;
    row_available = true; 
    columns = new ArrayList();
    parent_columns = new ArrayList();
    this.parent = parent;
  }

  /**
   * Get parent TableReader, or null if none.
   *
   * @return parent reader or null this is the root
   */
  public TableReader getParent() {
    return parent;
  }

  /**
   * Are parent reader columns referenced here?
   *
   * @return true if we reference columns in the parent reader
   */
  public boolean parentReferenced() {
    return parent_columns.size()>0;
  }

  /**
   * Get reference to a particular table.
   *
   * @return a particular table
   */
  public DatabaseTable getDatabaseTable(int table_index) {
    return tables[table_index];
  }

  /**
   * Get table alias (or null if none).
   *
   * @return alias for table
   */
  public String getTableAlias(int table_index) {
    return aliases[table_index];
  }

  /**
   * Returns total number of referenced columns.
   *
   * @return number of columns referenced
   */
  public int getColumnCount() {
    return columns.size();
  }

  /**
   * <p>Lookup description in list of tables to find a matching column.
   * The description can be in any one of the following forms:
   * 'alias.column_name', 'table_name.column_name', or 'column_name'.
   *
   * <p>If a suitable column is found, it is added to the list of referenced
   * columns (if it's not already there).
   *
   * <p>If a suitable column was not found and this TableReader has a parent,
   * the parent is searched for a matching column.
   *
   * @param description description of column to look for
   * @return Function representing column
   * @throws SQLException if the column was not found
   */
  public Function lookupFunction(String description) 
    throws SQLException {

    int lastdot = description.lastIndexOf('.');
    String tablename = lastdot>0 ? description.substring(0,lastdot) : null;
    String columnname = 
      lastdot>0 ? description.substring(lastdot+1) : description;
    
    int table_index = -1;
    int column_index = -1;
    if (tablename!=null) {
      // find specific table named
      for (int i=0; i<tables.length; ++i) {
	if (aliases[i]!=null) {
	  if (tablename.equalsIgnoreCase(aliases[i])) {
	    table_index = i;
	    break;
	  }
	}
	else if (tablename.equalsIgnoreCase(tables[i].getTableName())) {
	  table_index = i;
	  break;
	}
      }
      if (table_index>=0) {
	column_index = tables[table_index].findColumn(columnname);
	if (column_index<0)
 	  throw new SQLException("column '"+columnname+
				 "' not found in table '"+
				 tables[table_index].getTableName()+"'");
      }
    }
    else {
      // search all tables for column
      for (int i=0; i<tables.length; ++i)
	if ((column_index=tables[i].findColumn(columnname))>=0) {
	  table_index = i;
	  break;
	}
    }
    
    if (table_index>=0) {
      // column was found, check to see if it is already referenced
      for (int i=0; i<columns.size(); ++i) {
	ColumnValue c = (ColumnValue)columns.get(i);
	if (table_index==c.table && column_index==c.column)
	  return c;
      }
      // create new ColumnValue
      ColumnValue c = new ColumnValue(this,table_index,column_index);
      columns.add(c);
      return c;
    }
    
    if (parent!=null) {
      // column not found, check with parent
      Function c = parent.lookupFunction(description);
      if (c!=null) {
	parent_columns.add(c);
	return c;
      }
    }

    throw new SQLException("column '"+description+"' not found");
  }

  /**
   * Check if the specified column of the specified table is indexed.
   *
   * @param table index of table
   * @param column index of column within table
   * @return true if an index is available on the specified column
   * @throws SQLException if thrown by a database module
   */
  public boolean isIndexAvailable(int table, int column) throws SQLException {
    if (tables[table].isIndexAvailable(column))
      return true;
    String fn = 
      IndexTable.getIndexFilename(tables[table].getTableName(),
				  tables[table].getColumnName(column));
    return IndexTable.isIndexAvailable(fn);
  }


  /**
   * Reorder parameters in function to optimize query efficiency.  This 
   * method is the same as optimizeParameterOrder() below, but with an
   * empty bitmap for tables_read.
   *
   * @param function the function to optimize by reordering terms
   * @throws SQLException if an error occurs
   */
  public void optimizeParameterOrder(Function function) throws SQLException {
    optimizeParameterOrder(function, new BitSet(tables.length));
  }

  /**
   * Reorder parameters in function to optimize query efficiency.  This 
   * method essentially decides the join order of the tables.
   *
   * @param function the function to optimize by reordering terms
   * @param tables_read bitmap indicating which tables have been read from
   * @throws SQLException if an error occurs
   */
  public void optimizeParameterOrder(Function function, BitSet tables_read)
    throws SQLException {
    int n = function.getParameterCount();
    if (n<=1) {
      if (n==1)
	optimizeParameterOrder(function.getParameter(0),tables_read);
      return;
    }
    // we have two or more parameters so we need to order them
    // first figure out which tables each parameter needs
    TableAccess[] ta = new TableAccess[n];    
    BitSet indexed_tables = new BitSet(tables.length);
    for (int i=0; i<n; ++i) {
      ta[i] = new TableAccess();
      function.getParameter(i).registerWith(ta[i]);
      indexed_tables.or(ta[i].index_available);
    }

    // keep track of which parameters we've ordered already
    boolean[] ordered = new boolean[n];
    Arrays.fill(ordered,false);
    int order=0;
    BitSet tmp = new BitSet(tables.length);
    
    // main loop to order parameters
    do {
      /* Find all parameters that don't need any new tables.  Ideally, we
       * should break ties as follows:
       *   - parameters that require the fewest tables first
       *   - parameters that access indexed columns first
       * but we currently don't do either of these.  Or maybe this is best:
       *   - parameters that access the fewest non-indexed columns first
       */
      for (int i=0; i<n; ++i) {
	if (!ordered[i]) {
	  tmp.xor(tmp);
	  tmp.or(ta[i].table_needed);
	  tmp.andNot(tables_read);
	  if (tmp.length()==0) {
	    function.evaluateOrder(i,order++);
	    optimizeParameterOrder(function.getParameter(i),tables_read);
	    ordered[i] = true;
	  }
	}
      }
      if (order>=n)
	break;
      
      /* Find the next appropriate parameter that opens a new table.  
       * Preference is as follows:
       *   - we choose parameters that open tables that are not indexed first
       *   - for tables that are indexed, we choose parameters that make use
       *     of the index first
       *   - we try to open as few new tables as possible with each parameter
       */

      // find a parameter that requires a non-indexed table
      int ni_choice=-1;
      int ni_opens=0;
      for (int i=0; i<n; ++i) {
	if (!ordered[i]) {
	  tmp.xor(tmp);
	  tmp.or(ta[i].table_needed);
	  tmp.andNot(tables_read);
	  int new_opens = cardinality(tmp);
	  tmp.andNot(indexed_tables);
	  if (tmp.length()>0 && (ni_choice<0 || new_opens<ni_opens)) {
	    ni_choice=i;
	    ni_opens=new_opens;
	  }
	}
      }
      if (ni_choice>=0) {
	function.evaluateOrder(ni_choice,order++);
	optimizeParameterOrder(function.getParameter(ni_choice),tables_read);
	tables_read.or(ta[ni_choice].table_needed);
	ordered[ni_choice] = true;
	continue;
      }

      // find a parameter that opens a new table by index
      int i_choice=-1;
      int i_opens=0;
      int i_noindex=0;
      for (int i=0; i<n; ++i) {
	if (!ordered[i]) {
	  tmp.xor(tmp);
	  tmp.or(ta[i].table_needed);
	  tmp.andNot(tables_read);
	  int new_opens = cardinality(tmp);
	  tmp.and(ta[i].index_available);
	  int noindex = new_opens-cardinality(tmp);
	  if (i_choice<0 || noindex<i_noindex || new_opens<i_opens) {
	    i_choice = i;
	    i_noindex = noindex;
	    i_opens = new_opens;
	  }
	}
      }
      if (i_choice>=0) {
	function.evaluateOrder(i_choice,order++);
	optimizeParameterOrder(function.getParameter(i_choice),tables_read);
	tables_read.or(ta[i_choice].table_needed);
	ordered[i_choice] = true;
      }
      else
	throw new SQLException("SOFTWARE BUG: failed to order parameters");

    } while (order<n);
  }

  /**
   * Get all column values starting at column 0 and ending at column
   * ncolumns-1.  These value are useful for reloading into row using
   * setColumnValues().
   *
   * @param ncolumns total number of column values to fetch
   * @return array of column values
   * @throws SQLException if an error occurs
   * @throws EndOfTable if the end of a table has been encountered
   */
  public Object[] getColumnValues(int ncolumns) 
    throws SQLException, EndOfTable {
    Object[] result = new Object[ncolumns];
    for (int i=0; i<result.length; ++i)
      result[i] = ((Function)columns.get(i)).evaluate(false);
    return result;
  }

  /**
   * Get values for all referenced columns.  This method is the same as
   * getColumnValues() above, but with ncolumns set to fetch values for
   * all columns.
   *
   * @return array of column values
   * @throws SQLException if an error occurs
   * @throws EndOfTable if the end of a table has been encountered
   */
  public Object[] getColumnValues() throws SQLException, EndOfTable {
    return getColumnValues(columns.size());
  }

  /**
   * Load columns values into respective columns.  This method can be used
   * to reload a row of data fetched earlier using getColumnValues().  If
   * the length of values is less than the number of columns, the remaining
   * columns will be in an indeterminant state.
   *
   * @param values values for each referenced column
   * @throws SQLException if an error occurs
   */
  public void setColumnValues(Object[] values) throws SQLException {
    for (int i=0; i<values.length; ++i)
      ((ColumnValue)columns.get(i)).setValue(values[i]);
  }

  /**
   * Invalidate all column data and reset tables to before the first row.
   * Clients should call next() before evaluating the first row.
   */
  public void reset() {
    if (DriverConfig.debugLevel>0)
      System.err.println("ModSQL.TableReader: reseting all tables");
    last_read = -1;
    Arrays.fill(read_sequence,-1);
    for (int i=0; i<columns.size(); ++i)  // is this necessary?
      ((ColumnValue)columns.get(i)).invalidate();
    row_available=true; // indicates we're before the first row
  }

  /** 
   * Advance to next row.  The tables are initially positioned before the 
   * first row so this method should be called before the first row is
   * evaluated.
   *
   * @throws SQLException if an error occurs
   * @throws EndOfTable if the end of a table has been encountered
   */
  protected void next() throws SQLException, EndOfTable {
    if (!row_available) {
      // we're either after the last row or failed to read a row since
      // the last next call
      throw new EndOfTable(this);
    }

    if (DriverConfig.debugLevel>=2)
      System.err.println("ModSQL.TableReader: next row (last_read="+
			 last_read+")");
    
    // mark data as invalid for all columns that are from the table we
    // are about to increment
    if (last_read>=0) {
      for (int i=0; i<columns.size(); ++i) {
	ColumnValue c = (ColumnValue)columns.get(i);
	if (c.table==last_read) 
	  c.invalidate();
      }
    }
    
    // indicate that a row needs to be read
    row_available = false;    
  }

  /** 
   * Closes least-significant table.  This should be done in response to
   * EndOfTable throwable.  Call this method before calling nextRow() to
   * advance to the next row.
   *
   * @return true if all tables have been closed
   * @throws SQLException if an error occurs
   */
  public boolean finishTable() throws SQLException {
    if (last_read<0) {
      row_available=false;  // indicate after_last
      return true;
    }
    
    if (DriverConfig.debugLevel>=2)
      System.err.println("ModSQL.TableReader: finished with table '"+
			 tables[last_read].getTableName()+"'");
    
    // close current table
    int prev_seq = read_sequence[last_read]-1;
    read_sequence[last_read] = -1;
    if (prev_seq<0) {
      // all done
      row_available=false; // indicates that we are after last row
      last_read=-1;
      return true;
    }

    // row from previous table is still valid
    row_available=true;

    // find previous least-significant table
    for (int i=0; i<read_sequence.length; ++i)
      if (read_sequence[i]==prev_seq) {
	last_read=i;
	return false;
      }
    throw new SQLException("SOFTWARE BUG: failed to find previous table");
  }


  /**
   * Start reading the specified table.  If the table has never been read
   * before (ie. is not open), it may be opened via an index on the specified
   * column.  If the row from the previous table is not valid, it will be
   * read before the new table is opened.
   *
   * @param table_index index of next table to read
   * @param column_index index of column being referenced (-1 for none)
   * @throws SQLException if an error occurs
   * @throws EndOfTable if the end of a table has been encountered
   */
  protected void readTable(int table_index, int column_index) 
    throws SQLException, EndOfTable {
    if (DriverConfig.debugLevel>=2)
      System.err.println("ModSQL.TableReader: started reading table '"+
			 tables[table_index].getTableName()+"'");

    // make sure last table has been read
    if (last_read>=0 && !row_available) {
      if (!table_read[last_read].next())
	throw new EndOfTable(this);
      //row_available=true;  // unnecessary
    }

    if (read_sequence[table_index]!=-1)
      throw new SQLException("SOFTWARE BUG: table already open");
    
    if (table_read[table_index]==null) {
      if (column_index>=0) {
	// attempt to open index for column
	table_read[table_index] = tables[table_index].openIndex(column_index);
	if (DriverConfig.debugLevel>0 && table_read[table_index]!=null)
	  System.err.println("ModSQL.TableReader: native index opened");
	
	// no native support for index, open ModSQL index (if available)
	if (table_read[table_index]==null) {
	  table_read[table_index] =
	    IndexTable.openIndex(tables[table_index],
				 tables[table_index].
				 getColumnName(column_index));
	  if (DriverConfig.debugLevel>0 && table_read[table_index]!=null)
	    System.err.println("ModSQL.TableReader: ModSQL index opened");
	}
      }
      if (table_read[table_index]!=null) 
	indexed_column[table_index]=column_index;
      else {
	// no index available, use actual table
	table_read[table_index]=tables[table_index];
	indexed_column[table_index]=-1;
      } 
    }
    // invalidate data for all columns that are from the newly read table
    for (int i=0; i<columns.size(); ++i) {
      ColumnValue c = (ColumnValue)columns.get(i);
      if (c.table==table_index) 
	c.invalidate();
    }
    // reset table to before first row
    table_read[table_index].beforeFirst();
    // update open sequence
    read_sequence[table_index] = last_read<0 ? 0 : 1+read_sequence[last_read];
    last_read = table_index;
    // make sure we do a next() before attempting to read table
    row_available = false;    
  }

  /**
   * Make sure all tables have been read from.
   *
   * @throws SQLException if an error occurs
   * @throws EndOfTable if the end of a table has been encountered
   */
  public void readAllTables() throws SQLException, EndOfTable {
    for (int i=0; i<read_sequence.length; ++i)
      if (read_sequence[i]==-1)
	readTable(i,-1);
    if (!row_available && !table_read[last_read].next())
      throw new EndOfTable(this);
    row_available=true;
  }

  /**
   * Make sure tables referenced from a parent reader have been read by
   * attempting to fetch values for the first ncolumns referenced columns 
   * from the parent.
   *
   * @param ncolumns number of parent columns to check
   * @throws SQLException if an error occurs
   * @throws EndOfTable if the end of a table has been encountered
   */
  public void readParentColumns(int ncolumns) throws SQLException, EndOfTable {
    for (int i=0; i<ncolumns; ++i)
      ((ColumnValue)parent_columns.get(i)).evaluate(false);
  }

  /**
   * Make sure all tables referenced from a parent reader have been read by
   * attempting to fetch values for all referenced columns.  This method is
   * the same as readParentColumns() above, but with ncolumns set to check
   * all referenced columns.
   *
   * @throws SQLException if an error occurs
   * @throws EndOfTable if the end of a table has been encountered
   */
  public void readAllParentColumns() throws SQLException, EndOfTable {
    readParentColumns(parent_columns.size());
  }

  /**
   * Make sure tables have been read by attempting to fetch values for the
   * first ncolumn referenced columns.
   *
   * @param ncolumns number of columns to check
   * @throws SQLException if an error occurs
   * @throws EndOfTable if the end of a table has been encountered
   */
  public void readColumns(int ncolumns) throws SQLException, EndOfTable {
    for (int i=0; i<ncolumns; ++i) {
      ColumnValue c = (ColumnValue)columns.get(i);
      if (read_sequence[c.table]==-1)
	readTable(c.table,c.column);
      c.evaluate(false);
    }
    if (last_read>=0) {
      if (!row_available && !table_read[last_read].next())
	throw new EndOfTable(this);
      row_available=true;
    }
  }

  /**
   * Make sure all tables have been read from.  This method is the same as
   * readColumns() above, but with ncolumns set to ensure that all tables
   * with at least one referenced column are checked.
   *
   * @throws SQLException if an error occurs
   * @throws EndOfTable if the end of a table has been encountered
   */
  public void readAllColumns() throws SQLException, EndOfTable {
    readColumns(columns.size());
  }

  /**
   * Read the value of the specified column in the specified table.
   *
   * @param table_index index of table
   * @param column_index index of column within table
   * @return column value
   * @throws SQLException if an error occurs
   * @throws EndOfTable if the end of a table has been encountered
   */
  protected Object readColumnValue(int table_index, int column_index) 
    throws SQLException, EndOfTable {

    // make sure table is open
    if (read_sequence[table_index]==-1)
      readTable(table_index,column_index);

    // advance to next row is necessary
    if (table_index==last_read && !row_available) {
      if (!table_read[last_read].next())
	throw new EndOfTable(this);
      row_available=true;
    }

    // get column value
    return table_read[table_index].getObject(column_index);
  }

  /**
   * <p>Read the value of the specified column in the specified table.  If it
   * is necessary to advance to the next row of the table, search for a row
   * with match_value in the specified column.  This method is not obligated
   * to return match_value.  It may just advance to the next row as the
   * above implementation of readColumnValue() does.
   *
   * <p>Note that the type of object passed in match_value must exactly
   * match the column type as indicated by getSQLType().
   *
   * @param table_index index of table
   * @param column_index index of column within table
   * @param match_value object value to look for
   * @return column value
   * @throws SQLException if an error occurs
   * @throws EndOfTable if the end of a table has been encountered
   */
  protected Object readColumnValue(int table_index, int column_index,
				   Object match_value) 
    throws SQLException, EndOfTable {

    // make sure table is open
    if (read_sequence[table_index]==-1)
      readTable(table_index,column_index);

    // advance to next row is necessary
    if (table_index==last_read && !row_available) {
      if (table_read[last_read] instanceof DatabaseIndex &&
	  indexed_column[last_read]==column_index) {
	if (!((DatabaseIndex)table_read[last_read]).findNext(match_value))
	  throw new EndOfTable(this);
      }
      else if (!table_read[last_read].next())
	throw new EndOfTable(this);
      row_available=true;
    }
    
    // get column value
    return table_read[table_index].getObject(column_index);
  }


  /**
   * Update a column in the table.
   *
   * @param table_index index of table
   * @param column_index index of column within table
   * @param value new value for column
   * @throws SQLException if an error occurs
   */
  public void updateColumnValue(int table_index, int column_index, 
				Object value) throws SQLException {
    if (read_sequence[table_index]<0 || !row_available)
      throw new SQLException("no row to update");
    table_read[table_index].updateObject(column_index,value);
  }

  /**
   * Commit updated columns to database.
   *
   * @throws SQLException if an error occurs
   */
  public void commitUpdates() throws SQLException {
    for (int i=0; i<read_sequence.length; ++i)
      if (read_sequence[i]>=0)
	table_read[i].commitUpdates();
  }

  /**
   * Delete current row.
   *
   * @throws SQLException if an error occurs
   */
  public void deleteRow() throws SQLException {
    if (last_read<0 || !row_available)
      throw new SQLException("no row to delete");
    table_read[last_read].deleteRow();
  }


  /**
   * Implements java.util.BitSet.cardinality().  This method is needed because
   * the cardinality() method in BitSet is not available in before v1.4 JDK.
   *
   * @param bs bits to count
   * @return number of 1 bits in BitSet
   */
  public static int cardinality(BitSet bs) {
    int result=0;
    for (int i=0; i<bs.length(); ++i)
      if (bs.get(i))
	++result;
    return result;
  }


  /**
   * Class to register access to particular tables and whether the tables
   * can be accessed via an indexed column.  This class is used when
   * optimizing the join order to figure out which functions access which
   * tables.
   */
  class TableAccess {

    /** Tables needed by Function. */
    public BitSet table_needed;
    /** Tables that may be accessed via an index. */
    public BitSet index_available;

    /**
     * Constructor.
     */
    public TableAccess() {
      table_needed = new BitSet(tables.length);
      index_available = new BitSet(tables.length);
    }

    /**
     * Returns true if this object is from the specified table reader.
     *
     * @param reader parent to test for
     * @return true if object is from reader
     */
    public boolean forReader(TableReader reader) {
      return reader==TableReader.this;
    }
  };
     
};