text:
////////////////////////////////////////////////////////////////////////////////
/// @brief test suite for json.c
///
/// @file
///
/// DISCLAIMER
///
/// Copyright 2012 triagens GmbH, Cologne, Germany
///
/// 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.
///
/// Copyright holder is triAGENS GmbH, Cologne, Germany
///
/// @author Jan Steemann
/// @author Copyright 2012, triAGENS GmbH, Cologne, Germany
////////////////////////////////////////////////////////////////////////////////

#include <boost/test/unit_test.hpp>

#include "Basics/json.h"
#include "Basics/string-buffer.h"

// -----------------------------------------------------------------------------
// --SECTION--                                                    private macros
// -----------------------------------------------------------------------------

#define INIT_BUFFER  TRI_string_buffer_t* sb = TRI_CreateStringBuffer(TRI_UNKNOWN_MEM_ZONE);
#define FREE_BUFFER  TRI_FreeStringBuffer(TRI_UNKNOWN_MEM_ZONE, sb);
#define STRINGIFY    TRI_StringifyJson(sb, json);
#define STRING_VALUE sb->_buffer
#define FREE_JSON    TRI_FreeJson(TRI_UNKNOWN_MEM_ZONE, json);

// -----------------------------------------------------------------------------
// --SECTION--                                                 setup / tear-down
// -----------------------------------------------------------------------------

struct CJsonSetup {
  CJsonSetup () {
    BOOST_TEST_MESSAGE("setup json");
  }

  ~CJsonSetup () {
    BOOST_TEST_MESSAGE("tear-down json");
  }
};

// -----------------------------------------------------------------------------
// --SECTION--                                                        test suite
// -----------------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////////////
/// @brief setup
////////////////////////////////////////////////////////////////////////////////

BOOST_FIXTURE_TEST_SUITE(CJsonTest, CJsonSetup)

////////////////////////////////////////////////////////////////////////////////
/// @brief test null value
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_null) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateNullJson(TRI_UNKNOWN_MEM_ZONE);
  BOOST_CHECK_EQUAL(false, TRI_IsStringJson(json));

  STRINGIFY
  BOOST_CHECK_EQUAL("null", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test true value
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_true) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateBooleanJson(TRI_UNKNOWN_MEM_ZONE, true);
  BOOST_CHECK_EQUAL(false, TRI_IsStringJson(json));

  STRINGIFY
  BOOST_CHECK_EQUAL("true", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test false value
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_false) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateBooleanJson(TRI_UNKNOWN_MEM_ZONE, false);
  BOOST_CHECK_EQUAL(false, TRI_IsStringJson(json));

  STRINGIFY
  BOOST_CHECK_EQUAL("false", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test number value 0
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_number0) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 0.0);
  BOOST_CHECK_EQUAL(false, TRI_IsStringJson(json));

  STRINGIFY
  BOOST_CHECK_EQUAL("0", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test number value (positive)
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_number_positive1) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 1.0);
  BOOST_CHECK_EQUAL(false, TRI_IsStringJson(json));

  STRINGIFY
  BOOST_CHECK_EQUAL("1", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test number value (positive)
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_number_positive2) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 46281);
  BOOST_CHECK_EQUAL(false, TRI_IsStringJson(json));

  STRINGIFY
  BOOST_CHECK_EQUAL("46281", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test number value (negative)
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_number_negative1) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, -1.0);
  BOOST_CHECK_EQUAL(false, TRI_IsStringJson(json));

  STRINGIFY
  BOOST_CHECK_EQUAL("-1", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test number value (negative)
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_number_negative2) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, -2342);
  BOOST_CHECK_EQUAL(false, TRI_IsStringJson(json));

  STRINGIFY
  BOOST_CHECK_EQUAL("-2342", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test string value (empty)
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_string_empty) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateStringCopyJson(TRI_UNKNOWN_MEM_ZONE, (char*) "");
  BOOST_CHECK_EQUAL(true, TRI_IsStringJson(json));

  STRINGIFY
  BOOST_CHECK_EQUAL("\"\"", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test string value
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_string1) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateStringCopyJson(TRI_UNKNOWN_MEM_ZONE, (char*) "the quick brown fox");
  BOOST_CHECK_EQUAL(true, TRI_IsStringJson(json));

  STRINGIFY
  BOOST_CHECK_EQUAL("\"the quick brown fox\"", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test string value
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_string2) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateStringCopyJson(TRI_UNKNOWN_MEM_ZONE, (char*) "The Quick Brown Fox");
  BOOST_CHECK_EQUAL(true, TRI_IsStringJson(json));

  STRINGIFY
  BOOST_CHECK_EQUAL("\"The Quick Brown Fox\"", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test string reference value
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_string_reference) {
  INIT_BUFFER

  const char* data = "The Quick Brown Fox";
  char copy[64];

  memset(copy, 0, sizeof(copy));
  memcpy(copy, data, strlen(data));

  TRI_json_t* json = TRI_CreateStringReferenceJson(TRI_UNKNOWN_MEM_ZONE, copy);
  BOOST_CHECK_EQUAL(true, TRI_IsStringJson(json));

  STRINGIFY
  BOOST_CHECK_EQUAL("\"The Quick Brown Fox\"", STRING_VALUE);
  FREE_BUFFER

  FREE_JSON

  // freeing JSON should not affect our string
  BOOST_CHECK_EQUAL("The Quick Brown Fox", copy);

  json = TRI_CreateStringReferenceJson(TRI_UNKNOWN_MEM_ZONE, copy);
  BOOST_CHECK_EQUAL(true, TRI_IsStringJson(json));

  // modify the string we're referring to
  copy[0] = '*';
  copy[1] = '/';
  copy[2] = '+';
  copy[strlen(copy) - 1] = '!';

  sb = TRI_CreateStringBuffer(TRI_UNKNOWN_MEM_ZONE);
  STRINGIFY
  BOOST_CHECK_EQUAL("\"*/+ Quick Brown Fo!\"", STRING_VALUE);
  FREE_BUFFER

  BOOST_CHECK_EQUAL("*/+ Quick Brown Fo!", copy);

  FREE_JSON
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test string reference value
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_string_reference2) {
  INIT_BUFFER

  const char* data1 = "The first Brown Fox";
  const char* data2 = "The second Brown Fox";
  char copy1[64];
  char copy2[64];
  TRI_json_t* json;
  size_t len1 = strlen(data1);
  size_t len2 = strlen(data2);

  memset(copy1, 0, sizeof(copy1));
  memcpy(copy1, data1, len1);

  memset(copy2, 0, sizeof(copy2));
  memcpy(copy2, data2, len2);

  json = TRI_CreateArrayJson(TRI_UNKNOWN_MEM_ZONE);

  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "first",
                       TRI_CreateStringReferenceJson(TRI_UNKNOWN_MEM_ZONE, copy1));

  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "second",
                       TRI_CreateStringReference2Json(TRI_UNKNOWN_MEM_ZONE, copy2, len2));

  BOOST_CHECK_EQUAL(true, TRI_IsArrayJson(json));

  STRINGIFY
  BOOST_CHECK_EQUAL("{\"first\":\"The first Brown Fox\",\"second\":\"The second Brown Fox\"}", STRING_VALUE);
  FREE_BUFFER

  FREE_JSON

  // freeing JSON should not affect our string
  BOOST_CHECK_EQUAL("The first Brown Fox", copy1);
  BOOST_CHECK_EQUAL("The second Brown Fox", copy2);

  json = TRI_CreateArrayJson(TRI_UNKNOWN_MEM_ZONE);

  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "first",
                       TRI_CreateStringReferenceJson(TRI_UNKNOWN_MEM_ZONE, copy1));

  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "second",
                       TRI_CreateStringReference2Json(TRI_UNKNOWN_MEM_ZONE, copy2, len2));

  BOOST_CHECK_EQUAL(true, TRI_IsArrayJson(json));

  // modify the string we're referring to
  copy1[0] = '*';
  copy1[1] = '/';
  copy1[2] = '+';
  copy1[len1 - 1] = '!';

  copy2[0] = '*';
  copy2[1] = '/';
  copy2[2] = '+';
  copy2[len2 - 1] = '!';

  BOOST_CHECK_EQUAL("*/+ first Brown Fo!", copy1);
  BOOST_CHECK_EQUAL("*/+ second Brown Fo!", copy2);

  sb = TRI_CreateStringBuffer(TRI_UNKNOWN_MEM_ZONE);
  STRINGIFY
  BOOST_CHECK_EQUAL("{\"first\":\"*/+ first Brown Fo!\",\"second\":\"*/+ second Brown Fo!\"}", STRING_VALUE);

  FREE_BUFFER

  // freeing JSON should not affect our string
  BOOST_CHECK_EQUAL("*/+ first Brown Fo!", copy1);
  BOOST_CHECK_EQUAL("*/+ second Brown Fo!", copy2);

  FREE_JSON
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test string value (escaped)
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_string_escaped) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateStringCopyJson(TRI_UNKNOWN_MEM_ZONE, (char*) "\"the quick \"fox\" jumped over the \\brown\\ dog '\n\\\" \\' \\\\ lazy");
  BOOST_CHECK_EQUAL(true, TRI_IsStringJson(json));

  STRINGIFY
  BOOST_CHECK_EQUAL("\"\\\"the quick \\\"fox\\\" jumped over the \\\\brown\\\\ dog '\\n\\\\\\\" \\\\' \\\\\\\\ lazy\"", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test string value (special chars)
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_string_utf8_1) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateStringCopyJson(TRI_UNKNOWN_MEM_ZONE, (char*) "코리아닷컴 메일알리미 서비스 중단안내 [안내] 개인정보취급방침 변경 안내 회사소개 | 광고안내 | 제휴안내 | 개인정보취급방침 | 청소년보호정책 | 스팸방지정책 | 사이버고객센터 | 약관안내 | 이메일 무단수집거부 | 서비스 전체보기");
  BOOST_CHECK_EQUAL(true, TRI_IsStringJson(json));

  STRINGIFY
  BOOST_CHECK_EQUAL("\"\\uCF54\\uB9AC\\uC544\\uB2F7\\uCEF4 \\uBA54\\uC77C\\uC54C\\uB9AC\\uBBF8 \\uC11C\\uBE44\\uC2A4 \\uC911\\uB2E8\\uC548\\uB0B4 [\\uC548\\uB0B4] \\uAC1C\\uC778\\uC815\\uBCF4\\uCDE8\\uAE09\\uBC29\\uCE68 \\uBCC0\\uACBD \\uC548\\uB0B4 \\uD68C\\uC0AC\\uC18C\\uAC1C | \\uAD11\\uACE0\\uC548\\uB0B4 | \\uC81C\\uD734\\uC548\\uB0B4 | \\uAC1C\\uC778\\uC815\\uBCF4\\uCDE8\\uAE09\\uBC29\\uCE68 | \\uCCAD\\uC18C\\uB144\\uBCF4\\uD638\\uC815\\uCC45 | \\uC2A4\\uD338\\uBC29\\uC9C0\\uC815\\uCC45 | \\uC0AC\\uC774\\uBC84\\uACE0\\uAC1D\\uC13C\\uD130 | \\uC57D\\uAD00\\uC548\\uB0B4 | \\uC774\\uBA54\\uC77C \\uBB34\\uB2E8\\uC218\\uC9D1\\uAC70\\uBD80 | \\uC11C\\uBE44\\uC2A4 \\uC804\\uCCB4\\uBCF4\\uAE30\"", STRING_VALUE);

  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test string value (special chars)
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_string_utf8_2) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateStringCopyJson(TRI_UNKNOWN_MEM_ZONE, (char*) "äöüßÄÖÜ€µ");

  STRINGIFY
  BOOST_CHECK_EQUAL("\"\\u00E4\\u00F6\\u00FC\\u00DF\\u00C4\\u00D6\\u00DC\\u20AC\\u00B5\"", STRING_VALUE);

  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test string value (unicode surrogate pair)
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_string_utf8_3) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateStringCopyJson(TRI_UNKNOWN_MEM_ZONE, (char*) "a𝛢");

  STRINGIFY
  BOOST_CHECK_EQUAL("\"a\\uD835\\uDEE2\"", STRING_VALUE);

  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test empty json list
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_list_empty) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateListJson(TRI_UNKNOWN_MEM_ZONE);

  STRINGIFY
  BOOST_CHECK_EQUAL("[]", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test json list mixed
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_list_mixed) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateListJson(TRI_UNKNOWN_MEM_ZONE);
  TRI_PushBack3ListJson(TRI_UNKNOWN_MEM_ZONE, json, TRI_CreateNullJson(TRI_UNKNOWN_MEM_ZONE));
  TRI_PushBack3ListJson(TRI_UNKNOWN_MEM_ZONE, json, TRI_CreateBooleanJson(TRI_UNKNOWN_MEM_ZONE, true));
  TRI_PushBack3ListJson(TRI_UNKNOWN_MEM_ZONE, json, TRI_CreateBooleanJson(TRI_UNKNOWN_MEM_ZONE, false));
  TRI_PushBack3ListJson(TRI_UNKNOWN_MEM_ZONE, json, TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, -8093));
  TRI_PushBack3ListJson(TRI_UNKNOWN_MEM_ZONE, json, TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 1.5));
  TRI_PushBack3ListJson(TRI_UNKNOWN_MEM_ZONE, json, TRI_CreateStringCopyJson(TRI_UNKNOWN_MEM_ZONE, (char*) "the quick brown fox"));
  TRI_PushBack3ListJson(TRI_UNKNOWN_MEM_ZONE, json, TRI_CreateListJson(TRI_UNKNOWN_MEM_ZONE));
  TRI_PushBack3ListJson(TRI_UNKNOWN_MEM_ZONE, json, TRI_CreateArrayJson(TRI_UNKNOWN_MEM_ZONE));

  STRINGIFY
  BOOST_CHECK_EQUAL("[null,true,false,-8093,1.5,\"the quick brown fox\",[],{}]", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test json lists nested
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_list_nested) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateListJson(TRI_UNKNOWN_MEM_ZONE);
  TRI_json_t* list1 = TRI_CreateListJson(TRI_UNKNOWN_MEM_ZONE);
  TRI_json_t* list2 = TRI_CreateListJson(TRI_UNKNOWN_MEM_ZONE);
  TRI_json_t* list3 = TRI_CreateListJson(TRI_UNKNOWN_MEM_ZONE);
  TRI_json_t* list4 = TRI_CreateListJson(TRI_UNKNOWN_MEM_ZONE);

  TRI_PushBack3ListJson(TRI_UNKNOWN_MEM_ZONE, list1, TRI_CreateBooleanJson(TRI_UNKNOWN_MEM_ZONE, true));
  TRI_PushBack3ListJson(TRI_UNKNOWN_MEM_ZONE, list1, TRI_CreateBooleanJson(TRI_UNKNOWN_MEM_ZONE, false));
  TRI_PushBack3ListJson(TRI_UNKNOWN_MEM_ZONE, list2, TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, -8093));
  TRI_PushBack3ListJson(TRI_UNKNOWN_MEM_ZONE, list2, TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 1.5));
  TRI_PushBack3ListJson(TRI_UNKNOWN_MEM_ZONE, list3, TRI_CreateStringCopyJson(TRI_UNKNOWN_MEM_ZONE, (char*) "the quick brown fox"));
  TRI_PushBack3ListJson(TRI_UNKNOWN_MEM_ZONE, json, list1);
  TRI_PushBack3ListJson(TRI_UNKNOWN_MEM_ZONE, json, list2);
  TRI_PushBack3ListJson(TRI_UNKNOWN_MEM_ZONE, json, list3);
  TRI_PushBack3ListJson(TRI_UNKNOWN_MEM_ZONE, json, list4);

  STRINGIFY
  BOOST_CHECK_EQUAL("[[true,false],[-8093,1.5],[\"the quick brown fox\"],[]]", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test empty json array
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_array_empty) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateArrayJson(TRI_UNKNOWN_MEM_ZONE);

  STRINGIFY
  BOOST_CHECK_EQUAL("{}", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test json array mixed
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_array_mixed) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateArrayJson(TRI_UNKNOWN_MEM_ZONE);
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "one", TRI_CreateNullJson(TRI_UNKNOWN_MEM_ZONE));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "two", TRI_CreateBooleanJson(TRI_UNKNOWN_MEM_ZONE, true));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "three", TRI_CreateBooleanJson(TRI_UNKNOWN_MEM_ZONE, false));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "four", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, -8093));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "five", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 1.5));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "six", TRI_CreateStringCopyJson(TRI_UNKNOWN_MEM_ZONE, (char*) "the quick brown fox"));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "seven", TRI_CreateListJson(TRI_UNKNOWN_MEM_ZONE));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "eight", TRI_CreateArrayJson(TRI_UNKNOWN_MEM_ZONE));

  STRINGIFY
  BOOST_CHECK_EQUAL("{\"one\":null,\"two\":true,\"three\":false,\"four\":-8093,\"five\":1.5,\"six\":\"the quick brown fox\",\"seven\":[],\"eight\":{}}", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test nested json array
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_array_nested) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateArrayJson(TRI_UNKNOWN_MEM_ZONE);
  TRI_json_t* array1 = TRI_CreateArrayJson(TRI_UNKNOWN_MEM_ZONE);
  TRI_json_t* array2 = TRI_CreateArrayJson(TRI_UNKNOWN_MEM_ZONE);
  TRI_json_t* array3 = TRI_CreateArrayJson(TRI_UNKNOWN_MEM_ZONE);
  TRI_json_t* array4 = TRI_CreateArrayJson(TRI_UNKNOWN_MEM_ZONE);
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, array1, "one", TRI_CreateNullJson(TRI_UNKNOWN_MEM_ZONE));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, array1, "two", TRI_CreateBooleanJson(TRI_UNKNOWN_MEM_ZONE, true));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, array1, "three", TRI_CreateBooleanJson(TRI_UNKNOWN_MEM_ZONE, false));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, array2, "four", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, -8093));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, array2, "five", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 1.5));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, array2, "six", TRI_CreateStringCopyJson(TRI_UNKNOWN_MEM_ZONE, (char*) "the quick brown fox"));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, array3, "seven", TRI_CreateListJson(TRI_UNKNOWN_MEM_ZONE));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, array3, "eight", TRI_CreateArrayJson(TRI_UNKNOWN_MEM_ZONE));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "one", array1);
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "two", array2);
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "three", array3);
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "four", array4);

  STRINGIFY
  BOOST_CHECK_EQUAL("{\"one\":{\"one\":null,\"two\":true,\"three\":false},\"two\":{\"four\":-8093,\"five\":1.5,\"six\":\"the quick brown fox\"},\"three\":{\"seven\":[],\"eight\":{}},\"four\":{}}", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test json array keys
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_array_keys) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateArrayJson(TRI_UNKNOWN_MEM_ZONE);
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "\"quoted\"", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 1));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "'quoted'", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 2));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "\\slashed\\\"", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 3));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "white spaced", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 4));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "line\\nbreak", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 5));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 6));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, " ", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 7));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "null", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 8));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "true", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 9));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "false", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 10));

  STRINGIFY
  BOOST_CHECK_EQUAL("{\"\\\"quoted\\\"\":1,\"'quoted'\":2,\"\\\\slashed\\\\\\\"\":3,\"white spaced\":4,\"line\\\\nbreak\":5,\"\":6,\" \":7,\"null\":8,\"true\":9,\"false\":10}", STRING_VALUE);
  FREE_JSON
  FREE_BUFFER
}

