text:
/* boosted_stumps.cc
   Jeremy Barnes, 6 June 2003
   Copyright (c) 2003 Jeremy Barnes.  All rights reserved.
   $Source$

   Implementation of boosted decision stumps.
*/

#include "boosted_stumps.h"
#include "classifier_persist_impl.h"
#include "jml/math/xdiv.h"
#include "jml/arch/simd_vector.h"
#include "boosted_stumps_impl.h"
#include "stump_predict.h"
#include "jml/utils/environment.h"
#include <boost/timer.hpp>
#include <boost/progress.hpp>
#include "jml/utils/floating_point.h"
#include "jml/utils/vector_utils.h"
#include "boosting_core.h"
#include "boosting_training.h"
#include "config_impl.h"
#include "binary_symmetric.h"
#include "jml/utils/worker_task.h"
#include "jml/utils/guard.h"
#include <iostream>
#include <boost/bind.hpp>

using namespace std;
using namespace DB;

namespace ML {

namespace {

Env_Option<bool> profile("PROFILE_BOOSTED_STUMPS", false);

double t_train = 0.0, t_update = 0.0, t_predict = 0.0, t_accuracy = 0.0;

struct Stats {
    ~Stats()
    {
        if (profile) {
            cerr << "Boosted stumps profile: " << endl;
            cerr << "  train:          " << t_train       << "s" << endl;
            cerr << "  update:         " << t_update      << "s" << endl;
            cerr << "  predict:        " << t_predict     << "s" << endl;
            cerr << "  accuracy:       " << t_accuracy    << "s" << endl;
        }
    }
} stats;

class Function_Profiler {
public:
    boost::timer * t;
    double & var;
    Function_Profiler(double & var)
        : t(0), var(var)
    {
        if (profile) t = new boost::timer();
    }
    ~Function_Profiler()
    {
        if (t) var += t->elapsed();
        delete t;
    }
};

#define PROFILE_FUNCTION(var) \
Function_Profiler __profiler(var);

} // file scope

/*****************************************************************************/
/* BOOSTED_STUMPS                                                            */
/*****************************************************************************/

Boosted_Stumps::Boosted_Stumps()
{
}

Boosted_Stumps::
Boosted_Stumps(const std::shared_ptr<const Feature_Space> & feature_space,
               const Feature & predicted)
    : Classifier_Impl(feature_space, predicted)
{
    output = RAW;
}

Boosted_Stumps::
Boosted_Stumps(DB::Store_Reader & reader,
               const std::shared_ptr<const Feature_Space> & feature_space)
{
    this->reconstitute(reader, feature_space);
}

Boosted_Stumps::
Boosted_Stumps(const std::shared_ptr<const Feature_Space> & feature_space,
               const Feature & predicted,
               size_t label_count)
    : Classifier_Impl(feature_space, predicted, label_count)
{
}

namespace {

/** Class for the results which updates a whole distribution at once. */
struct Results_Dist {
    Results_Dist(distribution<float> & results,
                 const Feature_Space & fs)
        : results(results), fs(fs) {}

    void operator () (const distribution<float> & dist, float weight,
                      const Feature & feature) const
    {
        //cerr << "feature = " << fs.print(feature) << endl;
        //cerr << "  adding " << weight << " * " << dist;
        results += weight * dist;
        //cerr << "  result now " << results << endl;
    }

    distribution<float> & results;
    const Feature_Space & fs;
};

/** Class for the results which updates a single distribution at once. */
struct Results_Single {
    Results_Single(float & result, int label)
        : result(result), label(label) {}

    JML_ALWAYS_INLINE
    void operator () (const distribution<float> & dist, float weight,
                      const Feature & feature) const
    {
        result += weight * dist[label];
    }

    float & result;
    int label;

};

} // file scope

distribution<float>
Boosted_Stumps::
predict(const Feature_Set & features) const
{
    PROFILE_FUNCTION(t_predict);
    distribution<float> result(label_count());
    if (bias.size()) result += bias;
    predict_core(features, Results_Dist(result, *feature_space()));

    for (unsigned i = 0;  i < result.size();  ++i) {
        if (!finite(result[i])) {
            cerr << "result = " << result << endl;
            throw Exception("Boosted_Stumps::predict(): non-finite result");
        }
    }

    //cerr << "result = " << result << endl;

    //result =- result.max();

    //result = exp(result);
    //result.normalize();
    //result -= 0.5;

    double total = 0.0;

    if (output == LOGIT || output == LOGIT_NORM) {
        for (unsigned i = 0;  i < result.size();  ++i) {
            /* Avoid an overflow from the exp. */
            if (result[i] > fp_traits<float>::max_exp_arg * 0.9)
                result[i] = fp_traits<float>::max_exp_arg * 0.9;
            double e = exp(result[i]);
            double x = e / (e + (1.0 / e));
            total += x;
            result[i] = x;
        }
        if (output == LOGIT_NORM) {
            if ((float)total == 0.0F) {
                cerr << "warning: boosted stumps says no results are correct"
                     << endl;
                result.fill(1);  // assign all elements
                result.normalize();
            }
            else result /= total;
        }
    }

    for (unsigned i = 0;  i < result.size();  ++i) {
        if (!finite(result[i])) {
            distribution<float> result2(label_count());
            if (bias.size()) result2 += bias;
            predict_core(features, Results_Dist(result2, *feature_space()));

            cerr << "result = " << result << endl;
            cerr << "output of predict_core = " << result2 << endl;
            cerr << "total = " << total << endl;

            for (unsigned i = 0;  i < result2.size();  ++i) {
                /* Avoid an overflow from the exp. */
                if (result2[i] > fp_traits<float>::max_exp_arg * 0.9)
                    result2[i] = fp_traits<float>::max_exp_arg * 0.9;
                double e = exp(result2[i]);
                double x = e / (e + (1.0 / e));
                total += x;
                result[i] = x;
                cerr << "  i = " << i << " e = " << e << " x = " << x
                     << endl;
            }

            cerr << "after logit: result = " << result2 << endl;

            throw Exception("non-finite result");
        }
    }

    return result;
}

float
Boosted_Stumps::
predict(int label, const Feature_Set & features) const
{
    PROFILE_FUNCTION(t_predict);
    if (label < 0 || label >= label_count())
        throw Exception(format("Boosted_Stumps::predict(int, Feature_Set): "
                               "Attempt to predict label %d with label_count "
                               " %zd", label, label_count()));

    if (output == LOGIT_NORM) {
        /* Need to predict all, so we know how to normalize.  Could be much
           slower. */
        return predict(features)[label];
    }

    float result = 0.0;
    if (bias.size()) result += bias[label];
    predict_core(features, Results_Single(result, label));
    if (output == LOGIT) {
        double e = exp(result);
        result = e / (e + 1.0 / e);
    }
    return result;
}

Boosted_Stumps::iterator Boosted_Stumps::
insert(const Stump & stump, float weight)
{
    if (stump.split.feature() == MISSING_FEATURE) return end();

    iterator it = find(stump.split);
    if (it == end())
        return iterator
            (stumps.insert(make_pair(stump.split,
                                     stump.scaled(weight))).first);
    else it->merge(stump, weight);
    return it;
}

void Boosted_Stumps::insert(const std::vector<Stump> & stumps)
{
    distribution<float> scales(stumps.size(), 1.0 / stumps.size());
    insert(stumps, scales);
}

void Boosted_Stumps::
insert(const std::vector<Stump> & stumps, const distribution<float> & scale)
{
    if (scale.size() != stumps.size())
        throw Exception(format("Boosted_Stumps::insert(): stumps.size() = %zd"
                               " != scale.size() = %zd", stumps.size(),
                               scale.size()));
    for (unsigned i = 0;  i < stumps.size();  ++i)
        insert(stumps[i], scale[i]);
}

#if 0

namespace {

struct Accuracy_Job_Info {
    const Training_Data & data;
    const distribution<float> & example_weights;
    const Boosted_Stumps & stumps;
    const Optimization_Info & opt_info;
    boost::multi_array<float, 2> & output;
    bool bin_sym;

    Lock lock;
    double & correct;
    double & margin;

    Accuracy_Job_Info(const Training_Data & data,
                      const distribution<float> & example_weights,
                      const Boosted_Stumps & stumps,
                      const Optimization_Info & opt_info,
                      boost::multi_array<float, 2> & output,
                      bool bin_sym,
                      double & correct, double & margin)
        : data(data), example_weights(example_weights),
          stumps(stumps), opt_info(opt_info),
          output(output), bin_sym(bin_sym), correct(correct), margin(margin)
    {
    }

    void calc(unsigned start_x, unsigned end_x)
    {
        double sub_correct = 0.0, sub_margin = 0.0;

        int nl = output.shape()[1];

        const std::vector<Label> & labels
            = data.index().labels(stumps.predicted());

        if (bin_sym) {
            for (Boosted_Stumps::const_iterator it = stumps.begin();
                 it != stumps.end();  ++it) {

                typedef Binsym_Updater<Boosting_Predict> Updater;
                typedef Update_Weights<Updater> Update;
                Updater updater;
                Update update(updater);

                update(*it, opt_info, 1.0, output, data, start_x, end_x);
            }

            /* Now for the scoring. */
            typedef Binsym_Scorer Scorer;
            Scorer scorer;
            if (example_weights.empty()) {
                for (unsigned x = start_x;  x < end_x;  ++x)
                    sub_correct += scorer(labels[x], &output[x][0],
                                          &output[x][0]);
            }
            else {
                for (unsigned x = start_x;  x < end_x;  ++x)
                    sub_correct += scorer(labels[x], &output[x][0],
                                          &output[x][0] + 1)
                        * example_weights[x];
            }
        }
        else {
            for (Boosted_Stumps::const_iterator it = stumps.begin();
                 it != stumps.end();  ++it) {

                typedef Normal_Updater<Boosting_Predict> Updater;
                typedef Update_Weights<Updater> Update;
                Updater updater(nl);
                Update update(updater);

                update(*it, opt_info, 1.0, output, data, start_x, end_x);
            }

            /* Now for the scoring. */
            typedef Normal_Scorer Scorer;
            Scorer scorer;
            if (example_weights.empty()) {
                for (unsigned x = start_x;  x < end_x;  ++x)
                    sub_correct += scorer(labels[x], &output[x][0],
                                          &output[x][0]);
            }
            else {
                for (unsigned x = start_x;  x < end_x;  ++x)
                    sub_correct += scorer(labels[x], &output[x][0],
                                          &output[x][0] + 1)
                        * example_weights[x];
            }
        }

        Guard guard(lock);
        correct += sub_correct;
    }
};

struct Accuracy_Job {
    Accuracy_Job(Accuracy_Job_Info & info,
                 int x_start, int x_end)
        : info(info), x_start(x_start), x_end(x_end)
    {
    }

    Accuracy_Job_Info & info;
    int x_start, x_end;

