Terraria v1.4.4.9
Terraria source code documentation
Loading...
Searching...
No Matches

◆ RBInsert()

int System.Data.RBTree< K >.RBInsert ( int root_id,
int x_id,
int mainTreeNodeID,
int position,
bool append )
inlineprivate

Definition at line 542 of file RBTree.cs.

543 {
544 _version++;
545 int num = 0;
546 int num2 = ((root_id == 0) ? root : root_id);
547 if (_accessMethod == TreeAccessMethod.KEY_SEARCH_AND_INDEX && !append)
548 {
549 while (num2 != 0)
550 {
551 IncreaseSize(num2);
552 num = num2;
553 int num3 = ((root_id == 0) ? CompareNode(Key(x_id), Key(num2)) : CompareSateliteTreeNode(Key(x_id), Key(num2)));
554 if (num3 < 0)
555 {
556 num2 = Left(num2);
557 continue;
558 }
559 if (num3 > 0)
560 {
561 num2 = Right(num2);
562 continue;
563 }
564 if (root_id != 0)
565 {
566 throw ExceptionBuilder.InternalRBTreeError(RBTreeError.InvalidStateinInsert);
567 }
568 if (Next(num2) != 0)
569 {
570 root_id = RBInsert(Next(num2), x_id, num2, -1, append: false);
571 SetKey(num2, Key(Next(num2)));
572 }
573 else
574 {
575 int num4 = 0;
576 num4 = GetNewNode(Key(num2));
577 _inUseSatelliteTreeCount++;
578 SetNext(num4, num2);
579 SetColor(num4, color(num2));
580 SetParent(num4, Parent(num2));
581 SetLeft(num4, Left(num2));
582 SetRight(num4, Right(num2));
583 if (Left(Parent(num2)) == num2)
584 {
585 SetLeft(Parent(num2), num4);
586 }
587 else if (Right(Parent(num2)) == num2)
588 {
589 SetRight(Parent(num2), num4);
590 }
591 if (Left(num2) != 0)
592 {
593 SetParent(Left(num2), num4);
594 }
595 if (Right(num2) != 0)
596 {
597 SetParent(Right(num2), num4);
598 }
599 if (root == num2)
600 {
601 root = num4;
602 }
603 SetColor(num2, NodeColor.black);
604 SetParent(num2, 0);
605 SetLeft(num2, 0);
606 SetRight(num2, 0);
607 int size = SubTreeSize(num2);
608 SetSubTreeSize(num2, 1);
609 root_id = RBInsert(num2, x_id, num4, -1, append: false);
610 SetSubTreeSize(num4, size);
611 }
612 return root_id;
613 }
614 }
615 else
616 {
617 if (!(_accessMethod == TreeAccessMethod.INDEX_ONLY || append))
618 {
619 throw ExceptionBuilder.InternalRBTreeError(RBTreeError.UnsupportedAccessMethod1);
620 }
621 if (position == -1)
622 {
623 position = SubTreeSize(root);
624 }
625 while (num2 != 0)
626 {
627 IncreaseSize(num2);
628 num = num2;
629 int num5 = position - SubTreeSize(Left(num));
630 if (num5 <= 0)
631 {
632 num2 = Left(num2);
633 continue;
634 }
635 num2 = Right(num2);
636 if (num2 != 0)
637 {
638 position = num5 - 1;
639 }
640 }
641 }
642 SetParent(x_id, num);
643 if (num == 0)
644 {
645 if (root_id == 0)
646 {
647 root = x_id;
648 }
649 else
650 {
651 SetNext(mainTreeNodeID, x_id);
652 SetKey(mainTreeNodeID, Key(x_id));
653 root_id = x_id;
654 }
655 }
656 else
657 {
658 int num6 = 0;
659 if (_accessMethod == TreeAccessMethod.KEY_SEARCH_AND_INDEX)
660 {
661 num6 = ((root_id == 0) ? CompareNode(Key(x_id), Key(num)) : CompareSateliteTreeNode(Key(x_id), Key(num)));
662 }
663 else
664 {
665 if (_accessMethod != TreeAccessMethod.INDEX_ONLY)
666 {
667 throw ExceptionBuilder.InternalRBTreeError(RBTreeError.UnsupportedAccessMethod2);
668 }
669 num6 = ((position > 0) ? 1 : (-1));
670 }
671 if (num6 < 0)
672 {
673 SetLeft(num, x_id);
674 }
675 else
676 {
677 SetRight(num, x_id);
678 }
679 }
680 SetLeft(x_id, 0);
681 SetRight(x_id, 0);
682 SetColor(x_id, NodeColor.red);
683 num2 = x_id;
684 while (color(Parent(x_id)) == NodeColor.red)
685 {
686 if (Parent(x_id) == Left(Parent(Parent(x_id))))
687 {
688 num = Right(Parent(Parent(x_id)));
689 if (color(num) == NodeColor.red)
690 {
691 SetColor(Parent(x_id), NodeColor.black);
692 SetColor(num, NodeColor.black);
693 SetColor(Parent(Parent(x_id)), NodeColor.red);
694 x_id = Parent(Parent(x_id));
695 continue;
696 }
697 if (x_id == Right(Parent(x_id)))
698 {
699 x_id = Parent(x_id);
700 root_id = LeftRotate(root_id, x_id, mainTreeNodeID);
701 }
702 SetColor(Parent(x_id), NodeColor.black);
703 SetColor(Parent(Parent(x_id)), NodeColor.red);
704 root_id = RightRotate(root_id, Parent(Parent(x_id)), mainTreeNodeID);
705 continue;
706 }
707 num = Left(Parent(Parent(x_id)));
708 if (color(num) == NodeColor.red)
709 {
710 SetColor(Parent(x_id), NodeColor.black);
711 SetColor(num, NodeColor.black);
712 SetColor(Parent(Parent(x_id)), NodeColor.red);
713 x_id = Parent(Parent(x_id));
714 continue;
715 }
716 if (x_id == Left(Parent(x_id)))
717 {
718 x_id = Parent(x_id);
719 root_id = RightRotate(root_id, x_id, mainTreeNodeID);
720 }
721 SetColor(Parent(x_id), NodeColor.black);
722 SetColor(Parent(Parent(x_id)), NodeColor.red);
723 root_id = LeftRotate(root_id, Parent(Parent(x_id)), mainTreeNodeID);
724 }
725 if (root_id == 0)
726 {
727 SetColor(root, NodeColor.black);
728 }
729 else
730 {
731 SetColor(root_id, NodeColor.black);
732 }
733 return root_id;
734 }
System.Data.RBTree.Key
K Key(int nodeId)
Definition RBTree.cs:1407
System.Data.RBTree.color
NodeColor color(int nodeId)
Definition RBTree.cs:1392
System.Data.RBTree.SetNext
void SetNext(int nodeId, int nextNodeId)
Definition RBTree.cs:1351
System.Data.RBTree.SetRight
void SetRight(int nodeId, int rightNodeId)
Definition RBTree.cs:1326
System.Data.RBTree.SetColor
void SetColor(int nodeId, NodeColor color)
Definition RBTree.cs:1341
System.Data.RBTree.SubTreeSize
int SubTreeSize(int nodeId)
Definition RBTree.cs:1402
System.Data.RBTree.GetNewNode
int GetNewNode(K key)
Definition RBTree.cs:384
System.Data.RBTree._accessMethod
readonly TreeAccessMethod _accessMethod
Definition RBTree.cs:217
System.Data.RBTree.LeftRotate
int LeftRotate(int root_id, int x_id, int mainTreeNode)
Definition RBTree.cs:456
System.Data.RBTree.SetLeft
void SetLeft(int nodeId, int leftNodeId)
Definition RBTree.cs:1331
System.Data.RBTree._inUseSatelliteTreeCount
int _inUseSatelliteTreeCount
Definition RBTree.cs:215
System.Data.RBTree.IncreaseSize
void IncreaseSize(int nodeId)
Definition RBTree.cs:1361
System.Data.RBTree.RBInsert
int RBInsert(int root_id, int x_id, int mainTreeNodeID, int position, bool append)
Definition RBTree.cs:542
System.Data.RBTree.Next
int Next(int nodeId)
Definition RBTree.cs:1397
System.Data.RBTree.RightRotate
int RightRotate(int root_id, int x_id, int mainTreeNode)
Definition RBTree.cs:499
System.Data.RBTree.CompareSateliteTreeNode
int CompareSateliteTreeNode(K record1, K record2)
System.Data.RBTree.SetParent
void SetParent(int nodeId, int parentNodeId)
Definition RBTree.cs:1336
System.Data.RBTree.SetSubTreeSize
void SetSubTreeSize(int nodeId, int size)
Definition RBTree.cs:1356
System.Data.RBTree.SetKey
void SetKey(int nodeId, K key)
Definition RBTree.cs:1346
System.Data.RBTree.CompareNode
int CompareNode(K record1, K record2)