////////////////////////////////////////////////////////////////////////////////
/// @brief test utf8 json array keys
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_CASE (tst_json_array_keys_utf8) {
  INIT_BUFFER

  TRI_json_t* json = TRI_CreateArrayJson(TRI_UNKNOWN_MEM_ZONE);
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "äöüÄÖÜß", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 1));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "코리아닷컴", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 2));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "ジャパン", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 3));
  TRI_Insert3ArrayJson(TRI_UNKNOWN_MEM_ZONE, json, "мадридского", TRI_CreateNumberJson(TRI_UNKNOWN_MEM_ZONE, 4));

  STRINGIFY
  BOOST_CHECK_EQUAL("{\"\\u00E4\\u00F6\\u00FC\\u00C4\\u00D6\\u00DC\\u00DF\":1,\"\\uCF54\\uB9AC\\uC544\\uB2F7\\uCEF4\":2,\"\\u30B8\\u30E3\\u30D1\\u30F3\":3,\"\\u043C\\u0430\\u0434\\u0440\\u0438\\u0434\\u0441\\u043A\\u043E\\u0433\\u043E\":4}", STRING_VALUE);

  FREE_JSON
  FREE_BUFFER
}

// TODO: add tests for lookup json array value etc.

////////////////////////////////////////////////////////////////////////////////
/// @brief generate tests
////////////////////////////////////////////////////////////////////////////////

BOOST_AUTO_TEST_SUITE_END ()

// Local Variables:
// mode: outline-minor
// outline-regexp: "^\\(/// @brief\\|/// {@inheritDoc}\\|/// @addtogroup\\|// --SECTION--\\|/// @\\}\\)"
// End:

max_stars_repo_name: morsdatum/ArangoDB

max_issues_repo_name: morsdatum/ArangoDB

max_forks_repo_name: morsdatum/ArangoDB


text:
#ifndef EDMONDS_OPTIMUM_BRANCHING_IMPL_HPP
#define EDMONDS_OPTIMUM_BRANCHING_IMPL_HPP

#include <vector>
#include <algorithm>
#include <list>
#include <boost/property_map/property_map.hpp>
#include <boost/foreach.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/concept_check.hpp>
#include <boost/pending/disjoint_sets.hpp>

// namespace detail
//
// The namespace encapsulates classes and/or functions that are
// required for the implementation of edmonds's optimum branching
// algorithm which should not be visible to the user. This way the
// global namespace remains unpolluted.
namespace detail {
    using namespace boost;

    // class OptimumBranching
    //
    // I encapsulate all the details of edmonds's algorithm inside a
    // class. This makes the code easier to read (and easier to write)
    // since the number of template declarations is reduced
    // considerably. Besides, all the utility functions used to
    // implement one algorithm conceptually do belong together.
    //
    // Note that any concept checks are performed in the function that
    // uses this class, so there is no need to repeat them here.
    template <bool TOptimumIsMaximum,
              bool TAttemptToSpan,
              bool TGraphIsDense,
              class TEdgeListGraph,
              class TVertexIndexMap,
              class TWeightMap,
              class TInputIterator,
              class TOutputIterator>
    class OptimumBranching {
    public:
        typedef TEdgeListGraph                                        Graph;
        typedef typename graph_traits<Graph>::edge_descriptor         Edge;
        typedef typename graph_traits<Graph>::vertex_descriptor       Vertex;
        typedef typename graph_traits<Graph>::edge_iterator           EdgeIter;
        typedef typename property_traits<TWeightMap>::value_type      weight_t;
        typedef typename property_traits<TVertexIndexMap>::value_type vertex_idx_t;