    void operator () () const
    {
        info.calc(x_start, x_end);
    }
};

} // file scope

std::pair<float, float>
Boosted_Stumps::
accuracy(const Training_Data & data,
         const distribution<float> & example_weights,
         const Optimization_Info * opt_info_ptr) const
{
    PROFILE_FUNCTION(t_accuracy);
    unsigned nx = data.example_count();
    unsigned nl = label_count();

    boost::multi_array<float, 2> scores(boost::extents[nx][nl]);

    bool bin_sym = convert_bin_sym(scores, data, predicted_, all_features());

    double correct = 0.0, margin = 0.0;

    Optimization_Info new_opt_info;
    const Optimization_Info & opt_info
        = (opt_info_ptr ? *opt_info_ptr : new_opt_info);

    Accuracy_Job_Info info(data, example_weights, *this, opt_info,
                           scores, bin_sym,
                           correct, margin);

    static Worker_Task & worker = Worker_Task::instance(num_threads() - 1);

    int group;
    {
        int parent = -1;  // no parent group
        group = worker.get_group(NO_JOB,
                                 format("Boosted_Stumps::accuracy under %d", parent),
                                 parent);
        Call_Guard guard(boost::bind(&Worker_Task::unlock_group,
                                     boost::ref(worker),
                                     group));

        unsigned job_ex = 2048 / scores.shape()[1];

        for (unsigned x = 0;  x < data.example_count();  x += job_ex) {
            unsigned end = std::min(x + job_ex, nx);
            worker.add(Accuracy_Job(info, x, end),
                       format("Boosted_Stumps::accuracy() job %d-%d under %d",
                              x, end, group),
                       group);
        }
    }

    worker.run_until_finished(group);

    double total
        = (example_weights.empty() ? (float)nx : example_weights.total());

    return make_pair(correct / total, margin / total);
}

#else
std::pair<float, float>
Boosted_Stumps::
accuracy(const Training_Data & data,
         const distribution<float> & example_weights,
         const Optimization_Info * opt_info_ptr) const
{
    return Classifier_Impl::accuracy(data, example_weights, opt_info_ptr);
}
#endif

std::string Boosted_Stumps::print() const
{
    string result;
    for (const_iterator it = begin();  it != end();  ++it) {
        result += it->print();
        result += '\n';
    }
    return result;
}

std::vector<ML::Feature> Boosted_Stumps::all_features() const
{
    std::vector<ML::Feature> result;
    for (stumps_type::const_iterator it = stumps.begin();
         it != stumps.end();  ++it)
        result.push_back(it->first.feature());
    make_vector_set(result);
    return result;
}

Output_Encoding
Boosted_Stumps::
output_encoding() const
{
    switch (output) {
    case RAW: return OE_PM_INF;
    case LOGIT:
    case LOGIT_NORM:
        return OE_PROB;
    default:
        throw Exception("Boosted_Stumps::output_encoding(): uknown encoding");
    }
}

void Boosted_Stumps::calc_sum_missing()
{
    distribution<double> totals(label_count());
    for (const_iterator it = begin();  it != end();  ++it) {
        distribution<double> this_val(it->action.pred_missing.begin(),
                                      it->action.pred_missing.end());
        totals += this_val;
    }

    sum_missing = distribution<float>(totals.begin(), totals.end());
}

namespace {

static const std::string BOOSTED_STUMPS_MAGIC = "BOOSTED_STUMPS";
static const compact_size_t BOOSTED_STUMPS_VERSION = 4;

void serialize_dist(const distribution<float> & dist,
                    DB::Store_Writer & store)
{
    bool non_zero = false;
    for (unsigned i = 0;  i < dist.size();  ++i) {
        //if (dist[i] != 0.0) { non_zero = true;  break; }
        if (abs(dist[i]) > 1e-10) { non_zero = true;  break; }
    }

    if (non_zero) {
        bool pos_neg = (dist.size() == 2 && (abs(dist[0] + dist[1]) < 1e-10));
        if (pos_neg)
            store << compact_const(1) << dist[0];
        else store << dist;
    }
    else store << compact_const(0);
}

void reconstitute_dist(distribution<float> & dist,
                       DB::Store_Reader & store,
                       size_t nl)
{
    dist.clear();
    compact_size_t size(store);

    if (size == 0) dist.resize(nl);
    else if (size == 1) {
        dist.resize(2);
        store >> dist[0];
        dist[1] = -dist[0];
    }
    else {
        if (size != nl)
            throw Exception
                (format("reconstituting Boosted_Stumps dist of wrong size: "
                        "is %zd, should be %zd", size.size_, nl));

        dist.resize(size);
        for (unsigned i = 0;  i < nl;  ++i)
            store >> dist[i];
    }
}

} // file scope

COMPACT_PERSISTENT_ENUM_DECL(Boosted_Stumps::Output);
COMPACT_PERSISTENT_ENUM_IMPL(Boosted_Stumps::Output);

void Boosted_Stumps::serialize(DB::Store_Writer & store) const
{
    store << BOOSTED_STUMPS_MAGIC << BOOSTED_STUMPS_VERSION
          << compact_const(label_count());
    feature_space()->serialize(store, predicted_);
    store << output << bias;
    store << compact_const(stumps.size());

    for (stumps_type::const_iterator it = stumps.begin();
         it != stumps.end();  /* no inc */) {

        const Feature & feat = it->first.feature();
        feature_space()->serialize(store, feat);

        /* Work out how many entries we have with this feature. */
        int nf = 0;
        stumps_type::const_iterator first = it;
        while (it != stumps.end() && it->first.feature() == feat) {
            ++nf;
            ++it;
        }

        store << compact_const(nf);
        std::swap(it, first);

        for (unsigned i = 0;  i < nf;  ++i,++it) {
            const Stump & stump = it->second;
            stump.serialize_lw(store);
        }

        if (it != first)
            throw Exception("Boosted_Stumps::serialize(): logic error");
    }
}

void Boosted_Stumps::
reconstitute(DB::Store_Reader & store,
             const std::shared_ptr<const Feature_Space> & features)
{
    /* Implement the strong exception guarantee, except for the store. */
    string magic;
    compact_size_t version;
    store >> magic >> version;
    if (magic != BOOSTED_STUMPS_MAGIC)
        throw Exception("Attempt to reconstitute \"" + magic
                                + "\" with boosted stumps reconstitutor");
    if (version > BOOSTED_STUMPS_VERSION)
        throw Exception(format("Attemp to reconstitute boosted stumps "
                               "version %zd, only <= %zd supported",
                               version.size_,
                               BOOSTED_STUMPS_VERSION.size_));

    compact_size_t label_count(store);

    predicted_ = MISSING_FEATURE;
    if (version >= 4) { // added in version 4
        features->reconstitute(store, predicted_);
    }

    Boosted_Stumps new_me(features, predicted_, label_count);

    if (version >= 1) {  // added in version 1
        store >> new_me.output;
    }
    else new_me.output = RAW;

    if (version >= 2) // added in version 2
        store >> new_me.bias;
    else new_me.bias.clear();

    //ofstream dump("stump-load-dump.txt");

    if (version >= 3) {
        /* Load compact version... */
        compact_size_t stump_count(store);
        int ns = 0;

        while (ns < stump_count) {
            Feature feature;
            features->reconstitute(store, feature);
            compact_size_t nsf(store);  // number of stumps for this feature

            for (unsigned i = 0;  i < nsf;  ++i) {
                Stump stump(features, predicted_, label_count);
                stump.reconstitute_lw(store, feature);
                new_me.insert(stump);
                ++ns;

#if 0
                dump << "stump " << ns << ": " << features->print(stump.feature)
                     << " " << stump.arg << " " << stump.pred_true << " "
                     << stump.pred_false << " " << stump.pred_missing << endl;
#endif
            }
        }

        if (ns != stump_count)
            throw Exception("Boosted_Stumps::reconstitute(): logic error");

        calc_sum_missing();
    }
    else {
        compact_size_t stump_count(store);

        /* Load non-compact versions... */
        for (unsigned i = 0;  i < stump_count;  ++i) {
            Stump stump(store, features);
#if 0
            dump << "stump " << i << ": " << features->print(stump.feature)
                 << " " << stump.arg << " " << stump.pred_true << " "
                 << stump.pred_false << " " << stump.pred_missing << endl;
#endif

            new_me.insert(stump);
        }

        calc_sum_missing();
    }

    swap(new_me);

    //cerr << "predicted_ = " << predicted_ << endl;
}

Boosted_Stumps * Boosted_Stumps::make_copy() const
{
    return new Boosted_Stumps(*this);
}

void Boosted_Stumps::combine(const Boosted_Stumps & with, float scale)
{
    /* Check they are compatible. */
    if (with.label_count() != label_count())
        throw Exception("Attempt to combine two boosted stumps with different "
                        "label counts.");
    if (with.feature_space().get() != feature_space().get())
        throw Exception("Attempt to combine two boosted stumps with different "
                        "feature spaces.");

    for (const_iterator it = with.begin();  it != with.end();  ++it)
        insert(*it, scale);
}

bool
Boosted_Stumps::
merge_into(const Classifier_Impl & other, float weight)
{
    /* If the other is a stump, we merge it. */
    const Stump * as_stump = dynamic_cast<const Stump *>(&other);
    if (as_stump) {
        insert(*as_stump, weight);
        return true;
    }
    const Boosted_Stumps * as_stumps
        = dynamic_cast<const Boosted_Stumps *>(&other);
    if (as_stumps) {
        combine(*as_stumps, weight);
        return true;
    }

    return false;
}

Classifier_Impl *
Boosted_Stumps::
merge(const Classifier_Impl & other, float weight) const
{
    /* If the other is a boosted stumps or a stump, we can merge it. */

    const Stump * as_stump = dynamic_cast<const Stump *>(&other);
    if (as_stump) {
        unique_ptr<Boosted_Stumps> me_copy(make_copy());
        me_copy->insert(*as_stump, weight);
        return me_copy.release();
    }

    const Boosted_Stumps * as_stumps
        = dynamic_cast<const Boosted_Stumps *>(&other);
    if (as_stumps) {
        unique_ptr<Boosted_Stumps> me_copy(make_copy());
        me_copy->combine(*as_stumps, weight);
        return me_copy.release();
    }

    return 0;
}

/*****************************************************************************/
/* REGISTRATION                                                              */
/*****************************************************************************/

namespace {

Register_Factory<Classifier_Impl, Boosted_Stumps>
    STUMP_REGISTER("BOOSTED_STUMPS");

} // file scope
} // namespace ML

ENUM_INFO_NAMESPACE

const Enum_Opt<ML::Boosted_Stumps::Output>
Enum_Info<ML::Boosted_Stumps::Output>::OPT[3] = {
    { "raw",         ML::Boosted_Stumps::RAW        },
    { "logit",       ML::Boosted_Stumps::LOGIT      },
    { "logit_norm",  ML::Boosted_Stumps::LOGIT_NORM } };

const char * Enum_Info<ML::Boosted_Stumps::Output>::NAME
    = "Boosted_Stumps::Output";

END_ENUM_INFO_NAMESPACE

max_stars_repo_name: leobispo/jml

max_issues_repo_name: leobispo/jml

max_forks_repo_name: leobispo/jml


text:
//
// ip/basic_endpoint.hpp
// ~~~~~~~~~~~~~~~~~~~~~
//
// Copyright (c) 2003-2010 Christopher M. Kohlhoff (chris at kohlhoff dot com)
//
// Distributed under the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
//

#ifndef BOOST_ASIO_IP_BASIC_ENDPOINT_HPP
#define BOOST_ASIO_IP_BASIC_ENDPOINT_HPP

#if defined(_MSC_VER) && (_MSC_VER >= 1200)
# pragma once
#endif // defined(_MSC_VER) && (_MSC_VER >= 1200)

#include <boost/asio/detail/config.hpp>
#include <boost/asio/ip/address.hpp>
#include <boost/asio/ip/detail/endpoint.hpp>

#if !defined(BOOST_NO_IOSTREAM)
# include <iosfwd>
#endif // !defined(BOOST_NO_IOSTREAM)

#include <boost/asio/detail/push_options.hpp>

namespace boost {
namespace asio {
namespace ip {

/// Describes an endpoint for a version-independent IP socket.
/**
 * The boost::asio::ip::basic_endpoint class template describes an endpoint that
 * may be associated with a particular socket.
 *
 * @par Thread Safety
 * @e Distinct @e objects: Safe.@n
 * @e Shared @e objects: Unsafe.
 *
 * @par Concepts:
 * Endpoint.
 */
template <typename InternetProtocol>
class basic_endpoint
{
public:
  /// The protocol type associated with the endpoint.
  typedef InternetProtocol protocol_type;

  /// The type of the endpoint structure. This type is dependent on the
  /// underlying implementation of the socket layer.
#if defined(GENERATING_DOCUMENTATION)
  typedef implementation_defined data_type;
#else
  typedef boost::asio::detail::socket_addr_type data_type;
#endif

  /// Default constructor.
  basic_endpoint()
    : impl_()
  {
  }

  /// Construct an endpoint using a port number, specified in the host's byte
  /// order. The IP address will be the any address (i.e. INADDR_ANY or
  /// in6addr_any). This constructor would typically be used for accepting new
  /// connections.
  /**
   * @par Examples
   * To initialise an IPv4 TCP endpoint for port 1234, use:
   * @code
   * boost::asio::ip::tcp::endpoint ep(boost::asio::ip::tcp::v4(), 1234);
   * @endcode
   *
   * To specify an IPv6 UDP endpoint for port 9876, use:
   * @code
   * boost::asio::ip::udp::endpoint ep(boost::asio::ip::udp::v6(), 9876);
   * @endcode
   */
  basic_endpoint(const InternetProtocol& protocol, unsigned short port_num)
    : impl_(protocol.family(), port_num)
  {
  }

