text:
#include <basalt/utils/assert.h>
#include <basalt/utils/time_utils.hpp>

#include <fstream>
#include <iomanip>

#include <fmt/format.h>
#include <Eigen/Dense>
#include <nlohmann/json.hpp>

namespace basalt {

using namespace fmt::literals;

// compute the median of an eigen vector
// Note: Changes the order of elements in the vector!
// Note: For even sized vectors we don't return the mean of the middle two, but
// simply the second one as is.
template <class Scalar, int Rows>
Scalar median_non_const(Eigen::Matrix<Scalar, Rows, 1>& vec) {
  static_assert(Rows != 0);
  if constexpr (Rows < 0) {
    BASALT_ASSERT(vec.size() >= 1);
  }
  int n = vec.size() / 2;
  std::nth_element(vec.begin(), vec.begin() + n, vec.end());
  return vec(n);
}

template <class Scalar, int N>
Scalar variance(const Eigen::Matrix<Scalar, N, 1>& vec) {
  static_assert(N != 0);
  const Eigen::Matrix<Scalar, N, 1> centered = vec.array() - vec.mean();
  return centered.squaredNorm() / Scalar(vec.size());
}

ExecutionStats::Meta& ExecutionStats::add(const std::string& name,
                                          double value) {
  auto [it, new_item] = stats_.try_emplace(name);
  if (new_item) {
    order_.push_back(name);
    it->second.data_ = std::vector<double>();
  }
  std::get<std::vector<double>>(it->second.data_).push_back(value);
  return it->second;
}

ExecutionStats::Meta& ExecutionStats::add(const std::string& name,
                                          const Eigen::VectorXd& value) {
  auto [it, new_item] = stats_.try_emplace(name);
  if (new_item) {
    order_.push_back(name);
    it->second.data_ = std::vector<Eigen::VectorXd>();
  }
  std::get<std::vector<Eigen::VectorXd>>(it->second.data_).push_back(value);
  return it->second;
}

ExecutionStats::Meta& ExecutionStats::add(const std::string& name,
                                          const Eigen::VectorXf& value) {
  Eigen::VectorXd x = value.cast<double>();
  return add(name, x);
}

void ExecutionStats::merge_all(const ExecutionStats& other) {
  for (const auto& name : other.order_) {
    const auto& meta = other.stats_.at(name);
    std::visit(
        [&](auto& data) {
          for (auto v : data) {
            add(name, v);
          }
        },
        meta.data_);
    stats_.at(name).set_meta(meta);
  }
}

namespace {  // helper
// ////////////////////////////////////////////////////////////////////////////
// overloads for generic lambdas
// See also: https://stackoverflow.com/q/55087826/1813258
template <class... Ts>
struct overload : Ts... {
  using Ts::operator()...;
};
template <class... Ts>
overload(Ts...) -> overload<Ts...>;
}  // namespace

void ExecutionStats::merge_sums(const ExecutionStats& other) {
  for (const auto& name : other.order_) {
    const auto& meta = other.stats_.at(name);
    std::visit(overload{[&](const std::vector<double>& data) {
                          Eigen::Map<const Eigen::VectorXd> map(data.data(),
                                                                data.size());
                          add(name, map.sum());
                        },
                        [&](const std::vector<Eigen::VectorXd>& data) {
                          UNUSED(data);
                          // TODO: for now no-op
                        }},
               meta.data_);
    stats_.at(name).set_meta(meta);
  }
}

void ExecutionStats::print() const {
  for (const auto& name : order_) {
    const auto& meta = stats_.at(name);

    std::visit(
        overload{
            [&](const std::vector<double>& data) {
              Eigen::Map<const Eigen::VectorXd> map(data.data(), data.size());

              // create a copy for median computation
              Eigen::VectorXd vec = map;

              if (meta.format_ == "ms") {
                // convert seconds to milliseconds
                vec *= 1000;
              }

              int count = vec.size();
              // double sum = vec.sum();
              double mean = vec.mean();
              double stddev = std::sqrt(variance(vec));
              double max = vec.maxCoeff();
              double min = vec.minCoeff();

              // double median = median_non_const(vec);

              if (meta.format_ == "count") {
                std::cout << "{:20} ({:>4}):{: 8.1f}+-{:.1f} [{}, {}]\n"_format(
                    name, count, mean, stddev, min, max);
              } else if (meta.format_ != "none") {
                std::cout
                    << "{:20} ({:>4}):{: 8.2f}+-{:.2f} [{:.2f}, {:.2f}]\n"_format(
                           name, count, mean, stddev, min, max);
              }
            },
            [&](const std::vector<Eigen::VectorXd>& data) {
              int count = data.size();
              std::cout << "{:20} ({:>4})\n"_format(name, count);
            }},
        meta.data_);
  }
}

bool ExecutionStats::save_json(const std::string& path) const {
  using json = nlohmann::json;
  json result;

  for (const auto& name : order_) {
    const auto& meta = stats_.at(name);

    std::visit(
        overload{[&](const std::vector<double>& data) { result[name] = data; },
                 [&](const std::vector<Eigen::VectorXd>& data) {
                   std::vector<int> indices;
                   std::vector<double> values;
                   for (const auto& v : data) {
                     indices.push_back(int(values.size()));
                     values.insert(values.end(), v.begin(), v.end());
                   }
                   std::string name_values = std::string(name) + "__values";
                   std::string name_indices = std::string(name) + "__index";
                   result[name_indices] = indices;
                   result[name_values] = values;
                 }},
        meta.data_);
  }

  constexpr bool save_as_json = false;
  constexpr bool save_as_ubjson = true;

  // save json
  if (save_as_json) {
    std::ofstream ofs(path);

    if (!ofs.is_open()) {
      std::cerr << "Could not save ExecutionStats to {}.\n"_format(path);
      return false;
    }

    ofs << std::setw(4) << result;  //!< pretty printing
    // ofs << result;  //!< no pretty printing

    std::cout << "Saved ExecutionStats to {}.\n"_format(path);
  }

  // save ubjson
  if (save_as_ubjson) {
    std::string ubjson_path =
        path.substr(0, path.find_last_of('.')) + ".ubjson";
    std::ofstream ofs(ubjson_path, std::ios_base::binary);

    if (!ofs.is_open()) {
      std::cerr << "Could not save ExecutionStats to {}.\n"_format(ubjson_path);
      return false;
    }

    json::to_ubjson(result, ofs);

    std::cout << "Saved ExecutionStats to {}.\n"_format(ubjson_path);
  }

  return true;
}

}  // namespace basalt


text:
/*
 * #%L
 * OME-XML C++ library for working with OME-XML metadata structures.
 * %%
 * Copyright © 2016 Open Microscopy Environment:
 *   - Massachusetts Institute of Technology
 *   - National Institutes of Health
 *   - University of Dundee
 *   - Board of Regents of the University of Wisconsin-Madison
 *   - Glencoe Software, Inc.
 * %%
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 * 2. Redistributions 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.
 *
 * 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 COPYRIGHT HOLDERS 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.
 *
 * The views and conclusions contained in the software and documentation are
 * those of the authors and should not be interpreted as representing official
 * policies, either expressed or implied, of any organization.
 * #L%
 */

#include <iostream>
#include <fstream>

#include <boost/filesystem.hpp>
#include <boost/filesystem/fstream.hpp>

#include <ome/common/xsl/Platform.h>

#include <ome/xml/OMEEntityResolver.h>
#include <ome/xml/OMETransform.h>
#include <ome/xml/OMETransformResolver.h>
#include <ome/xml/version.h>

#include <ome/test/test.h>
#include <ome/test/io.h>

using boost::filesystem::path;
using boost::filesystem::directory_iterator;

struct TransformTestParameters
{
  path file;
  bool throws;
};

template<class charT, class traits>
inline std::basic_ostream<charT,traits>&
operator<< (std::basic_ostream<charT,traits>& os,
            const TransformTestParameters& p)
{
  return os << p.file;
}

namespace
{