        // struct EdgeNode
        //
        // One unique EdgeNode object is created for each edge of the
        // input graph. Any containers then store pointers to these
        // objects. The edges of the graph F (which is described in
        // the document describing the implementation) are stored in
        // each EdgeNode object via the parent and children members.
        // For efficiency reasons a boolean member 'removed_from_F' is
        // also present in each EdgeNode object. If this member is
        // set, then the edge (which is also a vertex in F) was
        // removed during the expansion phase of the algorithm.
        struct EdgeNode {
            Edge                        edge;
            vertex_idx_t                source;
            vertex_idx_t                target;
            weight_t                    weight;
            EdgeNode                   *parent;
            std::vector<EdgeNode *>     children;
            bool                        removed_from_F;

            EdgeNode(const Edge &e,
                     const vertex_idx_t &s,
                     const vertex_idx_t &t,
                     const weight_t w)
                : edge(e), source(s), target(t), weight(w), parent(0),
                  removed_from_F(false)
            {
                ;
            }

            // operator<
            //
            // This is only used temporarily when sorting the
            // EdgeNodes by their sources. Once a radix-sort algorithm
            // has been implemented, this is no longer needed.
            bool        operator<(const EdgeNode &en) const
            {
                return source < en.source;
            }
        };

        // The data members of the OptimumBranching class. These
        // include both the input and the variables needed internally for the implemenationa.
        const TEdgeListGraph   &g;
        const TVertexIndexMap  &index;
        const TWeightMap       &weight;
        TInputIterator          roots_begin;
        TInputIterator          roots_end;
        TOutputIterator         out;

        // The constructor
        OptimumBranching(const TEdgeListGraph &g,
                         const TVertexIndexMap &index,
                         const TWeightMap &weight,
                         TInputIterator roots_begin,
                         TInputIterator roots_end,
                         TOutputIterator out)
            : g(g), index(index), weight(weight),
              roots_begin(roots_begin), roots_end(roots_end), out(out)
        {
            ;
        }

        // remove_from_F()
        //
        // It removes the EdgeNode en and all its ancestors from the
        // graph F (by resetting the parent and children members and
        // setting the flag removed_from_F). Any newly created roots
        // of F are inserted into F_roots. Note that the root of F
        // that is removed as a consequence is not actually removed
        // from F_roots. It is simply marked as removed via the
        // 'removed_from_F' flag.
        void remove_from_F(EdgeNode *en, std::vector<EdgeNode *> &F_roots)
        {
            // Note that en is inserted into F_roots as well. But
            // since it is marked as removed_from_F it will not cause
            // any trouble. This is more efficient than making sure
            // that only the siblings of en are inserted into F_roots.
            for ( ; en != 0; en = en->parent)
            {
                en->removed_from_F = true;
                BOOST_FOREACH (EdgeNode *child, en->children)
                {
                    F_roots.push_back(child);
                    child->parent = 0;
                }

                // free the memory used in en->children.
                std::vector<EdgeNode *>().swap(en->children);
            }
        }

        // sort_edges()
        //
        // sorts a vector of EdgeNode pointers with EdgeNode.source as
        // key using the radix-sort algorithm. Also, if there are
        // several EdgeNode pointers with the same source, the
        // function only keeps the one with optimum weight.
        void sort_edges(std::vector<EdgeNode *> &edge_vec)
        {
            const int byte_len = 8;
            const int num_buckets = 1u << byte_len;
            const unsigned digits = (sizeof (vertex_idx_t)) * std::numeric_limits<unsigned char>::digits;
            const unsigned mask = (1u << byte_len) - 1;

            std::vector< std::list<EdgeNode *> > buckets(num_buckets);

            for (unsigned i = 0; byte_len * i <= digits; ++i)
            {
                BOOST_FOREACH (EdgeNode *en, edge_vec)
                {
                    buckets[(en->source >> byte_len * i) & mask].push_back(en);
                }

                edge_vec.clear();
                BOOST_FOREACH (std::list<EdgeNode *> &bucket, buckets)
                {
                    BOOST_FOREACH (EdgeNode *en, bucket)
                    {
                        if (!edge_vec.empty() && edge_vec.back()->source == en->source)
                        {
                            bool en_is_better = TOptimumIsMaximum ?
                                en->weight > edge_vec.back()->weight :
                                en->weight < edge_vec.back()->weight;
                            if (en_is_better)
                            {
                                edge_vec.back() = en;
                            }
                        }
                        else
                        {
                            edge_vec.push_back(en);
                        }
                    }
                }

                buckets.clear();
                buckets.resize(num_buckets);
            }
        }

        // operator()
        //
        // This is the main function implementing Tarjan's
        // implementation of Edmonds's algorithm.
        void operator()()
        {
            std::vector<EdgeNode> all_edges;
            vertex_idx_t max_vertex_idx;

            // Create EdgeNodes for all the edges and find the maximum vertex
            // index. Note that we skip self-loops.
            max_vertex_idx = 0;
            BOOST_FOREACH (const Edge &e, edges(g))
            {
                if (source(e, g) == target(e, g))
                    continue;

                all_edges.push_back(EdgeNode (e, source(e, g), target(e, g), get(weight, e)));
                max_vertex_idx = std::max(max_vertex_idx, index[target(e, g)]);
            }

            // insert into in_edges[v] all edges entering v.

            //!! TODO !! If sparse graphs, I have to change the
            //representation of in_edges to a special kind of priority
            //queue that are able to be merged in log n time.

            std::vector< std::vector<EdgeNode *> > in_edges(max_vertex_idx + 1);
            std::vector<weight_t> edge_weight_change(max_vertex_idx + 1);
            BOOST_FOREACH (EdgeNode &en, all_edges)
            {
                in_edges[en.target].push_back(&en);
            }
            BOOST_FOREACH (std::vector<EdgeNode *> &edges, in_edges)
            {
                sort_edges(edges);
            }

            // Save the specified roots in a random access fashion.
            std::vector<bool> is_specified_root(max_vertex_idx + 1);
            std::vector<vertex_idx_t> final_roots;
            for ( ; roots_begin != roots_end; ++roots_begin)
            {
                is_specified_root[index[*roots_begin]] = true;
                final_roots.push_back(index[*roots_begin]);
            }

            // Initialize S, W, roots, cycles, lambda, enter, F, and min
            std::vector< std::vector<EdgeNode *> > cycle(max_vertex_idx + 1);
            std::vector<EdgeNode *> lambda(max_vertex_idx + 1);
            std::vector<vertex_idx_t> roots;
            disjoint_sets_with_storage<> S(2*(max_vertex_idx +1));
            disjoint_sets_with_storage<> W(2*(max_vertex_idx +1));
            std::vector<vertex_idx_t> min(max_vertex_idx + 1);
            std::vector<EdgeNode *> enter(max_vertex_idx + 1);
            std::vector<EdgeNode *> F;
            for (vertex_idx_t v = 0; v <= max_vertex_idx; ++v)
            {
                S.make_set(v);
                W.make_set(v);
                min[v] = v;
                if (!is_specified_root[v])
                    roots.push_back(v);
            }

            // Keep adding critical edges and contracting cycles while
            // doing a whole bunch of book-keeping.
            while (!roots.empty())
            {
                // Find an S-component with an entering edge
                vertex_idx_t cur_root = roots.back(); roots.pop_back();
                if (in_edges[cur_root].empty())
                {
                    final_roots.push_back(min[cur_root]);
                    continue;
                }

                // Find an optimum-weight edge entering cur_root

                //!! TODO !! We have to do this differently for sparse graphs.
                EdgeNode *critical_edge = in_edges[cur_root].front();
                BOOST_FOREACH (EdgeNode *en, in_edges[cur_root])
                {
                    bool en_is_better = TOptimumIsMaximum ?
                        en->weight > critical_edge->weight :
                        en->weight < critical_edge->weight;
                    if (en_is_better)
                    {
                        critical_edge = en;
                    }
                }

                // Do not add critical_edge if it worsens the total
                // weight and we are not attempting to span.
                if (!TAttemptToSpan)
                {
                    bool improves = TOptimumIsMaximum ?
                        critical_edge->weight > weight_t(0) :
                        critical_edge->weight < weight_t(0);
                    if (!improves)
                    {
                        final_roots.push_back(min[cur_root]);
                        continue;
                    }
                }

                // Insert critical_edge into "F" and let any edges in
                // cycle[cur_root] be its children.
                F.push_back(critical_edge);
                BOOST_FOREACH (EdgeNode *en, cycle[cur_root])
                {
                    en->parent = critical_edge;
                    critical_edge->children.push_back(en);
                }

                // If critical_edge is a leaf in "F", then add a
                // pointer to it.
                if (cycle[cur_root].empty())
                {
                    lambda[cur_root] = critical_edge;
                }

                // If adding critical_edge didn't create a cycle
                if (W.find_set(critical_edge->source) !=
                    W.find_set(critical_edge->target))
                {
                    enter[cur_root] = critical_edge;
                    W.union_set(critical_edge->source, critical_edge->target);
                }
                else // If adding critical_edge did create a cycle
                {
                    // Find the edges of the cycle, the
                    // representatives of the strong components in the
                    // cycle, and the least costly edge of the cycle.
                    std::vector<EdgeNode *> cycle_edges;
                    std::vector<vertex_idx_t> cycle_repr;
                    EdgeNode *least_costly_edge = critical_edge;
                    enter[cur_root] = 0;

                    cycle_edges.push_back(critical_edge);
                    cycle_repr.push_back(S.find_set(critical_edge->target));
                    for (vertex_idx_t v = S.find_set(critical_edge->source);
                         enter[v] != 0; v = S.find_set(enter[v]->source))
                    {
                        cycle_edges.push_back(enter[v]);
                        cycle_repr.push_back(v);
                        bool is_less_costly = TOptimumIsMaximum ?
                            enter[v]->weight < least_costly_edge->weight :
                            enter[v]->weight > least_costly_edge->weight;
                        if (is_less_costly)
                        {
                            least_costly_edge = enter[v];
                        }
                    }
                    // change the weight of the edges entering
                    // vertices of the cycle.
                    //!! TODO !! Change this for sparse graphs
                    BOOST_FOREACH (EdgeNode *en, cycle_edges)
                    {
                        edge_weight_change[S.find_set(en->target)] =
                            least_costly_edge->weight - en->weight;
                    }

                    // Save the vertex that would be root if the newly
                    // created strong component would be a root.
                    vertex_idx_t cycle_root =
                        min[S.find_set(least_costly_edge->target)];

                    // Union all components of the cycle into one component.
                    vertex_idx_t new_repr = cycle_repr.front();
                    BOOST_FOREACH (vertex_idx_t v, cycle_repr)
                    {
                        S.link(v, new_repr);
                        new_repr = S.find_set(new_repr);
                    }
                    min[new_repr] = cycle_root;
                    roots.push_back(new_repr);
                    cycle[new_repr].swap(cycle_edges);

                    //!! TODO !! Needs to be changed for sparse graphs.
                    BOOST_FOREACH (vertex_idx_t v, cycle_repr)
                    {
                        BOOST_FOREACH (EdgeNode *en, in_edges[v])
                        {
                            en->weight += edge_weight_change[v];
                        }
                    }

                    // Merge all in_edges of the cycle into one list.
                    //!! TODO !! needs to be changed for sparse graphs.
                    std::vector<EdgeNode *> new_in_edges;
                    for (unsigned i = 1; i < cycle_repr.size(); ++i)
                    {
                        typedef typename std::vector<EdgeNode *>::iterator Iter;
                        Iter i1 = in_edges[cycle_repr[i]].begin();
                        Iter e1 = in_edges[cycle_repr[i]].end();
                        Iter i2 = in_edges[cycle_repr[i-1]].begin();
                        Iter e2 = in_edges[cycle_repr[i-1]].end();

                        ///*
                        while (i1 != e1 || i2 != e2)
                        {
                            while (i1 != e1 && S.find_set((*i1)->source) == new_repr)
                            {
                                ++i1;
                            }
                            while (i2 != e2 && S.find_set((*i2)->source) == new_repr)
                            {
                                ++i2;
                            }

                            if (i1 == e1 && i2 == e2)
                                break;

                            if (i1 == e1)
                            {
                                new_in_edges.push_back(*i2);
                                ++i2;
                            }
                            else if (i2 == e2)
                            {
                                new_in_edges.push_back(*i1);
                                ++i1;
                            }
                            else if (((*i1)->source) < ((*i2)->source))
                            {
                                new_in_edges.push_back(*i1);
                                ++i1;
                            }
                            else if ((*i1)->source > (*i2)->source)
                            {
                                new_in_edges.push_back(*i2);
                                ++i2;
                            }
                            else // if the sources are equal
                            {
                                bool i1_is_better = TOptimumIsMaximum ?
                                    (*i1)->weight > (*i2)->weight :
                                    (*i1)->weight < (*i2)->weight;
                                if (i1_is_better)
                                {
                                    new_in_edges.push_back(*i1);
                                }
                                else
                                {
                                    new_in_edges.push_back(*i2);
                                }
                                ++i1;
                                ++i2;
                            }
                        }
                        in_edges[cycle_repr[i]].swap(new_in_edges);
                        new_in_edges.clear();
                    }
                    in_edges[new_repr].swap(in_edges[cycle_repr.back()]);
                    edge_weight_change[new_repr] = weight_t(0);
                    //*/
                }
            } // while (!roots.empty())

            // Extract the optimum branching

            // Find all roots of F.
            std::vector<EdgeNode *> F_roots;
            BOOST_FOREACH (EdgeNode *en, F)
            {
                if (en->parent == 0)
                {
                    F_roots.push_back(en);
                }
            }

            // Remove edges entering the root nodes.
            BOOST_FOREACH (vertex_idx_t v, final_roots)
            {
                if (lambda[v] != 0)
                {
                    remove_from_F(lambda[v], F_roots);
                }
            }

            while (!F_roots.empty())
            {
                EdgeNode *en = F_roots.back(); F_roots.pop_back();
                if (en->removed_from_F)
                    continue;

                *out = en->edge;
                ++out;
                remove_from_F(lambda[en->target], F_roots);
            }
        }

    };
}

