/*----------------------------------------------------------------------------
FILE NAME:     array.cpp
               SOLUTION RECOMMENDATIONS to HMW 1, JAN 2003

AUTHOR:        Stefano Basagni

CREATED:       January 2003

DESCRIPTION:   Example of a simple C++ program to test functions on arrays.

---
Copyright (C) 2003 Stefano Basagni

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

To receive a copy of the GNU General Public License write to
the Free Software Foundation, Inc., 59 Temple Place - Suite
330, Boston, MA 02111-1307, USA.

Stefano Basagni can be contacted at basagni@ece.neu.edu.

----------------------------------------------------------------------------*/
// INCLUDE SECTION
#include <iostream.h>
#include <iomanip.h>
#include <math.h>
#include <algo.h>
#include <string>

// Pseudo-random number generation
#include "rstream.h"

// CONSTANT SECTION
const int MAXINT = 65536;

// PROTOTYPES
// Initialize and array with random integer numbers
void initR( int A[], int n, int lb, int ub );

void printArray( int A[], int n );

int piccolo( int A[], int n );

int oddSumma( int A[], int n );

bool isFancy( int A[], int n );

bool goodString( string s );

bool checkPar( string s ); 

void printSingles();

void printSingles2();

void sieve( bool B[], int n );


//---------------------------------------------------------------------
// MAIN
int main() {

  int nn = 10;
  int AA[ nn ];  

  // Testing piccolo
  initR( AA, nn, -10, MAXINT-1 );
  cout << "The smallest element of the array:" << endl;  
  printArray( AA, nn );
  cout << "is " << piccolo( AA, nn ) << endl;

  cout << "* * * * * * * * * * * * * * * * * * * * * * * * * * *" << endl;

  // Testing oddSumma
  initR( AA, nn, 0, 10 );
  cout << "The sum of the elements in odd positions of the array: " 
       << endl;
  printArray( AA, nn );
  cout << "is: " << oddSumma( AA, nn ) << endl;

  cout << "* * * * * * * * * * * * * * * * * * * * * * * * * * *" << endl;

  // Testing isFancy
  initR( AA, nn, 0, 15 );
  cout << "The array: ";
  printArray( AA, nn );
  if ( isFancy( AA, nn ) )
      cout << "is fancy!" << endl;
    else 
      cout << "is NOT fancy" << endl;
  for( int b = 0; b < nn; b++ )
    AA[ b ] = 0;
  cout << "The array: ";  
  printArray( AA, nn );
  if ( isFancy( AA, nn ) )
    cout << "is fancy!" << endl;

  cout << "* * * * * * * * * * * * * * * * * * * * * * * * * * *" << endl;

  // Testing printSingles
  //  printSingles();
  //  printSingles2();

  cout << "* * * * * * * * * * * * * * * * * * * * * * * * * * *" << endl;

  // Testing checkPar
  string ss;
  cout << "Type in a string of parenthes: ";
  cin >> ss;
  // Check if ss contains only parentheses
  while ( !goodString( ss ) ) { 
    cout << "String must contain only parentheses. Re-enter: ";
    cin >> ss;
  }
  // Test checkPar
  if ( checkPar( ss ) ) 
    cout << "Good string!" << endl;
  else 
    cout << "Bad string!" << endl;

  cout << "* * * * * * * * * * * * * * * * * * * * * * * * * * *" << endl;

  // Testing Eratosthenes' sieve
  int e;
  cout << "Enter number > 1 up to which you want to find prime numbers: ";
  cin >> e;
  while ( e < 2 ) {
      cout << "The number must be > 1. Please, re-enter: ";
		cin >> e;
  }
  cout << "The prime numbers up to " << e << " (inclusive) are: " << endl;
  bool BB[ e + 1 ];
  sieve( BB, e + 1 );
  for( int c = 2; c < e + 1; c++ )
    if ( BB[ c ] )
      cout << c << " ";
  cout << endl;

  return 0;

}
  