  /// Construct an endpoint using a port number and an IP address. This
  /// constructor may be used for accepting connections on a specific interface
  /// or for making a connection to a remote endpoint.
  basic_endpoint(const boost::asio::ip::address& addr, unsigned short port_num)
    : impl_(addr, port_num)
  {
  }

  /// Copy constructor.
  basic_endpoint(const basic_endpoint& other)
    : impl_(other.impl_)
  {
  }

  /// Assign from another endpoint.
  basic_endpoint& operator=(const basic_endpoint& other)
  {
    impl_ = other.impl_;
    return *this;
  }

  /// The protocol associated with the endpoint.
  protocol_type protocol() const
  {
    if (impl_.is_v4())
      return InternetProtocol::v4();
    return InternetProtocol::v6();
  }

  /// Get the underlying endpoint in the native type.
  data_type* data()
  {
    return impl_.data();
  }

  /// Get the underlying endpoint in the native type.
  const data_type* data() const
  {
    return impl_.data();
  }

  /// Get the underlying size of the endpoint in the native type.
  std::size_t size() const
  {
    return impl_.size();
  }

  /// Set the underlying size of the endpoint in the native type.
  void resize(std::size_t size)
  {
    impl_.resize(size);
  }

  /// Get the capacity of the endpoint in the native type.
  std::size_t capacity() const
  {
    return impl_.capacity();
  }

  /// Get the port associated with the endpoint. The port number is always in
  /// the host's byte order.
  unsigned short port() const
  {
    return impl_.port();
  }

  /// Set the port associated with the endpoint. The port number is always in
  /// the host's byte order.
  void port(unsigned short port_num)
  {
    impl_.port(port_num);
  }

  /// Get the IP address associated with the endpoint.
  boost::asio::ip::address address() const
  {
    return impl_.address();
  }

  /// Set the IP address associated with the endpoint.
  void address(const boost::asio::ip::address& addr)
  {
    impl_.address(addr);
  }

  /// Compare two endpoints for equality.
  friend bool operator==(const basic_endpoint<InternetProtocol>& e1,
      const basic_endpoint<InternetProtocol>& e2)
  {
    return e1.impl_ == e2.impl_;
  }

  /// Compare two endpoints for inequality.
  friend bool operator!=(const basic_endpoint<InternetProtocol>& e1,
      const basic_endpoint<InternetProtocol>& e2)
  {
    return !(e1 == e2);
  }

  /// Compare endpoints for ordering.
  friend bool operator<(const basic_endpoint<InternetProtocol>& e1,
      const basic_endpoint<InternetProtocol>& e2)
  {
    return e1.impl_ < e2.impl_;
  }

  /// Compare endpoints for ordering.
  friend bool operator>(const basic_endpoint<InternetProtocol>& e1,
      const basic_endpoint<InternetProtocol>& e2)
  {
    return e2.impl_ < e1.impl_;
  }

  /// Compare endpoints for ordering.
  friend bool operator<=(const basic_endpoint<InternetProtocol>& e1,
      const basic_endpoint<InternetProtocol>& e2)
  {
    return !(e2 < e1);
  }

  /// Compare endpoints for ordering.
  friend bool operator>=(const basic_endpoint<InternetProtocol>& e1,
      const basic_endpoint<InternetProtocol>& e2)
  {
    return !(e1 < e2);
  }

private:
  // The underlying IP endpoint.
  boost::asio::ip::detail::endpoint impl_;
};

#if !defined(BOOST_NO_IOSTREAM)

/// Output an endpoint as a string.
/**
 * Used to output a human-readable string for a specified endpoint.
 *
 * @param os The output stream to which the string will be written.
 *
 * @param endpoint The endpoint to be written.
 *
 * @return The output stream.
 *
 * @relates boost::asio::ip::basic_endpoint
 */
template <typename Elem, typename Traits, typename InternetProtocol>
std::basic_ostream<Elem, Traits>& operator<<(
    std::basic_ostream<Elem, Traits>& os,
    const basic_endpoint<InternetProtocol>& endpoint);

#endif // !defined(BOOST_NO_IOSTREAM)

} // namespace ip
} // namespace asio
} // namespace boost

#include <boost/asio/detail/pop_options.hpp>

#include <boost/asio/ip/impl/basic_endpoint.hpp>

#endif // BOOST_ASIO_IP_BASIC_ENDPOINT_HPP

ext: hpp

max_stars_repo_name: RaptDept/slimtune

max_issues_repo_name: RaptDept/slimtune

max_forks_repo_name: RaptDept/slimtune


text: #include <boost/type_traits/has_less_equal.hpp>

max_stars_repo_name: miathedev/BoostForArduino

max_issues_repo_name: miathedev/BoostForArduino

max_forks_repo_name: miathedev/BoostForArduino


text:
#include <cctbx/boost_python/flex_fwd.h>

#include <boost/python/class.hpp>
#include <boost/python/args.hpp>
#include <boost/python/return_value_policy.hpp>
#include <boost/python/return_by_value.hpp>
#include <boost/python/dict.hpp>
#include <iotbx/pdb/input.h>
#include <iotbx/pdb/write_utils_bpl.h>
#if PY_MAJOR_VERSION >= 3
#define IS_PY3K
#endif

namespace iotbx { namespace pdb {
namespace {

  struct columns_73_76_evaluator_wrappers
  {
    typedef columns_73_76_evaluator w_t;

    static void
    wrap()
    {
      using namespace boost::python;
      class_<w_t>("columns_73_76_evaluator", no_init)
        .def(init<
          af::const_ref<std::string> const&,
          optional<
            unsigned,
            unsigned> >((
              arg("lines"),
              arg("is_frequent_threshold_atom_records")=1000,
              arg("is_frequent_threshold_other_records")=100)))
        .def_readonly("finding", &w_t::finding)
        .def_readonly("is_old_style", &w_t::is_old_style)
      ;
    }
  };

  struct input_wrappers
  {
    typedef input w_t;

    static
    boost::python::dict
    record_type_counts_as_dict(w_t const& self)
    {
      using namespace boost::python;
      dict result;
      typedef w_t::record_type_counts_t rtct;
      rtct const& rtc = self.record_type_counts();
      for(rtct::const_iterator i=rtc.begin(); i!= rtc.end(); i++) {
        result[i->first.elems] = i->second;
      }
      return result;
    }

#ifdef IS_PY3K
    static PyObject *
#else
    static void
#endif
    as_pdb_string_cstringio(
      w_t const& self,
      boost::python::object cstringio,
      bool append_end=false,
      bool atom_hetatm=true,
      bool sigatm=true,
      bool anisou=true,
      bool siguij=true)
    {
#ifdef IS_PY3K
      std::stringstream ss;
      write_utils::sstream_write write(&ss);
#else
      write_utils::cstringio_write write(cstringio.ptr());
#endif
      input_as_pdb_string(
        self,
        write,
        append_end,
        atom_hetatm,
        sigatm,
        anisou,
        siguij);
#ifdef IS_PY3K
    return PyUnicode_FromStringAndSize( ss.str().c_str(), ss.str().size());
#endif
    }

    static void
    wrap()
    {
      using namespace boost::python;
      typedef return_value_policy<return_by_value> rbv;
      class_<w_t, boost::shared_ptr<input> >("input", no_init)
        .def(init<
          std::string const&>((
            arg("file_name"))))
        .def(init<
          const char*,
          af::const_ref<std::string> const&>((
            arg("source_info"),
            arg("lines"))))
        //
        .enable_pickling()
        .def("source_info", &w_t::source_info, rbv())
        .def("record_type_counts", record_type_counts_as_dict)
        .def("unknown_section", &w_t::unknown_section, rbv())
        .def("title_section", &w_t::title_section, rbv())
        .def("remark_section", &w_t::remark_section, rbv())
        .def("primary_structure_section",
          &w_t::primary_structure_section, rbv())
        .def("heterogen_section", &w_t::heterogen_section, rbv())
        .def("secondary_structure_section",
          &w_t::secondary_structure_section, rbv())
        .def("connectivity_annotation_section",
          &w_t::connectivity_annotation_section, rbv())
        .def("miscellaneous_features_section",
          &w_t::miscellaneous_features_section, rbv())
        .def("crystallographic_section", &w_t::crystallographic_section, rbv())
        .def("atoms", &w_t::atoms, rbv())
        .def("model_ids", &w_t::model_ids, rbv())
        .def("model_indices", &w_t::model_indices, rbv())
        .def("ter_indices", &w_t::ter_indices, rbv())
        .def("chain_indices", &w_t::chain_indices, rbv())
        .def("break_indices", &w_t::break_indices, rbv())
        .def("connectivity_section", &w_t::connectivity_section, rbv())
        .def("bookkeeping_section", &w_t::bookkeeping_section, rbv())
        .def("model_atom_counts", &w_t::model_atom_counts)
        .def("atoms_with_labels", &w_t::atoms_with_labels)
        .def("_as_pdb_string_cstringio", as_pdb_string_cstringio, (
          arg("self"),
          arg("cstringio"),
          arg("append_end"),
          arg("atom_hetatm"),
          arg("sigatm"),
          arg("anisou"),
          arg("siguij")))
        .def("_write_pdb_file", &w_t::write_pdb_file, (
          arg("file_name"),
          arg("open_append"),
          arg("append_end"),
          arg("atom_hetatm"),
          arg("sigatm"),
          arg("anisou"),
          arg("siguij")))
        .def("construct_hierarchy", &w_t::construct_hierarchy, (
          arg("residue_group_post_processing")=true,
          arg("set_atom_i_seq")=true,
          arg("sort_atoms")=true))
      ;
    }
  };

  void
  wrap_input_impl()
  {
#ifndef IS_PY3K
    scitbx::boost_python::cstringio_import();
#endif
    columns_73_76_evaluator_wrappers::wrap();
    input_wrappers::wrap();
  }

} // namespace <anonymous>

namespace boost_python {

  void
  wrap_input() { wrap_input_impl(); }

}}} // namespace iotbx::pdb::boost_python

ext: cpp


text:
#include <boost/static_assert.hpp>
#include <iostream>

template <unsigned long N>
struct binary
{
  BOOST_STATIC_ASSERT((N % 10 < 2));

  static unsigned const value = binary<N / 10>::value * 2 + N % 10;
};

template <>
struct binary<0>
{
  static unsigned const value = 0;
};

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

#define PRINT_AS_BINARY_AND_VALUE(theValue)                                    \
  {                                                                            \
    std::cout << theValue << " is the binary representation of "               \
              << binary<theValue>::value << std::endl;                         \
  }

  PRINT_AS_BINARY_AND_VALUE(111);
  PRINT_AS_BINARY_AND_VALUE(1011);
  PRINT_AS_BINARY_AND_VALUE(1101);
  PRINT_AS_BINARY_AND_VALUE(101010);

#undef PRINT_AS_BINARY_AND_VALUE
}

max_stars_repo_name: jbcoe/CppSandbox

max_issues_repo_name: jbcoe/CppSandbox

max_forks_repo_name: jbcoe/CppSandbox


text:
//---------------------------------------------------------------------------//
//!
//! \file   Data_DecayNuclide_def.hpp
//! \author Alex Robinson
//! \brief  The decay nuclide class template definitions
//!
//---------------------------------------------------------------------------//

#ifndef DATA_DECAY_NUCLIDE_DEF_HPP
#define DATA_DECAY_NUCLIDE_DEF_HPP

// Boost Includes
#include <boost/serialization/vector.hpp>
#include <boost/serialization/nvp.hpp>

namespace Data{

// Serialize the data
template<typename Archive>
void DecayNuclide::serialize( Archive &ar, const unsigned int version )
{
  ar & boost::serialization::make_nvp( "z", d_atomic_number );
  ar & boost::serialization::make_nvp( "a", d_atomic_mass_number );
  ar & boost::serialization::make_nvp( "s", d_isomer_number );
  ar & boost::serialization::make_nvp( "half_life", d_half_life );
  ar & boost::serialization::make_nvp( "half_life_err", d_half_life_error );
  ar & boost::serialization::make_nvp( "decay_const", d_decay_constant );
  ar & boost::serialization::make_nvp( "decay_const_err", d_decay_constant_error );
  ar & boost::serialization::make_nvp( "decay_data", d_decay_branches );
}

// Serialize the struct data
template<typename Archive>
void DecayNuclide::DecayBranch::serialize( Archive &ar,
					   const unsigned int version )
{
  ar & boost::serialization::make_nvp( "branching_ratio", branching_ratio );
  ar & boost::serialization::make_nvp( "branching_ratio_err",
				     branching_ratio_error );
  ar & boost::serialization::make_nvp( "daughter", daughter);
  ar & boost::serialization::make_nvp( "decay_type",
				     decay_type );
}

} // end Data namespace

