4
\$\begingroup\$

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 || objects.amountOfObjects>MaxVertexes) throw std::exception("Invalid amount of vertexes");
        }
        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 filename\n";
        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;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Could you include the task description in this question as well? Even if it's just a copy-paste. Having to go through links to know what the question is about is something not many reviewers appreciate. \$\endgroup\$ – dfhwze Aug 17 at 15:48
7
\$\begingroup\$

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 filename\n";
        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.

\$\endgroup\$
4
\$\begingroup\$
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_t{0}; i != objectCount; ++i)
        v.push_back(readValue(iss, objectCount));

    std::string anything;
    iss >> anything;

    if (!anything.empty() || !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.

\$\endgroup\$
  • \$\begingroup\$ "It's probably neater to calculate the min weight after we've read all of the weights, instead of doing it as we go." But that costs reading all vector (even 1 000 000 elements) again. \$\endgroup\$ – Jan Dycz Aug 18 at 0:44
  • 1
    \$\begingroup\$ 1. Yeah. But reading those 1000000 elements from a text file on the hard-drive is probably so slow in comparison that it doesn't matter. \$\endgroup\$ – user673679 Aug 18 at 7:27
  • 1
    \$\begingroup\$ 2. You can use a different type for the sum if it's necessary, but it's simpler not to (and we should really be checking for overflow with whatever type we use). Either way an unsigned type gives us more range than a signed one. \$\endgroup\$ – user673679 Aug 18 at 7:51
  • 1
    \$\begingroup\$ @JanDycz Sounds like that error is because you can't assign a value to a non-const reference. If you change the function to take the istringstream by value, it should work. \$\endgroup\$ – user673679 Aug 19 at 5:20
  • 1
    \$\begingroup\$ std::string anything; was to check that there's nothing else (other than whitespace) on the current line. If anything isn't empty after trying to read into it, or if we didn't hit eof(), then there's some extra data on the line. Thinking about it, it's probably better just to check for eof after reading the last expected value (although that would disallow any trailing whitespace). \$\endgroup\$ – user673679 Aug 19 at 5:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.