  std::vector<TransformTestParameters>
  find_transform_tests()
  {
    std::vector<TransformTestParameters> params;

    ome::xml::OMETransformResolver tr;
    std::set<std::string> versions = tr.schema_versions();

    path samplesdir(PROJECT_SOURCE_DIR "/specification/samples");
    if (exists(samplesdir) && is_directory(samplesdir))
      {
        for (directory_iterator si(samplesdir); si != directory_iterator(); ++si)
          {
            if (versions.find(si->path().filename().string()) == versions.end())
              continue; // Not a schema directory with transforms.
            path schemadir(si->path());
            if (exists(schemadir) && is_directory(schemadir))
              {
                for (directory_iterator fi(schemadir); fi != directory_iterator(); ++fi)
                  {
                    TransformTestParameters p;
                    p.file = *fi;
                    p.throws = false;

                    // 2008-09/instrument.ome.xml
                    if (schemadir.filename() == path("2008-09") &&
                        p.file.filename() == path("instrument.ome.xml"))
                      continue;
                    // timestampannotation.ome.xml - Contains non-POSIX timestamps.
                    if (p.file.filename() == path("timestampannotation.ome.xml"))
                      continue;

                    if (p.file.extension() == path(".ome") ||
                        p.file.extension() == path(".xml"))
                      params.push_back(p);
                  }
              }
          }
      }

    return params;
  }

}

std::vector<TransformTestParameters> transform_params(find_transform_tests());

class TransformTest : public ::testing::TestWithParam<TransformTestParameters>
{
public:
  ome::common::xsl::Platform xslplat;
  ome::xml::OMEEntityResolver entity_resolver;
  ome::xml::OMETransformResolver transform_resolver;

  TransformTest():
    ::testing::TestWithParam<TransformTestParameters>(),
    entity_resolver(),
    transform_resolver()
  {
  }

  void SetUp()
  {
    const TransformTestParameters& params = GetParam();
    std::cout << "Source file " << params.file << '\n';
  }
};

TEST_P(TransformTest, TransformFileToString)
{
  const TransformTestParameters& params = GetParam();

  std::string result;
  if(params.throws)
    {
      ASSERT_THROW(ome::xml::transform(OME_XML_MODEL_VERSION, params.file, result,
                                       entity_resolver, transform_resolver),
                   std::runtime_error);
    }
  else
    {
      ASSERT_NO_THROW(ome::xml::transform(OME_XML_MODEL_VERSION, params.file, result,
                                          entity_resolver, transform_resolver));

      ASSERT_TRUE(!result.empty());

      ome::common::xml::dom::Document resultdoc(ome::common::xml::dom::createDocument(result, entity_resolver));
      ASSERT_EQ(std::string(OME_XML_MODEL_VERSION),
                ome::xml::getModelVersion(resultdoc));
    }
}

TEST_P(TransformTest, TransformStreamToString)
{
  const TransformTestParameters& params = GetParam();

  boost::filesystem::ifstream input(params.file);

  std::string result;
  if(params.throws)
    {
      ASSERT_THROW(ome::xml::transform(OME_XML_MODEL_VERSION, params.file, result,
                                       entity_resolver, transform_resolver),
                   std::runtime_error);
    }
  else
    {
      ASSERT_NO_THROW(ome::xml::transform(OME_XML_MODEL_VERSION, params.file, result,
                                          entity_resolver, transform_resolver));

      ASSERT_TRUE(!result.empty());

      ome::common::xml::dom::Document resultdoc(ome::common::xml::dom::createDocument(result, entity_resolver));
      ASSERT_EQ(std::string(OME_XML_MODEL_VERSION),
                ome::xml::getModelVersion(resultdoc));
    }
}

TEST_P(TransformTest, TransformStringToString)
{
  const TransformTestParameters& params = GetParam();

  std::string input;
  readFile(params.file, input);

  std::string result;
  if(params.throws)
    {
      ASSERT_THROW(ome::xml::transform(OME_XML_MODEL_VERSION, input, result,
                                       entity_resolver, transform_resolver),
                   std::runtime_error);
    }
  else
    {
      ASSERT_NO_THROW(ome::xml::transform(OME_XML_MODEL_VERSION, input, result,
                                          entity_resolver, transform_resolver));

      ASSERT_TRUE(!result.empty());

      ome::common::xml::dom::Document resultdoc(ome::common::xml::dom::createDocument(result, entity_resolver));
      ASSERT_EQ(std::string(OME_XML_MODEL_VERSION),
                ome::xml::getModelVersion(resultdoc));
    }
}

// Disable missing-prototypes warning for INSTANTIATE_TEST_CASE_P;
// this is solely to work around a missing prototype in gtest.
#ifdef __GNUC__
#  if defined __clang__ || defined __APPLE__
#    pragma GCC diagnostic ignored "-Wmissing-prototypes"
#  endif
#  pragma GCC diagnostic ignored "-Wmissing-declarations"
#endif

INSTANTIATE_TEST_CASE_P(TransformVariants, TransformTest, ::testing::ValuesIn(transform_params));

ext: cpp

max_stars_repo_name: ngladitz/ome-model

max_issues_repo_name: ngladitz/ome-model

max_forks_repo_name: ngladitz/ome-model


text:
#include "simulationexecutor.h"

#include <boost/property_tree/ptree.hpp>
#include <boost/property_tree/json_parser.hpp>

#include "scriptloader.h"
#include "simulation.h"

#include "nonlinearhamiltonian.h"

using namespace boost;
using namespace property_tree;

SimulationExecutor::SimulationExecutor(const std::string& filename) {
    ptree tree;
    json_parser::read_json(filename, tree);

    for (auto it = tree.begin(); it != tree.end(); ++it) {
        if (it->first == "Simulation") {
            const ptree& child = it->second;
            SimulationParameter params(child.get<double>("dx"),
                                       child.get<double>("dt"),
                                       child.get<double>("mass"),
                                       child.get<int>("iterations"),
                                       child.get<int>("atoms"));
            simulations.push_back(std::pair<SimulationParameter, std::string>(params, child.get<std::string>("script")));
        }
    }

    run();
}

SimulationExecutor::SimulationExecutor(const SimulationParameter& params, const std::string& scriptFile) {
    simulations.push_back(std::pair<SimulationParameter, std::string>(params, scriptFile));

    run();
}

void SimulationExecutor::run() {
    for (std::pair<SimulationParameter, std::string> simul : simulations) {
        Simulation sim(simul.first, nullptr);
        ScriptExecutor(sim, simul.second);
    }
}

max_stars_repo_name: TheTimmy/CrankNicolson

max_issues_repo_name: TheTimmy/CrankNicolson

max_forks_repo_name: TheTimmy/CrankNicolson


text:
/* Copyright (C) 2012-2020 IBM Corp.
 * This program is 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. See accompanying LICENSE file.
 */
/* @file OptimizePermutations.cpp
 * @brief Implementation of optimized permutation networks
 */

#include <cstdlib>
#include <list>
#include <sstream>
#include <memory>

#include <NTL/vector.h>
#include <helib/NumbTh.h>
#include <helib/EncryptedArray.h>
#include <helib/permutations.h>
#include <helib/apiAttributes.h>