template <bool TOptimumIsMaximum,
          bool TAttemptToSpan,
          bool TGraphIsDense,
          class TEdgeListGraph,
          class TVertexIndexMap,
          class TWeightMap,
          class TInputIterator,
          class TOutputIterator>
void
edmonds_optimum_branching(TEdgeListGraph &g,
                          TVertexIndexMap index,
                          TWeightMap weight,
                          TInputIterator roots_begin,
                          TInputIterator roots_end,
                          TOutputIterator out)
{
    using namespace boost;

    typedef typename graph_traits<TEdgeListGraph>::edge_descriptor    Edge;
    typedef typename graph_traits<TEdgeListGraph>::vertex_descriptor  Vertex;
    typedef typename graph_traits<TEdgeListGraph>::edge_iterator      EdgeIter;
    typedef typename property_traits<TWeightMap>::value_type          weight_t;

    function_requires< EdgeListGraphConcept<TEdgeListGraph> >();
    function_requires< ReadablePropertyMapConcept<TWeightMap, Edge> >();
    function_requires< ReadablePropertyMapConcept<TVertexIndexMap, Vertex> >();
    function_requires< InputIteratorConcept<TInputIterator> >();
    function_requires< OutputIteratorConcept<TOutputIterator, Edge> >();
    //!! Add the following requirements:
    //
    // property_traits<TVertexIndexMap>::value_type is a built-in
    // integral type, or perhaps require that it can be used to index
    // into arrays.
    //
    // property_traits<TWeightMap>::value_type is a numeric type that
    // handles the operations +, -, and <.
    //
    // TInputIterator's value type is Vertex
    // TOutputIterator's value type is Edge

    ::detail::OptimumBranching<TOptimumIsMaximum, TAttemptToSpan,
        TGraphIsDense, TEdgeListGraph, TVertexIndexMap, TWeightMap,
        TInputIterator, TOutputIterator>
          optimum_branching(g, index, weight, roots_begin, roots_end, out);
    optimum_branching();
}

#endif // not EDMONDS_OPTIMUM_BRANCHING_IMPL_HPP

ext: hpp


text:
#pragma once

#include <msw/config.hpp>

#ifdef MSW_MSVC
#   pragma warning (push)
#   pragma warning (disable: 4512)
#endif

#include <boost/bimap.hpp>

#ifdef MSW_MSVC
#   pragma warning (pop)
#endif

max_stars_repo_name: yklishevich/RubetekIOS-CPP-releases

max_issues_repo_name: yklishevich/RubetekIOS-CPP-releases

max_forks_repo_name: yklishevich/RubetekIOS-CPP-releases


text:
/*
 * Copyright (c) 2012, 2013 Aldebaran Robotics. All rights reserved.
 * Use of this source code is governed by a BSD-style license that can be
 * found in the COPYING file.
 */

#ifdef _WIN32
# include <winsock2.h>
# include <process.h>  // for _getpid
# include <windows.h>
#else
# include <arpa/inet.h>
# include <unistd.h> // for getpid
#endif
#ifdef ANDROID
# include <sys/socket.h>
#endif
#include <limits>
#include <boost/filesystem/fstream.hpp>
#include <cstdio>
#include <future>

#include <gtest/gtest.h>
#include <boost/filesystem.hpp>
#include <boost/uuid/uuid_io.hpp>

#include <qi/path.hpp>
#include <qi/os.hpp>
#include <ka/scoped.hpp>
#include "testutils/testutils.hpp"

static std::chrono::milliseconds timeout()
{
  return std::chrono::milliseconds{1000};
}

#ifdef _MSC_VER
# pragma warning( push )
// truncation of constant value when building char* objects
# pragma warning( disable : 4309 )
#endif
class QiOSTests: public ::testing::Test
{
public:
  QiOSTests()
    : a_newPath()
  {
  }

protected:
  void SetUp() {
    a_newPath = qi::os::mktmpdir("QiOsTest");
    a_newPath.append(a_accent, qi::unicodeFacet());
    FILE* fileHandle = qi::os::fopen(a_newPath.string(qi::unicodeFacet()).c_str(), "w");
    fclose(fileHandle);
  }

  void TearDown() {
    if(boost::filesystem::exists(a_newPath)) {
      try {
        boost::filesystem::remove_all(a_newPath.parent_path());
      } catch (std::exception &) {
      }
    }
  }

public:
  boost::filesystem::path a_newPath;
  static const char       a_accent[4];
};

// "" in utf-8 w. french locale.
const char QiOSTests::a_accent[4] =  { (char) '/', (char) 0xc3, (char) 0xa9, (char) '\0' } ;

TEST_F(QiOSTests, LowLevelAccent)
{
  // Try to retrieve the file.
  // The name must be in utf-8 to be retrieved on unix.
  ASSERT_TRUE(boost::filesystem::exists(a_newPath))
    << a_newPath.string() << std::endl;
}

TEST(QiOs, fnmatch)
{
  EXPECT_TRUE(qi::os::fnmatch("fnmatch", "fnmatch"));
  EXPECT_FALSE(qi::os::fnmatch("fnmatc", "fnmatch"));
  EXPECT_TRUE(qi::os::fnmatch("fn*ch", "fnmatch"));
  EXPECT_FALSE(qi::os::fnmatch("fz*ch", "fnmatch"));
  EXPECT_TRUE(qi::os::fnmatch("fn???ch", "fnmatch"));
  EXPECT_FALSE(qi::os::fnmatch("fn?z?ch", "fnmatch"));
}

// TODO: us qi::time when it's available :)
TEST(QiOs, sleep)
{
  qi::os::sleep(1);
}

TEST(QiOs, msleep)
{
  qi::os::msleep(1000);
}

TEST(QiOs, currentThreadName)
{
#if !defined(_WIN32)
  qi::os::setCurrentThreadName("Iamathread");
  ASSERT_EQ(std::string("Iamathread"), qi::os::currentThreadName());
#endif
}

TEST(QiOs, MemoryUsage)
{
  ASSERT_TRUE(qi::os::memoryUsage(qi::os::getpid()) > 0);
  ASSERT_EQ(0u, qi::os::memoryUsage(0));
}

TEST(QiOs, timeValCtor)
{
  qi::os::timeval t0 = qi::os::timeval();
  // t0 members are initialized to 0
  EXPECT_EQ(0, t0.tv_sec);
  EXPECT_EQ(0, t0.tv_usec);
  qi::os::timeval t1;
  // t1 members are initialized to 0
  EXPECT_EQ(0, t1.tv_sec);
  EXPECT_EQ(0, t1.tv_usec);

  // t2 members are not normalized
  qi::os::timeval t2(-1, -2);
  EXPECT_EQ(-1, t2.tv_sec);
  EXPECT_EQ(-2, t2.tv_usec);

  qi::Seconds s(123456789);
  qi::MicroSeconds us(123456);
  qi::NanoSeconds ns(789);
  qi::Duration d_us(s + us);
  qi::Duration d_ns(d_us + ns);
  qi::int64_t normalized_s = s.count();
  qi::int64_t normalized_us = us.count();

  // positive
  {
    qi::os::timeval tv0(d_us);
    EXPECT_EQ(normalized_s, tv0.tv_sec);
    EXPECT_EQ(normalized_us, tv0.tv_usec);

    qi::Duration d_back = qi::Seconds(tv0.tv_sec) +
                          qi::MicroSeconds(tv0.tv_usec);
    EXPECT_TRUE(d_us - d_back < qi::MicroSeconds(1));
    qi::os::timeval tv1(d_us);
    EXPECT_EQ(normalized_s, tv1.tv_sec);
    EXPECT_EQ(normalized_us, tv1.tv_usec);
  }
  // negative
  d_us = -d_us;
  d_ns = -d_ns;
  normalized_s = -s.count() - 1;
  normalized_us = -us.count() + 1000000;
  {
    qi::os::timeval tv0(d_us);
    EXPECT_EQ(normalized_s, tv0.tv_sec);
    EXPECT_EQ(normalized_us, tv0.tv_usec);

    qi::Duration d_back = qi::Seconds(tv0.tv_sec) +
                          qi::MicroSeconds(tv0.tv_usec);
    EXPECT_TRUE(d_us - d_back < qi::MicroSeconds(1));
    qi::os::timeval tv1(d_us);
    EXPECT_EQ(normalized_s, tv1.tv_sec);
    EXPECT_EQ(normalized_us, tv1.tv_usec);
  }
}

