/**
* Merge Sort a Linked List
* Anwar Mamat
* anwarmamat@gmail.com
*
*/
#include <iostream>
using namespace std;
/*
* Single Linked List Node
*/
template <typename T>
class Node
{
public:
T data;
Node* next;
Node(const T& d):data(d),next(NULL){};
~Node(){};
};
/*
* Push an item into the linked list. The item is added to the head;
*/
template<typename T>
void pushToLinkedList(Node<T>** head, const T& item)
{
Node<T>* t = new Node<T>(item);
if(*head == NULL){
*head = t;
}
else{
t->next = *head;
*head = t;
}
}
/*
* Print the linked list
*/
template<typename T>
void printLinkedList(Node<T> *head)
{
Node<T> *t = head;
while(t != NULL){
cout << t->data << ", ";
t = t->next;
}
cout << endl;
}
/*
* delete the linked list
*/
template<typename T>
void deleteLinkedList(Node<T> *head)
{
Node<T> *t = NULL;
while(head != NULL)
{
t = head->next;
delete head;
head = t;
}
}
/*
* Split the linked list in half.
* pre: Linked list head
* post: two linked lists. original head: left list.
* returns node pointer to the right list.
*/
template<typename T>
Node<T>* splitLinkedlist(Node<T> *head)
{
if(head == NULL || head->next == NULL)
return head;
Node<T> * fast = head->next;
Node<T> * slow = head;
Node<T> * right = NULL;
while(fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next;
fast = fast->next;
}
right = slow->next;
slow->next = NULL;
return right;
}
/*
* merge two sorted linked lists the return head to the sorted list
*/
template<typename T>
Node<T>* merge(Node<T>* left, Node<T>* right)
{
if(left == NULL)
return right;
if(right == NULL)
return left;
Node<T> *h = NULL;
if(left->data < right->data){
h = left;
left = left->next;
}
else{
h = right;
right = right->next;
}
Node<T>* t = h;
while(left != NULL && right != NULL)
{
if(left->data < right->data){
t->next = left;
left = left->next;
t = t->next;
}
else{
t->next = right;
right = right->next;
t = t->next;
}
}
// if any of the list has remaining nodes
if(left == NULL)
t->next = right;
else
t->next = left;
return h;
}
/*
* merge sort a linked list
*/
template<typename T>
void mergeSort(Node<T>** headref)
{
Node<T>* head= *headref;
if(head == NULL || (head)->next == NULL)
return;
Node<T>* left = head;
Node<T>* right = splitLinkedlist(left);
mergeSort(&left);
mergeSort(&right);
*headref = merge(left, right);
}
int main()
{
Node<int>* head = NULL;
pushToLinkedList(&head, 5);
pushToLinkedList(&head, 15);
pushToLinkedList(&head, 11);
pushToLinkedList(&head, 8);
pushToLinkedList(&head, 17);
pushToLinkedList(&head, -1);
pushToLinkedList(&head, 4);
pushToLinkedList(&head, 20);
pushToLinkedList(&head, 11);
/*
Node<string>* head = NULL;
pushToLinkedList(&head, string("David"));
pushToLinkedList(&head, string("Alice"));
pushToLinkedList(&head, string("Bob"));
*/
cout << "Original List:";
printLinkedList(head);
mergeSort(&head);
cout << "Sorted List:";
printLinkedList(head);
deleteLinkedList(head);
return 0;
}
Wednesday, May 22, 2013
Merge Sort a Linked List
Saturday, December 29, 2012
Uyghur typesetting in Latex
XeTeX now supports Arabic typesetting. It means you can typeset Uyghur in Latex. It is not as good as the professional typesetting systems. But it definitely looks much better than the MS word typesetting. I made a sample. Here is link: Uyghur typesetting in Latex. Enjoy.
Saturday, December 22, 2012
Uyghur Latin Alphabet to Uyghur Alphabet converter
There are many websites and blogs that use Uyghur Latin Alphabet. I can read Uyghur Latin Alphabaet, but very slowly. It makes me dizzy if I read more than a page. So I wrote this simple convertor, which converts Uyghur Latin Text to Uyghur (arabic) text. The javascript source code is available at http://cis.temple.edu/~anwar/code/latin2uyghur.html
Thursday, December 13, 2012
Incetercept Java Keyboard event: Uyghur Input TextBox
I intercepted the keyboard input in Java JTextField and replaced the keycode with corresponding Uyghur Unicode letters. You can directly type Uyghur in Java forms using this class. You don't need system level Uyghur input methods. You don't have to switch between input methods even if you have system supported Uyghur input method.
This class can also be used to filter some keyboard inputs, such as numbers, or punctuations.
Here is the UyghurTextEdit class code:
UyghurTextEdit NetBeans Project
Jar File:
UyghurTextEdit.jar
Source Code of the class and test file.
UyghurTextEdit.java
UyghurTextBoxTest.java
This class can also be used to filter some keyboard inputs, such as numbers, or punctuations.
UyghurTextEdit NetBeans Project
Jar File:
UyghurTextEdit.jar
Source Code of the class and test file.
UyghurTextEdit.java
UyghurTextBoxTest.java
Sunday, April 15, 2012
Sort linked list
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define N 12 //number of elements in the array
typedef bool (*CompareFunction)(void *, void *);
typedef struct Node{
int data;
char str[20];
struct Node * next;
} Node;
/*
* create a linked list from an array of elements
*/
void createLinkedList(int array[], int length, Node **head)
{
int i;
Node *current;
Node *p;
if(length == 0)
return ;//;NULL;
for(i = 0; i < length; i++)
{
if(i == 0)
{
*head = (Node*) malloc(sizeof(Node));
(*head)->data = array[i];
snprintf((*head)->str, 10,"%d",array[i]);
(*head)->next = NULL;
current = *head;
}
else
{
p = (Node*) malloc(sizeof(Node));
p->data = array[i];
snprintf(p->str, 10, "%d", array[i]);
p->next = NULL;
current->next = p;
current = p;
}
}
}
/*
* integer compare
*/
bool compareint(void *a, void *b)
{
int x = *(int*)a;
int y = *(int*)b;
return (x > y);
}
/*
* string compare
*/
bool comparechar(void *a, void *b)
{
char *x = (char*)a;
char *y = (char*)b;
return strcmp(x, y) < 0 ? 1:0;
}
/*
* print the linked list
*/
void printLinkedList(Node *head)
{
Node *p = head;
while(p != NULL)
{
printf("(%d,", p->data);
printf("%s),", p->str);
p=p->next;
}
printf("\n");
}
bool sort(Node **head, CompareFunction cmpFunc)
{
Node *s = *head; //start node
Node *t = s->next; //iterating node
Node *t_parent = s; //parent of iterating node
Node *index = NULL; // max or min node index
Node *index_parent = NULL;
Node *current = NULL;
//iterate all nodes
while(s->next != NULL)
{
index = s;
t = s->next;
t_parent = s;
// find the max/min node
while( t != NULL)
{
if(cmpFunc(&(index->data), &(t->data)))
{
index = t;
index_parent = t_parent;
}
t_parent = t;
t = t->next;
}
//printf("index=%d\t,", index->data);
//move the seletced max/min to sorted list
if(current == NULL)
{
current = index;
*head = current;
}
else
{
current->next = index;
current = current->next;
}
//remove the selected node from the unsorted list
if(index == s)
s = s->next;
else
index_parent->next = index->next;
current->next = NULL;
}
//add the last single node in the original list to the sorted list
if(current != NULL)
current->next = s;
return true;
}
int main()
{
int array[N]={10,4,2,11,4,8,7,3,5,9,-1,2};
Node *root;
createLinkedList(array, N, &root);
printLinkedList(root);
sort(&root, &compareint);
printf("Sorted List\n");
printLinkedList(root);
return 0;
}
Integer Expression Evaluator code
/*
* Expression evaluator. It supports +,-,*,/ and (), and integers.
* Example: 2*((5+4)/2)*6=48
* This code does not evaluate unary expression, such as -1
*
*/
#include <iostream>
#include <stack>
using namespace std;
enum OPR{ADD='+', SUB='-', MUL='*', DIV='/', PAR='('};
int eval(const string &exp);
int calc(int, int, OPR);
int rank(OPR r1);
int main(int argc, char *argv[])
{
string exp;
if(argc > 1)
exp = argv[1];
else
exp = "2*((5+4)/2)*6+(2)";
int result = eval(exp);
cout << exp << "=" << result << endl;
}
/*
* Evaluates a math expression
*/
int eval(const string & exp)
{
stack<int> Opd; //stack for operands
stack<OPR> Opr; //stack for operators
int opd1;
int opd2;
OPR opr1;
int result = 0;
int i = 0;
int Len = exp.length();
for(i = 0; i < Len; i++)
{
//end of a parentheses
if(exp[i] == ')')
{
while(Opr.top() != PAR) //If last pushed opeator is not (, then evaluate
{
opr1 = Opr.top();
Opr.pop();
opd1 = Opd.top();
Opd.pop();
opd2 = Opd.top();
Opd.pop();
Opd.push(calc(opd1,opd2,opr1));
}
Opr.pop(); // pop '('
}
else if(isdigit(exp[i])) //if a number, push to operand stack
{
Opd.push(exp[i] - '0');
}
else
{
//If current element is an operator, and operator stack is not empty
//compare their precedence.
if(!Opr.empty())
{
opr1 = Opr.top();
if(opr1 != '(' && rank(opr1) >= rank(static_cast<OPR>(exp[i])) )
{
opd1 = Opd.top();
Opd.pop();
opd2 = Opd.top();
Opd.pop();
result = calc(opd1,opd2, opr1);
Opr.pop();
Opd.push(result);
}
}
Opr.push(static_cast<OPR>(exp[i]));
}
}
//Evaluate the last binary expression remainig in the stack
while(!Opr.empty())
{
opr1 = Opr.top();
Opr.pop();
opd1 = Opd.top();
Opd.pop();
opd2 = Opd.top();
Opd.pop();
Opd.push(calc(opd1,opd2,opr1));
}
return Opd.top();
}
/*
* Evaluates an binary expression such as 1+2
*/
int calc(int opd1, int opd2, OPR opr1)
{
int c;
switch(opr1)
{
case ADD:
c = opd2 + opd1; break;
case SUB:
c = opd1 - opd2; break;
case MUL:
c = opd1 * opd2; break;
case DIV:
c = opd2 / opd1; break;
}
return c;
}
/*
* Operator Precedence
*/
int rank(OPR opr1)
{
int r = 0;
switch(opr1)
{
case ADD:
case SUB:
r = 1; break;
case MUL:
case DIV:
r = 2; break;
case PAR:
r = 3; break;
}
return r;
}
Saturday, January 7, 2012
C++ Trie
/*
* Name: Trie
* Author: Anwar Mamat
* Date: 12/2011
*/
#include <iostream>
#include <vector>
using namespace std;
/*
* Trie Node
*/
class Node{
public:
Node(){ mContent=' '; marker=false; mPrefix = 1;}
~Node(){}
Node* findChild(char c) const ;
void addChild(Node * child) {children.push_back(child);}
void setMarker(bool t){marker=t;}
bool getMarker() const {return marker;}
char content() const {return mContent;}
void setContent(char c) { mContent = c;}
void setPrefix(int p){mPrefix = p;}
int getPrefix() {return mPrefix;}
int countChild() const {return children.size();}
bool deleteChild(char c);
Node * getChild(int index){
rd">if(index >=0 && index < countChild())
="kwrd">return children[index];
}
else
}
return NULL;
}
void setChild(Node *t, int index){
if(index>=0 && index< countChild())
children[index]=t;
}
private:
char mContent;
bool marker;
vector<Node*> children;
int mPrefix; //how many words this node prefixes
};
ostream& operator << (ostream& output, Node & node)
{
output << node.content();
return output;
}
/*
* Trie class
*/
class Trie
{
public:
Trie(){root = new Node();}
~Trie();
void addWord(const string & word);
bool findWord(const string & word) const;
bool deleteWord(const string & word);
void print() const;
void sort() const;
private:
Node *root;
void printWords(Node*, char *, int length) const;
void sortTrie(Node *) const;
void deleteSubTrie(Node *);
};
/*
Sort the trie words in alaphabetic order
*/
void Trie::sort() const
{
sortTrie(root);
}
void Trie::sortTrie(Node *current) const
{
int i;
int j;
Node *t;
//sort the children of current node level
for(i = 0; i < current->countChild()-1; i++)
for(j=i+1; j < current->countChild(); j++)
if(current->getChild(i)->content() > current->getChild(j)->content())
{
t = current->getChild(i);
current->setChild(current->getChild(j), i);
current->setChild(t, j);
}
//recursively sort children
for(i = 0; i < current->countChild(); i++)
{
sortTrie(current->getChild(i));
}
}
/*
* Enumerate all words in the trie
*/
void Trie::print() const
{
char word[256]={""};
printWords(root,word, 0);
}
void Trie::printWords(Node *current, char *word, int index) const
{
int i;
if(current == root)
index = 0;
for(i = 0; i < current->countChild(); i++)
{
Node *child = current->getChild(i);
word[index] = child->content();
if(child->getMarker())
{
word[index+1]='\0';
cout << word << endl;
}
printWords(child, word, index+1);
}
}
/*
* Trie deconstructor
*/
Trie::~Trie()
{
deleteSubTrie(root);
}
/*
* delete a child of a node
*/
bool Node::deleteChild(char c)
{
int i;
for(i = 0; i < children.size(); i++){
if(children[i]->content() == c)
children.erase(children.begin() + i);
}
}
/*
* Find a child of a node
* input: single char
* return: child if exists, NULL if does not exist
*/
Node* Node::findChild(char c) const
{
int i;
for(i=0; i < children.size(); i++)
if(children[i]->content() == c)
return children[i];
return NULL;
}
/*
*
* Add a word to the trie
*/
void Trie::addWord(const string & word)
{
int i;
char c;
Node *current= root;
if(word.length() == 0)
{
current->setMarker(true);
return;
}
for(i=0; i < word.length(); i++)
{
Node* child = current->findChild(word[i]);
if(child != NULL)
{
child->setPrefix(child->getPrefix() + 1);
current = child;
}
else
{
Node * tmp = new Node();
tmp->setContent(word[i]);
current->addChild(tmp);
current = tmp;
}
if(i == word.length() - 1 )
{
current->setMarker(true);
}
}
}
/*
* delete a sub trie
*/
void Trie::deleteSubTrie(Node *current)
{
for(int i = 0; i < current->countChild(); i++)
{
deleteSubTrie(current->getChild(i));
}
delete current;
}
/*
* Find a word from the trie
*/
bool Trie::findWord(const string & word) const
{
Node *current = root;
int i;
for(i = 0; i < word.length(); i++)
{
current = current->findChild(word[i]);
if(current == NULL)
return false;
}
if(current->getMarker())
return true;
else
return false;
}
/*
* delete a word from the trie
*/
bool Trie::deleteWord(const string & word)
{
//if the word exists
if(!findWord(word))
return false;
Node *current = root;
int i;
for(i = 0; i < word.length(); i++)
{
Node* child = current->findChild(word[i]);
//cout << *child << " \t" <<child->getPrefix() << endl;
if (child == NULL)
return false;
else if(child->getPrefix() == 1)
{
current->deleteChild(child->content());
deleteSubTrie(child);
return true;
}
else
{
child->setPrefix(child->getPrefix() - 1);
current = child;
}
}
//remove the word marker
current->setMarker(false);
}
int main()
{
Trie *t = new Trie();
t->addWord("BOB");
t->addWord("ABCDEF");
t->addWord("ABCD");
t->print();
t->sort();
cout << "After sort" << endl;
t->print();
t->deleteWord("ABCD");
cout << "ABCD is deleted" << endl;
t->print();
//cout << "delete tree" << endl;
delete(t);
t = NULL;
}
Subscribe to:
Posts (Atom)
