3.28.2013

C++: Testing If This Sequence Contains That Sequence

C++: シーケンスが別のシーケンスを含んでいるかテストする

<algorithm> std::search の簡単なラッパー。
主な用途は string と vector。

#include <iostream>
#include <vector>
#include <algorithm>

template <typename T>
bool contains(T const& a, T const& b){return std::search(a.begin(),a.end(),b.begin(),b.end())!=a.end();}

using namespace std;

int main(int argc, char **argv) {
  cout << contains(string("abcdefg"), string("efg")) << endl;  // true
  cout << contains(string("abcdefg"), string("efh")) << endl;  // false
  cout << contains(string("abcdefg"), string("")) << endl;  // true
  cout << contains(string(""), string("efg")) << endl;  // false
  cout << contains(string("efg"), string("efg")) << endl;  // true
  cout << contains(string(""), string("")) << endl;  // false

  int x[] = { 1, 2, 3, 4, 5 };
  int y[] = { 1, 2 };
  int z[] = { 1, 2, 5 };
  vector<vector<int> > seq;
  seq.push_back(vector<int>(x, x + sizeof(x) / sizeof(x[0])));
  seq.push_back(vector<int>(y, y + sizeof(y) / sizeof(y[0])));
  seq.push_back(vector<int>(z, z + sizeof(z) / sizeof(z[0])));

  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      cout << contains(seq[i], seq[j]) << " ";
    }
    cout << endl;
  }
  // true  true false
  // false true false
  // false true true
}

3.19.2013

Code Style and Coverage Check in Python

Python: コードスタイルとカバレッジをチェックする

pep8

コードが PEP8 のスタイルに適合しているかチェックするツール。

インストール

適切な権限を持ったユーザで以下のコマンドを実行

$ easy_install pep8
実行
$ pep8 xxx.py
  • 詳細を表示する場合
$ pep8 -v xxx.py
  • 出力例
$ pep8 -v xxx.py
checking xxx.py
xxx.py:1:1: W293 blank line contains whitespace
xxx.py:2:80: E111 indentation is not a multiple of four
xxx.py:2:80: E113 unexpected indentation
xxx.py:2:80: E501 line too long (80 > 79 characters)
xxx.py:2:81: W291 trailing whitespace

 

coverage.py

コードカバレッジを出力するツール。
グラフィカルなHTMLの出力機能も持つ。

 

インストール

適切な権限を持ったユーザで以下のコマンドを実行

$ easy_install coverage
実行
$ coverage run xxx.py
$ coverage report
  • カバーされていない行番号を表示
$ coverage report -m
  • HTML形式で出力
$ coverage html

HTMLの出力先は htmlcov ディレクトリ配下。
出力例は以下参照。
http://nedbatchelder.com/code/coverage/sample_html/


 

References

3.17.2013

Scala Conference in Japan 2013 - My First Ever Conference as a Staff

Scala Conference in Japan 2013 - スタッフの一人としてカンファレンスを振り返る

去る2013年3月2日〜3日、東京工業大学 大岡山キャンパスにおいてプログラミング言語 Scala に関する
国内初の大規模カンファレンス Scala Conference in Japan 2013 (以下、ScalaConfJP) が開催されました。

実に300人近くの技術者が一堂に会し、計20本以上の講演はもちろん海外ゲストとの交流やハッカソンと
Scala 一色の時間を分かち合い、大いに盛り上がりました。

私は、このイベントにスタッフとして参加しました。

右も左もわからない状態でしたし、他力本願な場面も多々あったので「どれだけ貢献できたか」と聞かれると
自信がありませんが、今ではスタッフになってよかったと心底思います。

ご来場の皆様(遠方や海外からも多くの方にお越しいただいたようです)、登壇者の皆様、スポンサーの皆様、
スタッフの皆様、会場をお貸しいただいた東工大関係者の皆様、本当にありがとうございました。
そしてチケットの完売によってご来場できなかった皆様、 申し訳ございませんでした。次回のお越しをお待ちしています。 

以下、簡単ではありますが私の目線から今回のカンファレンスを振り返ってみます。
と、その前に英語でもお礼を書かせてください。

 

For non-Japanese visitors / speakers / guests

Thank you very much for coming to Scala Conference in Japan 2013!

I had an amazing time with you.
I saw your devotion to Scala and I believe that it will make the world better.

I look forward to seeing you again.
By the next conference, I will learn more about Scala and English (or another language). 

