/* EXPORT-> HDrawArc: Draw arc from stAngle thru arcAngle degrees */
void HDrawArc(int x0, int y0, int x1, int y1, int stAngle, int arcAngle)
{
   int Center_x = (x0+x1)/2;
   int Center_y = (y0+y1)/2;
   int StartArc_x, StartArc_y;
   int EndArc_x, EndArc_y;
   int radius; /* major axis */
   double startAngle, endAngle,convrt = PI/180; /* degrees to radians */
   HGDIOBJ oldObject = SelectObject(memDC,thePen);
   HDC dc = GetDC(theWindow);
     
   CheckCorners(&x0,&y0,&x1,&y1);
     
   startAngle = stAngle *convrt; 
   endAngle=(arcAngle+stAngle)*convrt;
     
   radius = (((x1-x0) > (y1-y0)) ? x1-x0 : y1-y0)/2;
   StartArc_x = Center_x + (int) (radius * cos((double) startAngle));
   StartArc_y = Center_y - (int) (radius * sin((double) startAngle));
   EndArc_x = Center_x + (int) (radius * cos((double) endAngle));
   EndArc_y = Center_y - (int) (radius * sin((double) endAngle));
     
   Arc(memDC,x0,y0,x1,y1,StartArc_x,StartArc_y,EndArc_x,EndArc_y);
   SelectObject(memDC,oldObject);
     
   oldObject = SelectObject(dc,thePen);
   Arc(dc,x0,y0,x1,y1,StartArc_x,StartArc_y,EndArc_x,EndArc_y);
   SelectObject(dc,oldObject);
   ReleaseDC(theWindow,dc);
}

void APSPAlgorithms::GraphicalFloydWarshall()
{
    clock_t startTime = clock();
    relaxNum = 0;

    // GraphicalFloydWarshall initialization
    vector<map<int, Arc> > fromList, toList;
    fromList.resize(nodeNum + 1);
    toList.resize(nodeNum + 1);
    for (auto arc: arcs) {
        fromList[arc.from][arc.to] = arc;
        toList[arc.to][arc.from] = arc;
    }

    Arc startArc, endArc;
    for (int mid = 1; mid < nodeNum + 1; mid++)
        for (auto startArcEntry: toList[mid])
            for (auto endArcEntry: fromList[mid]) {
                startArc = startArcEntry.second;
                endArc = endArcEntry.second;

                relaxNum++;
                int temp = startArc.arcLength + endArc.arcLength;
                if (dis[startArc.from][endArc.to] > temp) {
                    fromList[startArc.from][endArc.to] = Arc(startArc.from, endArc.to, temp);
                    toList[endArc.to][startArc.from] = Arc(startArc.from, endArc.to, temp);

                    dis[startArc.from][endArc.to] = temp;
                    pre[startArc.from][endArc.to] = mid;
                }
            }

    processTime = clock() -startTime;
}

void circle(int x, int y, int radius)
{
    pcache.select(color+BG); 
    int ry = (unsigned)radius*aspect_ratio_x/aspect_ratio_y;
    int rx = radius;
    if (bgiemu_handle_redraw || visual_page != active_page) { 
	Arc(hdc[1], x-rx, y-ry, x+rx, y+ry, x+rx, y, x+rx, y);
    }
    if (visual_page == active_page) { 
        Arc(hdc[0], x-rx, y-ry, x+rx, y+ry, x+rx, y, x+rx, y);
    }    
}

void drawFace(HDC hdc, HPEN hFacePen,HPEN hOldPen, COLORREF face_color) {
    hFacePen = CreatePen(PS_SOLID, 3, face_color);
    hOldPen = (HPEN) SelectObject(hdc, hFacePen);
    Arc(hdc, 50, 200, 150, 300, 0, 0, 0, 0);
    Arc(hdc, 80, 230, 90, 240, 0, 0, 0, 0);
    Arc(hdc, 110, 230, 120, 240, 0, 0, 0, 0);
    if(bgoodMood) {
        Arc(hdc, 65, 215, 135, 285, 65, 260, 135, 260);
    } else {
        Arc(hdc, 65, 260, 135, 330, 135, 270, 65, 270);
    };
    SelectObject(hdc, hOldPen);
    DeleteObject(hFacePen);
}

