text:
/* RevKit: A Toolkit for Reversible Circuit Design (www.revkit.org)
 * Copyright (C) 2009-2011  The RevKit Developers <revkit@informatik.uni-bremen.de>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "costs.hpp"

#include <boost/tuple/tuple.hpp>

#include "../target_tags.hpp"
#include "../functions/flatten_circuit.hpp"

namespace revkit
{

  cost_t gate_costs::operator()( const circuit& circ ) const
  {
    return circ.num_gates();
  }

  cost_t line_costs::operator()( const circuit& circ ) const
  {
    return circ.lines();
  }

  quantum_costs::quantum_costs()
    : controls_offset( 0 )
  {
  }

  cost_t quantum_costs::operator()( const gate& g, unsigned lines ) const
  {
    cost_t costs = 0ull;

    unsigned n = lines;
    unsigned c = std::distance( g.begin_controls(), g.end_controls() );

    if ( is_fredkin( g ) )
    {
      costs = 2ull;
      c += 1u;
    }

    c += std::max( -1 * (int)c, controls_offset );
    c = std::min( c, lines - 1u );

    unsigned e = n - c - 1u; // empty lines

    switch ( c ) {
    case 0u:
    case 1u:
      costs = 1ull;
      break;
    case 2u:
      costs = 5ull;
      break;
    case 3u:
      costs = 13ull;
      break;
    case 4u:
      costs = ( e >= 2u ) ? 26ull : 29ull;
      break;
    case 5u:
      if ( e >= 3u ) {
        costs = 38ull;
      } else if ( e >= 1u ) {
        costs = 52ull;
      } else {
        costs = 61ull;
      }
      break;
    case 6u:
      if ( e >= 4u ) {
        costs = 50ull;
      } else if ( e >= 1u ) {
        costs = 80ull;
      } else {
        costs = 125ull;
      }
      break;
    case 7u:
      if ( e >= 5u ) {
        costs = 62ull;
      } else if ( e >= 1u ) {
        costs = 100ull;
      } else {
        costs = 253ull;
      }
      break;
    case 8u:
      if ( e >= 6u ) {
        costs = 74ull;
      } else if ( e >= 1u ) {
        costs = 128ull;
      } else {
        costs = 509ull;
      }
      break;
    case 9u:
      if ( e >= 7u ) {
        costs = 86ull;
      } else if ( e >= 1u ) {
        costs = 152ull;
      } else {
        costs = 1021ull;
      }
      break;
    default:
      if ( e >= c - 2u ) {
        costs = 12ull * c - 33ull;
      } else if ( e >= 1u ) {
        costs = 24ull * c - 87ull;
      } else {
        costs = ( 1ull << ( c + 1ull ) ) - 3ull;
      }
    }

    return costs;
  }

  cost_t transistor_costs::operator()( const gate& g, unsigned lines ) const
  {
    return 8ull * std::distance( g.begin_controls(), g.end_controls() );
  }

  struct costs_visitor : public boost::static_visitor<cost_t>
  {
    explicit costs_visitor( const circuit& circ ) : circ( circ ) {}

    cost_t operator()( const costs_by_circuit_func& f ) const
    {
      // flatten before if the circuit has modules
      if ( circ.modules().empty() )
      {
        return f( circ );
      }
      else
      {
        circuit flattened;
        flatten_circuit( circ, flattened );
        return f( flattened );
      }
    }

    cost_t operator()( const costs_by_gate_func& f ) const
    {
      cost_t sum = 0ull;
      foreach ( const gate& g, circ )
      {
        // respect modules
        if ( is_module( g ) )
        {
          sum += costs( *boost::any_cast<module_tag>( g.type() ).reference.get(), f );
        }
        else
        {
          sum += f( g, circ.lines() );
        }
      }
      return sum;
    }

  private:
    const circuit& circ;
  };

  cost_t costs( const circuit& circ, const cost_function& f )
  {
    return boost::apply_visitor( costs_visitor( circ ), f );
  }

}

max_stars_repo_name: clairechingching/ScaffCC

max_issues_repo_name: clairechingching/ScaffCC

max_forks_repo_name: clairechingching/ScaffCC


text:
// Copyright (c) 2018-present Baidu, Inc. 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 <boost/algorithm/string.hpp>
#include "qos.h"

namespace baikaldb {
DEFINE_int64(qps_statistics_minutes_ago,     60,     "qps_statistics_minutes_ago, default: 1h"); // 默认以前一小时的统计信息作为参考
DEFINE_int64(max_tokens_per_second,          100000, "max_tokens_per_second, default: 10w");
DEFINE_int64(use_token_bucket,               0,      "use_token_bucket, 0:close; 1:open, default: 0");
DEFINE_int64(get_token_weight,               5,      "get_token_weight, default: 5");
DEFINE_int64(min_global_extended_percent,    40,     "min_global_extended_percent, default: 40%");
DEFINE_int64(token_bucket_adjust_interval_s, 60,     "token_bucket_adjust_interval_s, default: 60s");
DEFINE_int64(token_bucket_burst_window_ms,   10,     "token_bucket_burst_window_ms, default: 10ms");
DEFINE_int64(dml_use_token_bucket,           0,      "dml_use_token_bucket, default: 0");
DEFINE_int64(sql_token_bucket_timeout_min,   5,      "sql_token_bucket_timeout_min, default: 5min");
DEFINE_int64(qos_reject_interval_s,          30,     "qos_reject_interval_s, default: 30s");
DEFINE_int64(qos_reject_ratio,               90,     "qos_reject_ratio, default: 90%");
DEFINE_int64(qos_reject_timeout_s,           30*60,  "qos_reject_timeout_s, default: 30min");
DEFINE_int64(qos_reject_max_scan_ratio,      50,     "qos_reject_max_scan_ratio, default: 50%");
DEFINE_int64(qos_reject_growth_multiple,     100,    "qos_reject_growth_multiple, default: 100倍");
DEFINE_int64(qos_need_reject,                0,      "qos_need_reject, default: 0");
DEFINE_string(sign_blacklist,                "",     "sign blacklist");

// need_statistics: 超过最小超额令牌时，不计入统计信息
int64_t TokenBucket::consume(int64_t expect_tokens, int64_t* expire_time, bool* need_statistics) {
    const int64_t now     = butil::gettimeofday_us();
    const int64_t divisor = now / (FLAGS_token_bucket_burst_window_ms * 1000);
    const int64_t window_start   = divisor * (FLAGS_token_bucket_burst_window_ms * 1000);
    const int64_t window_end     = (divisor + 1) * (FLAGS_token_bucket_burst_window_ms * 1000);
    const int64_t time_need = expect_tokens * _time_per_token;
    *expire_time = window_end;
    int64_t old_time = _time.load(std::memory_order_relaxed);
    int64_t new_time = old_time;
    if (new_time > window_end) {
        return -1;
    }

    if (!_valid) {
        return -1;
    }

    if (new_time < window_start) {
        // 前一个窗口的令牌丢弃
        new_time = window_start;
    }

    while (true) {
        if (new_time > window_end) {
            return -1;
        }

        int64_t desired_time = new_time + time_need;
        if (desired_time > window_end + _time_per_token) {
            // 该窗口内令牌不足，减少令牌获取量
            expect_tokens = (window_end - new_time) / _time_per_token + 1;
            desired_time = new_time + expect_tokens * _time_per_token;
        }

        if (_time.compare_exchange_weak(old_time, desired_time)) {
            if (_is_extended && desired_time > (window_start + _statistics_threshold)) {
                // 获取的令牌超过了最小超额令牌桶限制，不计入qps统计，防止超过阈值后等比例压缩造成正常sql被挤压
                *need_statistics = false;
            } else {
                *need_statistics = true;
            }
            return expect_tokens;
        }

        new_time = old_time;

    }

    return 0;
}

// 归还令牌
void TokenBucket::return_tokens(const int64_t tokens, const int64_t expire_time) {
    const int64_t now     = butil::gettimeofday_us();
    const int64_t divisor = now / (FLAGS_token_bucket_burst_window_ms * 1000);
    const int64_t window_start = divisor * (FLAGS_token_bucket_burst_window_ms * 1000);
    const int64_t window_end   = (divisor + 1) * (FLAGS_token_bucket_burst_window_ms * 1000);
    const int64_t time_need    = tokens * _time_per_token;

    int64_t old_time = _time.load();
    if (expire_time < now || expire_time <= window_start || expire_time < old_time) {
        return;
    }

    int64_t new_time = old_time;

    while (true) {

        new_time -= time_need;
        if (new_time < window_start) {
            new_time = window_start;
        }

        if (_time.compare_exchange_weak(old_time, new_time)) {
            return;
        }

        if (old_time > expire_time) {
            return;
        }

        new_time = old_time;

    }
}

QosBthreadLocal::QosBthreadLocal(QosType type, const uint64_t sign, const int64_t index_id) : _qos_type(type),
                                                                                _sign(sign),
                                                                                _index_id(index_id) {
    _bthread_id = bthread_self();
    if (_sign != 0) {
        _sqlqos_ptr = StoreQos::get_instance()->get_sql_shared_ptr(sign);
        _sqlqos_ptr->inc_index_count(index_id);
    }
    _get_token_weight = FLAGS_get_token_weight;
    _use_token_bucket = FLAGS_use_token_bucket;
    if (_sign == 0) {
        // 非sql请求不使用令牌桶
        _use_token_bucket = 0;
    }

    // DML需要单独判断是否需要限流
    if (_use_token_bucket == 1 && type == QOS_DML) {
        _use_token_bucket = FLAGS_dml_use_token_bucket;
    }
}

QosBthreadLocal::~QosBthreadLocal() {
    if (_sqlqos_ptr != nullptr) {
        // sql统计
        _sqlqos_ptr->dec_index_count(_index_id);
        _sqlqos_ptr->sql_statistics_adder(1);
        _sqlqos_ptr->get_statistics_adder(_get_count, _get_statistics_count);
        _sqlqos_ptr->scan_statistics_adder(_scan_count, _scan_statistics_count);
    }
}

void QosBthreadLocal::update_statistics() {
    if (_sqlqos_ptr != nullptr) {
        _sqlqos_ptr->get_statistics_adder(_get_count, _get_statistics_count);
        _sqlqos_ptr->scan_statistics_adder(_scan_count, _scan_statistics_count);
        _get_count = 0;
        _scan_count = 0;
        _get_statistics_count = 0;
        _scan_statistics_count = 0;
    }
}

void QosBthreadLocal::rate_limiting(int64_t tokens, bool* need_statistics) {
    if (_use_token_bucket == 0) {
        // 不限流
        *need_statistics = true;
        return;
    }

    if (tokens <= 0) {
        *need_statistics = false;
        return;
    }

    int64_t expire_time = 0;
    _sqlqos_ptr->fetch_tokens(tokens, &expire_time, &_is_commited_bucket, need_statistics);

    RocksdbVars::get_instance()->qos_fetch_tokens_count << tokens;
}

bool QosBthreadLocal::need_reject() {
    if (_sqlqos_ptr != nullptr) {
        return _sqlqos_ptr->need_reject(_index_id);
    }
    return false;
}

void SqlQos::get_statistics_adder(int64_t count, int64_t statistics_count) {
    _get_real.adder(count);
    _get_statistics.adder(statistics_count);
}

void SqlQos::scan_statistics_adder(int64_t count, int64_t statistics_count) {
    _scan_real.adder(count);
    _scan_statistics.adder(statistics_count);
}

void SqlQos::sql_statistics_adder(int64_t count) {
    _sql_real.adder(count);
    _sql_statistics.adder(count);
}

int64_t SqlQos::fetch_tokens(const int64_t tokens, int64_t* token_expire_time, bool* is_committed_bucket, bool* need_statistics) {

    TimeCost cost;
    bool wait = false;
    ON_SCOPE_EXIT(([this, &wait, &cost, tokens]() {
        _token_fetch.adder(tokens);
        if (wait) {
            RocksdbVars::get_instance()->qos_fetch_tokens_wait_time_cost << cost.get_time();
        }
    }));

    while (true) {
        int64_t expire_time = 0;
        int64_t count = _committed_bucket.consume(tokens, &expire_time);
        if (count > 0) {
            // 从承诺令牌桶中获取成功
            *is_committed_bucket = true;
            *token_expire_time = expire_time;
            *need_statistics = true;
            return count;
        }

        // 从全局超额令牌桶中获取令牌
        count = StoreQos::get_instance()->globle_extended_bucket_consume(tokens, &expire_time, need_statistics);
        if (count > 0) {
            *is_committed_bucket = false;
            *token_expire_time = expire_time;
            return count;
        }

        RocksdbVars::get_instance()->qos_fetch_tokens_wait_count << 1;
        // 获取令牌失败，等待到下一个窗口

        int64_t timeout_us = expire_time - butil::gettimeofday_us();
        if (timeout_us < 0) {
            RocksdbVars::get_instance()->qos_fetch_tokens_wait_count << -1;
            continue;
        }

        bthread_usleep(timeout_us);
        wait = true;
        RocksdbVars::get_instance()->qos_fetch_tokens_wait_count << -1;
    }
    return 0;
}

void SqlQos::return_tokens(const int64_t tokens, const bool is_committed_bucket, const int64_t expire_time) {
    if (is_committed_bucket) {
        _committed_bucket.return_tokens(tokens, expire_time);
    } else {
        StoreQos::get_instance()->globle_extended_bucket_return_tokens(tokens, expire_time);
    }
}

void QosReject::wheather_need_reject() {
    const int window_count = FLAGS_qos_reject_interval_s * 1000 / FLAGS_token_bucket_burst_window_ms;
    const int count = _count.get_value();
    bool match_reject_condition = (count * 100 / window_count > FLAGS_qos_reject_ratio);

    DB_WARNING("count: %d, window_count: %d, need_reject: %d, match_reject_condition: %d, time: %ld",
         count, window_count, _has_reject, match_reject_condition, _reject_begin_time.get_time());

    // 已经是拒绝状态
    if (_has_reject) {
        // 拒绝状态下压力无法降低，再次选择需要拒绝的sql
        if (match_reject_condition && _reject_begin_time.get_time() > FLAGS_qos_reject_interval_s * 1000 * 1000LL) {
            if (StoreQos::get_instance()->mark_need_reject_sql() >= 0) {
                _reject_begin_time.reset();
                DB_WARNING("mark need reject again count: %d, window_count: %d", count, window_count);
            }
        } else if (_reject_begin_time.get_time() > FLAGS_qos_reject_timeout_s * 1000 * 1000LL) {
            // 超时清理拒绝标记
            StoreQos::get_instance()->clear_need_reject();
            _has_reject = false;
            DB_WARNING("clear need reject, count: %d, window_count: %d", count, window_count);
        }
    } else if (match_reject_condition) {
        if (StoreQos::get_instance()->mark_need_reject_sql() >= 0) {
            _reject_begin_time.reset();
            _has_reject = true;
            DB_WARNING("mark need reject count: %d, window_count: %d", count, window_count);
        }
    }
}

void QosReject::update_blacklist() {
    std::set<uint64_t> cur_blacklist;
    if (!FLAGS_sign_blacklist.empty()) {
        std::vector<std::string> vec;
        boost::split(vec, FLAGS_sign_blacklist, boost::is_any_of(","));
        for (auto& sign : vec) {
            std::string sign_str = string_trim(sign);
            cur_blacklist.insert(atoll(sign_str.c_str()));
        }
    }

    if (cur_blacklist.empty() && _last_blacklist.empty()) {
        return;
    }

    std::set<uint64_t> clear_list;
    std::set<uint64_t> set_list;

    for (uint64_t sign : _last_blacklist) {
        if (cur_blacklist.find(sign) != cur_blacklist.end()) {
            clear_list.insert(sign);
        }
    }

    for (uint64_t sign : cur_blacklist) {
        if (_last_blacklist.find(sign) != _last_blacklist.end()) {
            set_list.insert(sign);
        }
    }

    if (!clear_list.empty()) {
        StoreQos::get_instance()->update_blacklist(clear_list, true);
    }

    if (!set_list.empty()) {
        StoreQos::get_instance()->update_blacklist(set_list, false);
    }

    _last_blacklist.clear();
    _last_blacklist = cur_blacklist;
}

void StoreQos::update_blacklist(const std::set<uint64_t>& signs, const bool is_clear) {
    DoubleBufQos::ScopedPtr ptr;
    if (_sign_sqlqos_map.Read(&ptr) != 0) {
        return;
    }
    if (ptr->empty()) {
        DB_WARNING("sign sqlqos map is empty");
        return;
    }

    for (const auto& sign : signs) {
        auto iter = ptr->find(sign);
        if (iter != ptr->end()) {
            if (is_clear) {
                iter->second->clear_blacklist();
            } else {
                iter->second->set_blacklist();
            }
        }
    }
}

void StoreQos::token_bucket_modify() {
    int64_t max_token        = FLAGS_max_tokens_per_second; // 最大qps限制
    int64_t get_token_weight = FLAGS_get_token_weight;      // get需要的令牌权重，即scan_token =  get_token / weight
    if (get_token_weight <= 0) {
        get_token_weight = 5;
    }
    int64_t total_get_qps    = 0;
    int64_t total_scan_qps   = 0;
    analyze_qps(total_get_qps, total_scan_qps);
    int64_t total_consume_token        = total_get_qps + total_scan_qps / get_token_weight;
    int64_t min_global_extended_tokens = max_token * FLAGS_min_global_extended_percent / 100;// 最小全局超额令牌个数
    int64_t global_extended_token      = max_token - total_consume_token;
    double  compression_ratio = 1.0; // 1.0 不压缩；< 1.0 等比例压缩

    if ((max_token - min_global_extended_tokens) < total_consume_token) {
        compression_ratio = (max_token - min_global_extended_tokens) * 1.0 / total_consume_token;
        global_extended_token = min_global_extended_tokens;
        total_consume_token = max_token - global_extended_token;
    }

    DB_WARNING("max_token: %ld, global_extended_token: %ld, total_consume_token: %ld, compression_ratio: %lf",
                    max_token, global_extended_token, total_consume_token, compression_ratio);

    {
        int64_t now = butil::gettimeofday_us();
        DoubleBufQos::ScopedPtr ptr;
        if (_sign_sqlqos_map.Read(&ptr) != 0) {
            return;
        }
        for (auto iter : *ptr) {

            int64_t get_qps  = iter.second->rocksdb_get_qps();
            int64_t scan_qps = iter.second->rocksdb_scan_qps();
            int64_t consume_token = (get_qps + scan_qps / get_token_weight) * compression_ratio;
            // 修改承诺令牌桶速率
            iter.second->reset_committed_rate(consume_token);
            total_consume_token -= consume_token;
            if (consume_token != 0) {
                DB_WARNING("sign: %lu, committed rate: %ld", iter.first, consume_token);
            }

        }

        global_extended_token += total_consume_token;
        DB_WARNING("globle extended bucket rate: %ld", global_extended_token);
        // 修改全局超额令牌桶速率
        _globle_extended_bucket.reset_rate(global_extended_token);
    }

}

int StoreQos::mark_need_reject_sql() {
    DoubleBufQos::ScopedPtr ptr;
    if (_sign_sqlqos_map.Read(&ptr) != 0) {
        return -1;
    }

    if (ptr->empty()) {
        DB_WARNING("sign sqlqos map is empty");
        return -1;
    }

    std::map<uint64_t, SqlInfo> sql_with_multi_index;
    // std::map<int64_t, SqlInfo> get_qps_sqlinfo_map;
    std::set<uint64_t> affect_indexids;
    auto iter = ptr->begin();
    while (iter != ptr->end()) {
        auto cur_iter = iter++;
        std::set<uint64_t> tmp_affect_indexids = cur_iter->second->fill_sqlqos_info(sql_with_multi_index);
        for (uint64_t indexid : tmp_affect_indexids) {
            affect_indexids.insert(indexid);
        }
    }

    bool mark = false;
    // 使用多个索引的高危sql
    if (sql_with_multi_index.empty()) {
        return -1;
    }

    for (auto it = sql_with_multi_index.rbegin(); it != sql_with_multi_index.rend(); it++) {
        int64_t index_id = met_rejection_conditions(it->second, affect_indexids);
        if (index_id <= 0) {
            DB_WARNING("conditions not met. sign: %lu, log_term [get: %ld, scan: %ld], short_term [get: %ld, scan: %ld]",
                it->first, it->second.get_long_term, it->second.scan_long_term, it->second.get_short_term, it->second.scan_short_term);
            continue;
        }

        auto sql_it = ptr->find(it->first);
        if (sql_it != ptr->end()) {
            DB_WARNING("sql use multi index need reject sign: %lu, log_term [get: %ld, scan: %ld], short_term [get: %ld, scan: %ld]",
                it->first, it->second.get_long_term, it->second.scan_long_term, it->second.get_short_term, it->second.scan_short_term);
            sql_it->second->set_need_reject(index_id);
            mark = true;
        }
    }

    // 没有标记成功
    if (!mark) {
        return -1;
    }

    return 0;
}

} // namespace baikaldb

ext: cpp

max_stars_repo_name: tisuama/BaikalDB

max_issues_repo_name: tisuama/BaikalDB

max_forks_repo_name: tisuama/BaikalDB


text:
// Copyright (c) 2013, German Neuroinformatics Node (G-Node)
//
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted under the terms of the BSD License. See
// LICENSE file in the root of the Project.

#include <nix.hpp>

#include <iostream>
#include <sstream>
#include <iterator>
#include <stdexcept>

#include <cppunit/TestFixture.h>
#include <cppunit/extensions/HelperMacros.h>
#include <cppunit/CompilerOutputter.h>
#include <cppunit/extensions/TestFactoryRegistry.h>
#include <cppunit/TestResult.h>
#include <cppunit/TestResultCollector.h>
#include <cppunit/TestRunner.h>
#include <cppunit/BriefTestProgressListener.h>
#include <boost/math/constants/constants.hpp>

class TestDimension: public CPPUNIT_NS::TestFixture {
private:

    CPPUNIT_TEST_SUITE(TestDimension);

    CPPUNIT_TEST(testValidate);
    CPPUNIT_TEST(testSetValidate);
    CPPUNIT_TEST(testSampleValidate);
    CPPUNIT_TEST(testRangeValidate);
    CPPUNIT_TEST(testIndex);
    CPPUNIT_TEST(testSampledDimLabel);
    CPPUNIT_TEST(testSampledDimOffset);
    CPPUNIT_TEST(testSampledDimUnit);
    CPPUNIT_TEST(testSampledDimSamplingInterval);
    CPPUNIT_TEST(testSampledDimOperators);
    CPPUNIT_TEST(testSampledDimIndexOf);
    CPPUNIT_TEST(testSampledDimPositionAt);
    CPPUNIT_TEST(testSampledDimAxis);

    CPPUNIT_TEST(testSetDimLabels);

    CPPUNIT_TEST(testRangeDimLabel);
    CPPUNIT_TEST(testRangeDimUnit);
    CPPUNIT_TEST(testRangeTicks);
    CPPUNIT_TEST(testRangeDimIndexOf);
    CPPUNIT_TEST(testRangeDimTickAt);
    CPPUNIT_TEST(testRangeDimAxis);

    CPPUNIT_TEST_SUITE_END ();

    nix::File file;
    nix::DataArray data_array;
    nix::Block block;

public:

    void setUp();
    void tearDown();

    void testValidate();
    void testSetValidate();
    void testSampleValidate();
    void testRangeValidate();

    void testIndex();

    void testSampledDimLabel();
    void testSampledDimOffset();
    void testSampledDimUnit();
    void testSampledDimSamplingInterval();
    void testSampledDimOperators();
    void testSampledDimIndexOf();
    void testSampledDimPositionAt();
    void testSampledDimAxis();

    void testSetDimLabels();

    void testRangeDimLabel();
    void testRangeTicks();
    void testRangeDimUnit();
    void testRangeDimIndexOf();
    void testRangeDimTickAt();
    void testRangeDimAxis();
};

ext: hpp


text:
// -*- mode:c++; c-style:k&r; c-basic-offset:4; indent-tabs-mode: nil; -*-
// vi:set et cin sw=4 cino=>se0n0f0{0}0^0\:0=sl1g0hspst0+sc3C0/0(0u0U0w0m0:

#ifndef __VCD_HPP__
#define __VCD_HPP__

#include <string>
#include <vector>
#include <set>
#include <map>
#include <fstream>
#include <boost/shared_ptr.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/thread.hpp>
#include "cstdint.hpp"
#include "error.hpp"

using namespace std;
//using namespace boost;

typedef const void *vcd_id_t;

class vcd_node {
public:
    vcd_node() throw();
public:
    typedef map<string, vcd_node> nodes_t;
public:
    vcd_id_t id; // invalid iff 0
    nodes_t children; // empty() <==> vcd_id == 0
};

class vcd_writer {
public:
    vcd_writer(const uint64_t &time, const boost::shared_ptr<ofstream> out,
               uint64_t start, uint64_t end) throw(err);
    void new_signal(const vcd_id_t &id, const vector<string> &path,
                    unsigned width) throw(err);
    void add_value(vcd_id_t id, uint64_t val) throw(err);
    void commit() throw(err); // call in the beginning of every tick
                              // to flush posedge values to VCD
    void finalize() throw(err); // call once at end to flush VCD
    void tick() throw();
    uint64_t get_time() const throw();
    void fast_forward_time(uint64_t new_time) throw();
    bool is_drained() const throw();
private:
    typedef map<vcd_id_t, string> id_map_t;
    typedef map<vcd_id_t, unsigned> widths_t;
    typedef map<vcd_id_t, uint64_t> cur_values_t;
    typedef map<vcd_id_t, uint64_t> last_values_t;
    typedef map<vcd_id_t, boost::tuple<streampos, streampos> > stream_locs_t;
private:
    string get_fresh_id() throw();
    void check_header() throw(err);
    void check_timestamp() throw(err);
    void write_val(const string &id, uint64_t val) throw(err);
    void writeln_val(const string &id, uint64_t val) throw(err);
    void declare_vars(const vcd_node::nodes_t &nodes,
                      const map<vcd_id_t, string> &ids) throw(err);
    bool is_sleeping() const throw();
private:
    uint64_t time;
    const uint64_t start_time;
    const uint64_t end_time;
    uint64_t last_timestamp;
    id_map_t ids;
    widths_t widths;
    cur_values_t cur_values;
    last_values_t last_values;
    set<vcd_id_t> dirty;
    string last_id;
    vcd_node::nodes_t paths;
    stream_locs_t def_locs;
    stream_locs_t init_locs;
    bool initialized;
    bool finalized;
    boost::shared_ptr<ofstream> out;
    mutable boost::recursive_mutex vcd_mutex;
};

#endif // __VCD_HPP__

max_stars_repo_name: rikygege/Hornet

max_issues_repo_name: rikygege/Hornet

max_forks_repo_name: rikygege/Hornet


text:
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\
|  Phycas: Python software for phylogenetic analysis                          |
|  Copyright (C) 2006 Mark T. Holder, Paul O. Lewis and David L. Swofford     |
|                                                                             |
|  This program is free software; you can redistribute it and/or modify       |
|  it under the terms of the GNU General Public License as published by       |
|  the Free Software Foundation; either version 2 of the License, or          |
|  (at your option) any later version.                                        |
|                                                                             |
|  This program is distributed in the hope that it will be useful,            |
|  but WITHOUT ANY WARRANTY; without even the implied warranty of             |
|  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the              |
|  GNU General Public License for more details.                               |
|                                                                             |
|  You should have received a copy of the GNU General Public License along    |
|  with this program; if not, write to the Free Software Foundation, Inc.,    |
|  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.                |
\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
#include <boost/cast.hpp>       //temporary!
#include <boost/math/special_functions/fpclassify.hpp>
#include "probability_distribution.hpp"
#include "relative_rate_distribution.hpp"
#include "model.hpp"
#include "basic_tree_node.hpp"
#include "tree_likelihood.hpp"
#include "xlikelihood.hpp"
#include "mcmc_chain_manager.hpp"
#include "dirichlet_move.hpp"
#include "basic_tree.hpp"
#include "tree_manip.hpp"
#include "gtr.hpp"
#include "hky.hpp"

using namespace phycas;

/*----------------------------------------------------------------------------------------------------------------------
|	The constructor sets tuning parameter `psi' and `max_psi' to 300.0 and calls reset().
*/
DirichletMove::DirichletMove() : MCMCUpdater()
	{
	is_move = true;
	dim = 0;
	psi = 300.0;
	reset();
	}

