/* C++ source of A160160, Richard J. Mathar, Jan 09 2010 */
#include <iostream>
#include <vector>
using namespace std ;

/* define the macro PRINT_GNUPLOT if a gnuplot(1) file is to be created, like a160160.gp:
gnuplot <<++
	set terminal postscript portrait enhanced color
	unset border
	set size 1,0.75
	set view 70,60
	set ticslevel 0
	set xrange [-5:5]
	set yrange [-5:5]
	set zrange [-5:5]
	set format x ""
	set format y ""
	set format z ""
	unset tics
	load "a160160.out"
++
Gv a160160*.eps

This assumes that a160160.nul contains gnuplot(1) axis coordinates:

0 -5 0 
0 5 0 


-5 0 0 
5 0 0 


0 0 -5
0 0 5
*/

/** A point in the 3D simple cubic integer grid
*/
class Pt {
public:
	/** The three Cartesian coordinates
	*/
	int x,y,z ;
	Pt(int X, int Y, int Z) : x(X), y(Y), z(Z)
	{
	}
} ; /* Pt */

/** A toothpick of length 2 in the 3D simple cubic grid,
* aligned with one of the 3 coordinate axes.
*/
class Tp {
public:
	/* its two terminating points */
	Pt a;
	Pt b;

	/* constructor from the three cartesian coordinates
	* of each of the 2 ends
	*/
	Tp(int x1, int y1, int z1, int x2, int y2, int z2) : a(x1,y1,z1), b(x2,y2,z2)
	{
	}

	/** Compute the toothpick that crosses the toothpick (which is from st to en)
	* at the point en.
	*/
	static vector<Tp> perp(const Pt & st, const Pt & en, int gen)
	{
		if ( st.x == en.x && st.y == en.y)	/* original toothp is vertical */
		{
			Tp fi(en.x-1, en.y, en.z, en.x+1, en.y, en.z) ;
			Tp se(en.x, en.y-1, en.z, en.x, en.y+1, en.z) ;
			vector<Tp> res ;
			switch( gen % 3)
			{
			case 0:
				res.push_back(se) ;
				break;
			case 1:
				break ;
			case 2:
				res.push_back(fi) ;
			}
			return res ;
		}
		else if( st.y == en.y && st.z == en.z)	/* is horizontal parallel to x */
		{	
			Tp fi(en.x, en.y-1, en.z, en.x, en.y+1, en.z) ;
			Tp se(en.x, en.y, en.z-1, en.x, en.y, en.z+1) ;
			vector<Tp> res ;
			switch( gen % 3)
			{
			case 0:
				res.push_back(fi) ;
				break;
			case 1:
				res.push_back(se) ;
				break ;
			case 2:
				break ;
			}
			return res ;
		}
		else	/* is horizontal parallel to y */
		{
			Tp fi(en.x-1, en.y, en.z, en.x+1, en.y, en.z) ;
			Tp se(en.x, en.y, en.z-1, en.x, en.y, en.z+1) ;
			vector<Tp> res ;
			switch( gen % 3)
			{
			case 0:
				break;
			case 1:
				res.push_back(se) ;
				break ;
			case 2:
				res.push_back(fi) ;
			}
			return res ;
		}
	}

	/* return true if the point pt is one of the ends of this tootpick here.
	*/
	bool has(const Pt & pt) const
	{
		return ( pt.x == a.x && pt.y == a.y && pt.z == a.z
			|| pt.x == b.x && pt.y == b.y && pt.z == b.z) ;
	}

	/* return true if the point pt is the mid point of this tootpick here.
	*/
	bool hasMid (const Pt & pt) const
	{
		return ( 2*pt.x == a.x+b.x && 2*pt.y == a.y+b.y && 2*pt.z == a.z+b.z) ;
	}
}; /* Tp */

/** A toothpick set
*/
class TpS {
public:
	/** The set of all toothpicks
	*/
	vector<Tp> ts;

	/* Construct it form a vector of known toothpicks
	*/
	TpS( vector<Tp> & in) : ts(in)
	{
	}

