Program 8A: Sort a Linked List

/*
*/

#ifndef NUMBER_ARRAY_LIST_H
#define NUMBER_ARRAY_LIST_H

#include <list>
#include <vector>

#ifndef SINGLE_VARIABLE_FUNCTION_H
#include "single_variable_function.h"
#endif

class number_array_list : public std::list< std::vector< double > >
{
 protected:
  int m_field_count;

 public:
  int field_count( void ) const;
  std::vector< double > head( void ) const;
  number_array_list tail( void ) const;
  number_array_list suffixed_by_item( const std::vector< double >& entry ) const;
  number_array_list suffixed_by_list( const number_array_list& rhs ) const;
  number_array_list mapped_to( int field_index, const single_variable_function& f ) const;
  number_array_list multiplied_by_list( int field_index, const number_array_list& rhs ) const;
  number_array_list sorted_by( int field_index ) const;
  number_array_list items_less_than( int field_index, double value ) const;
  number_array_list items_greater_than_or_equal_to( int field_index, double value ) const;

  bool is_valid_entry( const std::vector< double >& entry ) const;
  bool is_valid_field_index( int field_index ) const;
  bool is_sorted_by( int field_index ) const;
  double sum_by_field( int field_index ) const;
  double mean_by_field( int field_index ) const;
  int entry_count( void ) const;
  
  void set_field_count( int new_field_count );
  void add_entry( const std::vector< double >& entry );

  void make_from_entry( const std::vector< double >& entry );
  void make( void );
  void make_from_list( const number_array_list& rhs );
  number_array_list( void );
};

#endif

/*
*/

/*
*/

#include "number_array_list.h"

#ifndef CONTRACT_H
#include "contract.h"
#endif

int
number_array_list::field_count( void ) const
{
  return m_field_count;
}

std::vector< double >
number_array_list::head( void ) const
{
  REQUIRE( entry_count() >= 1 );
  return *(begin());
}

number_array_list
number_array_list::tail( void ) const
{
  number_array_list Result;
  if ( entry_count() > 1 )
    {
      number_array_list::const_iterator tail_head = begin();
      ++tail_head;
      Result.insert( Result.begin(), tail_head, end() );
      Result.m_field_count = field_count();
      ENSURE( Result.entry_count() == entry_count() - 1 );
    }
  return Result;
}

number_array_list
number_array_list::suffixed_by_item( const std::vector< double >& entry ) const
{
  number_array_list Result;
  Result.make_from_list( *this );
  Result.add_entry( entry );
  ENSURE( Result.entry_count() == entry_count() + 1 );
  return Result;
}

number_array_list
number_array_list::suffixed_by_list( const number_array_list& rhs ) const
{
  number_array_list Result;
  Result.make_from_list( *this );
  for ( number_array_list::const_iterator iter = rhs.begin(); iter != rhs.end(); ++iter )
    {
      Result.add_entry( *iter );
    }
  ENSURE( Result.entry_count() == entry_count() + rhs.entry_count() );
  return Result;
}

number_array_list
number_array_list::mapped_to( int field_index, const single_variable_function& f ) const
{
  REQUIRE( is_valid_field_index( field_index ) );
  number_array_list Result;
  if ( entry_count() > 0 )
    {
      std::vector<double> new_entry = head();
      new_entry[ field_index ] = f.at( head()[ field_index ] );
      Result.make_from_list( Result.suffixed_by_item( new_entry ).suffixed_by_list( tail().mapped_to( field_index, f )));
    }
  ENSURE( Result.entry_count() == entry_count() );
  return Result;
}

number_array_list
number_array_list::multiplied_by_list( int field_index, const number_array_list& rhs ) const
{
  REQUIRE( entry_count() == rhs.entry_count() );
  REQUIRE( field_count() == rhs.field_count() );
  REQUIRE( is_valid_field_index( field_index ) );
  number_array_list Result;
  if ( entry_count() > 0 )
    {
      std::vector< double > new_entry = head();
      new_entry[ field_index ] = head()[ field_index ] * rhs.head()[field_index];
      Result.make_from_list( Result.suffixed_by_item( new_entry ).
			      suffixed_by_list( tail().multiplied_by_list( field_index, rhs ) ) );
    }
  ENSURE( Result.entry_count() == entry_count() );
  return Result;
}

