import drawtree;

treeLevelStep = 10mm;
treeMinNodeWidth= 1mm;
treeNodeStep = 1mm;

TreeNode dotNode( TreeNode parent = null )
{
  frame f;
  dot( f, (0,0), defaultpen+3);
  return makeNode( parent, f );
}

TreeNode CompleteTree( TreeNode parent= null, int d, int h)
{
  TreeNode me=dotNode(parent);
  
  if ( h>1 ) {
    for( int j=0; j<d; ++j) {
      CompleteTree( me, d, h-1);
    }
  }
  return me;
}

TreeNode CompleteTreeOutline( TreeNode parent= null, int d, int h)
{
  frame f;

  label(f, format("$C_{%d}$", h), (0,0));
  //  draw(f,box(min(f),max(f)));
  

  real width=(max(f).x-min(f).x)+2pt;
  real height=(max(f).y-min(f).y)+2pt;
  real z=height/sqrt(3);
  real h=sqrt(3)*(z+width/2);

  pair bot=(max(f)+min(f)-(0,height))/2;
  
  pair llft=bot-(z+width/2,0);
  pair lrt=bot+(z+width/2,0);
  pair top=bot+(0,h);

  draw(f,llft--top--lrt--cycle);

  return makeNode( parent, f);
}

TreeNode FestoonBranch( int d, int branches[], bool outline=false )
{
  TreeNode root=dotNode();
  for( int j : branches ) {
    if ( outline ) {
      CompleteTreeOutline(root, d, j);
    } else if ( j>0 ) {
      CompleteTree(root, d, j );
    }
  }
  return root;
}

void FestoonTree( int d, int[] allbranches[], bool outline=false ) {
  TreeNode[] roots;

  for( int[] b : allbranches ) {
    roots.push(FestoonBranch(d, b, outline));
  }

  real x=0;
  path p=nullpath;

  for( TreeNode r : roots ) {
    real width= layout(1,r);
    p=p--(x+width/2,0);
    draw(r, (x+width/2,0));
    x += width+treeNodeStep;
  }

  draw(p);

}

int[] repeat_integer(int a, int n)
{
  return sequence( new int (int i) { return a; }, n );
}

int mod(int a, int b)
     // computes a mod b with 0<= a mod b < b
{
  return a-b*quotient(a,b) ;
}

void FestoonTree( int d, int n, bool outline=false ) {
  int m=(d-1)*n+1;
  int k=0;
  int[][] alltrees;

  while( m > 0 ) {
    int r=mod(d-1-m,d);
    int a=(d-1)*(1+(d+1)*r);
    int[] trees;

    if ( a<m ) {
      trees=concat(repeat_integer(k,d-1-r),
		   repeat_integer(k+2,r));
    } else {
      a=m;

      if ( a == 1) {
	trees=repeat_integer(k-1, d);
      } else {
	int t1 = quotient(a-d,d-1); // t1=q+(d+1)r
	int q = mod( t1, d+1);
	int r = quotient( t1-q, d+1 );
	trees=concat(repeat_integer(k, d-q-r),
		     repeat_integer(k+1, q),
		     repeat_integer(k+2, r));
      }
    } 
    
    m=quotient(m-a,d);
    ++k;
    alltrees.push(trees);

  }

  write(alltrees);
  FestoonTree( d, alltrees, outline );
}