/*--------------------------------------------------------------------------------------------------------------------------
|   Resets the 'dir_forward' and 'dir_reverse' shared pointers.
*/
void DirichletMove::reset()
	{
    dir_forward.reset();
    dir_reverse.reset();
	}

/*----------------------------------------------------------------------------------------------------------------------
|	Sets the value for the data member 'psi', which is the tuning parameter for this move.
*/
void DirichletMove::setTuningParameter(
  double x) /* is the new value for psi */
	{
	psi = x;
	}

/*----------------------------------------------------------------------------------------------------------------------
|	Sets the value for the data member 'dim', which is the number of parameters updated jointly by this move.
*/
void DirichletMove::setDimension(
  unsigned d) /* is the new value for psi */
	{
	dim = d;
	}

/*----------------------------------------------------------------------------------------------------------------------
|	Provides read access to the data member 'dim', which is the number of parameters updated jointly by this move.
*/
unsigned DirichletMove::getDimension() const
	{
	return dim;
	}

/*----------------------------------------------------------------------------------------------------------------------
|	Provides read access to the data member 'psi', which is the tuning parameter for this move.
*/
double DirichletMove::getTuningParameter() const
	{
	return psi;
	}

/*--------------------------------------------------------------------------------------------------------------------------
|   Chooses a new vector of state frequencies using a sharp Dirichlet distribution centered at the original frequencies.
*/
void DirichletMove::proposeNewState()
	{
    // copy the current parameters from the model to the data member orig_params
    getParams();

    // create vector of Dirichlet parameters for selecting new parameter values (by multiplying
    // each current parameter value by the value `psi')
    c_forward.resize(orig_params.size());
	std::transform(orig_params.begin(), orig_params.end(), c_forward.begin(), 1.0 + boost::lambda::_1*psi);

	//std::cerr << "c_forward:" << std::endl;
	//std::copy(c_forward.begin(), c_forward.end(), std::ostream_iterator<double>(std::cerr, " "));
	//std::cerr << std::endl;

	// create Dirichlet distribution and sample from it to get proposed frequencies
    dir_forward = DirichletShPtr(new DirichletDistribution(c_forward));
    dir_forward->SetLot(getLot().get());
    new_params = dir_forward->Sample();

	//std::cerr << "new_params:" << std::endl;
	//std::copy(new_params.begin(), new_params.end(), std::ostream_iterator<double>(std::cerr, " "));
	//std::cerr << std::endl;

    // create vector of Dirichlet parameters for selecting old frequencies (needed for Hasting ratio calculation)
    c_reverse.resize(new_params.size());
	std::transform(new_params.begin(), new_params.end(), c_reverse.begin(), 1.0 + boost::lambda::_1*psi);
    dir_reverse = DirichletShPtr(new DirichletDistribution(c_reverse));
	}