number_array_list
number_array_list::sorted_by( int field_index ) const
{
  REQUIRE( is_valid_field_index( field_index ) );
  number_array_list Result;
  if ( is_sorted_by( field_index ) )
    {
      Result.make_from_list( *this );
    }
  else
    {
      Result.make_from_list( tail().items_less_than( field_index, head()[field_index] ).sorted_by( field_index ).
			     suffixed_by_item( head() ).
			     suffixed_by_list( tail().items_greater_than_or_equal_to( field_index, head()[field_index] ).sorted_by( field_index )));
    }
  ENSURE( Result.entry_count() == entry_count() );
  return Result;
}

number_array_list
number_array_list::items_less_than( int field_index, double value ) const
{
  REQUIRE( is_valid_field_index( field_index ) );
  number_array_list Result;
  for ( number_array_list::const_iterator iter = begin(); iter != end(); ++iter )
    {
      if ( (*iter)[field_index] < value )
	{
	  Result.add_entry( *iter );
	}
    }
  ENSURE( Result.entry_count() <= entry_count() );
  return Result;
}

number_array_list
number_array_list::items_greater_than_or_equal_to( int field_index, double value ) const
{
  REQUIRE( is_valid_field_index( field_index ) );
  number_array_list Result;
  for ( number_array_list::const_iterator iter = begin(); iter != end(); ++iter )
    {
      if ( (*iter)[field_index] >= value )
	{
	  Result.add_entry(*iter);
	}
    }
  ENSURE( Result.entry_count() <= entry_count() );
  return Result;
}

bool
number_array_list::is_valid_entry( const std::vector<double>& entry ) const
{
  bool Result = false;
  if ( ( entry_count() == 0 ) 
       || ( ( entry_count() > 0 ) && ( entry.size() == field_count() ) ) )
    {
      Result = true;
    }
  return Result;
}

bool
number_array_list::is_valid_field_index( int field_index ) const
{
  bool Result = true;
  if ( entry_count() > 0 )
    {
      Result = ( 0 <= field_index ) && ( field_index < m_field_count );
    }
  return Result;
}

bool
number_array_list::is_sorted_by( int field_index ) const
{
  REQUIRE( is_valid_field_index( field_index ) );
  bool Result = true;
  if ( entry_count() > 1 )
    {
      Result = ( head()[field_index] < tail().head()[field_index] ) && tail().is_sorted_by( field_index );
    }
  return Result;
}

double
number_array_list::sum_by_field( int field_index ) const
{
  REQUIRE( is_valid_field_index( field_index ) )
  double Result = 0;
  if ( entry_count() > 0 )
    {
      Result = head()[field_index] + tail().sum_by_field( field_index );
    }
  return Result;
}

double
number_array_list::mean_by_field( int field_index ) const
{
  REQUIRE( is_valid_field_index( field_index ) );
  REQUIRE( entry_count() > 0 );
  double Result = sum_by_field( field_index ) / static_cast<double>( entry_count() );
  return Result;
}

int
number_array_list::entry_count( void ) const
{
  return size();
}

void
number_array_list::set_field_count( int new_field_count )
{
  REQUIRE( entry_count() == 0 );
  m_field_count = new_field_count;
  ENSURE( field_count() == new_field_count );
}

void
number_array_list::add_entry( const std::vector< double >& entry )
{
  if ( entry_count() == 0 )
    {
      set_field_count( entry.size() );
    }
  REQUIRE( is_valid_entry( entry ) );
  const int old_entry_count = entry_count();
  push_back( entry );
  ENSURE( entry_count() == old_entry_count + 1 );
}

void
number_array_list::make_from_entry( const std::vector<double>& entry )
{
  make();
  add_entry( entry );
  ENSURE( entry_count() == 1 );
  ENSURE( head() == entry );
}

void
number_array_list::make( void )
{
  clear();
  m_field_count = -1;
  ENSURE( m_field_count == -1 );
  ENSURE( entry_count() == 0 );
}

