//
//
//
//
// Lab. Calcolo II - Esempio di codice
//
//
//
//
//
//
// <![CDATA[
// Example code: quicksort.
#include <iostream>
#include <iomanip>
#include <string>
#include <fstream>
#include <sstream>
#include <vector>
#include <random>
#include <system_error>
#include <cerrno>
template<typename TNUM> class measurement;
template<typename TNUM>
std::ostream &operator<< (std::ostream &os, const measurement<TNUM> meas);
template<typename TNUM>
std::istream &operator>> (std::istream &is, measurement<TNUM> &meas);
template<typename TNUM> class measurement {
friend std::ostream &operator<<<TNUM> (std::ostream &os, const measurement<TNUM> meas);
friend std::istream &operator>><TNUM> (std::istream &is, measurement<TNUM> &meas);
public:
typedef TNUM value_type;
// Creators
measurement(const TNUM& value, const std::string date,
const std::string observer) :
m_value(value), m_date(date), m_observer(observer) {}
measurement() {}
// Destructor
~measurement() {}
TNUM value() const { return m_value; } // Use as 'rvalue'
TNUM& value() { return m_value; } // Use as 'lvalue'
void value(const TNUM& new_value) { m_value = new_value; } // Value assignment
const std::string &get_date() const { return m_date; }
const std::string &get_observer() const { return m_observer; }
private:
TNUM m_value;
std::string m_date;
std::string m_observer;
};
template<typename TNUM>
std::ostream &operator<< (std::ostream &os, const measurement<TNUM> meas)
{
return os << meas.m_date << " - " << meas.m_observer
<< " - " << meas.m_value;
}
template<typename TNUM>
std::istream &operator>> (std::istream &is, measurement<TNUM> &meas)
{
bool input_done = false;
while(!input_done)
{
std::stringbuf rsbuf;
std::string line;
is.get(rsbuf);
line=rsbuf.str();
if (!line.empty())
{
is.clear(); // We may be at EOF after reading a valid record.
std::string::size_type pos_sep1 = line.find_first_of('-');
std::string::size_type pos_sep2 = line.find_last_of('-');
if (pos_sep1 == std::string::npos || pos_sep2 == std::string::npos)
continue; // Skip malformed lines
meas.m_date = line.substr(0,pos_sep1-1);
meas.m_observer = line.substr(pos_sep1+2, (pos_sep2-pos_sep1-3));
std::istringstream valuestr(line.substr(pos_sep2+1));
valuestr >> meas.m_value;
input_done = true;
}
// Reading an empty string will set std::ios::failbit, which we
// don't want to consider an error.
if (is.rdstate() == std::ios::failbit) is.clear();
if (! is.good()) input_done = true;
else
{
is.get(); // Skip past delimiter (newline).
is.clear(); // Be happy if it doesn't succeed.
}
}
return is;
}
// We try to be as generic as we can by declaring this a template,
// but we'll shortly see how we can save all of this work...
template<typename MCONT>
void quicksort(MCONT &ms, typename MCONT::size_type left_bound,
typename MCONT::size_type right_bound)
{
static std::random_device rndgen;
typename MCONT::size_type partition_size = right_bound - left_bound + 1;
if (partition_size <= 1) return;
typename MCONT::value_type::value_type max, min, median, pick;
std::uniform_int_distribution<int> rndist(0,partition_size-1);
// Choose a partition value with the "median-of-three" method.
max = min = ms[left_bound + rndist(rndgen)].value();
pick = ms[left_bound + rndist(rndgen)].value();
if (pick > max) max = pick;
else if (pick < min) min = pick;
pick = ms[left_bound + rndist(rndgen)].value();
if (pick > max) median = max;
else if (pick < min) median = min;
else median = pick;
typename MCONT::size_type i,k;
for (i = left_bound, k = right_bound; ; i++,k--)
{
while (ms[i].value() < median) i++;
while (ms[k].value() > median) k--;
// Now stop if indexes crossed. This way we are sure that k is the
// last element of the left partition.
if (i>=k) break;
// We found a pair that's out of order. Let's swap them.
typename MCONT::value_type swap = ms[i];
ms[i] = ms[k];
ms[k] = swap;
}
// Operate recursively on the left and right sub-partitions.
quicksort<MCONT>(ms, left_bound, k);
quicksort<MCONT>(ms,k+1,right_bound);
return;
}
int main(int argc, char *argv[])
{
typedef measurement<double> measurement_t;
typedef std::vector<measurement_t> measurement_container_t;
measurement_container_t measurements;
std::ifstream input;
if (argc <= 1)
{
std::cerr << "Usage: " << argv[0] << " <measurement file name to read>"
<< std::endl;
return 1;
}
input.open(argv[1],std::ios::in);
if (!input)
{
std::cerr << argv[0] << ": Error: Cannot read from " << argv[1] << ": "
<< std::system_error(errno, std::system_category()).what()
<< "." << std::endl;
return 1;
}
while (input.good())
{
measurement_t meas;
input >> meas;
if (input.good()) measurements.push_back(meas);
}
std::cout << "Successfully read " << measurements.size() << " elements."
<< std::endl;
// Implicit template instantiation is playing here.
quicksort(measurements, static_cast<measurement_container_t::size_type>(0),
measurements.size()-1);
while (1) // Will exit with break;
{
measurement_t::value_type search_value;
std::cout << "Please enter a value to search for: ";
std::cin >> search_value;
if (! std::cin.good()) break;
//Procedural approach, for the sake of demonstration:
measurement_container_t::size_type lower_bound = 0;
measurement_container_t::size_type upper_bound = measurements.size() - 1;
measurement_container_t::size_type current_guess = (upper_bound + lower_bound) / 2;
bool found = false;
while(upper_bound >= lower_bound)
{
if (measurements[current_guess].value() == search_value)
{
found = true;
break;
}
else if (measurements[current_guess].value() < search_value)
{
lower_bound = current_guess + 1;
}
else
{
// Careful: size_type is unsigned...
if (current_guess == 0) break;
upper_bound = current_guess - 1;
}
current_guess = (upper_bound + lower_bound) / 2;
}
if (found)
std::cout << "Found: " << measurements[current_guess] << std::endl;
else
std::cout << "Value " << search_value << " not found." << std::endl;
}
return 0;
}
]]></plaintext></span>