template<typename PointT> inline void
pcl::PCA<PointT>::reconstruct (const PointCloud& projection, PointCloud& input)
{
    if(!compute_done_)
        initCompute ();
    if (!compute_done_)
        PCL_THROW_EXCEPTION (InitFailedException, "[pcl::PCA::reconstruct] PCA initCompute failed");
    if (input.is_dense)
    {
        input.resize (projection.size ());
        for (size_t i = 0; i < projection.size (); ++i)
            reconstruct (projection[i], input[i]);
    }
    else
    {
        PointT p;
        for (size_t i = 0; i < input.size (); ++i)
        {
            if (!pcl_isfinite (input[i].x) ||
                    !pcl_isfinite (input[i].y) ||
                    !pcl_isfinite (input[i].z))
                continue;
            reconstruct (projection[i], p);
            input.push_back (p);
        }
    }
}

void from_mat_ZZ_p_crt_rep(const mat_ZZ_p_crt_rep& X, mat_ZZ_p& A)
{
   long n = X.rep[0].NumRows();
   long m = X.rep[0].NumCols();

   const MatPrime_crt_helper& H = get_MatPrime_crt_helper_info();
   long nprimes = H.GetNumPrimes();

   if (NTL_OVERFLOW(nprimes, CRT_BLK, 0))
      ResourceError("overflow"); // this is pretty academic

   A.SetDims(n, m);

   ZZ_pContext context;
   context.save();

   bool seq = (double(n)*double(m)*H.GetCost() < PAR_THRESH);

   // FIXME: right now, we just partition the rows, but if
   // #cols > #rows, we should perhaps partition the cols
   NTL_GEXEC_RANGE(seq, n, first, last)
   NTL_IMPORT(n)
   NTL_IMPORT(m)
   NTL_IMPORT(nprimes)

   context.restore();

   MatPrime_crt_helper_scratch scratch;
   Vec<MatPrime_residue_t> remainders_store;
   remainders_store.SetLength(nprimes*CRT_BLK);
   MatPrime_residue_t *remainders = remainders_store.elts();

   for (long i = first; i < last; i++) {
      ZZ_p *a = A[i].elts();

      long jj = 0; 
      for (; jj <= m-CRT_BLK; jj += CRT_BLK) {
         for (long k = 0; k < nprimes; k++) {
            const MatPrime_residue_t *x = X.rep[k][i].elts();
            for (long j = 0; j < CRT_BLK; j++)
               remainders[j*nprimes+k] = x[jj+j];
         }
         for (long j = 0; j < CRT_BLK; j++)
            reconstruct(H, a[jj+j].LoopHole(), remainders + j*nprimes, scratch);
      }
      if (jj < m) {
         for (long k = 0; k < nprimes; k++) {
            const MatPrime_residue_t *x = X.rep[k][i].elts();
            for (long j = 0; j < m-jj; j++)
               remainders[j*nprimes+k] = x[jj+j];
         }
         for (long j = 0; j < m-jj; j++)
            reconstruct(H, a[jj+j].LoopHole(), remainders + j*nprimes, scratch);
      }
   }

   NTL_GEXEC_RANGE_END
}

/* 新規の文字列オブジェクトを作成する */
void ITextRenderer::NewText(unsigned int ID, const std::wstring& str, int x, int y, float scale, float width, ArgbColor color) {
	if (StringData.size() <= ID) StringData.resize(ID + 1, nullptr); // 配列の拡張
	bool TextChanged = (!StringData[ID]) || (StringData[ID]->str != str);
	if (StringData[ID] && TextChanged) delete StringData[ID]; // 既に存在した場合
	if (TextChanged) StringData[ID] = new StringAttr;
	StringData[ID]->X = x; StringData[ID]->Y = y;
	StringData[ID]->scale = scale; StringData[ID]->width = width;
	StringData[ID]->color = color;
	if (TextChanged) {
		StringData[ID]->str = std::wstring(str);
		reconstruct(ID, true);
	} else {
		reconstruct(ID, false);
	}
}