References System.Data.RBTree< K >._accessMethod, System.Data.RBTree< K >._inUseSatelliteTreeCount, System.Data.RBTree< K >._version, System.Data.RBTree< K >.color(), System.Data.RBTree< K >.CompareNode(), System.Data.RBTree< K >.CompareSateliteTreeNode(), System.Data.RBTree< K >.GetNewNode(), System.Data.RBTree< K >.IncreaseSize(), System.Data.ExceptionBuilder.InternalRBTreeError(), System.Data.RBTree< K >.Key(), System.Collections.Generic.Left, System.Data.RBTree< K >.LeftRotate(), System.Data.RBTree< K >.Next(), System.Data.Parent, System.Data.RBTree< K >.RBInsert(), System.Data.Right, System.Data.RBTree< K >.RightRotate(), System.Data.RBTree< K >.root, System.Data.RBTree< K >.SetColor(), System.Data.RBTree< K >.SetKey(), System.Data.RBTree< K >.SetLeft(), System.Data.RBTree< K >.SetNext(), System.Data.RBTree< K >.SetParent(), System.Data.RBTree< K >.SetRight(), System.Data.RBTree< K >.SetSubTreeSize(), and System.Data.RBTree< K >.SubTreeSize().

Referenced by System.Data.RBTree< K >.Add(), System.Data.RBTree< K >.Insert(), System.Data.RBTree< K >.InsertAt(), and System.Data.RBTree< K >.RBInsert().