/*--------------------------------------------------------------------------------------------------------------------------
|	Returns the natural log of the Hastings ratio for this move. The Hastings ratio is:
|>
|	Pr(new state -> old state)   Dir(c'[i]*psi) density evaluated at c
|	-------------------------- = -------------------------------------
|	Pr(old state -> new state)   Dir(c[i]*psi) density evaluated at c'
|>
|   where c[i] is the ith current parameter and c'[i] is the ith proposed new parameter.
*/
double DirichletMove::getLnHastingsRatio() const
	{
	double log_prob_reverse_move = dir_reverse->GetLnPDF(orig_params);
	double log_prob_forward_move = dir_forward->GetLnPDF(new_params);
    double log_hastings_ratio = log_prob_reverse_move - log_prob_forward_move;
	return log_hastings_ratio;
	}

/*--------------------------------------------------------------------------------------------------------------------------
|	This move does not change the model dimension, so the Jacobian is irrelevant.
*/
double DirichletMove::getLnJacobian() const
	{
	return 0.0;
	}

/*--------------------------------------------------------------------------------------------------------------------------
|	Called if the proposed move is accepted. Simply calls the reset() function.
*/
void DirichletMove::accept()
	{
	MCMCUpdater::accept();
	reset();
	}

/*--------------------------------------------------------------------------------------------------------------------------
|	Called if the proposed move is rejected. Calls the reset() function after reinstating the original state frequencies
|   and ensuring that all conditional likelihood arrays will be recalculated when the likelihood is next calculated.
*/
void DirichletMove::revert()
	{
	MCMCUpdater::revert();
    setParams(orig_params);

	ChainManagerShPtr p = chain_mgr.lock();
	PHYCAS_ASSERT(p);
    JointPriorManagerShPtr jpm = p->getJointPriorManager();
    jpm->multivariateModified(name, orig_params);
    curr_ln_prior = jpm->getLogJointPrior();

    // invalidate all CLAs
    likelihood->useAsLikelihoodRoot(NULL);
    likelihood->storeAllCLAs(tree);

	reset();
	}

