I have invented the fastest string search algorithm. It is called ""Choudhary String Search Algorithm (choudharyStringSearchAlgorithm)"". I have compared my algorithm with Brute Force Algorithm, Boyer Moore Algorithm, Rabin Karp Algorithm, and Knuth Morris Pratt Algorithm and my algorithm is the fastest.
You can copy this code and compile and run and see the results.
Can someone do the code review please. The code is below:
Fastest_String_Search_Algorithm.java
import java.math.BigInteger;
import java.util.*;
import java.io.*;
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
class Algo {
String name;
int numTimesCameFastest;
long timeTaken;
Algo(String name, int num, long timeTaken) {
this.name = name;
this.numTimesCameFastest = num;
this.timeTaken = timeTaken;
} // end of Algo constructor
} // end of Algo
public class Fastest_String_Search_Algorithm {
static int numAlgos = 5;
static int ASIZE = 256;
static LinkedHashMap<String, Algo> algoMap = new LinkedHashMap<String, Algo>();
/*
* Brute Force algorithm
*/
public static int bruteForceStringSearchAlgorithm(char[] text, char[] pattern) {
int n = text.length;
int m = pattern.length;
//brute force it -- loop over all characters in text O(n)
for (int i = 0; i <= n - m; i++) { //index into the text
//loop over all characters in pattern while characters match O(m)
int k = 0; //index into the pattern
while (k < m && text[i + k] == pattern[k]) {
k++;
}
//if at end of pattern, then found match starting at index i in text
if (k == m) {
return i;
}
} // end of for loop
return -1;
} // end of bruteForceStringSearchAlgorithm
/*
* Boyer Moore algorithm
*/
public static void preBmBc(char[] pattern, int m, int[] bmBc) {
int i = 0;
for (i = 0; i < ASIZE; ++i) {
bmBc[i] = m;
}
for (i = 0; i < m - 1; ++i) {
bmBc[pattern[i]] = m - i - 1;
}
} // end of preBmBc
public static void suffixes(char[] pattern, int m, int[] suff) {
int f = 0;
int g = 0;
int i = 0;
suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g) {
suff[i] = suff[i + m - 1 - f];
} else {
if (i < g) {
g = i;
}
f = i;
while (g >= 0 && pattern[g] == pattern[g + m - 1 - f]) {
--g;
}
suff[i] = f - g;
}
}
} // end of suffixes
public static void preBmGs(char[] pattern, int m, int[] bmGs) {
int i = 0;
int j = 0;
int[] suff = new int[m];
suffixes(pattern, m, suff);
for (i = 0; i < m; ++i) {
bmGs[i] = m;
}
j = 0;
for (i = m - 1; i >= 0; --i) {
if (suff[i] == i + 1) {
for (; j < m - 1 - i; ++j) {
if (bmGs[j] == m) {
bmGs[j] = m - 1 - i;
}
}
}
}
for (i = 0; i <= m - 2; ++i) {
bmGs[m - 1 - suff[i]] = m - 1 - i;
}
} // end of preBmGs
public static int boyerMooreStringSearchAlgorithm(char[] text, char[] pattern) {
int i = 0;
int j = 0;
int m = pattern.length;
int n = text.length;
int[] bmGs = new int[m];
int[] bmBc = new int[ASIZE];
/* Preprocessing */
preBmGs(pattern, m, bmGs);
preBmBc(pattern, m, bmBc);
/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; (i >= 0) && (pattern[i] == text[i + j]); --i);
if (i < 0) {
return j;
} else {
j = j + ((bmGs[i] > (bmBc[text[i + j]] - m + 1 + i)) ? bmGs[i] : (bmBc[text[i + j]] - m + 1 + i));
}
}
return -1;
} // end of boyerMooreStringSearchAlgorithm
/*
* Rabin Karp algorithm
*/
public static int rabinKarpStringSearchAlgorithm(char[] text, char[] pattern) {
int patternSize = pattern.length; // m
int textSize = text.length; // n
long prime = (BigInteger.probablePrime((Integer.SIZE - Integer.numberOfLeadingZeros(patternSize)) + 1, new Random())).longValue();
long r = 1;
for (int i = 0; i < patternSize - 1; i++) {
r *= 2;
r = r % prime;
}
long[] t = new long[textSize];
t[0] = 0;
long pfinger = 0;
for (int j = 0; j < patternSize; j++) {
t[0] = (2 * t[0] + text[j]) % prime;
pfinger = (2 * pfinger + pattern[j]) % prime;
}
int i = 0;
boolean passed = false;
int diff = textSize - patternSize;
for (i = 0; i <= diff; i++) {
if (t[i] == pfinger) {
passed = true;
for (int k = 0; k < patternSize; k++) {
if (text[i + k] != pattern[k]) {
passed = false;
break;
}
}
if (passed) {
return i;
}
}
if (i < diff) {
long value = 2 * (t[i] - r * text[i]) + text[i + patternSize];
t[i + 1] = ((value % prime) + prime) % prime;
}
}
return -1;
} // end of rabinKarpStringSearchAlgorithm
/*
* Knuth Morris Pratt algorithm
*/
public static int[] KnuthMorrisPrattShift(char[] pattern) {
int patternSize = pattern.length;
int[] shift = new int[patternSize];
shift[0] = 1;
int i = 1, j = 0;
while ((i + j) < patternSize) {
if (pattern[i + j] == pattern[j]) {
shift[i + j] = i;
j++;
} else {
if (j == 0) {
shift[i] = i + 1;
}
if (j > 0) {
i = i + shift[j - 1];
j = (((j - shift[j - 1]) > 0) ? (j - shift[j - 1]) : 0);
} else {
i = i + 1;
j = 0;
}
}
}
return shift;
} // end of KnuthMorrisPrattShift
public static int knuthMorrisPrattStringSearchAlgorithm(char[] text, char[] pattern) {
int patternSize = pattern.length; // m
int textSize = text.length; // n
int i = 0, j = 0;
int[] shift = KnuthMorrisPrattShift(pattern);
while ((i + patternSize) <= textSize) {
while (text[i + j] == pattern[j]) {
j += 1;
if (j >= patternSize) {
return i;
}
}
if (j > 0) {
i += shift[j - 1];
j = (((j - shift[j - 1]) > 0) ? (j - shift[j - 1]) : 0);
} else {
i++;
j = 0;
}
}
return -1;
} // end of knuthMorrisPrattStringSearchAlgorithm
/*
* Choudhary algorithm
*/
public static int choudharyStringSearchAlgorithm(char[] text, char[] pattern) {
int i = 0;
int j = 0;
int text_len = text.length;
int pattern_len = pattern.length;
int pi_44 = pattern_len - 1;
int[] skip_table = new int[ASIZE];
// preprocess pattern and fill skip_table
for (i = 0; i < ASIZE; i++) {
skip_table[i] = -1;
}
for (i = 0; i < pattern_len; i++) {
skip_table[pattern[i]] = pattern_len - 1 - i;
}
// now search
for (i = 0; i < text_len; i++) {
if ((text_len - i) < pattern_len) {
return -1;
}
if (pattern[pi_44] != text[i + pi_44]) {
if (skip_table[(int) (text[i + pi_44])] == -1) { // this character doesn't occur in pattern, so skip
i = i + pi_44;
} else if (skip_table[(int) (text[i + pi_44])] > 0) {
i = i + skip_table[(int) (text[i + pi_44])] - 1;
}
continue;
}
for (j = pi_44 - 1; j >=0; j--) {
if (pattern[j] != text[i + j]) {
if (skip_table[(int) (text[i + j])] == -1) { // this character doesn't occur in pattern, so skip
i = i + j;
}
break;
}
} // end of inner for loop
if (j == -1) { //string matched
return i;
}
} // end of outer for loop
return -1;
} // end of choudharyStringSearchAlgorithm
public static Algo getFastestAlgoEntryFromMap() {
Algo tmpAlgo = null;
Algo fastestAlgo = algoMap.get("BruteForce");
for (Map.Entry<String, Algo> entry : algoMap.entrySet()) {
tmpAlgo = entry.getValue();
if (tmpAlgo.timeTaken < fastestAlgo.timeTaken) {
fastestAlgo = tmpAlgo;
}
}
return fastestAlgo;
} // end of getFastestAlgoEntryFromMap
public static void initializeTimeTakenOfAllMapEntries() {
for (Map.Entry<String, Algo> entry : algoMap.entrySet()) {
entry.getValue().timeTaken = 0;
}
} // end of initializeTimeTakenOfAllMapEntries
public static void initializeNumTimesCameFastestOfAllMapEntries() {
for (Map.Entry<String, Algo> entry : algoMap.entrySet()) {
entry.getValue().numTimesCameFastest = 0;
}
} // end of initializeNumTimesCameFastestOfAllMapEntries
public static void initializeAlgoMap() {
algoMap.put("BruteForce", new Algo("Brute Force", 0, 0));
algoMap.put("BoyerMoore", new Algo("Boyer Moore", 0, 0));
algoMap.put("RabinKarp", new Algo("Rabin Karp", 0, 0));
algoMap.put("KnuthMorrisPratt", new Algo("KnuthMorrisPratt", 0, 0));
algoMap.put("Choudhary", new Algo("Choudhary", 0, 0));
} // end of initializeAlgoMap
public static void main(String[] args) {
Console c = new Console();
c.createAndShowConsole();
Console.jf.setTitle("Console");
Algo tmpAlgo = null;
int correctIndex = -1;
int index = -1;
long startTime = 0;
long endTime = 0;
String text = "This past summer, I had the privilege of participating in the University of Notre Dame's Research Experience for Undergraduates (REU) program . Under the mentorship of Professor Wendy Bozeman and Professor Georgia Lebedev from the department of Biological Sciences, my goal this summer was to research the effects of cobalt iron oxide cored (CoFe2O3) titanium dioxide (TiO2) nanoparticles as a scaffold for drug delivery, specifically in the delivery of a compound known as curcumin, a flavonoid known for its anti-inflammatory effects. As a high school student trying to find a research opportunity, it was very difficult to find a place that was willing to take me in, but after many months of trying, I sought the help of my high school biology teacher, who used his resources to help me obtain a position in the program. Using equipment that a high school student could only dream of using, I was able to map apoptosis (programmed cell death) versus necrosis (cell death due to damage) in HeLa cells, a cervical cancer line, after treating them with curcumin-bound nanoparticles. Using flow cytometry to excite each individually suspended cell with a laser, the scattered light from the cells helped to determine which cells were living, had died from apoptosis or had died from necrosis. Using this collected data, it was possible to determine if the curcumin and/or the nanoparticles had played any significant role on the cervical cancer cells. Later, I was able to image cells in 4D through con-focal microscopy. From growing HeLa cells to trying to kill them with different compounds, I was able to gain the hands-on experience necessary for me to realize once again why I love science. Living on the Notre Dame campus with other REU students, UND athletes, and other summer school students was a whole other experience that prepared me for the world beyond high school. For 9 weeks, I worked, played and bonded with the other students, and had the opportunity to live the life of an independent college student. Along with the individually tailored research projects and the housing opportunity, there were seminars on public speaking, trips to the Fermi National Accelerator Laboratory, and one-on-one writing seminars for the end of the summer research papers we were each required to write. By the end of the summer, I wasn't ready to leave the research that I was doing. While my research didn't yield definitive results for the effects of curcumin on cervical cancer cells, my research on curcumin-functionalized CoFe2O4/TiO2 core-shell nanoconjugates indicated that there were many unknown factors affecting the HeLa cells, and spurred the lab to expand their research into determining whether or not the timing of the drug delivery mattered and whether or not the position of the binding site of the drugs would alter the results. Through this summer experience, I realized my ambition to pursue a career in research. I always knew that I would want to pursue a future in science, but the exciting world of research where the discoveries are limitless has captured my heart. This school year, the REU program has offered me a year-long job, and despite my obligations as a high school senior preparing for college, I couldn't give up this offer, and so during this school year, I will be able to further both my research and interest in nanotechnology. I believe that humans will always have the ability to rise above any situation, because life is what you make of it. We don't know what life is or why we are in this world; all we know, all we feel, is that we must protect it anyway we can. Buddha said it clearly: \"Life is suffering.\" Life is meant to be challenging, and really living requires consistent work and review. By default, life is difficult because we must strive to earn happiness and success. Yet I've realized that life is fickler than I had imagined; it can disappear or change at any time. Several of my family members left this world in one last beating symphony; heart attacks seem to be a trend in my family. They left like birds; laughing one minute and in a better place the next. Steve Jobs inspired me, when in his commencement address to Stanford University in 2005, he said \\\"Your time is limited, so don't waste it living someone else's life. Don't be trapped by dogma--which is living with the results of other people's thinking.\\\" I want to make mistakes, because that is how I learn; I want to follow the beat of my own drum even if it is \\\"out of tune.\\\" The important thing is to live without regrets, so when my heart ceases to beat, it will make one last happy note and move on. I want to live my life daily. Every day I want to live. Every morning when I wake up, I want to be excited by the gift of a new day. I know I am being idealistic and young, and that my philosophy on life is comparable to a calculus limit; I will never reach it. But I won't give up on it because, I can still get infinitely close and that is amazing. Every day is an apology to my humanity; because I am not perfect, I get to try again and again to \\\"get it right.\\\" I breathe the peace of eternity, knowing that this stage is temporary; real existence is continuous. The hourglass of life incessantly trickles on and we are powerless to stop it. So, I will forgive and forget, love and inspire, experience and satire, laugh and cry, accomplish and fail, live and die. This is how I want to live my life, with this optimistic attitude that every day is a second chance. All the time, we have the opportunity to renew our perspective on life, to correct our mistakes, and to simply move on. Like the phoenix I will continue to rise from the ashes, experienced and renewed. I will not waste time for my life is already in flux. In all its splendor The Phoenix rises In a burst of orange and yellow It soars in the baby blue sky Heading to that Great Light Baptized in the dance of time Fearless, eternal, beautiful It releases a breathtaking aurora And I gasp at the enormity In most conventional classrooms, we are taught to memorize material. We study information to regurgitate it on a test and forget it the following day. I thought this was learning. But this past summer, I realized I was wrong. I attended the SPK Program, a five-week enrichment program with New Jersey's best and brightest students. I lived on a college campus with 200 students and studied a topic. I selected Physical Science. On the first day of class, our teacher set a box on the table and poured water into the top, and nothing came out. Then, he poured more water in, and everything slowly came out. We were told to figure out what had happened with no phones or textbooks, just our brains. We worked together to discover in the box was a siphon, similar to what is used to pump gas. We spent the next weeks building solar ovens, studying the dynamic of paper planes, diving into the content of the speed of light and space vacuums, among other things. We did this with no textbooks, flashcards, or information to memorize. During those five weeks, we were not taught impressive terminology or how to ace the AP Physics exam. We were taught how to think. More importantly, we were taught how to think together. Learning is not memorization or a competition. Learning is working together to solve the problems around us and better our community. To me, learning is the means to a better future, and that's exciting. As I sip a mug of hot chocolate on a dreary winter's day, I am already planning in my mind what I will do the next summer. I briefly ponder the traditional routes, such as taking a job or spending most of the summer at the beach. However, I know that I want to do something unique. I am determined to even surpass my last summer, in which I spent one month with a host family in Egypt and twelve days at a leadership conference in New York City The college courses I have taken at Oregon State University since the summer after 7th grade will no longer provide the kind of challenge I seek. Six months later, I step off the airplane to find myself surrounded by palm trees, with a view of the open-air airport. I chuckle to myself about the added bonus of good weather, but I know I have come to Palo Alto, California, with a much higher purpose in mind. I will spend six weeks here in my glory, not only studying and learning, but actually pursuing new knowledge to add to the repertoire of mankind. Through the Stanford Institutes of Medicine Summer Research Program, I will earn college credit by conducting original molecular biology research, writing my own research paper, and presenting my findings in a research symposium. I decided to spend my summer doing research because I knew that I liked scientific thought, and that I would passionately throw myself into any new challenge. I always want to know more - to probe deeper into the laws of the universe, to explore the power and beauty of nature, to solve the most complicated problems. I have an insatiable curiosity and a desire to delve deeper down in the recesses of my intellect. At the Summer Research Program, I found out how much I enjoy thinking critically, solving problems, and applying my knowledge to the real world. While pursuing research in California, I was also able to meet many similarly motivated, interesting people from across the United States and abroad. As I learned about their unique lifestyles, I also shared with them the diverse perspectives I have gained from my travel abroad and my Chinese cultural heritage. I will never forget the invaluable opportunity I had to explore California along with these bright people. I could have easily chosen to spend that summer the traditional way; in fact, my parents even tried to persuade me into taking a break. Instead, I chose to do molecular biology research at Stanford University. I wanted to immerse myself in my passion for biology and dip into the infinitely rich possibilities of my mind. This challenge was so rewarding to me, while at the same time I had the most fun of my life, because I was able to live with people who share the same kind of drive and passion as I do. I held my breath as my steady hands gently nestled the crumbly roots of the lettuce plant into the soil trench that I shoveled moments before. Rainwater and sweat dripped from my brow as I meticulously patted and pressed the surrounding earth, stamping the leafy green creature into its new home. After rubbing the gritty soil off of my hands, I looked at Brian, a co-volunteer and nonverbal 20-year-old with autism, who extended his arm for a high-five. In the year that I've been working with him, I've watched him revel in planting, nurturing, and eventually harvesting his veggies, especially the grape tomatoes, which we enjoy eating fresh off the vine! Upon walking to the next row of hollowed cavities, we were not contemplating the lengthy work that lay ahead, but rather, we sought to liberate the helpless lettuces, imprisoned in produce cartons that were too small for them to grow in. Finally, after taking a step back to admire the day's last plant, my chest swelled as a wave of contentment flushed through my body. My love for gardening began when I moved to Georgia during my sophomore year. In the time I've spent learning how to garden, I've developed an affinity for watching my vegetables grow to maturity, eager to be harvested and sold at the Saturday market. Though many see gardening as tedious busywork, I find it meditative, as I lose track of time while combining peat moss and soil in the garden's compost mixer. Saturday morning garden work has become a weekend ritual, ridding me of all extraneous responsibilities. My body goes into autopilot as I let my mind wander. I don't actively focus on focusing, but rather I observe myself internally digest the week's events. I'm a bystander to fireworks of thought that explode in my mind as my perception of important matters becomes trivial. Sometimes, it's the physics midterm that suddenly seems less daunting or the deadlines I need to meet for my Spanish project that push back farther. Other times, I contemplate alternative endings to conversations or make perfect sense of the calculus answer that was at the tip of my tongue in class. I met Brian, a close friend of mine who also basks in the tranquility of nature, through my gardening endeavors. While we aren't able to communicate verbally, we speak the language of earth, water, peat, and seedlings. He doesn't speak with words, but his face tells stories of newly found purpose and acceptance, a pleasant contrast to the typical condescension and babying he feels by those who don't think he's capable of independent thought. Throughout my time in the garden with Brian, I began to understand that he, like everyone, has a particular method of communicating. There are the obvious spoken languages, body languages, facial expressions, and interactions we share on a day-to-day basis that reflect who we are and communicate what we represent. Brian expresses himself through various manifestations of unspoken language that he uses to signal how he feels or what he wants. But the nuanced combinations of different methods of communicating are oftentimes overlooked, raising a barrier to mutual understanding that prevents one from being capable of truly connecting with others. I began to understand that in order to reach people, I have to speak in their language, be it verbally or otherwise. Working with Brian over the past year has made me more aware that people can have difficulty expressing themselves. I found that I can positively lead people if I can communicate with them, whether on the track or in my Jewish youth group discussions. As I move into the next phases of my life, I hope to bring these skills with me because, in order to effectuate positive change in my community, I learned that I must speak in the language of those around me. Those are the words Brian taught me.";
char[] ctext = text.toCharArray();
int textLen = text.length();
ArrayList<Integer> al = new ArrayList<>();
al.add(4);
al.add(8);
al.add(16);
al.add(32);
al.add(36);
al.add(40);
al.add(48);
al.add(56);
al.add(64);
al.add(128);
al.add(256);
al.add(512);
al.add(1024);
int patternLen = 0;
String pattern = "";
char[] cpattern = null;
int totalNumberOfRunsPerPattern = 25;
// initialize algo map
initializeAlgoMap();
while (al.isEmpty() != true) {
patternLen = al.remove(0);
System.out.println();
System.out.println("===================== Summary (Text Len: " + textLen + ", Pattern Len: " + patternLen + ", Total number of runs per pattern: " + totalNumberOfRunsPerPattern + ") =====================");
initializeNumTimesCameFastestOfAllMapEntries();
// initialize time taken by all algorithms to zero.
initializeTimeTakenOfAllMapEntries();
pattern = text.substring(textLen - patternLen);
cpattern = pattern.toCharArray();
correctIndex = text.indexOf(pattern);
if (correctIndex == -1) {
System.out.println("Pattern not found by indexOf() method...Exiting...");
return;
}
for (int j = 0; j < totalNumberOfRunsPerPattern; j++) {
Console.jf.setTitle("Console (Current Run Number: " + (j + 1) + " / " + totalNumberOfRunsPerPattern + ", Pattern Len: " + patternLen + ")");
// Brute Force algorithm
startTime = System.nanoTime();
index = bruteForceStringSearchAlgorithm(ctext, cpattern);
endTime = System.nanoTime();
if (index != correctIndex) {
System.out.println("bruteForceStringSearchAlgorithm is not correct...Exiting...");
return;
}
tmpAlgo = algoMap.get("BruteForce");
tmpAlgo.timeTaken = tmpAlgo.timeTaken + (endTime - startTime);
// Boyer Moore algorithm
startTime = System.nanoTime();
index = boyerMooreStringSearchAlgorithm(ctext, cpattern);
endTime = System.nanoTime();
if (index != correctIndex) {
System.out.println("boyerMooreStringSearchAlgorithm is not correct...Exiting...");
return;
}
tmpAlgo = algoMap.get("BoyerMoore");
tmpAlgo.timeTaken = tmpAlgo.timeTaken + (endTime - startTime);
// Rabin Karp algorithm
startTime = System.nanoTime();
index = rabinKarpStringSearchAlgorithm(ctext, cpattern);
endTime = System.nanoTime();
if (index != correctIndex) {
System.out.println("rabinKarpStringSearchAlgorithm is not correct...Exiting...");
return;
}
tmpAlgo = algoMap.get("RabinKarp");
tmpAlgo.timeTaken = tmpAlgo.timeTaken + (endTime - startTime);
// Knuth Morris Pratt algorithm
startTime = System.nanoTime();
index = knuthMorrisPrattStringSearchAlgorithm(ctext, cpattern);
endTime = System.nanoTime();
if (index != correctIndex) {
System.out.println("knuthMorrisPrattStringSearchAlgorithm is not correct...Exiting...");
return;
}
tmpAlgo = algoMap.get("KnuthMorrisPratt");
tmpAlgo.timeTaken = tmpAlgo.timeTaken + (endTime - startTime);
// Choudhary algorithm
startTime = System.nanoTime();
index = choudharyStringSearchAlgorithm(ctext, cpattern);
endTime = System.nanoTime();
if (index != correctIndex) {
System.out.println("choudharyStringSearchAlgorithm is not correct...Exiting...");
return;
}
tmpAlgo = algoMap.get("Choudhary");
tmpAlgo.timeTaken = tmpAlgo.timeTaken + (endTime - startTime);
tmpAlgo = getFastestAlgoEntryFromMap();
tmpAlgo.numTimesCameFastest = tmpAlgo.numTimesCameFastest + 1;
} // end of for loop j < totalNumberOfRunsPerPattern
System.out.println();
for (Map.Entry<String, Algo> entry : algoMap.entrySet()) {
tmpAlgo = entry.getValue();
float percent = (((((float) (tmpAlgo.numTimesCameFastest)) * 100) / totalNumberOfRunsPerPattern) * 100) / 100;
System.out.println(tmpAlgo.name + " algorithm is fastest \"" + percent + "%\" of times.");
}
System.out.println();
System.out.println("===================== End of Summary =====================");
} // end of while true
} // end of main
} // end of Fastest_String_Search_Algorithm
class Console implements KeyListener, ActionListener {
Dimension screenSize = Toolkit.getDefaultToolkit().getScreenSize();
int screenWidth = screenSize.width;
int screenHeight = screenSize.height;
String title = null;
String text = null;
static JFrame jf = null;
JTextArea jta = null;
JScrollPane jsp = null;
JMenuBar jmb = null;
JMenu jm = null;
JMenuItem jmi = null;
// key codes
int BACKSPACE = 8;
int ENTER = 10;
int PG_UP = 33; // do nothing for this key pressed
int PG_DN = 34; // do nothing for this key pressed
int END = 35;
int HOME = 36;
int LEFT_ARROW = 37;
int UP_ARROW = 38; // do nothing for this key pressed
//int RIGHT_ARROW = 39; // handled by JTextArea
int DOWN_ARROW = 40; // do nothing for this key pressed
int CTRL = 128;
int A = 65; // disable ctrl-a
int H = 72; // handle ctrl-h
//int DELETE = 127; // handled by JTextArea
int initialCaretPosition = 0;
int endOfInputCaretPosition = 0;
Object lock1 = new Object();
Object lock2 = new Object();
boolean inputAvailable = false;
byte[] b = null;
int len = -1;
int indexIntoByteArray = -1;
boolean newLineSent = false;
byte endOfInput = -1;
byte newLine = 10;
boolean enterAlreadyPressedEarlier = false;
long Id_keyPressed = 0;
long Id_getNextByteFromJTextArea = 0;
long Id_outputToJTextArea = 0;
public void actionPerformed(ActionEvent ae) {
int cCurrPos = jta.getCaretPosition();
jta.selectAll();
jta.copy();
jta.select(cCurrPos, cCurrPos);
} // end of actionPerformed
public void keyTyped(KeyEvent ke) {
} // end of keyTyped
public void keyReleased(KeyEvent ke) {
} // end of keyReleased
public void keyPressed(KeyEvent ke) {
Id_keyPressed = Thread.currentThread().getId();
int keyCode = ke.getKeyCode();
if ((keyCode == PG_UP) || (keyCode == PG_DN) || (keyCode == UP_ARROW) || (keyCode == DOWN_ARROW) || ((keyCode == A) && (ke.getModifiersEx() == CTRL))) {
ke.consume();
} else if ((keyCode == LEFT_ARROW) || (keyCode == BACKSPACE) || ((keyCode == H) && (ke.getModifiersEx() == CTRL))) {
synchronized (lock1) {
if (jta.getCaretPosition() <= initialCaretPosition) {
ke.consume();
}
} // end of synchronized block
} else if (keyCode == HOME) {
synchronized (lock1) {
jta.setCaretPosition(initialCaretPosition);
ke.consume();
} // end of synchronized block
} else if (keyCode == END) {
synchronized (lock1) {
jta.setCaretPosition(jta.getDocument().getLength());
ke.consume();
} // end of synchronized block
} else if (keyCode == ENTER) {
// this if block should not exit until all the input has been
// processed.
synchronized (lock1) {
inputAvailable = true;
endOfInputCaretPosition = jta.getDocument().getLength();
//if ((endOfInputCaretPosition - initialCaretPosition) == 1) {
// only newline was entered, so increment initialCaretPosition
if ((enterAlreadyPressedEarlier == true) && (endOfInputCaretPosition - initialCaretPosition) > 0) {
// need to increment initialCaretPosition by 1 to account for last enter pressed
initialCaretPosition++;
}
jta.setCaretPosition(jta.getDocument().getLength());
enterAlreadyPressedEarlier = true;
lock1.notifyAll();
}
// wait until all input has been processed
synchronized (lock2) {
//if (Thread.holdsLock(lock2) == true) { System.out.println("Thread id: " + Thread.currentThread().getId() + ", lock2 is held"); } else { System.out.println("Thread id: " + Thread.currentThread().getId() + ", lock2 is _not_ held"); }
try {
lock2.wait();
} catch (Exception e) {
//System.out.println("Exception (debug:1): " + e.getMessage());
}
}
} // end of if else if
} // end of keyPressed
byte getNextByteFromJTextArea() {
String s = "";
Id_getNextByteFromJTextArea = Thread.currentThread().getId();
synchronized (lock1) {
//if (Thread.holdsLock(lock1) == true) { System.out.println("Thread id: " + Thread.currentThread().getId() + ", lock1 is held"); } else { System.out.println("Thread id: " + Thread.currentThread().getId() + ", lock1 is _not_ held"); }
if (inputAvailable == false) {
try {
lock1.wait();
} catch (Exception e) {
//System.out.println("Excpetion (debug:2): " + e.getMessage());
//System.exit(1);
} // end of try catch
} // end of if inputAvailable
if (newLineSent == true) {
// send endOfInput now, all input has been prcocessed, anyone
// waiting on lock2 should be woken up and some variables
// should be re-initialized
newLineSent = false;
b = null;
len = -1;
indexIntoByteArray = -1;
inputAvailable = false;
initialCaretPosition = jta.getDocument().getLength();
endOfInputCaretPosition = jta.getDocument().getLength();
synchronized (lock2) {
//if (Thread.holdsLock(lock2) == true) {
// System.out.println("lock2 is held..2..Thread id = " + Thread.currentThread().getId());
//} else {
// System.out.println("lock2 is ___not___ held..2..Thread id = " + Thread.currentThread().getId());
//}
lock2.notifyAll();
return endOfInput;
}
} // end of if newLineSent
if (len == -1) { // read input
len = endOfInputCaretPosition - initialCaretPosition;
try {
s = jta.getText(initialCaretPosition, len);
b = s.getBytes(); // enter is still getting processed, the text area
// hasn't been updated with the enter, so send a
// newline once all bytes have been sent.
} catch (Exception e) {
//System.out.println("Exception (debug:3): " + e.getMessage());
if (b != null) {
Arrays.fill(b, (byte) (-1));
}
} // end of try catch
} // end of if len == -1
// if control reaches here then it means that we have to send a byte
indexIntoByteArray++;
if (indexIntoByteArray == len) { // send newLine as all input have been sent already
newLineSent = true;
return newLine;
}
if (b[indexIntoByteArray] == newLine) {
newLineSent = true;
}
return b[indexIntoByteArray];
} // end of synchronized block
} // end of getNextByteFromJTextArea
void outputToJTextArea(byte b) {
Id_outputToJTextArea = Thread.currentThread().getId();
synchronized (lock1) {
char ch = (char) (b);
String text = Character.toString(ch);
jta.append(text);
jta.setCaretPosition(jta.getDocument().getLength());
initialCaretPosition = jta.getCaretPosition();
enterAlreadyPressedEarlier = false;
}
} // end of outputToJTextArea
void configureJTextAreaForInputOutput() {
jta.addKeyListener(this);
// remove all mouse listeners
for (MouseListener listener : jta.getMouseListeners()) {
//outputToJTextArea(jta, "\nRemoving mouse listener\n");
jta.removeMouseListener(listener);
}
// remove all mouse motion listeners
for (MouseMotionListener listener : jta.getMouseMotionListeners()) {
//outputToJTextArea(jta, "\nRemoving mouse motion listener\n");
jta.removeMouseMotionListener(listener);
}
// remove all mouse wheel listeners
for (MouseWheelListener listener : jta.getMouseWheelListeners()) {
//outputToJTextArea(jta, "\nRemoving mouse wheel listener\n");
jta.removeMouseWheelListener(listener);
}
System.setIn(new InputStream() {
@Override
public int read() {
// we need to sleep here because of some threading issues
//try {
// Thread.sleep(1);
//} catch (Exception e) {
//System.out.println("Exception (debug:4): " + e.getMessage());
//}
byte b = getNextByteFromJTextArea();
return ((int) (b));
}
});
System.setOut(new PrintStream(new OutputStream() {
@Override
public void write(int b) {
outputToJTextArea((byte) (b));
}
}));
System.setErr(new PrintStream(new OutputStream() {
@Override
public void write(int b) {
outputToJTextArea((byte) (b));
}
}));
} // end of configureJTextAreaForInputOutput
void createAndShowConsole() {
title = "Console";
jf = InitComponents.setupJFrameAndGet(title, (3 * screenWidth) / 4, (3 * screenHeight) / 4);
jta = InitComponents.setupJTextAreaAndGet("", 5000, 100, true, true, true, false, 0, 0, 0, 0);
configureJTextAreaForInputOutput();
jsp = InitComponents.setupScrollableJTextAreaAndGet(jta, 10, 10, (3 * screenWidth) / 4 - 33, (3 * screenHeight) / 4 - 79);
jsp.setHorizontalScrollBarPolicy(ScrollPaneConstants.HORIZONTAL_SCROLLBAR_AS_NEEDED);
jsp.setVerticalScrollBarPolicy(ScrollPaneConstants.VERTICAL_SCROLLBAR_ALWAYS);
jf.add(jsp);
//jf.setLocation(screenWidth / 5, screenHeight / 6);
jmb = InitComponents.setupJMenuBarAndGet();
jm = InitComponents.setupJMenuAndGet("Copy All to Clipboard");
jm.setBorder(BorderFactory.createLineBorder(Color.green, 2));
jmi = InitComponents.setupJMenuItemAndGet("Copy All to Clipboard");
jm.add(jmi);
jmb.add(jm);
jmi.addActionListener(this);
jf.setJMenuBar(jmb);
jf.setLocationRelativeTo(null);
jf.setVisible(true);
} // end of createAndShowConsole
} // end of Console
class InitComponents {
public static JFrame setupJFrameAndGet(String title, int width, int height) {
JFrame tmpJF = new JFrame(title);
tmpJF.setSize(width, height);
tmpJF.setLocationRelativeTo(null);
tmpJF.setLayout(null);
tmpJF.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
return tmpJF;
} // end of setupJFrameAndGet
public static JTextArea setupJTextAreaAndGet(String text, int rows, int columns, boolean setEditableFlag, boolean setLineWrapFlag, boolean setWrapStyleWordFlag, boolean setBoundsFlag, int xpos, int ypos, int width, int height) {
JTextArea tmpJTA = new JTextArea(text, rows, columns);
tmpJTA.setEditable(setEditableFlag);
tmpJTA.setLineWrap(setLineWrapFlag);
tmpJTA.setWrapStyleWord(setWrapStyleWordFlag);
if (setBoundsFlag == true) {
tmpJTA.setBounds(xpos, ypos, width, height);
}
return tmpJTA;
} // end of setupJTextAreaAndGet
public static JScrollPane setupScrollableJTextAreaAndGet(JTextArea jta, int xpos, int ypos, int width, int height) {
JScrollPane tmpJSP = new JScrollPane(jta);
tmpJSP.setBounds(xpos, ypos, width, height);
return tmpJSP;
} // end of setupScrollableJTextAreaAndGet
public static JMenuBar setupJMenuBarAndGet() {
JMenuBar tmpJMB = new JMenuBar();
return tmpJMB;
} // end of setupJMenuBarAndGet
public static JMenu setupJMenuAndGet(String text) {
JMenu tmpJM = new JMenu(text);
return tmpJM;
} // end of setupJMenuAndGet
public static JMenuItem setupJMenuItemAndGet(String text) {
JMenuItem tmpJMI = new JMenuItem(text);
return tmpJMI;
} // end of setupJMenuItemAndGet
}// end of InitComponents
Results
== Summary (Text Len: 14013, Pattern Len: 4, Total number of runs per pattern: 25) ==
Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "0.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "44.0%" of times.
Choudhary algorithm is fastest "56.0%" of times.
==== End of Summary ====
== Summary (Text Len: 14013, Pattern Len: 8, Total number of runs per pattern: 25) ==
Brute Force algorithm is fastest "92.0%" of times.
Boyer Moore algorithm is fastest "0.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "8.0%" of times.
==== End of Summary ====
== Summary (Text Len: 14013, Pattern Len: 16, Total number of runs per pattern: 25) ==
Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "0.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "100.0%" of times.
==== End of Summary ====
== Summary (Text Len: 14013, Pattern Len: 32, Total number of runs per pattern: 25) ==
Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "0.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "100.0%" of times.
==== End of Summary ====
== Summary (Text Len: 14013, Pattern Len: 36, Total number of runs per pattern: 25) ==
Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "4.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "96.0%" of times.
==== End of Summary ====
== Summary (Text Len: 14013, Pattern Len: 40, Total number of runs per pattern: 25) ==
Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "4.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "96.0%" of times.
==== End of Summary ====
== Summary (Text Len: 14013, Pattern Len: 48, Total number of runs per pattern: 25) ==
Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "4.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "96.0%" of times.
==== End of Summary ====
== Summary (Text Len: 14013, Pattern Len: 56, Total number of runs per pattern: 25) ==
Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "16.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "84.0%" of times.
==== End of Summary ====
== Summary (Text Len: 14013, Pattern Len: 64, Total number of runs per pattern: 25) ==
Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "0.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "100.0%" of times.
==== End of Summary ====
== Summary (Text Len: 14013, Pattern Len: 128, Total number of runs per pattern: 25) ==
Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "4.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "96.0%" of times.
==== End of Summary ====
== Summary (Text Len: 14013, Pattern Len: 256, Total number of runs per pattern: 25) ==
Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "0.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "100.0%" of times.
==== End of Summary ====
== Summary (Text Len: 14013, Pattern Len: 512, Total number of runs per pattern: 25) ==
Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "0.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "100.0%" of times.
==== End of Summary ====
== Summary (Text Len: 14013, Pattern Len: 1024, Total number of runs per pattern: 25) ==
Brute Force algorithm is fastest "0.0%" of times.
Boyer Moore algorithm is fastest "0.0%" of times.
Rabin Karp algorithm is fastest "0.0%" of times.
KnuthMorrisPratt algorithm is fastest "0.0%" of times.
Choudhary algorithm is fastest "100.0%" of times.
==== End of Summary ====