void
number_array_list::make_from_list( const number_array_list& rhs )
{
  make();
  insert( begin(), rhs.begin(), rhs.end() );
  m_field_count = rhs.field_count();
  ENSURE( entry_count() == rhs.entry_count() );
}

number_array_list::number_array_list( void )
{
  make();
}

/*
*/

#ifndef NUMBER_ARRAY_LIST_PARSER_H
#define NUMBER_ARRAY_LIST_PARSER_H

#ifndef SIMPLE_INPUT_PARSER_H
#include "simple_input_parser.h"
#endif
#ifndef NUMBER_ARRAY_LIST_H
#include "number_array_list.h"
#endif

class number_array_list_parser: public simple_input_parser
{
 protected:
  number_array_list number_list;
  enum state_t { Parsing_historical_data, Parsing_prediction_data };
  state_t state;

 public:
  virtual std::string transformed_line (const std::string & line) const;
  std::string string_stripped_of_comments (const std::string & str) const;
  static bool is_double (const std::string & str);
  static double double_from_string (const std::string & str);
  static const std::string & historical_data_terminator;
  static const std::string & inline_comment_begin;
  bool last_line_is_blank (void);

  virtual void parse_last_line (void);
  void parse_last_line_as_historical_data (void);
  void parse_last_line_as_end_of_historical_data (void);
  void make( void );
  number_array_list_parser( void );

  bool last_line_is_valid_historical_data( void ) const;
  static std::vector< std::string > split_string( const std::string& string_to_split, const std::string& separator );
  static std::string string_before_separator( const std::string& string_to_split, const std::string& separator );
  static std::string string_after_separator( const std::string& string_to_split, const std::string& separator );
  static std::vector< double > numbers_from_string( const std::string& string_to_split );

  void print_number_list_sorted_by( int field_index ) const;
  void print_entry( const std::vector< double >& entry ) const;
};

#endif

/*
*/

#include "number_array_list_parser.h"
#ifndef WHITESPACE_STRIPPER_H
#include "whitespace_stripper.h"
#endif
#ifndef ERROR_LOG_H
#include "error_log.h"
#endif
#ifndef CONTRACT_H
#include "contract.h"
#endif

void
number_array_list_parser::make (void)
{
  simple_input_parser::reset ();
  state = Parsing_historical_data;
  number_list.make ();
}

std::string number_array_list_parser::transformed_line (const std::string & str) const
{
  return whitespace_stripper::string_stripped_of_whitespace (string_stripped_of_comments (str));
}

std::string
  number_array_list_parser::string_stripped_of_comments (const std::string & str) const
{
  const std::string::size_type comment_index = str.find (inline_comment_begin);
  return str.substr (0, comment_index);
}

bool 
number_array_list_parser::is_double (const std::string & str)
{
  bool
    Result = true;
  char *
    conversion_end = NULL;
  strtod (str.c_str (), &conversion_end);
  if (conversion_end == str.data ())
    {
      Result = false;
    }
  return Result;
}

double
number_array_list_parser::double_from_string (const std::string & str)
{
  REQUIRE (is_double (str));
  return strtod (str.c_str (), NULL);
}


const
  std::string & number_array_list_parser::historical_data_terminator = "stop";

const
  std::string & number_array_list_parser::inline_comment_begin = "--";

bool number_array_list_parser::last_line_is_blank (void)
{
  if (last_line ().length () == 0)
    {
      return true;
    }
  else
    {
      return false;
    }
}

void
number_array_list_parser::parse_last_line (void)
{
  if (last_line_is_blank ())
    {
      return;
    }
  if ( state == Parsing_historical_data )
    {
      if ( last_line () == historical_data_terminator)
	{
	  parse_last_line_as_end_of_historical_data ();
	}
      else
	{
	  parse_last_line_as_historical_data ();
	}
      //        else
      //  	{
      //  	  parse_last_line_as_prediction ();
      //  	}
    }
}


