MESSAGE
| DATE | 2016-11-23 |
| FROM | Ruben Safir
|
| SUBJECT | Subject: [Learn] Parrelel Programming HW2 with maxpath
|
From learn-bounces-at-nylxs.com Wed Nov 23 01:17:30 2016
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: from www.mrbrklyn.com (www.mrbrklyn.com [96.57.23.82])
by mrbrklyn.com (Postfix) with ESMTP id B3DC8161317;
Wed, 23 Nov 2016 01:17:29 -0500 (EST)
X-Original-To: learn-at-nylxs.com
Delivered-To: learn-at-nylxs.com
Received: from [10.0.0.62] (flatbush.mrbrklyn.com [10.0.0.62])
by mrbrklyn.com (Postfix) with ESMTP id 26246161313;
Wed, 23 Nov 2016 01:15:27 -0500 (EST)
To: Samir Iabbassen
From: Ruben Safir
Message-ID:
Date: Wed, 23 Nov 2016 01:15:27 -0500
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
Thunderbird/45.4.0
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="------------28880EA7B9C8B633B134B083"
X-Mailman-Approved-At: Wed, 23 Nov 2016 01:17:26 -0500
Subject: [Learn] Parrelel Programming HW2 with maxpath
X-BeenThere: learn-at-nylxs.com
X-Mailman-Version: 2.1.17
Precedence: list
List-Id:
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
Errors-To: learn-bounces-at-nylxs.com
Sender: "Learn"
This is a multi-part message in MIME format.
--------------28880EA7B9C8B633B134B083
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
This is the submission for the 2nd HW. I haven't actually yet checked
the final result, although I've been testing it all along. I've been
working on it almost exclusive for more than a week. I tripped up on
several programs which I wish to describe.
First of all, a year ago, when taking the algorithm class with Dr
Rodriguez, I worked on a method of creating large binary trees in a
balanced fashion. I failed miserably because to do it in a balanced
means,you can't just test for null. I tried measuring heights to
determine when to shift, and other methods, and I just didn't find a
means. I finally, after about 3 days of working on this problem, gave
up and looked for a solution and discovered a wonderfully short
algorithm that does this nice, but it is written in C.
#include
#include
#include
struct node
{
struct node *left ;
char data ;
struct node *right ;
} ;
struct node * buildtree ( int ) ;
void inorder ( struct node * ) ;
char a[ ] = {
'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H', '\0',
'\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0'
} ;
void main( )
{
struct node *root ;
clrscr( ) ;
root = buildtree ( 0 ) ;
printf ( "In-order Traversal:\n" ) ;
inorder ( root ) ;
getch( ) ;
}
struct node * buildtree ( int n )
{
struct node *temp = NULL ;
if ( a[n] != '\0' )
{
temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
temp -> left = buildtree ( 2 * n + 1 ) ;
temp -> data = a[n] ;
temp -> right = buildtree ( 2 * n + 2 ) ;
}
return temp ;
}
void inorder ( struct node *root )
{
if ( root != NULL )
{
inorder ( root -> left ) ;
printf ( "%c\t", root -> data ) ;
inorder ( root -> right ) ;
}
}
It is nice, and I was thinking along this line in solving the problem
but I just couldn't come up with the solution. I was trying to do it in
pairs, and he does hop scotch like a two headed monster.
So once I found this, I then needed to adapt it to C++ and I wanted
something that seemed like C++ and sat in my Tree object that a property
of the tree. This ended up being much harder than I though and I did
this at one point accept that my return value for the root kept giving
me a node from the center of the run. I tried to track down the data
flow problem, but even with DDD I still couldn't track the problem with
the data. Then I messed up the algorithm all together with
experimentation, so after 2 more days, I had to rewrite from scratch
much closer to the C code. I then tweaked it so it worked smoothly in
my class hierarchy. So that is already a week shot, and I finally
slept, because I didn't sleep for few days while working on this. I got
up at 11AM this morning and finally broke it down into 4 threads using
the new C++ library. I did an overide of a class's
operator()() so I could embed an entire class into the thread call back.
I was going to try to use a try catch method to handle thread joins,
but that didn't work as the try block is not visible to the catch block
and are two different scopes. That is not how I would design it.
The program should have destructors that do delete. I needed to spawn
nodes. I tried to get around it, but there is really no practical means
of doing that or eliminating the pointers in the tree object. I tried
to replace them with references but you can't have references that are
assigned to nullptr.
If you change SIZE in main.cpp you can make an expediently small
dataset. My C++ skills are not as good as they were a few years ago,
and that is very much bothering me.
Ruben
--
So many immigrant groups have swept through our town
that Brooklyn, like Atlantis, reaches mythological
proportions in the mind of the world - RI Safir 1998
http://www.mrbrklyn.com
DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002
http://www.nylxs.com - Leadership Development in Free Software
http://www2.mrbrklyn.com/resources - Unpublished Archive
http://www.coinhangout.com - coins!
http://www.brooklyn-living.com
Being so tracked is for FARM ANIMALS and and extermination camps,
but incompatible with living as a free human being. -RI Safir 2013
--------------28880EA7B9C8B633B134B083
Content-Type: text/x-c++src;
name="binary_build.C"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="binary_build.C"
/*
* =====================================================================================
*
* Filename: binary_build.C
*
* Description: Builds Binaries
*
* Version: 1.0
* Created: 11/20/2016 08:03:41 PM
* Revision: none
* Compiler: gcc
*
* Author: Ruben Safir (mn), ruben-at-mrbrklyn.com
* Company: NYLXS Inc
*
* =====================================================================================
*/
#include
#include
#include
struct node
{
struct node *left ;
char data ;
struct node *right ;
} ;
struct node * buildtree ( int ) ;
void inorder ( struct node * ) ;
char a[ ] = {
'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H', '\0',
'\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0'
} ;
void main( )
{
struct node *root ;
clrscr( ) ;
root = buildtree ( 0 ) ;
printf ( "In-order Traversal:\n" ) ;
inorder ( root ) ;
getch( ) ;
}
struct node * buildtree ( int n )
{
struct node *temp = NULL ;
if ( a[n] != '\0' )
{
temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
temp -> left = buildtree ( 2 * n + 1 ) ;
temp -> data = a[n] ;
temp -> right = buildtree ( 2 * n + 2 ) ;
}
return temp ;
}
void inorder ( struct node *root )
{
if ( root != NULL )
{
inorder ( root -> left ) ;
printf ( "%c\t", root -> data ) ;
inorder ( root -> right ) ;
}
}
--------------28880EA7B9C8B633B134B083
Content-Type: text/x-c++src;
name="main.cpp"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="main.cpp"
/*
* =====================================================================================
*
* Filename: main.cpp
*
* Description: Max Path discovery test program HW
*
* Version: 1.0
* Created: 11/18/2016 09:33:20 AM
* Revision: none
* Compiler: gcc
*
* Author: Ruben Safir
* Company: NYLXS
*
* =====================================================================================
*/
#include
#include "maxpath.h"
#include
#include
#include
#define SIZE 200000000
class workerbee
{
public:
workerbee(maxpath::Tree &in, maxpath::Node *startpt):_cladogram{in}, _startpt{startpt}{};
void operator()()
{
std::cout << cladogram().max_calc( startpt() ) << std::endl;
std::cout << "Cells =>" << cladogram().node_count() << std::endl;
std::cout << "height =>" << cladogram().height() << std::endl;
}
maxpath::Tree cladogram (maxpath::Tree& in ){
return _cladogram = in;
}
maxpath::Tree cladogram (){
return _cladogram;
}
maxpath::Node * startpt (maxpath::Node *& in ){
return _startpt = in;
}
maxpath::Node * startpt (){
return _startpt;
}
private:
maxpath::Tree _cladogram;
maxpath::Node * _startpt;
};
//std::cout << mytree.max_calc(mytree.root()) << std::endl;
//std::cout << "Cells =>" << mytree.node_count() << std::endl;
//std::cout << "height =>" << mytree.height() << std::endl;
int main(int argv, char **argc)
{
using namespace std;
int *data = new int[SIZE];
// int *cache = new int[SIZE];
struct timespec now;
clock_gettime(CLOCK_REALTIME, &now);
long seed = now.tv_nsec;
srand( (unsigned int) seed);
for(int i = 0; i < SIZE; i++){
data[i] = rand() % 1000000;
// cout << data[i] << "\t";
}
cout << endl;
cout << "________________________________________________________" << endl;
cout << "***Size of Array " << SIZE << "****" << endl;
cout << "____________________" << endl;
cout << "Array Before" << endl;
for(int i = 0; i < SIZE; i++){
cout << "--------------------" << endl;
cout << "| " << i << " ==> " << data[i] << "\t |" << endl;
}
cout << "--------------------" << endl;
cout << "--------------------" << endl;
//build the tree
maxpath::Node top;
maxpath::Tree mytree(top); //initialize tree
std::cout << "MAIN::Initial Node Count " << mytree.node_count() << std::endl;
// std::cout << "Initial Height " << mytree.height() << std::endl;
mytree.create_tree(data, SIZE);
mytree.root();
std::cout << "root value: " << mytree.root()->value() << std::endl;
mytree.post_fix();
maxpath::Node *first, *second, *third, *fourth;
first = mytree.root()->left()->left();
second = mytree.root()->left()->right();
third = mytree.root()->right()->left();
fourth = mytree.root()->right()->right();
long x1, x2, x3, x4;
x1 = max(first->max(), second->max());
x2 = max(third->max(), fourth->max());
x3 = mytree.root()->left()->value();
x4 = mytree.root()->right()->value();
mytree.root()->left()->max(x1 + x3 );
mytree.root()->right()->max(x2 + x4 );
x3 = mytree.root()->left()->max();
x4 = mytree.root()->right()->max();
x1 = max(x3, x4);
mytree.root()->max(x1 + mytree.root()->value() );
std::cout << "Final Max Path Result" << mytree.root()->max() << std::endl;
workerbee one (mytree, first);
workerbee two (mytree, second);
workerbee three (mytree, third );
workerbee four (mytree, fourth);
std::thread echud(one);
std::thread shnayim(two);
std::thread shlosha(three);
std::thread arbaa(four);
echud.join();
shnayim.join();
shlosha.join();
arbaa.join();
// merge::track(0, SIZE - 1, data);
// cout << "____________________" << endl;
// cout << "Array AFTER" << endl;
// for(int i = 0; i < SIZE; i++){
// cout << "--------------------" << endl;
// cout << "| " << i << " ==> " << data[i] << "\t |" << endl;
// }
// cout << "--------------------" << endl;
// cout << "--------------------" << endl;
return 0;
}
--------------28880EA7B9C8B633B134B083
Content-Type: text/plain; charset=UTF-8;
name="makefile"
Content-Transfer-Encoding: base64
Content-Disposition: attachment;
filename="makefile"
Q1hYOj1nKysgCkNYWEZMQUdTOj0tV2FsbCAtZ2dkYiAgLXBnIC1wdGhyZWFkCgpMREZMQUdT
Oj0tTC91c3IvbG9jYWwvbGliL215c3FsIC1sbXlzcWxwcCAtbG15c3FsY2xpZW50CgptYXhw
YXRoIDoJbWF4cGF0aC5vIG1haW4ubwoJJHtDWFh9ICAke0NYWEZMQUdTfSAtbyBtYXhwYXRo
IG1heHBhdGgubyBtYWluLm8KCm1haW4ubyA6CW1haW4uY3BwCgkke0NYWH0gICR7Q1hYRkxB
R1N9IC1vIG1haW4ubyAtYyBtYWluLmNwcAkKCm1heHBhdGgubyA6CW1heHBhdGguY3BwCW1h
eHBhdGguaAoJJHtDWFh9ICAke0NYWEZMQUdTfSAtYyBtYXhwYXRoLmNwcAoKY2xlYW4JOiAK
CXJtIG1heHBhdGggKi5vIG1ha2UuZGVwcwoJdG91Y2ggKi5jcHAgKi5oCgppbmNsdWRlIG1h
a2UuZGVwcwptYWtlLmRlcHM6ICouY3BwIDsgZ2NjIC1NICouY3BwID4kQAo=
--------------28880EA7B9C8B633B134B083
Content-Type: text/x-c++src;
name="maxpath.cpp"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="maxpath.cpp"
#include "maxpath.h"
#include
#include
namespace merge{
int min(int x, int y){
int ret;
x //std::cout << x << ":" << y << "==>" << ret << std::endl;
return ret;
}
void merge(int j, int l, int m, int k, int * value){
int size = (k-j) + 1;
std::cout << "Allocating scratch ==>" << size << std::endl;
int * scratch = new int[size];
int l_pos1 = j;
int l_pos2 = l;
int r_pos1 = m;
int r_pos2 = k;
int i = 0;
std::cout << "Scratch index: " << i << std::endl;
std::cout << "l_pos1: " << l_pos1 << "\tr_pos1: " << r_pos1 << std::endl;
std::cout << "l_pos2: " << l_pos2 << "\tr_pos2: " << r_pos2 << std::endl;
int l_next = l_pos1;
int r_next = r_pos1;
int cur = -1;//cursor rest position
int cursor[3] = {cur, l_next, r_next};
while((cursor[1] <= l_pos2) && (cursor[2] <= r_pos2)) {
std::cout << "Positions" << cursor[0] << ":" << cursor[1] << ":" << cursor[2] << std::endl;
std::cout << "Values " << value[cursor[1]] << ":" << value[cursor[2]] << std::endl;
if(value[cursor[1]] <= value[cursor[2]]) {
scratch[i] = value[cursor[1]];
cursor[0] = cursor[1];
cursor[1]++;
}else if(value[cursor[1]] > value[cursor[2]]){
scratch[i] = value[cursor[2]];
cursor[0] = cursor[2];
cursor[2]++;
}
std::cout << "Positions" << cursor[0] << ":" << cursor[1] << ":" << cursor[2] << std::endl;
std::cout << "Values " << value[cursor[1]] << ":" << value[cursor[2]] << std::endl;
i++;
}
//we hit the top
while(1){
std::cout << "clearing data...";
if(cursor[2] <= r_pos2 ){
scratch[i] = value[cursor[2]];
i++;
cursor[2]++;
}else if(cursor[1] <= l_pos2){
scratch[i] = value[cursor[1]];
i++;
cursor[1]++;
}else{
break;
}
}
std::cout << "done" << std::endl;
//copy scratch to the array
std::cout << "copying scratch" << std::endl;
for(int pos = j, i=0; i <= (k-j); pos++, i++){
std::cout << i << " : " << scratch[i] <<" to position " << pos << std::endl;
value[pos] = scratch[i];
}
std::cout << "free scratch" << std::endl;
delete[] scratch;
std::cout << "done with scratch" << std::endl;
return;
}
//j is far left of array
//k is far right of array
//l is middle of array - right of left child array
//m is middle + 1 of the array - left of right child array
//
// j l m k
//_____________________________________
//| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11|
//--------------------------------------
//
void track(int j, int k, int * parent )
{
//std::cout << "\n j is far left of array\n k is far right of array\n l is middle of array - right of left child array\n m is middle + 1 of the array - left of right child array\n\n j l m k\n _____________________________________\n | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11|\n --------------------------------------\n ";
std:: cout << "======================" << std::endl;
std::cout << "|| __NEW NODE__ ||\n|| j =>" << j << " " << "k=> " << k << " ||" << std::endl;
std:: cout << "======================" << std::endl;
int length = k - j;
int l = j + (length / 2);
int m = l + 1;
if(j == k )
{
std::cout << "\n\n\n**********RETURN**********" << std::endl;
return;
}
std::cout << "Left Branch: j =>" << j << "\t" << "l => " << l << std::endl;
std::cout << "Right Branch: m =>" << m << "\t" << "k => " << k << std::endl;
std::cout << std::endl;
std::cout << std::endl;
std::cout << std::endl;
std::cout << "***Enter left : j =>" << j << "\t" << "l => " << l << "***" << std::endl;
std::thread sinetro( track, j, l, parent ) ;
std::cout << "Returned to Node j => " << j << "\tk=> " << k << " From the left" << std::endl;
std::cout << std::endl;
std::cout << "***Enter right : m =>" << m << "\t" << "k => " << k << std::endl;
std::thread dextro( track, m, k, parent);
std::cout << "Returned to Node j => " << j << "\tk=> " << k << " From the right" << std::endl;
std::cout << "**********MERGE**********" << std::endl;
sinetro.join();
dextro.join();
merge(j,l,m,k, parent);
}
}//end namespace
namespace maxpath{
long max(long a, long b)
{
return a > b? a : b ;
}
void Tree::post_fix(){
post_fix(root());
return;
}
void Tree::post_fix(Node * in ) {
std::cout << "\t\t postfix cont..." << std::endl;
current( in ) ;
if(in != nullptr)
{
std::cout << "\tLeft " << std::endl;
post_fix(in->left() );
std::cout << "data => " << in->value() << std::endl;
std::cout << "\tRight " << std::endl;
post_fix (in->right() );
}
return;
}
long Node::find_max(Node * in)
{
long a, b, c;
if(in->left() != nullptr)
{
a = in->left()->max();
}else{
a = 0;
}
if(in->right() != nullptr)
{
b = in->right()->max();
}else{
b = 0;
}
std::cout << "Compare a: " << a << " b: " << b << std::endl;
c = max(a,b);
// std::cout << "Compare c: " << c << " val: " << in->value() << std::endl;
std::cout << " val: " << in->value() << std::endl;
// c = max(c, in->value() );
std::cout << "building max" << std::endl;
std::cout << "subtotal :" << in->max(c + in->value()) << std::endl;
return in->max();
}
long Tree::max_calc(Node * in)
{
long m = 0;
std::cout << "\tStart " << std::endl;
if(in != nullptr)
{
std::cout << "\tLeft" << std::endl;
max_calc(in->left() );
std::cout << "\tDone Left" << std::endl;
// m = in->find_max(in);
std::cout << "Max => " << m << std::endl;
std::cout << "\tRight " << std::endl;
max_calc(in->right() );
m = in->find_max(in);
std::cout << "\tDone Right - going up" << std::endl;
return m;
}
std::cout << "empty node going ... \tUP " << std::endl;
return m;
}
Node * Tree::buildtree ( int pos, const int *d, const int SZ )
{
SIZE(SZ);
Node * temp = nullptr;
if(pos< SIZE() ){
temp = add_node(temp);
temp->left(buildtree ( 2 * pos + 1 , d, SZ) );
temp->value( d[pos] );
temp->right(buildtree ( 2 * pos + 2 , d, SZ) );
}
return temp ;
}
int Tree::create_tree(const int * d, const int SZ ){
Node * new_root = new Node;
std::cout << "Starting the tree building at pos 0"<< std::endl;
new_root = buildtree( 0, d, SZ ) ; //starting in position zero
root(new_root);
return this->node_count();
}
/**************************This is retired code***************************************************
void Tree::build(Node * sin, Node * dex, const int * data, const int SIZE, int pos )
{
std::cout << "Building ... index is: " << pos << std::endl;
std::cout << "current ticket is ... : " << ticket << std::endl;
std::cout << "height is ... : " << height() << std::endl;
if(pos >= SIZE)
return;
//Get a ticket and create a node
//We need at most 4 nodes
std::cout << "Get a ticket" << std::endl;;
int sin_l = (++ticket);
std::cout << "ticket number " << sin_l << std::endl;;
if(sin_l >= SIZE)
return; //No more data
Node * sin_lnode{sin};
sin->left(sin_lnode);
node_count(node_count() + 1 );
sin_lnode->value(data[sin_l]);
sin_lnode->max(data[sin_l]);
sin_lnode->parent()->max( max( sin_lnode->max(), sin_lnode->parent()->max() ) );
std::cout << "sin_lnode add. Number of nodes is ... : " << node_count() << std::endl;
std::cout << "sin_lnode added height is ... : " << height() << std::endl;
std::cout << "Get a ticket" << std::endl;;
int sin_r = (++ticket);
std::cout << "ticket number " << sin_r << std::endl;;
if(sin_r >= SIZE) //only data for one node - fill it and leave
return;
Node * sin_rnode{sin};
sin->right(sin_rnode);
node_count(node_count() + 1 );
sin_rnode->value(data[sin_r]);
sin_rnode->max(data[sin_r]);
sin_rnode->parent()->max( max( sin_rnode->max(), sin_rnode->parent()->max() ) );
std::cout << "sin_rnode add. Number of nodes is ... : " << node_count() << std::endl;
std::cout << "sin_rnode added height is ... : " << height() << std::endl;
std::cout << "Get a ticket" << std::endl;;
int dex_l = (++ticket);
std::cout << "ticket number " << dex_l << std::endl;;
if(dex_l >= SIZE) //only data for one node - fill it and leave
return;
Node * dex_lnode{dex};
dex->left(dex_lnode);
node_count(node_count() + 1 );
dex_lnode->value(data[dex_l]);
dex_lnode->max(data[dex_l]);
dex_lnode->parent()->max( max( dex_lnode->max(), dex_lnode->parent()->max() ) );
std::cout << "dex_lnode add. Number of nodes is ... : " << node_count() << std::endl;
std::cout << "dex_lnode added height is ... : " << height() << std::endl;
std::cout << "Get a ticket" << std::endl;;
int dex_r = (++ticket);
std::cout << "ticket number " << dex_r << std::endl;;
if(dex_r >= SIZE) //only data for one node - fill it and leave
return;
Node * dex_rnode{dex};
dex->right(dex_rnode);
node_count(node_count() + 1 );
dex_rnode->value(data[dex_r]);
dex_rnode->max(data[dex_r]);
dex_rnode->parent()->max( max( dex_rnode->max(), dex_rnode->parent()->max() ) );
std::cout << "dex_rnode add. Number of nodes is ... : " << node_count() << std::endl;
std::cout << "dex_rnode added height is ... : " << height() << std::endl;
if(flag == 1){
flag = -1;
std::cout << "_Green_ Light on left" << std::endl;
build(sin_lnode, sin_rnode, data, SIZE, dex_r );
}
if(flag == 0){
flag = -2;
std::cout << "_Green_ Light on right" << std::endl;
build(dex_lnode, dex_rnode, data, SIZE, dex_r );
}
if(flag == -1)
{
flag = 0;
std::cout << "RETURN Set for Right and Return" << std::endl;
return;
}
if(flag == -2)
{
flag = 1;
std::cout << "RETURN Set for Left and Return" << std::endl;
return;
}
}
**********************************************************************************/
}
--------------28880EA7B9C8B633B134B083
Content-Type: text/x-chdr;
name="maxpath.h"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="maxpath.h"
/*
* =====================================================================================
*
* Filename: max_path.h
*
* Description: Header File for Parrell discovery of the maximum tree
*
* Version: 1.0
* Created: 11/09/2016 04:28:51 AM
* Revision: none
* Compiler: gcc
*
* Author: Ruben Safir
* Company: NYLXS Inc
*
* =====================================================================================
*/
#ifndef MAXPATH
#define MAXPATH
#include
#include
namespace maxpath{
/*
* =====================================================================================
* Class: Node
* Description: Node of a binary tree
* =====================================================================================
*/
class Node
{
public:
/* ==================== LIFECYCLE ======================================= */
Node (): _parent{nullptr}, _left{nullptr}, _right{nullptr}, _value{0},_max{0} {std::cout << "Create a node" << std::endl; }; /* constructor */
Node (Node * par, Node * sin = nullptr, Node * dex = nullptr ): _parent{par}, _left{sin}, _right{dex}
{ value(par->value() ); value(par->max() ); std::cout << "Create a node from a node"<< std::endl;}; /* constructor */
Node ( const Node &other ){ parent(other.parent() ) ; right(other.right()); left(other.left() ); value(other.value() ); max(other.max()); std::cout << "Copy a node" << std::endl; }; /* copy constructor */
~Node (){}; /* destructor */
/* ==================== ACCESSORS ======================================= */
Node * parent() const{
return _parent;
}
Node * left() const{
return _left;
}
Node * right() const{
return _right;
}
long value() const{
return _value;
}
long max() const{
return _max;
}
long find_max(Node * );
Node * parent(Node * in){
_parent = in;
return _parent;
}
Node * left(Node * in){
_left = in;
return _left;
}
Node * right(Node *in){
_right = in;
return _right;
}
long value(int in){
_value = in;
return _value;
}
long max(long in){
_max = in;
return _max;
}
/* ==================== MUTATORS ======================================= */
int max(long x, long y){
return x > y? x: y;
};
/* ==================== OPERATORS ======================================= */
const Node& operator = ( const Node &other ){
std::cout << "copy.. ";
left(other.left());
std::cout << "copy.. ";
right(other.right());
std::cout << "copy.. ";
value(other.value());
std::cout << "copy.. ";
max(other.max());
std::cout << "copy.. " << std::endl;
return * this;
}; /* assignment operator */
/* ==================== DATA MEMBERS ======================================= */
protected:
private:
Node *_parent;
Node *_left;
Node *_right;
long _value;
long _max;
}; /* ----- end of class Node ----- */
/*
* =====================================================================================
* Class: Tree
* Description: A tree of Nodes
* The purpose of this class is to handle tree manipulations and analysis as a whole
* and to give quick assess to specific tree data points
* =====================================================================================
*/
class Tree
{
public:
/* ==================== LIFECYCLE ======================================= */
Tree (Node * rt): _root{rt}, _node_count{0}, _SIZE{0}{ add_node(root()); current(root()); }; /* constructor */
Tree (Node rt): _root{&rt}, _node_count{0}, _SIZE{0}{ add_node(root() );}; /* constructor */
Tree (): _root{nullptr}, _node_count{0}, _SIZE{0}{}; /* constructor */
/* ==================== ACCESSORS ======================================= */
Node* add_node(Node * parent)
{
node_count(node_count() + 1);
if(parent == nullptr){
//std::cout << "creating new node" << std::endl;
parent = new Node;
}
// current(parent);//This needs to be hooked first. left or right? it needs to be hooked f we don't know
//return current();
return parent;
};
void post_fix();
void post_fix(Node *);
long max_calc(Node * in);
Node * current(Node *in)
{
_current = in;
return in;
};
Node * current()
{
return _current;
};
Node* root(){
std::cout << "reading root" << std::endl;
return _root;
};
Node * root(Node in){
std::cout << "adding root" << std::endl;
_root = ∈
// current(_root);
return _root;
};
Node * root(Node * in){
std::cout << "adding root" << std::endl;
_root = in;
// current(_root);
return _root;
};
int SIZE(int in){
_SIZE = in;
return _SIZE;
};
int SIZE(){
return _SIZE;
};
int * dataset(){
return _dataset;
};
int * dataset(int * d){
_dataset = d;
return _dataset;
};
int height(){
// std::cout << "calling from height" << std::endl;
_height = ceil( ( log2(node_count()) ) );
// std::cout << "nodes: " << node_count() << " log " << log2(node_count() ) << std::endl;
// std::cout << "Ceiling: " << ceil( log2(node_count()) ) << std::endl;
// std::cout << "Height calculated to be " << _height << " with " << node_count() << " nodes" << std::endl;
// std::cout << "height says bye" << std::endl;
return _height;
};
int node_count() const{
return _node_count;
};
int node_count(int x){
return _node_count = x;
};
/* ==================== MUTATORS ======================================= */
int create_tree(const int * dataset, const int SIZE);//return node count
//void build(Node * l, Node * r, const int * dataset, const int SIZE, int pos);
Node * buildtree( int , const int * , const int );
/* ==================== OPERATORS ======================================= */
/* ==================== DATA MEMBERS ======================================= */
protected:
private:
Node* _root;
Node* _current;
int _height;
int _node_count;
int * _dataset;
int _SIZE;
}; /* ----- end of class Tree ----- */
int min(int x, int y);
void populate_tree(int j, int k, Node * root);
void track(int , int, int * );
void merge(int j, int l, int m, int k, int * parent);
}
#endif /* ----- #ifndef MSORT_INC ----- */
--------------28880EA7B9C8B633B134B083
Content-Type: text/x-c++src;
name="maxpath_old.cpp"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="maxpath_old.cpp"
#include "maxpath.h"
#include
#include
namespace merge{
int min(int x, int y){
int ret;
x std::cout << x << ":" << y << "==>" << ret << std::endl;
return ret;
}
void merge(int j, int l, int m, int k, int * value){
int size = (k-j) + 1;
std::cout << "Allocating scratch ==>" << size << std::endl;
int * scratch = new int[size];
int l_pos1 = j;
int l_pos2 = l;
int r_pos1 = m;
int r_pos2 = k;
int i = 0;
std::cout << "Scratch index: " << i << std::endl;
std::cout << "l_pos1: " << l_pos1 << "\tr_pos1: " << r_pos1 << std::endl;
std::cout << "l_pos2: " << l_pos2 << "\tr_pos2: " << r_pos2 << std::endl;
int l_next = l_pos1;
int r_next = r_pos1;
int cur = -1;//cursor rest position
int cursor[3] = {cur, l_next, r_next};
while((cursor[1] <= l_pos2) && (cursor[2] <= r_pos2)) {
std::cout << "Positions" << cursor[0] << ":" << cursor[1] << ":" << cursor[2] << std::endl;
std::cout << "Values " << value[cursor[1]] << ":" << value[cursor[2]] << std::endl;
if(value[cursor[1]] <= value[cursor[2]]) {
scratch[i] = value[cursor[1]];
cursor[0] = cursor[1];
cursor[1]++;
}else if(value[cursor[1]] > value[cursor[2]]){
scratch[i] = value[cursor[2]];
cursor[0] = cursor[2];
cursor[2]++;
}
std::cout << "Positions" << cursor[0] << ":" << cursor[1] << ":" << cursor[2] << std::endl;
std::cout << "Values " << value[cursor[1]] << ":" << value[cursor[2]] << std::endl;
i++;
}
//we hit the top
while(1){
std::cout << "clearing data...";
if(cursor[2] <= r_pos2 ){
scratch[i] = value[cursor[2]];
i++;
cursor[2]++;
}else if(cursor[1] <= l_pos2){
scratch[i] = value[cursor[1]];
i++;
cursor[1]++;
}else{
break;
}
}
std::cout << "done" << std::endl;
//copy scratch to the array
std::cout << "copying scratch" << std::endl;
for(int pos = j, i=0; i <= (k-j); pos++, i++){
std::cout << i << " : " << scratch[i] <<" to position " << pos << std::endl;
value[pos] = scratch[i];
}
std::cout << "free scratch" << std::endl;
delete[] scratch;
std::cout << "done with scratch" << std::endl;
return;
}
//j is far left of array
//k is far right of array
//l is middle of array - right of left child array
//m is middle + 1 of the array - left of right child array
//
// j l m k
//_____________________________________
//| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11|
//--------------------------------------
//
void track(int j, int k, int * parent )
{
//std::cout << "\n j is far left of array\n k is far right of array\n l is middle of array - right of left child array\n m is middle + 1 of the array - left of right child array\n\n j l m k\n _____________________________________\n | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11|\n --------------------------------------\n ";
std:: cout << "======================" << std::endl;
std::cout << "|| __NEW NODE__ ||\n|| j =>" << j << " " << "k=> " << k << " ||" << std::endl;
std:: cout << "======================" << std::endl;
int length = k - j;
int l = j + (length / 2);
int m = l + 1;
if(j == k )
{
std::cout << "\n\n\n**********RETURN**********" << std::endl;
return;
}
std::cout << "Left Branch: j =>" << j << "\t" << "l => " << l << std::endl;
std::cout << "Right Branch: m =>" << m << "\t" << "k => " << k << std::endl;
std::cout << std::endl;
std::cout << std::endl;
std::cout << std::endl;
std::cout << "***Enter left : j =>" << j << "\t" << "l => " << l << "***" << std::endl;
std::thread sinetro( track, j, l, parent ) ;
std::cout << "Returned to Node j => " << j << "\tk=> " << k << " From the left" << std::endl;
std::cout << std::endl;
std::cout << "***Enter right : m =>" << m << "\t" << "k => " << k << std::endl;
std::thread dextro( track, m, k, parent);
std::cout << "Returned to Node j => " << j << "\tk=> " << k << " From the right" << std::endl;
std::cout << "**********MERGE**********" << std::endl;
sinetro.join();
dextro.join();
merge(j,l,m,k, parent);
}
}//end namespace
namespace maxpath{
int Tree::ticket = 0;
int Tree::flag = 1;
int max(int a, int b)
{
return a > b? a : b ;
}
int Tree::create_tree(const int * dataset, const int SIZE ){
//We are assuming here that we have at least 3 nodes
//Get a ticket
//I'm going to need to lock this ticket
std::cout << "What is the starting ticket? " << ticket << std::endl;
std::cout << "Initial Index:" << 0 << std::endl;
std::cout << "Initial Height:" << this->height() << std::endl;
this->root()->value(dataset[0]);
this->root()->max(dataset[0]);
//build the first left node
int index = (++ticket);
std::cout << "Index for the left side:" << index << std::endl;
this->node_count(this->node_count() + 1);
this->root()->left(new Node{this->root() });
std::cout << "Node Count after adding left:" << this->node_count() << std::endl;
this->root()->left()->value(dataset[index]);
this->root()->left()->max(dataset[index]);
this->root()->max(this->root()->left()->value() > this->root()->value() ? this->root()->left()->value(): this->root()->value() );
std::cout << "New Height after adding left:" << this->height() << std::endl;
std::cout << "Node Count after adding left:" << this->node_count() << std::endl;
//build the right node
index = (++ticket);
std::cout << "Index for the right side:" << index << std::endl;
if(index >= SIZE){//This shouldn't happen if you have at three nodes to start
int pos = index - 1;
build(this->root()->left(), this->root()->right(nullptr), dataset, SIZE, pos);
return ( this->node_count() );
}
this->node_count(this->node_count() + 1);
this->root()->right(new Node{this->root() });
this->root()->right()->value(dataset[index]);
this->root()->right()->max(dataset[index]);
this->root()->max(this->root()->right()->value() > this->root()->value() ? this->root()->right()->value(): this->root()->value() );
std::cout << "Node Count after adding right:" << this->node_count() << std::endl;
std::cout << "New Height after adding right:" << this->height() << std::endl;
//OK dynamically build the rest
std::cout << "OK dynamically build the rest" << std::endl;
build(this->root()->left(), this->root()->right(), dataset, SIZE, index);
return (this->node_count() );
}
void Tree::build(Node * sin, Node * dex, const int * data, const int SIZE, int pos )
{
std::cout << "Building ... index is: " << pos << std::endl;
std::cout << "current ticket is ... : " << ticket << std::endl;
std::cout << "height is ... : " << height() << std::endl;
if(pos >= SIZE)
return;
//Get a ticket and create a node
//We need at most 4 nodes
std::cout << "Get a ticket" << std::endl;;
int sin_l = (++ticket);
std::cout << "ticket number " << sin_l << std::endl;;
if(sin_l >= SIZE)
return; //No more data
Node * sin_lnode{sin};
sin->left(sin_lnode);
node_count(node_count() + 1 );
sin_lnode->value(data[sin_l]);
sin_lnode->max(data[sin_l]);
sin_lnode->parent()->max( max( sin_lnode->max(), sin_lnode->parent()->max() ) );
std::cout << "sin_lnode add. Number of nodes is ... : " << node_count() << std::endl;
std::cout << "sin_lnode added height is ... : " << height() << std::endl;
std::cout << "Get a ticket" << std::endl;;
int sin_r = (++ticket);
std::cout << "ticket number " << sin_r << std::endl;;
if(sin_r >= SIZE) //only data for one node - fill it and leave
return;
Node * sin_rnode{sin};
sin->right(sin_rnode);
node_count(node_count() + 1 );
sin_rnode->value(data[sin_r]);
sin_rnode->max(data[sin_r]);
sin_rnode->parent()->max( max( sin_rnode->max(), sin_rnode->parent()->max() ) );
std::cout << "sin_rnode add. Number of nodes is ... : " << node_count() << std::endl;
std::cout << "sin_rnode added height is ... : " << height() << std::endl;
std::cout << "Get a ticket" << std::endl;;
int dex_l = (++ticket);
std::cout << "ticket number " << dex_l << std::endl;;
if(dex_l >= SIZE) //only data for one node - fill it and leave
return;
Node * dex_lnode{dex};
dex->left(dex_lnode);
node_count(node_count() + 1 );
dex_lnode->value(data[dex_l]);
dex_lnode->max(data[dex_l]);
dex_lnode->parent()->max( max( dex_lnode->max(), dex_lnode->parent()->max() ) );
std::cout << "dex_lnode add. Number of nodes is ... : " << node_count() << std::endl;
std::cout << "dex_lnode added height is ... : " << height() << std::endl;
std::cout << "Get a ticket" << std::endl;;
int dex_r = (++ticket);
std::cout << "ticket number " << dex_r << std::endl;;
if(dex_r >= SIZE) //only data for one node - fill it and leave
return;
Node * dex_rnode{dex};
dex->right(dex_rnode);
node_count(node_count() + 1 );
dex_rnode->value(data[dex_r]);
dex_rnode->max(data[dex_r]);
dex_rnode->parent()->max( max( dex_rnode->max(), dex_rnode->parent()->max() ) );
std::cout << "dex_rnode add. Number of nodes is ... : " << node_count() << std::endl;
std::cout << "dex_rnode added height is ... : " << height() << std::endl;
if(flag == 1){
flag = -1;
std::cout << "_Green_ Light on left" << std::endl;
build(sin_lnode, sin_rnode, data, SIZE, dex_r );
}
if(flag == 0){
flag = -2;
std::cout << "_Green_ Light on right" << std::endl;
build(dex_lnode, dex_rnode, data, SIZE, dex_r );
}
if(flag == -1)
{
flag = 0;
std::cout << "RETURN Set for Right and Return" << std::endl;
return;
}
if(flag == -2)
{
flag = 1;
std::cout << "RETURN Set for Left and Return" << std::endl;
return;
}
}
}
--------------28880EA7B9C8B633B134B083
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
Learn mailing list
Learn-at-nylxs.com
http://lists.mrbrklyn.com/mailman/listinfo/learn
--------------28880EA7B9C8B633B134B083--
|
|
