Mfcttrf

I've made a solution for a problem which involves changing order of objects having some mass, so it costs a mass of an object A and a mass of an object B to make a swap.

The full description of the problem and the original source code is at
Least cost swapping in C++
Please, review my code.

#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
int constexpr MaxWeight = 6500, MinVertexes = 2, MaxVertexes = 1000000;

struct ObjectCollection 

 int amountOfObjects = 0;
 std::vector<int> weights;
 std::vector<int> startingOrder;
 std::vector<int> endingOrder;
 int minWeight = MaxWeight;
;

std::vector<int> readOrder(std::istringstream& iss, int const amountOfObjects) 

 std::vector<int> v;
 v.reserve(amountOfObjects);
 int i = 1;
 while(!iss.eof() && i <= amountOfObjects)
 
 int number;
 iss >> number;
 if (number - 1 > amountOfObjects) throw std::logic_error("Too high index in order");
 v.push_back(number-1);
 i++;
 
 if (v.size() != amountOfObjects) throw std::logic_error("Too few values in line");
 return v;


void readWeightsAndSetMinWeight(std::istringstream& iss, ObjectCollection& objects)

 objects.weights.reserve(objects.amountOfObjects);
 int i = 1;
 while (!iss.eof() && i <= objects.amountOfObjects)
 
 int number;
 iss >> number;
 if (number> MaxWeight) throw std::logic_error("Too high weight");
 objects.weights.push_back(number);
 objects.minWeight = std::min(objects.minWeight, number);
 i++;
 
 if (objects.weights.size() != objects.amountOfObjects) throw std::logic_error("Too few values in line");


//todo version for weight

