Skip to content

Commit ea64e7a

Browse files
justcoding121justcoding121
authored
Merge pull request justcoding121#26 from justcoding121/master
Beta
2 parents 10aea5d + 818fd1f commit ea64e7a

File tree

7 files changed

+183
-31
lines changed

7 files changed

+183
-31
lines changed

‎docs/api/Advanced.Algorithms.DataStructures.BpTree-1.html

Lines changed: 53 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -122,7 +122,7 @@ <h4 id="Advanced_Algorithms_DataStructures_BpTree_1__ctor_System_Int32_" data-ui
122122
<div class="markdown level1 conceptual"></div>
123123
<h5 class="decalaration">Declaration</h5>
124124
<div class="codewrapper">
125-
<pre><code class="lang-csharp hljs">public BpTree(int maxKeysPerNode)</code></pre>
125+
<pre><code class="lang-csharp hljs">public BpTree(int maxKeysPerNode = 3)</code></pre>
126126
</div>
127127
<h5 class="parameters">Parameters</h5>
128128
<table class="table table-bordered table-striped table-condensed">
@@ -172,7 +172,7 @@ <h5 class="propertyValue">Property Value</h5>
172172

173173
<a id="Advanced_Algorithms_DataStructures_BpTree_1_Max_" data-uid="Advanced.Algorithms.DataStructures.BpTree`1.Max*"></a>
174174
<h4 id="Advanced_Algorithms_DataStructures_BpTree_1_Max" data-uid="Advanced.Algorithms.DataStructures.BpTree`1.Max">Max</h4>
175-
<div class="markdown level1 summary"><p>Time complexity: O(log(n)).</p>
175+
<div class="markdown level1 summary"><p>Time complexity: O(1).</p>
176176
</div>
177177
<div class="markdown level1 conceptual"></div>
178178
<h5 class="decalaration">Declaration</h5>
@@ -224,6 +224,32 @@ <h3 id="methods">Methods
224224
</h3>
225225

226226

227+
<a id="Advanced_Algorithms_DataStructures_BpTree_1_AsEnumerableDesc_" data-uid="Advanced.Algorithms.DataStructures.BpTree`1.AsEnumerableDesc*"></a>
228+
<h4 id="Advanced_Algorithms_DataStructures_BpTree_1_AsEnumerableDesc" data-uid="Advanced.Algorithms.DataStructures.BpTree`1.AsEnumerableDesc">AsEnumerableDesc()</h4>
229+
<div class="markdown level1 summary"><p>Descending enumerable.</p>
230+
</div>
231+
<div class="markdown level1 conceptual"></div>
232+
<h5 class="decalaration">Declaration</h5>
233+
<div class="codewrapper">
234+
<pre><code class="lang-csharp hljs">public IEnumerable&lt;T&gt; AsEnumerableDesc()</code></pre>
235+
</div>
236+
<h5 class="returns">Returns</h5>
237+
<table class="table table-bordered table-striped table-condensed">
238+
<thead>
239+
<tr>
240+
<th>Type</th>
241+
<th>Description</th>
242+
</tr>
243+
</thead>
244+
<tbody>
245+
<tr>
246+
<td><span class="xref">IEnumerable</span>&lt;T&gt;</td>
247+
<td></td>
248+
</tr>
249+
</tbody>
250+
</table>
251+
252+
227253
<a id="Advanced_Algorithms_DataStructures_BpTree_1_Delete_" data-uid="Advanced.Algorithms.DataStructures.BpTree`1.Delete*"></a>
228254
<h4 id="Advanced_Algorithms_DataStructures_BpTree_1_Delete__0_" data-uid="Advanced.Algorithms.DataStructures.BpTree`1.Delete(`0)">Delete(T)</h4>
229255
<div class="markdown level1 summary"><p>Time complexity: O(log(n)).</p>
@@ -277,6 +303,31 @@ <h5 class="returns">Returns</h5>
277303
</table>
278304

279305