void
number_array_list_parser::parse_last_line_as_historical_data (void)
{
  if ( last_line_is_valid_historical_data() )
    {
      const std::vector< double >this_entry = numbers_from_string( last_line() );
      number_list.add_entry( this_entry );
    }
  else
    {
      error_log errlog;
      errlog.log_error( std::string( "Invalid data entry: " ) + last_line() );
    }
}
  
void
number_array_list_parser::parse_last_line_as_end_of_historical_data (void)
{
  REQUIRE (last_line () == historical_data_terminator);
  cout << "Historical data read; " 
       << number_list.entry_count() << " entries, " 
       << number_list.field_count() << " fields.\n";
  if ( number_list.entry_count() > 0 )
    {
      for ( int i = 0; i < number_list.field_count(); ++i )
	{
	  print_number_list_sorted_by( i );
	}
    }
  state = Parsing_prediction_data;
}

number_array_list_parser::number_array_list_parser (void)
{
  make();
}


bool
number_array_list_parser::last_line_is_valid_historical_data( void ) const
{
  const std::vector< std::string > substrings = split_string( last_line(), "," );
  bool Result = true;
  //make sure we have a valid field count for the number_array_list
  if ( ( number_list.entry_count() > 0 ) && ( substrings.size() != number_list.field_count() ) )
    {
      Result = false;
    }
  //...and that each substring can be interpreted as a double
  for ( int i = 0; i < substrings.size(); ++i )
    {
      if ( !is_double( substrings[ i ] ) )
	{
	  Result = false;
	}
    }
  return Result;
}

std::vector< std::string >
number_array_list_parser::split_string( const std::string& string_to_split, const std::string& separator ) 
{
  std::vector< std::string > Result;
  const std::string prefix = string_before_separator( string_to_split, separator );
  const std::string remainder = string_after_separator( string_to_split, separator );
  Result.push_back( prefix );
  if ( remainder.size() > 0 )
    {
      const std::vector< std::string > split_remainder = split_string( remainder, separator );
      Result.insert( Result.end(), split_remainder.begin(), split_remainder.end() );
    }
  return Result;
}

std::string
number_array_list_parser::string_before_separator( const std::string& string_to_split, const std::string& separator )
{
  const std::string::size_type separator_position = string_to_split.find( separator );
  std::string Result;
  if ( separator_position == string_to_split.npos )
    {
    //not found; result is entire string
      Result = string_to_split;
    }
  else
    {
      Result = string_to_split.substr( 0, separator_position );
    }
  return Result;
}

std::string
number_array_list_parser::string_after_separator( const std::string& string_to_split, const std::string& separator )
{
  const std::string::size_type separator_position = string_to_split.find( separator );
  std::string Result;
  if ( separator_position == string_to_split.npos )
    {
      //not found; result is empty
      Result = "";
    }
  else
    {
      Result = string_to_split.substr( separator_position + separator.size(), string_to_split.size() );
    }
  return Result;
}

std::vector< double >
number_array_list_parser::numbers_from_string( const std::string& string_to_split )
{
  const std::vector< std::string > number_strings = split_string( string_to_split, "," );
  std::vector< double > Result;
  for ( std::vector< std::string >::const_iterator iter = number_strings.begin(); iter != number_strings.end(); ++iter )
    {
      CHECK( is_double( *iter ) );
      const double new_value = double_from_string( *iter );
      Result.push_back( new_value );
    }
  return Result;
}

void
number_array_list_parser::print_number_list_sorted_by( int field_index ) const
{
  cout << "Sorted by field " << field_index << "\n";
  const number_array_list sorted_list = number_list.sorted_by( field_index );
  for ( number_array_list::const_iterator iter = sorted_list.begin(); iter != sorted_list.end(); ++iter )
    {
      print_entry( *iter );
      cout << "\n";
    }
  cout << "\n\n";
}

void 
number_array_list_parser::print_entry( const std::vector< double >& entry ) const
{
  cout << "( ";
  for ( std::vector< double >::const_iterator iter = entry.begin(); iter != entry.end(); ++iter )
    {
      cout << *iter;
      if ( ( iter + 1 ) != entry.end() )
	{
	  cout << ", ";
	}
    }
  cout << " )";
}


/*
*/

/*
*/

#include <fstream>
#include <iostream>
#include "string.h"