/*----------------------------------------------------------------------------------------------------------------------
|	Calls proposeNewState(), then decides whether to accept or reject the proposed new state, calling accept() or
|	revert(), whichever is appropriate.
*/
bool DirichletMove::update()
	{
	if (is_fixed)
		return false;

	ChainManagerShPtr p = chain_mgr.lock();
	PHYCAS_ASSERT(p);
    JointPriorManagerShPtr jpm = p->getJointPriorManager();

	proposeNewState();

	double prev_ln_like = p->getLastLnLike();
    double prev_ln_prior = jpm->getLogJointPrior();
	PHYCAS_ASSERT(!use_ref_dist || mv_ref_dist);
	double prev_ln_ref_dist = (use_ref_dist ? mv_ref_dist->GetLnPDF(orig_params) : 0.0);

    // replace current parameter values with new ones
    setParams(new_params);
    likelihood->useAsLikelihoodRoot(NULL);	// invalidates all CLAs

    jpm->multivariateModified(name, new_params);
    curr_ln_prior = jpm->getLogJointPrior();

	double curr_ln_like = (heating_power > 0.0 ? likelihood->calcLnL(tree) : 0.0);
	double curr_ln_ref_dist = (use_ref_dist ? mv_ref_dist->GetLnPDF(new_params) : 0.0);

    double prev_posterior = 0.0;
	double curr_posterior = 0.0;

	if (is_standard_heating)
		{
		prev_posterior = heating_power*(prev_ln_like + prev_ln_prior);
		curr_posterior = heating_power*(curr_ln_like + curr_ln_prior);
		if (use_ref_dist)
			{
			prev_posterior += (1.0 - heating_power)*prev_ln_ref_dist;
			curr_posterior += (1.0 - heating_power)*curr_ln_ref_dist;
			}
		}
	else
		{
		prev_posterior = heating_power*prev_ln_like + prev_ln_prior;
		curr_posterior = heating_power*curr_ln_like + curr_ln_prior;
		}

	double ln_hastings			= getLnHastingsRatio();
	double ln_accept_ratio		= curr_posterior - prev_posterior + ln_hastings;

    double lnu = std::log(rng->Uniform());

    bool accepted = false;

	if (ln_accept_ratio >= 0.0 || lnu <= ln_accept_ratio)
		{
	    if (save_debug_info)
    	    {
			debug_info = boost::str(boost::format("ACCEPT, prev_ln_ref_dist = %.5f, curr_ln_ref_dist = %.5f, prev_ln_prior = %.5f, curr_ln_prior = %.5f, prev_ln_like = %.5f, curr_ln_like = %.5f, lnu = %.5f, ln_accept_ratio = %.5f\norig_params: ") % prev_ln_ref_dist % curr_ln_ref_dist % prev_ln_prior % curr_ln_prior % prev_ln_like % curr_ln_like % lnu % ln_accept_ratio);
			for (std::vector<double>::const_iterator it = orig_params.begin(); it != orig_params.end(); ++it)
				debug_info += boost::str(boost::format("%15.8f ") % (*it));
			debug_info += "\nnew_params:  ";
			for (std::vector<double>::const_iterator it = new_params.begin(); it != new_params.end(); ++it)
				debug_info += boost::str(boost::format("%15.8f ") % (*it));
			debug_info += "\nc_forward:  ";
			for (std::vector<double>::const_iterator it = c_forward.begin(); it != c_forward.end(); ++it)
				debug_info += boost::str(boost::format("%15.8f ") % (*it));
			debug_info += "\ndir_forward:  ";
			debug_info += dir_forward->GetDistributionDescription();
			}
		p->setLastLnLike(curr_ln_like);

		accept();
		accepted = true;
		}
	else
		{
	    if (save_debug_info)
    	    {
			debug_info = boost::str(boost::format("REJECT, prev_ln_ref_dist = %.5f, curr_ln_ref_dist = %.5f, prev_ln_prior = %.5f, curr_ln_prior = %.5f, prev_ln_like = %.5f, curr_ln_like = %.5f, lnu = %.5f, ln_accept_ratio = %.5f\norig_params: ") % prev_ln_ref_dist % curr_ln_ref_dist % prev_ln_prior % curr_ln_prior % prev_ln_like % curr_ln_like % lnu % ln_accept_ratio);
			for (std::vector<double>::const_iterator it = orig_params.begin(); it != orig_params.end(); ++it)
				debug_info += boost::str(boost::format("%15.8f ") % (*it));
			debug_info += "\nnew_params:  ";
			for (std::vector<double>::const_iterator it = new_params.begin(); it != new_params.end(); ++it)
				debug_info += boost::str(boost::format("%15.8f ") % (*it));
			debug_info += "\nc_forward:  ";
			for (std::vector<double>::const_iterator it = c_forward.begin(); it != c_forward.end(); ++it)
				debug_info += boost::str(boost::format("%15.8f ") % (*it));
			debug_info += "\ndir_forward:  ";
			debug_info += dir_forward->GetDistributionDescription();
			}
		curr_ln_like	= p->getLastLnLike();

		revert();
		accepted = false;
		}

    double inverse_psi = 1.0/psi;
    inverse_psi = p->adaptUpdater(inverse_psi, nattempts, accepted);
    psi = 1.0/inverse_psi;

    return accepted;
	}

/*----------------------------------------------------------------------------------------------------------------------
|	This base class version simply returns an empty vector. Override this function in derived classes to return a vector
|	of parameter values.
*/
double_vect_t DirichletMove::listCurrValuesFromModel()
	{
	double_vect_t v;
	return v;
	}

max_stars_repo_name: plewis/phycas

max_issues_repo_name: plewis/phycas

max_forks_repo_name: plewis/phycas


text:
/*
 * Copyright 2010 Vicente J. Botet Escriba
 * Copyright 2015 Andrey Semashev
 *
 * Distributed under the Boost Software License, Version 1.0.
 * See http://www.boost.org/LICENSE_1_0.txt
 */

#ifndef BOOST_WINAPI_LOCAL_MEMORY_HPP_INCLUDED_
#define BOOST_WINAPI_LOCAL_MEMORY_HPP_INCLUDED_

#include <boost/winapi/basic_types.hpp>

#ifdef BOOST_HAS_PRAGMA_ONCE
#pragma once
#endif

#if BOOST_WINAPI_PARTITION_APP_SYSTEM

#if !defined( BOOST_USE_WINDOWS_H )
namespace boost { namespace winapi {
typedef HANDLE_ HLOCAL_;
}}

extern "C" {
BOOST_SYMBOL_IMPORT boost::winapi::HLOCAL_ BOOST_WINAPI_WINAPI_CC
LocalAlloc(
    boost::winapi::UINT_ uFlags,
    boost::winapi::SIZE_T_ uBytes);

BOOST_SYMBOL_IMPORT boost::winapi::HLOCAL_ BOOST_WINAPI_WINAPI_CC
LocalReAlloc(
    boost::winapi::HLOCAL_ hMem,
    boost::winapi::SIZE_T_ uBytes,
    boost::winapi::UINT_ uFlags);

BOOST_SYMBOL_IMPORT boost::winapi::HLOCAL_ BOOST_WINAPI_WINAPI_CC LocalFree(boost::winapi::HLOCAL_ hMem);
} // extern "C"
#endif

namespace boost {
namespace winapi {
#if defined( BOOST_USE_WINDOWS_H )
typedef ::HLOCAL HLOCAL_;
#endif
using ::LocalAlloc;
using ::LocalReAlloc;
using ::LocalFree;
}
}

#endif // BOOST_WINAPI_PARTITION_APP_SYSTEM
#endif // BOOST_WINAPI_LOCAL_MEMORY_HPP_INCLUDED_


text:
/*
 * Copyright 2012-2019 CNRS-UM LIRMM, CNRS-AIST JRL
 */

// includes
// std
#include <iostream>

// boost
#define BOOST_TEST_MODULE IDIMTest
#include <boost/test/unit_test.hpp>

// SpaceVecAlg
#include <SpaceVecAlg/SpaceVecAlg>

// RBDyn
#include "RBDyn/FK.h"
#include "RBDyn/FV.h"
#include "RBDyn/ID.h"
#include "RBDyn/IDIM.h"

// arm
#include "Tree30Dof.h"

sva::RBInertiad randomInertia()
{
  Eigen::Matrix<double, 10, 1> v(Eigen::Matrix<double, 10, 1>::Random());
  v(0) = std::abs(v(0)) + 0.001; // positive mass
  v.tail<6>() = v.tail<6>().array().abs(); // positive inertia
  return rbd::vectorToInertia(v);
}

