commit e437c5a63c42caa3c8617003fbabb7cd11242512
parent 90f51b997be6f411db84363e505cbbbcd3547bb4
Author: Samir Parikh <noreply@samirparikh.com>
Date: Wed, 5 Jan 2022 20:25:21 +0000
add binary search tree files and reorganize existing files into directories
Diffstat:
9 files changed, 290 insertions(+), 0 deletions(-)
diff --git a/binary-search-tree/BinarySearchTree.pm b/binary-search-tree/BinarySearchTree.pm
@@ -0,0 +1,65 @@
+package BinarySearchTree;
+use strict;
+use warnings;
+use Exporter qw<import>;
+our @EXPORT_OK = qw<tree treeSort>;
+
+#
+# implementation of binary search tree
+# as demonstrated in "Perl Cookbook" by Tom Christiansen and Nathan Torkington
+# https://www.oreilly.com/library/view/perl-cookbook/1565922433/
+#
+
+sub create_new_node {
+ my $value = shift;
+ # create anonymous array to represent the new node
+ my $tree = {};
+ $tree->{data} = $value;
+ $tree->{left} = undef;
+ $tree->{right} = undef;
+ return $tree;
+}
+
+sub insert {
+ my ( $tree, $value ) = @_;
+
+ # if node we want to insert (at any location in the tree) does not exist,
+ # create it and return a reference to the anonymous array containing it
+ # by updating the value that was passed to the subroutine ($tree)
+ unless ( $tree ) {
+ $_[0] = create_new_node ( $value );
+ return; # need to return since we just created a new node
+ }
+
+ # recursively find where to place new node in the tree
+ if ( $tree->{data} < $value ) { insert ( $tree->{right}, $value ) }
+ else { insert ( $tree->{left}, $value ) }
+}
+
+sub tree {
+ my ($data) = @_;
+ my $tree;
+ insert ( $tree, $_ ) foreach ( @{ $data } );
+ return $tree;
+}
+
+# recurse on left subtree, obtain root, recurse on right tree
+# until we get to empty node
+sub in_order {
+ my($tree) = @_;
+ return () unless $tree;
+ return (
+ in_order($tree->{left}),
+ $tree->{data},
+ in_order($tree->{right})
+ );
+}
+
+# You are expected to create a tree and then do an in-order walk.
+# Using the sort() function is cheating!
+sub treeSort {
+ my ($data) = @_;
+ return [in_order( tree ( $data ) )];
+}
+
+1;
diff --git a/binary-search-tree/binary-search-tree.t b/binary-search-tree/binary-search-tree.t
@@ -0,0 +1,225 @@
+#!/usr/bin/env perl
+use Test2::V0;
+use JSON::PP;
+use constant JSON => JSON::PP->new;
+
+use FindBin qw<$Bin>;
+use lib $Bin, "$Bin/local/lib/perl5";
+
+use BinarySearchTree qw<tree treeSort>;
+
+my @test_cases = do { local $/; @{ JSON->decode(<DATA>) }; };
+
+imported_ok qw<tree treeSort> or bail_out;
+
+subtest data => sub {
+ for my $case ( grep { $_->{property} eq 'data' } @test_cases ) {
+ is( tree( $case->{input}{treeData} ),
+ $case->{expected}, $case->{description}, );
+ }
+};
+
+subtest sorting => sub {
+ for my $case ( grep { $_->{property} eq 'sortedData' } @test_cases )
+ {
+ is( treeSort( $case->{input}{treeData} ),
+ $case->{expected}, $case->{description}, );
+ }
+};
+
+done_testing;
+
+__DATA__
+[
+ {
+ "description": "data is retained",
+ "expected": {
+ "data": "4",
+ "left": null,
+ "right": null
+ },
+ "input": {
+ "treeData": [
+ "4"
+ ]
+ },
+ "property": "data"
+ },
+ {
+ "description": "insert data at proper node: smaller number at left node",
+ "expected": {
+ "data": "4",
+ "left": {
+ "data": "2",
+ "left": null,
+ "right": null
+ },
+ "right": null
+ },
+ "input": {
+ "treeData": [
+ "4",
+ "2"
+ ]
+ },
+ "property": "data"
+ },
+ {
+ "description": "insert data at proper node: same number at left node",
+ "expected": {
+ "data": "4",
+ "left": {
+ "data": "4",
+ "left": null,
+ "right": null
+ },
+ "right": null
+ },
+ "input": {
+ "treeData": [
+ "4",
+ "4"
+ ]
+ },
+ "property": "data"
+ },
+ {
+ "description": "insert data at proper node: greater number at right node",
+ "expected": {
+ "data": "4",
+ "left": null,
+ "right": {
+ "data": "5",
+ "left": null,
+ "right": null
+ }
+ },
+ "input": {
+ "treeData": [
+ "4",
+ "5"
+ ]
+ },
+ "property": "data"
+ },
+ {
+ "description": "can create complex tree",
+ "expected": {
+ "data": "4",
+ "left": {
+ "data": "2",
+ "left": {
+ "data": "1",
+ "left": null,
+ "right": null
+ },
+ "right": {
+ "data": "3",
+ "left": null,
+ "right": null
+ }
+ },
+ "right": {
+ "data": "6",
+ "left": {
+ "data": "5",
+ "left": null,
+ "right": null
+ },
+ "right": {
+ "data": "7",
+ "left": null,
+ "right": null
+ }
+ }
+ },
+ "input": {
+ "treeData": [
+ "4",
+ "2",
+ "6",
+ "1",
+ "3",
+ "5",
+ "7"
+ ]
+ },
+ "property": "data"
+ },
+ {
+ "description": "can sort data: can sort single number",
+ "expected": [
+ "2"
+ ],
+ "input": {
+ "treeData": [
+ "2"
+ ]
+ },
+ "property": "sortedData"
+ },
+ {
+ "description": "can sort data: can sort if second number is smaller than first",
+ "expected": [
+ "1",
+ "2"
+ ],
+ "input": {
+ "treeData": [
+ "2",
+ "1"
+ ]
+ },
+ "property": "sortedData"
+ },
+ {
+ "description": "can sort data: can sort if second number is same as first",
+ "expected": [
+ "2",
+ "2"
+ ],
+ "input": {
+ "treeData": [
+ "2",
+ "2"
+ ]
+ },
+ "property": "sortedData"
+ },
+ {
+ "description": "can sort data: can sort if second number is greater than first",
+ "expected": [
+ "2",
+ "3"
+ ],
+ "input": {
+ "treeData": [
+ "2",
+ "3"
+ ]
+ },
+ "property": "sortedData"
+ },
+ {
+ "description": "can sort data: can sort complex tree",
+ "expected": [
+ "1",
+ "2",
+ "3",
+ "5",
+ "6",
+ "7"
+ ],
+ "input": {
+ "treeData": [
+ "2",
+ "1",
+ "3",
+ "6",
+ "7",
+ "5"
+ ]
+ },
+ "property": "sortedData"
+ }
+]
diff --git a/dijkstra.pl b/dijkstra/dijkstra.pl
diff --git a/dijkstra_shortest_path.pl b/dijkstra/dijkstra_shortest_path.pl
diff --git a/graph1.txt b/dijkstra/graph1.txt
diff --git a/graph2.txt b/dijkstra/graph2.txt
diff --git a/graph3.txt b/dijkstra/graph3.txt
diff --git a/coconet.dat b/hash_of_hash/coconet.dat
diff --git a/hash_of_hash.pl b/hash_of_hash/hash_of_hash.pl
