/* ----------------------------------------------------------------------
 * moves all names of an element to a new position
 */
static void *
MoveElementName (ElementTypePtr Element)
{
  if (PCB->ElementOn && (FRONT (Element) || PCB->InvisibleObjectsOn))
    {
      EraseElementName (Element);
      ELEMENTTEXT_LOOP (Element);
      {
	if (PCB->Data->name_tree[n])
	  r_delete_entry (PCB->Data->name_tree[n], (BoxType *)text);
	MOVE_TEXT_LOWLEVEL (text, DeltaX, DeltaY);
	if (PCB->Data->name_tree[n])
	  r_insert_entry (PCB->Data->name_tree[n], (BoxType *)text, 0);
      }
      END_LOOP;
      DrawElementName (Element);
      Draw ();
    }
  else
    {
      ELEMENTTEXT_LOOP (Element);
      {
	if (PCB->Data->name_tree[n])
	  r_delete_entry (PCB->Data->name_tree[n], (BoxType *)text);
	MOVE_TEXT_LOWLEVEL (text, DeltaX, DeltaY);
	if (PCB->Data->name_tree[n])
	  r_insert_entry (PCB->Data->name_tree[n], (BoxType *)text, 0);
      }
      END_LOOP;
    }
  return (Element);
}

/* ---------------------------------------------------------------------------
 * rotates the contents of the pastebuffer
 */
void
RotateBuffer (BufferType *Buffer, BYTE Number)
{
  /* rotate vias */
  VIA_LOOP (Buffer->Data);
  {
    r_delete_entry (Buffer->Data->via_tree, (BoxType *)via);
    ROTATE_VIA_LOWLEVEL (via, Buffer->X, Buffer->Y, Number);
    SetPinBoundingBox (via);
    r_insert_entry (Buffer->Data->via_tree, (BoxType *)via, 0);
  }
  END_LOOP;

  /* elements */
  ELEMENT_LOOP (Buffer->Data);
  {
    RotateElementLowLevel (Buffer->Data, element, Buffer->X, Buffer->Y,
			   Number);
  }
  END_LOOP;

  /* all layer related objects */
  ALLLINE_LOOP (Buffer->Data);
  {
    r_delete_entry (layer->line_tree, (BoxType *)line);
    RotateLineLowLevel (line, Buffer->X, Buffer->Y, Number);
    r_insert_entry (layer->line_tree, (BoxType *)line, 0);
  }
  ENDALL_LOOP;
  ALLARC_LOOP (Buffer->Data);
  {
    r_delete_entry (layer->arc_tree, (BoxType *)arc);
    RotateArcLowLevel (arc, Buffer->X, Buffer->Y, Number);
    r_insert_entry (layer->arc_tree, (BoxType *)arc, 0);
  }
  ENDALL_LOOP;
  ALLTEXT_LOOP (Buffer->Data);
  {
    r_delete_entry (layer->text_tree, (BoxType *)text);
    RotateTextLowLevel (text, Buffer->X, Buffer->Y, Number);
    r_insert_entry (layer->text_tree, (BoxType *)text, 0);
  }
  ENDALL_LOOP;
  ALLPOLYGON_LOOP (Buffer->Data);
  {
    r_delete_entry (layer->polygon_tree, (BoxType *)polygon);
    RotatePolygonLowLevel (polygon, Buffer->X, Buffer->Y, Number);
    r_insert_entry (layer->polygon_tree, (BoxType *)polygon, 0);
  }
  ENDALL_LOOP;

  /* finally the origin and the bounding box */
  ROTATE (Buffer->X, Buffer->Y, Buffer->X, Buffer->Y, Number);
  RotateBoxLowLevel (&Buffer->BoundingBox, Buffer->X, Buffer->Y, Number);
  SetCrosshairRangeToBuffer ();
}

/* ---------------------------------------------------------------------------
 * get next slot for an element, allocates memory if necessary
 */