BOOST_AUTO_TEST_CASE(toFrom10Vec)
{
  using namespace Eigen;
  using namespace sva;
  using namespace rbd;

  double mass = 11.11;
  Matrix3d I;
  I << 1., 2., 3., 2., 10., 4., 3., 4., 12.;
  Vector3d h = Vector3d::Random() * 100.;

  RBInertiad rbi(mass, h, I);
  auto vec10d = inertiaToVector(rbi);
  RBInertiad rbi2 = vectorToInertia(vec10d);

  BOOST_CHECK_EQUAL(rbi, rbi2);
}

BOOST_AUTO_TEST_CASE(IMPhiTest)
{
  using namespace Eigen;
  using namespace sva;
  using namespace rbd;

  // test that Im = IMPhi(m)*phi_i
  for(int i = 0; i < 100; ++i)
  {
    RBInertiad rbi(randomInertia());
    MotionVecd m(Vector6d::Random());

    ForceVecd res1 = rbi * m;
    ForceVecd res2(IMPhi(m) * inertiaToVector(rbi));

    BOOST_CHECK_SMALL((res1 - res2).vector().norm(), 1e-8);
  }

  // test that m x^* Im = m x^* IMPhi(m)*phi_i
  for(int i = 0; i < 100; ++i)
  {
    RBInertiad rbi(randomInertia());
    MotionVecd m(Vector6d::Random());

    ForceVecd res1 = m.crossDual(rbi * m);
    ForceVecd res2((vector6ToCrossDualMatrix(m.vector()) * IMPhi(m)) * inertiaToVector(rbi));

    BOOST_CHECK_SMALL((res1 - res2).vector().norm(), 1e-8);
  }
}

BOOST_AUTO_TEST_CASE(computeY)
{
  using namespace Eigen;
  using namespace sva;
  using namespace rbd;

  MultiBody mb;
  MultiBodyConfig mbc;
  MultiBodyGraph mbg;
  std::tie(mb, mbc, mbg) = makeTree30Dof(false);

  // first we initialize all the inertia of our multibody with random data
  std::vector<Body> oldB(mb.bodies());
  std::vector<Body> newB;
  newB.reserve(oldB.size());
  for(const Body & b : mb.bodies())
  {
    newB.push_back(Body(randomInertia(), b.name()));
  }
  mb = MultiBody(newB, mb.joints(), mb.predecessors(), mb.successors(), mb.parents(), mb.transforms());

  VectorXd inertiaVec(multiBodyToInertialVector(mb));
  VectorXd idimTorque(mb.nrDof());
  VectorXd idTorque(mb.nrDof());

  InverseDynamics id(mb);
  IDIM idim(mb);

  for(int i = 0; i < 50; ++i)
  {
    VectorXd q(VectorXd::Random(mb.nrParams()) * 4.);
    VectorXd alpha(VectorXd::Random(mb.nrDof()));
    VectorXd alphaD(VectorXd::Random(mb.nrDof()));
    vectorToParam(q, mbc.q);
    vectorToParam(alpha, mbc.alpha);
    vectorToParam(alphaD, mbc.alphaD);

    forwardKinematics(mb, mbc);
    forwardVelocity(mb, mbc);

    id.inverseDynamics(mb, mbc);
    idim.sComputeY(mb, mbc);

    paramToVector(mbc.jointTorque, idTorque);
    idimTorque = idim.Y() * inertiaVec;

    BOOST_CHECK_SMALL((idTorque - idimTorque).norm(), 1e-8);
  }
}

max_stars_repo_name: mmurooka/RBDyn

max_issues_repo_name: mmurooka/RBDyn

max_forks_repo_name: mmurooka/RBDyn


text:
//---------------------------------------------------------------------------//
// Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.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
//
// See http://boostorg.github.com/compute for more information.
//---------------------------------------------------------------------------//

#ifndef BOOST_COMPUTE_ALGORITHM_DETAIL_COPY_ON_DEVICE_HPP
#define BOOST_COMPUTE_ALGORITHM_DETAIL_COPY_ON_DEVICE_HPP

#include <iterator>

#include <boost/compute/command_queue.hpp>
#include <boost/compute/async/future.hpp>
#include <boost/compute/iterator/buffer_iterator.hpp>
#include <boost/compute/iterator/discard_iterator.hpp>
#include <boost/compute/memory/svm_ptr.hpp>
#include <boost/compute/detail/iterator_range_size.hpp>
#include <boost/compute/detail/meta_kernel.hpp>
#include <boost/compute/detail/parameter_cache.hpp>
#include <boost/compute/detail/work_size.hpp>

namespace boost {
namespace compute {
namespace detail {

inline size_t pick_copy_work_group_size(size_t n, const device &device)
{
    (void) device;

    if(n % 32 == 0) return 32;
    else if(n % 16 == 0) return 16;
    else if(n % 8 == 0) return 8;
    else if(n % 4 == 0) return 4;
    else if(n % 2 == 0) return 2;
    else return 1;
}

template<class InputIterator, class OutputIterator>
class copy_kernel : public meta_kernel
{
public:
    copy_kernel(const device &device)
        : meta_kernel("copy")
    {
        m_count = 0;

        typedef typename std::iterator_traits<InputIterator>::value_type input_type;

        boost::shared_ptr<parameter_cache> parameters =
            detail::parameter_cache::get_global_cache(device);

        std::string cache_key =
            "__boost_copy_kernel_" + boost::lexical_cast<std::string>(sizeof(input_type));

        m_vpt = parameters->get(cache_key, "vpt", 4);
        m_tpb = parameters->get(cache_key, "tpb", 128);
    }

    void set_range(InputIterator first,
                   InputIterator last,
                   OutputIterator result)
    {
        m_count_arg = add_arg<uint_>("count");

        *this <<
            "uint index = get_local_id(0) + " <<
               "(" << m_vpt * m_tpb << " * get_group_id(0));\n" <<
            "for(uint i = 0; i < " << m_vpt << "; i++){\n" <<
            "    if(index < count){\n" <<
                     result[expr<uint_>("index")] << '=' <<
                         first[expr<uint_>("index")] << ";\n" <<
            "        index += " << m_tpb << ";\n"
            "    }\n"
            "}\n";

        m_count = detail::iterator_range_size(first, last);
    }

    event exec(command_queue &queue)
    {
        if(m_count == 0){
            // nothing to do
            return event();
        }

        size_t global_work_size = calculate_work_size(m_count, m_vpt, m_tpb);

        set_arg(m_count_arg, uint_(m_count));

        return exec_1d(queue, 0, global_work_size, m_tpb);
    }

private:
    size_t m_count;
    size_t m_count_arg;
    uint_ m_vpt;
    uint_ m_tpb;
};

template<class InputIterator, class OutputIterator>
inline OutputIterator copy_on_device(InputIterator first,
                                     InputIterator last,
                                     OutputIterator result,
                                     command_queue &queue)
{
    const device &device = queue.get_device();

    copy_kernel<InputIterator, OutputIterator> kernel(device);

    kernel.set_range(first, last, result);
    kernel.exec(queue);

    return result + std::distance(first, last);
}

template<class InputIterator>
inline discard_iterator copy_on_device(InputIterator first,
                                       InputIterator last,
                                       discard_iterator result,
                                       command_queue &queue)
{
    (void) queue;

    return result + std::distance(first, last);
}

template<class InputIterator, class OutputIterator>
inline future<OutputIterator> copy_on_device_async(InputIterator first,
                                                   InputIterator last,
                                                   OutputIterator result,
                                                   command_queue &queue)
{
    const device &device = queue.get_device();

    copy_kernel<InputIterator, OutputIterator> kernel(device);

    kernel.set_range(first, last, result);
    event event_ = kernel.exec(queue);

    return make_future(result + std::distance(first, last), event_);
}

#ifdef CL_VERSION_2_0
// copy_on_device() specialization for svm_ptr
template<class T>
inline svm_ptr<T> copy_on_device(svm_ptr<T> first,
                                 svm_ptr<T> last,
                                 svm_ptr<T> result,
                                 command_queue &queue)
{
    size_t count = iterator_range_size(first, last);
    if(count == 0){
        return result;
    }

    queue.enqueue_svm_memcpy(
        result.get(), first.get(), count * sizeof(T)
    );

    return result + count;
}

template<class T>
inline future<svm_ptr<T> > copy_on_device_async(svm_ptr<T> first,
                                                svm_ptr<T> last,
                                                svm_ptr<T> result,
                                                command_queue &queue)
{
    size_t count = iterator_range_size(first, last);
    if(count == 0){
        return result;
    }

    event event_ = queue.enqueue_svm_memcpy_async(
        result.get(), first.get(), count * sizeof(T)
    );

    return make_future(result + count, event_);
}
#endif // CL_VERSION_2_0

} // end detail namespace
} // end compute namespace
} // end boost namespace

#endif // BOOST_COMPUTE_ALGORITHM_DETAIL_COPY_ON_DEVICE_HPP

max_stars_repo_name: mistydew/RSSearch

max_issues_repo_name: mistydew/RSSearch

max_forks_repo_name: mistydew/RSSearch


text:
#include "compiler/function_manager.hpp"

#include <boost/test/unit_test.hpp>

using namespace perseus::detail;

typedef function_manager::function_pointer iterator;

BOOST_AUTO_TEST_SUITE( compiler )

BOOST_AUTO_TEST_SUITE( function_manager_tests )

using namespace std::string_literals;

BOOST_AUTO_TEST_CASE( register_functions )
{
  using namespace perseus::detail;
  function_manager man;
  {
    iterator add;
    BOOST_REQUIRE( man.register_function( function_signature{ "add"s, { type_id::i32, type_id::i32 } }, function_info{ type_id::i32 }, add ) );

    iterator subtract;
    BOOST_REQUIRE( man.register_function( function_signature{ "subtract"s,{ type_id::i32, type_id::i32 } }, function_info{ type_id::i32 }, subtract ) );

    BOOST_CHECK_EQUAL( add->first.name, "add"s );
    BOOST_CHECK_EQUAL( subtract->first.name, "subtract"s );
  }
}

BOOST_AUTO_TEST_CASE( functions_lookup )
{
  function_manager man;
  {
    function_signature add_signature{ "add"s,{ type_id::i32, type_id::i32 } };
    iterator add;
    BOOST_REQUIRE( man.register_function( function_signature{ add_signature }, function_info{ type_id::i32 }, add ) );

    iterator subtract;
    BOOST_REQUIRE( man.register_function( function_signature{ "subtract"s,{ type_id::i32, type_id::i32 } }, function_info{ type_id::i32 }, subtract ) );

    iterator found_add;
    BOOST_REQUIRE( man.get_function( add_signature, found_add ) );
    BOOST_CHECK_EQUAL( found_add->first.name, "add"s );
  }
}