#endif // end DATA_DECAY_NUCLIDE_DEF_HPP

//---------------------------------------------------------------------------//
// end Data_DecayNuclide_def.hpp
//---------------------------------------------------------------------------//


text:
#include <ros/ros.h>
#include <string.h>
#include <tf/transform_listener.h>
#include <pcl_ros/transforms.h>
#include <laser_geometry/laser_geometry.h>
#include <pcl/conversions.h>
#include <pcl/point_cloud.h>
#include <pcl/point_types.h>
#include <pcl/io/pcd_io.h>
#include <sensor_msgs/PointCloud.h>
#include <sensor_msgs/PointCloud2.h>
#include <sensor_msgs/point_cloud_conversion.h>
#include "sensor_msgs/LaserScan.h"
#include "pcl_ros/point_cloud.h"
#include <Eigen/Dense>
#include <dynamic_reconfigure/server.h>
#include <ira_laser_tools/LaserscanMultiMergerConfig.h>
#include <sstream>

class LaserscanMerger
{
public:
  LaserscanMerger();
  void scanCallback(const sensor_msgs::LaserScan& scan, int input_number);
  void pointcloudToLaserscan(const pcl::PointCloud<pcl::PointXYZI>& merge, sensor_msgs::LaserScan& scan,
                             pcl::PointCloud<pcl::PointXYZI>& output_cloud);
  void reconfigureCallback(ira_laser_tools::LaserscanMultiMergerConfig& config, uint32_t level);

private:
  ros::NodeHandle node_;
  ros::NodeHandle private_node_;
  laser_geometry::LaserProjection projector_;
  tf::TransformListener tf_listener_;

  ros::Publisher pointcloud_publisher_;
  ros::Publisher laserscan_publisher_;
  std::vector<ros::Subscriber> scan_subscribers_;

  std::vector<bool> clouds_modified_;
  std::vector<sensor_msgs::LaserScan> input_scans_;
  std::vector<pcl::PointCloud<pcl::PointXYZI>> output_clouds_;

  std::vector<std::string> input_topics_;

  void laserscanTopicParser();
  void subscribeToTopics();

  // scan merging configuration
  double angle_min_;
  double angle_max_;
  double angle_increment_;
  double time_increment_;
  double scan_time_;
  double range_min_;
  double range_max_;

  std::string destination_frame_;
  std::string fixed_frame_;
  std::string cloud_destination_topic_;
  std::string scan_destination_topic_;
  bool check_topic_type_;
  std::string laserscan_topics_;
};

LaserscanMerger::LaserscanMerger() : node_(""), private_node_("~")
{
  private_node_.getParam("destination_frame", destination_frame_);
  private_node_.getParam("fixed_frame", fixed_frame_);
  private_node_.getParam("cloud_destination_topic", cloud_destination_topic_);
  private_node_.getParam("scan_destination_topic", scan_destination_topic_);

  private_node_.getParam("laserscan_topics", laserscan_topics_);
  check_topic_type_ = false;
  private_node_.getParam("check_topic_type", check_topic_type_);

  laserscanTopicParser();
  subscribeToTopics();

  pointcloud_publisher_ = private_node_.advertise<sensor_msgs::PointCloud2>(cloud_destination_topic_, 1, false);
  laserscan_publisher_ = private_node_.advertise<sensor_msgs::LaserScan>(scan_destination_topic_, 1, false);
}

void LaserscanMerger::reconfigureCallback(ira_laser_tools::LaserscanMultiMergerConfig& config, uint32_t level)
{
  this->angle_min_ = config.angle_min;
  this->angle_max_ = config.angle_max;
  this->angle_increment_ = config.angle_increment;
  this->time_increment_ = config.time_increment;
  this->scan_time_ = config.scan_time;
  this->range_min_ = config.range_min;
  this->range_max_ = config.range_max;
}

void LaserscanMerger::laserscanTopicParser()
{
  // LaserScan topics to subscribe
  ros::master::V_TopicInfo topics;
  ros::master::getTopics(topics);

  std::istringstream iss(laserscan_topics_);
  std::vector<std::string> tokens;
  std::copy(std::istream_iterator<std::string>(iss), std::istream_iterator<std::string>(),
            std::back_inserter<std::vector<std::string>>(tokens));

  std::vector<std::string> tmp_input_topics_;

  if (check_topic_type_ == false)
  {
    tmp_input_topics_ = tokens;
  }
  else
  {
    for (int i = 0; i < tokens.size(); ++i)
    {
      for (int j = 0; j < topics.size(); ++j)
      {
        if ((topics[j].name.compare(node_.resolveName(tokens[i])) == 0) &&
            (topics[j].datatype.compare("sensor_msgs/LaserScan") == 0))
        {
          tmp_input_topics_.push_back(topics[j].name);
        }
      }
    }
  }

  sort(tmp_input_topics_.begin(), tmp_input_topics_.end());
  std::vector<std::string>::iterator last = std::unique(tmp_input_topics_.begin(), tmp_input_topics_.end());
  tmp_input_topics_.erase(last, tmp_input_topics_.end());
  input_topics_ = tmp_input_topics_;
}

void LaserscanMerger::subscribeToTopics()
{
  // Unsubscribe from previous topics
  for (int i = 0; i < scan_subscribers_.size(); ++i)
    scan_subscribers_[i].shutdown();

  if (input_topics_.size() > 0)
  {
    scan_subscribers_.resize(input_topics_.size());
    clouds_modified_.resize(input_topics_.size());
    input_scans_.resize(input_topics_.size());
    output_clouds_.resize(input_topics_.size());

    std::ostringstream ss;
    ss << "Subscribing to " << scan_subscribers_.size() << " topics:";
    for (int i = 0; i < input_topics_.size(); ++i)
    {
      // this weird node_.subscribe<MsgType, const MsgType&> is needed to bind to a callback
      // which receives a const Type&
      // otherwise, we are forced to subscribe to callback which receives a shared_ptr
      scan_subscribers_[i] = node_.subscribe<sensor_msgs::LaserScan, const sensor_msgs::LaserScan&>(
          input_topics_[i], 1, boost::bind(&LaserscanMerger::scanCallback, this, _1, i));
      clouds_modified_[i] = false;
      ss << " " << input_topics_[i];
    }
    ROS_INFO_STREAM(ss.str());
  }
  else
    ROS_INFO("Not subscribed to any topic.");
}

void LaserscanMerger::scanCallback(const sensor_msgs::LaserScan& scan, int input_number)
{
  // Verify that TF knows how to transform from the received scan to the fixed scan frame
  // as we are using a high precission projector, we need the tf at the time of the last
  // scan
  try
  {
    ros::Time end_stamp = (scan.header.stamp + ros::Duration().fromSec((scan.ranges.size() - 1) * scan.time_increment));
    if (!tf_listener_.waitForTransform(fixed_frame_, scan.header.frame_id, end_stamp, ros::Duration(10)))
      return;
  }
  catch (const tf::TransformException& ex)
  {
    ROS_ERROR("%s", ex.what());
    return;
  }

  input_scans_[input_number] = scan;
  sensor_msgs::PointCloud2 scan_in_fixed_frame;
  try
  {
    projector_.transformLaserScanToPointCloud(fixed_frame_, scan, scan_in_fixed_frame, tf_listener_);
    // need this weird if. otherwise, in case of no intensities on input, it will keep printing at each iteration
    // a warning message about intensities missing field
    if (scan.intensities.size() != 0)
    {
      pcl::fromROSMsg(scan_in_fixed_frame, output_clouds_[input_number]);
    }
    else
    {
      pcl::PointCloud<pcl::PointXYZ> cloud_without_intensities;
      pcl::fromROSMsg(scan_in_fixed_frame, cloud_without_intensities);
      pcl::copyPointCloud(cloud_without_intensities, output_clouds_[input_number]);
    }
  }
  catch (const tf::TransformException& ex)
  {
    ROS_ERROR("%s", ex.what());
    return;
  }

  clouds_modified_[input_number] = true;

  // Count how many scans we have
  int totalClouds = 0;
  for (int i = 0; i < clouds_modified_.size(); ++i)
    if (clouds_modified_[i])
      ++totalClouds;

  // Go ahead only if all subscribed scans have arrived
  if (totalClouds == clouds_modified_.size())
  {
    ros::Time current_stamp;
    pcl_conversions::fromPCL(std::min_element(output_clouds_.begin(), output_clouds_.end(),
                                              [](pcl::PointCloud<pcl::PointXYZI> n, pcl::PointCloud<pcl::PointXYZI> m) {
                                                return n.header.stamp < m.header.stamp;
                                              })
                                 ->header.stamp,
                             current_stamp);

    int first = 0;
    for (first = 0; first < clouds_modified_.size(); first++)
      if (output_clouds_[first].points.size() != 0)
        break;

    if (first == clouds_modified_.size())
    {
      ROS_INFO_THROTTLE(5, "Input is empty (either laserscan was empty or couldn't be transformed into fixed frame)");
      return;
    }

    for (int i = first; i < clouds_modified_.size(); ++i)
    {
      clouds_modified_[i] = false;
    }

    pcl::PointCloud<pcl::PointXYZI> merge;
    merge.header.frame_id = destination_frame_;
    merge.header.stamp = pcl_conversions::toPCL(current_stamp);
    for (auto& cloud : output_clouds_)
    {
      pcl::PointCloud<pcl::PointXYZI> transformed;
      pcl_ros::transformPointCloud(destination_frame_, current_stamp, cloud, fixed_frame_, transformed, tf_listener_);
      merge += transformed;
    }

    sensor_msgs::LaserScan output_scan;
    output_scan.header.frame_id = destination_frame_;
    output_scan.header.stamp = current_stamp;
    pcl::PointCloud<pcl::PointXYZI> output_cloud;
    output_cloud.header = merge.header;
    pointcloudToLaserscan(merge, output_scan, output_cloud);

    pointcloud_publisher_.publish(output_cloud);
    laserscan_publisher_.publish(output_scan);
  }
}

void LaserscanMerger::pointcloudToLaserscan(const pcl::PointCloud<pcl::PointXYZI>& merge,
                                            sensor_msgs::LaserScan& output_scan,
                                            pcl::PointCloud<pcl::PointXYZI>& output_cloud)
{
  output_scan.angle_min = this->angle_min_;
  output_scan.angle_max = this->angle_max_;
  output_scan.angle_increment = this->angle_increment_;
  output_scan.time_increment = this->time_increment_;
  output_scan.scan_time = this->scan_time_;
  output_scan.range_min = this->range_min_;
  output_scan.range_max = this->range_max_;

  uint32_t ranges_size = std::ceil((output_scan.angle_max - output_scan.angle_min) / output_scan.angle_increment);
  output_scan.ranges.assign(ranges_size, output_scan.range_max + 1.0);
  output_scan.intensities.assign(ranges_size, 0);

  output_cloud.points.clear();
  for (auto& point : merge.points)
  {
    const float& x = point.x;
    const float& y = point.y;
    const float& z = point.z;
    const float& intensity = point.intensity;
    if (std::isnan(x) || std::isnan(y) || std::isnan(z))
    {
      ROS_DEBUG("rejected for nan in point(%f, %f, %f)\n", x, y, z);
      continue;
    }

    double range_sq = y * y + x * x;
    double range_min_sq_ = output_scan.range_min * output_scan.range_min;
    if (range_sq < range_min_sq_)
    {
      ROS_DEBUG("rejected for range %f below minimum value %f. Point: (%f, %f, %f)", range_sq, range_min_sq_, x, y, z);
      continue;
    }

    double angle = atan2(y, x);
    if (angle < output_scan.angle_min || angle > output_scan.angle_max)
    {
      ROS_DEBUG("rejected for angle %f not in range (%f, %f)\n", angle, output_scan.angle_min, output_scan.angle_max);
      continue;
    }
    int index = (angle - output_scan.angle_min) / output_scan.angle_increment;

    if (output_scan.ranges[index] * output_scan.ranges[index] > range_sq)
    {
      output_scan.ranges[index] = sqrt(range_sq);
      output_scan.intensities[index] = intensity;
      output_cloud.points.push_back(point);
    }
  }
}

