March 17, 2012, 12:05 am
A simple, rough and ready, maxheap implementation. It uses an vector as an implicit complete binary tree:
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
class Heap {
public:
Heap() {
store.push_back(0);
}
int l_child(int idx) {
return idx*2;
}
int r_child(int idx) {
return (idx*2)+1;
}
int get_parent(int idx) {
return (idx/2);
}
void insert(int val) {
store.push_back(val);
int idx = store.size()-1;
if(idx == 1) return;
// bubble up
for(;store[get_parent(idx)] < store[idx];) {
int t = store[get_parent(idx)];
store[get_parent(idx)] = val;
store[idx] = t;
idx = get_parent(idx);
if(get_parent(idx) == 0) break;
}
}
void dump() {
cout << "DUMPSTART" << endl;
for(size_t n=0;n<store.size();n++) {
cout << store[n] << endl;
}
cout << "DUMPEND" << endl;
}
int pop() {
int r = store[1];
store[1] = store[store.size()-1];
store.pop_back();
bool min=true;
int idx = 1;
for(;min==true;) {
min=false;
int lidx = l_child(idx);
int ridx = r_child(idx);
int lval;
int rval;
if(lidx < store.size()) lval = store[lidx]; else lval = INT_MIN;
if(ridx < store.size()) rval = store[ridx]; else rval = INT_MIN;
if(store[idx] < lval) { min=true; }
if(store[idx] < rval) { min=true; }
if(!min) break;
int t = store[idx];
if(lval > rval) {
store[idx] = store[l_child(idx)];
store[l_child(idx)] = t;
idx = l_child(idx);
} else {
store[idx] = store[r_child(idx)];
store[r_child(idx)] = t;
idx = r_child(idx);
}
}
return r;
}
vector<int> store;
};
int main() {
vector<int> testdata;
for(size_t n=0;n<10;n++) testdata.push_back(rand()%20);
Heap myheap;
for(size_t n=0;n<testdata.size();n++) myheap.insert(testdata[n]);
cout << "popping heap:" << endl;
for(size_t n=0;n<testdata.size();n++) cout << myheap.pop() << endl;
cout << "sorted testdata:" << endl;
sort(testdata.rbegin(),testdata.rend());
for(size_t n=0;n<testdata.size();n++) cout << testdata[n] << endl;
cout << "second test: " << endl;
Heap myheap2;
for(size_t n=0;n<testdata.size();n++) myheap2.insert(testdata[n]);
for(size_t n=0;n<(testdata.size()/2);n++) cout << myheap2.pop() << endl;
myheap2.insert(100);
myheap2.insert(7);
for(size_t n=0;n<(testdata.size()/2)+2;n++) cout << myheap2.pop() << endl;
}
March 15, 2012, 2:17 am
In (not particularly beautiful) C++, both recursive and non-recursive reverse methods:
#include <iostream>
using namespace std;
class ListItem {
public:
ListItem() : next(NULL)
{}
char data[100];
ListItem *next;
void reverse(ListItem *p) {
if(next == NULL) {
next = p;
} else {
next->reverse(this);
next = p;
}
}
};
class LinkedList {
public:
LinkedList() {}
ListItem *start;
ListItem *end;
ListItem *push_back(char *data) {
ListItem *i = new ListItem();
if(end != NULL) { end->next = i; }
else { start = i; }
for(size_t n=0;n<100;n++) {i->data[n] = data[n];}
end = i;
return i;
}
void reverse() {
start->reverse(NULL);
ListItem *temp = end;
end = start;
start = temp;
}
void reverse_nonrec() {
ListItem *last=NULL;
for(ListItem *p=start;p!=NULL;) {
ListItem *next = p->next;
p->next = last;
last = p;
p = next;
}
ListItem *temp = end;
end = start;
start = temp;
}
void dump() {
for(ListItem *p=start;p!=NULL;p=p->next) {
cout << "data: " << p->data << endl;
}
}
~LinkedList() {
ListItem *op = NULL;
for(ListItem *p=start;p!=NULL;p=p->next) {
if(op != NULL) delete op;
op = p;
}
if(op != NULL) delete op;
}
};
int main() {
LinkedList mylist;
char tempdata[100];
for(size_t n=0;n<100;n++) { tempdata[n] = 'A'; }
tempdata[99] = 0;
for(size_t n=0;n<20;n++) {
mylist.push_back(tempdata);
for(size_t n=0;n<99;n++) { tempdata[n]++; }
}
mylist.dump();
mylist.reverse();
cout << "Reversed List" << endl;
mylist.dump();
cout << "Reverse again" << endl;
mylist.reverse_nonrec();
mylist.dump();
}
March 14, 2012, 1:15 am
#include <vector>
#include <iostream>
using namespace std;
void reverse(vector<int> &seq,int n1,int n2) {
for(;(n2-n1)>=1;) {
int temp = seq[n1]; seq[n1] = seq[n2]; seq[n2]=temp;
n1++;
n2--;
}
}
int main() {
int seq_len=4;
vector<int> seq;
for(int n=0;n<seq_len;n++) {seq.push_back(n);}
for(int n=0;n<seq.size();n++) cout << seq[n] << " ";
cout << endl;
for(int n=0;n<seq_len;n++) {
for(bool final=false;final==false;) {
final=true;
int k=0;
for(int n=0;n<(seq.size()-1);n++) {
if(seq[n] < seq[n+1]) {k=n; final=false;}
}
if(!final) {
int l;
for(int n=k+1;n<seq.size();n++) {
if(seq[k] < seq[n]) {
l=n;
}
}
int temp = seq[k]; seq[k] = seq[l]; seq[l] = temp;
reverse(seq,k+1,seq.size()-1);
for(int n=0;n<seq.size();n++) cout << seq[n] << " ";
cout << endl;
}
}
}
}
March 8, 2012, 1:23 am
shellinabox is a web based terminal client, it’s neat and kind of useful for remote access. However, I don’t much like the default fonts (which are limited by want is available to your browser). I therefore modified it to use the Unifont WOFF I previously generated.
It /kind of/ works. The spacing is still off, and the Unifont WOFF only seems to work in Safari at the moment (it is kind of big!). Anyway, moving to Unifont resolved some of the Kanji rendering artifacts I was having:
You can see that the Hanzi in the first example inserts an extra whitespace above the line. In the second example the Hanzi throws the (s out of alignment, due to the Hanzi width being different than the normal text.
This is the version of shellinthebox modified to use Unifont. As you can see it keeps everything nicely in alignment. There’s also no /extra/ white horizontal line. However, every line now gets a whitespace between it, I need to figure out the css padding issues that are causing this.
You can find my shellinthebox fork on github here.
RSS