ElementTypePtr
GetElementMemory (DataTypePtr Data)
{
  ElementTypePtr element = Data->Element;
  int i;

  /* realloc new memory if necessary and clear it */
  if (Data->ElementN >= Data->ElementMax)
    {
      Data->ElementMax += STEP_ELEMENT;
      if (Data->element_tree)
	r_destroy_tree (&Data->element_tree);
      element = MyRealloc (element, Data->ElementMax * sizeof (ElementType),
			   "GetElementMemory()");
      Data->Element = element;
      memset (element + Data->ElementN, 0,
	      STEP_ELEMENT * sizeof (ElementType));
      Data->element_tree = r_create_tree (NULL, 0, 0);
      for (i = 0; i < MAX_ELEMENTNAMES; i++)
	{
	  if (Data->name_tree[i])
	    r_destroy_tree (&Data->name_tree[i]);
	  Data->name_tree[i] = r_create_tree (NULL, 0, 0);
	}

      ELEMENT_LOOP (Data);
      {
	r_insert_entry (Data->element_tree, (BoxType *) element, 0);
	PIN_LOOP (element);
	{
	  pin->Element = element;
	}
	END_LOOP;
	PAD_LOOP (element);
	{
	  pad->Element = element;
	}
	END_LOOP;
	ELEMENTTEXT_LOOP (element);
	{
	  text->Element = element;
	  r_insert_entry (Data->name_tree[n], (BoxType *) text, 0);
	}
	END_LOOP;
      }
      END_LOOP;
    }
  return (element + Data->ElementN++);
}

/* ---------------------------------------------------------------------------
 * get next slot for a line, allocates memory if necessary
 */
LineTypePtr
GetLineMemory (LayerTypePtr Layer)
{
  LineTypePtr line = Layer->Line;

  /* realloc new memory if necessary and clear it */
  if (Layer->LineN >= Layer->LineMax)
    {
      Layer->LineMax += STEP_LINE;
      /* all of the pointers move, so rebuild the whole tree */
      if (Layer->line_tree)
	r_destroy_tree (&Layer->line_tree);
      line = MyRealloc (line, Layer->LineMax * sizeof (LineType),
			"GetLineMemory()");
      Layer->Line = line;
      memset (line + Layer->LineN, 0, STEP_LINE * sizeof (LineType));
      Layer->line_tree = r_create_tree (NULL, 0, 0);
      LINE_LOOP (Layer);
      {
	r_insert_entry (Layer->line_tree, (BoxTypePtr) line, 0);
      }
      END_LOOP;
    }
  return (line + Layer->LineN++);
}

/* ---------------------------------------------------------------------------
 * get next slot for a Rat, allocates memory if necessary
 */
RatTypePtr
GetRatMemory (DataTypePtr Data)
{
  RatTypePtr rat = Data->Rat;

  /* realloc new memory if necessary and clear it */
  if (Data->RatN >= Data->RatMax)
    {
      Data->RatMax += STEP_RAT;
      /* all of the pointers move, so rebuild the whole tree */
      if (Data->rat_tree)
        r_destroy_tree (&Data->rat_tree);
      rat = MyRealloc (rat, Data->RatMax * sizeof (RatType),
		       "GetRatMemory()");
      Data->Rat = rat;
      memset (rat + Data->RatN, 0, STEP_RAT * sizeof (RatType));
      Data->rat_tree = r_create_tree (NULL, 0, 0);
      RAT_LOOP (Data);
      {
        r_insert_entry (Data->rat_tree, (BoxTypePtr) line, 0);
      }
      END_LOOP;
    }
  return (rat + Data->RatN++);
}

/* ---------------------------------------------------------------------------
 * get next slot for a pad, allocates memory if necessary
 */
PadTypePtr
GetPadMemory (ElementTypePtr Element)
{
  PadTypePtr pad = Element->Pad;
  bool onBoard = false;

  /* realloc new memory if necessary and clear it */
  if (Element->PadN >= Element->PadMax)
    {
      if (PCB->Data->pad_tree)
	{
	  PAD_LOOP (Element);
	  {
	    if (r_delete_entry (PCB->Data->pad_tree, (BoxType *) pad))
	      onBoard = true;
	  }
	  END_LOOP;
	}
      Element->PadMax += STEP_PAD;
      pad = MyRealloc (pad, Element->PadMax * sizeof (PadType),
		       "GetPadMemory()");
      Element->Pad = pad;
      memset (pad + Element->PadN, 0, STEP_PAD * sizeof (PadType));
      if (onBoard)
	{
	  PAD_LOOP (Element);
	  {
	    r_insert_entry (PCB->Data->pad_tree, (BoxType *) pad, 0);
	  }
	  END_LOOP;
	}
    }
  return (pad + Element->PadN++);
}