int startReconstruction(){

	int return_value = 0;
	char str[200];

	FILE *dataFile = fopen(sinoPath,"r");
	logIt(DEBUG, "startReconstruction() started.");
	//Read P2
	fgets(str, 200, dataFile);
	if(!(str[0] == 'P' && str[1] == '2')){
		logIt(ERR, "Not a pgm.");
		return 1;
	}


	fgets(str, 200, dataFile); //Hopefully a commentary
	fscanf(dataFile,"%d",&imgwidth);
	fscanf(dataFile,"%d",&numangles);
	logIt(TRACE, "width: %d, angles: %d", imgwidth, numangles);
	fgets(str, 200, dataFile);

	fgets(str, 200, dataFile);//colordepth, we dont care about


	imgheight = 512;		//This is the height of the reconstructed image.

	return_value = reconstruct(dataFile);

	logIt(DEBUG, "startReconstruction() finished.");
	return return_value;
}

    void scale_reconstruction_impl(Point_collection & input,
                                   viennagrid::mesh output,
                                   scale_options options)
    {
      typedef Reconstruction::Triple_const_iterator                   Triple_iterator;
      // Construct the reconstruction with parameters for
      // the neighborhood squared radius estimation.
      Reconstruction reconstruct( options.neighborhood_size, options.sample_size );
      // Add the points.
      reconstruct.insert( input.begin(), input.end() );
      // Advance the scale-space several steps.
      // This automatically estimates the scale-space.
      reconstruct.increase_scale( options.scale );

      typedef viennagrid::mesh                                   MeshType;
      typedef viennagrid::result_of::element<MeshType>::type    VertexType;
      std::vector<VertexType> vertex_handles(input.size());
      int i=0;

      for(Point_collection::iterator begin = input.begin();begin!=input.end();++begin,++i)
        vertex_handles[i] = viennagrid::make_vertex( output,
          viennagrid::make_point(begin->x(),begin->y(),begin->z()));

      for( std::size_t shell = 0; shell < reconstruct.number_of_shells(); ++shell )
        for( Triple_iterator it = reconstruct.shell_begin( shell ); it != reconstruct.shell_end( shell ); ++it )
        {
          viennagrid::make_triangle(
            output,vertex_handles[(*it)[0]],
                   vertex_handles[(*it)[1]],
                   vertex_handles[(*it)[2]]);
        }
    }

/*
 * g723_24_decoder()
 *
 * Decodes a 3-bit CCITT G.723_24 ADPCM code and returns
 * the resulting 16-bit linear PCM, A-law or u-law sample value.
 * -1 is returned if the output coding is unknown.
 */
int
g726_24_decoder(
	int		i,
	g726_state *state_ptr)
{
	int		sezi;
	int		sez;			/* ACCUM */
	int		sei;
	int		se;
	int		y;				/* MIX */
	int		dq;
	int		sr;				/* ADDB */
	int		dqsez;

	i &= 0x07;				/* mask to get proper bits */
	sezi = predictor_zero(state_ptr);
	sez = sezi >> 1;
	sei = sezi + predictor_pole(state_ptr);
	se = sei >> 1;			/* se = estimated signal */

	y = step_size(state_ptr);	/* adaptive quantizer step size */
	dq = reconstruct(i & 0x04, _dqlntab[i], y); /* unquantize pred diff */

	sr = (dq < 0) ? (se - (dq & 0x3FFF)) : (se + dq); /* reconst. signal */

	dqsez = sr - se + sez;			/* pole prediction diff. */

	update(3, y, _witab[i], _fitab[i], dq, sr, dqsez, state_ptr);

	return (sr << 2);	/* sr was of 14-bit dynamic range */
}

reconstruct(int size, int t[][size+1], int i, int kp, int w[])
{
	if(i==0)
	{
		return;
	}
	if(t[i][kp] > t[i-1][kp])
	{
		printf("Item %d\n",i);
		reconstruct(size, t, i-1, kp -w[i],w);
	}
	else
	{
		reconstruct(size, t, i-1,kp,w);
	}
}

reconstruct(int size, int t[][size+1], int i, int sum, int a[])
{
	if(sum==0)
	{
		return;
	}
	if(t[i][sum] > t[i-1][sum])
	{
		printf(" %d ",a[i]);
		reconstruct(size, t, i-1, sum - a[i], a);
	}
	else
	{
		reconstruct(size, t, i-1, sum, a);
	}
}

/*
 * g723_40_encoder()
 *
 * Encodes a 16-bit linear PCM, A-law or u-law input sample and retuens
 * the resulting 5-bit CCITT G.723 40Kbps code.
 * Returns -1 if the input coding value is invalid.
 */
