Validator

Before reading this chapter, please make sure you have read the Checker chapter and are familiar with the basic usage of cplib::var::Var. This chapter will not repeat the introduction to this part.

Validator is usually used to validate the validity of the input file for the test case and the "traits" that the input file conforms to.

There are two main differences between validator and checker. Firstly, validator only needs to process one file, which is the input file of the test case (inf). Secondly, the input stream used by validator defaults to "strict mode". In non-strict mode, cplib::io::InStream and cplib::var::Reader will ignore the differences between whitespace characters when using certain functions for reading. In strict mode, each byte will be strictly compared.

Let's start with an example to introduce validator:

Objective: Given an undirected graph with $n$ ($2 \le n \le 1000$) vertices and $m$ ($1 \le m \le 1000$) edges, verify its validity. Also check if it is a connected graph and if it is a tree.

Input format: The first line contains two integers $n$ and $m$. The next $m$ lines each contain two integers $u,v$, representing an edge.

Implementation

Below is a example implementation of a validator:

#include <algorithm>
#include <vector>
 
#include "cplib.hpp"
 
using namespace cplib;
 
CPLIB_REGISTER_VALIDATOR(val);
 
struct Edge {
  int u, v;
 
  static Edge read(var::Reader& in, int n) {
    auto [u, _, v] = in(var::i32("u", 1, n), var::space, var::i32("v", 1, n));
    return {u, v};
  }
};
 
struct Input {
  int n, m;
  std::vector<Edge> edges;
 
  static Input read(var::Reader& in) {
    auto [n, _, m, __] = in(var::i32("n", 2, 1000), var::space, var::i32("m", 1, 1000), var::eoln);
    auto edges = in.read(var::Vec(var::ExtVar<Edge>("edges", n), m, var::eoln));
    in.read(var::eoln);
    return {n, m, edges};
  }
};
 
struct DSU {
  std::vector<int> fa, size;
 
  DSU(int n) {
    fa.resize(n);
    size.resize(n);
    for (int i = 0; i < n; ++i) fa[i] = i, size[i] = 1;
  }
 
  int find(int x) {
    while (x != fa[x]) x = (fa[x] = fa[fa[x]]);
    return x;
  }
 
  void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (size[x] < size[y]) std::swap(x, y);
    size[x] += size[y];
    fa[y] = x;
  }
};
 
bool is_connected(const Input& input) {
  DSU dsu(input.n);
 
  for (auto [u, v] : input.edges) {
    dsu.merge(u - 1, v - 1);
  }
 
  for (int i = 1; i < input.n; ++i) {
    if (dsu.find(i) != dsu.find(0)) return false;
  }
  return true;
}
 
void validator_main() {
  Input input;
 
  val.traits({
      {"g_is_connected", [&]() { return is_connected(input); }},
      {"g_is_tree", [&]() { return input.n == input.m + 1; }, {"g_is_connected"}},
  });
 
  input = val.inf.read(var::ExtVar<Input>("input"));
 
  val.quit_valid();
}

As you can see, the overall structure of the validator is similar to the checker. The following points highlight the differences from the checker.

CPLIB_REGISTER_VALIDATOR(val);

Similar to the checker, validator needs to use the CPLIB_REGISTER_VALIDATOR macro to register the program as a CPLib checker and save the Checker's state in a global variable, named val in this case.

    auto [u, _, v] = in(var::i32(1, n, "u"), var::space, var::i32(1, n, "v"));

In strict mode, when using cplib::var::Reader to read variables, the whitespace characters in between will not be automatically ignored. We need to explicitly read the whitespace. cplib::var::space is a constant that is equivalent to cplib::var::Separator(' ', "space").

    auto edges = in.read(var::Vec(var::ExtVar<Edge>("edges", n), m, var::eoln));

Similarly to the previous code, when reading std::vector, we cannot directly use var::ExtVar<Edge>("edges", n) * m. This is because the default template generated by cplib::var::Var::operator* uses whitespace as the separator, but in this case, the separator is newline. In strict mode, different whitespace characters are not equivalent.

  val.traits({
      {"g_is_connected", [&]() { return is_connected(input); }},
      {"g_is_tree", [&]() { return input.n == input.m + 1; }, {"g_is_connected"}},
  });

Validator not only checks the legality of the input, but can also check if the input file meets certain "traits". Here, we add two traits: "whether the graph is connected" and "whether the graph is a tree".

The constructor of cplib::validator::Trait has two overloaded versions:

• Trait(std::string name, std::function(auto()->bool) check_func);
• Trait(std::string name, std::function(auto()->bool) check_func, std::vector<std::string> dependencies);

The second version can add dependencies for the current trait. The check for this trait will only be performed when all dependencies are true; otherwise, the trait will be set to false.

Usage

The usage of validator is similar to Checker. The only difference is that when calling validator, you only need to pass a file argument <input-file>. Also, to be compatible with the usage habits of Testlib validator, the <input-file> parameter can be omitted, and the standard input stream (stdin) will be automatically used as the input file.

Suggestions

In summary, when writing more complex validators, we recommend the following suggestions:

• Use custom types and cplib::var::ExtVar to encapsulate your code, instead of using basic type reading entirely.
• In the T::read function, check the "validity" of the variables while reading them.
• Always use val.inf to read the input file. Do not use std::cin or C-style input functions to read from stdin. These functions usually do not have the strict formatting requirements and error handling mechanisms required by validator, and using them will also break the internal state of val.inf, resulting in unpredictable behavior.