TEST(QiOs, timeValOperator)
{
  qi::os::timeval t0;
  t0.tv_sec = 2000;
  t0.tv_usec = 999999;

  qi::os::timeval t1;
  t1.tv_sec = 2000;
  t1.tv_usec = 2000;

  qi::os::timeval t2;
  t2.tv_sec = 10;
  t2.tv_usec = 10;

  // same values as t2, but not normalized
  qi::int64_t delta = 4;
  qi::os::timeval t2a;
  t2a.tv_sec = 10 - delta;
  t2a.tv_usec = 10 + delta*1000*1000;

  delta = -1;
  qi::os::timeval t2b;
  t2b.tv_sec = 10 - delta;
  t2b.tv_usec = 10 + delta*1000*1000;

  delta = 4000;
  qi::os::timeval t2c;
  t2c.tv_sec = 10 - delta;
  t2c.tv_usec = 10 + delta*1000*1000;

  delta = std::numeric_limits<qi::int64_t>::max()/(1000*1000);
  qi::os::timeval t2d;
  t2d.tv_sec = 10 - delta;
  t2d.tv_usec = 10 + delta*1000*1000;

  qi::os::timeval res;

  res = t0 + t2;
  EXPECT_EQ(2011, res.tv_sec);
  EXPECT_EQ(9, res.tv_usec);

  res = t1 + t2;
  EXPECT_EQ(2010, res.tv_sec);
  EXPECT_EQ(2010, res.tv_usec);

  res = t1 + t2a;
  EXPECT_EQ(2010, res.tv_sec);
  EXPECT_EQ(2010, res.tv_usec);
  res = t1 + t2b;
  EXPECT_EQ(2010, res.tv_sec);
  EXPECT_EQ(2010, res.tv_usec);
  res = t1 + t2c;
  EXPECT_EQ(2010, res.tv_sec);
  EXPECT_EQ(2010, res.tv_usec);
  res = t1 + t2d;
  EXPECT_EQ(2010, res.tv_sec);
  EXPECT_EQ(2010, res.tv_usec);

  // check overflow, when summing two (not normalized) values with
  // lots of usec
  // Won't pass because currently the implementation does not
  // normalize before summing.
  // res = t2d + t2d;
  // EXPECT_EQ(20, res.tv_sec);
  // EXPECT_EQ(20, res.tv_usec);

  res =  t1 - t2;
  EXPECT_EQ(1990, res.tv_sec);
  EXPECT_EQ(1990, res.tv_usec);

  res = t2 - t1;
  // result gets normalized
  // -1990*1000*1000 - 1990 == -1991*1000*1000 + 1000*1000 - 1990
  EXPECT_EQ(-1991, res.tv_sec);
  EXPECT_EQ(1000*1000 - 1990, res.tv_usec);

  res = t2 + 10L;
  EXPECT_EQ(10, res.tv_sec);
  EXPECT_EQ(20, res.tv_usec);

  res = t2 + 1000000L;
  ASSERT_EQ(11, res.tv_sec);
  ASSERT_EQ(10, res.tv_usec);

  res = t2 - 10L;
  EXPECT_EQ(10, res.tv_sec);
  EXPECT_EQ(0, res.tv_usec);

  res = t2 - 1000000L;
  ASSERT_EQ(9, res.tv_sec);
  ASSERT_EQ(10, res.tv_usec);
}

TEST(QiOs, DISABLED_timeValOperator)
{
  qi::int64_t delta = std::numeric_limits<qi::int64_t>::max()/(1000*1000);
  qi::os::timeval t2d;
  t2d.tv_sec = 10 - delta;
  t2d.tv_usec = 10 + delta*1000*1000;

  qi::os::timeval res;

  // check overflow, when summing two (not normalized) values with
  // lots of usec
  // Won't pass because currently the implementation does not
  // normalize before summing.
  res = t2d + t2d;
  EXPECT_EQ(20, res.tv_sec);
  EXPECT_EQ(20, res.tv_usec);
}

TEST(QiOs, env)
{
  int ret = qi::os::setenv("TITI", "TUTU");
  ASSERT_FALSE(ret);
  EXPECT_EQ("TUTU", qi::os::getenv("TITI"));
}

TEST(QiOs, envParam)
{
  int ret = qi::os::setenv("TITI", "45");
  ASSERT_FALSE(ret);
  EXPECT_EQ(45, qi::os::getEnvParam<int>("TITI", -1));
  EXPECT_EQ('z', qi::os::getEnvParam<char>("TOTO", 'z'));
}

TEST(QiOs, getpid)
{
// getpid is deprecated on windows, we should use _getpid instead
#ifdef _WIN32
  ASSERT_EQ(_getpid(), qi::os::getpid());
#else
  ASSERT_EQ(getpid(), qi::os::getpid());
#endif
}

TEST(QiOs, tmp)
{
  std::string temp = qi::os::tmp();

  ASSERT_NE(temp, std::string(""));

  EXPECT_TRUE(boost::filesystem::exists(temp));
  EXPECT_TRUE(boost::filesystem::is_directory(temp));
}

//check if the folder exists and is writable
void test_writable_and_empty(std::string fdir) {
  std::string             tempfile;
  boost::filesystem::path p(fdir, qi::unicodeFacet());
  boost::filesystem::path pp(fdir, qi::unicodeFacet());

  EXPECT_TRUE(boost::filesystem::exists(p));
  EXPECT_TRUE(boost::filesystem::is_directory(p));

  pp.append("tmpfile", qi::unicodeFacet());
  tempfile = pp.string(qi::unicodeFacet());

  FILE *f = qi::os::fopen(tempfile.c_str(), "w+");
  EXPECT_TRUE(f != NULL);
  fclose(f);

  EXPECT_TRUE(boost::filesystem::exists(pp));
  EXPECT_TRUE(boost::filesystem::is_regular_file(pp));

  boost::filesystem::directory_iterator it(p);

  EXPECT_EQ(pp, it->path());
  it++;

  EXPECT_TRUE((boost::filesystem::directory_iterator() == it));

}

void clean_dir(std::string fdir) {
  if(boost::filesystem::exists(fdir)) {
    //fail is dir is not removable => dir should be removable
    boost::filesystem::remove_all(fdir);
  }
}

TEST(QiOs, tmpdir_noprefix)
{
  std::string temp = qi::os::mktmpdir();
  test_writable_and_empty(temp);
  clean_dir(temp);
}

TEST(QiOs, tmpdir_tmpdir)
{
  std::string temp1 = qi::os::mktmpdir();
  std::string temp2 = qi::os::mktmpdir();
  EXPECT_NE(temp1, temp2);
  clean_dir(temp1);
  clean_dir(temp2);
}

TEST(QiOs, tmpdir_parent)
{
  std::string temp = qi::os::mktmpdir("plaf");

  boost::filesystem::path ppa(temp, qi::unicodeFacet());
  ppa = ppa.parent_path();

  boost::filesystem::path ppatmp(qi::os::tmp(), qi::unicodeFacet());
  EXPECT_TRUE(boost::filesystem::equivalent(ppa, ppatmp));

  clean_dir(temp);
}

TEST(QiOs, tmpdir_prefix)
{
  std::string temp = qi::os::mktmpdir("plaf");

  test_writable_and_empty(temp);

  boost::filesystem::path pp(temp, qi::unicodeFacet());
  std::string tempfname = pp.filename().string(qi::unicodeFacet());

  EXPECT_EQ(tempfname[0], 'p');
  EXPECT_EQ(tempfname[1], 'l');
  EXPECT_EQ(tempfname[2], 'a');
  EXPECT_EQ(tempfname[3], 'f');

  clean_dir(temp);
}

TEST(QiOs, tmpdir_prefix_accentuated)
{
  char utf8[]     = { (char) 0xC5, (char) 0xAA, (char) 0x6E, (char) 0xC4, (char) 0xAD, (char) 0x63, (char) 0xC5, (char) 0x8D, (char) 0x64, (char) 0x65, (char) 0xCC, (char) 0xBD, (char) 0 };

  std::string temp = qi::os::mktmpdir(utf8);

  test_writable_and_empty(temp);
  clean_dir(temp);
}

TEST(QiOs, tmpdir_prefix_zero)
{
  std::string temp = qi::os::mktmpdir(0);
  test_writable_and_empty(temp);
  clean_dir(temp);
}

TEST(QiOs, get_host_name)
{
  std::string temp = qi::os::gethostname();
  EXPECT_NE(std::string(), temp);
}

bool freeportbind(unsigned short port, int &sock)
{
  struct sockaddr_in name;
  name.sin_family = AF_INET;
  name.sin_addr.s_addr = htonl(INADDR_ANY);
  sock = static_cast<int>(::socket(AF_INET, SOCK_STREAM, 0));
  name.sin_port = htons(port);

  return (::bind(sock, (struct sockaddr *)&name, sizeof(name))) != 0;
}

TEST(QiOs, free_port)
{
  int sock;
  unsigned short port = qi::os::findAvailablePort(9559);
  ASSERT_GT(port, 0);
  int success = freeportbind(port, sock);

  if (success == -1)
    EXPECT_TRUE(false);
  else
#ifndef _WIN32
    ::close(sock);
#else
    ::closesocket(sock);
#endif

  EXPECT_TRUE(true);
}

TEST(QiOs, free_port2)
{
  int sock;
  unsigned short port = qi::os::findAvailablePort(54010);
  ASSERT_GT(port, 0);
  int success = freeportbind(port, sock);

  if (success == -1)
    EXPECT_TRUE(false);
  else
#ifndef _WIN32
    ::close(sock);
#else
    ::closesocket(sock);
#endif

  EXPECT_TRUE(true);
}

TEST(QiOs, free_port_multiple_connection)
{
  int sock1;
  unsigned short port1 = qi::os::findAvailablePort(9559);
  ASSERT_GT(port1, 0);
  int success1 = freeportbind(port1, sock1);
  int sock2;
  unsigned short port2 = qi::os::findAvailablePort(9559);
  ASSERT_GT(port2, 0);
  int success2 = freeportbind(port2, sock2);
  int sock3;
  unsigned short port3 = qi::os::findAvailablePort(9559);
  ASSERT_GT(port3, 0);
  int success3 = freeportbind(port3, sock3);

  if (success1 == -1)
    EXPECT_TRUE(false);
  else
#ifndef _WIN32
    ::close(sock1);
#else
    ::closesocket(sock1);
#endif
  if (success2 == -1)
    EXPECT_TRUE(false);
  else
#ifndef _WIN32
    ::close(sock2);
#else
    ::closesocket(sock2);
#endif
  if (success3 == -1)
    EXPECT_TRUE(false);
  else
#ifndef _WIN32
    ::close(sock3);
#else
    ::closesocket(sock3);
#endif

  EXPECT_TRUE(true);
}

TEST(QiOs, hostIPAddrs)
{
  std::map<std::string, std::vector<std::string> > ifsMap;

  ifsMap = qi::os::hostIPAddrs();
  ASSERT_TRUE(ifsMap.empty() == false);
}

TEST(QiOs, concurrentHostIPAddrs)
{
  using IfsMap = std::map<std::string, std::vector<std::string>>;
  const auto n = 200;

  std::vector<std::future<IfsMap>> futureMaps;
  futureMaps.reserve(n);

  for (auto i = 0; i < n; ++i)
  {
    std::cout << i << std::endl;
    futureMaps.push_back(std::async(std::launch::async,
                                    [] () {
      return qi::os::hostIPAddrs(false);
    }));
  }

  for (auto i = 0; i < n; ++i)
  {
    auto &future = futureMaps[i];
    future.wait();
    std::cout << "future " << i << " set" << std::endl;
    auto ifsMap = future.get();
    ASSERT_FALSE(ifsMap.empty());
    for (const auto &it : ifsMap)
    {
      std::cout << it.first << " : " << std::endl;
      for (const auto &tmp : it.second)
      {
        std::cout << tmp << "; ";
      }
      std::cout << std::endl;
    }
  }
}