int	g723_40_encoder (int sl, G72x_STATE *state_ptr)
{
	short		sei, sezi, se, sez;	/* ACCUM */
	short		d;			/* SUBTA */
	short		y;			/* MIX */
	short		sr;			/* ADDB */
	short		dqsez;			/* ADDC */
	short		dq, i;

	/* linearize input sample to 14-bit PCM */
	sl >>= 2;		/* sl of 14-bit dynamic range */

	sezi = predictor_zero(state_ptr);
	sez = sezi >> 1;
	sei = sezi + predictor_pole(state_ptr);
	se = sei >> 1;			/* se = estimated signal */

	d = sl - se;			/* d = estimation difference */

	/* quantize prediction difference */
	y = step_size(state_ptr);	/* adaptive quantizer step size */
	i = quantize(d, y, qtab_723_40, 15);	/* i = ADPCM code */

	dq = reconstruct(i & 0x10, _dqlntab[i], y);	/* quantized diff */

	sr = (dq < 0) ? se - (dq & 0x7FFF) : se + dq; /* reconstructed signal */

	dqsez = sr + sez - se;		/* dqsez = pole prediction diff. */

	update(5, y, _witab[i], _fitab[i], dq, sr, dqsez, state_ptr);

	return (i);
}

	void reconstruct(const vt& ax, const vt& bx, //
			const vt& ay, const vt& by,  //
			const vt& az = 0, const vt& bz = 0) {
		Point s(ax, ay, az);
		Point e(bx, by, bz);
		reconstruct(s, e);
	}

void PushDown::setup() {
    
    seed.addListener(this, &PushDown::reconstruct<int>);
    numCells.addListener(this, &PushDown::reconstruct<int>);
    
    reconstruct();
}

string Puzzle::reconstruct(const State *const state){
	if(state->getPrev()==NULL){
		return "";
	}else{
		return reconstruct(state->getPrev())+" "+state->getPrev()->getMove(state);
	}
}

/*
 * g723_40_decoder()
 *
 * Decodes a 5-bit CCITT G.723 40Kbps code and returns
 * the resulting 16-bit linear PCM, A-law or u-law sample value.
 * -1 is returned if the output coding is unknown.
 */
int	g723_40_decoder	(int i, G72x_STATE *state_ptr)
{
	short		sezi, sei, sez, se;	/* ACCUM */
	short		y ;			/* MIX */
	short		sr;			/* ADDB */
	short		dq;
	short		dqsez;

	i &= 0x1f;			/* mask to get proper bits */
	sezi = predictor_zero(state_ptr);
	sez = sezi >> 1;
	sei = sezi + predictor_pole(state_ptr);
	se = sei >> 1;			/* se = estimated signal */

	y = step_size(state_ptr);	/* adaptive quantizer step size */
	dq = reconstruct(i & 0x10, _dqlntab[i], y);	/* estimation diff. */

	sr = (dq < 0) ? (se - (dq & 0x7FFF)) : (se + dq); /* reconst. signal */

	dqsez = sr - se + sez;		/* pole prediction diff. */

	update(5, y, _witab[i], _fitab[i], dq, sr, dqsez, state_ptr);

	return (sr << 2);	/* sr was of 14-bit dynamic range */
}

		//Perform a breadth first search
		static std::vector<edge_t> search(const edges_t& graph, const object_t start, const object_t end)
		{
			std::queue<object_t> q; //queue
			std::set<object_t> m; //set of marked id_t's
			edges_t h;
			
			m.insert(start);
			q.emplace(start);
			
			while(!q.empty())
			{
				id_t t = q.front();
				q.pop();
				
				if(t == end)
					return reconstruct(h, start, end);
				
				for(const edge_t& e : graph)
				{
					if(e.first == t && m.find(e.second) == m.end())
					{
						m.insert(e.second);
						q.emplace(e.second);
						h.emplace_back(e);
					}
				}
			}
			
			throw std::runtime_error("No path from start to end");
		}

/*
 * g721_encoder()
 *
 * Encodes the input vale of linear PCM, A-law or u-law data sl and returns
 * the resulting code. -1 is returned for unknown input coding value.
 */
int
g721_encoder(
	int		sl,
	G72x_STATE *state_ptr)
{
	short		sezi, se, sez;		/* ACCUM */
	short		d;			/* SUBTA */
	short		sr;			/* ADDB */
	short		y;			/* MIX */
	short		dqsez;			/* ADDC */
	short		dq, i;

	/* linearize input sample to 14-bit PCM */
	sl >>= 2;			/* 14-bit dynamic range */

	sezi = predictor_zero(state_ptr);
	sez = sezi >> 1;
	se = (sezi + predictor_pole(state_ptr)) >> 1;	/* estimated signal */

	d = sl - se;				/* estimation difference */

	/* quantize the prediction difference */
	y = step_size(state_ptr);		/* quantizer step size */
	i = quantize(d, y, qtab_721, 7);	/* i = ADPCM code */

	dq = reconstruct(i & 8, _dqlntab[i], y);	/* quantized est diff */

	sr = (dq < 0) ? se - (dq & 0x3FFF) : se + dq;	/* reconst. signal */

	dqsez = sr + sez - se;			/* pole prediction diff. */

	update(4, y, _witab[i] << 5, _fitab[i], dq, sr, dqsez, state_ptr);

	return (i);
}