void Win32Window::drawCircle(int Ox, int Oy, int radius, COLORREF color, int linewidth)
{
    HPEN hPen = CreatePen(PS_SOLID, linewidth, color);
    SelectObject(hDoubleBufferDC, hPen);
    SetArcDirection(hDoubleBufferDC,AD_CLOCKWISE);
    Arc(hDoubleBufferDC, 
        Ox - radius, Oy - radius, Ox + radius, Oy + radius, 
        Ox, Oy - radius, Ox, Oy + radius);
    SetArcDirection(hDoubleBufferDC,AD_COUNTERCLOCKWISE);
    Arc(hDoubleBufferDC, 
        Ox - radius, Oy - radius, Ox + radius, Oy + radius, 
        Ox, Oy - radius, Ox, Oy + radius);
    DeleteObject(hPen);
}

void PLOTTER::ThickArc( const wxPoint& centre, double StAngle, double EndAngle,
                        int radius, int width, EDA_DRAW_MODE_T tracemode )
{
    if( tracemode == FILLED )
        Arc( centre, StAngle, EndAngle, radius, NO_FILL, width );
    else
    {
        SetCurrentLineWidth( -1 );
        Arc( centre, StAngle, EndAngle,
             radius - ( width - currentPenWidth ) / 2, NO_FILL, -1 );
        Arc( centre, StAngle, EndAngle,
             radius + ( width - currentPenWidth ) / 2, NO_FILL, -1 );
    }
}

// 根据半径、中心点和类型画四分之一圆弧
void DrawQuarterArc(HDC hdc, int radius, int xPoint, int yPoint, int style)
{
	POINT p1, p2, p3, p4, pStart, pEnd;
	p1.x = xPoint + radius;
	p1.y = yPoint;
	p2.x = xPoint;
	p2.y = yPoint - radius;
	p3.x = xPoint - radius;
	p3.y = yPoint;
	p4.x = xPoint;
	p4.y = yPoint + radius;
	switch (style)
	{
	case 0:
		pStart = p1;
		pEnd = p2;
		break;
	case 1:
		pStart = p2;
		pEnd = p3;
		break;
	case 2:
		pStart  = p3;
		pEnd = p4;
		break;
	case 3:
		pStart = p4;
		pEnd = p1;
		break;
	default:
		return;
	}

	Arc(hdc, xPoint - radius, yPoint - radius, xPoint + radius, yPoint + radius, pStart.x, pStart.y, pEnd.x, pEnd.y);
}

static Void local drawClassRelations(HDC hDC)
{
  Class cls;
  for(cls=CLASSMIN; cls<classMax(); cls++) {
    List supers;
    for(supers=cclass(cls).supers; nonNull(supers); supers=tl(supers)) {
      Class parent = getHead(hd(supers));
      if (isClass(parent)) {
	if (parent == cls) {     /* child of itself - draw an arc */
	  Class source = findClassInNodes(cls);
	  Arc(hDC, Nodes[source].Pos.right-5,  Nodes[source].Pos.bottom-5,
		   Nodes[source].Pos.right+15, Nodes[source].Pos.bottom+20,
		   Nodes[source].Pos.right-5,  Nodes[source].Pos.bottom-5,
		   Nodes[source].Pos.right-4,  Nodes[source].Pos.bottom-4);
	} else { 	               /* Join the two classes with a line */
	  Class source = findClassInNodes(parent);
	  Class target = findClassInNodes(cls);

	  INT sx = Nodes[source].Pos.right + 4;
	  INT sy = Nodes[source].Pos.top
		   + (Nodes[source].Pos.bottom - Nodes[source].Pos.top)/2;
	  INT tx = Nodes[target].Pos.left  - 4;
	  INT ty = Nodes[target].Pos.top
		   + (Nodes[target].Pos.bottom - Nodes[target].Pos.top)/2;

	  MoveToEx(hDC, sx, sy,NULL);
	  LineTo(hDC, tx, ty);
	}
      }
    }
  }
}