/* ---------------------------------------------------------------------------
 * get next slot for a pin, allocates memory if necessary
 */
PinTypePtr
GetPinMemory (ElementTypePtr Element)
{
  PinTypePtr pin = Element->Pin;
  bool onBoard = false;

  /* realloc new memory if necessary and clear it */
  if (Element->PinN >= Element->PinMax)
    {
      if (PCB->Data->pin_tree)
	{
	  PIN_LOOP (Element);
	  {
	    if (r_delete_entry (PCB->Data->pin_tree, (BoxType *) pin))
	      onBoard = true;
	  }
	  END_LOOP;
	}
      Element->PinMax += STEP_PIN;
      pin = MyRealloc (pin, Element->PinMax * sizeof (PinType),
		       "GetPinMemory()");
      Element->Pin = pin;
      memset (pin + Element->PinN, 0, STEP_PIN * sizeof (PinType));
      if (onBoard)
	{
	  PIN_LOOP (Element);
	  {
	    r_insert_entry (PCB->Data->pin_tree, (BoxType *) pin, 0);
	  }
	  END_LOOP;
	}
    }
  return (pin + Element->PinN++);
}

/* ---------------------------------------------------------------------------
 * get next slot for a polygon object, allocates memory if necessary
 */
PolygonTypePtr
GetPolygonMemory (LayerTypePtr Layer)
{
  PolygonTypePtr polygon = Layer->Polygon;

  /* realloc new memory if necessary and clear it */
  if (Layer->PolygonN >= Layer->PolygonMax)
    {
      Layer->PolygonMax += STEP_POLYGON;
      if (Layer->polygon_tree)
	r_destroy_tree (&Layer->polygon_tree);
      polygon = MyRealloc (polygon, Layer->PolygonMax * sizeof (PolygonType),
			   "GetPolygonMemory()");
      Layer->Polygon = polygon;
      memset (polygon + Layer->PolygonN, 0,
	      STEP_POLYGON * sizeof (PolygonType));
      Layer->polygon_tree = r_create_tree (NULL, 0, 0);
      POLYGON_LOOP (Layer);
      {
	r_insert_entry (Layer->polygon_tree, (BoxType *) polygon, 0);
      }
      END_LOOP;
    }
  return (polygon + Layer->PolygonN++);
}

/* ---------------------------------------------------------------------------
 * moves a text object between layers; lowlevel routines
 */
static void *
MoveTextToLayerLowLevel (LayerType *Source, TextType *text,
			 LayerType *Destination)
{
  RestoreToPolygon (PCB->Data, TEXT_TYPE, Source, text);
  r_delete_entry (Source->text_tree, (BoxType *)text);

  Source->Text = g_list_remove (Source->Text, text);
  Source->TextN --;
  Destination->Text = g_list_append (Destination->Text, text);
  Destination->TextN ++;

  if (GetLayerGroupNumberByNumber (solder_silk_layer) ==
      GetLayerGroupNumberByPointer (Destination))
    SET_FLAG (ONSOLDERFLAG, text);
  else
    CLEAR_FLAG (ONSOLDERFLAG, text);

  /* re-calculate the bounding box (it could be mirrored now) */
  SetTextBoundingBox (&PCB->Font, text);
  if (!Destination->text_tree)
    Destination->text_tree = r_create_tree (NULL, 0, 0);
  r_insert_entry (Destination->text_tree, (BoxType *)text, 0);
  ClearFromPolygon (PCB->Data, TEXT_TYPE, Destination, text);

  return text;
}

/* add a space-filler to the empty space representation.  */
void
mtspace_add (mtspace_t * mtspace, const BoxType * box, mtspace_type_t which,
	     Coord keepaway)
{
  mtspacebox_t *filler = mtspace_create_box (box, keepaway);
  r_insert_entry (which_tree (mtspace, which), (const BoxType *) filler, 1);
}

