#include "stdafx.h"
#include <deque>
#include <iostream>
using namespace std;
typedef struct Elem {
Elem(int val, bool isA) : value(val), isArrayA(isA), isFirstB(true) {}
int value;
bool isArrayA;
bool isFirstB;
} Element;
class CCombination {
public:
CCombination(unsigned int sizeA, int *a, unsigned int sizeB, int *b);
~CCombination();
void Combine();
void PrintResult();
private:
int *arrA, *arrB;
unsigned int uiSizeA, uiSizeB;
deque <Element> orgQue;
deque <int> orgResQue;
};
CCombination::CCombination(unsigned int sizeA, int *aA, unsigned int sizeB, int *aB)
: uiSizeA(sizeA), uiSizeB(sizeB)
{
arrA = new int[uiSizeA];
arrB = new int[uiSizeB];
memcpy((void*)arrA, (void*)aA, sizeof(int)*uiSizeA);
memcpy((void*)arrB, (void*)aB, sizeof(int)*uiSizeB);
for (int i = 0; i < uiSizeA; i++) {
}
for (int i = 0; i < uiSizeB; i++) {
}
}
CCombination::~CCombination()
{
delete [] arrA, arrB;
}
void CCombination::Combine()
{
if (!orgQue.empty()) {
cout << "Combined already!" << endl
; return;
}
unsigned int iIdxA = 0, iIdxB = 0;
deque <Element> arrangedQue;
arrangedQue.push_back(Element(arrA[iIdxA], true));
iIdxA++;
while (arrB[iIdxB] < arrangedQue.front().value) {
iIdxB++;
}
while (iIdxA < uiSizeA) {
if (iIdxB < uiSizeB && arrB[iIdxB] < arrA[iIdxA]) {
arrangedQue.push_back(Element(arrB[iIdxB], false));
iIdxB++;
}
else {
arrangedQue.push_back(Element(arrA[iIdxA], true));
iIdxA++;
}
}
while (iIdxB < uiSizeB) {
arrangedQue.push_back(Element(arrB[iIdxB], false));
iIdxB++;
}
deque <Element> tmpQue = orgQue = arrangedQue;
cout << "Combined array: "; while (!tmpQue.empty()) {
cout << tmpQue.
front().
value << "-" << (tmpQue.
front().
isArrayA ? "A " : "B "); tmpQue.pop_front();
}
}
void CCombination::PrintResult()
{
if (orgQue.empty()) {
cout << "Combine first!" << endl
; return;
}
int iArrangedQueSize = 0;
int iArrangedQueCnt = 0;
int iResQueSize = 0;
int iResQueCnt = 0;
int iResPairs = 0;
bool bFoundFirstB = false;
deque <Element> tmpQue, arrangedQue;
arrangedQue = orgQue;
while (1) {
// Create resultQue
iArrangedQueCnt = 0;
iArrangedQueSize = arrangedQue.size();
bFoundFirstB = false;
//cout << iArrangedQueSize << endl;
if (iArrangedQueSize < 2) break;
tmpQue = arrangedQue;
if (false == tmpQue.front().isArrayA) {
iArrangedQueCnt = 0;
orgQue.pop_front();
arrangedQue = orgQue;
continue;
}
iResQueCnt = 0;
while (1) {
if (iArrangedQueCnt == iArrangedQueSize) break;
if (true == tmpQue.front().isArrayA) {
if (true == orgResQue.empty() || iResQueCnt % 2 == 0) {
orgResQue.push_back(tmpQue.front().value);
iResQueCnt++;
}
else {
}
}
else {
if (iResQueCnt % 2 == 1 && tmpQue.front().isFirstB) {
orgResQue.push_back(tmpQue.front().value);
iResQueCnt++;
if (false == bFoundFirstB) {
arrangedQue.at(iArrangedQueCnt).isFirstB = false;
bFoundFirstB = true;
}
}
else {
}
}
tmpQue.pop_front();
iArrangedQueCnt++;
}
if (false == arrangedQue.back().isFirstB) {
orgQue.pop_front();
arrangedQue = orgQue;
}
// Display resultQue
iResQueSize = orgResQue.size();
iResPairs = iResQueSize / 2;
deque <int> tmpResQue = orgResQue;
for (int i = 0; i < iResPairs; i++) {
for (int j = 0; j < i + 1; j++) {
cout << tmpResQue.
at(2 * j
) << " " << tmpResQue.
at(2 * j
+ 1) << " "; }
}
orgResQue.clear();
}
}
int main()
{
int arrA[] = { 10, 15, 25 };
int arrB[] = { 1, 5, 20, 30 };
CCombination MyCombination(3, arrA, 4, arrB);
MyCombination.Combine();
MyCombination.Combine();
MyCombination.PrintResult();
cout << "\n END " << endl
;
getchar();
return 0;
}