int main(int argc, char** argv)
{
  ros::init(argc, argv, "laser_multi_merger");

  LaserscanMerger laser_merger;

  dynamic_reconfigure::Server<ira_laser_tools::LaserscanMultiMergerConfig> reconfigure_server;
  dynamic_reconfigure::Server<ira_laser_tools::LaserscanMultiMergerConfig>::CallbackType reconfigure_callback;

  reconfigure_callback = boost::bind(&LaserscanMerger::reconfigureCallback, &laser_merger, _1, _2);
  reconfigure_server.setCallback(reconfigure_callback);

  ros::spin();

  return 0;
}


text:
// Copyright (C) 2019-2020 Zilliz. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance
// with the License. You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software distributed under the License
// is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
// or implied. See the License for the specific language governing permissions and limitations under the License

#include <gtest/gtest.h>
#include <memory>
#include <boost/format.hpp>
#include <regex>

#include "pb/plan.pb.h"
#include "query/Expr.h"
#include "query/generated/PlanNodeVisitor.h"
#include "query/generated/ExecExprVisitor.h"
#include "segcore/SegmentGrowingImpl.h"
#include "test_utils/DataGen.h"
#include "query/PlanProto.h"
#include "query/Utils.h"
#include "query/SearchBruteForce.h"

using namespace milvus;

namespace {
template <typename T>
auto
GenGenericValue(T value) {
    auto generic = new proto::plan::GenericValue();
    if constexpr (std::is_same_v<T, bool>) {
        generic->set_bool_val(static_cast<bool>(value));
    } else if constexpr (std::is_integral_v<T>) {
        generic->set_int64_val(static_cast<int64_t>(value));
    } else if constexpr (std::is_floating_point_v<T>) {
        generic->set_float_val(static_cast<float>(value));
    } else if constexpr (std::is_same_v<T, std::string>) {
        generic->set_string_val(static_cast<std::string>(value));
    } else {
        static_assert(always_false<T>);
    }
    return generic;
}

auto
GenColumnInfo(int64_t field_id, proto::schema::DataType field_type, bool auto_id, bool is_pk) {
    auto column_info = new proto::plan::ColumnInfo();
    column_info->set_field_id(field_id);
    column_info->set_data_type(field_type);
    column_info->set_is_autoid(auto_id);
    column_info->set_is_primary_key(is_pk);
    return column_info;
}

auto
GenQueryInfo(int64_t topk, std::string metric_type, std::string search_params, int64_t round_decimal = -1) {
    auto query_info = new proto::plan::QueryInfo();
    query_info->set_topk(topk);
    query_info->set_metric_type(metric_type);
    query_info->set_search_params(search_params);
    query_info->set_round_decimal(round_decimal);
    return query_info;
}

auto
GenAnns(proto::plan::Expr* predicate, bool is_binary, int64_t field_id, std::string placeholder_tag = "$0") {
    auto query_info = GenQueryInfo(10, "L2", "{\"nprobe\": 10}", -1);
    auto anns = new proto::plan::VectorANNS();
    anns->set_is_binary(is_binary);
    anns->set_field_id(field_id);
    anns->set_allocated_predicates(predicate);
    anns->set_allocated_query_info(query_info);
    anns->set_placeholder_tag(placeholder_tag);
    return anns;
}

template <typename T>
auto
GenTermExpr(const std::vector<T>& values) {
    auto term_expr = new proto::plan::TermExpr();
    for (int i = 0; i < values.size(); i++) {
        auto add_value = term_expr->add_values();
        if constexpr (std::is_same_v<T, bool>) {
            add_value->set_bool_val(static_cast<T>(values[i]));
        } else if constexpr (std::is_integral_v<T>) {
            add_value->set_int64_val(static_cast<int64_t>(values[i]));
        } else if constexpr (std::is_floating_point_v<T>) {
            add_value->set_float_val(static_cast<double>(values[i]));
        } else if constexpr (std::is_same_v<T, std::string>) {
            add_value->set_string_val(static_cast<T>(values[i]));
        } else {
            static_assert(always_false<T>);
        }
    }
    return term_expr;
}

auto
GenCompareExpr(proto::plan::OpType op) {
    auto compare_expr = new proto::plan::CompareExpr();
    compare_expr->set_op(op);
    return compare_expr;
}

template <typename T>
auto
GenUnaryRangeExpr(proto::plan::OpType op, T value) {
    auto unary_range_expr = new proto::plan::UnaryRangeExpr();
    unary_range_expr->set_op(op);
    auto generic = GenGenericValue(value);
    unary_range_expr->set_allocated_value(generic);
    return unary_range_expr;
}

template <typename T>
auto
GenBinaryRangeExpr(bool lb_inclusive, bool ub_inclusive, T lb, T ub) {
    auto binary_range_expr = new proto::plan::BinaryRangeExpr();
    binary_range_expr->set_lower_inclusive(lb_inclusive);
    binary_range_expr->set_upper_inclusive(ub_inclusive);
    auto lb_generic = GenGenericValue(lb);
    auto ub_generic = GenGenericValue(ub);
    binary_range_expr->set_allocated_lower_value(lb_generic);
    binary_range_expr->set_allocated_upper_value(ub_generic);
    return binary_range_expr;
}

auto
GenNotExpr() {
    auto not_expr = new proto::plan::UnaryExpr();
    not_expr->set_op(proto::plan::UnaryExpr_UnaryOp_Not);
    return not_expr;
}

auto
GenExpr() {
    return std::make_unique<proto::plan::Expr>();
}

auto
GenPlanNode() {
    return std::make_unique<proto::plan::PlanNode>();
}

void
SetTargetEntry(std::unique_ptr<proto::plan::PlanNode>& plan_node, const std::vector<int64_t>& output_fields) {
    for (auto id : output_fields) {
        plan_node->add_output_field_ids(id);
    }
}

auto
GenTermPlan(const FieldMeta& fvec_meta, const FieldMeta& str_meta, const std::vector<std::string>& strs)
    -> std::unique_ptr<proto::plan::PlanNode> {
    auto column_info = GenColumnInfo(str_meta.get_id().get(), proto::schema::DataType::VarChar, false, false);
    auto term_expr = GenTermExpr<std::string>(strs);
    term_expr->set_allocated_column_info(column_info);

    auto expr = GenExpr().release();
    expr->set_allocated_term_expr(term_expr);

    auto anns = GenAnns(expr, fvec_meta.get_data_type() == DataType::VECTOR_BINARY, fvec_meta.get_id().get(), "$0");

    auto plan_node = GenPlanNode();
    plan_node->set_allocated_vector_anns(anns);
    return std::move(plan_node);
}

auto
GenAlwaysFalseExpr(const FieldMeta& fvec_meta, const FieldMeta& str_meta) {
    auto column_info = GenColumnInfo(str_meta.get_id().get(), proto::schema::DataType::VarChar, false, false);
    auto term_expr = GenTermExpr<std::string>({});  // in empty set, always false.
    term_expr->set_allocated_column_info(column_info);

    auto expr = GenExpr().release();
    expr->set_allocated_term_expr(term_expr);
    return expr;
}

auto
GenAlwaysTrueExpr(const FieldMeta& fvec_meta, const FieldMeta& str_meta) {
    auto always_false_expr = GenAlwaysFalseExpr(fvec_meta, str_meta);
    auto not_expr = GenNotExpr();
    not_expr->set_allocated_child(always_false_expr);
    auto expr = GenExpr().release();
    expr->set_allocated_unary_expr(not_expr);
    return expr;
}

auto
GenAlwaysFalsePlan(const FieldMeta& fvec_meta, const FieldMeta& str_meta) {
    auto always_false_expr = GenAlwaysFalseExpr(fvec_meta, str_meta);
    auto anns = GenAnns(always_false_expr, fvec_meta.get_data_type() == DataType::VECTOR_BINARY,
                        fvec_meta.get_id().get(), "$0");

    auto plan_node = GenPlanNode();
    plan_node->set_allocated_vector_anns(anns);
    return std::move(plan_node);
}

auto
GenAlwaysTruePlan(const FieldMeta& fvec_meta, const FieldMeta& str_meta) {
    auto always_true_expr = GenAlwaysTrueExpr(fvec_meta, str_meta);
    auto anns =
        GenAnns(always_true_expr, fvec_meta.get_data_type() == DataType::VECTOR_BINARY, fvec_meta.get_id().get(), "$0");

    auto plan_node = GenPlanNode();
    plan_node->set_allocated_vector_anns(anns);
    return std::move(plan_node);
}

SchemaPtr
GenTestSchema() {
    auto schema = std::make_shared<Schema>();
    schema->AddDebugField("str", DataType::VARCHAR);
    schema->AddDebugField("another_str", DataType::VARCHAR);
    schema->AddDebugField("fvec", DataType::VECTOR_FLOAT, 16, MetricType::METRIC_L2);
    auto pk = schema->AddDebugField("int64", DataType::INT64);
    schema->set_primary_field_id(pk);
    return schema;
}

SchemaPtr
GenStrPKSchema() {
    auto schema = std::make_shared<Schema>();
    auto pk = schema->AddDebugField("str", DataType::VARCHAR);
    schema->AddDebugField("another_str", DataType::VARCHAR);
    schema->AddDebugField("fvec", DataType::VECTOR_FLOAT, 16, MetricType::METRIC_L2);
    schema->AddDebugField("int64", DataType::INT64);
    schema->set_primary_field_id(pk);
    return schema;
}
}  // namespace

TEST(StringExpr, Term) {
    using namespace milvus::query;
    using namespace milvus::segcore;

    auto schema = GenTestSchema();
    const auto& fvec_meta = schema->operator[](FieldName("fvec"));
    const auto& str_meta = schema->operator[](FieldName("str"));

    auto vec_2k_3k = []() -> std::vector<std::string> {
        std::vector<std::string> ret;
        for (int i = 2000; i < 3000; i++) {
            ret.push_back(std::to_string(i));
        }
        return ret;
    }();

    std::map<int, std::vector<std::string>> terms = {
        {0, {"2000", "3000"}}, {1, {"2000"}}, {2, {"3000"}}, {3, {}}, {4, {vec_2k_3k}},
    };

    auto seg = CreateGrowingSegment(schema);
    int N = 1000;
    std::vector<std::string> str_col;
    int num_iters = 100;
    for (int iter = 0; iter < num_iters; ++iter) {
        auto raw_data = DataGen(schema, N, iter);
        auto new_str_col = raw_data.get_col(str_meta.get_id());
        auto begin = new_str_col->scalars().string_data().data().begin();
        auto end = new_str_col->scalars().string_data().data().end();
        str_col.insert(str_col.end(), begin, end);
        seg->PreInsert(N);
        seg->Insert(iter * N, N, raw_data.row_ids_.data(), raw_data.timestamps_.data(), raw_data.raw_);
    }

    auto seg_promote = dynamic_cast<SegmentGrowingImpl*>(seg.get());
    ExecExprVisitor visitor(*seg_promote, seg_promote->get_row_count(), MAX_TIMESTAMP);
    for (const auto& [_, term] : terms) {
        auto plan_proto = GenTermPlan(fvec_meta, str_meta, term);
        auto plan = ProtoParser(*schema).CreatePlan(*plan_proto);
        auto final = visitor.call_child(*plan->plan_node_->predicate_.value());
        EXPECT_EQ(final.size(), N * num_iters);

        for (int i = 0; i < N * num_iters; ++i) {
            auto ans = final[i];

            auto val = str_col[i];
            auto ref = std::find(term.begin(), term.end(), val) != term.end();
            ASSERT_EQ(ans, ref) << "@" << i << "!!" << val;
        }
    }
}