//---------------------------------------------------------------------
// FUNCTION DEFS
//---------------------------------------------------------------------
// Initialize and array with random integer numbers
void initR( int A[], int n, int lb, int ub ) {
  // Random stream for the positions
  static Rstream aElem( 1965 );
  for( int a = 0; a < n ; a++ ) 
	 A[ a ] = aElem.uniform_discrete( lb, ub );
}

//---------------------------------------------------------------------
// Print an array of n elements 
void printArray( int A[], int n ) {
  for( int a = 0; a < n; a++ )
    cout << A[ a ] << " ";
  cout << endl;
}

//---------------------------------------------------------------------
// Return the smaller element of the array (Problem 1)
int piccolo( int A[], int n ) {
  int p = A[ 0 ];
  for( int a = 1; a < n; a++ )
    if ( p > A[ a ] )
      p = A[ a ]; 
  return p;
}

//---------------------------------------------------------------------
// Compute the sum of the element of an array that are in odd positions
// (Problem 2)
int oddSumma( int A[], int n ) {
  int oSum = 0;
  for( int a = 1; a < n; a = a + 2 )
    oSum += A[ a ];
  return oSum;  
}

//---------------------------------------------------------------------
// Check is an array is fancy (Problem 3)
bool isFancy( int A[], int n ) { 
  int pSum = A[ 0 ], a = 1;
  while ( a < n )
    if ( pSum == A[ a ] ) {
      pSum += A[ a ];
      a++;
    }
    else
      return false;
  return true;
}

//---------------------------------------------------------------------
// Check if the string s contains only parentheses (useful fopr testing
// the following function)
bool goodString( string s ) {
  bool foundDif = false;
  unsigned int a = 0;
  cout << s.length() << endl;
  while ( ( a < s.length() ) && ( !foundDif ) ) {
    foundDif = ( ( s[ a ] != '(' ) && ( s[ a ] != ')' ) );
	 a++;
  }
  return !foundDif;
}

//---------------------------------------------------------------------
// Check if s is a "good" string of parentheses (Problem 4)
bool checkPar( string s ) {
  int count = 0;
  for( unsigned int a = 0; a < s.length(); a++ ) {
    if ( s[ a ] == '(' ) 
      count++;   
    if ( s[ a ] == ')' ) {
      if ( count == 0 )
        return false;
      count--;
    }
  }  
  return ( count == 0 );
}

//---------------------------------------------------------------------
// Problem 5-1
// This solution minimizes the time
void printSingles() {
  int in;
  bool isIn[ 91 ];
  for( int a = 0; a < 91; a++ )
    isIn[ a ] = false;
  for( int b = 0; b < 20; b++ ) {
	 cout << "Enter an integer number between 10 and 100 (inlusive): ";
	 cin >> in;
    while ( ( in < 10 ) || ( in > 100 ) ) {
      cout << "The number must be in the specified range. Re-enter: ";	
      cin >> in;
	 }
    if ( !isIn[ in - 10 ] )
      cout << "Number " << in << " is not a duplicate." << endl;
    isIn[ in - 10 ] = true;
  }
}

//---------------------------------------------------------------------
// Problem 5-2
// This solution minimizes the space
void printSingles2() {
  int in;
  int entered[ 20 ];
  int e = 0;
  for( int a = 0; a < 20; a++ ) {
    cout << "Enter an integer number between 10 and 100 (inclusive): ";
    cin >> in;
    while ( ( in < 10 ) || ( in > 100 ) ) {
      cout << "The number must be in the specified range. Re-enter: ";	
      cin >> in;
    }
    entered[ e ] = in;
    e++;
    int b = 0;
    bool found = false;
    while ( ( b < e - 1 ) && ( !found ) ) {
      found = ( in == entered[ b ] );
      b++;
	 }
    if ( !found )
      cout  << "Number " << in << " is not a duplicate." << endl; 
  }
}

//---------------------------------------------------------------------
// Prints out the first n prime number
void sieve( bool B[], int n ) {
  for( int a = 0; a < n; a++ )
    B[ a ] = true;
  for( int b = 2; b < n; b++ )
    if ( B[ b ] )
      for( int c = 2 * b; c < n; c = c + b )
        B[ c ] = false;
}