github.io

htmlを生成するテンプレートエンジンJade Jade - Template Engine と,cssを生成するStylus Expressive, dynamic, robust CSS — expressive, robust, feature-rich CSS preprocessor の使い方について少し勉強したので,かねてより手を付けたいと思っていたgithub.ioにとりあえずindexページを置いた.置いてみて思ったけれど,こことの使い分けのビジョンがイマイチ沸かないし不要そうだ.

http://fimbul.github.io/

Jadeはpythonライクなindentでタグのスコープが決まり,閉じタグを書く必要が無いとか,- var title = "page title"などと変数に値を入れておいて,#{title}で後から参照出来るとか便利なところは結構ある. templateなのでもっと色々使いまわしたり,includeでそのままファイルを埋め込むとか出来るようだけれど読んだだけでそこまで試してない.

Stylusは,sassやlessに似たものだけれど新しいもの好きなので試してみた.変数や条件分岐,ループなど一通り揃っている.

簡単にnpmで全部入るしgulp, gulp-stylus, gulp-jadeも入れて全部gulpを叩けばページが生成されるようにしてみたらよさ気だった.

fimbul.github.io/index.jade at master · fimbul/fimbul.github.io · GitHub

しかし,jadeにコードを埋め込もうと思うと普通にpreタグの中に#include と書くと#がJadeのdirectiveに認識されたりするし, かといって | を使うと</iostream>のような望まぬ閉じタグが生成されたりして結構困った.=を使うとエスケープしてくれるんだけど,今度は= "#include "とダブルクォートで囲ってやる必要があり コードが複数行になるとヒアドキュメントが無いためにいちいち各行を囲い,更に末尾に\nを追加し,途中にダブルクォートがあればバックスラッシュでエスケープしてやらないと上手くいかない.

とりあえずはコードをそのように変換してくれるスクリプトで対処すれば良いけれど,どうすれば幸せになれるんだろう.理解が足りない.

巷で流行りの活動日記

木構造系のデータ構造の実装のベストプラクティスが知りたいと思いつつ,適当に非常に簡単なものを試作するなど.
競プロ用途などで,自分用に簡単なprint機能などを備えた木構造のライブラリなどを作っておきたいという気持ちはある.
TSから標準に入るoptionalを使えば不正値を表現出来るので親が居ないだとか,子が居ないという状態を持つのは楽になる筈.

とりあえず二分木にしたけれど,葉の数nを渡せるような形にしてi番目の子にインデックスアクセス出来る方が良いのかも.

http://melpon.org/wandbox/permlink/FDIoIYYovywpE6ym

#include <functional>
#include <iostream>
#include <memory>
#include <queue>

namespace tree {

struct pre_order_tag {};
static constexpr pre_order_tag pre_order{};

struct in_order_tag {};
static constexpr in_order_tag in_order{};

struct post_order_tag {};
static constexpr post_order_tag post_order{};

struct dfs_order_tag {};
static constexpr dfs_order_tag dfs_order{};

template <typename T>
struct binary_tree : std::enable_shared_from_this<binary_tree<T>> {
  binary_tree(T v,
              std::weak_ptr<binary_tree> p = {},
              std::shared_ptr<binary_tree> l = nullptr,
              std::shared_ptr<binary_tree> r = nullptr)
    : value(v), parent(p), left(l), right(r) {}
  binary_tree(const binary_tree&) = default;
  binary_tree(binary_tree&&) = default;

  std::shared_ptr<binary_tree> append_left(std::shared_ptr<binary_tree> c) {
    left = c;
    c->parent = this->shared_from_this();
    return this->shared_from_this();
  }

  std::shared_ptr<binary_tree> append_right(std::shared_ptr<binary_tree> c) {
    right = c;
    c->parent = this->shared_from_this();
    return this->shared_from_this();
  }

  std::shared_ptr<binary_tree> remove_left() {
    left = nullptr;
    return this->shared_from_this();
  }

  std::shared_ptr<binary_tree> remove_right() {
    right = nullptr;
    return this->shared_from_this();
  }

  T value;
  std::weak_ptr<binary_tree> parent;
  std::shared_ptr<binary_tree> left;
  std::shared_ptr<binary_tree> right;
};

namespace detail {

  template <typename Tag>
  struct print;

  template <>
  struct print<pre_order_tag> {
    template <typename T, typename P>
    static void eval(const T& t, const P& printer) {
       if (t == nullptr) return;
       printer(t);
       eval(t->left, printer);
       eval(t->right, printer);
    }
  };