TEST(StringExpr, Compare) {
    using namespace milvus::query;
    using namespace milvus::segcore;

    auto schema = GenTestSchema();
    const auto& fvec_meta = schema->operator[](FieldName("fvec"));
    const auto& str_meta = schema->operator[](FieldName("str"));
    const auto& another_str_meta = schema->operator[](FieldName("another_str"));

    auto gen_compare_plan = [&, fvec_meta, str_meta,
                             another_str_meta](proto::plan::OpType op) -> std::unique_ptr<proto::plan::PlanNode> {
        auto str_col_info = GenColumnInfo(str_meta.get_id().get(), proto::schema::DataType::VarChar, false, false);
        auto another_str_col_info =
            GenColumnInfo(another_str_meta.get_id().get(), proto::schema::DataType::VarChar, false, false);

        auto compare_expr = GenCompareExpr(op);
        compare_expr->set_allocated_left_column_info(str_col_info);
        compare_expr->set_allocated_right_column_info(another_str_col_info);

        auto expr = GenExpr().release();
        expr->set_allocated_compare_expr(compare_expr);

        auto anns = GenAnns(expr, fvec_meta.get_data_type() == DataType::VECTOR_BINARY, fvec_meta.get_id().get(), "$0");

        auto plan_node = std::make_unique<proto::plan::PlanNode>();
        plan_node->set_allocated_vector_anns(anns);
        return std::move(plan_node);
    };

    std::vector<std::tuple<proto::plan::OpType, std::function<bool(std::string, std::string)>>> testcases{
        {proto::plan::OpType::GreaterThan, [](std::string v1, std::string v2) { return v1 > v2; }},
        {proto::plan::OpType::GreaterEqual, [](std::string v1, std::string v2) { return v1 >= v2; }},
        {proto::plan::OpType::LessThan, [](std::string v1, std::string v2) { return v1 < v2; }},
        {proto::plan::OpType::LessEqual, [](std::string v1, std::string v2) { return v1 <= v2; }},
        {proto::plan::OpType::Equal, [](std::string v1, std::string v2) { return v1 == v2; }},
        {proto::plan::OpType::NotEqual, [](std::string v1, std::string v2) { return v1 != v2; }},
        {proto::plan::OpType::PrefixMatch, [](std::string v1, std::string v2) { return PrefixMatch(v1, v2); }},
    };

    auto seg = CreateGrowingSegment(schema);
    int N = 1000;
    std::vector<std::string> str_col;
    std::vector<std::string> another_str_col;
    int num_iters = 100;
    for (int iter = 0; iter < num_iters; ++iter) {
        auto raw_data = DataGen(schema, N, iter);

        auto reserve_col = [&, raw_data](const FieldMeta& field_meta, std::vector<std::string>& str_col) {
            auto new_str_col = raw_data.get_col(field_meta.get_id());
            auto begin = new_str_col->scalars().string_data().data().begin();
            auto end = new_str_col->scalars().string_data().data().end();
            str_col.insert(str_col.end(), begin, end);
        };

        reserve_col(str_meta, str_col);
        reserve_col(another_str_meta, another_str_col);

        {
            seg->PreInsert(N);
            seg->Insert(iter * N, N, raw_data.row_ids_.data(), raw_data.timestamps_.data(), raw_data.raw_);
        }
    }

    auto seg_promote = dynamic_cast<SegmentGrowingImpl*>(seg.get());
    ExecExprVisitor visitor(*seg_promote, seg_promote->get_row_count(), MAX_TIMESTAMP);
    for (const auto& [op, ref_func] : testcases) {
        auto plan_proto = gen_compare_plan(op);
        auto plan = ProtoParser(*schema).CreatePlan(*plan_proto);
        auto final = visitor.call_child(*plan->plan_node_->predicate_.value());
        EXPECT_EQ(final.size(), N * num_iters);

        for (int i = 0; i < N * num_iters; ++i) {
            auto ans = final[i];

            auto val = str_col[i];
            auto another_val = another_str_col[i];
            auto ref = ref_func(val, another_val);
            ASSERT_EQ(ans, ref) << "@" << op << "@" << i << "!!" << val;
        }
    }
}

TEST(StringExpr, UnaryRange) {
    using namespace milvus::query;
    using namespace milvus::segcore;

    auto schema = GenTestSchema();
    const auto& fvec_meta = schema->operator[](FieldName("fvec"));
    const auto& str_meta = schema->operator[](FieldName("str"));

    auto gen_unary_range_plan = [&, fvec_meta, str_meta](proto::plan::OpType op,
                                                         std::string value) -> std::unique_ptr<proto::plan::PlanNode> {
        auto column_info = GenColumnInfo(str_meta.get_id().get(), proto::schema::DataType::VarChar, false, false);
        auto unary_range_expr = GenUnaryRangeExpr(op, value);
        unary_range_expr->set_allocated_column_info(column_info);

        auto expr = GenExpr().release();
        expr->set_allocated_unary_range_expr(unary_range_expr);

        auto anns = GenAnns(expr, fvec_meta.get_data_type() == DataType::VECTOR_BINARY, fvec_meta.get_id().get(), "$0");

        auto plan_node = std::make_unique<proto::plan::PlanNode>();
        plan_node->set_allocated_vector_anns(anns);
        return std::move(plan_node);
    };

    std::vector<std::tuple<proto::plan::OpType, std::string, std::function<bool(std::string)>>> testcases{
        {proto::plan::OpType::GreaterThan, "2000", [](std::string val) { return val > "2000"; }},
        {proto::plan::OpType::GreaterEqual, "2000", [](std::string val) { return val >= "2000"; }},
        {proto::plan::OpType::LessThan, "3000", [](std::string val) { return val < "3000"; }},
        {proto::plan::OpType::LessEqual, "3000", [](std::string val) { return val <= "3000"; }},
        {proto::plan::OpType::PrefixMatch, "a", [](std::string val) { return PrefixMatch(val, "a"); }},
    };

    auto seg = CreateGrowingSegment(schema);
    int N = 1000;
    std::vector<std::string> str_col;
    int num_iters = 100;
    for (int iter = 0; iter < num_iters; ++iter) {
        auto raw_data = DataGen(schema, N, iter);
        auto new_str_col = raw_data.get_col(str_meta.get_id());
        auto begin = new_str_col->scalars().string_data().data().begin();
        auto end = new_str_col->scalars().string_data().data().end();
        str_col.insert(str_col.end(), begin, end);
        seg->PreInsert(N);
        seg->Insert(iter * N, N, raw_data.row_ids_.data(), raw_data.timestamps_.data(), raw_data.raw_);
    }

    auto seg_promote = dynamic_cast<SegmentGrowingImpl*>(seg.get());
    ExecExprVisitor visitor(*seg_promote, seg_promote->get_row_count(), MAX_TIMESTAMP);
    for (const auto& [op, value, ref_func] : testcases) {
        auto plan_proto = gen_unary_range_plan(op, value);
        auto plan = ProtoParser(*schema).CreatePlan(*plan_proto);
        auto final = visitor.call_child(*plan->plan_node_->predicate_.value());
        EXPECT_EQ(final.size(), N * num_iters);

        for (int i = 0; i < N * num_iters; ++i) {
            auto ans = final[i];

            auto val = str_col[i];
            auto ref = ref_func(val);
            ASSERT_EQ(ans, ref) << "@" << op << "@" << value << "@" << i << "!!" << val;
        }
    }
}

TEST(StringExpr, BinaryRange) {
    using namespace milvus::query;
    using namespace milvus::segcore;

    auto schema = GenTestSchema();
    const auto& fvec_meta = schema->operator[](FieldName("fvec"));
    const auto& str_meta = schema->operator[](FieldName("str"));

    auto gen_binary_range_plan = [&, fvec_meta, str_meta](bool lb_inclusive, bool ub_inclusive, std::string lb,
                                                          std::string ub) -> std::unique_ptr<proto::plan::PlanNode> {
        auto column_info = GenColumnInfo(str_meta.get_id().get(), proto::schema::DataType::VarChar, false, false);
        auto binary_range_expr = GenBinaryRangeExpr(lb_inclusive, ub_inclusive, lb, ub);
        binary_range_expr->set_allocated_column_info(column_info);

        auto expr = GenExpr().release();
        expr->set_allocated_binary_range_expr(binary_range_expr);

        auto anns = GenAnns(expr, fvec_meta.get_data_type() == DataType::VECTOR_BINARY, fvec_meta.get_id().get(), "$0");

        auto plan_node = std::make_unique<proto::plan::PlanNode>();
        plan_node->set_allocated_vector_anns(anns);
        return std::move(plan_node);
    };

    // bool lb_inclusive, bool ub_inclusive, std::string lb, std::string ub
    std::vector<std::tuple<bool, bool, std::string, std::string, std::function<bool(std::string)>>> testcases{
        {false, false, "2000", "3000", [](std::string val) { return val > "2000" && val < "3000"; }},
        {false, true, "2000", "3000", [](std::string val) { return val > "2000" && val <= "3000"; }},
        {true, false, "2000", "3000", [](std::string val) { return val >= "2000" && val < "3000"; }},
        {true, true, "2000", "3000", [](std::string val) { return val >= "2000" && val <= "3000"; }},
        {true, true, "2000", "1000", [](std::string val) { return false; }},
    };

    auto seg = CreateGrowingSegment(schema);
    int N = 1000;
    std::vector<std::string> str_col;
    int num_iters = 100;
    for (int iter = 0; iter < num_iters; ++iter) {
        auto raw_data = DataGen(schema, N, iter);
        auto new_str_col = raw_data.get_col(str_meta.get_id());
        auto begin = new_str_col->scalars().string_data().data().begin();
        auto end = new_str_col->scalars().string_data().data().end();
        str_col.insert(str_col.end(), begin, end);
        seg->PreInsert(N);
        seg->Insert(iter * N, N, raw_data.row_ids_.data(), raw_data.timestamps_.data(), raw_data.raw_);
    }

    auto seg_promote = dynamic_cast<SegmentGrowingImpl*>(seg.get());
    ExecExprVisitor visitor(*seg_promote, seg_promote->get_row_count(), MAX_TIMESTAMP);
    for (const auto& [lb_inclusive, ub_inclusive, lb, ub, ref_func] : testcases) {
        auto plan_proto = gen_binary_range_plan(lb_inclusive, ub_inclusive, lb, ub);
        auto plan = ProtoParser(*schema).CreatePlan(*plan_proto);
        auto final = visitor.call_child(*plan->plan_node_->predicate_.value());
        EXPECT_EQ(final.size(), N * num_iters);

        for (int i = 0; i < N * num_iters; ++i) {
            auto ans = final[i];

            auto val = str_col[i];
            auto ref = ref_func(val);
            ASSERT_EQ(ans, ref) << "@" << lb_inclusive << "@" << ub_inclusive << "@" << lb << "@" << ub << "@" << i
                                << "!!" << val;
        }
    }
}

TEST(AlwaysTrueStringPlan, SearchWithOutputFields) {
    using namespace milvus::query;
    using namespace milvus::segcore;

    auto schema = GenStrPKSchema();
    const auto& fvec_meta = schema->operator[](FieldName("fvec"));
    const auto& str_meta = schema->operator[](FieldName("str"));

    auto N = 100000;
    auto dim = fvec_meta.get_dim();
    auto round_decimal = -1;
    auto dataset = DataGen(schema, N);
    auto vec_col = dataset.get_col<float>(fvec_meta.get_id());
    auto str_col = dataset.get_col(str_meta.get_id())->scalars().string_data().data();
    auto query_ptr = vec_col.data();
    auto segment = CreateGrowingSegment(schema);
    segment->disable_small_index();  // brute-force search.
    segment->PreInsert(N);
    segment->Insert(0, N, dataset.row_ids_.data(), dataset.timestamps_.data(), dataset.raw_);

    auto plan_proto = GenAlwaysTruePlan(fvec_meta, str_meta);
    SetTargetEntry(plan_proto, {str_meta.get_id().get()});
    auto plan = ProtoParser(*schema).CreatePlan(*plan_proto);
    auto num_queries = 5;
    auto topk = 10;
    auto ph_group_raw = CreatePlaceholderGroupFromBlob(num_queries, 16, query_ptr);
    auto ph_group = ParsePlaceholderGroup(plan.get(), ph_group_raw.SerializeAsString());

    Timestamp time = MAX_TIMESTAMP;
    std::vector<const PlaceholderGroup*> ph_group_arr = {ph_group.get()};

    query::dataset::SearchDataset search_dataset{
        faiss::MetricType::METRIC_L2,  //
        num_queries,                   //
        topk,                          //
        round_decimal,
        dim,       //
        query_ptr  //
    };
    auto sub_result = FloatSearchBruteForce(search_dataset, vec_col.data(), N, nullptr);

    auto sr = segment->Search(plan.get(), ph_group.get(), time);
    segment->FillPrimaryKeys(plan.get(), *sr);
    segment->FillTargetEntry(plan.get(), *sr);
    ASSERT_EQ(sr->pk_type_, DataType::VARCHAR);
    ASSERT_TRUE(sr->output_fields_data_.find(str_meta.get_id()) != sr->output_fields_data_.end());
    auto retrieved_str_col = sr->output_fields_data_[str_meta.get_id()]->scalars().string_data().data();
    for (auto q = 0; q < num_queries; q++) {
        for (auto k = 0; k < topk; k++) {
            auto offset = q * topk + k;
            auto seg_offset = sub_result.get_seg_offsets()[offset];
            ASSERT_EQ(std::get<std::string>(sr->primary_keys_[offset]), str_col[seg_offset]);
            ASSERT_EQ(retrieved_str_col[offset], str_col[seg_offset]);
        }
    }
}