BOOST_AUTO_TEST_SUITE_END()

BOOST_AUTO_TEST_SUITE_END()

max_stars_repo_name: mrwonko/perseus

max_issues_repo_name: mrwonko/perseus

max_forks_repo_name: mrwonko/perseus


text:
#include <boost/functional/hash.hpp>
#include "common/token.h"
#include "common/time.h"
#include "common/type.h"

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>

using namespace std;

double THRESHOLD;
long long cand_num;
long long res_num;

base_helper *helper;

namespace pattern
{
	int *seg_parts;
	int **seg_part_len;
	int **seg_part_pos;

	struct sub_match
	{
		int match_len;
		int match_part;
		int start_pos;
		int part_len;
	};

	vector<sub_match> *sub_matches;
	HashMap<size_t, vector<int>> **indexes;

	void init(int max_length)
	{
		seg_parts = new int[max_length + 1];
		seg_part_len = new int*[max_length + 1];
		seg_part_pos = new int*[max_length + 1];
		indexes = new HashMap<size_t, vector<int>>*[max_length + 1];
		for (int len = 1; len <= max_length; len++)
		{
			int to_match_len = helper->max_possible_length(len);
			seg_parts[len] = len + to_match_len - 2 * helper->require_overlap(len, to_match_len) + 1 + 1e-6;

			int part = seg_parts[len];
			indexes[len] = new HashMap<size_t, vector<int>>[part];
			seg_part_pos[len] = new int[part + 1];
			seg_part_len[len] = new int[part];

			int larger_num = len - len / part * part;
			for (int k = 0; k < part - larger_num; k++)
			{
				seg_part_len[len][k] = len / part;
			}
			for (int k = part - larger_num; k < part; k++)
			{
				seg_part_len[len][k] = len / part + 1;
			}

			seg_part_pos[len][0] = 0;
			for (int k = 1; k <= part; k++)
			{
				seg_part_pos[len][k] = seg_part_pos[len][k - 1] + seg_part_len[len][k - 1];
			}

			assert(seg_part_pos[len][part] == len);
		}

		sub_matches = new vector<sub_match>[max_length + 1];
		for (int len = 1; len <= max_length; len++)
		{
			for (int match_len = len; match_len <= min(helper->max_possible_length(len), max_length); match_len++)
			{
				int overlap = helper->require_overlap(len, match_len);
				int hr = match_len - overlap;
				int hs = len - overlap;

				for (int part = 0; part < seg_parts[match_len]; part++)
				{
					int p = seg_part_pos[match_len][part];
					int l = seg_part_len[match_len][part];

					int low = max(0, max(p - hr, p - part));
					int high = min(len - l, min(p + hs, p + len - match_len + seg_parts[match_len] - part - 1));
					for (int s = low; s <= high; s++)
					{
						sub_matches[len].push_back(sub_match());
						sub_match &last = sub_matches[len].back();
						last.match_len = match_len;
						last.match_part = part;
						last.start_pos = s;
						last.part_len = l;
					}
				}
			}
		}
	}
};

bool verify(vector<int> &a, vector<int> &b, double threshold)
{
	int posa = 0, posb = 0, count = 0;
	int overlap = helper->require_overlap(a.size(), b.size());

	while (posa < (int)a.size() && posb < (int)b.size())
	{
		if (count + min((int)a.size() - posa, (int)b.size() - posb) < overlap)
			return false;
		if (a[posa] == b[posb])
		{
			count++;
			posa++;
			posb++;
		} else if (a[posa] < b[posb])
		{
			posa++;
		} else {
			posb++;
		}
	}

	return helper->calc_similarity(a.size(), b.size(), count) >= threshold;
}

void join(vector<vector<int>> &token)
{
	bool *checked_flag = new bool[token.size()];
	for (int id = 0; id < (int)token.size(); id++)
	{
		int len = token[id].size();
		int part = pattern::seg_parts[len];

		memset(checked_flag, 0, id);
		for (pattern::sub_match &match : pattern::sub_matches[len])
		{
			int hash_value = boost::hash_range(token[id].begin() + match.start_pos, token[id].begin() + match.start_pos + match.part_len);
			auto &potential_candidates = pattern::indexes[match.match_len][match.match_part];
			if (potential_candidates.count(hash_value))
			{
				vector<int> &candidate = potential_candidates[hash_value];
				for (int cand_id : candidate)
				{
					if (!checked_flag[cand_id])
					{
						cand_num++;
						checked_flag[cand_id] = true;
						if (verify(token[id], token[cand_id], THRESHOLD))
						{
							res_num++;
						}
					}
				}
			}
		}

		for (int k = 0; k < part; k++)
		{
			int hash_value = boost::hash_range(token[id].begin() + pattern::seg_part_pos[len][k], token[id].begin() + pattern::seg_part_pos[len][k + 1]);
			pattern::indexes[len][k][hash_value].push_back(id);
		}
	}
	delete[] checked_flag;
}

int main(int argc, char **argv)
{
	if (argc != 4) return -1;
	log_start();

	FILE *in = fopen(argv[2], "r");
	THRESHOLD = atof(argv[3]);

	if (argv[1][0] == 'j')
	{
		helper = new jaccard_helper();
	} else if (argv[1][0] == 'c')
	{
		helper = new cosine_helper();
	} else if (argv[1][0] == 'd')
	{
		helper = new dice_helper();
	} else {
		return -1;
	}

	int count;
	vector<vector<int>> token;
	while (fread(&count, sizeof(int), 1, in))
	{
		fread(&count, sizeof(int), 1, in);
		token.push_back(vector<int>(count));
		fread(token.back().data(), sizeof(int), count, in);
	}

	fclose(in);

	reverse(token.begin(), token.end());

	assert(token.size() != 0);
	pattern::init(token.front().size());

	join(token);

	cout << res_num << endl;
	cout << cand_num << endl;

	return 0;
}

max_issues_repo_name: TsinghuaDatabaseGroup/similarity

max_forks_repo_name: TsinghuaDatabaseGroup/similarity


text:
/*
 * Copyright 2013 Open Source Robotics Foundation
 *
 * 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.
 *
*/

#ifndef _JOINTMAKER_HH_
#define _JOINTMAKER_HH_

#include <string>
#include <vector>
#include <boost/unordered/unordered_map.hpp>

#include <sdf/sdf.hh>

#include "gazebo/common/MouseEvent.hh"
#include "gazebo/common/CommonTypes.hh"
#include "gazebo/math/Vector3.hh"
#include "gazebo/rendering/RenderTypes.hh"
#include "gazebo/gui/qt.h"
#include "gazebo/util/system.hh"

namespace gazebo
{
  namespace gui
  {
    class JointData;
    class JointInspector;

    /// \addtogroup gazebo_gui
    /// \{

    /// \class JointMaker JointMaker.hh
    /// \brief Joint visualization
    class GAZEBO_VISIBLE JointMaker : public QObject
    {
      Q_OBJECT

      /// \enum Joint types
      /// \brief Unique identifiers for joint types that can be created.
      public: enum JointType
      {
        /// \brief none
        JOINT_NONE,
        /// \brief Fixed joint
        JOINT_FIXED,
        /// \brief Slider joint
        JOINT_SLIDER,
        /// \brief Hinge joint
        JOINT_HINGE,
        /// \brief Hinge2 joint
        JOINT_HINGE2,
        /// \brief Screw joint
        JOINT_SCREW,
        /// \brief Universal joint
        JOINT_UNIVERSAL,
        /// \brief Revolute joint
        JOINT_BALL
      };

      /// \brief Constructor
      public: JointMaker();

      /// \brief Destructor
      public: virtual ~JointMaker();

      /// \brief Reset the joint maker;
      public: void Reset();

      /// \brief Create a joint
      /// \param[_type] Type of joint to be created
      public: void CreateJoint(JointType _type);

      /// \brief Update callback on PreRender.
      public: void Update();

      /// \brief Remove joint by name
      /// \param[in] _jointName Name of joint to be removed.
      public: void RemoveJoint(const std::string &_jointName);

      /// \brief Remove all joints connected to part
      /// \param[in] _partName Name of joint to be removed.
      public: void RemoveJointsByPart(const std::string &_partName);

      /// \brief Generate SDF for all joints.
      public: void GenerateSDF();

      /// \brief Generate SDF for all joints.
      public: sdf::ElementPtr GetSDF() const;

      /// \brief Get the axis count for joint type.
      /// \param[in] _type Type of joint.
      public: static int GetJointAxisCount(JointMaker::JointType _type);

      /// \brief Get the joint type in string.
      /// \param[in] _type Type of joint.
      /// \return Joint type in string.
      public: static std::string GetTypeAsString(JointMaker::JointType _type);

      /// \brief Get state
      /// \return State of JointType if joint creation is in process, otherwise
      /// JOINT_NONE
      public: JointMaker::JointType GetState() const;

      /// \brief Stop the process of adding joint to the model.
      public: void Stop();

      /// \brief Mouse event filter callback when mouse button is pressed.
      /// \param[in] _event The mouse event.
      /// \return True if the event was handled
      private: bool OnMousePress(const common::MouseEvent &_event);

      /// \brief Mouse event filter callback when mouse button is released.
      /// \param[in] _event The mouse event.
      /// \return True if the event was handled
      private: bool OnMouseRelease(const common::MouseEvent &_event);

      /// \brief Mouse event filter callback when mouse is moved.
      /// \param[in] _event The mouse event.
      /// \return True if the event was handled
      private: bool OnMouseMove(const common::MouseEvent &_event);

      /// \brief Mouse event filter callback when mouse is double clicked.
      /// \param[in] _event The mouse event.
      /// \return True if the event was handled
      private: bool OnMouseDoubleClick(const common::MouseEvent &_event);

      /// \brief Helper method to create hotspot visual for mouse interaction.
      private: void CreateHotSpot();

      /// \brief Open joint inspector.
      /// \param[in] _name Name of joint.
      private: void OpenInspector(const std::string &_name);

      /// \brief Qt signal when the joint creation process has ended.
      Q_SIGNALS: void JointAdded();

      /// \brief Qt Callback to open joint inspector
      private slots: void OnOpenInspector();

      /// \brief Type of joint to create
      private: JointMaker::JointType jointType;

      /// \brief Visual that is currently hovered over by the mouse
      private: rendering::VisualPtr hoverVis;

      /// \brief Visual that is previously hovered over by the mouse
      private: rendering::VisualPtr prevHoverVis;

      /// \brief Currently selected visual
      private: rendering::VisualPtr selectedVis;

