text:
// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you 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 "exec/orc-metadata-utils.h"

#include <boost/algorithm/string.hpp>

#include "util/debug-util.h"
#include "common/names.h"

using boost::algorithm::iequals;

namespace impala {

Status OrcSchemaResolver::ResolveColumn(const SchemaPath& col_path,
    const orc::Type** node, bool* pos_field, bool* missing_field) const {
  const ColumnType* table_col_type = nullptr;
  *node = root_;
  *pos_field = false;
  *missing_field = false;
  if (col_path.empty()) return Status::OK();
  SchemaPath table_path, file_path;
  TranslateColPaths(col_path, &table_path, &file_path);
  for (int i = 0; i < table_path.size(); ++i) {
    int table_idx = table_path[i];
    int file_idx = file_path[i];
    if (table_idx == -1 || file_idx == -1) {
      DCHECK_NE(table_idx, file_idx);
      if (table_idx == -1) {
        DCHECK_EQ(*node, root_);
        *node = (*node)->getSubtype(file_idx);
      } else {
        DCHECK(table_col_type == nullptr);
        table_col_type = &tbl_desc_.col_descs()[table_idx].type();
      }
      continue;
    }
    if (table_col_type == nullptr) {
      table_col_type = &tbl_desc_.col_descs()[table_idx].type();
    } else if (table_col_type->type == TYPE_ARRAY &&
        table_idx == SchemaPathConstants::ARRAY_POS) {
      // To materialize the positions, the ORC lib has to materialize the whole array
      // column.
      *pos_field = true;
      break;  // return *node as the ARRAY node
    } else {
      table_col_type = &table_col_type->children[table_idx];
    }

    if (file_idx >= (*node)->getSubtypeCount()) {
      *missing_field = true;
      return Status::OK();
    }
    *node = (*node)->getSubtype(file_idx);
    if (table_col_type->type == TYPE_ARRAY) {
      DCHECK_EQ(table_col_type->children.size(), 1);
      if ((*node)->getKind() != orc::TypeKind::LIST) {
        return Status(TErrorCode::ORC_NESTED_TYPE_MISMATCH, filename_,
            PrintPath(tbl_desc_, GetCanonicalSchemaPath(table_path, i)), "array",
            (*node)->toString());
      }
    } else if (table_col_type->type == TYPE_MAP) {
      DCHECK_EQ(table_col_type->children.size(), 2);
      if ((*node)->getKind() != orc::TypeKind::MAP) {
        return Status(TErrorCode::ORC_NESTED_TYPE_MISMATCH, filename_,
            PrintPath(tbl_desc_, GetCanonicalSchemaPath(table_path, i)), "map",
            (*node)->toString());
      }
    } else if (table_col_type->type == TYPE_STRUCT) {
      DCHECK_GT(table_col_type->children.size(), 0);
      if ((*node)->getKind() != orc::TypeKind::STRUCT) {
        return Status(TErrorCode::ORC_NESTED_TYPE_MISMATCH, filename_,
            PrintPath(tbl_desc_, GetCanonicalSchemaPath(table_path, i)), "struct",
            (*node)->toString());
      }
    } else {
      DCHECK(!table_col_type->IsComplexType());
      DCHECK_EQ(i, table_path.size() - 1);
      RETURN_IF_ERROR(ValidateType(*table_col_type, **node));
    }
  }
  return Status::OK();
}

SchemaPath OrcSchemaResolver::GetCanonicalSchemaPath(const SchemaPath& col_path,
    int last_idx) const {
  DCHECK_LT(last_idx, col_path.size());
  SchemaPath ret;
  ret.reserve(col_path.size());
  std::copy_if(col_path.begin(),
               col_path.begin() + last_idx + 1,
               std::back_inserter(ret),
               [](int i) { return i >= 0; });
  return ret;
}

void OrcSchemaResolver::TranslateColPaths(const SchemaPath& col_path,
    SchemaPath* table_col_path, SchemaPath* file_col_path) const {
  DCHECK(!col_path.empty());
  DCHECK(table_col_path != nullptr);
  DCHECK(file_col_path != nullptr);
  table_col_path->reserve(col_path.size() + 1);
  file_col_path->reserve(col_path.size() + 1);
  int first_idx = col_path[0];
  int num_part_cols = tbl_desc_.num_clustering_cols();
  int remaining_idx = 0;
  if (!is_table_full_acid_) {
    // Table is not full ACID. Only need to adjust partitioning columns.
    table_col_path->push_back(first_idx);
    file_col_path->push_back(first_idx - num_part_cols);
    remaining_idx = 1;
  } else if (is_file_full_acid_) {
    DCHECK(is_table_full_acid_);
    // Table is full ACID, and file is in full ACID format too. We need to do some
    // conversions since the Frontend table schema and file schema differs. See the
    // comment at the declaration of this function.
    if (first_idx == num_part_cols + ACID_FIELD_ROW) {
      // 'first_idx' refers to "row" column. Table definition doesn't have "row" column.
      table_col_path->push_back(-1);
      file_col_path->push_back(first_idx - num_part_cols);
      if (col_path.size() == 1 ) return;
      int second_idx = col_path[1];
      // Adjust table with num partitioning colums and the synthetic 'row__id' column.
      table_col_path->push_back(num_part_cols + 1 + second_idx);
      file_col_path->push_back(second_idx);
    } else {
      DCHECK_GE(first_idx, num_part_cols);
      // 'col_path' refers to the ACID columns. In table schema they are nested
      // under the synthetic 'row__id' column. 'row__id' is at index 'num_part_cols'.
      table_col_path->push_back(num_part_cols);
      file_col_path->push_back(-1);
      // The ACID column is under 'row__id' at index 'table_idx - num_part_cols'.
      int acid_col_idx = first_idx - num_part_cols;
      table_col_path->push_back(acid_col_idx);
      file_col_path->push_back(acid_col_idx);
    }
    remaining_idx = 2;
  } else if (!is_file_full_acid_) {
    DCHECK(is_table_full_acid_);
    // Table is full ACID, but file is in non-ACID format.
    if (first_idx == num_part_cols + ACID_FIELD_ROW) {
      if (col_path.size() == 1 ) return;
      // 'first_idx' refers to "row" column. Table definition doesn't have "row" column,
      // but neither the file schema here. We don't include it in the output paths.
      int second_idx = col_path[1];
      // Adjust table with num partitioning colums and the synthetic 'row__id' column.
      table_col_path->push_back(num_part_cols + 1 + second_idx);
      file_col_path->push_back(second_idx);
    } else {
      DCHECK_GE(first_idx, num_part_cols);
      // 'col_path' refers to the ACID columns. In table schema they are nested
      // under the synthetic 'row__id' column. 'row__id' is at index 'num_part_cols'.
      table_col_path->push_back(num_part_cols);
      file_col_path->push_back(-1);
      // The ACID column is under 'row__id' at index 'table_idx - num_part_cols'.
      int acid_col_idx = first_idx - num_part_cols;
      table_col_path->push_back(acid_col_idx);
      // ACID columns in original files should be considered as missing colums.
      file_col_path->push_back(std::numeric_limits<int>::max());
    }
    remaining_idx = 2;
  }
  // The rest of the path is unchanged.
  for (int i = remaining_idx; i < col_path.size(); ++i) {
    table_col_path->push_back(col_path[i]);
    file_col_path->push_back(col_path[i]);
  }
  DCHECK_EQ(table_col_path->size(), file_col_path->size());
}

Status OrcSchemaResolver::ValidateType(const ColumnType& type,
    const orc::Type& orc_type) const {
  switch (orc_type.getKind()) {
    case orc::TypeKind::BOOLEAN:
      if (type.type == TYPE_BOOLEAN) return Status::OK();
      break;
    case orc::TypeKind::BYTE:
      if (type.type == TYPE_TINYINT || type.type == TYPE_SMALLINT
          || type.type == TYPE_INT || type.type == TYPE_BIGINT) {
        return Status::OK();
      }
      break;
    case orc::TypeKind::SHORT:
      if (type.type == TYPE_SMALLINT || type.type == TYPE_INT
          || type.type == TYPE_BIGINT) {
        return Status::OK();
      }
      break;
    case orc::TypeKind::INT:
      if (type.type == TYPE_INT || type.type == TYPE_BIGINT) return Status::OK();
      break;
    case orc::TypeKind::LONG:
      if (type.type == TYPE_BIGINT) return Status::OK();
      break;
    case orc::TypeKind::FLOAT:
    case orc::TypeKind::DOUBLE:
      if (type.type == TYPE_FLOAT || type.type == TYPE_DOUBLE) return Status::OK();
      break;
    case orc::TypeKind::STRING:
    case orc::TypeKind::VARCHAR:
    case orc::TypeKind::CHAR:
      if (type.type == TYPE_STRING || type.type == TYPE_VARCHAR
          || type.type == TYPE_CHAR) {
        return Status::OK();
      }
      break;
    case orc::TypeKind::TIMESTAMP:
      if (type.type == TYPE_TIMESTAMP) return Status::OK();
      break;
    case orc::TypeKind::DECIMAL: {
      if (type.type != TYPE_DECIMAL || type.scale != orc_type.getScale()) break;
      bool overflow = false;
      int orc_precision = orc_type.getPrecision();
      if (orc_precision == 0 || orc_precision > ColumnType::MAX_DECIMAL8_PRECISION) {
        // For ORC decimals whose precision is larger than 18, its value can't fit into
        // an int64 (10^19 > 2^63). So we should use int128 (16 bytes) for this case.
        // The possible byte sizes for Impala decimals are 4, 8, 16.
        // We mark it as overflow if the target byte size is not 16.
        overflow = (type.GetByteSize() != 16);
      } else if (orc_type.getPrecision() > ColumnType::MAX_DECIMAL4_PRECISION) {
        // For ORC decimals whose precision <= 18 and > 9, int64 and int128 can fit them.
        // We only mark it as overflow if the target byte size is 4.
        overflow = (type.GetByteSize() == 4);
      }
      if (!overflow) return Status::OK();
      return Status(Substitute(
          "Column $0 in ORC file '$1' can't be truncated to table column $2",
          orc_type.toString(), filename_, type.DebugString()));
    }
    case orc::TypeKind::DATE:
      if (type.type == TYPE_DATE) return Status::OK();
      break;
    default: break;
  }
  return Status(Substitute(
      "Type mismatch: table column $0 is map to column $1 in ORC file '$2'",
      type.DebugString(), orc_type.toString(), filename_));
}

bool OrcSchemaResolver::IsAcidColumn(const SchemaPath& col_path) const {
  DCHECK(is_table_full_acid_);
  DCHECK(!is_file_full_acid_);
  int num_part_cols = tbl_desc_.num_clustering_cols();
  return col_path.size() == 1 &&
         col_path.front() >= num_part_cols && col_path.front() < num_part_cols + 5;
}

void OrcSchemaResolver::DetermineFullAcidSchema() {
  is_file_full_acid_ = false;
  if (root_->getKind() != orc::TypeKind::STRUCT) return;
  if (root_->getSubtypeCount() != 6) return;
  if (root_->getSubtype(0)->getKind() != orc::TypeKind::INT ||
      root_->getSubtype(1)->getKind() != orc::TypeKind::LONG ||
      root_->getSubtype(2)->getKind() != orc::TypeKind::INT ||
      root_->getSubtype(3)->getKind() != orc::TypeKind::LONG ||
      root_->getSubtype(4)->getKind() != orc::TypeKind::LONG ||
      root_->getSubtype(5)->getKind() != orc::TypeKind::STRUCT) {
    return;
  }
  if (!iequals(root_->getFieldName(0), "operation") ||
      !iequals(root_->getFieldName(1), "originaltransaction") ||
      !iequals(root_->getFieldName(2), "bucket") ||
      !iequals(root_->getFieldName(3), "rowid") ||
      !iequals(root_->getFieldName(4), "currenttransaction") ||
      !iequals(root_->getFieldName(5), "row")) {
    return;
  }
  is_file_full_acid_ = true;
}

} // namespace impala

