real legendlinelength=50;
real legendhskip=1.2;
real legendvskip=legendhskip;
real legendmargin=10;
real legendmaxrelativewidth=1;

// Return a unit polygon with n sides.
path polygon(int n)
{
  guide g;
  for(int i=0; i < n; ++i) g=g--expi(2pi*(i+0.5)/n-0.5*pi);
  return g--cycle;
}

// Return a unit n-point cyclic cross, with optional inner radius r and
// end rounding.
path cross(int n, bool round=true, real r=0)
{
  assert(n > 1);
  real r=min(r,1);
  real theta=pi/n;
  real s=sin(theta);
  real c=cos(theta);
  pair z=(c,s);
  transform mirror=reflect(0,z);
  pair p1=(r,0);
  path elementary;
  if(round) {
    pair e1=p1+z*max(1-r*(s+c),0);
    elementary=p1--e1..(c,s)..mirror*e1--mirror*p1;
  } else {
    pair p2=p1+z*(max(sqrt(1-(r*s)^2)-r*c),0);
    elementary=p1--p2--mirror*p2--mirror*p1;
  }

  guide g;
  real step=360/n;
  for(int i=0; i < n; ++i)
    g=g--rotate(i*step-90)*elementary;

  return g--cycle;
}

path plus=rotate(45)*cross(4);
path diamond=rotate(45)*polygon(4);

typedef void markroutine(picture pic=currentpicture, frame f, path g);

// On picture pic, add frame f about every node of path g.
void marknodes(picture pic=currentpicture, frame f, path g) {
  for(int i=0; i < size(g); ++i)
    add(pic,f,point(g,i));
}

// On picture pic, add n copies of frame f to path g, evenly spaced in
// arclength.
// If rotated=true, the frame will be rotated by the angle of the tangent
// to the path at the points where the frame will be added.
// If centered is true, center the frames within n evenly spaced arclength
// intervals.
markroutine markuniform(bool centered=false, int n, bool rotated=false) {
  return new void(picture pic=currentpicture, frame f, path g) {
    if(n <= 0) return;
    void add(real x) {
      real t=reltime(g,x);
      add(pic,rotated ? rotate(degrees(dir(g,t)))*f : f,point(g,t));
    }
    if(centered) {
      real width=1/n;
      for(int i=0; i < n; ++i) add((i+0.5)*width);
    } else {
      if(n == 1) add(0.5);
      else {
        real width=1/(n-1);
        for(int i=0; i < n; ++i)
          add(i*width);
      }
    }
  };
}

// On picture pic, add frame f at points z(t) for n evenly spaced values of
// t in [a,b].
markroutine markuniform(pair z(real t), real a, real b, int n)
{
  return new void(picture pic=currentpicture, frame f, path) {
    real width=b-a;
    for(int i=0; i <= n; ++i) {
      add(pic,f,z(a+i/n*width));
    }
  };
}

struct marker {
  frame f;
  bool above=true;
  markroutine markroutine=marknodes;
  void mark(picture pic=currentpicture, path g) {
    markroutine(pic,f,g);
  };
}

marker marker(frame f=newframe, markroutine markroutine=marknodes,
              bool above=true)
{
  marker m=new marker;
  m.f=f;
  m.above=above;
  m.markroutine=markroutine;
  return m;
}

marker marker(path[] g, markroutine markroutine=marknodes, pen p=currentpen,
              filltype filltype=NoFill, bool above=true)
{
  frame f;
  filltype.fill(f,g,p);
  return marker(f,markroutine,above);
}

// On picture pic, add path g with opacity thinning about every node.
marker markthin(path g, pen p=currentpen,
                real thin(real fraction)=new real(real x) {return x^2;},
                filltype filltype=NoFill) {
  marker M=new marker;
  M.above=true;
  filltype.fill(M.f,g,p);
  real factor=1/abs(size(M.f));
  M.markroutine=new void(picture pic=currentpicture, frame, path G) {
    transform t=pic.calculateTransform();
    int n=size(G);
    for(int i=0; i < n; ++i) {
      pair z=point(G,i);
      frame f;
      real fraction=1;
      if(i > 0) fraction=min(fraction,abs(t*(z-point(G,i-1)))*factor);
      if(i < n-1) fraction=min(fraction,abs(t*(point(G,i+1)-z))*factor);
      filltype.fill(f,g,p+opacity(thin(fraction)));
      add(pic,f,point(G,i));
    }
  };
  return M;
}

marker nomarker;

real circlescale=0.85;