TEST(QiOs, sequentialHostIPAddrs)
{
  const auto n = 10000;
  for (auto i = 0; i < n; ++i)
  {
    std::cout << i << std::endl;
    auto ifsMap = qi::os::hostIPAddrs(false);
    ASSERT_FALSE(ifsMap.empty());
  }
}

TEST(QiOs, getMachineId)
{
  int status = 0;
  std::string bin = qi::path::findBin("check_machineid");
  ASSERT_FALSE(bin.empty());
  int childPid = qi::os::spawnlp(bin.c_str(), NULL);
  ASSERT_NE(-1, childPid);

  int error = qi::os::waitpid(childPid, &status);
  EXPECT_EQ(0, error);
  EXPECT_EQ(0, status);

  std::string uuid1 = qi::os::getMachineId();
  std::string uuid2;

  const qi::Path uuid2FileName = (qi::os::tmp()).append("machine_id_test_42");
  boost::filesystem::ifstream uuid2file(uuid2FileName);

  ASSERT_TRUE(uuid2file);

  uuid2file >> uuid2;
  uuid2file.close();

  ASSERT_TRUE(uuid1.compare(uuid2) == 0);
}

TEST(QiOs, getMachineIdAsUuid)
{
  using namespace qi;
  std::ostringstream ss;
  ss << os::getMachineIdAsUuid();
  EXPECT_EQ(ss.str(), os::getMachineId());
}

TEST(QiOs, getMachineIdAsUuidConst)
{
  using namespace qi;
  EXPECT_EQ(os::getMachineIdAsUuid(), os::getMachineIdAsUuid());
}

TEST(Os, getProcessUuidConstantInAProcess)
{
  using namespace qi::os;
  EXPECT_EQ(getProcessUuid(), getProcessUuid());
}

// To check that the process uuid really changes with a different process, we
// launch a helper executable that prints its process uuid in a file.
// We then read the process uuid from the file, remove the file and assert that
// the read uuid is different than ours.
TEST(Os, getProcessUuidDifferentInDifferentProcesses)
{
  using namespace qi::os;
  const auto parentProcessUuid = getProcessUuid();
  const auto childFilename = to_string(parentProcessUuid) + ".txt";
  {
    test::ScopedProcess process{
      qi::path::findBin("print_process_uuid"), {childFilename}, timeout()};
  }
  const auto _ = ka::scoped([=]() {
    boost::filesystem::remove(childFilename);
  });
  boost::filesystem::ifstream childFile{childFilename};
  qi::Uuid childProcessUuid;
  childFile >> childProcessUuid;
  EXPECT_NE(childProcessUuid, parentProcessUuid);
}

#if  defined(_WIN32) || defined(__linux__)
TEST(QiOs, CPUAffinity)
#else
TEST(QiOs, DISABLED_CPUAffinity)
#endif
{
  std::vector<int> cpus;
  long nprocs_max = -1;

  cpus.push_back(0);
  cpus.push_back(1);
  ASSERT_TRUE(qi::os::setCurrentThreadCPUAffinity(cpus));

  nprocs_max = qi::os::numberOfCPUs();
  ASSERT_TRUE(nprocs_max > 0);

  cpus.clear();
  cpus.push_back(nprocs_max + 1);
  ASSERT_FALSE(qi::os::setCurrentThreadCPUAffinity(cpus));
}

TEST(QiOs, dlerror)
{
  qi::os::dlerror(); // Reset errno value
  const char *error0 = qi::os::dlerror();
  // expect NULL since no error has occurred since initialization
  EXPECT_TRUE(error0 == NULL) << "Expected NULL, got: " << error0;

  qi::os::dlerror(); // Reset errno value
  qi::os::dlopen("failure.so");
  EXPECT_TRUE(qi::os::dlerror() != NULL) << "Expected error got NULL";
  const char *error1 = qi::os::dlerror(); // reset
  // expect NULL since no error has occurred since last dlerror call
  EXPECT_TRUE(error1 == NULL) << "Expected NULL, got: " << error1;

#ifndef __linux__
  // dlclose segfault on linux if an invalid pointer is given
  qi::os::dlerror(); // Reset errno value
  EXPECT_NE(0, qi::os::dlclose((void*) 123));
  const char* error2 = qi::os::dlerror();
  EXPECT_NE((const char*) NULL, error2);
#endif
}

TEST(QiOs, ptrUid)
{
  using namespace qi;
  void* ptr = &ptr;
  const auto ptruid = os::ptrUid(ptr);
  const auto expectedPtrUid = PtrUid(os::getMachineIdAsUuid(), os::getProcessUuid(), ptr);
  ASSERT_EQ(expectedPtrUid, ptruid);
}

#ifdef _MSC_VER
# pragma warning( pop )
#endif

ext: cpp

max_stars_repo_name: yumilceh/libqi

max_issues_repo_name: yumilceh/libqi

max_forks_repo_name: yumilceh/libqi


text:
/*
 * Copyright 2021 INRIA
 */

#ifndef __eigenpy_decomposition_minres_hpp__
#define __eigenpy_decomposition_minres_hpp__

#include "eigenpy/eigenpy.hpp"

#include <iostream>
#include <Eigen/Core>
#include <unsupported/Eigen/IterativeSolvers>

#include "eigenpy/utils/scalar-name.hpp"

namespace eigenpy
{
  template<typename _Solver>
  struct IterativeSolverBaseVisitor
  : public boost::python::def_visitor< IterativeSolverBaseVisitor<_Solver> >
  {
    typedef _Solver Solver;
    typedef typename Solver::MatrixType MatrixType;
    typedef typename Solver::Preconditioner Preconditioner;
    typedef typename Solver::Scalar Scalar;
    typedef typename Solver::RealScalar RealScalar;

    typedef Eigen::Matrix<Scalar,Eigen::Dynamic,Eigen::Dynamic,MatrixType::Options> MatrixXs;

    template<class PyClass>
    void visit(PyClass& cl) const
    {
      namespace bp = boost::python;
      cl
      .def("analyzePattern",
           (Solver & (Solver::*)(const Eigen::EigenBase<MatrixType> & matrix))&Solver::analyzePattern,
           bp::args("self","A"),
           "Initializes the iterative solver for the sparsity pattern of the matrix A for further solving Ax=b problems.",
           bp::return_self<>())
      .def("factorize",
           (Solver & (Solver::*)(const Eigen::EigenBase<MatrixType> & matrix))&Solver::factorize,
           bp::args("self","A"),
           "Initializes the iterative solver with the numerical values of the matrix A for further solving Ax=b problems.",
           bp::return_self<>())
      .def("compute",
           (Solver & (Solver::*)(const Eigen::EigenBase<MatrixType> & matrix))&Solver::compute,
           bp::args("self","A"),
           "Initializes the iterative solver with the matrix A for further solving Ax=b problems.",
           bp::return_self<>())

      .def("rows",&Solver::rows,bp::arg("self"),"Returns the number of rows.")
      .def("cols",&Solver::cols,bp::arg("self"),"Returns the number of columns.")
      .def("tolerance",&Solver::tolerance,bp::arg("self"),
           "Returns the tolerance threshold used by the stopping criteria.")
      .def("setTolerance",&Solver::setTolerance,bp::args("self","tolerance"),
           "Sets the tolerance threshold used by the stopping criteria.\n"
           "This value is used as an upper bound to the relative residual error: |Ax-b|/|b|.\n"
           "The default value is the machine precision given by NumTraits<Scalar>::epsilon().",
           bp::return_self<>())
      .def("preconditioner",(Preconditioner & (Solver::*)())&Solver::preconditioner,bp::arg("self"),
           "Returns a read-write reference to the preconditioner for custom configuration.",
           bp::return_internal_reference<>())

      .def("maxIterations",&Solver::maxIterations,bp::arg("self"),
           "Returns the max number of iterations.\n"
           "It is either the value setted by setMaxIterations or, by default, twice the number of columns of the matrix.")
      .def("setMaxIterations",&Solver::setMaxIterations,bp::args("self","max_iterations"),
           "Sets the max number of iterations.\n"
           "Default is twice the number of columns of the matrix.",
           bp::return_self<>())

      .def("iterations",&Solver::iterations,bp::arg("self"),
           "Returns the number of iterations performed during the last solve.")
      .def("error",&Solver::error,bp::arg("self"),
           "Returns the tolerance error reached during the last solve.\n"
           "It is a close approximation of the true relative residual error |Ax-b|/|b|.")
      .def("info",&Solver::error,bp::arg("info"),
           "Returns Success if the iterations converged, and NoConvergence otherwise.")

      .def("solveWithGuess",&solveWithGuess<MatrixXs,MatrixXs>,bp::args("self","b","x0"),
           "Returns the solution x of A x = b using the current decomposition of A and x0 as an initial solution.")

      .def("solve",&solve<MatrixXs>,bp::args("self","b"),
           "Returns the solution x of A x = b using the current decomposition of A where b is a right hand side matrix or vector.")
      ;
    }

  private:

    template<typename MatrixOrVector1, typename MatrixOrVector2>
    static MatrixOrVector1 solveWithGuess(const Solver & self, const MatrixOrVector1 & b, const MatrixOrVector2 & guess)
    {
      return self.solveWithGuess(b,guess);
    }

    template<typename MatrixOrVector>
    static MatrixOrVector solve(const Solver & self, const MatrixOrVector & mat_or_vec)
    {
      MatrixOrVector res = self.solve(mat_or_vec);
      return res;
    }
  };

  template<typename _MatrixType>
  struct MINRESSolverVisitor
  : public boost::python::def_visitor< MINRESSolverVisitor<_MatrixType> >
  {

    typedef _MatrixType MatrixType;
    typedef typename MatrixType::Scalar Scalar;
    typedef typename MatrixType::RealScalar RealScalar;
    typedef Eigen::Matrix<Scalar,Eigen::Dynamic,1,MatrixType::Options> VectorXs;
    typedef Eigen::Matrix<Scalar,Eigen::Dynamic,Eigen::Dynamic,MatrixType::Options> MatrixXs;
    typedef Eigen::MINRES<MatrixType> Solver;

    template<class PyClass>
    void visit(PyClass& cl) const
    {
      namespace bp = boost::python;
      cl
      .def(bp::init<>("Default constructor"))
      .def(bp::init<MatrixType>(bp::arg("matrix"),
                                "Initialize the solver with matrix A for further Ax=b solving.\n"
                                "This constructor is a shortcut for the default constructor followed by a call to compute()."))

      .def(IterativeSolverBaseVisitor<Solver>())
      ;
    }

    static void expose()
    {
      static const std::string classname = "MINRES" + scalar_name<Scalar>::shortname();
      expose(classname);
    }

    static void expose(const std::string & name)
    {
      namespace bp = boost::python;
      bp::class_<Solver, boost::noncopyable>(name.c_str(),
                         "A minimal residual solver for sparse symmetric problems.\n"
                         "This class allows to solve for A.x = b sparse linear problems using the MINRES algorithm of Paige and Saunders (1975). The sparse matrix A must be symmetric (possibly indefinite). The vectors x and b can be either dense or sparse.\n"
                         "The maximal number of iterations and tolerance value can be controlled via the setMaxIterations() and setTolerance() methods. The defaults are the size of the problem for the maximal number of iterations and NumTraits<Scalar>::epsilon() for the tolerance.\n",
                         bp::no_init)
      .def(MINRESSolverVisitor());
    }

  private:

    template<typename MatrixOrVector>
    static MatrixOrVector solve(const Solver & self, const MatrixOrVector & vec)
    {
      return self.solve(vec);
    }
  };

} // namespace eigenpy