#ifndef NUMBER_ARRAY_LIST_PARSER_H
#include "number_array_list_parser.h"
#endif
#ifndef CONTRACT_H
#include "contract.h"
#endif

istream *
input_stream_from_args (int arg_count, const char **arg_vector)
{
  istream *Result = NULL;
  if (arg_count == 1)
    {
      Result = &cin;
    }
  else
    {
      const char *help_text =
	"PSP exercise 8A: Sort a linked list of entries.\nUsage:\n\tpsp_5a\n\n";
      cout << help_text;
    }
  return Result;
}

int
main (int arg_count, const char **arg_vector)
{
  //get the input stream, or print the help text as appropriate
  istream *input_stream = input_stream_from_args (arg_count, arg_vector);
  if (input_stream != NULL)
    {
      number_array_list_parser parser;
      parser.set_input_stream (input_stream);
      try 
	{
	  parser.parse_until_eof ();
	}
      catch ( yak_exception& e )
	{
	  cerr << "Exception: " << e.what() << "\n";
	}
    }
}

/*
*/

class NUMBER_ARRAY_LIST
   
inherit
   LINKED_LIST[ ARRAY[ DOUBLE ] ]
      redefine
	 make;
   
creation
   make, make_from_entry, make_from_list
      
feature { ANY }
   
   field_count : INTEGER
	 --number of fields allowed in an entry
   
   head : like item is
      --first item
      require
	 entry_count >= 1
      do
	 Result := first;
      end
   
   tail : like Current is
	 --all items after the first
      do
	 !!Result.make
	 if ( entry_count > 1 ) then
	    Result := slice( lower + 1, upper );
	    Result.set_field_count( field_count )
	 end --if
      ensure
	 ( entry_count > 1 ) implies Result.entry_count = entry_count - 1 and Result.field_count = field_count
      end
   
   suffixed_by_list( rhs: like Current ) : like Current is
	 --the list, suffixed by another list
      local
	 i : INTEGER
      do
	 !!Result.make_from_list( Current );
	 from
	    i := rhs.lower
	 until
	    not rhs.valid_index ( i )
	 loop
	    Result.add_entry( rhs.item( i ) );
	    i := i + 1
	 end --from
      ensure
	 Result.entry_count = entry_count + rhs.entry_count
      end
   
   make_from_entry( entry : like item ) is
	 --clear the list, then add the entry
      do
	 make
	 add_entry( entry )
      ensure
	 head.equals( entry )
	 field_count = entry.count
      end
   
   make is
	 --clear the list
      do
	 Precursor
	 field_count := -1
      ensure
	 entry_count = 0
	 field_count = -1
      end
   
   make_from_list( rhs: like Current ) is
	 --clear the list, setting it equal to another list
      do
	 from_collection( rhs )
	 field_count := rhs.field_count
      end
   
   sum_by_field( field_index : INTEGER ) : DOUBLE is
	 --the sum of a given field over all entries
      require
	 is_valid_field_index( field_index )
      do
	 if entry_count = 0 then
	    Result := 0
	 else
	    Result := head.item( field_index ) + tail.sum_by_field( field_index )
	 end
      end
   
   mean_by_field( field_index : INTEGER ) : DOUBLE is
	 --the mean of a given field over all entries
      require
	 is_valid_field_index( field_index )
	 entry_count >= 1
      do
	 Result := sum_by_field( field_index ) / entry_count.to_double
      end
   
   entry_count : INTEGER is
	 --the number of entries
      do
	 Result := count
      end
   
   add_entry( new_entry : like item ) is
	 -- adds an entry to the end of the list
      require
	 is_valid_entry( new_entry )
      do
	 if entry_count = 0 then
	    set_field_count( new_entry.count )
	 end
	 add_last( new_entry )
      ensure
	 entry_count = old entry_count + 1
      end
   
   mapped_to( field_index : INTEGER; f: SINGLE_VARIABLE_FUNCTION ) : like Current is
	 --the elements, with the given field mapped to f
      require
	 is_valid_field_index( field_index )
      local
	 new_entry : like item
      do
	 !!Result.make
	 if entry_count > 0 then
	    new_entry := head
	    new_entry.put( f.at( head.item(field_index) ), field_index )
	    Result.add_entry( new_entry );
	    Result := Result.suffixed_by_list( tail.mapped_to( field_index, f ) )
	 end -- if
      ensure
	 Result.entry_count = entry_count
      end
   
   multiplied_by_list( field_index : INTEGER; rhs : like Current ) : like Current is
      --the elements, with the given field multiplied by the 
	 --corresponding field in rhs
      require
	 entry_count = rhs.entry_count
	 field_count = rhs.field_count
	 is_valid_field_index( field_index )
      local
	 new_entry : like item
      do
	 !!Result.make
	 if entry_count > 0 then
	    new_entry := head
	    new_entry.put( head.item( field_index ) * rhs.head.item( field_index ), field_index )
	    Result.add_entry( new_entry )
	    Result := Result.suffixed_by_list( tail.multiplied_by_list( rhs.tail ) )
	 end
      ensure
	 Result.entry_count = entry_count
      end
   
   sorted_by( field_index : INTEGER ) : like Current is
	 --the list, sorted by the given field
      require
	 is_valid_field_index( field_index )
      do
	 if is_sorted_by( field_index ) then
	    !!Result.make_from_list( Current )
	 else
	    !!Result.make_from_list( tail.items_less_than( field_index, head.item( field_index ) ).sorted_by( field_index ).
				     suffixed_by_item( head ).
				     suffixed_by_list( tail.items_greater_than_or_equal_to( field_index, head.item( field_index ) ).sorted_by( field_index ) ) )
	 end -- if
      ensure
	 Result.entry_count = entry_count
      end
   
   is_valid_entry( entry : like item ) : BOOLEAN is
	 --whether entry is a valid entry
      do
	 if ( entry_count = 0 and entry.count > 0 ) or ( entry.count = field_count and entry.lower = 1 ) then
	    Result := true
	 else
	    Result := false
	 end
      end
   
   items_less_than( field_index : INTEGER; value : DOUBLE ) : like Current is
	 --list of items less than the given value in the given field
      require
	 is_valid_field_index( field_index )
      local
	 i : INTEGER
      do
	 !!Result.make
	 from
	    i := lower
	 until
	    not valid_index( i )
	 loop
	    if not( item( i ).item( field_index ) >= value ) then
	       Result.add_entry( item( i ) )
	    end
	    i := i + 1
	 end
      ensure
	 Result.entry_count <= entry_count
      end
   
   items_greater_than_or_equal_to( field_index : INTEGER; value : DOUBLE ) : like Current is
      --list of items greater than or equal to the given value in the 
	 --given field
      require
	 is_valid_field_index( field_index )
      local
	 i : INTEGER
      do
	 !!Result.make
	 from
	    i := lower
	 until
	    not valid_index( i )
	 loop
	    if item(i).item( field_index ) >= value then
	       Result.add_entry( item( i ) )
	    end
	    i := i + 1
	 end
      ensure
	 Result.entry_count <= entry_count
      end
   
   suffixed_by_item( entry : like item ) : like Current is
	 --the list, suffixed by a single item
      require
	 is_valid_entry( entry )
      do
	 !!Result.make_from_list( Current )
	 Result.add_entry( entry )
      ensure
	 Result.entry_count = entry_count + 1
      end
   
   set_field_count( new_field_count : INTEGER ) is
	 --sets the field count
      require
	 entry_count = 0 or ( entry_count > 0 implies head.count = new_field_count )
      do
	 field_count := new_field_count
      ensure
	 field_count = new_field_count
      end
   
   is_valid_field_index( field_index : INTEGER ) : BOOLEAN is
	 --whether the given field index is valid
      do
	 if entry_count = 0 then
	    Result := true
	 else
	    Result := ( ( 1 <= field_index ) and ( field_index <= field_count ) )
	 end
      end
   
   is_sorted_by( field_index : INTEGER ) : BOOLEAN is
	 --whether the list is sorted by the given field index
      require
	 is_valid_field_index( field_index )
      do
	 Result := true
	 if entry_count > 1 then
	    Result := ( head.item( field_index ) < tail.head.item( field_index ) ) 
	       and tail.is_sorted_by( field_index )
	 end
      end
   