/* ---------------------------------------------------------------------------
 * inserts a point into a line
 */
static void *
InsertPointIntoLine (LayerTypePtr Layer, LineTypePtr Line)
{
  LineTypePtr line;
  LocationType X, Y;

  if (((Line->Point1.X == InsertX) && (Line->Point1.Y == InsertY)) ||
      ((Line->Point2.X == InsertX) && (Line->Point2.Y == InsertY)))
    return (NULL);
  X = Line->Point2.X;
  Y = Line->Point2.Y;
  AddObjectToMoveUndoList (LINEPOINT_TYPE, Layer, Line, &Line->Point2,
			   InsertX - X, InsertY - Y);
  EraseLine (Line);
  r_delete_entry (Layer->line_tree, (BoxTypePtr) Line);
  Line->Point2.X = InsertX;
  Line->Point2.Y = InsertY;
  SetLineBoundingBox (Line);
  r_insert_entry (Layer->line_tree, (BoxTypePtr) Line, 0);
  DrawLine (Layer, Line, 0);
  /* we must create after playing with Line since creation may
   * invalidate the line pointer
   */
  if ((line = CreateDrawnLineOnLayer (Layer, InsertX, InsertY,
				      X, Y,
				      Line->Thickness, Line->Clearance,
				      Line->Flags)))
    {
      AddObjectToCreateUndoList (LINE_TYPE, Layer, line, line);
      DrawLine (Layer, line, 0);
      /* creation call adds it to the rtree */
    }
  Draw ();
  return (line);
}

/* ---------------------------------------------------------------------------
 * creates a new rat-line
 */
RatTypePtr
CreateNewRat (DataTypePtr Data, LocationType X1, LocationType Y1,
	      LocationType X2, LocationType Y2, Cardinal group1,
	      Cardinal group2, BDimension Thickness, FlagType Flags)
{
  RatTypePtr Line = GetRatMemory (Data);

  if (!Line)
    return (Line);

  Line->ID = ID++;
  Line->Flags = Flags;
  SET_FLAG (RATFLAG, Line);
  Line->Thickness = Thickness;
  Line->Point1.X = X1;
  Line->Point1.Y = Y1;
  Line->Point1.ID = ID++;
  Line->Point2.X = X2;
  Line->Point2.Y = Y2;
  Line->Point2.ID = ID++;
  Line->group1 = group1;
  Line->group2 = group2;
  SetLineBoundingBox ((LineTypePtr) Line);
  if (!Data->rat_tree)
    Data->rat_tree = r_create_tree (NULL, 0, 0);
  r_insert_entry (Data->rat_tree, &Line->BoundingBox, 0);
  return (Line);
}

/*!
 * \brief Create an r-tree from an unsorted list of boxes.
 *
 * Create an rtree from the list of boxes.  If 'manage' is true, then
 * the tree will take ownership of 'boxlist' and free it when the tree
 * is destroyed.
 *
 * The r-tree will keep pointers into it, so don't free the box list
 * until you've called r_destroy_tree.
 *
 * If you set 'manage' to true, r_destroy_tree will free your boxlist.
 */
rtree_t *
r_create_tree (const BoxType * boxlist[], int N, int manage)
{
  rtree_t *rtree;
  struct rtree_node *node;
  int i;

  assert (N >= 0);
  rtree = (rtree_t *)calloc (1, sizeof (*rtree));
  /* start with a single empty leaf node */
  node = (struct rtree_node *)calloc (1, sizeof (*node));
  node->flags.is_leaf = 1;
  node->parent = NULL;
  rtree->root = node;
  /* simple, just insert all of the boxes! */
  for (i = 0; i < N; i++)
    {
      assert (boxlist[i]);
      r_insert_entry (rtree, boxlist[i], manage);
    }
#ifdef SLOW_ASSERTS
  assert (__r_tree_is_good (rtree->root));
#endif
  return rtree;
}

