[C++][Acero] Negative values in NormalizeTime are mapped to the highest uint64_t values

[mroz45]

Describe the bug, including details regarding any error messages, version, and platform.

asof-join-node and sorted-merge-node use the NormalizeTime function, but in its current implementation, negative values are mapped to the highest uint64_t values. In the case of asof-join-node, where the column contains negative numbers at the beginning, they are converted into extremely large values, potentially causing an out-of-order error. The issue can be reproduced with the following test:

TEST(AsofJoinTest, NegativeStartTime) {
 auto l_schema = schema({field("time", int32()), field("key", int32()), field("l_value", int32())});
 auto r_schema = schema({field("time", int32()), field("key", int32()), field("r_value", int32())});


 ASSERT_OK_AND_ASSIGN(auto l_batches, MakeBatchesFromNumString(l_schema, {R"([[-1, -10, 1], [2, 1, 2], [10, 14, 3], [15, 16, 3]])"}));
 ASSERT_OK_AND_ASSIGN(auto r_batches, MakeBatchesFromNumString(r_schema, {R"([[-5, 1, 10], [5, 1, 20], [15, 1, 30], [18, 1, 30]])"}));

 Declaration l_src = {"source", SourceNodeOptions(l_schema, l_batches.gen(false, false))};
 Declaration r_src = {"source", SourceNodeOptions(r_schema, r_batches.gen(false, false))};

 arrow::acero::AsofJoinNodeOptions::Keys left_keys, right_keys;
 left_keys.on_key = arrow::FieldRef("time"); 
 right_keys.on_key = arrow::FieldRef("time"); 

 AsofJoinNodeOptions asof_join_opts({left_keys, right_keys}, 1);

 Declaration asofjoin = {
 "asofjoin", {std::move(l_src), std::move(r_src)}, std::move(asof_join_opts)};

 ASSERT_OK_AND_ASSIGN(auto result, DeclarationToTable(asofjoin));
}

Component(s)

C++