namespace helib {

//! \cond FALSE (make doxygen ignore these classes)
template <typename T>
class ClassHash
{ // helper class to make defining hash functions easier
public:
  size_t operator()(const T& t) const { return t.hash(); }
};
//! \endcond

// routines for finding optimal level-collapsing strategies for Benes networks

// Removes duplicates from list x. Uses vector aux as scratch space
//   invariants:
//     * all elements in x lie in a range a..b
//     * aux[a..b] is false before and after removeDups is called
void removeDups(std::list<long>& x, bool* aux)
{
  for (std::list<long>::iterator i = x.begin(); i != x.end();) {
    if (aux[*i])
      i = x.erase(i);
    else {
      aux[*i] = true;
      i++;
    }
  }

  for (std::list<long>::iterator i = x.begin(); i != x.end(); i++)
    aux[*i] = false;
}

// Creates a new list with the old values and old values +/- offset.
// results outside the range -n+1 .. n-1 are discarded
// and all resulting duplicates are removed
void addOffset(std::list<long>& x,
               long offset,
               long n,
               bool* aux,
               UNUSED bool good = false)
{
  for (std::list<long>::iterator i = x.begin(); i != x.end(); i++) {
    long val = *i;
    long val1 = val + offset;
    long val2 = val - offset;
    if (val1 > -n && val1 < n)
      x.push_front(val1);
    if (val2 > -n && val2 < n)
      x.push_front(val2);
    /* FIXME: Alternative Impl:
     *        Replace the above two lines by
     *        if (good) {
     *           if (val1 < 0 && val1 > -n) val1 += n;
     *           if (val2 < 0 && val2 > -n) val2 += n;
     *        }
     *        if (val1 > -n && val1 < n && !aux[val1]) {
     *           x.push_front(val1);
     *           aux[val1] = true;
     *        }
     *        if (val2 > -n && val2 < n && !aux[val2]) {
     *           x.push_front(val2);
     *           aux[val2] = true;
     *        }
     * Then we can eliminate both removeDups and reducedCount
     */
  }

  removeDups(x, aux);
}

// Counts the number of unique elements mod n in x
long reducedCount(const std::list<long>& x, long n, bool* aux)
{
  long res = 0;

  for (std::list<long>::const_iterator i = x.begin(); i != x.end(); i++) {
    long val = *i;
    if (val < 0)
      val += n;

    if (!aux[val]) {
      res++;
      aux[val] = true;
    }
  }

  for (std::list<long>::const_iterator i = x.begin(); i != x.end(); i++) {
    long val = *i;
    if (val < 0)
      val += n;
    aux[val] = false;
  }

  return res;
}

// Compute the cost for all (n choose 2) possible ways to collapse levels.
// For j in [0..nlev-i) tab[i][j] is the cost of collapsing levels i..i+j.
// I.e., how many different shift amounts would we need to implement for
// a permutation-network-layer constructed by collapsing these levels.
void buildBenesCostTable(long n,
                         long k,
                         bool good,
                         NTL::Vec<NTL::Vec<long>>& tab)
{
  long nlev = 2 * k - 1;
  tab.SetLength(nlev);
  for (long i = 0; i < nlev; i++)
    tab[i].SetLength(nlev - i);

  NTL::Vec<bool> aux_vec;
  aux_vec.SetLength(2 * n - 1);
  bool* aux = &aux_vec[n - 1];
  for (long i = 0; i < 2 * n - 1; i++)
    aux_vec[i] = false;

  for (long i = 0; i < nlev; i++) {
    std::list<long> x;

    x.push_front(0L);
    for (long j = 0; j < nlev - i; j++) {
      long shamt = GeneralBenesNetwork::shamt(n, k, i + j);
      // The shift amount for this level

      addOffset(x, shamt, n, aux);
      if (good)
        tab[i][j] = reducedCount(x, n, aux) - 1;
      else
        tab[i][j] = x.size() - 1;
      // FIXME: Alternative Impl:
      //        Replace the 5 lines above by
      //        addOffset(x, shamt, n, aux, good);
      //        tab[i][j] = x.size() - 1;
      //        Also initialize aux to false in every iteration
    }
  }
}

//! \cond FALSE (make doxygen ignore these classes)
class LongNode;
typedef std::shared_ptr<LongNode> LongNodePtr;
// A "shared_ptr" is a pointer with (some) garbage collection

// A LongNode is an implementation of std::list<long>, i.e. a linked list of
// counters, representing a particular way of "collapsing levels" in a Benes
// network. Each LongNode holds a count of collapsed levels, and the sum of all
// counter in the list must equal the number of levels in the Benes network.
class LongNode
{
public:
  long count;       // number of levels collapsed
  LongNodePtr next; // next node in the list

  LongNode(long _count, LongNodePtr _next)
  {
    count = _count;
    next = _next;
  }
};
//! \endcond

// Returns the length of the linked list, starting with this pointer
static long length(LongNodePtr ptr)
{
  long res = 0;
  for (LongNodePtr p = ptr; p != nullptr; p = p->next)
    res++;
  return res;
}

// Converts std::list<long> to NTL::Vec<long>
static long listToVec(NTL::Vec<long>& vec, LongNodePtr ptr)
{
  long len = length(ptr);

  vec.SetLength(len);
  long i = 0;
  for (LongNodePtr p = ptr; p != nullptr; p = p->next) {
    vec[i] = p->count;
    i++;
  }
  return len;
}

// Prints out a list of integers
std::ostream& operator<<(std::ostream& s, LongNodePtr p)
{
  if (p == nullptr)
    return s << "[]";

  s << "[" << p->count;
  for (p = p->next; p != nullptr; p = p->next)
    s << " " << p->count;
  return s << "]";
}

// Data structures to hold the memoization table for the dynamic-programming
// computation of the level collapsing in a Benes network. An entry in the
// table is specified by the first-level index i and the allotted budget
// (depth). Once the computation is over, this entry will contain the optimal
// way of breaking this network (encoded as a LongNode list) and the cost of
// this network.
//! \cond FALSE (make doxygen ignore these classes)
class BenesMemoKey
{
public:
  long i;      // Index of 1st level to consider
  long budget; // max-depth of network after collapsing

  BenesMemoKey(long _i, long _budget)
  {
    i = _i;
    budget = _budget;
  }

  size_t hash() const
  {
    std::stringstream s;
    s << i << " " << budget;
    return std::hash<std::string>()(s.str());
  }

  bool operator==(const BenesMemoKey& other) const
  {
    return i == other.i && budget == other.budget;
  }
};

class BenesMemoEntry
{
public:
  long cost;            // Cost of the optimal solution
  LongNodePtr solution; // The solution itself, as a list of LongNode's

  BenesMemoEntry(long _cost, LongNodePtr _solution)
  {
    cost = _cost;
    solution = _solution;
  }

  BenesMemoEntry() {}
};

typedef std::
    unordered_map<BenesMemoKey, BenesMemoEntry, ClassHash<BenesMemoKey>>
        BenesMemoTable;
//! \endcond

// A dynamic program (implemented as a recursive routine with memoization) for
// computing the optimal collapsing of layers in a generalized Benes network.
//
// The parameter i indicates the sub-problem at hand, namely we are trying
// to find the optimal way of collapsing the sub-network from level i to
// the end (level nlev).
//
// The budget is the largest number of levels that we can afford after
// collapsing. (For example, if budget >= nlev-i, then there is no need to
// collapse anything.)

BenesMemoEntry optimalBenesAux(long i,
                               long budget,
                               long nlev,
                               const NTL::Vec<NTL::Vec<long>>& costTab,
                               BenesMemoTable& memoTab)
{
  assertInRange<InvalidArgument>(i,
                                 0l,
                                 nlev,
                                 "Level to collapse index out of bound",
                                 true);
  assertTrue<InvalidArgument>(budget > 0, "No budget left");

  // Did we already solve this problem? If so just return the solution.
  BenesMemoTable::iterator find = memoTab.find(BenesMemoKey(i, budget));
  if (find != memoTab.end()) {
    return find->second;
  }

  // a new subproblem to process...

  long cost;
  LongNodePtr solution;

  if (i == nlev) { // An empty network, nothing to collapse, trivial solution
    cost = 0;
    solution = LongNodePtr();
  } else if (budget == 1) {
    // Almost no budget is left, the only possible solution is to collapse
    // all remaining levels together.

    cost = costTab[i][nlev - i - 1];
    solution = LongNodePtr(new LongNode(nlev - i, LongNodePtr()));
  } else {
    // We consider collapsing levels i..i+j, for all j in [0..nlev-i),
    // then choose the option that gives the best cost.

    long bestCost = NTL_MAX_LONG;
    long bestJ = 0;
    BenesMemoEntry bestT;
    for (long j = 0; j < nlev - i; j++) {
      // If we collapse levels i..i+j, then we need to compute the optimal
      // way of collapsing the rest, i.e. level i+j+1 to the end.
      BenesMemoEntry t =
          optimalBenesAux(i + j + 1, budget - 1, nlev, costTab, memoTab);

      // The total cost of this solution is the cost of the collapsed level
      // (i..i+j) itself, plus the cost of the optimal solution for the rest.
      if (t.cost + costTab[i][j] < bestCost) {
        bestCost = t.cost + costTab[i][j];
        bestJ = j;
        bestT = t;
      }
    }

    cost = bestCost;
    solution = LongNodePtr(new LongNode(bestJ + 1, bestT.solution));
  }

  return memoTab[BenesMemoKey(i, budget)] = BenesMemoEntry(cost, solution);
}

// Computes an optimal level-collapsing strategy for a Benes network
//   n = the size of the network
//   budget = an upper bound on the number of levels in the collapsed network
//   good = flag indicating whether this is with respect to a "good" generator,
//     for which shifts by i and i-n correspond to the same rotation
//   cost = total number of shifts needed by the collapsed network
//   solution = list indicating how levels in a standard benes network
//      are collapsed: if solution = [s_1 s_2 ... s_k], then k <= budget,
//      and the first s_1 levels are collapsed, the next s_2 levels
//      are collapsed, etc.
void optimalBenes(long n,
                  long budget,
                  bool good,
                  long& cost,
                  LongNodePtr& solution)
{
  long k = GeneralBenesNetwork::depth(n); // k = ceiling(log_2 n)
  long nlev = 2 * k - 1; // before collapsing, we have 2k-1 levels

  NTL::Vec<NTL::Vec<long>> costTab;
  // costTab[i][j] to holds the cost of collapsing levels i..i+j

  buildBenesCostTable(n, k, good, costTab);
  // Compute the cost for all (n choose 2) possible ways to collapse levels.

  BenesMemoTable memoTab;
  BenesMemoEntry t = optimalBenesAux(0, budget, nlev, costTab, memoTab);
  // Compute the optimal collapsing of layers in a width-n Benes network

  cost = t.cost;
  solution = t.solution;
}

/********************************************************************/
/***** Routines for finding the optimal splits among generators *****/
/********************************************************************/

//! \cond FALSE (make doxygen ignore these classes)

// A binary tree data structure for splitting generators
class SplitNode;
typedef std::shared_ptr<SplitNode> SplitNodePtr;
// A "std::shared_ptr" is a pointer with (some) garbage collection

class SplitNode
{
public:
  long order; // order associated with this node
  long mid;   // the "middle" token, 0 or 1
  bool good;  // the "good" flag
  LongNodePtr solution1, solution2;
  // The benes solution(s).
  // For non-middle nodes there may be two different solutions,
  // depending on how the budget is split
  SplitNodePtr left, right; // the children (for internal nodes)

