トーナメント作成
はるか昔にバランスのいいトーナメントの書き方というトピックを書いた記憶があるが、それをプログラムに起こしてみた。
方針は、決勝から順番に等分に分けていくというだけです。ただし奇数の場合、どちらを多くするかという自由度があるので、内側に多くなるように振り分ける。
class Branch{ public: Branch(){} virtual ~Branch(){} //深さ virtual int GetDepth() = 0; //エントリー数 virtual int GetEntrySize() = 0; //表示 virtual void PrintOut( std::ostream& out, int iDepth2, int iNumber2, int iSubDepth2 ) = 0; //位置 virtual int GetCenterPosition() = 0; virtual int GetLeftEnd() = 0; virtual int GetRightEnd() = 0; }; class Entry: public Branch { public: Entry( int number ):Branch(),m_iNumber( number ){} virtual ~Entry(){} virtual int GetDepth(){ return 1; } virtual int GetEntrySize(){ return 1; } virtual void PrintOut( std::ostream& out, int iDepth2, int /*iNumber2*/, int /*iSubDepth2*/ ){ if( iDepth2 == 0 ){ if( m_iNumber / 10 == 0 ){ out << ' ' << m_iNumber; }else{ out << m_iNumber; } }else{ out << "│"; } } virtual int GetCenterPosition(){ return m_iNumber * 2; } virtual int GetLeftEnd(){ return m_iNumber * 2; } virtual int GetRightEnd(){ return m_iNumber * 2; } private: int m_iNumber; }; class SubTournament:public Branch { public: SubTournament( bool bLeft, int iSize, int iStart ):Branch() { int iLeftSize = iSize / 2; int iRightSize = iSize - iLeftSize; //反対側を多くする。 if( bLeft == (iLeftSize > iRightSize) ){ std::swap( iLeftSize, iRightSize ); } if( iLeftSize == 1 ){ m_pLeft.reset( new Entry( iStart ) ); }else{ m_pLeft.reset( new SubTournament( true, iLeftSize, iStart ) ); } if( iRightSize == 1 ){ m_pRight.reset( new Entry( iStart + iLeftSize ) ); }else{ m_pRight.reset( new SubTournament( false, iRightSize, iLeftSize + iStart ) ); } } virtual ~SubTournament(){} virtual int GetDepth(){ return (std::max)( m_pLeft->GetDepth(), m_pRight->GetDepth() ) + 1; } virtual int GetEntrySize(){ return m_pLeft->GetEntrySize() + m_pRight->GetEntrySize(); } virtual void PrintOut( std::ostream& out, int iDepth2, int iNumber2, int iSubDepth2 ){ if( 0 == iSubDepth2 ){ //│を表示する if( GetCenterPosition() == iNumber2 ){ out << "|"; }else{ out << " "; } }else if( 1 == iSubDepth2 ){ //蓋を表示する if( iNumber2 < m_pLeft->GetCenterPosition() ){ out << " "; }else if( iNumber2 == m_pLeft->GetCenterPosition() ){ out << "┌"; }else if( iNumber2 < GetCenterPosition() ){ out << "─"; }else if( iNumber2 == GetCenterPosition() ){ out << "┴"; }else if( iNumber2 < m_pRight->GetCenterPosition() ){ out << "─"; }else if( iNumber2 == m_pRight->GetCenterPosition() ){ out << "┐"; }else{ out << " "; } }else{ //下を表示する if( iNumber2 < GetCenterPosition() ){ m_pLeft->PrintOut( out, iDepth2, iNumber2, iSubDepth2 - 2 ); }else if( iNumber2 == GetCenterPosition() ){ out << " "; }else{ m_pRight->PrintOut( out, iDepth2, iNumber2, iSubDepth2 - 2 ); } } } virtual int GetCenterPosition(){ return (m_pLeft->GetRightEnd() + m_pRight->GetLeftEnd()) / 2; } virtual int GetLeftEnd(){ return m_pLeft->GetLeftEnd(); } virtual int GetRightEnd(){ return m_pRight->GetRightEnd(); } private: std::unique_ptr< Branch > m_pLeft, m_pRight; }; class Tournament { public: Tournament(){} virtual ~Tournament(){} //出場者の数を設定 void SetEntrySize( int iEntry ){ m_pTournament.reset( new SubTournament( true, iEntry, 0 ) ); } //プリントアウト void PrintOut( std::ostream& out ){ const int depth2 = m_pTournament->GetDepth() * 2; int subDepth = 0; for( int d = depth2 - 1; d >= 0; --d, ++subDepth ){ for( int n = 0; n < m_pTournament->GetEntrySize() * 2 - 1; ++n ){ m_pTournament->PrintOut( out, d, n, subDepth ); } out << std::endl; } } private: std::unique_ptr< SubTournament > m_pTournament; };
試しのメイン関数の中身はこんな感じ
std::ofstream fout ("tournament.dat"); Tournament tn; tn.SetEntrySize( 75 ); tn.PrintOut( fout );
トーナメントの構造を作るのは割と簡単です。ぶっちゃけ、バイナリツリーを作るだけですから。結局大変だったのが表示部分。途中で疲れてとりあえず動けばいいや的なコードになっております。ていうか、表示部分は分離したいのだが木構造の出力ってどうすればいいんだろう(汗
本当はテンプレートメタプログラミングまで持っていくつもりだったんだが諦めました。や、構造を作るだけだったらそんなに難しくないわけですよ。しかし表示系が・・・。というわけで使う予定もないし今回はここまでorz