#endif // ifndef __eigenpy_decomposition_minres_hpp__

max_stars_repo_name: seanyen/eigenpy

max_issues_repo_name: seanyen/eigenpy

max_forks_repo_name: seanyen/eigenpy


text:
/* <dory/compress/snappy/snappy_codec.cc>

   ----------------------------------------------------------------------------
   Copyright 2013-2014 if(we)

   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.
   ----------------------------------------------------------------------------

   Implements <dory/compress/snappy/snappy_codec.h>.
 */

#include <dory/compress/snappy/snappy_codec.h>

#include <cassert>
#include <memory>
#include <mutex>
#include <string>

#include <boost/lexical_cast.hpp>

#include <dory/compress/snappy/lib_snappy.h>
#include <server/counter.h>

using namespace Dory;
using namespace Dory::Compress;
using namespace Dory::Compress::Snappy;

SERVER_COUNTER(SnappyBufferTooSmallError);
SERVER_COUNTER(SnappyInvalidInputError);
SERVER_COUNTER(SnappyUnknownError);

static void CheckSnappyStatus(snappy_status status,
    const char *snappy_function_name) {
  assert(snappy_function_name);

  if (status == SNAPPY_OK) {
    return;
  }

  std::string msg("Function ");
  msg += snappy_function_name;
  msg += " reported ";

  switch (status) {
    case SNAPPY_INVALID_INPUT: {
      SnappyInvalidInputError.Increment();
      msg += "invalid input";
      break;
    }
    case SNAPPY_BUFFER_TOO_SMALL: {
      SnappyBufferTooSmallError.Increment();
      msg += "buffer too small";
      break;
    }
    default: {
      SnappyUnknownError.Increment();
      msg += "unknown error ";
      msg += boost::lexical_cast<std::string>(status);
      break;
    }
  }

  throw TCompressionCodecApi::TError(msg.c_str());
}

static std::mutex SingletonInitMutex;

static std::unique_ptr<const TSnappyCodec> Singleton;

const TSnappyCodec &TSnappyCodec::The() {
  if (!Singleton) {
    std::lock_guard<std::mutex> lock(SingletonInitMutex);

    if (!Singleton) {
      Singleton.reset(new TSnappyCodec);
    }
  }

  return *Singleton;
}

size_t TSnappyCodec::ComputeCompressedResultBufSpace(
    const void * /*uncompressed_data*/, size_t uncompressed_size) const {
  assert(this);
  return Lib.snappy_max_compressed_length(uncompressed_size);
}

size_t TSnappyCodec::Compress(const void *input_buf, size_t input_buf_size,
    void *output_buf, size_t output_buf_size) const {
  assert(this);
  CheckSnappyStatus(Lib.snappy_compress(
      reinterpret_cast<const char *>(input_buf), input_buf_size,
      reinterpret_cast<char *>(output_buf), &output_buf_size),
                    "snappy_compress()");

  /* Return true size of compressed output (set by above library call). */
  return output_buf_size;
}

size_t TSnappyCodec::ComputeUncompressedResultBufSpace(
    const void *compressed_data, size_t compressed_size) const {
  assert(this);
  size_t result = 0;
  CheckSnappyStatus(Lib.snappy_uncompressed_length(
      reinterpret_cast<const char *>(compressed_data), compressed_size,
      &result),
                    "snappy_uncompressed_length()");
  return result;
}

size_t TSnappyCodec::Uncompress(const void *input_buf, size_t input_buf_size,
    void *output_buf, size_t output_buf_size) const {
  assert(this);
  CheckSnappyStatus(Lib.snappy_uncompress(
      reinterpret_cast<const char *>(input_buf), input_buf_size,
      reinterpret_cast<char *>(output_buf), &output_buf_size),
                    "snappy_uncompress()");

  /* Return true size of uncompressed output (set by above library call). */
  return output_buf_size;
}

TSnappyCodec::TSnappyCodec()
    : Lib(*TLibSnappy::The()) {
}

ext: cc

max_stars_repo_name: femtonaut/dory

max_issues_repo_name: femtonaut/dory

max_forks_repo_name: femtonaut/dory


text:
/*
 * OBJLoader.cpp
 *
 *  Created on: 13.05.2018
 *      Author: Christoph Neuhauser
 */

#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <boost/algorithm/string.hpp>
#include <boost/algorithm/string/split.hpp>
#include <glm/glm.hpp>

#include <Utils/File/Logfile.hpp>
#include <Utils/File/FileUtils.hpp>
#include <Utils/Convert.hpp>
#include <Graphics/Shader/ShaderManager.hpp>
#include <Graphics/Shader/ShaderAttributes.hpp>
#include <Graphics/Renderer.hpp>

#include "MeshSerializer.hpp"
#include "KDTree.hpp"

using namespace std;
using namespace sgl;

// Converts a triangle strip to normal triangles (see OpenGL vertex modes for more information)
void triangleStripToTriangles(vector<uint32_t> tristrip, vector<uint32_t> &triangles) {
    if (tristrip.size() < 3) {
        return;
    }

    for (size_t i = 3; i < tristrip.size(); i++) {
        triangles.push_back(tristrip.at(i));
    }
    for (size_t i = 3; i < tristrip.size(); i++) {
        if (i % 2 == 0) {
            triangles.push_back(tristrip[i-2]);
            triangles.push_back(tristrip[i-1]);
            triangles.push_back(tristrip[i]);
        } else {
            triangles.push_back(tristrip[i]);
            triangles.push_back(tristrip[i-1]);
            triangles.push_back(tristrip[i-2]);
        }
    }
}

// Converts a triangle fan to normal triangles (see OpenGL vertex modes for more information)
void triangleFanToTriangles(vector<uint32_t> trifan, vector<uint32_t> &triangles) {
    if (trifan.size() < 3) {
        return;
    }

    //std::reverse(triangles.begin(), triangles.end());

    for (size_t i = 3; i < trifan.size(); i++) {
        triangles.push_back(trifan.at(i));
    }
    for (size_t i = 3; i < trifan.size(); i++) {
        triangles.push_back(trifan[0]);
        triangles.push_back(trifan[i-1]);
        triangles.push_back(trifan[i]);
    }
}

struct TempSubmesh
{
    TempSubmesh() : smooth(false) {}

    ObjMaterial material;
    bool smooth;

    std::vector<uint32_t> vertexIndices;
    std::vector<uint32_t> tecoordIndices;
    std::vector<uint32_t> normalIndices;
};

void globalIndicesToLocal(std::vector<uint32_t> &globalIndexBuffer, std::vector<glm::vec3> &globalVertexBuffer,
                          std::vector<uint32_t> &localIndexBuffer, std::vector<glm::vec3> &localVertexBuffer)
{
    // Create global indices <-> local indices mapping
    std::vector<uint32_t> sortedIndexBuffer = globalIndexBuffer;
    std::sort(sortedIndexBuffer.begin(), sortedIndexBuffer.end());
    std::map<uint32_t, uint32_t> mappingGlobalToLocal;
    std::map<uint32_t, uint32_t> mappingLocalToGlobal;
    size_t index = 0;
    for (size_t i = 0; i < globalIndexBuffer.size(); i++) {
        if (i == 0 || sortedIndexBuffer.at(i) != sortedIndexBuffer.at(i-1)) {
            mappingGlobalToLocal.insert(make_pair(sortedIndexBuffer.at(i), index));
            mappingLocalToGlobal.insert(make_pair(index, sortedIndexBuffer.at(i)));
            index++;
        }
    }

    localVertexBuffer.resize(index);
    for (size_t i = 0; i < index; i++) {
        localVertexBuffer.at(i) = globalVertexBuffer.at(mappingLocalToGlobal[i]);
    }
    localIndexBuffer.resize(globalIndexBuffer.size());
    for (size_t i = 0; i < globalIndexBuffer.size(); i++) {
        localIndexBuffer.at(i) = mappingGlobalToLocal[globalIndexBuffer.at(i)];
    }
}

void processTempSubmesh(ObjMesh &mesh, TempSubmesh &tempSubmesh, std::vector<glm::vec3> &globalVertices,
        std::vector<glm::vec2> &globalTexcoords, std::vector<glm::vec3> &globalNormals)
{
    // Input
    bool smooth = tempSubmesh.smooth;
    std::vector<uint32_t> &vertexIndices = tempSubmesh.vertexIndices;
    std::vector<uint32_t> &tecoordIndices = tempSubmesh.tecoordIndices;
    std::vector<uint32_t> &normalIndices = tempSubmesh.normalIndices;

    // Output
    ObjSubmesh submesh;
    std::vector<uint32_t> &indices = submesh.indices;
    std::vector<glm::vec3> &vertices = submesh.vertices;
    std::vector<glm::vec2> &texcoords = submesh.texcoords;
    std::vector<glm::vec3> &normals = submesh.normals;
    submesh.material = tempSubmesh.material;

    if (!smooth) {
        for (size_t i = 0; i < vertexIndices.size(); i++) {
            vertices.push_back(globalVertices.at(vertexIndices.at(i)));
            //if (tecoordIndices.size() > 0)
            //  texcoords.push_back(globalTexcoords.at(tecoordIndices.at(i)));
            if (normalIndices.size() > 0)
                normals.push_back(globalNormals.at(normalIndices.at(i)));
        }

        if (normalIndices.size() == 0) {
            // Compute manually
            for (size_t i = 0; i < vertices.size(); i += 3) {
                glm::vec3 normal = glm::cross(vertices.at(i) - vertices.at(i+1), vertices.at(i) - vertices.at(i+2));
                normal = glm::normalize(normal);
                normals.push_back(normal);
                normals.push_back(normal);
                normals.push_back(normal);
            }
        }
    } else {
        std::vector<uint32_t> &globalIndices = vertexIndices;
        globalIndicesToLocal(globalIndices, globalVertices, indices, vertices);

        // For finding all triangles with a specific index. Maps vertex index -> first triangle index.
        std::multimap<size_t, size_t> indexMap;
        for (size_t j = 0; j < indices.size(); j++) {
            indexMap.insert(make_pair(indices.at(j), (j/3)*3));
        }

        for (size_t i = 0; i < vertices.size(); i++) {
            glm::vec3 normal(0.0f, 0.0f, 0.0f);
            int numTrianglesSharedBy = 0;
            auto triangleRange = indexMap.equal_range(i);
            for (auto it = triangleRange.first; it != triangleRange.second; it++) {
                size_t j = it->second;
                size_t i1 = indices.at(j), i2 = indices.at(j+1), i3 = indices.at(j+2);
                glm::vec3 faceNormal = glm::cross(vertices.at(i1) - vertices.at(i2), vertices.at(i1) - vertices.at(i3));
                faceNormal = glm::normalize(faceNormal);
                normal += faceNormal;
                numTrianglesSharedBy++;
            }
            /*for (size_t j = 0; j < indices.size(); j += 3) {
                // Does this triangle contain vertex #i?
                if (indices.at(j) == i || indices.at(j+1) == i || indices.at(j+2) == i) {
                    size_t i1 = indices.at(j), i2 = indices.at(j+1), i3 = indices.at(j+2);
                    glm::vec3 faceNormal = glm::cross(vertices.at(i1) - vertices.at(i2), vertices.at(i1) - vertices.at(i3));
                    faceNormal = glm::normalize(faceNormal);
                    normal += faceNormal;
                    numTrianglesSharedBy++;
                }
            }*/

            if (numTrianglesSharedBy == 0) {
                Logfile::get()->writeError("Error in parseObjMesh: numTrianglesSharedBy == 0");
                exit(1); // TODO: Global vertex buffer
            }
            normal /= (float)numTrianglesSharedBy;
            normals.push_back(normal);
        }
    }

    mesh.submeshes.push_back(submesh);
}