  SplitNode(long _order,
            long _mid,
            bool _good,
            LongNodePtr _solution1,
            LongNodePtr _solution2)
  {
    // constructor for leaves
    order = _order;
    mid = _mid;
    good = _good;
    solution1 = _solution1;
    solution2 = _solution2;
    left = right = SplitNodePtr();
  }

  SplitNode(long _order,
            long _mid,
            bool _good,
            SplitNodePtr _left,
            SplitNodePtr _right)
  {
    // constructor for internal nodes
    order = _order;
    mid = _mid;
    good = _good;
    solution1 = solution2 = LongNodePtr();
    left = _left;
    right = _right;
  }

  bool isLeaf() const { return left == nullptr && right == nullptr; }
};
//! \endcond

// Routines for printing the leaves of a generator-tree
void print(std::ostream& s, SplitNodePtr p, bool first)
{
  if (p->isLeaf()) {
    if (!first)
      s << " ";
    s << "[";
    if (p->mid == 1)
      s << "*";
    if (p->good)
      s << "g ";
    else
      s << "b ";
    s << p->order << " " << p->solution1 << " " << p->solution2 << "]";
  } else {
    print(s, p->left, first);
    print(s, p->right, false);
  }
}
std::ostream& operator<<(std::ostream& s, SplitNodePtr p)
{
  s << "[";
  print(s, p, true);
  s << "]";
  return s;
}

// Data structures to hold the memory table for the dynamic-programming
// computation optimizing a generator tree. An entry in the table is specified
// by (order,good-flag,budget,middle-flag). When the computation is over, this
// entry will contain the optimal tree for a single generator (encoded as a
// SplitNode tree) and the cost of this solution.
//! \cond FALSE (make doxygen ignore these classes)
class LowerMemoKey
{
public:
  long order;  // size of hypercube corresponding to this sub-tree
  bool good;   // is this a good subtree
  long budget; // max-depth of network(s) associated to this node
  long mid;    // whether or not this is the middle layer of the network

  LowerMemoKey(long _order, bool _good, long _budget, long _mid)
  {
    order = _order;
    good = _good;
    budget = _budget;
    mid = _mid;
  }

  size_t hash() const
  {
    std::stringstream s;
    s << order << " " << good << " " << budget << " " << mid;
    return std::hash<std::string>()(s.str());
  }

  bool operator==(const LowerMemoKey& other) const
  {
    return order == other.order && good == other.good &&
           budget == other.budget && mid == other.mid;
  }
};

class LowerMemoEntry
{
public:
  long cost;
  SplitNodePtr solution;

  LowerMemoEntry(long _cost, SplitNodePtr _solution)
  {
    cost = _cost;
    solution = _solution;
  }

  LowerMemoEntry() {}
};

typedef std::
    unordered_map<LowerMemoKey, LowerMemoEntry, ClassHash<LowerMemoKey>>
        LowerMemoTable;

// list structure for managing generators

class GenNode;
typedef std::shared_ptr<GenNode> GenNodePtr;
// A "shared_ptr" is a pointer with (some) garbage collection

class GenNode
{
public:
  SplitNodePtr solution; // the solution tree for this generator
  GenNodePtr next;       // next node in the list

  GenNode(SplitNodePtr _solution, GenNodePtr _next)
  {
    solution = _solution;
    next = _next;
  }
};
//! \endcond

// Compute the length of a list
long length(GenNodePtr ptr)
{
  long res = 0;
  for (GenNodePtr p = ptr; p != nullptr; p = p->next)
    res++;
  return res;
}

std::ostream& operator<<(std::ostream& s, GenNodePtr p)
{
  if (p == nullptr) {
    s << "[]";
    return s;
  }

  s << "[" << p->solution;
  p = p->next;
  while (p != nullptr) {
    s << " " << p->solution;
    p = p->next;
  }
  s << "]";

  return s;
}

// upper level memo table

// Data structures to hold the memory table for optimizing the partition to
// separate generator tree. An entry in the table is specified by the index
// of a generator, the budget allocated to this tree, and the middle flag.
// When the computation is over, this entry will contain the optimal list
// of trees (encoded as a GenNode list) and the cost of this solution.
//! \cond FALSE (make doxygen ignore these classes)
class UpperMemoKey
{
public:
  long i;
  long budget;
  long mid;

  UpperMemoKey(long _i, long _budget, long _mid)
  {
    i = _i;
    budget = _budget;
    mid = _mid;
  }

  size_t hash() const
  {
    std::stringstream s;
    s << i << " " << budget << " " << mid;
    return std::hash<std::string>()(s.str());
  }

  bool operator==(const UpperMemoKey& other) const
  {
    return i == other.i && budget == other.budget && mid == other.mid;
  }
};

class UpperMemoEntry
{
public:
  long cost;
  GenNodePtr solution;

  UpperMemoEntry(long _cost, GenNodePtr _solution)
  {
    cost = _cost;
    solution = _solution;
  }