ObjectCollection readFromFile(std::string const& filename)

 ObjectCollection objects;
 std::ifstream file(filename);

 if (!file.is_open()) throw std::exception("Unable to open file");

 for (int i = 0; i < 4; i++)
 
 std::string line;
 std::getline(file, line);
 if (line.empty()) throw std::logic_error("Invalid input");
 std::istringstream iss(line);

 if (i == 0)
 
 iss >> objects.amountOfObjects;
 if (objects.amountOfObjects<MinVertexes 
 else if (i == 1)
 
 objects.weights.reserve(objects.amountOfObjects);
 for (int j = 0; j < objects.amountOfObjects; j++)
 
 //int number;
 //iss >> number;
 //objects.weights.push_back(number);
 //objects.minWeight = std::min(objects.minWeight, objects.weights[j]);
 readWeightsAndSetMinWeight(iss, objects);
 
 
 else if (i == 2)
 
 objects.startingOrder = readOrder(iss,objects.amountOfObjects);
 
 else if (i == 3)
 
 objects.endingOrder = readOrder(iss, objects.amountOfObjects);
 
 
 return objects;


long long calculateLowestCostOfWork(ObjectCollection const& objects)

 int n = objects.amountOfObjects;
 std::vector<int> permutation(n);

 //constructing permutation
 for (int i = 0; i < n; i++) 
 
 permutation[objects.endingOrder[i]] = objects.startingOrder[i];
 

 long long result = 0;
 std::vector<bool> visitedVertexes(n);

 for (int i = 0; i < n; i++)
 
 int numberOfElementsInCycle = 0;
 int minWeightInCycle = MaxWeight;
 long long sumOfWeightsInCycle = 0;
 if (!visitedVertexes[i])
 
 int vertexToVisit = i;
 //decomposition for simple cycles and calculating parameters for each cycle
 while (!visitedVertexes[vertexToVisit])
 
 visitedVertexes[vertexToVisit] = true;
 numberOfElementsInCycle++;
 vertexToVisit = permutation[vertexToVisit];
 sumOfWeightsInCycle += objects.weights[vertexToVisit];
 minWeightInCycle = std::min(minWeightInCycle, objects.weights[vertexToVisit]);
 
 //calculating lowest cost for each cycle
 long long swappingWithMinWeightInCycle = sumOfWeightsInCycle + (static_cast<long long>(numberOfElementsInCycle) - 2) * static_cast<long long>(minWeightInCycle);
 long long swappingWithMinWeight = sumOfWeightsInCycle + minWeightInCycle + (static_cast<long long>(numberOfElementsInCycle) + 1) * static_cast<long long>(objects.minWeight);
 result += std::min(swappingWithMinWeightInCycle, swappingWithMinWeight);
 
 
 return result;


int main(int argc, char* argv[])

 if (argc < 2)
 
 std::cerr << "Error: missing filenamen";
 return 1;
 

 ObjectCollection elephants;
 try
 
 elephants = readFromFile(argv[1]);
 std::cout << calculateLowestCostOfWork(elephants);
 
 catch (std::exception const& ex) 
 
 std::cerr << "Error: " << ex.what() << "n";
 return 1;
 
 catch (...)
 
 std::cerr << "Error unknown n";
 return 1;
 
 return 0;

This is not a comparative review.

Self Documenting Code

There is a standard header file that supplies constant values for exiting main(). For both C and C++ the standard constants for exiting are EXIT_SUCCESS and EXIT_FAILURE. The C++ header for this is

#include <cstdlib>

int main(int argc, char* argv[])

 if (argc < 2)
 
 std::cerr << "Error: missing filenamen";
 return EXIT_FAILURE;
 

 ObjectCollection elephants;
 try
 
 elephants = readFromFile(argv[1]);
 std::cout << calculateLowestCostOfWork(elephants);
 
 catch (std::exception const& ex)
 
 std::cerr << "Error: " << ex.what() << "n";
 return EXIT_FAILURE;
 
 catch (...)
 
 std::cerr << "Error unknown n";
 return EXIT_FAILURE;
 
 return EXIT_SUCCESS;

Vertical Spacing

The code might be easier to read and maintain if there was some vertical spacing between logic blocks in the functions.

Numeric Constants On Only One Line

The code might be easier to read and maintain each declaration for a numeric constant was on a separate line.

int constexpr MaxWeight = 6500;
int constexpr MinVertexes = 2;
int constexpr MaxVertexes = 1000000;

Then and Else Clauses

Plan for future maintenance. Quite often updating code requires the insertion of an additional statement in a then or else clause in an if statement. It is generally a good practice to make all of the if statements have compound statements to ease future modification. Separating the if from the action also makes the code a little more readable.

 if (number - 1 > amountOfObjects) throw std::logic_error("Too high index in order");

 if (number - 1 > amountOfObjects)
 
 throw std::logic_error("Too high index in order");
 

Variable Names

In the input functions the code might be more understandable if variables used indicated what was being read in, the variable name number might be a little too general. We know it is a number because it is declared as int. In the function int readWeightsAndSetMinWeight() perhaps weight could be used instead of number?

Commented Out Code

When code gets moved into a function, there is generally no reason to leave the code in comments in the original place. It can be confusing to someone that has to maintain the code.

if (line.empty()) throw std::logic_error("Invalid input");

std::logic_error is used for "violating logical preconditions or class invariants", which generally translates to programmer error (and means it's seldom the correct exception type to use).

Invalid input data certainly doesn't fit this category, and we should probably use std::runtime_error instead.

for (int i = 0; i < 4; i++)

 std::string line;
 std::getline(file, line);
 if (line.empty()) throw std::logic_error("Invalid input");
 std::istringstream iss(line);

 if (i == 0) ...
 else if (i == 1) ...
 else if (i == 2) ...
 else if (i == 3) ...

A for loop with a separate branch for every iteration? Hmm.

We can avoid this by abstracting the code that needs to be repeated (reading a line) into a separate function, and then do something like:

objects.count = ReadObjectCount(readLine(file));
objects.weights = ReadObjectWeights(readLine(file), objects.count);
objects.minWeight = CalculateMinWeight(objects.weights);
objects.startingOrder = ReadObjectOrder(readLine(file), objects.count);
objects.endingOrder = ReadObjectOrder(readLine(file), objects.count);
...

It's probably neater to calculate the min weight after we've read all of the weights, instead of doing it as we go.

The amountOfObjects should be a std::size_t, since it can't be negative, and should match the vectors' index type.

Similarly, the order vectors should contain std::size_t if they represent indices into a vector.

Presumably weights can also never be negative. So we should use an unsigned type like std::uint32_t or std::uint64_t for them, and be consistent (the current code uses both int and long long).

std::vector<int> readOrder(std::istringstream& iss, int const amountOfObjects) 

 std::vector<int> v;
 v.reserve(amountOfObjects);
 int i = 1;
 while(!iss.eof() && i <= amountOfObjects)
 
 int number;
 iss >> number;
 if (number - 1 > amountOfObjects) throw std::logic_error("Too high index in order");
 v.push_back(number-1);
 i++;
 
 if (v.size() != amountOfObjects) throw std::logic_error("Too few values in line");
 return v;

We should check that we read each number successfully by checking the stream state. (Again, we can abstract that into a separate function).

Presumably the indices must be >= 0 (as well as less than the object count), so we should check that if we aren't using an unsigned type.

Maybe something like:

std::size_t readValue(std::istringstream& iss)

 std::size_t value;
 iss >> value;

 if (!iss) // check if we failed to read the value
 throw std::runtime_error("Invalid input.");

 return value;


std::vector<std::size_t> readOrder(std::istringstream iss, std::size_t objectCount)

 std::vector<std::size_t> v;
 v.reserve(objectCount);

 for (auto i = std::size_t0; i != objectCount; ++i)
 v.push_back(readValue(iss, objectCount));

 std::string anything;
 iss >> anything;

 if (!iss.eof())
 throw std::runtime_error("Extra stuff at end of line.");

 OffsetAndCheckValues(v); // do the range checking and -1

 return v;

Doing the range checking and offsetting by 1 later (after reading all the values), makes the readValue function more reusable.

In C++ it's usual to iterate using the pre-increment operator (++i), because it reflects the intent more accurately (we don't need a temporary unincremented variable).

It's also more common to use != as the end condition, instead of <, since this translates better to using iterators.

Make sure to use the appropriate type for iteration (e.g. std::size_t for iterating over vector indices).

for (std::size_t i = 0; i != objects.count; ++i)

It's good to use descriptive names, but some of them are a bit excessive. At some point the longer names just hinder readability.

std::vector<bool> visited(objects.count);
...
 std::size_t cycleSize = 0;
 std::uint64_t cycleMin = MaxWeight;
 std::uint64_t cycleSum = 0;

Prefer to return or continue early to avoid unnecessary indentation:

 if (visited[i])
 continue;

 // no need to indent this code...

Note that numberOfElementsInCycle (and others) aren't used if we have visited the vertex, so could be declared after this check.