LineTypePtr
CreateNewLineOnLayer (LayerTypePtr Layer,
		      LocationType X1, LocationType Y1,
		      LocationType X2, LocationType Y2,
		      BDimension Thickness, BDimension Clearance,
		      FlagType Flags)
{
  LineTypePtr Line;

  Line = GetLineMemory (Layer);
  if (!Line)
    return (Line);
  Line->ID = ID++;
  Line->Flags = Flags;
  CLEAR_FLAG (RATFLAG, Line);
  Line->Thickness = Thickness;
  Line->Clearance = Clearance;
  Line->Point1.X = X1;
  Line->Point1.Y = Y1;
  Line->Point1.ID = ID++;
  Line->Point2.X = X2;
  Line->Point2.Y = Y2;
  Line->Point2.ID = ID++;
  SetLineBoundingBox (Line);
  if (!Layer->line_tree)
    Layer->line_tree = r_create_tree (NULL, 0, 0);
  r_insert_entry (Layer->line_tree, (BoxTypePtr) Line, 0);
  return (Line);
}

/* ---------------------------------------------------------------------------
 * creates a new text on a layer
 */
TextTypePtr
CreateNewText (LayerTypePtr Layer, FontTypePtr PCBFont,
	       LocationType X, LocationType Y,
	       BYTE Direction, int Scale, char *TextString, FlagType Flags)
{
  TextType *text;

  if (TextString == NULL)
    return NULL;

  text = GetTextMemory (Layer);
  if (text == NULL)
    return NULL;

  /* copy values, width and height are set by drawing routine
   * because at this point we don't know which symbols are available
   */
  text->X = X;
  text->Y = Y;
  text->Direction = Direction;
  text->Flags = Flags;
  text->Scale = Scale;
  text->TextString = strdup (TextString);

  /* calculate size of the bounding box */
  SetTextBoundingBox (PCBFont, text);
  text->ID = ID++;
  if (!Layer->text_tree)
    Layer->text_tree = r_create_tree (NULL, 0, 0);
  r_insert_entry (Layer->text_tree, (BoxTypePtr) text, 0);
  return (text);
}

static void *
MyMoveTextLowLevel (LayerType *Layer, TextType *Text, Coord dx, Coord dy)
{
  if (Layer)
    r_delete_entry (Layer->text_tree, (BoxType *) Text);
  MOVE_TEXT_LOWLEVEL (Text, dx, dy);
  if (Layer)
    r_insert_entry (Layer->text_tree, (BoxType *) Text, 0);
  return Text;
}

/* ---------------------------------------------------------------------------
 * removes a polygon-point from a polygon
 */
static void *
RemovePolygonPoint (LayerTypePtr Layer,
		    PolygonTypePtr Polygon, PointTypePtr Point)
{
  Cardinal point_idx;
  Cardinal i;
  Cardinal contour;
  Cardinal contour_start, contour_end, contour_points;

  point_idx = polygon_point_idx (Polygon, Point);
  contour = polygon_point_contour (Polygon, point_idx);
  contour_start = (contour == 0) ? 0 : Polygon->HoleIndex[contour - 1];
  contour_end = (contour == Polygon->HoleIndexN) ? Polygon->PointN :
                                                   Polygon->HoleIndex[contour];
  contour_points = contour_end - contour_start;

  if (contour_points <= 3)
    return RemovePolygonContour (Layer, Polygon, contour);

  if (Layer->On)
    ErasePolygon (Polygon);

  /* insert the polygon-point into the undo list */
  AddObjectToRemovePointUndoList (POLYGONPOINT_TYPE, Layer, Polygon, point_idx);
  r_delete_entry (Layer->polygon_tree, (BoxType *) Polygon);

  /* remove point from list, keep point order */
  for (i = point_idx; i < Polygon->PointN - 1; i++)
    Polygon->Points[i] = Polygon->Points[i + 1];
  Polygon->PointN--;

  /* Shift down indices of any holes */
  for (i = 0; i < Polygon->HoleIndexN; i++)
    if (Polygon->HoleIndex[i] > point_idx)
      Polygon->HoleIndex[i]--;

  SetPolygonBoundingBox (Polygon);
  r_insert_entry (Layer->polygon_tree, (BoxType *) Polygon, 0);
  RemoveExcessPolygonPoints (Layer, Polygon);
  InitClip (PCB->Data, Layer, Polygon);

  /* redraw polygon if necessary */
  if (Layer->On)
    {
      DrawPolygon (Layer, Polygon);
      if (!Bulk)
	Draw ();
    }
  return NULL;
}

