CSharpExperiments/RankOfStreamOfNumbers.cs at master · DForshner/CSharpExperiments · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
using Microsoft.VisualStudio.TestTools.UnitTesting;

// Determine the rank of a integer compared to all of the integers that
// have been streamed thus far.

namespace RankOfStreamOfNumbers
{
    public class Node
    {
        public int Value { get; set; }

        Node Left { get; set; }
        Node Right { get; set; }
        int LeftSize { get; set; }

        public void Insert(Node node)
        {
            if (node.Value < this.Value)
            {
                if (Left == null)
                {
                    Left = node;
                    return;
                }

                Left.Insert(node);
                LeftSize++;
            }
            else
            {
                if (Right == null)
                {
                    Right = node;
                    return;
                }

                Right.Insert(node);
            }
        }

        public int Rank(int valueToRank)
        {
            if (valueToRank == this.Value)
            {
                return LeftSize;
            }
            else if (valueToRank < this.Value)
            {
                if (Left == null) { return -1; }
                return Left.Rank(valueToRank);
            }
            else
            {
                int RightRank = (Right == null) ? -1 : Right.Rank(valueToRank);
                if (RightRank == -1)
                    return -1; // Didn't find element

                return LeftSize + 1 + RightRank;
            }
        }
    }

    public class Tree
    {
        Node root { get; set; }

        public void Insert(int valueToInsert)
        {
            var node = new Node() { Value = valueToInsert };

            if (root == null)
            {
                root = node;
                return;
            }

            root.Insert(node);
        }

        public int Rank(int valueToRank)
        {
            if (root == null)
                return -1;

            return root.Rank(valueToRank);
        }
    }

    [TestClass]
    public class UnitTests
    {
        const int NO_RANK = -1;

        [TestMethod]
        public void Rank_WhenEmptyTree_ExpectNoRank()
        {
            var tree = new Tree();
            Assert.AreEqual(NO_RANK, tree.Rank(7));
        }

        [TestMethod]
        public void Rank_WhenOnlyLesserNodes_ExpectNoRank()
        {
            var tree = new Tree();
            tree.Insert(5);
            tree.Insert(4);
            tree.Insert(6);
            Assert.AreEqual(NO_RANK, tree.Rank(7));
        }

        [TestMethod]
        public void Rank_WhenOnlyGreaterNodes_ExpectNoRank()
        {
            var tree = new Tree();
            tree.Insert(5);
            tree.Insert(4);
            tree.Insert(6);
            Assert.AreEqual(NO_RANK, tree.Rank(3));
        }

        [TestMethod]
        public void Rank_WhenLowestNode_ExpectBottomRank()
        {
            var tree = new Tree();
            tree.Insert(5);
            tree.Insert(4);
            tree.Insert(6);
            Assert.AreEqual(0, tree.Rank(5));
        }

        [TestMethod]
        public void Rank_WhenGreatestNode_ExpectTopRank()
        {
            var tree = new Tree();
            tree.Insert(5);
            tree.Insert(4);
            tree.Insert(6);
            Assert.AreEqual(1, tree.Rank(6));
        }

        [TestMethod]
        public void Rank_WhenRightLeafNode_ExpectCorrect()
        {
            var tree = new Tree();
            tree.Insert(10);
            tree.Insert(5);
            tree.Insert(15);
            tree.Insert(7);
            tree.Insert(13);
            Assert.AreEqual(1, tree.Rank(7));
        }
    }
}