306+
<a id="Advanced_Algorithms_DataStructures_BpTree_1_GetEnumeratorDesc_" data-uid="Advanced.Algorithms.DataStructures.BpTree`1.GetEnumeratorDesc*"></a>
307+
<h4 id="Advanced_Algorithms_DataStructures_BpTree_1_GetEnumeratorDesc" data-uid="Advanced.Algorithms.DataStructures.BpTree`1.GetEnumeratorDesc">GetEnumeratorDesc()</h4>
308+
<div class="markdown level1 summary"></div>
309+
<div class="markdown level1 conceptual"></div>
310+
<h5 class="decalaration">Declaration</h5>
311+
<div class="codewrapper">
312+
<pre><code class="lang-csharp hljs">public IEnumerator&lt;T&gt; GetEnumeratorDesc()</code></pre>
313+
</div>
314+
<h5 class="returns">Returns</h5>
315+
<table class="table table-bordered table-striped table-condensed">
316+
<thead>
317+
<tr>
318+
<th>Type</th>
319+
<th>Description</th>
320+
</tr>
321+
</thead>
322+
<tbody>
323+
<tr>
324+
<td><span class="xref">IEnumerator</span>&lt;T&gt;</td>
325+
<td></td>
326+
</tr>
327+
</tbody>
328+
</table>
329+
330+
280331
<a id="Advanced_Algorithms_DataStructures_BpTree_1_HasItem_" data-uid="Advanced.Algorithms.DataStructures.BpTree`1.HasItem*"></a>
281332
<h4 id="Advanced_Algorithms_DataStructures_BpTree_1_HasItem__0_" data-uid="Advanced.Algorithms.DataStructures.BpTree`1.HasItem(`0)">HasItem(T)</h4>
282333
<div class="markdown level1 summary"><p>Time complexity: O(log(n)).</p>

