mmnaseri / cs-review Goto Github PK

LevelLinkedTreeNodeTest should be implemented.

We should have a facility that would monitor data structures and their respective states and reports back a failure on their part to abide by the intrinsic properties

I have seen invalid colorings that break the red black property on the red black tree class.

Each of these should instead return a new graph that matches the original, and mark, color, or otherwise modify that graph.

Right now, controlling a feature requires extending the original class for the data structure which, while trivial, is tedious.

It would be far better if there was a facility for proxying data structures and setting feature-base expectations on the data structure so that we could arbitrarily secure any given data structure of choice for any given task.

One example would be:

final SearchTree<Integer, ? extends TreeNode<Integer>> tree;
tree = new BinarySearchTree<Integer, BinaryTreeNode<Integer>>();
final SearchTree<Integer, ? extends TreeNode<Integer>> securedTree;
securedTree = givenDataStructure(tree)
                            .observe(inOrderWalkYieldsSortedValues())
                            .observe(minimumIsOnTheLeftMostNode())
                            .observe(maximumIsOnTheRightMostNode())
                            .observe(nodeIsGreaterOrEqualToItsLeftChild())
                            .observe(nodeIsLessThanItsRightChild())
                            .observe(nodeIsGreaterOrEqualToItsLeftChild())
                            .secure();

At this point, if the tree is not honoring any of the features, we will see MonitorFailureExceptions. Features will be checked before and after the execution of each operation, ensuring that the data structure is always in a valid state.

(We could probably monitor the data structure upon creation, and then after each operation, and it would suffice).

This should be theoretically implementable if features can be observed from the outside, which is not always the case. In such cases, a strategy is probably required and I should probably think of a way to incorporate that into the DSL.

LinearSelector uses divide and conquer algorithm to split, partition and find the order. When the order is not the pivot index, we don't need to include it in the next sub problem.

ArrayHeap can also be tested with equal items as an edge case.

ArrayMatrix should be tested

The private delete method runs over few hundres of lines of code. Can this be more modular?
https://github.com/mmnaseri/cs-review/blob/master/cs-clrs/src/main/java/com/mmnaseri/cs/clrs/ch18/s3/BTree.java#L31

The algorithm described by the book does not return the minimum tree. This is demonstrated by the book on page 633 of the ebook where the result has a total weight of 37, while running the Prim algorithm from the book returns a total of 35, as seen on page 635.

Figure out why this behavior is not considered as invalid.