This a simple LinkList class that can hold any object.
import java.lang.Object;
class LinkList extends Object {
private LinkList therest;
private Object value;
public LinkList(Object obj) {
therest=null;
value=obj;
}
public LinkList cons(Object obj) {
LinkList newnode;
newnode=new LinkList(obj);
newnode.value=value;
newnode.therest=therest;
therest=newnode;
value=obj;
return this;
}
public Object first() {
return value;
}
public LinkList rest() {
return therest;
}
public String toString() {
StringBuffer out;
LinkList list;
out=new StringBuffer();
out.append("LinkList Object: ["+value.toString());
list=therest;
while(list!=null) {
out.append(","+list.first().toString());
list=list.rest();
}
out.append("]");
return out.toString();
}
}
class test extends Object {
public static void main(String argv[]) {
LinkList foo;
foo=new LinkList("This is the End");
foo.cons(new Integer(5));
foo.cons(new Boolean(true));
foo.cons(new LinkList(new Integer(7)));
System.out.println(foo.toString());
System.out.println((foo=foo.rest()).first().toString());
System.out.println((foo=foo.rest()).first().toString());
System.out.println((foo=foo.rest()).first().toString());
}
}
Refer to http://www.cerf.net/~paulp/java/btree/
In Bubble sort the main idea is to interchange the elements immediately upon discovering that those are out of order. With this sorting method at most we need n-1 passes through an array of size n. During the first pass elements one and two are compared, and if they are found to be out of order they will be interhanged. This way all the elements in the array are compared with its preceeding elements, and interchanged if necessary. After the completion of the first pass the highest element will be in the nth place. After few passes (equal to n-1 or less than that ) all the elements will be placed in their respective positions (i.e sorting order.)(Submitted by Jon. M. Madison)In the code shown below, during each pass if any interchanges are done variable count will be incremented, which indicates that interchanges are done during that pass. If the value of the count is zero or number of passes equal to n-1 sorting is completed and the program stops execution.
For complete details of bubble sort algorithm please refer to page no:541 of the book "An Introduction to Datastructures With Applications" written by Jean-Paul Tremblay and Paul G.Sorensen.
class bubblesort { public static void main (String args[]) { int sort[] = {42,23,74,11,65,58,94,36,99,87}; // values to be sorted int temp; int count; // for checking whether interchanges are done or not int n; // for counting number of passes n=0; count=1; while (n < sort.length-1 || count != 0) { count = 0; for(int j=0;j < sort.length-1;j++) { if (sort[j] > sort[j+1]) { temp = sort[j]; sort[j] = sort[j+1]; sort[j+1] = temp; count++; } } n++; } for(int i=0; i < sort.length;i++) { System.out.println(sort[i]); } } }
Example from java.sun.com
Here is an example of creating a stack class which extends the API Stack class. In this example, the new class, NameStack, allows String values to be pushed, and prevents duplicate string values from being pushed.Select to see an entire program which uses this class
Select to see the program run (requires a Beta browser)
/** * The stack class, which extends the API Stack class, adding * behavior which prevents duplicate String values from being pushed * onto the stack. */ class NameStack extends Stack { /** * Overloads Stack.push() * Pushes an item onto the stack. * @param item the item to be pushed on. * Checks that the item value (a String) is unique. */ public String push(String item) { for (int i = 0; i < size(); i++) { String s = (String)(elementAt(i)); if (s.equals(item)) { // duplicate: not allowed return null; } } // no duplicates found; add item to stack addElement(item); return item; } }
Here is a circular queue:(Submitted by Joydeep Tripathy)
import java.util.Vector; import java.util.Enumeration; import java.util.NoSuchElementException; /** A fixed size circular queue. Adding a new element overwrites the oldest one. */ public class CircularQueue extends Vector { int size = 0; // # of elements the queue can contain int count = 0; // # of elements currently in the queue int head; public CircularQueue ( int s ) { if ( s < 2 ) { throw new IllegalArgumentException("Queue size must be >= 2"); } size = s; // (should throw exception if s < 2) count = 0; // just discard existing items for now this.setSize(size); // allocate exact amount of storage this.trimToSize(); // using Vector methods head = size - 2; // initialize head pointer } public void add ( Object obj ) { if ( count < size ) { // update # of in-use elements count++; } head++; // update head pointer if (head == size ) { head = 0; // wrap at the end } this.setElementAt( obj, head ); // replace object at this location } public int count() { return count; // return the # of in-use elements } // Returns an enumeration of the elements. Use the Enumeration methods on // the returned object to fetch the elements sequentially. public final synchronized Enumeration enumeration() { return new CircularQueueEnumerator(elementData, count, head); } } // end CircularQueue /** Supporting class for CircularQueue to allow enumeration of the contents. Elements are returned in the reverse order of entry (i.e., newest to oldest). */ final class CircularQueueEnumerator implements Enumeration { Object data[]; // data array int count; // # of objects returned so far int actualCount; // # of objects in-use int head; // head pointer int current; // current enumeration position pointer CircularQueueEnumerator( Object d[], int ac, int h) { data = d; count = 0; actualCount = ac; head = h; current = head; // initialize pointer to return first element } public boolean hasMoreElements() { return count < actualCount; } public Object nextElement () { if ( count < actualCount ) { // done yet? if (count > 0) { // not first one? current--; // walk down list if (current < 0) { // wrap around current = data.length - 1; } } count++; return data[current]; } throw new NoSuchElementException("CircularQueueEnumerator"); } } // end CircularQueueEnumeratorHere is a program to test the queue:
// Sample code to test CircularQueue class import java.applet.Applet; import java.lang.String; import java.util.Enumeration; public class someClass extends Applet { CircularQueue cq; int size = 4; public void init() { cq = new CircularQueue( size ); // instantiate queue of a given size String s1 = "12:00"; String s2 = "12:01"; String s3 = "12:02"; String s4 = "12:03"; cq.add( s1 ); // add items to the queue cq.add( s2 ); cq.add( s3 ); cq.add( s4 ); // list elements in reverse order of entry (newest-to-oldest) for (Enumeration e = cq.enumeration(); e.hasMoreElements(); ) { String s = (String) e.nextElement(); System.out.println( s ); } System.out.println(); String s5 = "12:04"; cq.add( s5 ); // overwrite oldest item // list elements in reverse order of entry (newest-to-oldest) for (Enumeration e = cq.enumeration(); e.hasMoreElements(); ) { String s = (String) e.nextElement(); System.out.println( s ); } } }
Here is a little queue class, complete with a test program.
import java.awt.*;
import java.applet.*;
import java.util.Vector;
class Queue extends Vector {
Queue(int initialCapacity, int capacityIncrement) {
super(initialCapacity, capacityIncrement);
}
// Now add methods to insert and remove from the queue
void insert(Object o) {
addElement(o);
}
Object remove() {
if (isEmpty()) return null;
Object o = firstElement();
removeElement(o);
return o;
}
Object peek() {
if (isEmpty()) return null;
return firstElement();
}
}
public class QueueTest extends Applet {
Queue queue;
Button bi;
Button br;
static int uniqueId = 0;
public void init() {
queue = new Queue(10, 10);
add(bi = new Button("Insert"));
add(br = new Button("Remove"));
}
public void start() {}
public void stop() {}
public boolean handleEvent(Event e) {
if (e.id == Event.WINDOW_DESTROY) {
System.exit(0);
}
if (e.target == bi) {
// insert an object into queue
String s = String.valueOf(uniqueId++);
queue.insert(s);
System.out.println("Inserted: " + s);
}
else if (e.target == br) {
// remove an object from queue
Object o = queue.remove();
if (o == null) o = "";
System.out.println("Removed: " + (String)o);
}
return false;
}
public static void main(String args[]) {
// Create a Frame
MainFrame f = new MainFrame("QueueTest");
// Instantiate the Applet
QueueTest queueTest = new QueueTest();
// Init and start the Applet
queueTest.init();
queueTest.start();
// Add the Applet to the Frame
f.add("West", queueTest);
// Resize and show the Frame
f.resize(300, 300);
f.show();
}
}
class MainFrame extends Frame {
public MainFrame(String s) {
super(s);
}
// Handle close events by simply exiting
public boolean handleEvent(Event e) {
if (e.id == Event.WINDOW_DESTROY)
{
System.exit(0);
}
return false;
}
}
Click here to see sample code
/** getDoubles class is a class into which a string is placed. After that,
* repeated invocation of the next() method will return either the next
* double in the string or Double.POSITIVE_INFINITY if there are no more
* doubles in the string. White space is ignored. Numbers followed by letters
* are translated, but numbers directly preceded by letters are not. Scientific
* notation is handled correctly, but only if the exponent is signed: a number
* like 1.546e78 will not be parsed correctly (the exponent is lost). Luckily
* the String translation functions of Java generate numbers with signed
* exponents, even when the exponent is positive.
*
* This file Copyright (c) 1996 by Tim Farnum (tfarnum@rpa.net). THERE IS NO
* WARRANTY OF MERCHANTIBILITY OR FITNESS FOR ANY PURPOSE AND THE AUTHOR
* ACCEPTS NO LIABILITY FOR ANY USE OF THIS SOFTWARE. ANYONE USING THIS
* SOFTWARE USES IT AT THEIR OWN RISK.
*
* Constructor
* public getDoubles(String inString)
* inString is inserted into a StreamTokenizer for processing by the
* methods of the class.
*
* Methods
*
* public double next()
* throws IOException
* This is the workhorse method which parses the next double in the string
* if there is one, skipping over white space, newlines, and text. It will
* not convert numbers directly preceded by text, and it will convert
* numbers followed by text if they are preceded by a space. It will
* convert numbers in scientific notation, if the exponent is signed. With
* an unsigned exponent, only the mantissa is converted.
*
* When the scan reaches the end of the string without finding a double to
* translate, this method returns Double.POSITIVE_INFINITY.
*
* The IOException can be thrown by the nextToken() method of the
* StreamTokenizer.
*
* public static void main(String argv[])
* throws IOException
*
* This is a test module which exercises some of the cases this software
* might be expected to find in text. This is not a complete or exhaustive
* test, but it does demonstrate the ability of the code to translate
* well-formed numbers from text to numeric format. In production code,
* this method (and the 'import doubleArray' associated with it) should
* be commented out, mostly to avoid importing doubleArray, which you
* may or may not have, since it is not part of this package. (It may
* become part of a package at some point, but I haven't done that yet.)
* If you want a copy of the source for doubleArray class, I plan to post
* it on my web page: http://www2.rpa.net/~tfarnum/my_java_page.html, and
* it is also posted on the java developers' FAQ at the Java Developer:
* http://www.digitalfocus.com/digitalfocus/faq/howdoi.html. (Search under
* my name or the phrase 'dot product'.) *
*
*/
import java.io.*;
import java.lang.*;
import doubleArray;
public class getDoubles {
private StreamTokenizer ST;
public getDoubles(String inString) {
ST = new StreamTokenizer(new StringBufferInputStream(inString));
ST.resetSyntax();
ST.whitespaceChars("\t".charAt(0), " ".charAt(0));
ST.wordChars("-".charAt(0), "d".charAt(0)); //'e' and '+' are special chars
ST.wordChars("f".charAt(0), "z".charAt(0)); //so we can handle them explicitly
ST.parseNumbers();
}
public double next()
throws IOException { //in nextToken()
int aType = 0;
boolean converted = false;
double tempdbl = Double.POSITIVE_INFINITY;
while(! converted && aType != StreamTokenizer.TT_EOF) {
aType = ST.nextToken();
if(aType == StreamTokenizer.TT_NUMBER) { //this token is a number
tempdbl = ST.nval;
converted = true;
aType = ST.nextToken(); //get next token to check for
if(aType == "e".charAt(0)) { //scientific notation
aType = ST.nextToken();
if(aType == "+".charAt(0)) { //number parser doesn't handle plus
aType = ST.nextToken();
}
if(aType == StreamTokenizer.TT_NUMBER) {
tempdbl = tempdbl * Math.pow(10, ST.nval);
} else {
ST.pushBack();
}
} else {
ST.pushBack();
}
}//if(aType == StreamTokenizer.TT_NUMBER)
}//while(! converted && aType != StreamTokenizer.TT_EOF)
if(converted) {
return tempdbl;
}
return Double.POSITIVE_INFINITY;
}//public double next()
public static void main(String argv[])
throws IOException { //in getD.next()
double temp = 3.4e-25;
doubleArray da = new doubleArray(10);
StringBuffer tempsb;
int i;
for(i = 0; i < 10; i++) {
da.getDoubleArray()[i] = temp;
temp = temp * Math.pow(10, i);
}
tempsb = new StringBuffer(da.toString());
tempsb.append("1234.5678 123eats456 789is234 6.745e+50 1.2867e3 -167.8 +876.1");
String something = tempsb.toString();
System.out.println(something);
getDoubles getD = new getDoubles(something);
while(temp != Double.POSITIVE_INFINITY) {
temp = getD.next();
System.out.println(String.valueOf(temp));
}
}//public static void main(String argv[])
}//public class getDoubles