ext: cc

max_stars_repo_name: ColdZoo/impala

max_issues_repo_name: ColdZoo/impala

max_forks_repo_name: ColdZoo/impala


text:
// Copyright (c) 2001 Ronald Garcia, Indiana University (garcia@osl.iu.edu)
// Andrew Lumsdaine, Indiana University (lums@osl.iu.edu).

// Distributed under the Boost Software License, Version 1.0.
// (See http://www.boost.org/LICENSE_1_0.txt)

#ifndef MEMORIA_BOOST_FILESYSTEM_UTF8_CODECVT_FACET_HPP
#define MEMORIA_BOOST_FILESYSTEM_UTF8_CODECVT_FACET_HPP

#include <memoria/filesystem/config.hpp>

#define BOOST_UTF8_BEGIN_NAMESPACE \
     namespace memoria { namespace filesystem { namespace detail {

#define BOOST_UTF8_END_NAMESPACE }}}

#define MEMORIA_BOOST_FILESYSTEM_DECL

#define BOOST_UTF8_DECL MEMORIA_BOOST_FILESYSTEM_DECL

#include <boost/detail/utf8_codecvt_facet.hpp>

#undef BOOST_UTF8_BEGIN_NAMESPACE
#undef BOOST_UTF8_END_NAMESPACE
#undef BOOST_UTF8_DECL

#endif

ext: hpp

max_stars_repo_name: victor-smirnov/memoria

max_issues_repo_name: victor-smirnov/memoria

max_forks_repo_name: victor-smirnov/memoria


text:
//==================================================================================================
/*!
  @file

    @copyright 2016 NumScale SAS

  Distributed under the Boost Software License, Version 1.0.
  (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
*/
//==================================================================================================
#ifndef BOOST_SIMD_FUNCTION_PEDANTIC_HPP_INCLUDED
#define BOOST_SIMD_FUNCTION_PEDANTIC_HPP_INCLUDED

#include <boost/simd/config.hpp>
#include <boost/simd/detail/decorator.hpp>
#include <boost/simd/detail/dispatch.hpp>
#if defined(DOXYGEN_ONLY)
namespace boost { namespace simd
{
  /*!
    @ingroup group-decorator

    calls a version of the functor
      that can do some agressive optimization at the cost of certain
      properties or corner cases of the original functor.

      These losses are of the `pedantic_math` kind.

    @par Header <boost/simd/function/pedantic.hpp>

    @par Semantic

    @code
    T r = pedantic_(func)(< func parameters >);
    @endcode

  **/
  template<typename T> auto pedantic_(T const& x) {}
} }
#endif

namespace boost { namespace simd
{
  struct pedantic_tag : decorator_<pedantic_tag>
  {
    using parent = decorator_<pedantic_tag>;
  };

  const detail::decorator<pedantic_tag> pedantic_ = {};
} }

#endif


text:
#include <algorithm>
#include <cfloat>
#include <cmath>
#include <iostream>
#include <list>
#include <map>
#include <string>
#include <thread>
#include <vector>
using namespace std;

#include "log.hpp"
#include "phoenixword.hpp"

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graphviz.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
    boost::no_property, boost::property<boost::edge_weight_t, float> > Graph;
typedef std::pair<int, int>                             Edge;
typedef boost::graph_traits<Graph>::vertex_descriptor   Vertex;

typedef std::tuple<string,double,double,string,string,string,int> LabelVertex;

struct sample_graph_writer {
  void operator()(std::ostream& out, int i) const {
    auto wordPair = labelVertex_.at(i);
    out << " [ label = <";
    out << "
";
    out << "
";
    out << "" << std::get<0>(wordPair) << "";
    out << "
";
    out << "
";
    out << "" << 1.0/std::get<1>(wordPair);
    out << " " << std::get<3>(wordPair);
    out << "";
    out << "
";
    out << "
";
    out << "" << std::get<1>(wordPair);
    out << " " << std::get<4>(wordPair);
    out  << "";
    out << "
";
    out << "
";
    out << "" << std::get<2>(wordPair);
    out << " " << std::get<5>(wordPair);
    out << "";
    out << "
";
    out << "
";
/*
    out << "" << std::get<0>(wordPair) << "";
    out << "
";
    out << "" << " " ;
    out << 1.0/(std::get<1>(wordPair)) << "
";
    out << std::get<1>(wordPair) << "
" ;
    out << std::get<2>(wordPair) << "";
*/
    out << ">]";
  }
  sample_graph_writer(vector<LabelVertex> &labelVertex):labelVertex_(labelVertex) {
  }
  vector<LabelVertex> &labelVertex_;
};

void PhoenixWord::calcPrediction(const multimap<int, WordElement> &confuse) {
  Graph g;
  multimap<int, std::tuple<string, Vertex,double,double>> vertexWator;
  vector<LabelVertex> labelVertex;

  auto vrtxStart = boost::add_vertex(g);
  auto vrtxPrStart = std::make_tuple("S", vrtxStart,1.0,1.0);
  vertexWator.insert(std::make_pair(-1, vrtxPrStart));
  labelVertex.push_back(std::make_tuple("S",1.0,1.0,"","","",-1));

  int posLast = 0;
  for (auto elem : confuse) {
    auto word = std::get<0>(elem.second);
    auto position = std::get<1>(elem.second);
    auto weight = std::get<3>(elem.second);
    auto weightO = std::get<4>(elem.second);
    auto vrtx = boost::add_vertex(g);
    auto vrtxPr = std::make_tuple(word, vrtx,weight,weightO);
    vertexWator.insert(std::make_pair(position, vrtxPr));
    labelVertex.push_back(std::make_tuple(word,weight,weightO,"","","",position));
    posLast = position + word.size();
  }
  auto vrtxEnd = add_vertex(g);
  auto vrtxPrvrtxEnd = std::make_tuple("E", vrtxEnd,1.0,1.0);
  vertexWator.insert(std::make_pair(posLast,vrtxPrvrtxEnd));
  labelVertex.push_back(std::make_tuple("E",1.0,1.0,"","","",-1));

  // add dummy start.
  {
    auto startPos = confuse.begin()->first;
    auto rangeSelf = vertexWator.equal_range(startPos);
    for (auto itSelf = rangeSelf.first; itSelf != rangeSelf.second; itSelf++) {
      auto wordSelf = std::get<0>(itSelf->second);
      auto vrtxSelf = std::get<1>(itSelf->second);
      auto weightR = std::get<2>(itSelf->second);
      auto weightRO = std::get<3>(itSelf->second);
      auto ed = boost::add_edge(vrtxStart, vrtxSelf,g);
      auto weightOld = boost::get(boost::edge_weight_t(), g, ed.first);
      boost::put(boost::edge_weight_t(), g, ed.first, 1.0/weightR);
      auto weightNew = boost::get(boost::edge_weight_t(), g, ed.first);
      TRACE_VAR(weightR,weightRO,weightOld,weightNew);
    }
  }

  for (auto elem : wordHintSeq_) {
    auto word = std::get<0>(elem.second);
    auto position = std::get<1>(elem.second);
    auto range = std::get<2>(elem.second);
    auto next = position + range;
    auto rangeSelf = vertexWator.equal_range(position);
    for (auto itSelf = rangeSelf.first; itSelf != rangeSelf.second; itSelf++) {
      auto wordSelf = std::get<0>(itSelf->second);
      auto vrtxSelf = std::get<1>(itSelf->second);
      auto weightR = std::get<2>(itSelf->second);
      auto weightRO = std::get<3>(itSelf->second);
      if (word == wordSelf) {
        auto rangeNext = vertexWator.equal_range(next);
        for (auto itNext = rangeNext.first; itNext != rangeNext.second;
             itNext++) {
          auto vrtxNext = std::get<1>(itNext->second);
          auto ed = boost::add_edge(vrtxSelf, vrtxNext,g);
          auto weightOld = boost::get(boost::edge_weight_t(), g, ed.first);
          boost::put(boost::edge_weight_t(), g, ed.first, 1.0/weightR);
          auto weightNew = boost::get(boost::edge_weight_t(), g, ed.first);
          TRACE_VAR(weightR,weightRO,weightOld,weightNew);
        }
        break;
      }
    }
    // add dummy end.
    if(posLast == position + range) {
      auto rangeSelf = vertexWator.equal_range(position);
      for (auto itSelf = rangeSelf.first; itSelf != rangeSelf.second; itSelf++) {
        auto wordSelf = std::get<0>(itSelf->second);
        auto vrtxSelf = std::get<1>(itSelf->second);
        if (word == wordSelf) {
          auto ed = boost::add_edge(vrtxSelf,vrtxEnd,g);
          auto weight = boost::get(boost::edge_weight_t(), g, ed.first);
          boost::put(boost::edge_weight_t(), g, ed.first, 0.0);
          auto weight2 = boost::get(boost::edge_weight_t(), g, ed.first);
          TRACE_VAR(weight,weight2);
          break;
        }
      }
    }
  }

  sample_graph_writer gw(labelVertex);

  std::stringstream ss;
  boost::write_graphviz(ss, g, gw);
  auto dotStr = ss.str();
  boost::algorithm::replace_all(
      dotStr, "digraph G {",
      "digraph G { \n rankdir=LR;\n graph [charset=\"UTF-8\"];\n");
  TRACE_VAR(dotStr);
  // dot -v -T svg 1.dot -o 1.svg

  TRACE_VAR(boost::num_vertices(g),vrtxStart,vrtxEnd);

  std::vector<Vertex> parents(boost::num_vertices(g));
  std::vector<float> distance(boost::num_vertices(g));

  auto predmap = boost::predecessor_map(boost::make_iterator_property_map(parents.begin(), boost::get(boost::vertex_index, g))).
                          distance_map(boost::make_iterator_property_map(distance.begin(), boost::get(boost::vertex_index, g)));

  boost::dijkstra_shortest_paths(g,vrtxStart,predmap);

  #if 0
  boost::graph_traits < Graph >::vertex_iterator vi, vend;
  for (boost::tie(vi, vend) = vertices(g); vi != vend; ++vi) {
    auto labelSelf = std::get<0>(labelVertex.at(*vi));
    auto labelParent = std::get<0>(labelVertex.at(parents[*vi]));
    std::cout << "distance(" << labelSelf << ") = " << distance[*vi] << ", ";
    std::cout << "parent(" << labelSelf << ") = " << labelParent << std::endl;
  }
  #endif

  TRACE_VAR(distance.at(vrtxEnd));

  if (parents[vrtxEnd] == vrtxEnd) {
    std::cout << "no path" << std::endl;
    return ;
  }
  std::vector<int> path;
  for(auto v = vrtxEnd; v != vrtxStart; v = parents[v]) {
    if(v != vrtxEnd) {
      path.push_back(v);
    }
  }
  for(auto it = path.rbegin();it != path.rend();it++) {
      auto wordSelected = std::get<0>(labelVertex.at(*it));
      auto positionSelected = std::get<6>(labelVertex.at(*it));
      TRACE_VAR(*it,wordSelected);
      for (auto elem : confuse) {
        auto word = std::get<0>(elem.second);
        auto position = std::get<1>(elem.second);
        if(word ==wordSelected && position == positionSelected) {
            wordSeqTopSelected_.insert(elem);
            break;
        }
      }
  }
}

#include <boost/uuid/uuid.hpp>
#include <boost/uuid/uuid_io.hpp>
#include <boost/uuid/uuid_generators.hpp>
#include <boost/lexical_cast.hpp>
#include <fstream>

string PhoenixWord::createGraph(const string &text,const string &sentence) {
  Graph g;
  multimap<int, std::tuple<string, Vertex,double,double>> vertexWator;
  vector<LabelVertex> labelVertex;

  auto vrtxStart = boost::add_vertex(g);
  auto vrtxPrStart = std::make_tuple("S", vrtxStart,1.0,1.0);
  vertexWator.insert(std::make_pair(-1, vrtxPrStart));
  labelVertex.push_back(std::make_tuple("S",1.0,1.0,"","","",-1));

  int posLast = 0;
  for (auto elem : wordAdjustedSeq_) {
    auto word = std::get<0>(elem.second);
    auto position = std::get<1>(elem.second);
    auto weight = std::get<3>(elem.second);
    auto weightO = std::get<4>(elem.second);
    auto vrtx = boost::add_vertex(g);
    auto vrtxPr = std::make_tuple(word, vrtx,weight,weightO);
    vertexWator.insert(std::make_pair(position, vrtxPr));
    labelVertex.push_back(std::make_tuple(word,weight,weightO,"","","",position));
    posLast = position + word.size();
  }
  auto vrtxEnd = add_vertex(g);
  auto vrtxPrvrtxEnd = std::make_tuple("E", vrtxEnd,1.0,1.0);
  vertexWator.insert(std::make_pair(posLast,vrtxPrvrtxEnd));
  labelVertex.push_back(std::make_tuple("E",1.0,1.0,"","","",-1));

  auto vrtxTitle = add_vertex(g);
  auto title = u8"input=【" + text + u8"】";
  auto vrtxPrvrtxTitle = std::make_tuple(title, vrtxTitle,0.0,0.0);
  vertexWator.insert(std::make_pair(posLast + 10,vrtxPrvrtxTitle));
  labelVertex.push_back(std::make_tuple(title,1.0,1.0,"distance : 1.0 / adjusted duplicate rate"
                                        ," adjusted duplicate rate:  duplicate rate* power(CONST, word length)"
                                        ,"duplicate rate : this word duplicate couter / max duplicate couter",-1));

  auto vrtxSentence = add_vertex(g);
  auto titleSentence = u8"output=【" + sentence + u8"】";
  auto vrtxPrvrtxvrtxSentence = std::make_tuple(titleSentence, vrtxSentence,0.0,0.0);
  vertexWator.insert(std::make_pair(posLast + 11,vrtxPrvrtxvrtxSentence));
  labelVertex.push_back(std::make_tuple(titleSentence,1.0,1.0,"---"
                                        ,"---"
                                        ,"---",-1));

  auto ed = boost::add_edge(vrtxTitle,vrtxSentence,g);

  // add dummy start.
  {
    auto startPos = wordAdjustedSeq_.begin()->first;
    auto rangeSelf = vertexWator.equal_range(startPos);
    for (auto itSelf = rangeSelf.first; itSelf != rangeSelf.second; itSelf++) {
      auto wordSelf = std::get<0>(itSelf->second);
      auto vrtxSelf = std::get<1>(itSelf->second);
      auto weightR = std::get<2>(itSelf->second);
      auto weightRO = std::get<3>(itSelf->second);
      auto ed = boost::add_edge(vrtxStart, vrtxSelf,g);
      auto weightOld = boost::get(boost::edge_weight_t(), g, ed.first);
      boost::put(boost::edge_weight_t(), g, ed.first, 1.0/weightR);
      auto weightNew = boost::get(boost::edge_weight_t(), g, ed.first);
      TRACE_VAR(weightR,weightRO,weightOld,weightNew);
    }
  }

  for (auto elem : wordAdjustedSeq_) {
    auto word = std::get<0>(elem.second);
    auto position = std::get<1>(elem.second);
    auto range = std::get<2>(elem.second);
    auto next = position + range;
    auto rangeSelf = vertexWator.equal_range(position);
    for (auto itSelf = rangeSelf.first; itSelf != rangeSelf.second; itSelf++) {
      auto wordSelf = std::get<0>(itSelf->second);
      auto vrtxSelf = std::get<1>(itSelf->second);
      auto weightR = std::get<2>(itSelf->second);
      auto weightRO = std::get<3>(itSelf->second);
      if (word == wordSelf) {
        auto rangeNext = vertexWator.equal_range(next);
        for (auto itNext = rangeNext.first; itNext != rangeNext.second;
             itNext++) {
          auto vrtxNext = std::get<1>(itNext->second);
          auto ed = boost::add_edge(vrtxSelf, vrtxNext,g);
          auto weightOld = boost::get(boost::edge_weight_t(), g, ed.first);
          boost::put(boost::edge_weight_t(), g, ed.first, 1.0/weightR);
          auto weightNew = boost::get(boost::edge_weight_t(), g, ed.first);
          TRACE_VAR(weightR,weightRO,weightOld,weightNew);
        }
        break;
      }
    }
    // add dummy end.
    if(posLast == position + range) {
      auto rangeSelf = vertexWator.equal_range(position);
      for (auto itSelf = rangeSelf.first; itSelf != rangeSelf.second; itSelf++) {
        auto wordSelf = std::get<0>(itSelf->second);
        auto vrtxSelf = std::get<1>(itSelf->second);
        if (word == wordSelf) {
          auto ed = boost::add_edge(vrtxSelf,vrtxEnd,g);
          auto weight = boost::get(boost::edge_weight_t(), g, ed.first);
          boost::put(boost::edge_weight_t(), g, ed.first, 0.0);
          auto weight2 = boost::get(boost::edge_weight_t(), g, ed.first);
          TRACE_VAR(weight,weight2);
          break;
        }
      }
    }
  }

  sample_graph_writer gw(labelVertex);

  std::stringstream ss;
  boost::write_graphviz(ss, g, gw);
  auto dotStr = ss.str();
  boost::algorithm::replace_all(
      dotStr, "digraph G {",
      "digraph G { \n rankdir=LR;\n graph [charset=\"UTF-8\"];\n");
  TRACE_VAR(dotStr);

  int prePost = -2;
  string oneSame;
  string allSame;
  int elemPost = 1;
  for (auto elem : wordAdjustedSeq_) {
      auto position = std::get<1>(elem.second);
      if(position == prePost) {
          oneSame += ";";
          oneSame += to_string(elemPost);
      } else {
          if(oneSame.empty()==false) {
              oneSame += "}\n";
              allSame += oneSame;
          }
          oneSame = "{rank = same;";
          oneSame += to_string(elemPost);
      }
      prePost = position;
      elemPost++;
  }
  TRACE_VAR(allSame);
  boost::algorithm::replace_all(
      dotStr, "}",
      allSame +"}");
  TRACE_VAR(dotStr);

  /*{rank = same; A; X;}*/

  auto id = boost::uuids::random_generator()();
  auto fileName = boost::lexical_cast<std::string>(id);
  ::system("mkdir -p /tmp/wator/wai/graph/");
  string pathDot = "/tmp/wator/wai/graph/" + fileName +".dot";
  std::ofstream outfile(pathDot,std::ofstream::binary);
  if(outfile.good()) {
    outfile << dotStr;
    outfile.close();
  }
  ::system("mkdir -p /watorvapor/autogen/wator/wai/graph/");
  {
      string dotCmd = "dot -v -T png ";
      dotCmd += pathDot;
      dotCmd += " -o ";
      dotCmd += "/watorvapor/autogen/wator/wai/graph/" + fileName +".png";
      ::system(dotCmd.c_str());
      // dot -v -T png 1.dot -o 1.png
  }
  {
      string dotCmd = "dot -v -T svg ";
      dotCmd += pathDot;
      dotCmd += " -o ";
      dotCmd += "/watorvapor/autogen/wator/wai/graph/" + fileName +".svg";
      ::system(dotCmd.c_str());
      // dot -v -T svg 1.dot -o 1.svg
  }

    string url("/autogen/wai/graph/");
    url += fileName +"";
    return url;
}

ext: cpp


text:
#include "baldr/graphtile.h"
#include "baldr/compression_utils.h"
#include "baldr/datetime.h"
#include "baldr/tilehierarchy.h"
#include "filesystem.h"
#include "midgard/aabb2.h"
#include "midgard/pointll.h"
#include "midgard/tiles.h"

#include <boost/algorithm/string.hpp>
#include <cmath>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <locale>
#include <string>
#include <vector>

using namespace valhalla::midgard;

namespace {
struct dir_facet : public std::numpunct<char> {
protected:
  virtual char do_thousands_sep() const {
    return '/';
  }

  virtual std::string do_grouping() const {
    return "\03";
  }
};
const std::locale dir_locale(std::locale("C"), new dir_facet());
const AABB2<PointLL> world_box(PointLL(-180, -90), PointLL(180, 90));
constexpr float COMPRESSION_HINT = 3.5f;
} // namespace

namespace valhalla {
namespace baldr {

// Default constructor
GraphTile::GraphTile()
    : header_(nullptr), nodes_(nullptr), directededges_(nullptr), ext_directededges_(nullptr),
      transitions_(nullptr), departures_(nullptr), transit_stops_(nullptr), transit_routes_(nullptr),
      transit_schedules_(nullptr), transit_transfers_(nullptr), access_restrictions_(nullptr),
      signs_(nullptr), admins_(nullptr), edge_bins_(nullptr), complex_restriction_forward_(nullptr),
      complex_restriction_reverse_(nullptr), edgeinfo_(nullptr), textlist_(nullptr),
      complex_restriction_forward_size_(0), complex_restriction_reverse_size_(0), edgeinfo_size_(0),
      textlist_size_(0), lane_connectivity_(nullptr), lane_connectivity_size_(0),
      turnlanes_(nullptr) {
}

// Constructor given a filename. Reads the graph data into memory.
GraphTile::GraphTile(const std::string& tile_dir, const GraphId& graphid) : header_(nullptr) {

  // Don't bother with invalid ids
  if (!graphid.Is_Valid() || graphid.level() > TileHierarchy::get_max_level() || tile_dir.empty()) {
    return;
  }

  // Open to the end of the file so we can immediately get size
  std::string file_location =
      tile_dir + filesystem::path::preferred_separator + FileSuffix(graphid.Tile_Base());
  std::ifstream file(file_location, std::ios::in | std::ios::binary | std::ios::ate);
  if (file.is_open()) {
    // Read binary file into memory. TODO - protect against failure to
    // allocate memory
    size_t filesize = file.tellg();
    graphtile_.reset(new std::vector<char>(filesize));
    file.seekg(0, std::ios::beg);
    file.read(graphtile_->data(), filesize);
    file.close();

    // Set pointers to internal data structures
    Initialize(graphid, graphtile_->data(), graphtile_->size());
  } else {
    // try to load a gzipped tile
    std::ifstream file(file_location + ".gz", std::ios::in | std::ios::binary | std::ios::ate);
    if (file.is_open()) {
      // read the compressed file into memory
      size_t filesize = file.tellg();
      file.seekg(0, std::ios::beg);
      std::vector<char> compressed(filesize);
      file.read(&compressed[0], filesize);
      file.close();

      // try to decompress it
      DecompressTile(graphid, compressed);
    }
  }
}

bool GraphTile::DecompressTile(const GraphId& graphid, std::vector<char>& compressed) {
  // for setting where to read compressed data from
  auto src_func = [&compressed](z_stream& s) -> void {
    s.next_in = static_cast<Byte*>(static_cast<void*>(compressed.data()));
    s.avail_in = static_cast<unsigned int>(compressed.size());
  };

  // for setting where to write the uncompressed data to
  graphtile_.reset(new std::vector<char>(0, 0));
  auto dst_func = [this, &compressed](z_stream& s) -> int {
    // if the whole buffer wasn't used we are done
    auto size = graphtile_->size();
    if (s.total_out < size)
      graphtile_->resize(s.total_out);
    // we need more space
    else {
      // assume we need 3.5x the space
      graphtile_->resize(size + (compressed.size() * COMPRESSION_HINT));
      // set the pointer to the next spot
      s.next_out = static_cast<Byte*>(static_cast<void*>(graphtile_->data() + size));
      s.avail_out = compressed.size() * COMPRESSION_HINT;
    }
    return Z_NO_FLUSH;
  };

  // Decompress tile into memory
  if (!baldr::inflate(src_func, dst_func)) {
    LOG_ERROR("Failed to gunzip " + FileSuffix(graphid, true));
    graphtile_.reset();
    return false;
  }

  // Set pointers to internal data structures
  Initialize(graphid, graphtile_->data(), graphtile_->size());
  return true;
}

GraphTile::GraphTile(const GraphId& graphid, char* ptr, size_t size) : header_(nullptr) {
  // Initialize the internal tile data structures using a pointer to the
  // tile and the tile size
  Initialize(graphid, ptr, size);
}

GraphTile GraphTile::CacheTileURL(const std::string& tile_url,
                                  const GraphId& graphid,
                                  curler_t& curler,
                                  bool gzipped,
                                  const std::string& cache_location) {
  // Don't bother with invalid ids
  if (!graphid.Is_Valid() || graphid.level() > TileHierarchy::get_max_level()) {
    return {};
  }

  // Get the response returned from curl, notice that when we expect zipped
  // we tell curl not to unzip it, so that we can store it on the disk unzipped
  auto suffix = FileSuffix(graphid.Tile_Base(), gzipped);
  auto uri = tile_url + '/' + suffix;
  long http_code;
  auto tile_data = curler(uri, http_code, false);

  // If its good try to use it
  if (http_code == 200) {
    // try to cache it on disk so we dont have to keep fetching it from url
    if (!cache_location.empty()) {
      auto disk_location = cache_location + filesystem::path::preferred_separator + suffix;
      auto dir = filesystem::path(cache_location + filesystem::path::preferred_separator + suffix);
      dir.replace_filename("");
      if (filesystem::create_directories(dir)) {
        std::ofstream file(disk_location, std::ios::out | std::ios::binary | std::ios::ate);
        file.write(&tile_data[0], tile_data.size());
      }
    }

    // turn the memory into a tile
    auto tile = GraphTile();
    if (gzipped) {
      tile.DecompressTile(graphid, tile_data);
    } // we dont need to decompress so just take ownership of the data
    else {
      tile.graphtile_.reset(new std::vector<char>(0, 0));
      *tile.graphtile_ = std::move(tile_data);
      tile.Initialize(graphid, tile.graphtile_->data(), tile.graphtile_->size());
    }

    return tile;
  }
  return {};
}

GraphTile::~GraphTile() {
}

// Set pointers to internal tile data structures
void GraphTile::Initialize(const GraphId& graphid, char* tile_ptr, const size_t tile_size) {
  char* ptr = tile_ptr;
  header_ = reinterpret_cast<GraphTileHeader*>(ptr);
  ptr += sizeof(GraphTileHeader);

  // TODO check version

  // Set a pointer to the node list
  nodes_ = reinterpret_cast<NodeInfo*>(ptr);
  ptr += header_->nodecount() * sizeof(NodeInfo);

  // Set a pointer to the node transition list
  transitions_ = reinterpret_cast<NodeTransition*>(ptr);
  ptr += header_->transitioncount() * sizeof(NodeTransition);

  // Set a pointer to the directed edge list
  directededges_ = reinterpret_cast<DirectedEdge*>(ptr);
  ptr += header_->directededgecount() * sizeof(DirectedEdge);

  // Extended directed edge attribution (if available).
  if (header_->has_ext_directededge()) {
    ext_directededges_ = reinterpret_cast<DirectedEdgeExt*>(ptr);
    ptr += header_->directededgecount() * sizeof(DirectedEdgeExt);
  }

  // Set a pointer access restriction list
  access_restrictions_ = reinterpret_cast<AccessRestriction*>(ptr);
  ptr += header_->access_restriction_count() * sizeof(AccessRestriction);

  // Set a pointer to the transit departure list
  departures_ = reinterpret_cast<TransitDeparture*>(ptr);
  ptr += header_->departurecount() * sizeof(TransitDeparture);

  // Set a pointer to the transit stop list
  transit_stops_ = reinterpret_cast<TransitStop*>(ptr);
  ptr += header_->stopcount() * sizeof(TransitStop);

  // Set a pointer to the transit route list
  transit_routes_ = reinterpret_cast<TransitRoute*>(ptr);
  ptr += header_->routecount() * sizeof(TransitRoute);

  // Set a pointer to the transit schedule list
  transit_schedules_ = reinterpret_cast<TransitSchedule*>(ptr);
  ptr += header_->schedulecount() * sizeof(TransitSchedule);

  // Set a pointer to the transit transfer list
  transit_transfers_ = reinterpret_cast<TransitTransfer*>(ptr);
  ptr += header_->transfercount() * sizeof(TransitTransfer);

  // Set a pointer to the sign list
  signs_ = reinterpret_cast<Sign*>(ptr);
  ptr += header_->signcount() * sizeof(Sign);

  // Start of turn lane data.
  turnlanes_ = reinterpret_cast<TurnLanes*>(ptr);
  ptr += header_->turnlane_count() * sizeof(TurnLanes);

  // Set a pointer to the admininstrative information list
  admins_ = reinterpret_cast<Admin*>(ptr);
  ptr += header_->admincount() * sizeof(Admin);

  // Set a pointer to the edge bin list
  edge_bins_ = reinterpret_cast<GraphId*>(ptr);

  // Start of forward restriction information and its size
  complex_restriction_forward_ = tile_ptr + header_->complex_restriction_forward_offset();
  complex_restriction_forward_size_ =
      header_->complex_restriction_reverse_offset() - header_->complex_restriction_forward_offset();

  // Start of reverse restriction information and its size
  complex_restriction_reverse_ = tile_ptr + header_->complex_restriction_reverse_offset();
  complex_restriction_reverse_size_ =
      header_->edgeinfo_offset() - header_->complex_restriction_reverse_offset();

  // Start of edge information and its size
  edgeinfo_ = tile_ptr + header_->edgeinfo_offset();
  edgeinfo_size_ = header_->textlist_offset() - header_->edgeinfo_offset();

  // Start of text list and its size
  textlist_ = tile_ptr + header_->textlist_offset();
  textlist_size_ = header_->lane_connectivity_offset() - header_->textlist_offset();

  // Start of lane connections and their size
  lane_connectivity_ =
      reinterpret_cast<LaneConnectivity*>(tile_ptr + header_->lane_connectivity_offset());
  lane_connectivity_size_ = header_->predictedspeeds_offset() - header_->lane_connectivity_offset();

  // Start of predicted speed data.
  if (header_->predictedspeeds_count() > 0) {
    char* ptr1 = tile_ptr + header_->predictedspeeds_offset();
    char* ptr2 = ptr1 + (header_->directededgecount() * sizeof(int32_t));
    predictedspeeds_.set_offset(reinterpret_cast<uint32_t*>(ptr1));
    predictedspeeds_.set_profiles(reinterpret_cast<int16_t*>(ptr2));

    lane_connectivity_size_ = header_->predictedspeeds_offset() - header_->lane_connectivity_offset();
  } else {
    lane_connectivity_size_ = header_->end_offset() - header_->lane_connectivity_offset();
  }

  // For reference - how to use the end offset to set size of an object (that
  // is not fixed size and count).
  // example_size_ = header_->end_offset() - header_->example_offset();

  // ANY NEW EXPANSION DATA GOES HERE

  // Associate one stop Ids for transit tiles
  if (graphid.level() == 3) {
    AssociateOneStopIds(graphid);
  }
}

// For transit tiles we need to save off the pair<tileid,lineid> lookup via
// onestop_ids.  This will be used for including or excluding transit lines
// for transit routes.  We save 2 maps because operators contain all of their
// route's tile_line pairs and it is used to include or exclude the operator
// as a whole. Also associates stops.
void GraphTile::AssociateOneStopIds(const GraphId& graphid) {
  // Associate stop Ids
  stop_one_stops.reserve(header_->stopcount());
  for (uint32_t i = 0; i < header_->stopcount(); i++) {
    const auto& stop = GetName(transit_stops_[i].one_stop_offset());
    stop_one_stops[stop] = {graphid.tileid(), graphid.level(), i};
  }

  // Associate route and operator Ids
  auto deps = GetTransitDepartures();
  for (auto const& dep : deps) {
    const auto* t = GetTransitRoute(dep.second->routeid());
    const auto& route_one_stop = GetName(t->one_stop_offset());
    auto stops = route_one_stops.find(route_one_stop);
    if (stops == route_one_stops.end()) {
      std::list<GraphId> tile_line_ids;
      tile_line_ids.emplace_back(graphid.tileid(), graphid.level(), dep.second->lineid());
      route_one_stops[route_one_stop] = tile_line_ids;
    } else {
      route_one_stops[route_one_stop].emplace_back(graphid.tileid(), graphid.level(),
                                                   dep.second->lineid());
    }

    // operators contain all of their route's tile_line pairs.
    const auto& op_one_stop = GetName(t->op_by_onestop_id_offset());
    stops = oper_one_stops.find(op_one_stop);
    if (stops == oper_one_stops.end()) {
      std::list<GraphId> tile_line_ids;
      tile_line_ids.emplace_back(graphid.tileid(), graphid.level(), dep.second->lineid());
      oper_one_stops[op_one_stop] = tile_line_ids;
    } else {
      oper_one_stops[op_one_stop].emplace_back(graphid.tileid(), graphid.level(),
                                               dep.second->lineid());
    }
  }
}

std::string GraphTile::FileSuffix(const GraphId& graphid, bool gzipped) {
  /*
  if you have a graphid where level == 8 and tileid == 24134109851 you should get:
  8/024/134/109/851.gph since the number of levels is likely to be very small this limits the total
  number of objects in any one directory to 1000 which is an empirically derived good choice for
  mechanical hard drives this should be fine for s3 as well (even though it breaks the rule of most
  unique part of filename first) because there will be just so few objects in general in practice
  */

  // figure the largest id for this level
  auto found = TileHierarchy::levels().find(graphid.level());
  if (found == TileHierarchy::levels().cend() &&
      graphid.level() != TileHierarchy::GetTransitLevel().level) {
    throw std::runtime_error("Could not compute FileSuffix for non-existent level: " +
                             std::to_string(graphid.level()));
  }

  // get the level info
  const auto& level = graphid.level() == TileHierarchy::GetTransitLevel().level
                          ? TileHierarchy::GetTransitLevel()
                          : found->second;

  // figure out how many digits
  auto max_id = level.tiles.ncolumns() * level.tiles.nrows() - 1;
  size_t max_length = static_cast<size_t>(std::log10(std::max(1, max_id))) + 1;
  const size_t remainder = max_length % 3;
  if (remainder) {
    max_length += 3 - remainder;
  }

  // make a locale to use as a formatter for numbers
  std::ostringstream stream;
  stream.imbue(dir_locale);

  // if it starts with a zero the pow trick doesn't work
  if (graphid.level() == 0) {
    stream << static_cast<uint32_t>(std::pow(10, max_length)) + graphid.tileid() << ".gph"
           << (gzipped ? ".gz" : "");
    std::string suffix = stream.str();
    suffix[0] = '0';
    return suffix;
  }
  // it was something else
  stream << graphid.level() * static_cast<uint32_t>(std::pow(10, max_length)) + graphid.tileid()
         << ".gph" << (gzipped ? ".gz" : "");
  return stream.str();
}

// Get the tile Id given the full path to the file.
GraphId GraphTile::GetTileId(const std::string& fname) {
  std::unordered_set<std::string::value_type> allowed{filesystem::path::preferred_separator,
                                                      '0',
                                                      '1',
                                                      '2',
                                                      '3',
                                                      '4',
                                                      '5',
                                                      '6',
                                                      '7',
                                                      '8',
                                                      '9'};
  // we require slashes
  auto pos = fname.find_last_of(filesystem::path::preferred_separator);
  if (pos == fname.npos) {
    throw std::runtime_error("Invalid tile path: " + fname);
  }

  // swallow numbers until you reach the end or a dot
  for (; pos < fname.size(); ++pos) {
    if (allowed.find(fname[pos]) == allowed.cend()) {
      break;
    }
  }
  allowed.erase(static_cast<std::string::value_type>(filesystem::path::preferred_separator));

  // if you didnt reach the end and it wasnt a dot then this isnt valid
  if (pos != fname.size() && fname[pos] != '.') {
    throw std::runtime_error("Invalid tile path: " + fname);
  }

  // run backwards while you find an allowed char but stop if not 3 digits between slashes
  std::vector<int> digits;
  auto last = pos;
  while (--pos < last) {
    auto c = fname[pos];
    // invalid char showed up
    if (allowed.find(c) == allowed.cend()) {
      throw std::runtime_error("Invalid tile path: " + fname);
    }

    // if its the last thing or the next one is a separator thats another digit
    if (pos == 0 || fname[pos - 1] == filesystem::path::preferred_separator) {
      // this is not 3 or 1 digits so its wrong
      auto dist = last - pos;
      if (dist != 3 && dist != 1) {
        throw std::runtime_error("Invalid tile path: " + fname);
      }
      // we'll keep this
      auto i = atoi(fname.substr(pos, dist).c_str());
      digits.push_back(i);
      // and we'll stop if it was the level (always a single digit see GraphId)
      if (dist == 1) {
        break;
      }
      // next
      last = --pos;
    }
  }

  // if the first thing isnt a valid level bail
  auto found = TileHierarchy::levels().find(digits.back());
  if (found == TileHierarchy::levels().cend() &&
      digits.back() != TileHierarchy::GetTransitLevel().level) {
    throw std::runtime_error("Invalid tile path: " + fname);
  }

  // get the level info
  uint32_t level = digits.back();
  digits.pop_back();
  const auto& tile_level = level == TileHierarchy::GetTransitLevel().level
                               ? TileHierarchy::GetTransitLevel()
                               : found->second;

  // get the number of sub directories that we should have
  auto max_id = tile_level.tiles.ncolumns() * tile_level.tiles.nrows() - 1;
  size_t parts = static_cast<size_t>(std::log10(std::max(1, max_id))) + 1;
  if (parts % 3 != 0) {
    parts += 3 - (parts % 3);
  }
  parts /= 3;

  // bail if its the wrong number of sub dirs
  if (digits.size() != parts) {
    throw std::runtime_error("Invalid tile path: " + fname);
  }

  // parse the id of the tile
  int multiplier = 1;
  uint32_t id = 0;
  for (auto digit : digits) {
    id += digit * multiplier;
    multiplier *= 1000;
  }

  // if after parsing them the number is out of bounds bail
  if (id > max_id) {
    throw std::runtime_error("Invalid tile path: " + fname);
  }

  // you've passed the test enjoy your id
  return {id, level, 0};
}

// Get the bounding box of this graph tile.
AABB2<PointLL> GraphTile::BoundingBox() const {

  // figure the largest id for this level
  auto level = TileHierarchy::levels().find(header_->graphid().level());
  if (level == TileHierarchy::levels().end() &&
      header_->graphid().level() == ((TileHierarchy::levels().rbegin())->second.level + 1)) {
    level = TileHierarchy::levels().begin();
  }

  auto tiles = level->second.tiles;
  return tiles.TileBounds(header_->graphid().tileid());
}

iterable_t<const DirectedEdge> GraphTile::GetDirectedEdges(const GraphId& node) const {
  if (node.id() < header_->nodecount()) {
    const auto& nodeinfo = nodes_[node.id()];
    const auto* edge = directededge(nodeinfo.edge_index());
    return iterable_t<const DirectedEdge>{edge, nodeinfo.edge_count()};
  }
  throw std::runtime_error(
      "GraphTile NodeInfo index out of bounds: " + std::to_string(node.tileid()) + "," +
      std::to_string(node.level()) + "," + std::to_string(node.id()) +
      " nodecount= " + std::to_string(header_->nodecount()));
}

iterable_t<const DirectedEdge> GraphTile::GetDirectedEdges(const size_t idx) const {
  if (idx < header_->nodecount()) {
    const auto& nodeinfo = nodes_[idx];
    const auto* edge = directededge(nodeinfo.edge_index());
    return iterable_t<const DirectedEdge>{edge, nodeinfo.edge_count()};
  }
  throw std::runtime_error(
      "GraphTile NodeInfo index out of bounds: " + std::to_string(header_->graphid().tileid()) + "," +
      std::to_string(header_->graphid().level()) + "," + std::to_string(idx) +
      " nodecount= " + std::to_string(header_->nodecount()));
}

// Get a pointer to edge info.
EdgeInfo GraphTile::edgeinfo(const size_t offset) const {
  return EdgeInfo(edgeinfo_ + offset, textlist_, textlist_size_);
}

// Get the complex restrictions in the forward or reverse order based on
// the id and modes.
std::vector<ComplexRestriction*>
GraphTile::GetRestrictions(const bool forward, const GraphId id, const uint64_t modes) const {
  size_t offset = 0;
  std::vector<ComplexRestriction*> cr_vector;
  if (forward) {
    while (offset < complex_restriction_forward_size_) {
      ComplexRestriction* cr =
          reinterpret_cast<ComplexRestriction*>(complex_restriction_forward_ + offset);
      if (cr->to_graphid() == id && (cr->modes() & modes)) {
        cr_vector.push_back(cr);
      }
      offset += cr->SizeOf();
    }
  } else {
    while (offset < complex_restriction_reverse_size_) {
      ComplexRestriction* cr =
          reinterpret_cast<ComplexRestriction*>(complex_restriction_reverse_ + offset);
      if (cr->from_graphid() == id && (cr->modes() & modes)) {
        cr_vector.push_back(cr);
      }
      offset += cr->SizeOf();
    }
  }
  return cr_vector;
}

// Get the directed edges outbound from the specified node index.
const DirectedEdge*
GraphTile::GetDirectedEdges(const uint32_t node_index, uint32_t& count, uint32_t& edge_index) const {
  const NodeInfo* nodeinfo = node(node_index);
  count = nodeinfo->edge_count();
  edge_index = nodeinfo->edge_index();
  return directededge(nodeinfo->edge_index());
}

// Convenience method to get the names for an edge given the offset to the
// edge info
std::vector<std::string> GraphTile::GetNames(const uint32_t edgeinfo_offset) const {
  return edgeinfo(edgeinfo_offset).GetNames();
}

// Convenience method to get the types for the names given the offset to the
// edge info
uint16_t GraphTile::GetTypes(const uint32_t edgeinfo_offset) const {
  return edgeinfo(edgeinfo_offset).GetTypes();
}

// Get the admininfo at the specified index.
AdminInfo GraphTile::admininfo(const size_t idx) const {
  if (idx < header_->admincount()) {
    const Admin& admin = admins_[idx];
    return AdminInfo(textlist_ + admin.country_offset(), textlist_ + admin.state_offset(),
                     admin.country_iso(), admin.state_iso());
  }
  throw std::runtime_error("GraphTile AdminInfo index out of bounds");
}

// Get the admin at the specified index.
const Admin* GraphTile::admin(const size_t idx) const {
  if (idx < header_->admincount()) {
    return &admins_[idx];
  }
  throw std::runtime_error("GraphTile Admin index out of bounds");
}

// Convenience method to get the text/name for a given offset to the textlist
std::string GraphTile::GetName(const uint32_t textlist_offset) const {
  if (textlist_offset < textlist_size_) {
    return textlist_ + textlist_offset;
  } else {
    throw std::runtime_error("GetName: offset exceeds size of text list");
  }
}

// Convenience method to get the signs for an edge given the
// directed edge index.
std::vector<SignInfo> GraphTile::GetSigns(const uint32_t idx) const {
  uint32_t count = header_->signcount();
  std::vector<SignInfo> signs;
  if (count == 0) {
    return signs;
  }

  // Signs are sorted by edge index.
  // Binary search to find a sign with matching edge index.
  int32_t low = 0;
  int32_t high = count - 1;
  int32_t mid;
  int32_t found = count;
  while (low <= high) {
    mid = (low + high) / 2;
    const auto& sign = signs_[mid];
    // matching edge index
    if (idx == sign.edgeindex()) {
      found = mid;
      high = mid - 1;
    } // need a smaller index
    else if (idx < sign.edgeindex()) {
      high = mid - 1;
    } // need a bigger index
    else {
      low = mid + 1;
    }
  }

  // Add signs
  for (; found < count && signs_[found].edgeindex() == idx; ++found) {
    if (signs_[found].text_offset() < textlist_size_) {
      // Skip tagged text strings (Future code is needed to handle tagged strings)
      if (signs_[found].tagged()) {
        continue;
      }
      signs.emplace_back(signs_[found].type(), signs_[found].is_route_num(),
                         (textlist_ + signs_[found].text_offset()));
    } else {
      throw std::runtime_error("GetSigns: offset exceeds size of text list");
    }
  }
  if (signs.size() == 0) {
    LOG_ERROR("No signs found for idx = " + std::to_string(idx));
  }
  return signs;
}

// Get lane connections ending on this edge.
std::vector<LaneConnectivity> GraphTile::GetLaneConnectivity(const uint32_t idx) const {
  uint32_t count = lane_connectivity_size_ / sizeof(LaneConnectivity);
  std::vector<LaneConnectivity> lcs;
  if (count == 0) {
    LOG_ERROR("No lane connections found for idx = " + std::to_string(idx));
    return lcs;
  }

  // Lane connections are sorted by edge index.
  // Binary search to find a sign with matching edge index.
  int32_t low = 0;
  int32_t high = count - 1;
  int32_t mid;
  int32_t found = count;
  while (low <= high) {
    mid = (low + high) / 2;
    const auto& lc = lane_connectivity_[mid];
    // matching edge index
    if (idx == lc.to()) {
      found = mid;
      high = mid - 1;
    } // need a smaller index
    else if (idx < lc.to()) {
      high = mid - 1;
    } // need a bigger index
    else {
      low = mid + 1;
    }
  }

  // Add Lane connections
  for (; found < count && lane_connectivity_[found].to() == idx; ++found) {
    lcs.emplace_back(lane_connectivity_[found]);
  }
  if (lcs.size() == 0) {
    LOG_ERROR("No lane connections found for idx = " + std::to_string(idx));
  }
  return lcs;
}

// Get the next departure given the directed line Id and the current
// time (seconds from midnight).
const TransitDeparture* GraphTile::GetNextDeparture(const uint32_t lineid,
                                                    const uint32_t current_time,
                                                    const uint32_t day,
                                                    const uint32_t dow,
                                                    bool date_before_tile,
                                                    bool wheelchair,
                                                    bool bicycle) const {
  uint32_t count = header_->departurecount();
  if (count == 0) {
    return nullptr;
  }

  // Departures are sorted by edge Id and then by departure time.
  // Binary search to find a departure with matching line Id.
  int32_t low = 0;
  int32_t high = count - 1;
  int32_t mid;
  int32_t found = count;
  while (low <= high) {
    mid = (low + high) / 2;
    const auto& dep = departures_[mid];
    // matching lineid and a workable time
    if (lineid == dep.lineid() &&
        ((current_time <= dep.departure_time() && dep.type() == kFixedSchedule) ||
         (current_time <= dep.end_time() && dep.type() == kFrequencySchedule))) {
      found = mid;
      high = mid - 1;
    } // need a smaller lineid
    else if (lineid < dep.lineid()) {
      high = mid - 1;
    } // either need a bigger lineid or a later time
    else {
      low = mid + 1;
    }
  }

  // Iterate through departures until one is found with valid date, dow or
  // calendar date, and does not have a calendar exception.
  for (; found < count && departures_[found].lineid() == lineid; ++found) {
    // Make sure valid departure time
    if (departures_[found].type() == kFixedSchedule) {
      if (departures_[found].departure_time() >= current_time &&
          GetTransitSchedule(departures_[found].schedule_index())
              ->IsValid(day, dow, date_before_tile) &&
          (!wheelchair || departures_[found].wheelchair_accessible()) &&
          (!bicycle || departures_[found].bicycle_accessible())) {
        return &departures_[found];
      }
    } else {
      uint32_t departure_time = departures_[found].departure_time();
      uint32_t end_time = departures_[found].end_time();
      uint32_t frequency = departures_[found].frequency();
      while (departure_time < current_time && departure_time < end_time) {
        departure_time += frequency;
      }

      if (departure_time >= current_time && departure_time < end_time &&
          GetTransitSchedule(departures_[found].schedule_index())
              ->IsValid(day, dow, date_before_tile) &&
          (!wheelchair || departures_[found].wheelchair_accessible()) &&
          (!bicycle || departures_[found].bicycle_accessible())) {

        const auto& d = departures_[found];
        const TransitDeparture* dep =
            new TransitDeparture(d.lineid(), d.tripid(), d.routeid(), d.blockid(),
                                 d.headsign_offset(), departure_time, d.end_time(), d.frequency(),
                                 d.elapsed_time(), d.schedule_index(), d.wheelchair_accessible(),
                                 d.bicycle_accessible());
        return dep;
      }
    }
  }

  // TODO - maybe wrap around, try next day?
  LOG_DEBUG("No more departures found for lineid = " + std::to_string(lineid) +
            " current_time = " + std::to_string(current_time));
  return nullptr;
}

// Get the departure given the line Id and tripid
const TransitDeparture* GraphTile::GetTransitDeparture(const uint32_t lineid,
                                                       const uint32_t tripid,
                                                       const uint32_t current_time) const {
  uint32_t count = header_->departurecount();
  if (count == 0) {
    return nullptr;
  }

  // Departures are sorted by edge Id and then by departure time.
  // Binary search to find a departure with matching line Id.
  int32_t low = 0;
  int32_t high = count - 1;
  int32_t mid;
  int32_t found = count;
  while (low <= high) {
    mid = (low + high) / 2;
    const auto& dep = departures_[mid];
    // find the first matching lineid in the list
    if (lineid == dep.lineid() &&
        ((current_time <= dep.departure_time() && dep.type() == kFixedSchedule) ||
         (current_time <= dep.end_time() && dep.type() == kFrequencySchedule))) {
      found = mid;
      high = mid - 1;
    } // need a smaller lineid
    else if (lineid < dep.lineid()) {
      high = mid - 1;
    } // need a bigger lineid
    else {
      low = mid + 1;
    }
  }

  // Iterate through departures until one is found with matching trip id
  for (; found < count && departures_[found].lineid() == lineid; ++found) {
    if (departures_[found].tripid() == tripid) {

      if (departures_[found].type() == kFixedSchedule) {
        return &departures_[found];
      }

      uint32_t departure_time = departures_[found].departure_time();
      uint32_t end_time = departures_[found].end_time();
      uint32_t frequency = departures_[found].frequency();
      while (departure_time < current_time && departure_time < end_time) {
        departure_time += frequency;
      }

      if (departure_time >= current_time && departure_time < end_time) {
        const auto& d = departures_[found];
        const TransitDeparture* dep =
            new TransitDeparture(d.lineid(), d.tripid(), d.routeid(), d.blockid(),
                                 d.headsign_offset(), departure_time, d.end_time(), d.frequency(),
                                 d.elapsed_time(), d.schedule_index(), d.wheelchair_accessible(),
                                 d.bicycle_accessible());
        return dep;
      }
    }
  }

  LOG_INFO("No departures found for lineid = " + std::to_string(lineid) +
           " and tripid = " + std::to_string(tripid));
  return nullptr;
}

// Get a map of departures based on lineid.  No dups exist in the map.
std::unordered_map<uint32_t, TransitDeparture*> GraphTile::GetTransitDepartures() const {

  std::unordered_map<uint32_t, TransitDeparture*> deps;
  deps.reserve(header_->departurecount());

  for (uint32_t i = 0; i < header_->departurecount(); i++) {
    deps.insert({departures_[i].lineid(), &departures_[i]});
  }

  return deps;
}

// Get the stop onestop Ids in this tile.
const std::unordered_map<std::string, GraphId>& GraphTile::GetStopOneStops() const {
  return stop_one_stops;
}

// Get the route onestop Ids in this tile.
const std::unordered_map<std::string, std::list<GraphId>>& GraphTile::GetRouteOneStops() const {
  return route_one_stops;
}

// Get the operator onestop Ids in this tile.
const std::unordered_map<std::string, std::list<GraphId>>& GraphTile::GetOperatorOneStops() const {
  return oper_one_stops;
}

// Get the transit stop given its index within the tile.
const TransitStop* GraphTile::GetTransitStop(const uint32_t idx) const {
  uint32_t count = header_->stopcount();
  if (count == 0) {
    return nullptr;
  }

  if (idx < count) {
    return &transit_stops_[idx];
  }
  throw std::runtime_error("GraphTile Transit Stop index out of bounds");
}

// Get the transit route given its index within the tile.
const TransitRoute* GraphTile::GetTransitRoute(const uint32_t idx) const {
  uint32_t count = header_->routecount();
  if (count == 0) {
    return nullptr;
  }

  if (idx < count) {
    return &transit_routes_[idx];
  }
  throw std::runtime_error("GraphTile GetTransitRoute index out of bounds");
}

// Get the transit schedule given its schedule index.
const TransitSchedule* GraphTile::GetTransitSchedule(const uint32_t idx) const {
  uint32_t count = header_->schedulecount();
  if (count == 0) {
    return nullptr;
  }

  if (idx < count) {
    return &transit_schedules_[idx];
  }
  throw std::runtime_error("GraphTile GetTransitSchedule index out of bounds");
}

// Get the access restriction given its directed edge index
std::vector<AccessRestriction> GraphTile::GetAccessRestrictions(const uint32_t idx,
                                                                const uint32_t access) const {

  std::vector<AccessRestriction> restrictions;
  uint32_t count = header_->access_restriction_count();
  if (count == 0) {
    return restrictions;
  }

  // Access restriction are sorted by edge Id.
  // Binary search to find a access restriction with matching edge Id.
  int32_t low = 0;
  int32_t high = count - 1;
  int32_t mid;
  int32_t found = count;
  while (low <= high) {
    mid = (low + high) / 2;
    const auto& res = access_restrictions_[mid];
    // find the first matching index in the list
    if (idx == res.edgeindex()) {
      found = mid;
      high = mid - 1;
    } // need a smaller index
    else if (idx < res.edgeindex()) {
      high = mid - 1;
    } // need a bigger index
    else {
      low = mid + 1;
    }
  }

  // Add restrictions for only the access that we are interested in
  for (; found < count && access_restrictions_[found].edgeindex() == idx; ++found) {
    if (access_restrictions_[found].modes() & access) {
      restrictions.emplace_back(access_restrictions_[found]);
    }
  }

  return restrictions;
}

// Get the array of graphids for this bin
midgard::iterable_t<GraphId> GraphTile::GetBin(size_t column, size_t row) const {
  auto offsets = header_->bin_offset(column, row);
  return iterable_t<GraphId>{edge_bins_ + offsets.first, edge_bins_ + offsets.second};
}

midgard::iterable_t<GraphId> GraphTile::GetBin(size_t index) const {
  auto offsets = header_->bin_offset(index);
  return iterable_t<GraphId>{edge_bins_ + offsets.first, edge_bins_ + offsets.second};
}

// Get turn lanes for this edge.
uint32_t GraphTile::turnlanes_offset(const uint32_t idx) const {
  uint32_t count = header_->turnlane_count();
  if (count == 0) {
    LOG_ERROR("No turn lanes found for idx = " + std::to_string(idx));
    return 0;
  }
  auto tl = std::lower_bound(&turnlanes_[0], &turnlanes_[count], TurnLanes(idx, 0));
  return tl != &turnlanes_[count] ? tl->text_offset() : 0;
}

} // namespace baldr
} // namespace valhalla

max_stars_repo_name: bryanrideshark/valhalla

max_issues_repo_name: bryanrideshark/valhalla

max_forks_repo_name: bryanrideshark/valhalla