Thanks!

 

はじめに

 

私のスペック
  • 仕事: 業務系の レガシィ なインフラエンジニア (SIer)
  • アプリ開発経験: なし
  • イベント運営経験: なし
  • Scala: 初心者
  • もう決して若くはない

最初はさすがに場違い感を覚えました。が、皆さんのおかげで徐々に打ち解けることができたと思います。

 

スタッフになったきっかけ

たしか、私が初めて Scala という言語を知ったのは WebLogic Server勉強会 でした。
JDK 8 で導入される関数型言語のエッセンスを学ぶのに Scala がちょうど良いという話に刺激を受けた気がします。

それから 日本Scalaユーザーズグループ(ScalaJP) のメーリングリストに登録して
最初に飛び込んできたトピックが、2012年7月21日に行われた Scala Conference in Japan(仮) キックオフ の案内でした。 

行ってみると、見知った顔はありませんでしたが意外となごやか(註: こわくない)な雰囲気で安心しました。
当時折しも準備の真っ只中だった PyCon JP 2012 (Python Conference Japan 2012) のノウハウを 丸パクリ 参考に
しながら座長(@kmizu)・副座長(@gakuzzzz)・チーム構成を決定。

チームリーダーが決まった後、一人ずつ担当するチームを決めていくことになったので私は @seratch さんと同じ
プログラムチームを選びました。

後に  @seratch さんが Webサイトも会場チームも統括し獅子奮迅の活躍をされるとは、この時知る由もありませんでした。

 

私が行ったこと

 

カンファレンス前々日まで
  • 定例ミーティングへの参加
    2012年7月から、月1回程度の間隔で開催されました。
    これが一つのチェックポイントとなるので、プロジェクトの遂行にはやはりオフライン・ミーティングも必要だと感じました。
  • PyCon JP の情報収集
    BPStudy#61 の「第2部 PyCon JP2012の裏側全部見せます。ポロリもあるよ」の情報は非常に有用でした。
    「まず一回やってみるのが大事」だとか「燃え尽き症候群 (burn out)に注意」というお話は身に染みました。 
  • Call for Speakers の対応
    通常セッションおよびLT大会の募集・選考の期間や文面の検討、メールのやり取りを行いました。
    とはいえ、ほぼ @seratch さんに任せきりでした。
  • 登壇者とのメール連絡など
    当日の段取りや発表スライドに関する連絡を行いました。
    海外の方との英文メールのやり取りはほぼ初めてだったのですがいい勉強になりました。
  • LT大会の段取り検討
  • プログラムのPDF版を作成、Webサイトへ掲載
  • ノベルティなどの物品受け取り
    紙袋、スタッフパーカー、スポンサーからの提供物などを私の自宅で受け取りました。
    私が不在がちだったり、宅配業者が部屋番号を間違えるトラブルに見舞われたりして
    かなりギリギリの対応となってしまいました。(結局全部揃ったのはカンファレンス前日の朝でした)
    もっと余裕を持って案内を出せばよかったです。
  • ひっそりと Twitter bot を作ったり
    @scalaconfjp_cd 

 

カンファレンス前日 (3月1日)
  • 物品の運搬
    車で荷物を運んだり、ドラを受け取ったりしました。
    Photo 2013 02 28 20 26 06
  • 受付用の机などを準備
  • リクルーティングセッションの段取り確認
  • 来場者用の紙袋づくり
  • 各会場の下見
    Photo 2013 03 01 15 10 52
  • LT大会用ドラの準備
    Dora (Photo by @kmizu)

 

カンファレンス当日 (3月2日)

私は 会場B の担当でしたので、残念ながら会場A の講演は見られませんでした。
ビデオができあがったらチェックするつもりです。 

  • 会場B の機材セッティング
  • シュティフさん、土佐さんのセッションを拝見
    直前まで誰もお客さんが来ないのでかなり焦りました。
    大岡山駅前の交差点でエンジニアがわらわらと大挙移動する様は感動的ですらありました。
  • 会場B で昼食を配ったり食べたり
  • LT大会の前半部分を拝見
    念願のドラの音が聞けてよかったです。ただやはり、全部を見られなかったのは残念。
  • リクルーティングセッションの司会
    緊張しました。
    どうなることかと思いましたが、途中から徐々に人が増えたようです。
    来年に向けて改善したい部分です。
  • 中村さん、後藤さん、高橋さん、粕谷さんのセッションを拝見
    会場A での望月さんのマシンの電源が切れたという連絡を受けても何もできず、てんやわんやでした。 
  • 池田さん、Y.L.Lan さんのセッションの司会
  • 撤収作業
  • 懇親会への参加
    車だったのでお酒は飲めませんでしたが、楽しい時間を過ごすことができました。
    Scala Ninja こと @yllan さんとも少しお話できました。 
