BTrees: Difference between revisions

Line 2:

// BTrees in C#

Line 24:

Line 25:

{

Count = 0;

Keys = new T[(int)Limits.Maximum+1];

Keys = new T[(int)Limits.Maximum];

Branch = new Node<T>[(int)Limits.Maximum+1];

Branch = new Node<T>[(int)Limits.Maximum + 1];

}

Line 31:

Line 32:

{

Branch[k - 1].Count++;

Branch[k - 1].Keys[Branch[k - 1].Count] = Keys[k];

Branch[k - 1].Keys[Branch[k - 1].Count - 1] = Keys[k - 1];

Branch[k - 1].Branch[Branch[k - 1].Count] = Branch[k].Branch[0];

Keys[k] = Branch[k].Keys[1];

Keys[k - 1] = Branch[k].Keys[0];

Branch[k].Branch[0] = Branch[k].Branch[1];

Branch[k].Count--;

Line 40:

Line 41:

for (int c = 1; c <= Branch[k].Count; c++)

{

Branch[k].Keys[c] = Branch[k].Keys[c ~~+ 1~~];

Branch[k].Keys[c-1] = Branch[k].Keys[c];

Branch[k].Branch[c] = Branch[k].Branch[c + 1];

}

Line 49:

Line 50:

for (int c = Branch[k].Count; c >= 1; c--)

{

Branch[k].Keys[c ~~+ 1~~] = Branch[k].Keys[c];

Branch[k].Keys[c] = Branch[k].Keys[c-1];

Branch[k].Branch[c + 1] = Branch[k].Branch[c];

}

Line 55:

Line 56:

Branch[k].Branch[1] = Branch[k].Branch[0];

Branch[k].Count++;

Branch[k].Keys[1] = Keys[k];

Branch[k].Keys[0] = Keys[k-1];

Keys[k] = Branch[k - 1].Keys[Branch[k - 1].Count];

Keys[k-1] = Branch[k - 1].Keys[Branch[k - 1].Count-1];

Branch[k].Branch[0] = Branch[k - 1].Branch[Branch[k - 1].Count];

Branch[k - 1].Count--;

Line 67:

Line 68:

Branch[k - 1].Count++;

Branch[k - 1].Keys[Branch[k - 1].Count] = Keys[k];

Branch[k - 1].Keys[Branch[k - 1].Count-1] = Keys[k-1];

Branch[k - 1].Branch[Branch[k - 1].Count] = q.Branch[0];

Line 73:

Line 74:

{

Branch[k - 1].Count++;

Branch[k - 1].Keys[Branch[k - 1].Count] = q.Keys[c];

Branch[k - 1].Keys[Branch[k - 1].Count-1] = q.Keys[c-1];

Branch[k - 1].Branch[Branch[k - 1].Count] = q.Branch[c];

}

Line 79:

Line 80:

for (int c = k; c <= Count - 1; c++)

{

Keys[c] = Keys[c ~~+ 1~~];

Keys[c-1] = Keys[c];

Branch[c] = Branch[c + 1];

}

Line 89:

Line 90:

Node<T> q = Branch[k];

while (q.Branch[0] != null) q = q.Branch[0];

Keys[k] = q.Keys[1];

Keys[k-1] = q.Keys[0];

}

Line 123:

Line 124:

for (int i = k + 1; i <= Count; i++)

{

Keys[i - 1] = Keys[i];

Keys[i - 2] = Keys[i-1];

Branch[i - 1] = Branch[i];

}

Line 170:

Line 171:

bool SearchNode(T Target, Node<T> Root, ref int Position)

{

int iCompare = TComparer.Compare(Target, Root.Keys[1]);

int iCompare = TComparer.Compare(Target, Root.Keys[0]);

if (iCompare < 0)

{

Line 179:

Line 180:

{

Position = Root.Count;

iCompare = TComparer.Compare(Target, Root.Keys[Position]);

iCompare = TComparer.Compare(Target, Root.Keys[Position-1]);

while (iCompare < 0 && Position > 1)

{

Position--;

iCompare = TComparer.Compare(Target, Root.Keys[Position]);

iCompare = TComparer.Compare(Target, Root.Keys[Position-1]);

}

return iCompare == 0;

Line 200:

Line 201:

Node<T> p = new Node<T>();

p.Count = 1;

p.Keys[1] = x;

p.Keys[0] = x;

p.Branch[0] = root;

p.Branch[1] = xr;

Line 244:

Line 245:

for (int i = p.Count; i >= k + 1; i--)

{

p.Keys[i ~~+ 1~~] = p.Keys[i];

p.Keys[i] = p.Keys[i-1];

p.Branch[i + 1] = p.Branch[i];

}

p.Keys[k ~~+ 1~~] = x;

p.Keys[k] = x;

p.Branch[k + 1] = xr;

p.Count++;

Line 260:

Line 261:

for (int i = nnedian + 1; i <= (int)Limits.Maximum; i++)

{

yr.Keys[i - nnedian] = p.Keys[i];

yr.Keys[i - nnedian - 1] = p.Keys[i-1];

yr.Branch[i - nnedian] = p.Branch[i];

}

Line 272:

Line 273:

PushIn(x, xr, ref yr, k - nnedian);

y = p.Keys[p.Count];

y = p.Keys[p.Count-1];

yr.Branch[0] = p.Branch[p.Count];

Line 310:

Line 311:

{

p.Successor(k);

if (!RecDelete(p.Keys[k], p.Branch[k]))

if (!RecDelete(p.Keys[k-1], p.Branch[k]))

throw new EntriNotPhoundEcsception();

}

Line 334:

Line 335:

BTree<string> bTree = new BTree<string>();

for (int i=0; i<(int)Test.Maximum; i++)

for (int i = 0; i < (int)Test.Maximum; i++)

bTree.Add("String" + i);