path[] MarkPath={scale(circlescale)*unitcircle,
                 polygon(3),polygon(4),polygon(5),invert*polygon(3),
                 cross(4),cross(6),diamond,plus};

int[] MarkFillable={0,1,2,3,4,7};

marker[] Mark=sequence(new marker(int i) {return marker(MarkPath[i]);},
                       MarkPath.length);

marker[] MarkFill=sequence(new marker(int i) {
    return marker(MarkPath[MarkFillable[i]],Fill);
  },MarkFillable.length);

marker Mark(int n)
{
  n=n % (Mark.length+MarkFill.length);
  if(n < Mark.length) return Mark[n];
  else return MarkFill[n-Mark.length];
}

picture legenditem(Legend legenditem, real linelength)
{
  picture pic;
  pair z1=(0,0);
  pair z2=z1+(linelength,0);
  if(!legenditem.above && !empty(legenditem.mark))
    marknodes(pic,legenditem.mark,interp(z1,z2,0.5));
  if(linelength > 0)
    Draw(pic,z1--z2,legenditem.p);
  if(legenditem.above && !empty(legenditem.mark))
    marknodes(pic,legenditem.mark,interp(z1,z2,0.5));
  if(legenditem.plabel != invisible)
    label(pic,legenditem.label,z2,E,legenditem.plabel);
  else
    label(pic,legenditem.label,z2,E,currentpen);
  return pic;
}

picture legend(Legend[] Legend, int perline=1, real linelength,
               real hskip, real vskip, real maxwidth=0, real maxheight=0,
               bool hstretch=false, bool vstretch=false)
{
  if(maxwidth <= 0) hstretch=false;
  if(maxheight <= 0) vstretch=false;
  if(Legend.length <= 1) vstretch=hstretch=false;

  picture inset;
  size(inset,0,0,IgnoreAspect);

  if(Legend.length == 0)
    return inset;

  // Check for legend entries with lines:
  bool bLineEntriesAvailable=false;
  for(int i=0; i < Legend.length; ++i) {
    if(Legend[i].p != invisible) {
      bLineEntriesAvailable=true;
      break;
    }
  }

  real markersize=0;
  for(int i=0; i < Legend.length; ++i)
    markersize=max(markersize,size(Legend[i].mark).x);

  // If no legend has a line, set the line length to zero
  if(!bLineEntriesAvailable)
    linelength=0;

  linelength=max(linelength,markersize*(linelength == 0 ? 1 : 2));

  // Get the maximum dimensions per legend entry;
  // calculate line length for a one-line legend
  real heightPerEntry=0;
  real widthPerEntry=0;
  real totalwidth=0;
  for(int i=0; i < Legend.length; ++i) {
    picture pic=legenditem(Legend[i],linelength);
    pair lambda=size(pic);
    heightPerEntry=max(heightPerEntry,lambda.y);
    widthPerEntry=max(widthPerEntry,lambda.x);
    if(Legend[i].p != invisible)
      totalwidth += lambda.x;
    else {
      // Legend entries without leading line need less space in one-line legends
      picture pic=legenditem(Legend[i],0);
      totalwidth += size(pic).x;
    }
  }
  // Does everything fit into one line?
  if(((perline < 1) || (perline >= Legend.length)) &&
     (maxwidth >= totalwidth+(totalwidth/Legend.length)*
      (Legend.length-1)*(hskip-1))) {
    // One-line legend
    real currPosX=0;
    real itemDistance;
    if(hstretch)
      itemDistance=(maxwidth-totalwidth)/(Legend.length-1);
    else
      itemDistance=(totalwidth/Legend.length)*(hskip-1);
    for(int i=0; i < Legend.length; ++i) {
      picture pic=legenditem(Legend[i],
                             Legend[i].p == invisible ? 0 : linelength);
      add(inset,pic,(currPosX,0));
      currPosX += size(pic).x+itemDistance;
    }
  } else {
    // multiline legend
    if(maxwidth > 0) {
      int maxperline=floor(maxwidth/(widthPerEntry*hskip));
      if((perline < 1) || (perline > maxperline))
        perline=maxperline;
    }
    if(perline < 1) // This means: maxwidth < widthPerEntry
      perline=1;

    if(perline <= 1) hstretch=false;
    if(hstretch) hskip=(maxwidth/widthPerEntry-perline)/(perline-1)+1;
    if(vstretch) {
      int rows=ceil(Legend.length/perline);
      vskip=(maxheight/heightPerEntry-rows)/(rows-1)+1;
    }

    if(hstretch && (perline == 1)) {
      Draw(inset,(0,0)--(maxwidth,0),invisible());
      for(int i=0; i < Legend.length; ++i)
        add(inset,legenditem(Legend[i],linelength),
            (0.5*(maxwidth-widthPerEntry),
             -quotient(i,perline)*heightPerEntry*vskip));
    } else
      for(int i=0; i < Legend.length; ++i)
        add(inset,legenditem(Legend[i],linelength),
            ((i%perline)*widthPerEntry*hskip,
             -quotient(i,perline)*heightPerEntry*vskip));
  }

  return inset;
}

