// 両端キューの使用例
#include < iostream>
#include < deque>
#include < cstring>
using namespace std;

int main()
{
  deque< char> q1;
  char str[] = "Using a deque.";
  int i;

  for(i=0; str[i]; i++) {
    q1.push_front(str[i]);
    q1.push_back(str[i]);
  }

  cout << "Original q1:\n";
  for(i=0; i< q1.size(); i++)
    cout << q1[i];
  cout << "\n\n";

  // 逆順の文字列を削除する
  for(i=0; i< strlen(str); i++) q1.pop_front();
  cout << "q1 after popping front:\n";
  for(i=0; i< q1.size(); i++)
    cout << q1[i];
  cout << "\n\n";

  deque< char> q2(q1); // q1のコピーを構築する
  cout << "q2 original contents:\n";
  for(i=0; i< q2.size(); i++)
    cout << q2[i];
  cout << "\n\n";

  // q2をずらす
  for(i=0; i< q2.size(); i++)
     q2[i] = q2[i]+1;
  
  cout << "q2 transposed contents:\n";
  for(i=0; i< q2.size(); i++)
    cout << q2[i];
  cout << "\n\n";

  // 最初のaを指す反復子を取得する
  deque< char>::iterator p = q1.begin();
  while(p != q1.end()) {
    if(*p == 'a') break;
    p++;
  }

  // ずらしたq2をq1へ挿入する
  q1.insert(p, q2.begin(), q2.end());

  cout << "q1 after insertion:\n";
  for(i=0; i< q1.size(); i++)
    cout << q1[i];
  cout << "\n\n";

  return 0;
}

// dequeを反転しながらコピーする1つの方法
#include < iostream>
#include < deque>
using namespace std;

int main()
{
  deque< char> q;
  deque< char> rev_q;
  int i;

  for(i=0; i<10; i++) q.push_back('A'+i);

  cout << "Contents of q: ";
  for(i=0; i< q.size(); i++) 
    cout << q[i];
  cout << "\n";

  // qから要素を削除し、rev_qに逆順に格納する
  while(!q.empty()) {
    rev_q.push_front(q.front());
    q.pop_front();
  }

  cout << "Contents of rev_q: ";
  for(i=0; i< rev_q.size(); i++) 
    cout << rev_q[i];
    
  return 0;
}

// 両端キューを回転する
#include < iostream>
#include < deque>
#include < string>
using namespace std;

// 両端キューを左に回転する
template < class T> lrot(deque< T> &q)
{
  q.push_back(q.front());
  q.pop_front();
}

// 両端キューを右に回転する
template < class T> rrot(deque< T> &q)
{
  q.push_front(q.back());
  q.pop_back();
}

int main()
{
  deque< string> w;
  int i, n;

  w.push_back("Rotation");
  w.push_back("is");
  w.push_back("easy");
  w.push_back("using");
  w.push_back("deque.");

  cout << "This is the original sentence:\n";
  for(i=0; i< w.size(); i++)
    cout << w[i] << " ";
  cout << "\n\n";

  cout << "First, left rotate:\n";
  for(n=0; n< w.size(); n++) {
    lrot(w);
    for(i=0; i< w.size(); i++)
      cout << w[i] << " ";
    cout << "\n";
  }

  cout << "\nNow, right rotate:\n";
  for(n=0; n< w.size(); n++) {
    rrot(w);
    for(i=0; i< w.size(); i++)
      cout << w[i] << " ";
    cout << "\n";
  }

  return 0;
}

// 逆方向反復子を使用する
#include < iostream>
#include < deque>
using namespace std;

int main()
{
  deque< int> q;
  deque< int>::reverse_iterator rp;
  int i;

  for(i=0; i<10; i++) q.push_back(i);

  cout << "Contents printed backward:\n";
  rp = q.rbegin();
  while(rp != q.rend()) {
    cout << *rp << " ";
    rp++;
  }
  cout << "\n\n";

  cout << "Contents printed forward:\n";
  rp = q.rend();
  while(rp != q.rbegin()) {
    rp--;
    cout << *rp << " ";
  }

  return 0;
}