本当に、あっという間の一日でした。

 

ハッカソン当日 (3月3日)

ハッカソンは、スタッフというよりは個人として参加した形です。
ハイレベルな発表には全く付いていけませんでしたが、お祭り感覚を味わうことはできました。

もう少し準備しておけばよかったとしきりに反省。

スポンサーである ENRAPTさんのチャレンジ問題が頭の体操にちょうど良かったです。

 

ScalaConfJP を支えた三種の神器

いつの時代も、道具の性能は仕事の効率を大きく決定づけます。
ScalaConfJP では、以下の『三種の神器』を使うことで、非常にスマートな仕事ができたと感じました。 

GitHub

GitHub 時代の言語 Scala と言われるだけあって、スタッフは慣れている方が多いようでした。
私は全く触ったことがなかったので 、逆によい勉強の機会となりました。 (初めての pull req も経験しました) 

Wiki を利用して進捗状況の共有をしたり、Webサイトのコンテンツ管理を行いました。

 

co-meeting

「突然の co-meeting ブーム!」から世界が一変したといっても言い過ぎではないでしょう。

メーリングリスト中心のやり取りとは比較にならないくらい議論が活発になり、決定がスピーディーになりました。 

発言の流れや「人の顔」が見えることによる臨場感は凄まじいです。
ツールが変わっても特定のスタッフに負荷が集中するという状況は変わりませんが、
「今忙しいので誰か巻き取って」 ->  「自分がやります」というやり取りが至る所で見られました。

何よりメールと違って楽しいし、気負わずに誰でも発言できる、そんな雰囲気を co-meeting が醸成してくれたのではないかと思います。 

問題はあるかもしれませんが、スタッフだけでなく、登壇者などとのやり取りも co-meeting 上で行う余地があったかもしれません。

ただし、

  • TODO管理には向かない
    共有ノートでやディスカッションで TODO を管理しましたが、運用で工夫しないといけないです。
  • 個人宛のメッセージは見逃される可能性があるのでフォローが必要
  • 実際の会議以上に時間を決めて臨まないと、延々と仕事をし続けることになりがち
  • しばらく時間を空けると未読数が膨大になって見る気が失せる
  • 同時利用ユーザ数が増えると性能が悪化する
という点は注意が必要と思いました。

co-meeting だけではカバーできない、スプレッドシートの作成や差分の確認などは、それぞれ Google Docs や GitHub で補完しました。

 

Doorkeeper

これもまた画期的なサービスだと思います。

有料イベントで悩みの種だった決済/キャンセル処理をお任せするだけではなく、当日の受付業務まで
完璧にこなしていただき、大変助かりました。

一般参加者と招待者の区別にも対応していただけましたし、メールの一斉送信機能も便利でした。

DoorKeeper のおかげで、スタッフはそれぞれの本来の「仕事」に集中することができました。

 

次回に向けて

非常に多くのフィードバックを参加者・登壇者の皆様からいただくことができました。
皆様のご意見や今回培ったノウハウを今後に活かし、さらなる発展をしていきたいです。

限られた予算と人的リソースの中、『まず一回やってみる』という目的は達成できました。
真価が問われるのは次回です。

  • 会場設備の拡充
    空調、電源供給に関するご意見が多く寄せられました。
    また会場の移動でご不便を強いてしまったことも反省材料の一つです。
  • 講演内容と参加者属性のマッチング最適化
    見たい講演が重なってしまう or 見たい講演がない、といったケースをどれだけ減らせるか。 
  • Up, Up and Out
    より多くの参加者へ、より多彩な講演を。
    予算が増えれば会場やデザインへさらなる投資が可能となり、より洗練されたイベントになるでしょう。
    同時にスタッフ業務は可能な範囲で自動化・効率化し、よりスケーラブルな仕組みを考える必要があると思います。
  • コミュニティの垣根を越えて
    カンファレンス開催のノウハウは、他の言語やコミュニティでも有益なものとなるはず。
    カンファレンス勉強会(勉強会の勉強会)をしたり、カンファレンス開催のフレームワークができたり
    すると面白くなるのではないかとふと思いました。 

 