‎docs/index.json

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -77,7 +77,7 @@
7777
"api/Advanced.Algorithms.DataStructures.BpTree-1.html": {
7878
"href": "api/Advanced.Algorithms.DataStructures.BpTree-1.html",
7979
"title": "Class BpTree<T> | Advanced Algorithms",
80-
"keywords": "Class BpTree<T> A B+ tree implementation. Inheritance Object BpTree<T> Namespace : Advanced.Algorithms.DataStructures Assembly : Advanced.Algorithms.dll Syntax public class BpTree<T> : IEnumerable<T> where T : IComparable Type Parameters Name Description T Constructors BpTree(Int32) Declaration public BpTree(int maxKeysPerNode) Parameters Type Name Description Int32 maxKeysPerNode Properties Count Declaration public int Count { get; } Property Value Type Description Int32 Max Time complexity: O(log(n)). Declaration public T Max { get; } Property Value Type Description T Min Time complexity: O(1). Declaration public T Min { get; } Property Value Type Description T Methods Delete(T) Time complexity: O(log(n)). Declaration public void Delete(T value) Parameters Type Name Description T value GetEnumerator() Declaration public IEnumerator<T> GetEnumerator() Returns Type Description IEnumerator <T> HasItem(T) Time complexity: O(log(n)). Declaration public bool HasItem(T value) Parameters Type Name Description T value Returns Type Description Boolean Insert(T) Time complexity: O(log(n)). Declaration public void Insert(T newValue) Parameters Type Name Description T newValue"
80+
"keywords": "Class BpTree<T> A B+ tree implementation. Inheritance Object BpTree<T> Namespace : Advanced.Algorithms.DataStructures Assembly : Advanced.Algorithms.dll Syntax public class BpTree<T> : IEnumerable<T> where T : IComparable Type Parameters Name Description T Constructors BpTree(Int32) Declaration public BpTree(int maxKeysPerNode = 3) Parameters Type Name Description Int32 maxKeysPerNode Properties Count Declaration public int Count { get; } Property Value Type Description Int32 Max Time complexity: O(1). Declaration public T Max { get; } Property Value Type Description T Min Time complexity: O(1). Declaration public T Min { get; } Property Value Type Description T Methods AsEnumerableDesc() Descending enumerable. Declaration public IEnumerable<T> AsEnumerableDesc() Returns Type Description IEnumerable <T> Delete(T) Time complexity: O(log(n)). Declaration public void Delete(T value) Parameters Type Name Description T value GetEnumerator() Declaration public IEnumerator<T> GetEnumerator() Returns Type Description IEnumerator <T> GetEnumeratorDesc() Declaration public IEnumerator<T> GetEnumeratorDesc() Returns Type Description IEnumerator <T> HasItem(T) Time complexity: O(log(n)). Declaration public bool HasItem(T value) Parameters Type Name Description T value Returns Type Description Boolean Insert(T) Time complexity: O(log(n)). Declaration public void Insert(T newValue) Parameters Type Name Description T newValue"
8181
},
8282
"api/Advanced.Algorithms.DataStructures.BST-1.html": {
8383
"href": "api/Advanced.Algorithms.DataStructures.BST-1.html",

‎docs/xrefmap.yml

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1010,6 +1010,23 @@ references:
10101010
fullName.vb: Advanced.Algorithms.DataStructures.BpTree(Of T).BpTree
10111011
nameWithType: BpTree<T>.BpTree
10121012
nameWithType.vb: BpTree(Of T).BpTree
1013+
- uid: Advanced.Algorithms.DataStructures.BpTree`1.AsEnumerableDesc
1014+
name: AsEnumerableDesc()
1015+
href: api/Advanced.Algorithms.DataStructures.BpTree-1.html#Advanced_Algorithms_DataStructures_BpTree_1_AsEnumerableDesc
1016+
commentId: M:Advanced.Algorithms.DataStructures.BpTree`1.AsEnumerableDesc
1017+
fullName: Advanced.Algorithms.DataStructures.BpTree<T>.AsEnumerableDesc()
1018+
fullName.vb: Advanced.Algorithms.DataStructures.BpTree(Of T).AsEnumerableDesc()
1019+
nameWithType: BpTree<T>.AsEnumerableDesc()
1020+
nameWithType.vb: BpTree(Of T).AsEnumerableDesc()
1021+
- uid: Advanced.Algorithms.DataStructures.BpTree`1.AsEnumerableDesc*
1022+
name: AsEnumerableDesc
1023+
href: api/Advanced.Algorithms.DataStructures.BpTree-1.html#Advanced_Algorithms_DataStructures_BpTree_1_AsEnumerableDesc_
1024+
commentId: Overload:Advanced.Algorithms.DataStructures.BpTree`1.AsEnumerableDesc
1025+
isSpec: "True"
1026+
fullName: Advanced.Algorithms.DataStructures.BpTree<T>.AsEnumerableDesc
1027+
fullName.vb: Advanced.Algorithms.DataStructures.BpTree(Of T).AsEnumerableDesc
1028+
nameWithType: BpTree<T>.AsEnumerableDesc
1029+
nameWithType.vb: BpTree(Of T).AsEnumerableDesc
10131030
- uid: Advanced.Algorithms.DataStructures.BpTree`1.Count
10141031
name: Count
10151032
href: api/Advanced.Algorithms.DataStructures.BpTree-1.html#Advanced_Algorithms_DataStructures_BpTree_1_Count
@@ -1061,6 +1078,23 @@ references:
10611078
fullName.vb: Advanced.Algorithms.DataStructures.BpTree(Of T).GetEnumerator
10621079
nameWithType: BpTree<T>.GetEnumerator
10631080
nameWithType.vb: BpTree(Of T).GetEnumerator
1081+
- uid: Advanced.Algorithms.DataStructures.BpTree`1.GetEnumeratorDesc
1082+
name: GetEnumeratorDesc()
1083+
href: api/Advanced.Algorithms.DataStructures.BpTree-1.html#Advanced_Algorithms_DataStructures_BpTree_1_GetEnumeratorDesc
1084+
commentId: M:Advanced.Algorithms.DataStructures.BpTree`1.GetEnumeratorDesc
1085+
fullName: Advanced.Algorithms.DataStructures.BpTree<T>.GetEnumeratorDesc()
1086+
fullName.vb: Advanced.Algorithms.DataStructures.BpTree(Of T).GetEnumeratorDesc()
1087+
nameWithType: BpTree<T>.GetEnumeratorDesc()
1088+
nameWithType.vb: BpTree(Of T).GetEnumeratorDesc()
1089+
- uid: Advanced.Algorithms.DataStructures.BpTree`1.GetEnumeratorDesc*
1090+
name: GetEnumeratorDesc
1091+
href: api/Advanced.Algorithms.DataStructures.BpTree-1.html#Advanced_Algorithms_DataStructures_BpTree_1_GetEnumeratorDesc_
1092+
commentId: Overload:Advanced.Algorithms.DataStructures.BpTree`1.GetEnumeratorDesc
1093+
isSpec: "True"
1094+
fullName: Advanced.Algorithms.DataStructures.BpTree<T>.GetEnumeratorDesc
1095+
fullName.vb: Advanced.Algorithms.DataStructures.BpTree(Of T).GetEnumeratorDesc
1096+
nameWithType: BpTree<T>.GetEnumeratorDesc
1097+
nameWithType.vb: BpTree(Of T).GetEnumeratorDesc
10641098
- uid: Advanced.Algorithms.DataStructures.BpTree`1.HasItem(`0)
10651099
name: HasItem(T)
10661100
href: api/Advanced.Algorithms.DataStructures.BpTree-1.html#Advanced_Algorithms_DataStructures_BpTree_1_HasItem__0_

‎src/Advanced.Algorithms/DataStructures/Heap/BHeap.cs

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -55,7 +55,7 @@ public BHeap(SortDirection sortDirection, IEnumerable<T> initial, IComparer<T> c
5555
i++;
5656
}
5757

58-
BulkInit(initArray);
58+
bulkInit(initArray);
5959
Count = initArray.Length;
6060
}
6161
else
@@ -64,7 +64,7 @@ public BHeap(SortDirection sortDirection, IEnumerable<T> initial, IComparer<T> c
6464
}
6565
}
6666

67-
private void BulkInit(T[] initial)
67+
private void bulkInit(T[] initial)
6868
{
6969
var i = (initial.Length - 1) / 2;
7070

@@ -86,7 +86,8 @@ private void bulkInitRecursive(int i, T[] initial)
8686
var left = 2 * i + 1;
8787
var right = 2 * i + 2;
8888

89-
var minMax = left < initial.Length && right < initial.Length ? comparer.Compare(initial[left], initial[right]) < 0 ? left : right
89+
var minMax = left < initial.Length && right < initial.Length ?
90+
comparer.Compare(initial[left], initial[right]) < 0 ? left : right
9091
: left < initial.Length ? left
9192
: right < initial.Length ? right : -1;
9293

‎src/Advanced.Algorithms/DataStructures/Heap/d-aryHeap.cs

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -47,7 +47,7 @@ public DaryHeap(int k, SortDirection sortDirection = SortDirection.Ascending, IE
4747
}
4848

4949
Count = initArray.Length;
50-
BulkInit(initArray);
50+
bulkInit(initArray);
5151

5252
}
5353
else
@@ -60,7 +60,7 @@ public DaryHeap(int k, SortDirection sortDirection = SortDirection.Ascending, IE
6060
/// Initialize with given input.
6161
/// Time complexity: O(n).
6262
/// </summary>
63-
private void BulkInit(T[] initial)
63+
private void bulkInit(T[] initial)
6464
{
6565
var i = (initial.Length - 1) / k;
6666

‎src/Advanced.Algorithms/DataStructures/Tree/B+Tree.cs

Lines changed: 68 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -14,24 +14,26 @@ public class BpTree<T> : IEnumerable<T> where T : IComparable
1414
internal BpTreeNode<T> Root;
1515

1616
/// <summary>
17-
///Keep a reference of Bottom Left Node
18-
///For faster enumeration with IEnumerable implementation using Next pointer
17+
/// Keep a reference of Bottom Left/Right Node
18+
/// for fast ascending/descending enumeration using Next pointer.
19+
/// See IEnumerable and IEnumerableDesc implementation at bottom.
1920
/// </summary>
2021
internal BpTreeNode<T> BottomLeftNode;
22+
internal BpTreeNode<T> BottomRightNode;
2123

2224
private readonly int maxKeysPerNode;
2325
private readonly int minKeysPerNode;
2426

2527
/// <summary>
26-
/// Time complexity: O(log(n)).
28+
/// Time complexity: O(1).
2729
/// </summary>
2830
public T Max
2931
{
3032
get
3133
{
3234
if (Root == null) return default(T);
3335

34-
var maxNode = findMaxNode(Root);
36+
var maxNode = BottomRightNode;
3537
return maxNode.Keys[maxNode.KeyCount - 1];
3638
}
3739
}
@@ -50,7 +52,7 @@ public T Min
5052
}
5153
}
5254

53-
public BpTree(int maxKeysPerNode)
55+
public BpTree(int maxKeysPerNode = 3)
5456
{
5557
if (maxKeysPerNode < 3)
5658
{
@@ -122,6 +124,7 @@ public void Insert(T newValue)
122124
Root.KeyCount++;
123125
Count++;
124126
BottomLeftNode = Root;
127+
BottomRightNode = Root;
125128
return;
126129
}
127130

@@ -204,6 +207,11 @@ private void insertAndSplit(ref BpTreeNode<T> node, T newValue,
204207
right.Next = node.Next;
205208
node.Next.Prev = right;
206209
}
210+
else
211+
{
212+
//bottom right most node
213+
BottomRightNode = right;
214+
}
207215

208216
if (node.Prev != null)
209217
{
@@ -212,7 +220,7 @@ private void insertAndSplit(ref BpTreeNode<T> node, T newValue,
212220
}
213221
else
214222
{
215-
//left most bottom node
223+
//bottom left most node
216224
BottomLeftNode = left;
217225
}
218226
}
@@ -559,7 +567,10 @@ private void sandwich(BpTreeNode<T> leftSibling, BpTreeNode<T> rightSibling, T d
559567
newNode.Next = rightSibling.Next;
560568
rightSibling.Next.Prev = newNode;
561569
}
562-
570+
else
571+
{
572+
BottomRightNode = newNode;
573+
}
563574
}
564575

565576
var newIndex = 0;
@@ -912,6 +923,14 @@ private void removeAt<TS>(TS[] array, int index)
912923
Array.Copy(array, index + 1, array, index, array.Length - index - 1);
913924
}
914925

926+
/// <summary>
927+
/// Descending enumerable.
928+
/// </summary>
929+
public IEnumerable<T> AsEnumerableDesc()
930+
{
931+
return GetEnumeratorDesc().AsEnumerable();
932+
}
933+
915934
//Implementation for the GetEnumerator method.
916935
IEnumerator IEnumerable.GetEnumerator()
917936
{
@@ -922,6 +941,11 @@ public IEnumerator<T> GetEnumerator()
922941
{
923942
return new BpTreeEnumerator<T>(this);
924943
}
944+
945+
public IEnumerator<T> GetEnumeratorDesc()
946+
{
947+
return new BpTreeEnumerator<T>(this, false);
948+
}
925949
}
926950

927951
internal class BpTreeNode<T> : BNode<T> where T : IComparable
@@ -970,14 +994,21 @@ internal override BNode<T>[] GetChildren()
970994

971995
internal class BpTreeEnumerator<T> : IEnumerator<T> where T : IComparable
972996
{
973-
private BpTreeNode<T> bottomLeftNode;
997+
private readonly bool asc;
998+
999+
private BpTreeNode<T> startNode;
9741000
private BpTreeNode<T> current;
975-
private int index = -1;
9761001

977-
internal BpTreeEnumerator(BpTree<T> tree)
1002+
private int index;
1003+
1004+
internal BpTreeEnumerator(BpTree<T> tree, bool asc = true)
9781005
{
979-
bottomLeftNode = tree.BottomLeftNode;
980-
current = bottomLeftNode;
1006+
this.asc = asc;
1007+
1008+
startNode = asc ? tree.BottomLeftNode : tree.BottomRightNode;
1009+
current = startNode;
1010+
1011+
index = asc ? -1 : current.KeyCount;
9811012
}
9821013

9831014
public bool MoveNext()
@@ -987,22 +1018,38 @@ public bool MoveNext()
9871018
return false;
9881019
}
9891020

990-
if (index + 1 < current.KeyCount)
1021+
if (asc)
9911022
{
992-
index++;
993-
return true;
1023+
if (index + 1 < current.KeyCount)
1024+
{
1025+
index++;
1026+
return true;
1027+
}
1028+
}
1029+
else
1030+
{
1031+
if (index - 1 >= 0)
1032+
{
1033+
index--;
1034+
return true;
1035+
}
9941036
}
9951037

996-
current = current.Next;
997-
index = 0;
1038+
current = asc ? current.Next : current.Prev;
1039+
1040+
var canMove = current != null && current.KeyCount > 0;
1041+
if (canMove)
1042+
{
1043+
index = asc ? 0 : current.KeyCount - 1;
1044+
}
9981045

999-
return current != null && current.KeyCount > 0;
1046+
return canMove;
10001047
}
10011048

10021049
public void Reset()
10031050
{
1004-
current = bottomLeftNode;
1005-
index = -1;
1051+
current = startNode;
1052+
index = asc ? -1 : current.KeyCount;
10061053
}
10071054

10081055
object IEnumerator.Current => Current;
@@ -1018,8 +1065,7 @@ public T Current
10181065
public void Dispose()
10191066
{
10201067
current = null;
1021-
bottomLeftNode = null;
1022-
index = -1;
1068+
startNode = null;
10231069
}
10241070
}
10251071

0 commit comments

Comments
 (0)