void addMaterialsFromFile(const std::string &filename, const std::string &objFilename,
        std::map<std::string, ObjMaterial> &materials)
{
    std::string absFilename = filename;
    if (!FileUtils::get()->exists(absFilename)) {
        absFilename = FileUtils::get()->getPathToFile(objFilename) + FileUtils::get()->getPureFilename(absFilename);
    }

    std::ifstream file(absFilename.c_str());

    if (!file.is_open()) {
        Logfile::get()->writeError(string() + "Error in parseObjMesh: File \"" + filename + "\" does not exist.");
        return;
    }

    std::string materialName;
    ObjMaterial currMaterial;

    std::string lineString;
    while (getline(file, lineString)) {
        while (lineString.size() > 0 && (lineString[lineString.size()-1] == '\r' || lineString[lineString.size()-1] == ' ')) {
            // Remove '\r' of Windows line ending
            lineString = lineString.substr(0, lineString.size() - 1);
        }
        std::vector<std::string> line;
        boost::algorithm::split(line, lineString, boost::is_any_of("\t "), boost::token_compress_on);

        std::string command = line.at(0);

        if (command == "newmtl") {
            // New object
            if (materialName.length() != 0) {
                materials.insert(make_pair(materialName, currMaterial));
            }
            materialName = line.at(1);
            currMaterial = ObjMaterial();
        } else if (command == "Ka") {
            // Ambient color
            currMaterial.ambientColor = glm::vec3(fromString<float>(line.at(1)), fromString<float>(line.at(2)),
                                                  fromString<float>(line.at(3)));
        }  else if (command == "Kd") {
            // Diffuse color
            currMaterial.diffuseColor = glm::vec3(fromString<float>(line.at(1)), fromString<float>(line.at(2)),
                                                  fromString<float>(line.at(3)));
        } else if (command == "Ks") {
            // Specular color
            currMaterial.specularColor = glm::vec3(fromString<float>(line.at(1)), fromString<float>(line.at(2)),
                                                   fromString<float>(line.at(3)));
        } else if (command == "Ns") {
            // Specular exponent
            currMaterial.specularExponent = fromString<float>(line.at(1));
        } else if (command == "d") {
            // Opacity
            currMaterial.opacity = fromString<float>(line.at(1));
        } else if (command == "tr") {
            // Transparency (= 1 - opacity)
            currMaterial.opacity = 1.0f - fromString<float>(line.at(1));
        } else if (command == "illum") {
            // TODO
        } else if (boost::starts_with(command, "#") || command == "") {
            // Ignore comments and empty lines
        } else {
            //Logfile::get()->writeError(string() + "Error in addMaterialsFromFile: Unknown command \"" + command + "\".");
        }
    }

    if (materialName.length() != 0) {
        materials.insert(make_pair(materialName, currMaterial));
    }

    file.close();
}

void convertObjMeshToBinary(
        const std::string &objFilename,
        const std::string &binaryFilename)
{
    std::ifstream file(objFilename.c_str());

    if (!file.is_open()) {
        Logfile::get()->writeError(string() + "Error in parseObjMesh: File \"" + objFilename + "\" does not exist.");
        return;
    }

    vector<TempSubmesh> tempMesh;
    TempSubmesh currSubmesh;
    uint32_t indexOffset = 1;
    std::map<std::string, ObjMaterial> materials;

    std::vector<glm::vec3> globalVertices;
    std::vector<glm::vec2> globalTexcoords;
    std::vector<glm::vec3> globalNormals;

    std::string lineString;
    while (getline(file, lineString)) {
        while (lineString.size() > 0 && (lineString[lineString.size()-1] == '\r' || lineString[lineString.size()-1] == ' ')) {
            // Remove '\r' of Windows line ending
            lineString = lineString.substr(0, lineString.size() - 1);
        }
        std::vector<std::string> line;
        boost::algorithm::split(line, lineString, boost::is_any_of("\t "), boost::token_compress_on);

        std::string command = line.at(0);

        if (command == "o") {
            // New object
            if (globalVertices.size() != 0) {
                tempMesh.push_back(currSubmesh);
                currSubmesh = TempSubmesh();
            }
        } else if (command == "g") {
            // Groups not supported for now
        }  else if (command == "mtllib") {
            //  Load material definition file
            addMaterialsFromFile(line.at(1), objFilename, materials);
        } else if (command == "usemtl") {
            // Use new material
            auto it = materials.find(line.at(1));
            if (it != materials.end()) {
                currSubmesh.material = it->second;
            } else if (materials.size() > 0) {
                Logfile::get()->writeError(string() + "Error in parseObjMesh: Material \""
                        + line.at(1) + "\" does not exist.");
            }
        } else if (command == "s") {
            // Smooth shading is always assumed for now
            currSubmesh.smooth = true; // TODO
        } else if (command == "v") {
            // Vertex position
            globalVertices.push_back(glm::vec3(fromString<float>(line.at(1)), fromString<float>(line.at(2)),
                    fromString<float>(line.at(3))));
        } else if (command == "vt") {
            // Texture coordinate
            globalTexcoords.push_back(glm::vec2(fromString<float>(line.at(1)),
                    fromString<float>(line.at(2))));
        } else if (command == "vn") {
            // Vertex normal
            globalNormals.push_back(glm::vec3(fromString<float>(line.at(1)), fromString<float>(line.at(2)),
                    fromString<float>(line.at(3))));
        } else if (command == "f") {
            // Face indices
            std::vector<uint32_t> tempVertexIndices;
            std::vector<uint32_t> tempTecoordIndices;
            std::vector<uint32_t> tempNormalIndices;
            for (size_t i = 1; i < line.size(); i++) {
                std::vector<std::string> indices;
                boost::algorithm::split(indices, line.at(i), boost::is_any_of("/"));
                currSubmesh.vertexIndices.push_back(atoi(indices.at(0).c_str()) - indexOffset);
                if (indices.size() > 1)
                    currSubmesh.tecoordIndices.push_back(atoi(indices.at(1).c_str()) - indexOffset);
                if (indices.size() > 2)
                    currSubmesh.normalIndices.push_back(atoi(indices.at(2).c_str()) - indexOffset);
            }
            triangleStripToTriangles(tempVertexIndices, currSubmesh.vertexIndices);
            triangleStripToTriangles(tempTecoordIndices, currSubmesh.tecoordIndices);
            triangleStripToTriangles(tempNormalIndices, currSubmesh.normalIndices);
        } else if (boost::starts_with(command, "#") || command == "") {
            // Ignore comments and empty lines
        } else {
//            Logfile::get()->writeError(string() + "Error in parseObjMesh: Unknown command \"" + command + "\".");
        }
    }

    if (globalVertices.size() != 0) {
        tempMesh.push_back(currSubmesh);
    }

    ObjMesh mesh;
    mesh.submeshes.reserve(tempMesh.size());
    for (TempSubmesh tempSubmesh : tempMesh) {
        processTempSubmesh(mesh, tempSubmesh, globalVertices, globalTexcoords, globalNormals);
    }

    file.close();

    BinaryMesh binaryMesh;
    binaryMesh.submeshes.resize(tempMesh.size());
    for (size_t i = 0; i < mesh.submeshes.size(); ++i) {
        ObjSubmesh &submesh = mesh.submeshes.at(i);
        BinarySubMesh &binarySubmesh = binaryMesh.submeshes.at(i);
        binarySubmesh.material = submesh.material;
        binarySubmesh.vertexMode = VERTEX_MODE_TRIANGLES;
        binarySubmesh.indices = submesh.indices;

        BinaryMeshAttribute positionAttribute;
        positionAttribute.name = "vertexPosition";
        positionAttribute.attributeFormat = ATTRIB_FLOAT;
        positionAttribute.numComponents = 3;
        positionAttribute.data.resize(submesh.vertices.size() * sizeof(glm::vec3));
        memcpy(&positionAttribute.data.front(), &submesh.vertices.front(), submesh.vertices.size() * sizeof(glm::vec3));
        binarySubmesh.attributes.push_back(positionAttribute);

        if (submesh.normals.size() > 0) {
            BinaryMeshAttribute normalAttribute;
            normalAttribute.name = "vertexNormal";
            normalAttribute.attributeFormat = ATTRIB_FLOAT;
            normalAttribute.numComponents = 3;
            normalAttribute.data.resize(submesh.normals.size() * sizeof(glm::vec3));
            memcpy(&normalAttribute.data.front(), &submesh.normals.front(), submesh.normals.size() * sizeof(glm::vec3));
            binarySubmesh.attributes.push_back(normalAttribute);
        }

        if (submesh.texcoords.size() > 0) {
            BinaryMeshAttribute texcoordAttribute;
            texcoordAttribute.name = "vertexTexcoords";
            texcoordAttribute.attributeFormat = ATTRIB_FLOAT;
            texcoordAttribute.numComponents = 2;
            texcoordAttribute.data.resize(submesh.texcoords.size() * sizeof(glm::vec2));
            memcpy(&texcoordAttribute.data.front(), &submesh.texcoords.front(), submesh.texcoords.size() * sizeof(glm::vec2));
            binarySubmesh.attributes.push_back(texcoordAttribute);
        }
    }

    writeMesh3D(binaryFilename, binaryMesh);
}

max_stars_repo_name: chrismile/PixelSyncOIT

max_issues_repo_name: chrismile/PixelSyncOIT

max_forks_repo_name: chrismile/PixelSyncOIT


text:
// =============================================================================
// Copyright 2017 National Technology & Engineering Solutions of Sandia, LLC
// (NTESS). Under the terms of Contract DE-NA0003525 with NTESS, the U.S.
// Government retains certain rights in this software.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
// =============================================================================
// Maintained by Sandia National Laboratories <Netmeld@sandia.gov>
// =============================================================================

#ifndef GRAPH_HELPER_HPP
#define GRAPH_HELPER_HPP

#include <boost/graph/adjacency_list.hpp>

#include <string>

//==============================================================================
// Graphviz helper objects
//==============================================================================
struct VertexProperties
{
  std::string name;
  std::string label;
  std::string shape;
  std::string style;
  std::string fillcolor;

  double distance = std::numeric_limits<double>::infinity();
  double extra_weight = 0.0;
};

struct EdgeProperties
{
  std::string label;

  double weight = 1.0;
};

using AcGraph =
boost::adjacency_list<
  boost::listS,        // OutEdgeList
  boost::vecS,         // VertexList
  boost::directedS,    // Directed/Undirected
  VertexProperties,    // VertexProperties
  EdgeProperties,      // EdgeProperties
  boost::no_property   // GraphProperties
  >;

using Vertex = AcGraph::vertex_descriptor;
using Edge   = AcGraph::edge_descriptor;

//==============================================================================
// Writer helper objects
//==============================================================================
class LabelWriter
{
  private:
    AcGraph const& graph;

  public:
    explicit LabelWriter(AcGraph&);

    void operator()(std::ostream&, Vertex const&) const;
    void operator()(std::ostream&, Edge const&) const;

};

class GraphWriter
{
  public:
    void operator()(std::ostream&) const;
};
#endif // GRAPH_HELPER_HPP

max_stars_repo_name: cmwill/netmeld

max_issues_repo_name: cmwill/netmeld

max_forks_repo_name: cmwill/netmeld