スタッフになって得られたもの

  • この上ない達成感
    準備期間では普段の仕事と折り合いをつけたり、忙しい時もありましたが
    カンファレンスをやり遂げた時の達成感、スタッフ仲間との一体感は格別のものがありました。
    仕事の喜びとはまた別の感覚があったと思います。 
  • 明確な目標とモチベーション
    これまで雲の上の存在だった人たちと会うことができ、その雲の切れ目から頂上の高さを
    窺い知ることができました。
    また、まだ知らない世界が広がっていることと、何かを発信すればすぐに世界各地から反応が
    返ってくるということで、世界の広さと狭さを同時に体感することもできました。
    Scala の世界にエレベーターは無いので、これから螺旋階段を一段ずつ自分の足で上っていきたいと思います。
  • 仲間の存在
    カンファレンスを通して、多くの方と知り合うことができました。
    私はあまりコミュニケーションが得意なほうではありませんが、今後も勉強会などを通して
    さらに親交を深めていけたら幸いです。 
  • Joshua Suereth 氏のサイン
    プログラミングコンテストと関係のない所で、実はこっそりと頂いちゃいました。
    この Scala in Depth を片手に、今後勉強に励みたい思います。
    Photo 2013 03 03 11 15 29
  • 転職の機会
    ご縁がありまして、4月より新天地で働くこととなりました。
    Scala エンジニアとしての第一歩を踏み出す予定です。

 

さいごに

長文をお読みくださりどうもありがとうございました。 

大熱狂の中、幕を閉じた ScalaConfJP ですが、まだいくつかの作業が残っています。
直近のタスクは、今私の自宅にある、余ったパーカーを 売りさばく プレゼントすることです。
ブログを書いてくださった皆様、今しばらくお待ちくださいませ。
Photo 2013 03 17 18 41 31

最後に、来場者・関係者の皆様に改めてお礼を申し上げたいと思います。
素晴らしく貴重な時間を、どうもありがとうございました。

また、どこかでお会いしましょう! 

 

References

 

 

Enhancing GitHub Pages with Jekyll

Jekyll で GitHub Pages を拡張する

GitHub Pages には、Jekyll (ジキル) によるHTMLのレンダリング機能が標準で備わっている。
これを利用すれば、GitHub Pages のコンテンツを Markdown で管理することができるようになる。

 

Jekyllとは

静的サイトのジェネレータ。Rubyで実装されている。

Markdown はもちろんのこと、Syntax Highlighting などの機能も持っており、
シンプルな形式のテキストからモダンなHTMLを生成することが容易となる。

 

事前準備

 

Jekyll のインストール

GitHub Pages 上で Jekyll を利用するだけであれば必須ではないが、
動作確認用にまずはローカルに Jekyll をインストールする。 

ruby、gem をインストールの上、"gem install jekyll" を行えばよい。

Install · mojombo/jekyll Wiki

 

Jekyll の概要を知る

こちらの記事が分かりやすかった。

30分のチュートリアルでJekyllを理解する 

 

ローカルでの動作確認

まずは既存のHTMLで Jekyll の動作を確認。ローカルリポジトリのルートで以下のコマンドを実行する。

$ jekyll --server

 その後、ブラウザで http://localhost:4000/ へアクセスし、Webページが表示されればOK。

 

対応手順

 

.gitignore の作成

Jekyllの設定を行う前に、Jekyll の出力ディレクトリを Git 対象外にするため
以下のような .gitignore ファイルを作成する。

.DS_Store
Thumbs.db
*~
_site

 

レイアウトファイルの作成

index.html をもとに default という名前のレイアウト(テンプレート)を作る。
_layouts ディレクトリを新規作成し、その配下に default.html を作ればよい。

$ mkdir _layouts
$ cp -pi ./index.html ./_layouts/default.html

default.html は以下のように編集する。

  • コンテンツ格納領域を {{ content }} に置き換える
        <!-- MAIN CONTENT -->
        <div id="main_content_wrap" class="outer">
          <section id="main_content" class="inner">
            {{ content }}
          </section>
        </div>
  • タイトルを {{ page.title }} などの変数に書き換えてもよい

 

Markdown ファイルの作成

index.html のコンテンツの内容を index.md として Markdown で記述する。

先頭の 3行は、レイアウトを指定してレンダリングを行うために必須の設定。

---
layout: default
---

example
=======

Repository for example