bool RecVolumesRestore(RAROptions *Cmd,const wchar *Name,bool Silent)
{
  Archive Arc(Cmd);
  if (!Arc.Open(Name))
  {
    if (!Silent)
      ErrHandler.OpenErrorMsg(Name);
    return false;
  }

  RARFORMAT Fmt=RARFMT15;
  if (Arc.IsArchive(true))
    Fmt=Arc.Format;
  else
  {
    byte Sign[REV5_SIGN_SIZE];
    Arc.Seek(0,SEEK_SET);
    if (Arc.Read(Sign,REV5_SIGN_SIZE)==REV5_SIGN_SIZE && memcmp(Sign,REV5_SIGN,REV5_SIGN_SIZE)==0)
      Fmt=RARFMT50;
  }
  Arc.Close();

  // We define RecVol as local variable for proper stack unwinding when
  // handling exceptions. So it can close and delete files on Cancel.
  if (Fmt==RARFMT15)
  {
    RecVolumes3 RecVol(false);
    return RecVol.Restore(Cmd,Name,Silent);
  }
  else
  {
    RecVolumes5 RecVol(false);
    return RecVol.Restore(Cmd,Name,Silent);
  }
}

void CDrawHelper::DrawCircle( COLORREF clr, int x, int y, int radius, bool filled /*= true*/ )
{
	RECT rc;
	rc.left = x - radius / 2;
	rc.right = rc.left + radius;
	rc.top = y - radius / 2;
	rc.bottom = y + radius;

	OffsetSubRect( rc );

	HPEN pen = CreatePen( PS_SOLID, 1, clr );
	HBRUSH br = CreateSolidBrush( clr );

	HPEN oldPen = (HPEN)SelectObject( m_dcMemory, pen );
	HBRUSH oldBr = (HBRUSH)SelectObject( m_dcMemory, br );

	if ( filled )
	{
		Ellipse( m_dcMemory, rc.left, rc.top, rc.right, rc.bottom );
	}
	else
	{
		Arc( m_dcMemory, rc.left, rc.top, rc.right, rc.bottom,
			rc.left, rc.top, rc.left, rc.top );
	}
	
	SelectObject( m_dcMemory, oldPen );
	SelectObject( m_dcMemory, oldBr );

	DeleteObject( pen );
	DeleteObject( br );
}