Foam::ensightPartFaces::ensightPartFaces(Istream& is)
:
    ensightPart()
{
    isCellData_ = false;
    reconstruct(is);
}

/*
 * g726_32_decoder()
 *
 * Description:
 *
 * Decodes a 4-bit code of G.726_32 encoded data of i and
 * returns the resulting linear PCM, A-law or u-law value.
 * return -1 for unknown out_coding value.
 */
int
g726_32_decoder(
	int		i,
	int		out_coding,
	struct g726_state *state_ptr)
{
	short		sezi, sei, sez, se;	/* ACCUM */
	short		y;			/* MIX */
	short		sr;			/* ADDB */
	short		dq;
	short		dqsez;

	i &= 0x0f;			/* mask to get proper bits */
	sezi = predictor_zero(state_ptr);
	sez = sezi >> 1;
	sei = sezi + predictor_pole(state_ptr);
	se = sei >> 1;			/* se = estimated signal */

	y = step_size(state_ptr);	/* dynamic quantizer step size */

	dq = reconstruct(i & 0x08, _dqlntab[i], y); /* quantized diff. */

	sr = (dq < 0) ? (se - (dq & 0x3FFF)) : se + dq;	/* reconst. signal */

	dqsez = sr - se + sez;			/* pole prediction diff. */

	update(4, y, _witab[i] << 5, _fitab[i], dq, sr, dqsez, state_ptr);

	switch (out_coding) {
	case AUDIO_ENCODING_LINEAR:
		return (sr << 2);	/* sr was 14-bit dynamic range */
	default:
		return (-1);
	}
}

int main(int argc, char ** argv) {
	//create_dummy_vol_file(); exit(0);
	holger_time_start(0, "Main");	
	holger_time(0, "OpenCL initialization");
	read_input(
		"C:\\Master Holger\\Franks thumb drive\\UL\\Nevro_Spine\\SpineData\\ultrasoundSample5.mhd",
		"C:\\Master Holger\\Franks thumb drive\\UL\\Nevro_Spine\\SpineData\\ultrasoundSample5.pos",
		"C:\\Master Holger\\Franks thumb drive\\UL\\Nevro_Spine\\SpineData\\ultrasoundSample5.tim",
		"C:\\Master Holger\\Franks thumb drive\\UL\\Nevro_Spine\\SpineData\\ultrasoundSample5.msk",
		//"C:\\Master Holger\\Simple test input\\Lines\\lines.vol",
		"C:\\Master Holger\\Franks thumb drive\\UL\\Nevro_Spine\\SpineData\\ultrasoundSample5.vol",
		"C:\\Master Holger\\Franks thumb drive\\UL\\Nevro_Spine\\calibration_files\\M12L.cal"
	);
	holger_time(0, "Read input files");
	#pragma omp parallel num_threads(2)
	{
		int thread_idx = omp_get_thread_num();
		if (thread_idx == 0) {
			printf("Reconstruct thread\n");
			reconstruct();
		} else if (thread_idx == 1) {
			printf("GUI thread\n");
			gui(argc, argv);
		}
	}

	gui(argc, argv);
	holger_time(0, "Reconstruction");
	holger_time_print(0);
	exit(0);
}

int 
main () {
	char A[][5] = {"abc", "def", "gap", "h", "wxyz"};
	char S[] = "abcpaa";

	printf ("String %s, constructed: %d.\n", S, reconstruct(S, 5, A, 5));
	return 0;
}

/* 根据前序和中序遍历结果，重建子树，返回其根节点的地址
 *
 * 前序遍历：1   2   4   7   3   5   6   8
 *           ^   ^^^^^^^^^   ^^^^^^^^^^^^^
 *           根    左子树        右子树
 *
 * 中序遍历：4   7   2   1   5   3   8   6
 *           ^^^^^^^^^   ^   ^^^^^^^^^^^^^
 *             左子树    根      右子树
 */
TREE_NODE* reconstruct (int preorder[], int inorder[], size_t size) {
	if (! preorder || ! inorder || ! size)
		return NULL;

	TREE_NODE* root = create_node (preorder[0]);

	size_t len; /* 左子树长度 */
	for (len = 0; len < size && inorder[len] != preorder[0]; ++len);
	if (len >= size)
		return NULL;

	root->left = reconstruct (preorder + 1, inorder, len);
	root->right = reconstruct (preorder + 1 + len, inorder + len + 1,
		size - len - 1);

	return root;
}