      /// \brief Visual that is currently being inspected.
      private: rendering::VisualPtr inspectVis;

      /// \brief All joints created by joint maker.
      private: boost::unordered_map<std::string, JointData *> joints;

      /// \brief Joint currently being created.
      private: JointData *mouseJoint;

      /// \brief All the event connections.
      private: std::vector<event::ConnectionPtr> connections;

      /// \brief Flag set to true when a joint has been connected.
      private: bool newJointCreated;

      /// \brief A map of joint type to its corresponding material.
      private: boost::unordered_map<JointMaker::JointType, std::string>
          jointMaterials;

      /// \brief The SDF element pointer to the model that contains the joints.
      private: sdf::ElementPtr modelSDF;

      /// \brief Counter for the number of joints in the model.
      private: int jointCounter;

      /// \brief Qt action for opening the joint inspector.
      private: QAction *inspectAct;
    };
    /// \}

    /// \class JointData JointData.hh
    /// \brief Helper class to store joint data
    class GAZEBO_VISIBLE JointData : public QObject
    {
      Q_OBJECT

      /// \brief Visual of the dynamic line
      public: rendering::VisualPtr visual;

      /// \brieft Visual of the hotspot
      public: rendering::VisualPtr hotspot;

      /// \brief Parent visual the joint is connected to.
      public: rendering::VisualPtr parent;

      /// \brief Child visual the joint is connected to.
      public: rendering::VisualPtr child;

      /// \brief Visual line used to represent joint connecting parent and child
      public: rendering::DynamicLines *line;

      /// \brief Type of joint.
      public: JointMaker::JointType type;

      /// \brief Joint axis direction.
      public: math::Vector3 axis[2];

      /// \brief Joint lower limit.
      public: double lowerLimit[2];

      /// \brief Joint upper limit.
      public: double upperLimit[2];

      /// \brief Joint anchor point.
      public: math::Vector3 anchor;

      /// \brief True if the joint visual needs update.
      public: bool dirty;

      /// \brief Inspector for configuring joint properties.
      public: JointInspector *inspector;

      /// \brief Qt Callback when joint inspector configurations are to be
      /// applied.
      private slots: void OnApply();
    };
    /// \}
  }
}
#endif

ext: hh

max_stars_repo_name: hyunoklee/Gazebo

max_issues_repo_name: hyunoklee/Gazebo

max_forks_repo_name: hyunoklee/Gazebo


text:
#define GRB_USE_SEQUENTIAL

#include <vector>
#include <iostream>
#include <string>
#include <numeric>
#include <algorithm>
#include <map>

#include <cstdio>
#include <cstdlib>

#include "graphblas/graphblas.hpp"
#include "test/test.hpp"

#define BOOST_TEST_MAIN
#define BOOST_TEST_MODULE dup_suite

#include <boost/test/included/unit_test.hpp>
#include <boost/program_options.hpp>

void testCountUnique( std::vector<int>& array, const int correct )
{
  int count = countUnique( array );
  //std::cout << count << "=" << correct << std::endl;
  BOOST_ASSERT( count==correct );
}

BOOST_AUTO_TEST_SUITE( util_suite )

BOOST_AUTO_TEST_CASE( util1 )
{
  std::vector<int> adj_deg   = {1, 1, 3, 2, 2, 3, 3};
  testCountUnique( adj_deg, 3 );
}

BOOST_AUTO_TEST_CASE( util2 )
{
  std::vector<int> adj_t_deg = {3, 3, 3, 2, 3, 1, 0};
  testCountUnique( adj_t_deg, 4 );
}

BOOST_AUTO_TEST_CASE( util3 )
{
  std::vector<int> adj_deg   = {4, 3, 3, 1, 1, 2, 4, 4, 1, 3};
  testCountUnique( adj_deg, 4 );
}

BOOST_AUTO_TEST_CASE( util4 )
{
  std::vector<int> adj_t_deg = {4, 4, 2, 1, 2, 1, 3, 3, 4, 1};
  testCountUnique( adj_t_deg, 4 );
}

BOOST_AUTO_TEST_CASE( util5 )
{
  std::vector<int> correct_ind = {1, 2, 3, 4, 5, 6};
  testCountUnique( correct_ind, 6 );
}

BOOST_AUTO_TEST_CASE( util6 )
{
  std::vector<int> correct_val = {1, 1, 1, 2, 2, 1};
  testCountUnique( correct_val, 2 );
}

BOOST_AUTO_TEST_CASE( util7 )
{
  std::vector<int> correct_ind = {1, 2, 3, 4, 5, 6, 7, 8};
  testCountUnique( correct_ind, 8 );
}

BOOST_AUTO_TEST_CASE( util8 )
{
  std::vector<int> correct_val = {1, 1, 1, 2, 2, 1, 1, 10};
  testCountUnique( correct_val, 3 );
}

/*BOOST_FIXTURE_TEST_CASE( dup12, TestMatrix )
{
  std::map<graphblas::Index,graphblas::Index> out_edge;
  out_edge.insert({{2, 1}, {3, 0}, {4,1}});
  std::vector<graphblas::Index> correct = {1, 2, 3, 0, 2, 4, 3, 4, -1, 5, 6, 2, 6, -1, 6, 8, 9, 10, 9, 10};
  testEwiseSubCol( "data/small/test_cc.tsv", out_edge, correct);
}

BOOST_FIXTURE_TEST_CASE( dup18, TestMatrix )
{
  std::map<graphblas::Index,graphblas::Index> out_edge;
  out_edge.insert( {{1,1}, {2,0}, {4,1}, {5,2}, {6,1}, {7,1}, {8,10}} );
  std::vector<graphblas::Index> correct_ind = {1, 2, 3, 0, 2, 4, 5, 3, 4, 5, 5, 6, 2, 5, 6, 5, 6, 5, 5, 8, 9, 10, 5, 9, 10 };
  std::vector<graphblas::T>     correct_val = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 10, 1, 1 };
  testEwiseAddCol( "data/small/test_cc.tsv", out_edge, correct_ind, correct_val);
}*/

BOOST_AUTO_TEST_SUITE_END()

max_stars_repo_name: BenBrock/graphblast

max_issues_repo_name: BenBrock/graphblast

max_forks_repo_name: BenBrock/graphblast


text:
//---------------------------------------------------------------------------//
// Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.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
//
// See http://boostorg.github.com/compute for more information.
//---------------------------------------------------------------------------//

#define BOOST_TEST_MODULE TestAccumulate
#include <boost/test/unit_test.hpp>

#include <numeric>

#include <boost/compute/command_queue.hpp>
#include <boost/compute/algorithm/accumulate.hpp>
#include <boost/compute/algorithm/iota.hpp>
#include <boost/compute/container/mapped_view.hpp>
#include <boost/compute/container/vector.hpp>
#include <boost/compute/iterator/counting_iterator.hpp>

#include "context_setup.hpp"

BOOST_AUTO_TEST_CASE(sum_int)
{
    int data[] = { 2, 4, 6, 8 };
    boost::compute::vector<int> vector(data, data + 4, queue);
    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(vector.begin(), vector.end(), 0, queue),
        20
    );

    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(vector.begin(), vector.end(), -10, queue),
        10
    );

    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(vector.begin(), vector.end(), 5, queue),
        25
    );
}

BOOST_AUTO_TEST_CASE(product_int)
{
    int data[] = { 2, 4, 6, 8 };
    boost::compute::vector<int> vector(data, data + 4);
    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(
            vector.begin(), vector.end(), 1, boost::compute::multiplies<int>()),
        384
    );

    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(
            vector.begin(), vector.end(), -1, boost::compute::multiplies<int>()),
        -384
    );

    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(
            vector.begin(), vector.end(), 2, boost::compute::multiplies<int>()),
        768
    );
}

BOOST_AUTO_TEST_CASE(quotient_int)
{
    int data[] = { 2, 8, 16 };
    boost::compute::vector<int> vector(data, data + 3, queue);
    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(
            vector.begin(),
            vector.end(),
            1024,
            boost::compute::divides<int>(),
            queue
        ),
        4
    );
}

BOOST_AUTO_TEST_CASE(sum_counting_iterator)
{
    // sum 0 -> 9
    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(
            boost::compute::make_counting_iterator(0),
            boost::compute::make_counting_iterator(10),
            0,
            boost::compute::plus<int>(),
            queue
        ),
        45
    );

    // sum 0 -> 9 + 7
    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(
            boost::compute::make_counting_iterator(0),
            boost::compute::make_counting_iterator(10),
            7,
            boost::compute::plus<int>(),
            queue
        ),
        52
    );

    // sum 15 -> 24
    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(
            boost::compute::make_counting_iterator(15),
            boost::compute::make_counting_iterator(25),
            0,
            boost::compute::plus<int>(),
            queue
        ),
        195
    );

    // sum -5 -> 10
    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(
            boost::compute::make_counting_iterator(-5),
            boost::compute::make_counting_iterator(10),
            0,
            boost::compute::plus<int>(),
            queue
        ),
        30
    );

    // sum -5 -> 10 - 2
    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(
            boost::compute::make_counting_iterator(-5),
            boost::compute::make_counting_iterator(10),
            -2,
            boost::compute::plus<int>(),
            queue
        ),
        28
    );
}

BOOST_AUTO_TEST_CASE(sum_iota)
{
    // size 0
    boost::compute::vector<int> vector(0, context);

    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(vector.begin(), vector.end(), 0, queue),
        0
    );

    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(vector.begin(), vector.end(), 4, queue),
        4
    );

    // size 50
    vector.resize(50);
    boost::compute::iota(vector.begin(), vector.end(), 0, queue);

    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(vector.begin(), vector.end(), 0, queue),
        1225
    );

    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(vector.begin(), vector.end(), 11, queue),
        1236
    );

    // size 1000
    vector.resize(1000);
    boost::compute::iota(vector.begin(), vector.end(), 0, queue);

    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(vector.begin(), vector.end(), 0, queue),
        499500
    );

    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(vector.begin(), vector.end(), -45, queue),
        499455
    );

    // size 1025
    vector.resize(1025);
    boost::compute::iota(vector.begin(), vector.end(), 0, queue);

    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(vector.begin(), vector.end(), 0, queue),
        524800
    );

    BOOST_CHECK_EQUAL(
        boost::compute::accumulate(vector.begin(), vector.end(), 2, queue),
        524802
    );
}