* This is a README file written using Markdown syntax.
* This line is appended.
* Enhanced with Jekyll.

 

ローカルでの動作確認

ローカルリポジトリのルートで以下のコマンドを実行する。

$ jekyll --server --auto

ブラウザで確認し、問題があればファイルを修正する。
--auto オプションを付けると、ファイルを更新してもデーモン再起動不要ですぐに反映が行われる。

 

GitHub へのアップロード

これは通常の Git の手順と同じ。gh-pages ブランチの内容を origin へ push する。

git add .
git rm index.html
git commit -m “Enhanced with Jekyll”
git push

 

作ったもの 

  • example リポジトリ: gh-pages ブランチ
    mogproject/example at gh-pages · GitHub
  • GitHub Pages の URL
    http://mogproject.github.com/example/
  • ファイル構成
    % tree -a -I .git
    .
    ├── .gitignore
    ├── _layouts
    │   └── default.html
    ├── _site
    │   ├── images
    │   │   ├── bg_hr.png
    │   │   ├── blacktocat.png
    │   │   ├── icon_download.png
    │   │   └── sprite_download.png
    │   ├── index.html
    │   ├── javascripts
    │   │   └── main.js
    │   ├── params.json
    │   └── stylesheets
    │       ├── pygment_trac.css
    │       └── stylesheet.css
    ├── images
    │   ├── bg_hr.png
    │   ├── blacktocat.png
    │   ├── icon_download.png
    │   └── sprite_download.png
    ├── index.md
    ├── javascripts
    │   └── main.js
    ├── params.json
    └── stylesheets
        ├── pygment_trac.css
        └── stylesheet.css
    
  • 画面 
    Example 2
    今回は、レイアウトファイル _layouts/default.html にソーシャルボタン (twitter/facebook) も追加してみた。

とりあえず、これで Markdown を GitHub Pages に装備されている Jekyll でレンダリングするという
最低限の目標は達成できた。

あとは _config.yml を作ってグローバルな定義を行ったり
Jekyll Bootstrap や Twitter Bootstrap なりを取り入れていけば、さらに良くなっていくはず。

 

Related Posts

 

References

3.16.2013

Setting Up GitHub Pages

GitHub Pages の開設

リポジトリの GitHub Pages 化を試してみた記録。

 

GitHub Pages とは

GitHub が無償で提供している Webサイトのホスティングサービス。
簡単な手順で、リポジトリを華麗に Webサイトへ変身させることができる。

 

セットアップ前の状態

適当に作った example リポジトリでセットアップを行う。

  • ブランチ構成: master のみ
  • ファイル構成: 
    $ tree -a -I .git
    .
    ├── .gitignore
    ├── README.md
    └── example.py
    

 

セットアップ手順 

 

Options 2

リポジトリの Settings -> Options
-> GitHub Pages -> Automatic Page Generator ボタンをクリック

Create Page  mogproject example

トップページ(index.html)へ適用されるパラメータを定義する。

Load README.md ボタンをクリックすると、Body が README.md の内容に置き換わる

Create Page  mogproject example 2 必要に応じて編集した後、
Continue to Layouts ボタンをクリック
GitHub  Build software better together 2 10種類程度あるテンプレートから適当なものを選択し、PUBLISH ボタンをクリック
 Mogproject example  GitHub

リポジトリの画面に戻る。

表示されているように、GitHub Pages の URL が有効になるには 10分程度の時間を要する。

Mogproject example at gh pages  GitHub リポジトリ内に gh-pages という新しいブランチが作成された。
Example

以下の URL で GitHub Pages へアクセスできる。
実に簡単である。

http://ユーザID.github.com/リポジトリ名

 

セットアップ後の状態

ローカルリポジトリで以下のコマンドを実行すれば、新しいブランチの追跡が可能となる。

$ git fetch
$ git checkout gh-pages

 

  • ブランチ構成: master, gh-pages
  • gh-pages ブランチのファイル構成 (Slate テンプレートの例): 
    $ tree -a -I .git
    .
    ├── images
    │   ├── bg_hr.png
    │   ├── blacktocat.png
    │   ├── icon_download.png
    │   └── sprite_download.png
    ├── index.html
    ├── javascripts
    │   └── main.js
    ├── params.json
    └── stylesheets
        ├── pygment_trac.css
        └── stylesheet.css
    

gh-pages ブランチでファイルの編集を行い、commit, push を行えば即座に Webサイトのコンテンツも更新される。