end

	 
			     
	 

class NUMBER_ARRAY_LIST_PARSER
--reads a list of number pairs, and performs linear regression analysis

inherit 
   SIMPLE_INPUT_PARSER
      redefine parse_last_line, transformed_line
      end; 
   
creation {ANY} 
   make

feature {ANY} 
   
   inline_comment_begin: STRING is "--";
   
   string_stripped_of_comment(string: STRING): STRING is 
      --strip the string of any comment
      local 
         comment_index: INTEGER;
      do  
         if string.has_string(inline_comment_begin) then 
            comment_index := string.index_of_string(inline_comment_begin);
            if comment_index = 1 then 
               !!Result.make_from_string( "" );
            else 
               Result := string.substring(1,comment_index - 1);
            end; 
         else 
            Result := string.twin;
         end; 
      end -- string_stripped_of_comment
   
   string_stripped_of_whitespace(string: STRING): STRING is 
      --strip string of whitespace
      do  
         Result := string.twin;
         Result.left_adjust;
         Result.right_adjust;
      end -- string_stripped_of_whitespace
   
   transformed_line(string: STRING): STRING is 
      --strip comments and whitespace from parseable line      
      do  
         Result := string_stripped_of_whitespace(string_stripped_of_comment(string));
      end -- transformed_line
   
   number_list: NUMBER_ARRAY_LIST;
   
   state : INTEGER
   
   Parsing_historical_data : INTEGER is unique
   
   Parsing_prediction_data : INTEGER is unique
   
   historical_data_terminator: STRING is "stop";
   
   double_from_string(string: STRING): DOUBLE is 
      require 
         string.is_double or string.is_integer; 
      do  
         if string.is_double then 
            Result := string.to_double;
         elseif string.is_integer then 
            Result := string.to_integer.to_double;
         end; 
      end -- double_from_string
   