BOOST_AUTO_TEST_CASE(min_and_max)
{
    using boost::compute::int2_;

    int data[] = { 5, 3, 1, 6, 4, 2 };
    boost::compute::vector<int> vector(data, data + 6, queue);

    BOOST_COMPUTE_FUNCTION(int2_, min_and_max, (int2_ accumulator, const int value),
    {
        return (int2)(min(accumulator.x, value), max(accumulator.y, value));
    });

    int2_ result = boost::compute::accumulate(
        vector.begin(), vector.end(), int2_(100, -100), min_and_max, queue
    );
    BOOST_CHECK_EQUAL(result[0], 1);
    BOOST_CHECK_EQUAL(result[1], 6);
}

BOOST_AUTO_TEST_CASE(min_max)
{
    float data[] = { 1.2f, 5.5f, 0.1f, 9.6f, 4.2f, 6.7f, 9.0f, 3.4f };
    boost::compute::vector<float> vec(data, data + 8, queue);

    using ::boost::compute::min;
    using ::boost::compute::max;

    float min_value = boost::compute::accumulate(
        vec.begin(), vec.end(), std::numeric_limits<float>::max(), min<float>(), queue
    );
    BOOST_CHECK_EQUAL(min_value, 0.1f);

    float max_value = boost::compute::accumulate(
        vec.begin(), vec.end(), std::numeric_limits<float>::min(), max<float>(), queue
    );
    BOOST_CHECK_EQUAL(max_value, 9.6f);

    // find min with init less than any value in the array
    min_value = boost::compute::accumulate(
        vec.begin(), vec.end(), -1.f, min<float>(), queue
    );
    BOOST_CHECK_EQUAL(min_value, -1.f);

    // find max with init greater than any value in the array
    max_value = boost::compute::accumulate(
        vec.begin(), vec.end(), 10.f, max<float>(), queue
    );
    BOOST_CHECK_EQUAL(max_value, 10.f);
}

template<class T>
void ensure_std_accumulate_equality(const std::vector<T> &data,
                                    boost::compute::command_queue &queue)
{
    boost::compute::mapped_view<T> view(&data[0], data.size(), queue.get_context());

    BOOST_CHECK_EQUAL(
        std::accumulate(data.begin(), data.end(), 0),
        boost::compute::accumulate(view.begin(), view.end(), 0, queue)
    );
}

BOOST_AUTO_TEST_CASE(std_accumulate_equality)
{
    // test accumulate() with int
    int data1[] = { 1, 2, 3, 4 };
    std::vector<int> vec1(data1, data1 + 4);
    ensure_std_accumulate_equality(vec1, queue);

    vec1.resize(10000);
    std::fill(vec1.begin(), vec1.end(), 2);
    ensure_std_accumulate_equality(vec1, queue);

    // test accumulate() with float
    float data2[] = { 1.2f, 2.3f, 4.5f, 6.7f, 8.9f };
    std::vector<float> vec2(data2, data2 + 5);
    ensure_std_accumulate_equality(vec2, queue);

    vec2.resize(10000);
    std::fill(vec2.begin(), vec2.end(), 1.01f);
    ensure_std_accumulate_equality(vec2, queue);

    // test accumulate() with double
    if(device.supports_extension("cl_khr_fp64")){
        double data3[] = { 1.2, 2.3, 4.5, 6.7, 8.9 };
        std::vector<double> vec3(data3, data3 + 5);
        ensure_std_accumulate_equality(vec3, queue);

        vec3.resize(10000);
        std::fill(vec3.begin(), vec3.end(), 2.02);
        ensure_std_accumulate_equality(vec3, queue);
    }
}

BOOST_AUTO_TEST_SUITE_END()


text:
#include <iostream>
#include <cassert>
#include <vector>
#include <iomanip>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> Graph;

const int debug_level = 0;

#define DEBUG(min_level, x)      \
  if (debug_level >= min_level)  \
  {                              \
    std::cerr << x << std::endl; \
  }

class DPCell
{
public:
  int set, unset_uncovered, unset_covered;
};

class DPVisitor : public boost::default_dfs_visitor
{
public:
  DPVisitor(std::vector<DPCell> &dp_table, const std::vector<int> &costs_by_city) : dp_table(dp_table), costs_by_city(costs_by_city) {}

  void finish_vertex(int vertex, const Graph &G)
  {
    int cheapest_set_child = -1, cheapest_set_child_cost = std::numeric_limits<int>::max();
    for (auto it = boost::out_edges(vertex, G); it.first != it.second; it.first++)
    {
      const int i = it.first->m_target;
      const DPCell &child_cell = dp_table.at(i);
      const int cost = child_cell.set - std::min(child_cell.set, child_cell.unset_uncovered);
      if (cheapest_set_child == -1 || cheapest_set_child_cost > cost)
      {
        cheapest_set_child = i;
        cheapest_set_child_cost = cost;
      }
    }

    DPCell &parent_cell = dp_table.at(vertex);
    parent_cell.set = costs_by_city.at(vertex);
    parent_cell.unset_covered = 0;

    if (cheapest_set_child == -1)
    {
      parent_cell.unset_uncovered = std::numeric_limits<int>::max();
    }
    else
    {
      assert(cheapest_set_child >= 0);
      parent_cell.unset_uncovered = 0;
      for (auto it = boost::out_edges(vertex, G); it.first != it.second; it.first++)
      {
        const int i = it.first->m_target;
        const DPCell &child_cell = dp_table.at(i);
        parent_cell.set += std::min(child_cell.set, child_cell.unset_covered);
        parent_cell.unset_uncovered += i == cheapest_set_child ? child_cell.set : std::min(child_cell.set, child_cell.unset_uncovered);
        parent_cell.unset_covered += std::min(child_cell.set, child_cell.unset_uncovered);
      }
    }

    DEBUG(2, "finish_vertex(" << vertex << "): " << parent_cell.set << " " << parent_cell.unset_uncovered << " " << parent_cell.unset_covered);
  }

  int get_result()
  {
    const DPCell &cell = dp_table.at(0);
    DEBUG(2, "result " << cell.set << " " << cell.unset_uncovered << " " << cell.unset_covered)
    return std::min(cell.set, cell.unset_uncovered);
  }

private:
  std::vector<DPCell> &dp_table;
  const std::vector<int> &costs_by_city;
};

void testcase()
{
  int n;
  std::cin >> n;
  assert(n >= 1 && n <= 1e5);

  std::vector<std::pair<int, int>> stages(n - 1);
  for (std::pair<int, int> &s : stages)
  {
    std::cin >> s.first >> s.second;
    assert(s.first != s.second && s.first >= 0 && s.first < n && s.second >= 0 && s.second < n);
  }

  std::vector<int> costs_by_city(n);
  for (int &c : costs_by_city)
  {
    std::cin >> c;
    assert(c >= 0 && c <= (1 << 14));
  }

  Graph G(n);
  for (const std::pair<int, int> &s : stages)
  {
    boost::add_edge(s.first, s.second, G);
  }

  std::vector<DPCell> dp_table(n);
  DPVisitor visitor(dp_table, costs_by_city);
  // WARNING: Boost copies the visitor, we have to save the DP table externally, otherwise we will never get the filled-out copy.
  boost::depth_first_search(G, boost::visitor(visitor));
  std::cout << visitor.get_result() << "\n";
}

int main()
{
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(0);

  int t;
  std::cin >> t;
  for (int i = 0; i < t; i++)
  {
    testcase();
    DEBUG(1, "");
  }

  return 0;
}

max_stars_repo_name: tehwalris/algolab

max_issues_repo_name: tehwalris/algolab

max_forks_repo_name: tehwalris/algolab


text:
//  ================================================================
//  Created by Gregory Kramida on 10/23/18.
//  Copyright (c) 2018 Gregory Kramida
//  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.
//  ================================================================
#pragma once

//stdlib
#include <cstdlib>
#include <vector>

//libraries
#include <Eigen/Eigen>
#include <unsupported/Eigen/CXX11/Tensor>

//local
#include "vector2.hpp"
#include "matrix2.hpp"
#include "typedefs.hpp"

namespace math {

/***
 * Make a nested vector field out of a set of scalar fields by stacking values in each location into a vector.
 * @param set the set of scalar fields to use
 */
template<typename Scalar>
Eigen::Matrix<math::Vector2<Scalar>, Eigen::Dynamic, Eigen::Dynamic, Eigen::ColMajor>
stack(const std::vector<Eigen::Matrix<Scalar, Eigen::Dynamic, Eigen::Dynamic, Eigen::ColMajor>>& set);

template<typename Scalar>
Eigen::Tensor<Scalar, 3, Eigen::ColMajor>
stack(const std::vector<Eigen::Tensor<Scalar, Eigen::ColMajor>>& set);

//legacy
MatrixXv2f stack_as_xv2f(const Eigen::MatrixXf& matrix_a, const Eigen::MatrixXf& matrix_b);
void unstack_xv2f(Eigen::MatrixXf& matrix_a, Eigen::MatrixXf& matrix_b, const MatrixXv2f vector_field);

} //namespace math

max_stars_repo_name: Algomorph/LevelSetFusionExperimentsCPP

max_issues_repo_name: Algomorph/LevelSetFusionExperimentsCPP

max_forks_repo_name: Algomorph/LevelSetFusionExperimentsCPP


text:
// Name:            beanstalk_connect_test.h
// Description:     beanstalk 客户端测试程序
// Author:          zhangshiguang
// Email:           zhangshiguang@gmail.com
// Date:            2016-03

#include <stdio.h>
#include "beanstalk_connect.h"
#include <boost/thread/thread.hpp>

using namespace std;

//任务生成线程
void task_gen_func() {
    tml::beanstalk_connect conn("127.0.0.1", 7888);
    conn.connect();
    conn.use("foo");

    int count = 1;
    while (true) {
        char buf[128];
        sprintf(buf, "job %d", count++);
        int64_t job_id;
        conn.put(buf, job_id);
        printf("[GENERATE] %ld - %s\n", job_id, buf);
        boost::this_thread::sleep(boost::posix_time::milliseconds(100));
    }
}

//任务消费线程
void task_consume_func() {
    tml::beanstalk_connect conn("127.0.0.1", 7888);
    conn.connect();
    conn.watch("foo");

    while (true) {
        Beanstalkpp::Job job;
        conn.reserve(job);
        printf("[CONSUME] %d - %s\n", job.getJobId(), job.asString().c_str());
        conn.del(job);
    }
}

int main(int argc, char *argv[]) {
    boost::thread t1(task_gen_func);
    boost::thread t2(task_consume_func);
    t1.join();
    t2.join();
    return 0;
}

max_stars_repo_name: andyzhshg/tml

max_issues_repo_name: andyzhshg/tml

max_forks_repo_name: andyzhshg/tml