// 逆方向反復子とコピー
#include < iostream>
#include < deque>
#include < algorithm>
#include < cstring>
using namespace std;

int main()
{
  deque< char> q1(30), q2, q3;
  int i;

  char str1[] = "forward";
  for(i=0; str1[i]; i++) q2.push_back(str1[i]);

  // 順方向へコピーする
  copy(q2.begin(), q2.end(), q1.begin());

  cout << "Contents q1 after forward copy:\n";
  for(i=0; i< q1.size(); i++)
    cout << q1[i];
  cout << "\n\n";

  char str2[] = "backward";
  for(i=0; str2[i]; i++) q3.push_back(str2[i]);

  // 逆方向へコピーする
  copy(q3.rbegin(), q3.rend(), q1.begin()+strlen(str1));

  cout << "Contents q1 after reverse copy:\n";
  for(i=0; i< q1.size(); i++)
    cout << q1[i];

  return 0;
}

// 両端キューオブジェクトへの代入
#include < iostream>
#include < deque>
using namespace std;

int main()
{
  deque< char> q1(10), q2;
  int i;

  for(i=0; i<10; i++) q1[i] = i + 'A';
  cout << "Contents of q1 are: ";
  for(i=0; i< q1.size(); i++)
    cout << q1[i];
  cout << "\n\n";

  // 両端キューを別の両端キューに代入する
  q2 = q1;

  cout << "Size of q2 is " << q2.size() << "\n";
  cout << "Contents of q2 are: ";
  for(i=0; i< q2.size(); i++)
    cout << q2[i];
  cout << "\n\n";

  // q1の特定の範囲をq2に代入する
  q2.assign(q1.begin()+2, q1.end()-2);

  cout << "Size of q2 is " << q2.size() << "\n";
  cout << "Contents of q2 are: ";
  for(i=0; i< q2.size(); i++)
    cout << q2[i];
  cout << "\n\n";

  // いくつかの要素をq2に代入する
  q2.assign(8, 'X');

  cout << "Size of q2 is " << q2.size() << "\n";
  cout << "Contents of q2 are: ";
  for(i=0; i< q2.size(); i++)
    cout << q2[i];

  return 0;
}

// swap()の使用例
#include < iostream>
#include < deque>
using namespace std;

int main()
{
  deque< char> q1, q2;
  int i;

  for(i=0; i<26; i++) q1.push_back(i+'A');
  for(i=0; i<10; i++) q2.push_front(i+'0');

  cout << "Size of q1 and q2: ";
  cout << q1.size() << " " << q2.size() << "\n";

  cout << "q1: ";
  for(i=0; i< q1.size(); i++)
    cout << q1[i];
  cout << "\n";

  cout << "q2: ";
  for(i=0; i< q2.size(); i++)
    cout << q2[i];
  cout << "\n\n";

  // メンバ関数を使って両端キューを交換する
  q1.swap(q2);

  cout << "Size of q1 and q2 after first swap: ";
  cout << q1.size() << " " << q2.size() << "\n";

  cout << "q1 after first swap: ";
  for(i=0; i< q1.size(); i++)
    cout << q1[i];
  cout << "\n";

  cout << "q2 after first swap: ";
  for(i=0; i< q2.size(); i++)
    cout << q2[i];
  cout << "\n\n";

  // アルゴリズムを使って両端キューを交換する
  swap(q1, q2);

  cout << "Size of q1 and q2 after second swap: ";
  cout << q1.size() << " " << q2.size() << "\n";

  cout << "q1 after second swap: ";
  for(i=0; i< q1.size(); i++)
    cout << q1[i];
  cout << "\n";

  cout << "q2 after second swap: ";
  for(i=0; i< q2.size(); i++)
    cout << q2[i];
  cout << "\n";

  return 0;
}