feature {ANY} --parsing

   reset is 
      --resets the parser and makes it ready to go again
      do  
         state := Parsing_historical_data;
         number_list.make;
      end -- reset
   
   make is 
      do  
         !!number_list.make;
         reset;
      end -- make
   
   parse_last_line_as_historical_data is 
      --interpret last_line as a pair of comma-separated values
      local 
         error_log: ERROR_LOG;
	 this_line_numbers : ARRAY[ DOUBLE ]
      do  
	 !!error_log.make
	 if last_line_is_valid_historical_data then
	    this_line_numbers := numbers_from_string( last_line )
	    number_list.add_entry( this_line_numbers )
	 else
	    error_log.log_error( "Invalid historical data: " + last_line + "%N" )
	 end
      end
   
   parse_last_line_as_end_of_historical_data is 
      --interpret last line as the end of historical data
      require 
         last_line.compare(historical_data_terminator) = 0; 
      local
	 i : INTEGER
      do  
	 state := Parsing_prediction_data
	 from
	    i := 1
	 until
	    not number_list.is_valid_field_index( i )
	 loop
	    print_number_list_sorted_by( i )
	    i := i + 1
	 end
      end -- parse_last_line_as_end_of_historical_data
   
   parse_last_line is 
      --parse the last line according to state
      do  
         if not last_line.empty then 
	    if state = Parsing_historical_data then
	       if last_line.compare(historical_data_terminator) = 0 then 
		  parse_last_line_as_end_of_historical_data;
	       else 
                  parse_last_line_as_historical_data;
               end; 
            end; 
         end; 
      end -- parse_last_line
   
   last_line_is_valid_historical_data : BOOLEAN is
	 --whether last line is valid historical data
      local
	 substrings : ARRAY[ STRING ]
	 i : INTEGER
      do
	 substrings := split_string( last_line, "," )
	 Result := true
	 if ( number_list.entry_count > 0 and substrings.count /= number_list.field_count ) then
	    Result := false;
	 end
	 --check and see if each substring is convertible to a double
	 from
	    i := substrings.lower
	 until
	    not substrings.valid_index( i )
	 loop
	    if not ( substrings.item(i).is_double or substrings.item(i).is_integer ) then
	       Result := false;
	    end
	    i := i + 1
	 end
      end
   
   split_string( string_to_split, separator : STRING ) : ARRAY[ STRING ] is
      --a list of components of a string, separated by the given 
      --separator, ie split_string( "1,2,3", "," ) = [ "1", "2", "3" ]
      local
	 prior_to_separator : STRING
	 remainder : STRING
	 split_remainder : ARRAY[ STRING ]
	 i : INTEGER
      do
	 prior_to_separator := string_before_separator( string_to_split, separator )
	 remainder := string_after_separator( string_to_split, separator )
	 !!Result.make( 1, 0 )
	 Result.add_last( prior_to_separator )
	 if remainder.count > 0 then
	    split_remainder := split_string( remainder, separator )
	    from
	       i := split_remainder.lower
	    until
	       not split_remainder.valid_index( i )
	    loop
	       Result.add_last( split_remainder.item( i ) )
	       i := i + 1
	    end
	 end
      end
   
   string_before_separator( string_to_split, separator : STRING ) : STRING is
	 --the part of a string which comes before the separator, or 
	 --the whole string if it's not found
      local
	 separator_index : INTEGER
      do
	 separator_index := string_to_split.substring_index( separator, 1 )
	 if ( separator_index = 0 ) then
	    --not found; copy whole string
	    Result := string_to_split.twin
	 else
	    Result := string_to_split.substring( 1, separator_index - 1 )
	 end
      end
   
   string_after_separator( string_to_split, separator : STRING ) : STRING is
	 --the part of the string after the separator,
      local
	 separator_index : INTEGER
      do
	 separator_index := string_to_split.substring_index( separator, 1 )
	 if ( separator_index = 0 ) then
	    --not found; result is empty
	    !!Result.make_from_string( "" )
	 else
	    Result := string_to_split.substring( separator_index + separator.count, string_to_split.count )
	 end
      end
   
   numbers_from_string( string_to_split : STRING ) : ARRAY[ DOUBLE ] is
	 --an array of numbers, from a string of numbers separated by commas
      local
	 number_strings : ARRAY[ STRING ]
	 i : INTEGER
      do
	 !!Result.make( 1, 0 )
	 number_strings := split_string( string_to_split, "," )
	 from
	    i := number_strings.lower
	 until
	    not number_strings.valid_index( i )
	 loop
	    check
	       number_strings.item(i).is_double or number_strings.item(i).is_integer
	    end
	    Result.add_last( double_from_string( number_strings.item( i ) ) )
	    i := i + 1
	 end
      end
   
   print_number_list_sorted_by( field_index : INTEGER ) is
	 --prints the number list, sorted by field
      local
	 sorted_list : NUMBER_ARRAY_LIST
	 i : INTEGER
      do
	 sorted_list := number_list.sorted_by( field_index )
	 std_output.put_string( "Sorted by " )
	 std_output.put_integer( field_index )
	 std_output.put_new_line
	 from
	    i := sorted_list.lower
	 until
	    not sorted_list.valid_index( i )
	 loop
	    print_entry( sorted_list.item( i ) )
	    std_output.put_string( "%N" )
	    i := i + 1
	 end
	 std_output.put_string( "%N%N" )
      end
   
   print_entry( entry : ARRAY[ DOUBLE ] ) is
	 --prints an entry
      local
	 i : INTEGER
      do
	 std_output.put_string( "( " )
	 from
	    i := entry.lower
	 until
	    not entry.valid_index( i )
	 loop
	    std_output.put_double( entry.item( i ) )
	    if ( entry.valid_index( i + 1 ) ) then
	       std_output.put_string( ", " )
	    end
	    i := i + 1
	 end
	 std_output.put_string( " )" )
      end

end -- class NUMBER_ARRAY_LIST_PARSER

class MAIN

creation {ANY} 
   make

feature {ANY} 
   
   make is 
      local 
         parser: NUMBER_ARRAY_LIST_PARSER;
      do  
         !!parser.make;
         parser.set_input(io);
         parser.parse_until_eof;
      end -- make

end -- MAIN