  UpperMemoEntry() {}
};

typedef std::
    unordered_map<UpperMemoKey, UpperMemoEntry, ClassHash<UpperMemoKey>>
        UpperMemoTable;
//! \endcond

// Optimize a single tree: try all possible ways of splitting the order into
// order1*order2 (and also the solution of not splitting at all). For every
// possible split, try all budget allocations and allocations of good and mid.
LowerMemoEntry optimalLower(long order,
                            bool good,
                            long budget,
                            long mid,
                            LowerMemoTable& lowerMemoTable)
{
  assertTrue<InvalidArgument>(order > 1, "Order must be greater than 1");
  assertTrue<InvalidArgument>(mid == 0 || mid == 1, "mid value is not 1 or 2");
  assertTrue<InvalidArgument>(budget > 0, "No budget left");

  // Did we already solve this problem? If so just return the solution.
  LowerMemoTable::iterator find =
      lowerMemoTable.find(LowerMemoKey(order, good, budget, mid));

  if (find != lowerMemoTable.end()) {
    return find->second;
  }

  long cost;
  SplitNodePtr solution;

  if (mid == 0 && budget == 1) {
    // Insufficient budget, no solution is possible

    cost = NTL_MAX_LONG;
    solution = SplitNodePtr();
  } else {
    // First calculate a solution without splitting, making this a leaf node
    LongNodePtr benesSolution1, benesSolution2;

    if (mid == 1) {
      // this is the middle node, so just one Benes network

      optimalBenes(order, budget, good, cost, benesSolution1);
      benesSolution2 = LongNodePtr();
    } else {
      // not the middle node, so we need two Benes networks.
      // if budget is odd, we split it unevenly

      long cost1, cost2;
      optimalBenes(order, budget / 2, good, cost1, benesSolution1);
      if (budget % 2 == 0) { // both networks have the same budget
        cost2 = cost1;
        benesSolution2 = benesSolution1;
      } else { // one network has budget larger by one than the other
        optimalBenes(order, budget - budget / 2, good, cost2, benesSolution2);
      }

      cost = cost1 + cost2;
    }

    // The initial solution corresponds to this being a leaf node
    solution = SplitNodePtr(
        new SplitNode(order, mid, good, benesSolution1, benesSolution2));

    // Recursively try all the ways of splitting order = order1 * order2

    for (long order1 = 2; order1 < order; order1++) {
      // try all factors of order
      // there is some redundancy here, since we consider
      // both the splits (d, n/d) and (n/d, d); however,
      // we utilize this redundancy (see below) to streamline
      // allocation of the "good" token (if we have it)

      // continue;  // temporary hack to force benes for testing
      if (order % order1 != 0)
        continue;

      bool good1 = good;
      bool good2 = good;

      if (good && NTL::GCD(order1, order / order1) != 1)
        good2 = false;

      // The logic is that if the problem is "good"
      // but the split is not relatively prime,
      // then only one of the subproblems is good.
      // since order1 ranges over all factors of order,
      // it suffices to choose the left subproblem to be
      // the good one.

      // Try all possible ways of splitting the budget between the two nodes
      for (long budget1 = 1; budget1 < budget; budget1++) {

        // A slick way of giving the middle token to one of the
        // nodes if we have it, and to none of the nodes if we don't
        for (long mid1 = 0; mid1 <= mid; mid1++) {
          LowerMemoEntry s1 =
              optimalLower(order1, good1, budget1, mid1, lowerMemoTable);
          // FIXME: If s1.cost==NTL_MAX_LONG we do not need to compute
          //        the cost of s2
          LowerMemoEntry s2 = optimalLower(order / order1,
                                           good2,
                                           budget - budget1,
                                           mid - mid1,
                                           lowerMemoTable);
          if (s1.cost != NTL_MAX_LONG && s2.cost != NTL_MAX_LONG &&
              s1.cost + s2.cost < cost) {
            cost = s1.cost + s2.cost;
            // Record the new best solution
            solution = SplitNodePtr(
                new SplitNode(order, mid, good, s1.solution, s2.solution));
          }
        }
      }
    }
  }

  // Record the best solution in the lowerMemoTable and return it
  return lowerMemoTable[LowerMemoKey(order, good, budget, mid)] =
             LowerMemoEntry(cost, solution);
}

// Optimizing a list of trees, trying all the ways of allocating the budget
// and mid token between the trees. This procedure splits the "current
// remaining budget" between trees i through vec.length()-1.
UpperMemoEntry optimalUpperAux(const NTL::Vec<GenDescriptor>& vec,
                               long i,
                               long budget,
                               long mid,
                               UpperMemoTable& upperMemoTable,
                               LowerMemoTable& lowerMemoTable)
{
  assertInRange<InvalidArgument>(i,
                                 0l,
                                 (long)vec.length(),
                                 "Index i does not point to "
                                 "a tree (index out of range)",
                                 true);
  assertTrue<InvalidArgument>(budget >= 0, "Negative budget");
  assertTrue<InvalidArgument>(mid == 0 || mid == 1, "mid value is not 1 or 2");

  // FIXME: Did we already solve this problem? If so just return the solution.
  UpperMemoTable::iterator find =
      upperMemoTable.find(UpperMemoKey(i, budget, mid));
  if (find != upperMemoTable.end()) {
    return find->second;
  }

  long cost;
  GenNodePtr solution;

  if (i == vec.length()) {
    // An empty list, recursion stops here with trivial solution

    cost = 0;
    solution = GenNodePtr();
  } else if (budget == 0) {
    // recursion stops here with no solution

    cost = NTL_MAX_LONG;
    solution = GenNodePtr();
  } else {
    // allocate resources (budget, mid) between generator i and the rest

    long bestCost = NTL_MAX_LONG;
    LowerMemoEntry bestS;
    UpperMemoEntry bestT;

    for (long budget1 = 1; budget1 <= budget; budget1++) {
      for (long mid1 = 0; mid1 <= mid; mid1++) {
        // Optimize the first tree (index i) with the allotted budget1, mid1
        LowerMemoEntry s = optimalLower(vec[i].order,
                                        vec[i].good,
                                        budget1,
                                        mid1,
                                        lowerMemoTable);
        // FIXME: If s.cost==NTL_MAX_LONG we do not need to compute
        //        the cost of t

        // Optimize the rest of the list with the remaining budget and mid
        UpperMemoEntry t = optimalUpperAux(vec,
                                           i + 1,
                                           budget - budget1,
                                           mid - mid1,
                                           upperMemoTable,
                                           lowerMemoTable);
        if (s.cost != NTL_MAX_LONG && t.cost != NTL_MAX_LONG &&
            s.cost + t.cost < bestCost) {
          bestCost = s.cost + t.cost;
          bestS = s;
          bestT = t;
        }
      }
    }

    cost = bestCost;
    if (cost == NTL_MAX_LONG)
      solution = GenNodePtr();
    else
      solution = GenNodePtr(new GenNode(bestS.solution, bestT.solution));
  }

  // Record the best solution in the upperMemoTable and return it
  return upperMemoTable[UpperMemoKey(i, budget, mid)] =
             UpperMemoEntry(cost, solution);
}

/**
 * optimalUpper is the high-level routine used to find
 * an optimal strategy for evaluating a permutation
 * The inputs are:
 *   * vec: a vector describing the generators, each entry
 *       consist of a long/bool pair (order, good)
 *   * budget: the total budget for levels in the network,
 *       which corresponds to the (multiplicative) circuit depth
 * The outputs are:
 *   * cost: the number of rotations needed (a specific
 *       permutation could use fewer)
 *   * solution: the optimal strategy, described below
 *
 * The solution is a linked list of length equal to the length of vec.
 * The ith entry of the list corresponds to the ith entry in vec.
 * Each entry in the list is a binary tree (SplitNodePtr).
 * Every node in such a tree is either a leaf or an internal node
 *   with two children.
 * Every node contains the order associated with that node, along with
 *   a "mid" flag: 1 means this is a "middle" node, 0 means not.
 * In the top-level list of trees, only one tree root will be a middle node,
 *   and for every internal middle node in any tree, only one child
 *   will be a middle node.
 * A leaf node in a tree will contain two "benes network collapsing solutions",
 *   solution1 and solution2.
 *   If this leaf node is a middle node, solution2 is empty.
 *   Otherwise, there are actually two solutions: this is because
 *   the benes network corresponding to this leaf will appear twice
 *   in the overall network, and if the budget allocated to this leaf
 *   is *odd*, we may want to split the budget unevenly between the two
 *   networks (floor(budget/2) and floor(budget/2)+1.
 *   NOTE: one could consider more general splits of the budget
 *   between these two occurrences of the network, but it seems doubtful
 *   to be of benefit.
 * A "benes network collapsing solution" is a list of longs (longNodePtr).
 *   If the list is [n_1 n_2 ... n_k], this means we are to collapse
 *   the first n_1 levels of the Benes network, then the next n_2 levels,
 *   and so on.  The resulting "collapsed" Benes network will have k
 *   levels.
 *********************************************************************/

// Returns the total number of layers in the corresponding (sub)network
static long recursiveCopy2Tree(OneGeneratorTree& gTree,
                               long nodeIdx,
                               SplitNodePtr& solution)
{
  if (solution->isLeaf()) { // Copy the Benes levels
    return listToVec(gTree[nodeIdx].getData().frstBenes, solution->solution1) +
           listToVec(gTree[nodeIdx].getData().scndBenes, solution->solution2);
  }

  // Copy left and right children into the tree. A child with mid-token
  // is copied last, if none has the mid-token then copy them in order.

  SplitNodePtr leftChld, rightChld;
  if (solution->left->mid) {
    rightChld = solution->left;
    leftChld = solution->right;
  } else {
    leftChld = solution->left;
    rightChld = solution->right;
  }
  SubDimension leftData(leftChld->order, leftChld->good);
  SubDimension rightData(rightChld->order, rightChld->good);
  gTree.addChildren(nodeIdx, leftData, rightData);
  return recursiveCopy2Tree(gTree, gTree.leftChildIdx(nodeIdx), leftChld) +
         recursiveCopy2Tree(gTree, gTree.rightChildIdx(nodeIdx), rightChld);
}

// A recursive procedure for computing the e exponent values
static void computeEvalues(const OneGeneratorTree& T, long idx, long genOrd)
{
  // if either child is missing then we are at a leaf (this is a full tree)
  long left = T[idx].getLeftChild();
  long right = T[idx].getRightChild();
  if (left < 0 || right < 0)
    return;

  SubDimension& lData = (SubDimension&)T[left].getData();
  SubDimension& rData = (SubDimension&)T[right].getData();

  // The entire tree size is sz1 * sz2;
  long sz1 = lData.size; // size of left subtree
  long sz2 = rData.size; // size of right subtree

  long ee = T[idx].getData().e;
  // If right tree is bad, copy e from parent to right and scale left
  if (!rData.good) {
    rData.e = ee;
    lData.e = ee * sz2;
  }
  // If right tree is good and left is bad, copy parent to left and scale right
  else if (!lData.good) {
    lData.e = ee;
    rData.e = ee * sz1;
  }
  // If both are good, scale both using CRT coefficients (assuming GCD==1)
  else {
    long f1 = CRTcoeff(sz1, sz2); // f1 = 0 mod sz1, 1 mod sz2
    long f2 = sz1 * sz2 + 1 - f1; // f2 = 1 mod sz1, 0 mod sz2
    lData.e = NTL::MulMod(ee, f2, genOrd);
    rData.e = NTL::MulMod(ee, f1, genOrd);
  }
  // Recurse on the two subtrees
  computeEvalues(T, left, genOrd);
  computeEvalues(T, right, genOrd);
}

// Copy data from a SplitNode tree to a OneGeneratorTree
static long copyToGenTree(OneGeneratorTree& gTree, SplitNodePtr& solution)
{
  SubDimension rootData(solution->order, solution->good, /*e=*/1);
  gTree.putDataInRoot(rootData);
  long len = recursiveCopy2Tree(gTree, gTree.rootIdx(), solution);
  computeEvalues(gTree, gTree.rootIdx(), solution->order);
  return len;
}

// Compute the trees corresponding to the "optimal" way of breaking
// a permutation into dimensions, subject to some constraints
long GeneratorTrees::buildOptimalTrees(const NTL::Vec<GenDescriptor>& gens,
                                       long depthBound)
{
  // TODO: is this check necessary?
  assertTrue<InvalidArgument>(gens.length() >= 0, "negative gens size");
  trees.SetLength(gens.length()); // allocate space if needed

  if (gens.length() == 0) {
    map2cube.SetLength(1, 0);
    map2array.SetLength(1, 0);
    return 0;
  }
  assertTrue<InvalidArgument>(depthBound > 0, "Zero or negative depthBound");

  // reset the trees, starting from only the roots
  for (long i = 0; i < trees.length(); i++) {
    if (trees[i].getNleaves() > 1) // tree is not empty/trivial
      trees[i].collapseToRoot();
  }

  UpperMemoTable upperMemoTable;
  LowerMemoTable lowerMemoTable;

  // Compute a solution in { t.cost, t.solution }
  UpperMemoEntry t =
      optimalUpperAux(gens, 0, depthBound, 1, upperMemoTable, lowerMemoTable);

  // Copy the solution into the trees
  GenNodePtr midPtr;
  long i = 0, treeIdx = 0, midIdx = 0;
  depth = 0; // Also compute the depth of the permutation network
  for (GenNodePtr genPtr = t.solution; genPtr != nullptr;
       genPtr = genPtr->next, i++) {
    if (genPtr->solution->mid) { // Keep the "middle tree" for last
      midPtr = genPtr;
      midIdx = i;
      continue;
    }
    depth += copyToGenTree(trees[treeIdx], genPtr->solution);
    trees[treeIdx].setAuxKey(gens[i].genIdx);
    treeIdx++;
  }
  if (!midPtr) {
    // no solution, undo initialization and return
    // NTL_MAX_LONG

    depth = 0;
    trees.kill();
    map2cube.kill();
    map2array.kill();
    return NTL_MAX_LONG;
  }

  depth += copyToGenTree(trees[treeIdx], midPtr->solution);
  trees[treeIdx].setAuxKey(gens[midIdx].genIdx);

  // Compute the mapping from array to cube and back
  ComputeCubeMapping();

#ifdef HELIB_DEBUG
  NTL::Vec<long> dims; // The "crude" cube dimensions, one dimension per tree
  getCubeDims(dims);
  std::cerr << " dims=" << dims << std::endl;
  std::cerr << " trees=" << *this << std::endl;
  if (map2cube.length() < 100) {
    std::cerr << " map2cube=" << map2cube << std::endl;
    std::cerr << " map2array=" << map2array << std::endl;
  }
  std::cerr << std::endl;
#endif

  return t.cost;
}

} // namespace helib