	/** OEIS main functionality: count toothpicks in the set
	*/
	int cnt() const
	{
		return ts.size() ;
	}

	/** return true if p is a terminal point of any toothpick of this set
	*/
	bool isExp(const Pt & p) const
	{
		/* scan all toothpicks in the set and increment the counter by
		* 1 each time p is an end, and by 2 if p is a mid point
		*/
		int cnt = 0;
		for(int i=0; i< ts.size() ; i++)
		{
			if ( ts[i].has(p) )
				cnt++ ;
			if ( ts[i].hasMid(p) )
				cnt += 2 ;
		}
		/* return true if the counter is 1, else false */
		return ( cnt == 1) ;
	}

	/** return the next generation of toothpicks, including the
	* tootpick of the current set (generation).
	*/
	TpS nextg(int gen) const
	{
		/* new generation, initially empty */
		vector<Tp> res ;

		/* scan all tootpicks in the current set */
		for(int i=0 ; i < ts.size() ; i++)
		{
			/* if one of the two ends of the tootpick in the current
			* set is an exposed point, construct the crossing toothpick
			* and add it to the new generation.
			*/
			if ( isExp( ts[i].a ) )
			{
				vector<Tp> n = Tp::perp(ts[i].b,ts[i].a,gen) ;
				if ( n.size() > 0 )
					res.push_back(n[0]) ;
			}
			if ( isExp( ts[i].b ) )
			{
				vector<Tp> n = Tp::perp(ts[i].a,ts[i].b,gen) ;
				if ( n.size() > 0 )
					res.push_back(n[0]) ;
			}
		}
#ifdef PRINT_GNUPLOT
		/* debug: print status for gnuplot(1) */
		for(int i=0 ; i < res.size() ; i++)
		{
			cout << "set arrow from " 
				<< res[i].a.x << "," << res[i].a.y << "," << res[i].a.z << " to "
				<< res[i].b.x << "," << res[i].b.y << "," << res[i].b.z << " nohead lt 2 "
				<< endl ;
		}
#endif
		/* append the toothpicks of the current set 
		*/
		for(int i=0 ; i < ts.size() ; i++)
		{
			res.push_back( ts[i] ) ;
#ifdef PRINT_GNUPLOT
			cout << "set arrow from " 
				<< ts[i].a.x << "," << ts[i].a.y << "," << ts[i].a.z << " to "
				<< ts[i].b.x << "," << ts[i].b.y << "," << ts[i].b.z << " nohead "
				<< endl ;
#endif
		}
#ifdef PRINT_GNUPLOT
		cout << "splot \"a160160.nul\" notitle wi li" << endl ;
		cout << "unset arrow" << endl ;
#endif
		return res ;
	}
}; /* TpS */


/* Main function. No command line arguments. Makefile:
a160160_2.eps: a160160.out a160160.gp a160160.nul
        a160160.gp

a160160.out: a160160
        $< > $@

a160160: a160160.cpp
        # $(CXX) -O -o $@ -DPRINT_GNUPLOT $<
        $(CXX) -O -o $@ $<
*/
int main(int argc, char *argv[])
{
#ifndef PRINT_GNUPLOT
	cout << "0," ;
#endif
	/* Start with a single tootpick pointing from (0,0,-1) to (0,0,1)
	*/
	Tp rol(0,0,-1,0,0,1) ;
	vector<Tp> rot;
	rot.push_back(rol) ;
	/* Initialize the first generation with the toothpick set that
	* contains only this one toothpick
	*/
	TpS root(rot) ;

	/* loop over generations */
	for(int gen=2 ;
#ifdef PRINT_GNUPLOT
		gen < 12  ;
#else
		gen < 80  ;
#endif
		gen++)
	{
		/* print the current total count of toothpicks in that generation */
#ifndef PRINT_GNUPLOT
		cout << root.cnt() << ",\n" ;
#else
		cout << "# gen= " << gen << " " << root.cnt() << endl ;
		cout << "set output \"a160160_" << gen << ".eps\n" ;
#endif
		/* add toothpicks to the exposed points */
		TpS g = root.nextg(gen);
		root = g ;
	}
	cout << endl ;
}