// This function draws a circular arc, centered at (x,y) with the given radius.
// The arc travels from angle stangle to angle endangle.  The angles are given
// in degrees in standard mathematical notation, with 0 degrees along the
// vector (1,0) and travelling counterclockwise.
// POSTCONDITION: The arccoords variable (arcinfo) for the current window
//                is set with data resulting from this call.
//                The current position is not modified.
//
void arc( int x, int y, int stangle, int endangle, int radius )
{
    HDC hDC;
    WindowData* pWndData = BGI__GetWindowDataPtr( );
    // Convert coordinates to those expected by GDI Arc
    int left, top, right, bottom;
    int xstart, ystart, xend, yend;

    // Convert center coordinates to box coordinates
    CenterToBox( x, y, radius, radius, &left, &top, &right, &bottom );
    // Convert given arc specifications to pixel start and end points.
    ArcEndPoints( x, y, radius, radius, stangle, endangle, &xstart, &ystart, &xend, &yend );

    // Draw to the current active page
    hDC = BGI__GetWinbgiDC( );
    Arc( hDC, left, top, right, bottom, xstart, ystart, xend, yend );
    BGI__ReleaseWinbgiDC( );
    
    // The update rectangle does not contain the right or bottom edge.  Thus
    // add 1 so the entire region is included.
    RECT rect = { left, top, right+1, bottom+1 };
    RefreshWindow( &rect );

    // Set the arccoords structure to relevant data.
    pWndData->arcInfo.x = x;
    pWndData->arcInfo.y = y;
    pWndData->arcInfo.xstart = xstart;
    pWndData->arcInfo.ystart = ystart;
    pWndData->arcInfo.xend = xend;
    pWndData->arcInfo.yend = yend;
}

		/// \brief Marks the specified arc as being used.
		void use(const Tilewire& inTilewire1, const Tilewire& inTilewire2) {
			// extract the tile indexes
			TileIndex tileIndex1 = inTilewire1.getTileIndex();
			TileIndex tileIndex2 = inTilewire2.getTileIndex();
			// ensure that these tilewires belong to the same tile
			/// \todo Throw a meaningful exception.
			if(tileIndex1 != tileIndex2) throw InvalidArcException(Arc(inTilewire1, inTilewire2));

			// make sure we have a bitset for this tile
			dynamic_bitset* bitset = mBitsets[tileIndex1];
			if(bitset == 0) {
				// determine how many arcs are in this tile
				const TileInfo& tileInfo = mTiles.getTileInfo(tileIndex1);
				TileTypeIndex type = tileInfo.getTypeIndex();
				const Array<const WireInfo>& wires = mTiles.getWireInfo(type);
				if(wires.getSize() == 0) return;
				const WireInfo& wireInfo = mTiles.getWireInfo(type, WireIndex(wires.getSize() - 1));
				// caution: we have to add the regular and irregular sink count from the last wire
				size_t size = wireInfo.getArcOffset() + wireInfo.getSinks().getSize() 
					+ wireInfo.getIrregularSinks().getSize() 
					+ wireInfo.getRoutethroughSinks().getSize()
					+ wireInfo.getTiedSinks().getSize();
				bitset = mBitsets[tileIndex1] = new dynamic_bitset(size);
				// track the statistics
				mTileUsageCount++;
				mBitCount += size;
			}

			// set the bit and mark the tile dirty
			bitset->set(getArcOffset(inTilewire1, inTilewire2));
			mTileDirty.set(tileIndex1, true);
		}

void iupDrawArc(IdrawCanvas* dc, int x1, int y1, int x2, int y2, double a1, double a2, unsigned char r, unsigned char g, unsigned char b, int style)
{
  int XStartArc = winDrawCalcArc(x1, x2, a1, 1);
  int XEndArc = winDrawCalcArc(x1, x2, a2, 0);
  int YStartArc = winDrawCalcArc(y1, y2, a1, 1);
  int YEndArc = winDrawCalcArc(y1, y2, a2, 0);

  if (style==IUP_DRAW_FILL)
  {
    HBRUSH hBrush = CreateSolidBrush(RGB(r,g,b));
    HPEN hBrushOld = SelectObject(dc->hBitmapDC, hBrush); 
    BeginPath(dc->hBitmapDC); 
    Pie(dc->hBitmapDC, x1, y1, x2+1, y2+1, XStartArc, YStartArc, XEndArc, YEndArc);
    EndPath(dc->hBitmapDC);
    FillPath(dc->hBitmapDC);
    SelectObject(dc->hBitmapDC, hBrushOld);
    DeleteObject(hBrush);
  }
  else
  {
    HPEN hPen = CreatePen(style==IUP_DRAW_STROKE_DASH? PS_DASH: PS_SOLID, 1, RGB(r, g, b));
    HPEN hPenOld = SelectObject(dc->hBitmapDC, hPen);
    Arc(dc->hBitmapDC, x1, y1, x2+1, y2+1, XStartArc, YStartArc, XEndArc, YEndArc);
    SelectObject(dc->hBitmapDC, hPenOld);
    DeleteObject(hPen);
  }
}