// resize()の使用例
#include < iostream>
#include < deque>
#include < algorithm>
#include < cmath>
using namespace std;

int main()
{
  deque< double> radians, sines;
  double num;
  int i;

  for(;;) {
    cout << "Enter angles (0 to stop): ";
    cin >> num;
    if(num == 0.0) break;
    radians.push_back(num);
  }

  // すべての結果を格納できるようにsinesのサイズを変更する
  sines.resize(radians.size());

  transform(radians.begin(), radians.end(),
            sines.begin(), sin);

  for(i=0; i< sines.size(); i++) {
    cout << "Angle and sine: ";
    cout << radians[i] << " " << sines[i];
    cout << "\n";
  }
  cout << "\n";
   
  return 0;
}

// 反復子の値が変化することに注意
#include < iostream>
#include < deque>
using namespace std;

int main()
{
  deque< char> q;
  deque< char>::iterator p1, p2;
  int i;

  for(i=0; i<5; i++) q.push_back(i + 'A');

  cout << "Original sequence: ";
  for(i=0; i< q.size(); i++)
    cout << q[i] << " ";
  cout << "\n";

  p1 = q.begin() + 2;
  p2 = q.begin() + 3;
  cout << "*p1: " << *p1 << ", ";
  cout << "*p2: " << *p2 << "\n";
  cout << "\n";

  // シーケンスに要素を挿入する
  q.insert(p1, 'X');

  cout << "Sequence after insert: ";
  for(i=0; i< q.size(); i++)
    cout << q[i] << " ";
  cout << "\n";

  // これらは異なる要素を指している
  cout << "*p1: " << *p1 << ", ";
  cout << "*p2: " << *p2 << "\n";

  return 0;
}

// 両端キューを使用して順不同の情報パケットを再構成する
#include < iostream>
#include < deque>
#include < algorithm>
#include < string>
using namespace std;

class packet {
  int pnum;    // パケット番号
  string info; // 情報
public:
  packet() { pnum = -1; info = ""; }
  packet(int n, string i) {
    pnum = n;
    info = i;
  }

  int getpnum() const { return pnum; } 
  string getinfo() { return info; }
};

// 2つのパケットの大小を比較する
bool operator< (const packet &a, const packet &b) {
  return a.getpnum() < b.getpnum();
}

// 2つのパケットが等しいかどうかを判定する
bool operator==(const packet &a, const packet &b) {
  return a.getpnum() == b.getpnum();
}

/* 次のパケットを取得する
   パケットが取得できた場合はtrueを返し、
   そうでない場合はfalseを返す */
bool getpacket(packet &pkt)
{
  static packet message[] = {
    packet(2, "is"),
    packet(4, "Programming"),
    packet(0,"The"),
    packet(3, "Power"),
    packet(1, "STL"),
    packet(-1, "") // 転送の終了を示すマーク
  };
  static int i=0;

  if(message[i] == packet(-1, "")) return false;

  pkt = message[i];

  cout << "Sending: " << pkt.getinfo() << "\n";

  i++;
  return true;
}

int main()
{
  deque< packet> pack;
  deque< packet>::iterator p;
  packet pkt;

  getpacket(pkt); // 最初のパケットを取得する
  pack.push_back(pkt); // 最初のパケットを両端キューに格納する

  // 残りのパケットを読み取り、格納する
  while(getpacket(pkt)) {
    if(pkt.getpnum() <= pack.front().getpnum())
      pack.push_front(pkt);
    else if(pkt.getpnum() >= pack.back().getpnum())
      pack.push_back(pkt);
    else {
      p = lower_bound(pack.begin(), pack.end(), pkt);
      pack.insert(p, pkt);
    }
  }

  cout << "\nPackets reassembled:\n";
  for(int i=0; i< pack.size(); i++)
    cout << pack[i].getinfo() << " "; 

  return 0;
}