TEST(AlwaysTrueStringPlan, QueryWithOutputFields) {
    using namespace milvus::query;
    using namespace milvus::segcore;

    auto schema = GenStrPKSchema();
    const auto& fvec_meta = schema->operator[](FieldName("fvec"));
    const auto& str_meta = schema->operator[](FieldName("str"));

    auto N = 100000;
    auto dataset = DataGen(schema, N);
    auto vec_col = dataset.get_col<float>(fvec_meta.get_id());
    auto str_col = dataset.get_col(str_meta.get_id())->scalars().string_data().data();
    auto segment = CreateGrowingSegment(schema);
    segment->disable_small_index();  // brute-force search.
    segment->PreInsert(N);
    segment->Insert(0, N, dataset.row_ids_.data(), dataset.timestamps_.data(), dataset.raw_);

    auto expr_proto = GenAlwaysTrueExpr(fvec_meta, str_meta);
    auto plan_proto = GenPlanNode();
    plan_proto->set_allocated_predicates(expr_proto);
    SetTargetEntry(plan_proto, {str_meta.get_id().get()});
    auto plan = ProtoParser(*schema).CreateRetrievePlan(*plan_proto);

    Timestamp time = MAX_TIMESTAMP;

    auto retrieved = segment->Retrieve(plan.get(), time);
    ASSERT_EQ(retrieved->ids().str_id().data().size(), N);
    ASSERT_EQ(retrieved->offset().size(), N);
    ASSERT_EQ(retrieved->fields_data().size(), 1);
    ASSERT_EQ(retrieved->fields_data(0).scalars().string_data().data().size(), N);
}

max_stars_repo_name: aakejiang/milvus

max_issues_repo_name: aakejiang/milvus

max_forks_repo_name: aakejiang/milvus


text:
//IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.

// By downloading, copying, installing or using the software you agree to this license.
// If you do not agree to this license, do not download, install,
// copy or use the software.

//                          License Agreement
//               For Open Source Computer Vision Library

//Copyright (C) 2000-2008, Intel Corporation, all rights reserved.
//Copyright (C) 2008-2010, Willow Garage Inc., all rights reserved.
//Third party copyrights are property of their respective owners.

//Redistribution and use in source and binary forms, with or without modification,
//are permitted provided that the following conditions are met:

//  * Redistribution's of source code must retain the above copyright notice,
//  this list of conditions and the following disclaimer.

//  * Redistribution's in binary form must reproduce the above copyright notice,
//  this list of conditions and the following disclaimer in the documentation
//  and/or other materials provided with the distribution.

//  * The name of the copyright holders may not be used to endorse or promote products
//  derived from this software without specific prior written permission.

//This software is provided by the copyright holders and contributors "as is" and
//any express or implied warranties, including, but not limited to, the implied
//warranties of merchantability and fitness for a particular purpose are disclaimed.
//In no event shall the Intel Corporation or contributors be liable for any direct,
//indirect, incidental, special, exemplary, or consequential damages
//(including, but not limited to, procurement of substitute goods or services;
//loss of use, data, or profits; or business interruption) however caused
//and on any theory of liability, whether in contract, strict liability,
//or tort (including negligence or otherwise) arising in any way out of
//the use of this software, even if advised of the possibility of such damage.

//--------------------Google Code 2010 -- Yannick Verdie--------------------//

#include <memory>

#include "GuiReceiver.h"
#include "GraphViewer.h"
#include "view/MatrixViewer.h"
#include "Convertor.h"

#ifdef _WIN32
#pragma warning(disable:4503)
#pragma warning(push)
#pragma warning(disable:4996 4251 4275 4800)
#endif
#include <math.h>
#include <QColorDialog>
#include <boost/lexical_cast.hpp>
#include <boost/thread/lock_guard.hpp>
#include <opencv2/highgui.hpp>
#include <QString>
#include <QDialogButtonBox>

#ifdef _WIN32
#pragma warning(disable:4503)
#include <windows.h>
#pragma warning(pop)
#else
#include <unistd.h>
#endif

using boost::lexical_cast;
using boost::lock_guard;
using namespace cv;
using namespace charliesoft;

//Static and global first
static bool multiThreads = false;
GuiReceiver* GuiReceiver::guiMainThread = NULL;

static MatrixViewer* icvFindWindowByName(QString name)
{
  MatrixViewer* window = 0;

  QWidgetList winList = QApplication::topLevelWidgets();
  for (auto* widget : winList)
  {
    if (widget != NULL && widget->isWindow() && !widget->parentWidget())//is a window without parent
    {
      if (MatrixViewer* w = dynamic_cast<MatrixViewer*>(widget))
      {
        if (w->windowTitle() == name)
        {
          window = w;
          break;
        }
      }
    }
  }

  return window;
}

static GraphViewer* icvFindGraphViewByName(QString name)
{
  GraphViewer* window = 0;

  //This is not a very clean way to do the stuff. Indeed, QAction automatically generate toolTil (QLabel)
  //that can be grabbed here and crash the code at 'w->param_name==name'.
  foreach(QWidget* widget, QApplication::topLevelWidgets())
  {
    if (widget!=NULL && widget->isWindow() && !widget->parentWidget())//is a window without parent
    {
      if (GraphViewer* w = dynamic_cast<GraphViewer*>(widget))
      {
        if (w->windowTitle() == name)
        {
          window = w;
          break;
        }
      }
    }
  }

  return window;
}

void imshow(cv::String name, cv::Mat im)
{
  GuiReceiver::getInstance()->showImage(QString(name.c_str()), im);
}

GraphViewer* createGraphView(cv::String name)
{
  GraphViewer* gv = icvFindGraphViewByName(name.c_str());
  if (gv == NULL)
  {
    QMetaObject::invokeMethod(GuiReceiver::getInstance(),
      "createGraph",
      Qt::AutoConnection,
      Q_ARG(QString, QString(name.c_str())));

    boost::this_thread::sleep(boost::posix_time::milliseconds(100));//wait for the window creation
    gv = icvFindGraphViewByName(name.c_str());
  }

  return gv;
}

MatrixViewer* createWindow(cv::String name, int params)
{
  MatrixViewer* mv = icvFindWindowByName(name.c_str());
  if (mv == NULL)
  {
    QMetaObject::invokeMethod(GuiReceiver::getInstance(),
      "createWindow",
      Qt::AutoConnection,
      Q_ARG(QString, QString(name.c_str())),
      Q_ARG(int, params));

    boost::this_thread::sleep(boost::posix_time::milliseconds(100));//wait for the window creation
    mv = icvFindWindowByName(name.c_str());
  }

  return mv;
}

//////////////////////////////////////////////////////
// GuiReceiver
boost::recursive_mutex mtx_gui;
GuiReceiver* GuiReceiver::getInstance()
{
  boost::unique_lock<boost::recursive_mutex> guard(mtx_gui);
  if (guiMainThread==NULL)
    guiMainThread = new GuiReceiver();
  return guiMainThread;
}

GuiReceiver::GuiReceiver() : bTimeOut(false), nb_windows(0)
{
  guiMainThread = this;
  doesExternalQAppExist = (QApplication::instance() != 0);

  timer = new QTimer(this);
  QObject::connect(timer, SIGNAL(timeout()), this, SLOT(timeOut()));
  timer->setSingleShot(true);
}

void GuiReceiver::saveWindowParameters(QString name)
{
  QPointer<MatrixViewer> w = icvFindWindowByName(name);

  if (w)
    w->writeSettings();
}

void GuiReceiver::loadWindowParameters(QString name)
{
  QPointer<MatrixViewer> w = icvFindWindowByName(name);

  if (w)
    w->readSettings();
}

double GuiReceiver::getPropWindow(QString name)
{
  QPointer<MatrixViewer> w = icvFindWindowByName(name);

  if (!w)
    return -1;

  return (double)w->getPropWindow();
}

void GuiReceiver::setPropWindow(QString name, double arg2)
{
  QPointer<MatrixViewer> w = icvFindWindowByName(name);

  if (!w)
    return;

  int flags = (int)arg2;

  w->setPropWindow(flags);
}

double GuiReceiver::isFullScreen(QString name)
{
  QPointer<MatrixViewer> w = icvFindWindowByName(name);

  if (!w)
    return -1;

  return w->isFullScreen() ? CV_WINDOW_FULLSCREEN : CV_WINDOW_NORMAL;
}

void GuiReceiver::toggleFullScreen(QString name, double arg2)
{
  QPointer<MatrixViewer> w = icvFindWindowByName(name);

  if (!w)
    return;

  int flags = (int)arg2;

  w->toggleFullScreen(flags);
}

void GuiReceiver::createGraph(QString name)
{
  if (!qApp)
    CV_Error(CV_StsNullPtr, "NULL session handler");

  // Check the name in the storage
  if (icvFindGraphViewByName(name.toLatin1().data()))
    return;

  nb_windows++;
  GraphViewer* w = new GraphViewer();
  w->setWindowTitle(name);
}

void GuiReceiver::createWindow(QString name, int flags)
{
  if (!qApp)
  {
    int argc = 1;
    char ** argv = NULL;
    new QApplication(argc, argv);
  }
  //  CV_Error(CV_StsNullPtr, "NULL session handler");

  // Check the name in the storage
  if (icvFindWindowByName(name.toLatin1().data()))
    return;

  nb_windows++;
  MatrixViewer* w = new MatrixViewer(name, flags);

  w->updateImage(Mat::zeros(3,3,CV_8UC1));

}

void GuiReceiver::timeOut()
{
  bTimeOut = true;
}

void GuiReceiver::displayInfo(QString name, QString text, int delayms)
{
  QPointer<MatrixViewer> w = icvFindWindowByName(name);

  if (w)
    w->displayInfo(text, delayms);
}

void GuiReceiver::showImage(QString name, cv::Mat arr)
{
  QPointer<MatrixViewer> w = icvFindWindowByName(name);

  if (!w) //as observed in the previous implementation (W32, GTK or Carbon), create a new window is the pointer returned is null
  {
    QMetaObject::invokeMethod(guiMainThread,
      "createWindow",
      //Qt::BlockingQueuedConnection,
      Qt::AutoConnection,
      Q_ARG(QString, QString(name)),
      Q_ARG(int, 0));
    w = icvFindWindowByName(name);
  }

  if (!w || arr.empty())
    return; // keep silence here.

  w->updateImage(arr);

  if (w->isHidden())
  {
    QMetaObject::invokeMethod(w,
      "show",
      Qt::AutoConnection);
  }
}

void GuiReceiver::destroyWindow(QString name)
{
  QPointer<MatrixViewer> w = icvFindWindowByName(name);

  if (w)
  {
    w->close();

    //in not-multiThreads mode, looks like the window is hidden but not deleted
    //so I do it manually
    //otherwise QApplication do it for me if the exec command was executed (in multiThread mode)
    if (!multiThreads)
      delete w;
  }
}

void GuiReceiver::moveWindow(QString name, int x, int y)
{
  QPointer<MatrixViewer> w = icvFindWindowByName(name);

  if (w)
    w->move(x, y);
}

void GuiReceiver::resizeWindow(QString name, int width, int height)
{
  QPointer<MatrixViewer> w = icvFindWindowByName(name);

  if (w)
  {
    w->showNormal();
    w->setViewportSize(QSize(width, height));
  }
}

void GuiReceiver::enablePropertiesButtonEachWindow()
{
  //For each window, enable window property button
  foreach(QWidget* widget, QApplication::topLevelWidgets())
  {
    if (widget!=NULL && widget->isWindow() && !widget->parentWidget()) //is a window without parent
    {
      if (MatrixViewer* w = dynamic_cast<MatrixViewer*>(widget))
      {
        //active window properties button
        w->enablePropertiesButton();
      }
    }
  }
}

max_stars_repo_name: Petititi/imGraph

max_issues_repo_name: Petititi/imGraph

max_forks_repo_name: Petititi/imGraph


text:
// Copyright (c) 2017-2022 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.

#include <wallet/coinselection.h>