  template <>
  struct print<in_order_tag> {
    template <typename T, typename P>
    static void eval(const T& t, const P& printer) {
       if (t == nullptr) return;
       eval(t->left, printer);
       printer(t);
       eval(t->right, printer);
    }
  };

  template <>
  struct print<post_order_tag> {
    template <typename T, typename P>
    static void eval(const T& t, const P& printer) {
       if (t == nullptr) return;
       eval(t->left, printer);
       eval(t->right, printer);
       printer(t);
    }
  };

  template <>
  struct print<dfs_order_tag> {
    template <typename T, typename P>
    static void eval(const T& t, const P& printer) {
      if (t == nullptr) return;
      std::queue<T> q;
      q.push(t);
      while (!q.empty()) {
        const auto& tmp = q.front();
        q.pop();
        printer(tmp);
        if (tmp->left != nullptr) q.push(tmp->left);
        if (tmp->right != nullptr) q.push(tmp->right);
      }
    }
  };

}  // namespace detail

struct default_printer_t {
  template <typename T>
  void operator()(const T& t) const { std::cout << t->value << std::endl; }
};

static constexpr default_printer_t default_printer{};

template <typename T, typename Tag = pre_order_tag>
inline void print(const T& t,
           Tag = {}, const std::function<void(const T&)>& printer = default_printer) {
  if (t != nullptr) detail::print<Tag>::eval(t, printer);
}

}  // namespace tree

int main() {
  using tree_type = tree::binary_tree<int>;

  auto t = std::make_shared<tree_type>(0);
  t->append_left(std::make_shared<tree_type>(1));
  t->append_right(std::make_shared<tree_type>(2));
  t->left->append_left(std::make_shared<tree_type>(3));
  t->left->append_right(std::make_shared<tree_type>(4));
  t->right->append_left(std::make_shared<tree_type>(5));
  t->right->append_right(std::make_shared<tree_type>(6));

  std::cout << "pre_order:" << std::endl;
  tree::print(t);
 
  std::cout << "in_order:" << std::endl;
  tree::print(t, tree::in_order);
  
  std::cout << "post_order:" << std::endl;
  tree::print(t, tree::post_order);

  std::cout << "dfs_order:" << std::endl;
  tree::print(t, tree::dfs_order);
}

Tower of Hanoi

#include <iostream>
#include <stack>

int main() {
  int n;
  std::cin >> n;
  std::stack<int> s[3];
  for (int i = n; i > 0; --i) {
    s[0].push(i);
  }

  int mpos = 0;
  while (!s[0].empty() || !s[1].empty()) {
    s[(mpos + 1 + (n % 2)) % 3].push(s[mpos].top());
    s[mpos].pop();
    mpos = (mpos + 1 + (n % 2)) % 3;

    if (s[0].empty() && s[1].empty())
      break;

    if (s[(mpos + 1) % 3].empty()) {
      s[(mpos + 1) % 3].push(s[(mpos + 2) % 3].top());
      s[(mpos + 2) % 3].pop();
    } else if (s[(mpos + 2) % 3].empty()) {
      s[(mpos + 2) % 3].push(s[(mpos + 1) % 3].top());
      s[(mpos + 1) % 3].pop();
    } else if (s[(mpos + 1) % 3].top() < s[(mpos + 2) % 3].top()) {
      s[(mpos + 2) % 3].push(s[(mpos + 1) % 3].top());
      s[(mpos + 1) % 3].pop();
    } else {
      s[(mpos + 1) % 3].push(s[(mpos + 2) % 3].top());
      s[(mpos + 2) % 3].pop();
    }
  }

  std::cout << "----" << std::endl;

  for (int i = 0; i < 3; ++i) {
    while (!s[i].empty()) {
      std::cout << s[i].top() << ' ';
      s[i].pop();
    }
    std::cout << std::endl;
  }
}

lambda is tuple

理解したのでメモ

melpon.org

#include <iostream>

auto stack = [](auto... xs) { 
    return [=](auto access) { 
        return access(xs...);
    }; 
}; 

auto size = [](auto xs) { 
    return xs([=](auto... z) {
        return sizeof...(z);
    }); 
};

auto push = [](auto xs, auto x) {
    return xs([=](auto... z) {
        return [=](auto access) {
            return access(x, z...);
        };
    });
};

