March 23, 2012, 11:24 pm
Some more rough and ready algorithm code, non-OO C++. Pretty bad code, not well tested, just playing.
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
using namespace std;
class Node {
public:
Node() {
}
vector<Node *> children;
Node *parent;
};
Node *make_random_tree(size_t size,Node *root=NULL) {
if(root == NULL) {
root = new Node();
}
Node *current = root;
size_t children=rand()%size;
for(size_t i=0;i<children;i++) {
Node *nd = new Node();
nd->parent = current;
current->children.push_back(nd);
}
for(size_t n=0;n<current->children.size();n++) {
make_random_tree(size-children,current->children[n]);
}
return root;
}
Node *get_random(Node *root,size_t avg_size) {
Node *current = root;
for(;rand()%(avg_size*2) != 0;) {
if(current->children.size() == 0) return current;
current = current->children[rand()%current->children.size()];
}
return current;
}
Node * get_next_child(Node *node,Node *child) {
bool next=false;
for(size_t n=0;n<node->children.size();n++) {
if(next==true) {
return node->children[n];
}
if(node->children[n] == child) next=true;
}
return NULL;
}
vector<Node *> get_path(Node *root,Node *n) {
vector<Node *> current_path;
current_path.push_back(root);
if(n==root) return current_path;
Node *current_child = root->children[0];
for(;;) {
current_path.push_back(current_child);
if(current_child == n) return current_path;
if(current_child->children.size() != 0) {
current_path.push_back(current_child->children[0]);
current_child = current_child->children[0];
} else {
current_child = NULL;
for(;current_child == NULL;) {
Node *old_child = current_path[current_path.size()-1];
current_path.erase(current_path.begin()+current_path.size()-1,current_path.end());
current_child = get_next_child(current_path[current_path.size()-1],old_child);
if(old_child==root) { return vector<Node *>(); }
}
}
}
// Should never get here
return vector<Node *>();
}
vector<Node *> get_path_parent(Node *root,Node *n) {
vector<Node *> v;
for(Node *current = n;current != root;current = current->parent) {
v.push_back(current);
}
v.push_back(root);
reverse(v.begin(),v.end());
return v;
}
Node *find_lca_parent(Node *root,Node *n1,Node *n2) {
vector<Node *> path1 = get_path_parent(root,n1);
vector<Node *> path2 = get_path_parent(root,n2);
for(size_t n=0;n<path1.size();n++) {cout << path1[n] << " ";} cout << endl;
for(size_t n=0;n<path2.size();n++) {cout << path2[n] << " ";} cout << endl;
size_t shortest_path_length;
if(path1.size() < path2.size()) shortest_path_length = path1.size();
else shortest_path_length = path2.size();
size_t n;
for(n=0;(n<shortest_path_length) && (path1[n] == path2[n]);n++);
return path1[n-1];
}
Node *find_lca(Node *root,Node *n1,Node *n2) {
vector<Node *> path1 = get_path(root,n1);
vector<Node *> path2 = get_path(root,n2);
size_t shortest_path_length;
if(path1.size() < path2.size()) shortest_path_length = path1.size();
else shortest_path_length = path2.size();
size_t n;
for(n=0;(n<shortest_path_length) && (path1[n] == path2[n]);n++);
return path1[n-1];
}
int main() {
Node *root = make_random_tree(100);
Node *n1 = get_random(root,20);
Node *n2 = get_random(root,20);
Node *lca1a = find_lca_parent(root,n1,n2);
Node *lca1b = find_lca (root,n1,n2);
cout << "LCA1-a: " << lca1a << endl;
cout << "LCA1-b: " << lca1a << endl;
Node *n3 = root->children[0]->children[0]->children[0];
Node *n4 = root->children[0]->children[0]->children[1];
Node *lca2a = find_lca_parent(root,n3,n4);
Node *lca2b = find_lca (root,n3,n4);
cout << "LCA2-a: " << lca2a << endl;
cout << "LCA2-b: " << lca2b << endl;
}
March 20, 2012, 4:42 pm
This is a simple, inefficient implementation of the Burrows-Wheeler transform in C++. I wrote it just to play around with the algorithm, not for any practical application. It takes a single text file as the input, then performs the transform and reverses it:
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
void bwt(string input,string &bwt_str,int &primaryidx) {
vector<string> rotations;
// 1. generate rotations of input
cout << "rotations:" << endl;
for(int n=0;n<input.size();n++) {
string s;
s += input[n];
for(int i=n+1;i!=n;i++) {
if(i==input.size()) i=0;
s += input[i];
if(i==input.size()-1) i=-1;
}
rotations.push_back(s);
cout << s << endl;
}
// 2. sort
cout << "sorted:" << endl;
sort(rotations.begin(),rotations.end());
for(size_t n=0;n<rotations.size();n++) {
cout << rotations[n] << endl;
}
bwt_str.clear();
for(size_t n=0;n<rotations.size();n++) {
bwt_str += rotations[n].substr(rotations[n].size()-1,1);
if(rotations[n] == input) {primaryidx = n;}
}
cout << "bwt string: " << bwt_str << endl;
cout << "primaryidx: " << primaryidx << endl;
}
string rbwt(string bwt_str,int primaryidx) {
vector<string> cur_str;
for(size_t n=0;n<bwt_str.size();n++) {
string s;
s = bwt_str.substr(n,1);
cur_str.push_back(s);
}
for(;cur_str[0].size() < bwt_str.size();) {
vector<string> new_str = cur_str;
sort(new_str.begin(),new_str.end());
for(size_t n=0;n<cur_str.size();n++) {
cur_str[n] = cur_str[n] + new_str[n].substr(new_str[n].size()-1,1);
}
}
cout << "reversed transform:" << endl;
for(size_t n=0;n<cur_str.size();n++) {
cout << cur_str[n] << endl;
}
sort(cur_str.begin(),cur_str.end());
cout << "Original String: " << cur_str[primaryidx] << endl;
return cur_str[primaryidx];
}
int main(int argc,char **argv) {
string s;
ifstream infile(argv[1]);
for(;!infile.eof();) {
char c = (char)infile.get();
if(!infile.eof()) s += string(1,c);
}
cout << "input: " << s << "END" << endl;
string bwt_str;
int primaryidx;
bwt(s,bwt_str,primaryidx);
rbwt(bwt_str,primaryidx);
}
March 20, 2012, 10:24 am
Some quick Javascript which plots random walks from a point…
View it here.
<html>
<head>
<script type="text/javascript">
var ittr=8;
var delta=-0.005;
function draw_frame() {
var canvas = document.getElementById("m_canvas");
if(canvas.getContext) {
var ctx = canvas.getContext("2d");
ctx.lineWidth = 0;
ctx.fillStyle = "rgb(0,0,0)";
var x=250;
var y=250;
for(var n=0;n<200;n++) {
var r=Math.floor(Math.random()*4);
if(r==0) { x+=1; y+=0; }
if(r==1) { x+=0; y+=1; }
if(r==2) { x-=1; y+=0; }
if(r==3) { x-=0; y-=1; }
ctx.fillRect(x*1,y*1,1,1);
}
ctx.fillStyle = "rgb(0,200,200)";
ctx.fillRect(250,250,3,3);
}
}
</script>
</head>
<body onload="setInterval(draw_frame,10);" >
<canvas id="m_canvas" width="500" height="500">You need a Javascipt</canvas>
</body>
</html>
March 18, 2012, 2:55 pm
Another quick and dirty algorithm implementation in C++. This time a Binary search tree (no balancing):
#include <iostream>
#include <vector>
using namespace std;
class Node {
public:
int value;
Node *less;
Node *more;
};
class BinarySearchTree {
public:
BinarySearchTree() : root(NULL) {}
void find_node(int value,Node **findnode,Node **parent) {
*findnode = NULL;
*parent = NULL;
if(root == NULL) {
return;
}
Node *current = root;
for(;;) {
if(current->value == value) {*findnode = current; return;}
if(value < current->value) {
if(current->less != NULL) {*parent = current; current = current->less;}
else {
return;
}
} else {
if(current->more != NULL) {*parent = current; current = current->more;}
else {
return;
}
}
}
}
Node *getr(Node *c,Node **parent) {
*parent = c;
for(;c->more != NULL;) {
*parent = c;
c = c->more;
}
return c;
}
void remove(int value) {
Node *delnode;
Node *parent;
find_node(value,&delnode,&parent);
if(delnode == NULL) return;
// leaf
if((delnode->less == NULL) && (delnode->more == NULL)) {
if(parent->less == delnode) {parent->less = NULL;}
if(parent->more == delnode) {parent->more = NULL;}
delete delnode;
return;
}
// only one child
if((delnode->less == NULL) || (delnode->more == NULL)) {
if(delnode->less != NULL) {
if(parent->less == delnode) {parent->less = delnode->less;}
if(parent->more == delnode) {parent->more = delnode->less;}
delete delnode;
return;
}
if(delnode->more != NULL) {
if(parent->less == delnode) {parent->less = delnode->more;}
if(parent->more == delnode) {parent->more = delnode->more;}
delete delnode;
return;
}
}
// two children
Node *i = getr(delnode->less,&parent);
delnode->value = i->value;
if(parent == i) { delnode->less = NULL;}
if(parent->less == i) { parent->less = NULL; }
else { parent->more = NULL; }
delete i;
}
void insert(int value) {
if(root == NULL) {
Node *n = new Node();
n->value = value;
n->less = NULL;
n->more = NULL;
root = n;
return;
}
Node *current = root;
for(;;) {
if(value < current->value) {
if(current->less != NULL) current = current->less;
else {
Node *n = new Node();
n->value = value;
n->less = NULL;
n->more = NULL;
current->less = n;
break;
}
} else {
if(current->more != NULL) current = current->more;
else {
Node *n = new Node();
n->value = value;
n->less = NULL;
n->more = NULL;
current->more = n;
break;
}
}
}
}
bool exists(int value) {
if(root == NULL) {
return false;
}
Node *current = root;
for(;;) {
if(current->value == value) return true;
if(value < current->value) {
if(current->less != NULL) current = current->less;
else {
return false;
}
} else {
if(current->more != NULL) current = current->more;
else {
return false;
}
}
}
}
Node *root;
};
int main() {
BinarySearchTree s;
vector<int> testdata;
for(size_t n=0;n<10;n++) { testdata.push_back(rand()%20); }
for(size_t n=0;n<10;n++) { s.insert(testdata[n]); }
cout << "testdata: " << endl;
for(size_t n=0;n<10;n++) { cout << testdata[n] << endl; }
cout << "existance check: " << endl;
for(size_t n=0;n<10;n++) { if(s.exists(testdata[n])) cout << "existance: " << testdata[n] << " true" << endl; else cout << "existance: " << testdata[n] << " false" << endl;}
for(size_t n=0;n<10;n++) { if(s.exists(testdata[n]+20)) cout << "existance: " << testdata[n]+20 << " true" << endl; else cout << "existance: " << testdata[n]+20 << " false" << endl;}
cout << "remove: " << testdata[5] << endl;
s.remove(testdata[5]);
if(s.exists(testdata[5])) cout << testdata[5] << " still exists" << endl; else cout << testdata[5] << " no longer exists" << endl;
cout << "remove: " << testdata[3] << endl;
s.remove(testdata[3]);
if(s.exists(testdata[3])) cout << testdata[3] << " still exists" << endl; else cout << testdata[3] << " no longer exists" << endl;
cout << "remove: " << testdata[0] << endl;
s.remove(testdata[0]);
if(s.exists(testdata[0])) cout << testdata[0] << " still exists" << endl; else cout << testdata[0] << " no longer exists" << endl;
}
RSS