int GParc (
    Gwidget_t *widget, Gpoint_t gc, Gsize_t gs,
    double ang1, double ang2, Ggattr_t *ap
) {
    PIXpoint_t pc;
    PIXsize_t ps;
    double a1, a2;

    pc = pdrawtopix (widget, gc), ps = sdrawtopix (widget, gs);
    setgattr (widget, ap);
    a1 = ang1 * M_PI / 180, a2 = ang2 * M_PI / 180;
    if (WPU->gattr.fill)
        Chord (
            GC, pc.x - ps.x, pc.y - ps.y, pc.x + ps.x, pc.y + ps.y,
            (int) (cos (a1) * ps.x), (int) (sin (a1) * ps.x),
            (int) (cos (a2) * ps.x), (int) (sin (a2) * ps.x)
        );
    else
        Arc (
            GC, pc.x - ps.x, pc.y - ps.y, pc.x + ps.x, pc.y + ps.y,
            (int) (cos (a1) * ps.x), (int) (sin (a1) * ps.x),
            (int) (cos (a2) * ps.x), (int) (sin (a2) * ps.x)
        );
    return 0;
}

void PLOTTER::sketchOval( const wxPoint& pos, const wxSize& aSize, double orient, int width )
{
    SetCurrentLineWidth( width );
    width = currentPenWidth;
    int radius, deltaxy, cx, cy;
    wxSize size( aSize );

    if( size.x > size.y )
    {
        std::swap( size.x, size.y );
        orient = AddAngles( orient, 900 );
    }

    deltaxy = size.y - size.x;       /* distance between centers of the oval */
    radius   = ( size.x - width ) / 2;
    cx = -radius;
    cy = -deltaxy / 2;
    RotatePoint( &cx, &cy, orient );
    MoveTo( wxPoint( cx + pos.x, cy + pos.y ) );
    cx = -radius;
    cy = deltaxy / 2;
    RotatePoint( &cx, &cy, orient );
    FinishTo( wxPoint( cx + pos.x, cy + pos.y ) );

    cx = radius;
    cy = -deltaxy / 2;
    RotatePoint( &cx, &cy, orient );
    MoveTo( wxPoint( cx + pos.x, cy + pos.y ) );
    cx = radius;
    cy = deltaxy / 2;
    RotatePoint( &cx, &cy, orient );
    FinishTo( wxPoint( cx + pos.x, cy + pos.y ) );

    cx = 0;
    cy = deltaxy / 2;
    RotatePoint( &cx, &cy, orient );
    Arc( wxPoint( cx + pos.x, cy + pos.y ),
         orient + 1800, orient + 3600,
         radius, NO_FILL );
    cx = 0;
    cy = -deltaxy / 2;
    RotatePoint( &cx, &cy, orient );
    Arc( wxPoint( cx + pos.x, cy + pos.y ),
         orient, orient + 1800,
         radius, NO_FILL );
}

/****************************************************************
 * Function finds if the current node is at the root of the tree.
 * If the node's id is found to match its parent, the node is a root 
 * and the function returns the current node. If not, the function 
 * recurses up the tree to find the root and then returns the parent 
 * and all previous arcs.
 *
 * Returns:
 *   Node
**/
Node UnionFind::find(int currentNodeID, vector<Arc>& prevArcs)
{
    Node currentNode = this->nodes[currentNodeID];

    
    if(currentNode.parent == currentNodeID)
    {
        prevArcs.push_back(Arc(currentNodeID, currentNode.parent));
        return currentNode;
    }
    
    else
    {
        prevArcs.push_back(Arc(currentNodeID, currentNode.parent));
        return find(currentNode.parent, prevArcs);
    }
}

