using System;
using System.Collections.Generic;
namespace FastReport.Export
{
///
/// Binary tree class
///
internal class BinaryTree
{
#region Private variables and constants
// Acceptable disbalance in branches.
const int DISBALANCE = 3;
private int count;
private int index;
private BinaryTreeNode root;
private BinaryTreeNode[] nodes;
private float inaccuracy;
private float maxDistance;
private float prevValue;
#endregion
#region Public properties
///
/// Maximal value between child and parent
///
public float MaxDistance
{
get { return maxDistance; }
set { maxDistance = value; }
}
///
/// Nodes count
///
public int Count
{
get { return count; }
}
///
/// Root node
///
public BinaryTreeNode RootNode
{
get { return root; }
}
///
/// Nodes array. Accending sorting by node value. Available after close of tree.
///
public BinaryTreeNode[] Nodes
{
get { return nodes; }
}
///
/// Acceptable inaccuracy of new values.
///
public float Inaccuracy
{
get { return inaccuracy; }
set { inaccuracy = value; }
}
#endregion
#region Private methods
///
/// Recursive add value to a node.
///
///
///
///
private int AddChild(ref BinaryTreeNode node, float value)
{
if (node == null)
{
node = new BinaryTreeNode(value);
count++;
}
else
{
float diff = value - node.value;
if (diff < -inaccuracy)
if (node.left == null)
{
node.left = new BinaryTreeNode(value);
node.leftCount = 1;
count++;
}
else
{
node.leftCount = AddChild(ref node.left, value);
if (node.leftCount > node.rightCount + DISBALANCE)
PollLeft(ref node);
}
else if (diff > inaccuracy)
if (node.right == null)
{
node.right = new BinaryTreeNode(value);
node.rightCount = 1;
count++;
}
else
{
node.rightCount = AddChild(ref node.right, value);
if (node.leftCount + DISBALANCE < node.rightCount)
PollRight(ref node);
}
}
return node.leftCount + node.rightCount + 1;
}
///
/// Poll right child node for correct balance.
///
///
private void PollRight(ref BinaryTreeNode node)
{
BinaryTreeNode top = node.right;
BinaryTreeNode rightLeft = top.left;
top.left = node;
node.right = rightLeft;
node.rightCount = (node.right == null) ? 0 : node.right.leftCount + node.right.rightCount + 1;
top.leftCount = node.leftCount + node.rightCount + 1;
node = top;
}
///
/// Poll left child for correct balance.
///
///
private void PollLeft(ref BinaryTreeNode node)
{
BinaryTreeNode top = node.left;
BinaryTreeNode leftRight = top.right;
top.right = node;
node.left = leftRight;
node.leftCount = (node.left == null) ? 0 : node.left.leftCount + node.left.rightCount + 1;
top.rightCount = node.leftCount + node.rightCount + 1;
node = top;
}
///
/// Recursive indexation of node and childs.
///
///
private void Index(BinaryTreeNode node)
{
if (node.left != null)
Index(node.left);
if (maxDistance > 0 && index > 0 && node.value - prevValue > maxDistance + inaccuracy)
{
float value = prevValue;
while (value < node.value - maxDistance)
{
value += maxDistance;
AddChild(ref root, value);
}
prevValue = node.value;
}
else if (index < nodes.Length)
{
node.index = index;
nodes[index++] = node;
prevValue = node.value;
}
if (node.right != null)
Index(node.right);
}
#endregion
#region Public methods
///
/// Add new value in tree. All equals are skipped.
///
///
public void Add(float value)
{
AddChild(ref root, value);
}
///
/// Close the tree and make index array.
///
public void Close()
{
int oldCount = 0;
while (oldCount != count)
{
nodes = new BinaryTreeNode[count];
index = 0;
oldCount = count;
Index(root);
}
}
///
/// Seek of value index in the tree.
///
///
///
public int IndexOf(float value)
{
return Find(root, value);
}
///
/// Find of value index in sub-tree of node.
///
///
///
///
public int Find(BinaryTreeNode node, float value)
{
if (node == null)
return -1;
if (Math.Abs(value - node.value) <= inaccuracy)
return node.index;
else if (value < node.value)
return Find(node.left, value);
else
return Find(node.right, value);
}
///
/// Borrow values form List in the tree
///
///
public void FromList(List array)
{
foreach (float value in array)
AddChild(ref root, value);
}
///
/// Borrow values form array in the tree
///
///
public void FromArray(float[] array)
{
foreach (float value in array)
AddChild(ref root, value);
}
///
/// Clear tree
///
public void Clear()
{
count = 0;
root = null;
nodes = null;
}
#endregion
///
/// Tree constructor
///
public BinaryTree()
{
Clear();
}
}
///
/// Tree node class
///
internal class BinaryTreeNode
{
///
/// Link to left child
///
public BinaryTreeNode left;
///
/// Link to right child
///
public BinaryTreeNode right;
///
/// Node value
///
public float value;
///
/// Count of nodes in left sub-tree
///
public int leftCount;
///
/// Count of nodes in right sub-tree
///
public int rightCount;
///
/// Node index
///
public int index;
///
/// Node constructor
///
///
public BinaryTreeNode(float nodeValue)
{
value = nodeValue;
index = -1;
}
}
}