max_stars_repo_name: TomMD/HElib

max_issues_repo_name: TomMD/HElib

max_forks_repo_name: TomMD/HElib


text:
#define BOOST_TEST_MAIN
#define BOOST_TEST_DYN_LINK

#include <string>
#include <boost/test/unit_test.hpp>
#include "soa/service/http_header.h"

using namespace std;

/* Ensure that long long/int64 header content-length are supported */
BOOST_AUTO_TEST_CASE(test_http_header_long_long)
{
    Datacratic::HttpHeader header;

    string response = ("HTTP/1.1 200 OK\r\n"
                       "x-amz-id-2: a4KTwfjQazJISfG4fout1ZGxh8zT9okHNw+x0IK9yeOf13sfBCPWaTU9NVX9UYDe\r\n"
                       "x-amz-request-id: 5C7BFD14CC6988A3\r\n"
                       "Date: Tue, 03 Jun 2014 12:19:58 GMT\r\n"
                       "Last-Modified: Tue, 03 Jun 2014 02:55:25 GMT\r\n"
                       "ETag: \"0d24e1a5d399439dcf60907de62101e8-173\"\r\n"
                       "Accept-Ranges: bytes\r\n"
                       "Content-Type: binary/octet-stream\r\n"
                       "Content-Length: 10893368309\r\n"
                       "Server: AmazonS3\r\n"
                       "\r\n");
    header.parse(response, false);

    BOOST_CHECK_EQUAL(header.contentLength, 10893368309);
}

/* query parsing */

BOOST_AUTO_TEST_CASE(test_http_header_query_parser_no_query)
{
    const std::string query = "GET /bid? HTTP/1.1\r\n"
                              "\r\n";
    Datacratic::HttpHeader header;
    header.parse(query);
}

BOOST_AUTO_TEST_CASE(test_http_header_query_parser_no_var)
{
    const std::string query = "GET /bid?& HTTP/1.1\r\n"
                              "\r\n";
    Datacratic::HttpHeader header;
    header.parse(query);
}

namespace {

Datacratic::HttpHeader generateParser(const std::string& q)
{

    const std::string query = "GET " + q + " HTTP/1.1\r\n\r\n";
    Datacratic::HttpHeader parser;
    parser.parse(query);
    return std::move(parser);
}

void testQueryParam(const Datacratic::HttpHeader& header,
                    const std::string& var,
                    const std::string& expectedValue)
{
    auto const& val = header.queryParams.getValue(var);
    BOOST_CHECK_EQUAL(val, expectedValue);
}
} // namespace

// From Google url
BOOST_AUTO_TEST_CASE(test_http_header_query_parser_g1)
{
    auto header = generateParser("/?arg1=1&arg2=2&bar");

    testQueryParam(header, "arg1", "1");
    testQueryParam(header, "arg2", "2");
    testQueryParam(header, "bar", "");
}

BOOST_AUTO_TEST_CASE(test_http_header_query_parser_g2)
{
    // Empty param at the end.
    auto parser = generateParser("/?foo=bar&");
    testQueryParam(parser, "foo", "bar");
}

BOOST_AUTO_TEST_CASE(test_http_header_query_parser_g3)
{
    // Empty param at the beginning.
    auto parser = generateParser("/?&foo=bar");
    testQueryParam(parser, "", "");
    testQueryParam(parser, "foo", "bar");
}

BOOST_AUTO_TEST_CASE(test_http_header_query_parser_g4)
{
    // Empty key with value.
    auto parser = generateParser("http://www.google.com?=foo");
    testQueryParam(parser, "", "foo");
}

BOOST_AUTO_TEST_CASE(test_http_header_query_parser_g5)
{
    // Empty value with key.
    auto parser = generateParser("/?foo=");
    testQueryParam(parser, "foo", "");
}

BOOST_AUTO_TEST_CASE(test_http_header_query_parser_g6)
{
    // Empty key and values.
    auto parser = generateParser("/?&&==&=");
    BOOST_CHECK_EQUAL(parser.queryParams[0].second, "");
    BOOST_CHECK_EQUAL(parser.queryParams[1].second, "");
    BOOST_CHECK_EQUAL(parser.queryParams[2].second, "=");
    BOOST_CHECK_EQUAL(parser.queryParams[3].second, "");
}

BOOST_AUTO_TEST_CASE(test_http_header_space_as_plus)
{
    auto header = generateParser("/?arg1=1+2");

    testQueryParam(header, "arg1", "1 2");
}

ext: cc

max_stars_repo_name: etnrlz/rtbkit

max_issues_repo_name: TuanTranEngineer/rtbkit

max_forks_repo_name: TuanTranEngineer/rtbkit


text:
///
/// @file t_split_ustr.cpp
/// @brief test splitting UString into group/attribute values
/// @author Jun Jiang <jun.jiang@izenesoft.com>
/// @date Created 2011-08-17
///

#include <util/ustring/UString.h>
#include <mining-manager/util/split_ustr.h>

#include <boost/test/unit_test.hpp>

#include <string>
#include <vector>

using namespace std;
using namespace boost;
using namespace sf1r;