// rshapes draws shapes with random colors, strokes, and sizes. 
void rshapes(int width, int height, int n) {
	int i, j, np = 10;
	VGfloat sx, sy, cx, cy, px, py, ex, ey, pox, poy;
	VGfloat polyx[np], polyy[np];
	rseed();
	Start(width, height);
	for (i = 0; i < n; i++) {
		Fill(randcolor(), randcolor(), randcolor(), drand48());
		Ellipse(randf(width), randf(height), randf(200), randf(100));
		Circle(randf(width), randf(height), randf(100));
		Rect(randf(width), randf(height), randf(200), randf(100));
		Arc(randf(width), randf(height), randf(200), randf(200), randf(360), randf(360));

		sx = randf(width);
		sy = randf(height);
		Stroke(randcolor(), randcolor(), randcolor(), 1);
		StrokeWidth(randf(5));
		Line(sx, sy, sx + randf(200), sy + randf(100));
		StrokeWidth(0);

		sx = randf(width);
		sy = randf(height);
		ex = sx + randf(200);
		ey = sy;
		cx = sx + ((ex - sx) / 2.0);
		cy = sy + randf(100);
		Qbezier(sx, sy, cx, cy, ex, ey);

		sx = randf(width);
		sy = randf(height);
		ex = sx + randf(200);
		ey = sy;
		cx = sx + ((ex - sx) / 2.0);
		cy = sy + randf(100);
		px = cx;
		py = sy - randf(100);
		Cbezier(sx, sy, cx, cy, px, py, ex, ey);

		pox = randf(width);
		poy = randf(height);
		for (j = 0; j < np; j++) {
			polyx[j] = pox + randf(200);
			polyy[j] = poy + randf(100);
		}
		Polygon(polyx, polyy, np);

		pox = randf(width);
		poy = randf(height);
		for (j = 0; j < np; j++) {
			polyx[j] = pox + randf(200);
			polyy[j] = poy + randf(100);
		}
		Polyline(polyx, polyy, np);
	}
	Fill(128, 0, 0, 1);
	Text(20, 20, "OpenVG on the Raspberry Pi", 32);
	End();
}

/****************************************************************
 * Function to add arcs by calling isArcUnique and testing. If 
 * isArcUnique returns true then function is added to the vector. 
 * If the arc is not unique, it is ignored implicitly.
 *
 * Returns:
 *   none
**/
void UnionFind::addArc(const int a, const int b)
{
    std::vector<Arc>::iterator it;
    Arc arcToAdd = Arc(a, b);

    if( this->isArcUnique(arcToAdd) ) {
        this->arcs.push_back(arcToAdd);
    }
}

void arc(int x, int y, int start_angle, int end_angle, int radius)
{
    ac.x = x;
    ac.y = y;
    ac.xstart = x + int(radius*cos(start_angle*pi/180.0));
    ac.ystart = y - int(radius*sin(start_angle*pi/180.0));
    ac.xend = x + int(radius*cos(end_angle*pi/180.0));
    ac.yend = y - int(radius*sin(end_angle*pi/180.0));

    if (bgiemu_handle_redraw || visual_page != active_page) { 
        Arc(hdc[1], x-radius, y-radius, x+radius, y+radius, 
	ac.xstart, ac.ystart, ac.xend, ac.yend);
    }
    if (visual_page == active_page) { 
	Arc(hdc[0], x-radius, y-radius, x+radius, y+radius, 
	    ac.xstart, ac.ystart, ac.xend, ac.yend);
    }
}

int FacilityLocation::createConsAssignment()
{
	int numCons = 0;
	VariableHash::iterator vit;
	Row::ROWSENSE sense = Row::EQUAL;
	int maxnnz = (g->nVertices - g->nTerminals) + 1;
	double rhs = 1.0;

	for (int i = 1; i <= g->nVertices; ++i)
	{
		Vertex client = g->vertices[i];

		if (!client.isTerminal())
			continue;

		Constraint c(maxnnz, sense, rhs);
		c.setType(Constraint::C_ASSIGNMENT);
		c.setNode(client);

		Variable x;
		x.setType(Variable::V_X);

		for (int j = 1; j <= g->nVertices; ++j)
		{
			Vertex router = g->vertices[j];

			// @annotation: comment next filter to resolve instances where
			// the vpn terminals may be considered internal nodes
			// 20160125
			if (client == router || router.isTerminal())
				continue;

			x.setArc(Arc(router, client, 0.));

			vit = vHash[Variable::V_X].find(x);
			if (vit != vHash[Variable::V_X].end())
			{
				int colVarX = vit->second;
				c.rowAddVar(colVarX, 1.0);
			}
		}

		if (c.getRowNnz() > 0)
		{
			bool isInserted = addRow(&c);

			if (isInserted)
			{
				c.setRowIdx(getNRows() - 1);
				cHash[c] = c.getRowIdx();
				numCons++;
			}
		}
	}

	return numCons;
}