Git のリポジトリと Webサイトの内容が完全に同期されるという点が非常に便利である。

 Example 2

 

その他のトピック
  • ユーザID と同名のリポジトリを作成し GitHub ページ化すれば
    ドメインルートの Webサイトを構築できるらしい
    (ただし既存のリポジトリ名と同名のディレクトリを作るとよろしくない様子)
  •  Jekyll レンダリングを活用することで、Markdown で簡単にリッチなサイトを作れるらしい
    (別エントリで紹介予定)

 

Related Posts

  

References

How to Turn Off Auto Indent When Pasting in Vim

Vim: ペースト時のオートインデントを無効にする方法 

Vimでコードなどをペーストした時、オートインデント機能の副作用でこのような残念な感じに
なってしまうことがある。

{
  "foo": "FOO",
    "bar": "BAR",
      "foo": "FOO",
        "bar": "BAR",
          "foo": "FOO",
            "bar": "BAR"
            }

 

これを回避するには、

  • :set paste
  • :set noautoindent, :set nosmartindent (:se noai, :se nosi)
  • :a! -> ペースト -> エスケープ

などの方法があるが、いずれもペースト前に一手間かかるのが面倒。

 

.vimrc に以下のようなコードを書けば、ペーストか手入力かを判定し
ペースト時にのみオートインデントを無効にしてくれる。 

if &term =~ "xterm"
    let &t_ti .= "\e[?2004h"
    let &t_te .= "\e[?2004l"
    let &pastetoggle = "\e[201~"

    function XTermPasteBegin(ret)
        set paste
        return a:ret
    endfunction

    noremap   [200~ XTermPasteBegin("0i")
    inoremap   [200~ XTermPasteBegin("")
    cnoremap  [200~
    cnoremap  [201~
endif

詳細は以下を参照。

 

References

クリップボードからの貼り付け時に自動インデントを無効にする
http://ttssh2.sourceforge.jp/manual/ja/usage/tips/vim.html#Bracketed

3.10.2013

Histogram in C++

C++: ヒストグラムの作成

first と last という 2つのイテレータからその範囲内の連続する値をカウントし
その個数と値の pair を vector にして返すテンプレート関数 encodeList を作成。
ソート済みのリストに対してこれを適用すれば、ヒストグラムを作成することができる。

コード

using namespace std;

template <typename Iterator>
vector<pair<int , typename Iterator::value_type> > encodeList(Iterator first, Iterator last) {
  vector<pair<int , typename Iterator::value_type> > ret;
  for (Iterator i = first; i != last;) {
    Iterator j = i;
    while (j != last && *i == *j) ++j;
    ret.push_back(make_pair(j - i, *i));
    i = j;
  }
  return ret;
}

実行例

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

template <typename Iterator>
vector<pair<int , typename Iterator::value_type> > encodeList(Iterator first, Iterator last) {
  vector<pair<int , typename Iterator::value_type> > ret;
  for (Iterator i = first; i != last;) {
    Iterator j = i;
    while (j != last && *i == *j) ++j;
    ret.push_back(make_pair(j - i, *i));
    i = j;
  }
  return ret;
}

template <typename T>
std::ostream & operator<<(std::ostream & stream, std::vector<T> & v) {
  stream << "[";
  for(typeof(v.begin()) i = v.begin(); i != v.end(); ++i) {
    if (i != v.begin()) { stream << ", "; }
    stream << *i;
  }
  stream << "]";
  return stream;
}
template <typename T, typename U>
std::ostream & operator<<(std::ostream & stream, std::pair<T, U> & p) {
  stream << "(" << p.first << ", " << p.second << ")";
  return stream;
}
#define all(a) (a).begin(),(a).end()
template <typename T>
void printResult(T v) {
  cout << v << endl;
  vector<pair<int , typename T::iterator::value_type> > result = encodeList(all(v));
  cout << result << endl;
}

int main() {
  vector<int> v1, v2;
  for (int i = 1; i < 4; ++i) for (int j = 0; j < i * 2; ++j) v1.push_back(i);
  printResult(v1);
  // [1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3]
  // [(2, 1), (4, 2), (6, 3)]

  printResult(v2);
  // []
  // []

  string s = "aabbbaac";
  printResult(s);
  // aabbbaac
  // [(2, a), (3, b), (2, a), (1, c)]

  sort(all(s));
  printResult(s);
  // aaaabbbc
  // [(4, a), (3, b), (1, c)]

  return 0;
}