auto pop = [](auto xs) {
    return xs([=](auto, auto... z) {
        return [=](auto access) {
            return access(z...);
        };
    });
};

auto top = [](auto xs) {
    return xs([=](auto v, auto...) {
        return v;
    });
};

int main() {
    auto s = push(push(push(stack(), 1), "lambda is tuple"), 3.14);
    std::cout << size(s) << std::endl;
    std::cout << top(s) << ", "
              << top(pop(s)) << ", " 
              << top(pop(pop(s)))
              << std::endl;
}

c++ - Is there a name for this tuple-creation idiom? - Stack Overflow

型リストからindex_sequenceを作る

組込のfolding-exprを再帰深度O(1)とみなすと全体でも再帰深度O(1)

melpon.org

#include <type_traits>
#include <utility>

template<typename... Types>
struct make_indices_from_types {
  private:
    template <std::size_t N, std::size_t...>
    struct make_indices {
        template <std::size_t M, std::size_t... Indices>
        make_indices<N + M, M, Indices...> operator +(const make_indices<M, Indices...>&);
    };
    template <typename> static constexpr int step = 1;
    template <std::size_t... Indices>
    static std::index_sequence<sizeof...(Types) - Indices...> impl(const make_indices<Indices...>&);

  public:
    using type = decltype(impl((make_indices<step<Types>>{} + ...)));
};

int main() {
    static_assert(std::is_same<
                    typename make_indices_from_types<int, char, double, float, void*, bool>::type,
                    std::index_sequence<0, 1, 2, 3, 4, 5>
                  >::value);
}

printfに型チェックを付ける

どうもコンパイラ拡張で文字列を型パラメータとして取れるユーザ定義リテラルがあるようなので,printfに型チェックを付けるようなのを書いてみた. 桁数表示とか何も実装してないけれど,雰囲気がそれっぽくなってきたあたりで飽きた.もっと賢い実装方法があるように思う.あと地味にrequiresなんてconceptカッコつけて使ってみたり.

melpon.org

#include <iostream>
#include <tuple>
#include <type_traits>
#include <utility>

namespace detail {

template <char C>
struct format {};

template <> struct format<'d'> { using type = int; };
template <> struct format<'c'> { using type = char; };
template <> struct format<'s'> { using type = const char*; };
template <> struct format<'f'> { using type = float; };
    
template <typename Str, typename F, typename B, char... Chars>
struct formatter {
    using type = std::tuple<Str, F>;
};

template <typename Str, typename... Fs, bool B, bool... Bs, char C, char... Chars>
requires B
struct formatter<Str, std::tuple<Fs...>, std::integer_sequence<bool, B, Bs...>, C, Chars...> {
    using type = typename formatter<
        Str,
        std::tuple<Fs..., typename format<C>::type>,
        std::integer_sequence<bool, Bs...>,
        Chars...>::type;
};
    
template <typename Str, typename... Fs, bool B, bool... Bs, char C, char... Chars>
requires not B
struct formatter<Str, std::tuple<Fs...>, std::integer_sequence<bool, B, Bs...>, C, Chars...> {
    using type = typename formatter<
        Str, std::tuple<Fs...>,
        std::integer_sequence<bool, Bs...>,
        Chars...>::type;
};

template <typename... Types>
struct and_ {
    static constexpr bool value = false;
};

template <typename... Types>
struct and_<Types*...> {
    static constexpr bool value = true;
};
    
}

template <bool... Bs>
struct and_ {
    static constexpr bool value = detail::and_<
        typename std::conditional<Bs, int*, int>::type...>::value;
};

template <char... Chars>
struct formatter : detail::formatter<
    std::integer_sequence<char, Chars...>,
    std::tuple<>,
    std::integer_sequence<bool, false, (Chars == '%')...>,
    Chars...,
    '\0'> {};

template <typename Char, Char... Chars>
constexpr auto operator ""_fmt() {
    return typename formatter<Chars...>::type{};
}

template <char... Chars, typename... Types, typename... UTypes>
void print(const std::tuple<std::integer_sequence<char, Chars...>,
           std::tuple<Types...>>&, UTypes&&... args) {
    static_assert(and_<std::is_convertible<std::decay_t<Types>, std::decay_t<UTypes&&>>::value...>::value);
    const char str[sizeof...(Chars)] = { Chars... };
    std::printf(str, std::forward<UTypes>(args)...);
}

int main() {
    print("%d %d %f %s\n"_fmt, 10, 20, 3.14f, "hoge");
}