namespace
{
const izenelib::util::UString::EncodingType ENCODING_TYPE = izenelib::util::UString::UTF_8;

void checkGroupPaths(
    const vector<vector<izenelib::util::UString> >& groupPaths,
    const vector<vector<string> >& goldGroupPaths
)
{
    BOOST_CHECK_EQUAL(groupPaths.size(), goldGroupPaths.size());
    for (unsigned int i = 0; i < groupPaths.size(); ++i)
    {
        const vector<izenelib::util::UString>& path = groupPaths[i];
        const vector<string>& goldPath = goldGroupPaths[i];
        BOOST_CHECK_EQUAL(path.size(), goldPath.size());

        for (unsigned int j = 0; j < path.size(); ++j)
        {
            std::string valueUtf8;
            path[j].convertString(valueUtf8, ENCODING_TYPE);
            BOOST_CHECK_EQUAL(valueUtf8, goldPath[j]);
        }
    }
}

typedef pair<string, vector<string> > AttrPairStr;
void checkAttrPairs(
    const vector<AttrPair>& attrPairs,
    const vector<AttrPairStr>& goldAttrPairs
)
{
    BOOST_CHECK_EQUAL(attrPairs.size(), goldAttrPairs.size());
    for (unsigned int i = 0; i < attrPairs.size(); ++i)
    {
        std::string nameUtf8;
        attrPairs[i].first.convertString(nameUtf8, ENCODING_TYPE);
        BOOST_CHECK_EQUAL(nameUtf8, goldAttrPairs[i].first);

        BOOST_CHECK_EQUAL(attrPairs[i].second.size(), goldAttrPairs[i].second.size());
        for (unsigned int j = 0; j < attrPairs[i].second.size(); ++j)
        {
            std::string valueUtf8;
            attrPairs[i].second[j].convertString(valueUtf8, ENCODING_TYPE);
            BOOST_CHECK_EQUAL(valueUtf8, goldAttrPairs[i].second[j]);
        }
    }
}

}

BOOST_AUTO_TEST_SUITE(split_ustr_test)

BOOST_AUTO_TEST_CASE(split_group)
{
    {
        izenelib::util::UString src("", ENCODING_TYPE);
        vector<vector<izenelib::util::UString> > groupPaths;
        split_group_path(src, groupPaths);
        BOOST_CHECK_EQUAL(groupPaths.size(), 0U);
    }

    {
        izenelib::util::UString src(",,,;,;;,", ENCODING_TYPE);
        vector<vector<izenelib::util::UString> > groupPaths;
        split_group_path(src, groupPaths);
        BOOST_CHECK_EQUAL(groupPaths.size(), 0U);
    }

    {
        izenelib::util::UString src("a,b,c", ENCODING_TYPE);
        vector<vector<izenelib::util::UString> > groupPaths;
        split_group_path(src, groupPaths);

        vector<vector<string> > goldGroupPaths;
        goldGroupPaths.push_back(vector<string>());
        goldGroupPaths.back().push_back("a");
        goldGroupPaths.push_back(vector<string>());
        goldGroupPaths.back().push_back("b");
        goldGroupPaths.push_back(vector<string>());
        goldGroupPaths.back().push_back("c");

        checkGroupPaths(groupPaths, goldGroupPaths);
    }

    {
        izenelib::util::UString src("a;b;c", ENCODING_TYPE);
        vector<vector<izenelib::util::UString> > groupPaths;
        split_group_path(src, groupPaths);

        vector<vector<string> > goldGroupPaths;
        goldGroupPaths.push_back(vector<string>());
        goldGroupPaths.back().push_back("a");
        goldGroupPaths.push_back(vector<string>());
        goldGroupPaths.back().push_back("b");
        goldGroupPaths.push_back(vector<string>());
        goldGroupPaths.back().push_back("c");

        checkGroupPaths(groupPaths, goldGroupPaths);
    }

    {
        izenelib::util::UString src("A>B>C,D>E>F", ENCODING_TYPE);
        vector<vector<izenelib::util::UString> > groupPaths;
        split_group_path(src, groupPaths);

        vector<vector<string> > goldGroupPaths;
        goldGroupPaths.push_back(vector<string>());
        goldGroupPaths.back().push_back("A");
        goldGroupPaths.back().push_back("B");
        goldGroupPaths.back().push_back("C");
        goldGroupPaths.push_back(vector<string>());
        goldGroupPaths.back().push_back("D");
        goldGroupPaths.back().push_back("E");
        goldGroupPaths.back().push_back("F");

        checkGroupPaths(groupPaths, goldGroupPaths);
    }

    {
        izenelib::util::UString src("创意生活,电脑办公>网络设备  ,手机数码> 手机通讯>手机;\"John, Mark\">\"1+1>2\">\"\"\"Mary\"\"\"   ,,,,,", ENCODING_TYPE);
        vector<vector<izenelib::util::UString> > groupPaths;
        split_group_path(src, groupPaths);

        vector<vector<string> > goldGroupPaths;
        goldGroupPaths.push_back(vector<string>());
        goldGroupPaths.back().push_back("创意生活");
        goldGroupPaths.push_back(vector<string>());
        goldGroupPaths.back().push_back("电脑办公");
        goldGroupPaths.back().push_back("网络设备");
        goldGroupPaths.push_back(vector<string>());
        goldGroupPaths.back().push_back("手机数码");
        goldGroupPaths.back().push_back("手机通讯");
        goldGroupPaths.back().push_back("手机");
        goldGroupPaths.push_back(vector<string>());
        goldGroupPaths.back().push_back("John, Mark");
        goldGroupPaths.back().push_back("1+1>2");
        goldGroupPaths.back().push_back("\"Mary\"");

        checkGroupPaths(groupPaths, goldGroupPaths);
    }
}

BOOST_AUTO_TEST_CASE(split_attr)
{
    {
        izenelib::util::UString src(",,:,", ENCODING_TYPE);
        vector<AttrPair> attrPairs;
        split_attr_pair(src, attrPairs);
        BOOST_CHECK_EQUAL(attrPairs.size(), 0U);
    }

    {
        izenelib::util::UString src("abcde:", ENCODING_TYPE);
        vector<AttrPair> attrPairs;
        split_attr_pair(src, attrPairs);
        BOOST_CHECK_EQUAL(attrPairs.size(), 0U);
    }

    {
        izenelib::util::UString src("A:a,B:b,C:c", ENCODING_TYPE);
        vector<AttrPair> attrPairs;
        split_attr_pair(src, attrPairs);

        vector<AttrPairStr> goldAttrPairs;
        {
            AttrPairStr pairStr;
            pairStr.first = "A";
            pairStr.second.push_back("a");
            goldAttrPairs.push_back(pairStr);
        }
        {
            AttrPairStr pairStr;
            pairStr.first = "B";
            pairStr.second.push_back("b");
            goldAttrPairs.push_back(pairStr);
        }
        {
            AttrPairStr pairStr;
            pairStr.first = "C";
            pairStr.second.push_back("c");
            goldAttrPairs.push_back(pairStr);
        }

        checkAttrPairs(attrPairs, goldAttrPairs);
    }

    {
        izenelib::util::UString src("品牌: Two In One/欧艾尼 ,英文名:\"John, \nMark: \"\"Mary\"\" | Tom\",领子:圆领,季节:春季|\"夏|季\" abc |秋季,年份:2011,尺码:S|\" M \"| L|XL  ,,,:,,", ENCODING_TYPE);
        vector<AttrPair> attrPairs;
        split_attr_pair(src, attrPairs);

        vector<AttrPairStr> goldAttrPairs;
        {
            AttrPairStr pairStr;
            pairStr.first = "品牌";
            pairStr.second.push_back("Two In One/欧艾尼");
            goldAttrPairs.push_back(pairStr);
        }
        {
            AttrPairStr pairStr;
            pairStr.first = "英文名";
            pairStr.second.push_back("John, \nMark: \"Mary\" | Tom");
            goldAttrPairs.push_back(pairStr);
        }
        {
            AttrPairStr pairStr;
            pairStr.first = "领子";
            pairStr.second.push_back("圆领");
            goldAttrPairs.push_back(pairStr);
        }
        {
            AttrPairStr pairStr;
            pairStr.first = "季节";
            pairStr.second.push_back("春季");
            pairStr.second.push_back("夏|季");
            pairStr.second.push_back("秋季");
            goldAttrPairs.push_back(pairStr);
        }
        {
            AttrPairStr pairStr;
            pairStr.first = "年份";
            pairStr.second.push_back("2011");
            goldAttrPairs.push_back(pairStr);
        }
        {
            AttrPairStr pairStr;
            pairStr.first = "尺码";
            pairStr.second.push_back("S");
            pairStr.second.push_back(" M ");
            pairStr.second.push_back("L");
            pairStr.second.push_back("XL");
            goldAttrPairs.push_back(pairStr);
        }

        checkAttrPairs(attrPairs, goldAttrPairs);
    }
}