/* ---------------------------------------------------------------------------
 * moves one end of a line
 */
static void *
MoveLinePoint (LayerTypePtr Layer, LineTypePtr Line, PointTypePtr Point)
{
  if (Layer)
    {
      if (Layer->On)
	EraseLine (Line);
      RestoreToPolygon (PCB->Data, LINE_TYPE, Layer, Line);
      r_delete_entry (Layer->line_tree, &Line->BoundingBox);
      MOVE (Point->X, Point->Y, DeltaX, DeltaY);
      SetLineBoundingBox (Line);
      r_insert_entry (Layer->line_tree, &Line->BoundingBox, 0);
      ClearFromPolygon (PCB->Data, LINE_TYPE, Layer, Line);
      if (Layer->On)
	{
	  DrawLine (Layer, Line);
	  Draw ();
	}
      return (Line);
    }
  else				/* must be a rat */
    {
      if (PCB->RatOn)
	EraseRat ((RatTypePtr) Line);
      r_delete_entry (PCB->Data->rat_tree, &Line->BoundingBox);
      MOVE (Point->X, Point->Y, DeltaX, DeltaY);
      SetLineBoundingBox (Line);
      r_insert_entry (PCB->Data->rat_tree, &Line->BoundingBox, 0);
      if (PCB->RatOn)
	{
	  DrawRat ((RatTypePtr) Line);
	  Draw ();
	}
      return (Line);
    }
}

/* ---------------------------------------------------------------------------
 * inserts a point into a polygon
 */
static void *
InsertPointIntoPolygon (LayerTypePtr Layer, PolygonTypePtr Polygon)
{
  PointType save;
  Cardinal n;
  LineType line;

  if (!Forcible)
    {
      /*
       * first make sure adding the point is sensible
       */
      line.Thickness = 0;
      line.Point1 = Polygon->Points[prev_contour_point (Polygon, InsertAt)];
      line.Point2 = Polygon->Points[InsertAt];
      if (IsPointOnLine ((float) InsertX, (float) InsertY, 0.0, &line))
	return (NULL);
    }
  /*
   * second, shift the points up to make room for the new point
   */
  ErasePolygon (Polygon);
  r_delete_entry (Layer->polygon_tree, (BoxTypePtr) Polygon);
  save = *CreateNewPointInPolygon (Polygon, InsertX, InsertY);
  for (n = Polygon->PointN - 1; n > InsertAt; n--)
    Polygon->Points[n] = Polygon->Points[n - 1];

  /* Shift up indices of any holes */
  for (n = 0; n < Polygon->HoleIndexN; n++)
    if (Polygon->HoleIndex[n] > InsertAt ||
	(InsertLast && Polygon->HoleIndex[n] == InsertAt))
      Polygon->HoleIndex[n]++;

  Polygon->Points[InsertAt] = save;
  SetChangedFlag (true);
  AddObjectToInsertPointUndoList (POLYGONPOINT_TYPE, Layer, Polygon,
				  &Polygon->Points[InsertAt]);

  SetPolygonBoundingBox (Polygon);
  r_insert_entry (Layer->polygon_tree, (BoxType *) Polygon, 0);
  InitClip (PCB->Data, Layer, Polygon);
  if (Forcible || !RemoveExcessPolygonPoints (Layer, Polygon))
    {
      DrawPolygon (Layer, Polygon, 0);
      Draw ();
    }
  return (&Polygon->Points[InsertAt]);
}

/* ---------------------------------------------------------------------------
 * moves a line between layers; lowlevel routines
 */
static void *
MoveLineToLayerLowLevel (LayerType *Source, LineType *line,
			 LayerType *Destination)
{
  r_delete_entry (Source->line_tree, (BoxType *)line);

  Source->Line = g_list_remove (Source->Line, line);
  Source->LineN --;
  Destination->Line = g_list_append (Destination->Line, line);
  Destination->LineN ++;

  if (!Destination->line_tree)
    Destination->line_tree = r_create_tree (NULL, 0, 0);
  r_insert_entry (Destination->line_tree, (BoxType *)line, 0);
  return line;
}