#include <util.h>
#include <utilmoneystr.h>

#include <boost/optional.hpp>

#include <random>
#include <algorithm>

// Descending order comparator
struct {
    bool operator()(const OutputGroup& a, const OutputGroup& b) const
    {
        return a.effective_value > b.effective_value;
    }
} descending;

/*
 * This is the Branch and Bound Coin Selection algorithm designed by Murch. It searches for an input
 * set that can pay for the spending target and does not exceed the spending target by more than the
 * cost of creating and spending a change output. The algorithm uses a depth-first search on a binary
 * tree. In the binary tree, each node corresponds to the inclusion or the omission of a UTXO. UTXOs
 * are sorted by their effective values and the trees is explored deterministically per the inclusion
 * branch first. At each node, the algorithm checks whether the selection is within the target range.
 * While the selection has not reached the target range, more UTXOs are included. When a selection's
 * value exceeds the target range, the complete subtree deriving from this selection can be omitted.
 * At that point, the last included UTXO is deselected and the corresponding omission branch explored
 * instead. The search ends after the complete tree has been searched or after a limited number of tries.
 *
 * The search continues to search for better solutions after one solution has been found. The best
 * solution is chosen by minimizing the waste metric. The waste metric is defined as the cost to
 * spend the current inputs at the given fee rate minus the long term expected cost to spend the
 * inputs, plus the amount the selection exceeds the spending target:
 *
 * waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)
 *
 * The algorithm uses two additional optimizations. A lookahead keeps track of the total value of
 * the unexplored UTXOs. A subtree is not explored if the lookahead indicates that the target range
 * cannot be reached. Further, it is unnecessary to test equivalent combinations. This allows us
 * to skip testing the inclusion of UTXOs that match the effective value and waste of an omitted
 * predecessor.
 *
 * The Branch and Bound algorithm is described in detail in Murch's Master Thesis:
 * https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf
 *
 * @param const std::vector<CInputCoin>& utxo_pool The set of UTXOs that we are choosing from.
 *        These UTXOs will be sorted in descending order by effective value and the CInputCoins'
 *        values are their effective values.
 * @param const CAmount& target_value This is the value that we want to select. It is the lower
 *        bound of the range.
 * @param const CAmount& cost_of_change This is the cost of creating and spending a change output.
 *        This plus target_value is the upper bound of the range.
 * @param std::set<CInputCoin>& out_set -> This is an output parameter for the set of CInputCoins
 *        that have been selected.
 * @param CAmount& value_ret -> This is an output parameter for the total value of the CInputCoins
 *        that were selected.
 * @param CAmount not_input_fees -> The fees that need to be paid for the outputs and fixed size
 *        overhead (version, locktime, marker and flag)
 */

static const size_t TOTAL_TRIES = 100000;

bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees)
{
    out_set.clear();
    CAmount curr_value = 0;

    std::vector<bool> curr_selection; // select the utxo at this index
    curr_selection.reserve(utxo_pool.size());
    CAmount actual_target = not_input_fees + target_value;

    // Calculate curr_available_value
    CAmount curr_available_value = 0;
    for (const OutputGroup& utxo : utxo_pool) {
        // Assert that this utxo is not negative. It should never be negative, effective value calculation should have removed it
        assert(utxo.effective_value > 0);
        curr_available_value += utxo.effective_value;
    }
    if (curr_available_value < actual_target) {
        return false;
    }

    // Sort the utxo_pool
    std::sort(utxo_pool.begin(), utxo_pool.end(), descending);

    CAmount curr_waste = 0;
    std::vector<bool> best_selection;
    CAmount best_waste = MAX_MONEY;

    // Depth First search loop for choosing the UTXOs
    for (size_t i = 0; i < TOTAL_TRIES; ++i) {
        // Conditions for starting a backtrack
        bool backtrack = false;
        if (curr_value + curr_available_value < actual_target ||                // Cannot possibly reach target with the amount remaining in the curr_available_value.
            curr_value > actual_target + cost_of_change ||    // Selected value is out of range, go back and try other branch
            (curr_waste > best_waste && (utxo_pool.at(0).fee - utxo_pool.at(0).long_term_fee) > 0)) { // Don't select things which we know will be more wasteful if the waste is increasing
            backtrack = true;
        } else if (curr_value >= actual_target) {       // Selected value is within range
            curr_waste += (curr_value - actual_target); // This is the excess value which is added to the waste for the below comparison
            // Adding another UTXO after this check could bring the waste down if the long term fee is higher than the current fee.
            // However we are not going to explore that because this optimization for the waste is only done when we have hit our target
            // value. Adding any more UTXOs will be just burning the UTXO; it will go entirely to fees. Thus we aren't going to
            // explore any more UTXOs to avoid burning money like that.
            if (curr_waste <= best_waste) {
                best_selection = curr_selection;
                best_selection.resize(utxo_pool.size());
                best_waste = curr_waste;
            }
            curr_waste -= (curr_value - actual_target); // Remove the excess value as we will be selecting different coins now
            backtrack = true;
        }

        // Backtracking, moving backwards
        if (backtrack) {
            // Walk backwards to find the last included UTXO that still needs to have its omission branch traversed.
            while (!curr_selection.empty() && !curr_selection.back()) {
                curr_selection.pop_back();
                curr_available_value += utxo_pool.at(curr_selection.size()).effective_value;
            }

            if (curr_selection.empty()) { // We have walked back to the first utxo and no branch is untraversed. All solutions searched
                break;
            }

            // Output was included on previous iterations, try excluding now.
            curr_selection.back() = false;
            OutputGroup& utxo = utxo_pool.at(curr_selection.size() - 1);
            curr_value -= utxo.effective_value;
            curr_waste -= utxo.fee - utxo.long_term_fee;
        } else { // Moving forwards, continuing down this branch
            OutputGroup& utxo = utxo_pool.at(curr_selection.size());

            // Remove this utxo from the curr_available_value utxo amount
            curr_available_value -= utxo.effective_value;

            // Avoid searching a branch if the previous UTXO has the same value and same waste and was excluded. Since the ratio of fee to
            // long term fee is the same, we only need to check if one of those values match in order to know that the waste is the same.
            if (!curr_selection.empty() && !curr_selection.back() &&
                utxo.effective_value == utxo_pool.at(curr_selection.size() - 1).effective_value &&
                utxo.fee == utxo_pool.at(curr_selection.size() - 1).fee) {
                curr_selection.push_back(false);
            } else {
                // Inclusion branch first (Largest First Exploration)
                curr_selection.push_back(true);
                curr_value += utxo.effective_value;
                curr_waste += utxo.fee - utxo.long_term_fee;
            }
        }
    }

    // Check for solution
    if (best_selection.empty()) {
        return false;
    }

    // Set output set
    value_ret = 0;
    for (size_t i = 0; i < best_selection.size(); ++i) {
        if (best_selection.at(i)) {
            util::insert(out_set, utxo_pool.at(i).m_outputs);
            value_ret += utxo_pool.at(i).m_value;
        }
    }

    return true;
}

static void ApproximateBestSubset(const std::vector<OutputGroup>& groups, const CAmount& nTotalLower, const CAmount& nTargetValue,
                                  std::vector<char>& vfBest, CAmount& nBest, int iterations = 1000)
{
    std::vector<char> vfIncluded;

    vfBest.assign(groups.size(), true);
    nBest = nTotalLower;

    FastRandomContext insecure_rand;

    for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++)
    {
        vfIncluded.assign(groups.size(), false);
        CAmount nTotal = 0;
        bool fReachedTarget = false;
        for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++)
        {
            for (unsigned int i = 0; i < groups.size(); i++)
            {
                //The solver here uses a randomized algorithm,
                //the randomness serves no real security purpose but is just
                //needed to prevent degenerate behavior and it is important
                //that the rng is fast. We do not use a constant random sequence,
                //because there may be some privacy improvement by making
                //the selection random.
                if (nPass == 0 ? insecure_rand.randbool() : !vfIncluded[i])
                {
                    nTotal += groups[i].m_value;
                    vfIncluded[i] = true;
                    if (nTotal >= nTargetValue)
                    {
                        fReachedTarget = true;
                        if (nTotal < nBest)
                        {
                            nBest = nTotal;
                            vfBest = vfIncluded;
                        }
                        nTotal -= groups[i].m_value;
                        vfIncluded[i] = false;
                    }
                }
            }
        }
    }
}

bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& groups, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet)
{
    setCoinsRet.clear();
    nValueRet = 0;

    // List of values less than target
    boost::optional<OutputGroup> lowest_larger;
    std::vector<OutputGroup> applicable_groups;
    CAmount nTotalLower = 0;

    std::random_device rng;
    std::mt19937 urng(rng());
    std::shuffle(groups.begin(), groups.end(), urng);

    for (const OutputGroup& group : groups) {
        if (group.m_value == nTargetValue) {
            util::insert(setCoinsRet, group.m_outputs);
            nValueRet += group.m_value;
            return true;
        } else if (group.m_value < nTargetValue + MIN_CHANGE) {
            applicable_groups.push_back(group);
            nTotalLower += group.m_value;
        } else if (!lowest_larger || group.m_value < lowest_larger->m_value) {
            lowest_larger = group;
        }
    }

    if (nTotalLower == nTargetValue) {
        for (const auto& group : applicable_groups) {
            util::insert(setCoinsRet, group.m_outputs);
            nValueRet += group.m_value;
        }
        return true;
    }

    if (nTotalLower < nTargetValue) {
        if (!lowest_larger) return false;
        util::insert(setCoinsRet, lowest_larger->m_outputs);
        nValueRet += lowest_larger->m_value;
        return true;
    }

    // Solve subset sum by stochastic approximation
    std::sort(applicable_groups.begin(), applicable_groups.end(), descending);
    std::vector<char> vfBest;
    CAmount nBest;

    ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue, vfBest, nBest);
    if (nBest != nTargetValue && nTotalLower >= nTargetValue + MIN_CHANGE) {
        ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue + MIN_CHANGE, vfBest, nBest);
    }

    // If we have a bigger coin and (either the stochastic approximation didn't find a good solution,
    //                                   or the next bigger coin is closer), return the bigger coin
    if (lowest_larger &&
        ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || lowest_larger->m_value <= nBest)) {
        util::insert(setCoinsRet, lowest_larger->m_outputs);
        nValueRet += lowest_larger->m_value;
    } else {
        for (unsigned int i = 0; i < applicable_groups.size(); i++) {
            if (vfBest[i]) {
                util::insert(setCoinsRet, applicable_groups[i].m_outputs);
                nValueRet += applicable_groups[i].m_value;
            }
        }

        if (LogAcceptCategory(BCLog::SELECTCOINS)) {
            LogPrint(BCLog::SELECTCOINS, "SelectCoins() best subset: "); /* Continued */
            for (unsigned int i = 0; i < applicable_groups.size(); i++) {
                if (vfBest[i]) {
                    LogPrint(BCLog::SELECTCOINS, "%s ", FormatMoney(applicable_groups[i].m_value)); /* Continued */
                }
            }
            LogPrint(BCLog::SELECTCOINS, "total %s\n", FormatMoney(nBest));
        }
    }

    return true;
}

/******************************************************************************

 OutputGroup

 ******************************************************************************/

void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants) {
    m_outputs.push_back(output);
    m_from_me &= from_me;
    m_value += output.effective_value;
    m_depth = std::min(m_depth, depth);
    // ancestors here express the number of ancestors the new coin will end up having, which is
    // the sum, rather than the max; this will overestimate in the cases where multiple inputs
    // have common ancestors
    m_ancestors += ancestors;
    // descendants is the count as seen from the top ancestor, not the descendants as seen from the
    // coin itself; thus, this value is counted as the max, not the sum
    m_descendants = std::max(m_descendants, descendants);
    effective_value = m_value;
}

std::vector<CInputCoin>::iterator OutputGroup::Discard(const CInputCoin& output) {
    auto it = m_outputs.begin();
    while (it != m_outputs.end() && it->outpoint != output.outpoint) ++it;
    if (it == m_outputs.end()) return it;
    m_value -= output.effective_value;
    effective_value -= output.effective_value;
    return m_outputs.erase(it);
}

bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const
{
    return m_depth >= (m_from_me ? eligibility_filter.conf_mine : eligibility_filter.conf_theirs)
        && m_ancestors <= eligibility_filter.max_ancestors
        && m_descendants <= eligibility_filter.max_descendants;
}