BOOST_AUTO_TEST_SUITE_END()


text:
/// FUSE interface.
///
/// @file

#pragma once
#ifndef FUSE_HPP__EFM7PVEH
#define FUSE_HPP__EFM7PVEH

#include <thread>

#include "rewofs/disablewarnings.hpp"
#include <boost/noncopyable.hpp>
#define FUSE_USE_VERSION 32
#include <fuse3/fuse.h>
#include "rewofs/enablewarnings.hpp"

#include "rewofs/client/vfs.hpp"

//==========================================================================
namespace rewofs::client {
//==========================================================================

class Fuse : private boost::noncopyable
{
public:
    Fuse(IVfs& vfs);

    Fuse(const Fuse& vfs) = delete;
    Fuse& operator=(const Fuse& vfs) = delete;

    void set_mountpoint(const std::string& path);
    void start();
    void stop();
    void wait();

private:
    void run();

    IVfs& m_vfs;

    std::string m_mountpoint{};
    std::thread m_thread{};
    fuse* m_fuse{};
};

//==========================================================================
} // namespace rewofs::client

#endif /* include guard */

ext: hpp

max_stars_repo_name: dsiroky/rewofs

max_issues_repo_name: dsiroky/rewofs

max_forks_repo_name: dsiroky/rewofs


text:
#ifndef BOOST_DESCRIBE_MODIFIERS_HPP_INCLUDED
#define BOOST_DESCRIBE_MODIFIERS_HPP_INCLUDED

// Copyright 2020 Peter Dimov
// Distributed under the Boost Software License, Version 1.0.
// https://www.boost.org/LICENSE_1_0.txt

#include <boost/describe/enum.hpp>

namespace boost
{
namespace describe
{

enum modifiers
{
    mod_public = 1,
    mod_protected = 2,
    mod_private = 4,
    mod_virtual = 8,
    mod_static = 16,
    mod_function = 32,
    mod_any_member = 64,
    mod_inherited = 128,
    mod_hidden = 256,
};

BOOST_DESCRIBE_ENUM(modifiers,
    mod_public,
    mod_protected,
    mod_private,
    mod_virtual,
    mod_static,
    mod_function,
    mod_any_member,
    mod_inherited,
    mod_hidden);

BOOST_DESCRIBE_CONSTEXPR_OR_CONST modifiers mod_any_access = static_cast<modifiers>( mod_public | mod_protected | mod_private );

} // namespace describe
} // namespace boost

#endif // #ifndef BOOST_DESCRIBE_MODIFIERS_HPP_INCLUDED


text: #include <boost/spirit/home/support/lazy.hpp>

max_stars_repo_name: miathedev/BoostForArduino

max_issues_repo_name: miathedev/BoostForArduino

max_forks_repo_name: miathedev/BoostForArduino


text:
#include <dirent.h>
#include <stdio.h>

#include <fstream>
#include <iostream>

#include <boost/test/unit_test.hpp>

#include "paths.hpp"

#include "antlr4-runtime.h"
#include "antlr4/QueryErrorHandler.hpp"
#include "antlr4/generated/QueryLexer.h"
#include "antlr4/generated/QueryParser.h"
#include "antlr4/parse.hpp"

#include "netspeak/Dictionaries.hpp"
#include "netspeak/error.hpp"

using namespace antlr4;

BOOST_AUTO_TEST_CASE(test_detection) {
  std::string path(test::QUERIES_DIR);

  DIR *dir = opendir(path.c_str());

  if (dir == NULL) {
    std::cerr << "no such directory" << std::endl;
    return;
  }
  struct dirent *pdir;

  std::vector<std::string> files;

  while ((pdir = readdir(dir)) != NULL) {
    files.push_back(path + "/" + pdir->d_name);
  }
  closedir(dir);
  for (auto file = files.begin(); file != files.end(); file++) {
    std::ifstream inputStream(*file, std::ios::in);

    while (inputStream.peek() != -1) {
      std::string read;
      std::getline(inputStream, read);

      size_t pos = read.find("\t");
      std::string query = read.substr(0, pos);
      std::string expected = read.substr(pos + 4, read.size());

      antlr4::ANTLRInputStream input(query);
      QueryLexer lexer(&input);
      antlr4::CommonTokenStream tokens(&lexer);
      QueryParser parser(&tokens);

      antlr4::QueryErrorHandler error_handler;
      parser.removeErrorListeners();
      parser.addErrorListener(&error_handler);

      std::string actual;
      try {
        antlr4::tree::ParseTree *tree = parser.query();
        actual = tree->toStringTree(&parser);
      } catch (...) {
        actual = "FAIL";
      }

      BOOST_REQUIRE_EQUAL(actual, expected);

      if (actual != "FAIL") {
        // it's a valid query, so let's test the parse method
        BOOST_REQUIRE_NO_THROW(antlr4::parse_query(query));
      }
    }
    inputStream.close();
  }
}


text:
/**
 * Copyright Soramitsu Co., Ltd. All Rights Reserved.
 * SPDX-License-Identifier: Apache-2.0
 */

#ifndef KAGOME_NODE_IMPL_HPP
#define KAGOME_NODE_IMPL_HPP

#include <boost/optional.hpp>

#include "common/blob.hpp"
#include "common/buffer.hpp"
#include "storage/trie/node.hpp"

namespace kagome::storage::trie {

  /**
   * For specification see
   * https://github.com/w3f/polkadot-re-spec/blob/master/polkadot_re_spec.pdf
   * 5.3 The Trie structure
   */

  struct PolkadotNode : public Node {
    PolkadotNode() = default;
    PolkadotNode(common::Buffer key_nibbles,
                 boost::optional<common::Buffer> value)
        : key_nibbles{std::move(key_nibbles)}, value{std::move(value)} {}

    ~PolkadotNode() override = default;

    enum class Type {
      Special = 0b00,
      Leaf = 0b01,
      BranchEmptyValue = 0b10,
      BranchWithValue = 0b11
    };

    // dummy nodes are used to avoid unnecessary reads from the storage
    virtual bool isDummy() const = 0;

    // just to avoid static_casts every time you need a switch on a node type
    Type getTrieType() const {
      return static_cast<Type>(getType());
    }

    common::Buffer key_nibbles;
    boost::optional<common::Buffer> value;
  };

  struct BranchNode : public PolkadotNode {
    static constexpr int kMaxChildren = 16;

    BranchNode() = default;
    explicit BranchNode(common::Buffer key_nibbles,
                        boost::optional<common::Buffer> value = boost::none)
        : PolkadotNode{std::move(key_nibbles), std::move(value)} {}

    ~BranchNode() override = default;

    bool isDummy() const override {
      return false;
    }
    int getType() const override;

    uint16_t childrenBitmap() const;
    uint8_t childrenNum() const;

    // Has 1..16 children.
    // Stores their hashes to search for them in a storage and encode them more
    // easily.
    std::array<std::shared_ptr<PolkadotNode>, kMaxChildren> children;
  };

  struct LeafNode : public PolkadotNode {
    LeafNode() = default;
    LeafNode(common::Buffer key_nibbles, boost::optional<common::Buffer> value)
        : PolkadotNode{std::move(key_nibbles), std::move(value)} {}

    ~LeafNode() override = default;

    bool isDummy() const override {
      return false;
    }
    int getType() const override;
  };

  /**
   * Used in branch nodes to indicate that there is a node, but this node is not
   * interesting at the moment and need not be retrieved from the storage.
   */
  struct DummyNode : public PolkadotNode {
    /**
     * Constructs a dummy node
     * @param key a storage key, which is a hash of an encoded node according to
     * PolkaDot specification
     */
    explicit DummyNode(common::Buffer key) : db_key{std::move(key)} {}

    bool isDummy() const override {
      return true;
    }

    int getType() const override {
      // Special only because a node has to have a type. Actually this is not
      // the real node and the type of the underlying node is inaccessible
      // before reading from the storage
      return static_cast<int>(Type::Special);
    }

    common::Buffer db_key;
  };

}  // namespace kagome::storage::trie

#endif  // KAGOME_NODE_IMPL_HPP

max_stars_repo_name: Lederstrumpf/kagome

max_issues_repo_name: Lederstrumpf/kagome

max_forks_repo_name: Lederstrumpf/kagome