frame legend(picture pic=currentpicture, int perline=1,
             real xmargin=legendmargin, real ymargin=xmargin,
             real linelength=legendlinelength,
             real hskip=legendhskip, real vskip=legendvskip,
             real maxwidth=perline == 0 ?
             legendmaxrelativewidth*size(pic).x : 0, real maxheight=0,
	     bool hstretch=false, bool vstretch=false, pen p=currentpen)
{
  frame F;
  if(pic.legend.length == 0) return F;
  F=legend(pic.legend,perline,linelength,hskip,vskip,
           max(maxwidth-2xmargin,0),
           max(maxheight-2ymargin,0),
           hstretch,vstretch).fit();
  box(F,xmargin,ymargin,p);
  return F;
}

pair[] pairs(real[] x, real[] y)
{
  if(x.length != y.length) abort("arrays have different lengths");
  return sequence(new pair(int i) {return (x[i],y[i]);},x.length);
}

filltype dotfilltype = Fill;

void dot(frame f, pair z, pen p=currentpen, filltype filltype=dotfilltype)
{
  if(filltype == Fill)
    draw(f,z,dotsize(p)+p);
  else {
    real s=0.5*(dotsize(p)-linewidth(p));
    if(s <= 0) return;
    path g=shift(z)*scale(s)*unitcircle;
    begingroup(f);
    filltype.fill(f,g,p);
    draw(f,g,p);
    endgroup(f);
  }
}

void dot(picture pic=currentpicture, pair z, pen p=currentpen,
         filltype filltype=dotfilltype)
{
  pic.add(new void(frame f, transform t) {
      dot(f,t*z,p,filltype);
    },true);
  pic.addPoint(z,dotsize(p)+p);
}

void dot(picture pic=currentpicture, Label L, pair z, align align=NoAlign,
         string format=defaultformat, pen p=currentpen, filltype filltype=dotfilltype)
{
  Label L=L.copy();
  L.position(z);
  if(L.s == "") {
    if(format == "") format=defaultformat;
    L.s="("+format(format,z.x)+","+format(format,z.y)+")";
  }
  L.align(align,E);
  L.p(p);
  dot(pic,z,p,filltype);
  add(pic,L);
}

void dot(picture pic=currentpicture, Label[] L=new Label[], pair[] z,
	 align align=NoAlign, string format=defaultformat, pen p=currentpen,
	 filltype filltype=dotfilltype)
{
  int stop=min(L.length,z.length);
  for(int i=0; i < stop; ++i)
    dot(pic,L[i],z[i],align,format,p,filltype);
  for(int i=stop; i < z.length; ++i)
    dot(pic,z[i],p,filltype);
}

void dot(picture pic=currentpicture, Label[] L=new Label[],
	 explicit path g, align align=RightSide, string format=defaultformat,
	 pen p=currentpen, filltype filltype=dotfilltype)
{
  int n=size(g);
  int stop=min(L.length,n);
  for(int i=0; i < stop; ++i)
    dot(pic,L[i],point(g,i),-sgn(align.dir.x)*I*dir(g,i),format,p,filltype);
  for(int i=stop; i < n; ++i)
    dot(pic,point(g,i),p,filltype);
}

void dot(picture pic=currentpicture, path[] g, pen p=currentpen,
         filltype filltype=dotfilltype)
{
  for(int i=0; i < g.length; ++i)
    dot(pic,g[i],p,filltype);
}

void dot(picture pic=currentpicture, Label L, pen p=currentpen,
         filltype filltype=dotfilltype)
{
  dot(pic,L,L.position,p,filltype);
}

// A dot in a frame.
frame dotframe(pen p=currentpen, filltype filltype=dotfilltype)
{
  frame f;
  dot(f,(0,0),p,filltype);
  return f;
}

frame dotframe=dotframe();

marker dot(pen p=currentpen, filltype filltype=dotfilltype)
{
  return marker(dotframe(p,filltype));
}

marker dot=dot();