/**
* This class extends the BinarySearchTree by adding the rotate methods.
* Rotation will change the balance of a search tree while preserving the search tree property.
* Used as a common base class for self-balancing trees.
*
*/
public class BinarySearchTreeWithRotate<E extends Comparable<E>> extends BinarySearchTree<E> {
private static final long serialVersionUID = 1L;
// Methods
/**
* Method to perform a right operation.
* pre: root is the root of a binary search tree.
* post: root.right is the root of a binary search tree.
* root.right.right is raised on level.
* root.left.left does not change levels.
* root.left is lowered one level,
* the new root is returned.
* @param root
* @return
*/
protected Node<E> rotateRight(Node<E> root) {
Node<E> temp = root.left;
root.left = temp.right;
temp.right = root;
return temp;
}
protected Node<E> rotateLeft(Node<E> root) {
Node<E> temp = root.right;
root.right = temp.left;
temp.left = root;
return temp;
}
public static void main(String[] args) {
BinarySearchTreeWithRotate<Integer> app = new BinarySearchTreeWithRotate<Integer>();
BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
Node<Integer> root = new Node<Integer>(20);
root.left = new Node<Integer>(10);
root.left.right = new Node<Integer>(15);
root.left.left = new Node<Integer>(5);
root.left.left.right = new Node<Integer>(7);
root.right = new Node<Integer>(40);
bst.root = root;
System.out.println(bst);
bst.root = app.rotateRight(bst.root);
System.out.println("**********************");
System.out.println(bst);
}
}
public class BinarySearchTree<E extends Comparable<E>> extends BinaryTree<E> implements ISearchTree<> {
// Data fields
private static final long serialVersionUID = 1L;
/**
* Return value from the public add method.
*/
protected boolean addReturn;
/**
* Return value from the public delete method.
*/
protected E deleteReturn;
/**
* Starter add method pre: The object to insert must implement the
* Comparable interface.
*
* @param item
* The Comparable object being inserted.
* @return true if the object is inserted, false if the object already exits
* in the tree.
*/
public boolean add(E item) {
root = add(root, (Comparable<E>) item);
return addReturn;
}
@SuppressWarnings({ "unchecked", "rawtypes" })
private Node<E> add(Node<E> localRoot, Comparable item) {
if (localRoot == null) {
// The item is not in the tree - insert it
addReturn = true;
return new Node(item);
} else if (item.compareTo(localRoot.data) == 0) {
addReturn = false;
return localRoot;
} else if (item.compareTo(localRoot.data) < 0) {
// item is less than the localRoot.data
localRoot.left = add(localRoot.left, item);
return localRoot;
} else {
// item is greater than the localRoot.data
localRoot.right = add(localRoot.right, item);
return localRoot;
}
}
@Override
public boolean contains(E target) {
// TODO Auto-generated method stub
return false;
}
/**
* Starter method find. pre: The target object must implement the Comparable
* interface.
*
* @param target
* The comparable object being sought.
* @return The object, if found, otherwise null
*/
@Override
public E find(E target) {
return find(root, (Comparable<E>) target);
}
/**
* Recursive find method.
*
* @param localRoot
* The local subtree's root.
* @param target
* The object being sought.
* @return The object if found, otherwise null
*/
private E find(Node<E> localRoot, Comparable<E> target) {
if (localRoot == null) {
return null;
}
// Compare the target with the data field at the root.
int compResult = target.compareTo(localRoot.data);
if (compResult == 0) {
return localRoot.data;
} else if (compResult < 0) {
return find(localRoot.left, target);
} else {
return find(localRoot.right, target);
}
}
/**
* Starter method delete pre: The object being deleted must be Comparable.
* post: The object is not in the tree.
*
* @param target
* The object to be deleted.
* @return The object deleted from the tree or null if the object was not in
* the tree.
*/
@Override
public E delete(E target) {
root = delete(root, target);
return deleteReturn;
}
/**
* Recursive delete method post: The item is not in the tree; deleteReturn
* is equal to the deletedItem as it was stored in the tree or null if the
* item was not found.
*
* @param localRoot
* The root of the current subtree
* @param item
* The item to be deleted.
* @return The modified local root that does not contain the item.
*/
private Node<E> delete(Node<E> localRoot, E item) {
if (localRoot == null) {
// The item is not in the tree.
deleteReturn = null;
return localRoot;
}
// Search for item to delete.
int compResult = item.compareTo(localRoot.data);
if (compResult < 0) {
// The item i smaller than localRoot.data
localRoot.left = delete(localRoot.left, item);
return localRoot;
} else if (compResult > 0) {
// The item i greater than localRoot.data
localRoot.right = delete(localRoot.right, item);
return localRoot;
} else {
// The item is in the local root.
deleteReturn = localRoot.data;
if (localRoot.left == null) {
// If there is no left child, return right child
// which can also be null.
return localRoot.right;
} else if (localRoot.right == null) {
return localRoot.left;
} else {
// Node being deleted, has two children
// Replace the data with inorder predecessor.
if (localRoot.left.right == null) {
// the left child has no right child.
// Replace the data with the data in the left child.
localRoot.data = localRoot.left.data;
localRoot.left = localRoot.left.left;
return localRoot;
} else {
// Search for the inorder predecessor (ip) and
// replace deleted node's data with ip.
localRoot.data = findLargestChild(localRoot.left);
return localRoot;
}
}
}
}
/**
* Find the node that is the inorder predecessor and replace it with its
* left child (if any) post: The inorder predecessor is removed from the
* tree.
*
* @param parent
* The parent of possible inorder predecessor (ip)
* @return The data in the ip.
*/
private E findLargestChild(Node<E> parent) {
// If the right child has no right child, it is the inorder predecessor.
if (parent.right.right == null) {
E returnValue = parent.right.data;
parent.right = parent.right.left;
return returnValue;
} else {
return findLargestChild(parent.right);
}
}
@Override
public boolean remove(E target) {
// TODO Auto-generated method stub
return false;
}
}
/**
* Implements the quicksort algorithm.
*
*/
public class QuickSort {
/**
* Sort the table using the quick sort algorithm.
* pre: table contains Comparable objects.
* post: table is sorted.
* @param table The array to be sorted.
*/
public static void sort(Comparable<Integer>[] table) {
// Sort the whole table
quickSort(table, 0, table.length - 1);
}
private static void quickSort(Comparable<Integer>[] table, int first, int last) {
if (first < last) { // There is data to be sorted.
// Partition the table
int pivIndex = partition(table, first, last);
quickSort(table, first, pivIndex - 1);
quickSort(table, pivIndex + 1, last);
}
}
private static int partition(Comparable<Integer>[] table, int first,
int last) {
// Select the first item as the pivot value.
Comparable<Integer> pivot = table[first];
int up = first;
int down = last;
do {
// Invarient:
// All items in table[first .. up-1] <= pivot
// All items in table[down+1 .. last] > pivot
while (up < last && (pivot.compareTo((Integer)table[up]) >= 0) ) {
up++;
}
// assert: up equals last or table[up] > pivot
while (pivot.compareTo((Integer)table[down]) < 0) {
down--;
}
//assert down equals first or table[down] <= pivot.
if (up < down) {
// Exchange table[up] and table[down]
swap(table, up, down);
}
} while (up < down); // Repeat while up is left of down
// Exchange table[first] and table[down] thus putting the pivot value
// where it belongs
swap(table, first, down);
// return the index of the pivot value.
return down;
}
private static void swap(Comparable<Integer>[] table, int up, int down) {
Integer temp = (Integer) table[up];
table[up] = table[down];
table[down] = temp;
}
public static void main(String[] args) {
Integer[] table = { new Integer(50), new Integer(60), new Integer(45),
new Integer(30), new Integer(90), new Integer(20),
new Integer(80), new Integer(15), new Integer(10) };
System.out.println("Quick sort result: ");
QuickSort.sort(table);
for (Integer integer : table) {
System.out.print(integer + " ");
}
}
}
/**
* Implementation of the heapsort algorithm
*
*/
public class HeapSort {
/**
* Sort the array using heap sort algorithm.
* pre: table contains Comparable items.
* post: table is sorted.
* @param table
* The array to be sorted.
*/
public void sort(Comparable<Integer>[] table) {
buildHeap(table);
}
/**
* buildHeap transforms the table into a heap.
* pre: The array contains at least one item.
* post: All items in the array are in heap order.
*
* @param table
* The array to be transformed into a heap.
*/
private static void buildHeap(Comparable<Integer>[] table) {
int n = 1;
// Invarient: table[0..n-1] is a heap
while (n < table.length) {
n++; // Add a new item to the heap and reheap.
int child = n - 1;
int parent = (child - 1) / 2;
while (parent >= 0
&& table[parent].compareTo((Integer) table[child]) < 0) {
swap(table, parent, child);
child = parent;
parent = (child - 1) / 2;
}
}
}
/**
* shrinkHeap transforms a heap into a sorted array
* pre: All items in the array are in heap order.
* post: The array is sorted.
*
* @param table
* The array to be sorted.
*/
private static void shrinkHeap(Comparable<Integer>[] table) {
int n = table.length;
// Invarient: table[0..n-1] forms a heap.
// table[n..table.length-1] is sorted.
while (n > 0) {
n--;
swap(table, 0, n);
// table[1..n-1] form a heap.
// table[n..table.length-1] is sorted.
int parent = 0;
while (true) {
int leftChild = 2 * parent + 1;
if (leftChild >= n) {
break; // No more children.
}
int rightChild = leftChild + 1;
// Find the larger of the two children.
int maxChild = leftChild;
if (rightChild < n // There is a right child.
&& table[leftChild]
.compareTo((Integer) table[rightChild]) < 0) {
maxChild = rightChild;
}
// If the parent is smaller than the larger child
if (table[parent].compareTo((Integer) table[maxChild]) < 0) {
// Swap the parent and child
swap(table, parent, maxChild);
// Continue at the child level
parent = maxChild;
} else {
// Heap property is restored.
break;
}
}
}
}
private static void swap(Comparable<Integer>[] table, int parent, int child) {
Comparable<Integer> temp = table[parent];
table[parent] = table[child];
table[child] = temp;
}
private static void showHeap(Comparable<Integer>[] table) {
for (int i = 0; i < table.length; i++) {
System.out.print(table[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
Integer[] table = { new Integer(1), new Integer(2), new Integer(3),
new Integer(4), new Integer(5), new Integer(6), new Integer(7),
new Integer(8), new Integer(9), new Integer(10),
new Integer(11), new Integer(12), new Integer(13) };
buildHeap(table);
showHeap(table);
shrinkHeap(table);
showHeap(table);
}
}
/**
* implements the recursive merge sort algorithm. Copies of the
* sub tables are made, sorted, and then merged.
*
*/
public class MergeSortRecursive {
/**
* Sort the array using the merge sort algorithm. pre: table contains
* Comparable objects. post: table is sorted.
*
* @param table The array to be sorted.
*/
@SuppressWarnings("unchecked")
public static void sort(Comparable<Integer>[] table) {
// A table with one element is sorted already.
if (table.length > 1) {
// Split table into halves.
int halfSize = table.length / 2;
Comparable<Integer>[] leftTable = new Comparable[halfSize];
Comparable<Integer>[] rightTable = new Comparable[table.length
- halfSize];
System.arraycopy(table, 0, leftTable, 0, halfSize);
System.arraycopy(table, halfSize, rightTable, 0, table.length
- halfSize);
// Sort the halves.
sort(leftTable);
sort(rightTable);
// Merge the halves.
merge(table, leftTable, rightTable);
}
}
/**
* Merge two sequences
* pre: leftSequence and rightSequence are sorted
* post: outputSequence is the merged result and is sorted.
*
* @param outputsequence The destination
* @param leftSequence The left input
* @param rightSequence The right input
*/
private static void merge(Comparable[] outputsequence,
Comparable<Integer>[] leftSequence,
Comparable<Integer>[] rightSequence) {
int i = 0; // index into the left input sequence
int j = 0; // index into the right input sequence
int k = 0; // index into the output sequence
// While not finished with either sequence
while (i < leftSequence.length && j < rightSequence.length) {
// find the smaller and insert it into the output sequence
if (leftSequence[i].compareTo((Integer) rightSequence[j]) < 0) {
outputsequence[k++] = leftSequence[i++];
} else {
outputsequence[k++] = rightSequence[j++];
}
}
// assert: one of the sequences has more items to copy.
// Copy remaining input from left sequence into the output
while (i < leftSequence.length) {
outputsequence[k++] = leftSequence[i++];
}
// Copy remaining input from the right sequence into the output.
while (j < rightSequence.length) {
outputsequence[k++] = rightSequence[j++];
}
}
public static void main(String[] args) {
Integer[] table = { new Integer(50), new Integer(60), new Integer(45),
new Integer(30), new Integer(90), new Integer(20),
new Integer(80), new Integer(15), new Integer(10) };
System.out.println("Merge sort result: ");
MergeSortRecursive.sort(table);
for (Integer integer : table) {
System.out.print(integer + " ");
}
}
}
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class MapBasedPhoneDirectory implements PhoneDirectory {
// Data fields
/** The directory data */
private Map<String, String> theDirectory = new HashMap<String, String>();
private boolean modified = false;
/** The name of the data file */
private String sourceName = null;
@Override
public void loadData(String sourceName) {
// Remember the source name
this.sourceName = sourceName;
try {
// Create a BufferedReader for the file.
BufferedReader in = new BufferedReader(new FileReader(sourceName));
String name;
String number;
// Read each name and number and add the entry to the array
while ((name = in.readLine()) != null) {
// Read name and number from successive lines.
if ((number = in.readLine()) == null) {
break; // No number - end of data reached.
}
// Add an entry for this name and number.
theDirectory.put(name, number);
}
in.close();
} catch (FileNotFoundException fnfe) {
return;
} catch (IOException ioe) {
System.err.println("Load of directory failed.");
ioe.printStackTrace();
System.exit(1);
}
}
@Override
public String addOrChangeEntry(String name, String number) {
String oldNumber = theDirectory.put(name, number);
modified = true;
return oldNumber;
}
@Override
public String lookupEntry(String name) {
return theDirectory.get(name);
}
@Override
public String removeEntry(String name) {
String returnValue = theDirectory.remove(name);
if (returnValue != null) {
modified = true; // set to true only if the item is found and
// removed.
}
return returnValue;
}
@Override
public void save() {
if (modified) { // if not modified, do nothing.
try {
PrintWriter out = new PrintWriter(new FileWriter(sourceName));
Iterator<Map.Entry<String, String>> iter = theDirectory
.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry<String, String> current = (Map.Entry<String, String>) iter
.next();
out.println(current.getKey());
out.println(current.getValue());
}
// Close the file.
out.close();
modified = false;
} catch (Exception e) {
System.err.println("Save of directory failed.");
e.printStackTrace();
System.exit(1);
}
}
}
}
/** The interface for the telephone directory */
public interface PhoneDirectory {
/**
* Load the data file containing the directory, or establish a connection
* with the data source
* @param sourceName The name of the file (data source) with the phone directory entries
*/
void loadData(String sourceName);
/** Add an entry or change an existing entry.
*
* @param name The name of the person being added or changed
* @param number The new number to be assigned
* @return The old number, or if a new entry, null
*/
String addOrChangeEntry(String name, String number);
/**
*
* @param name The name of the person to lookup
* @return The number or null if name is not in the directory
*/
String lookupEntry(String name);
/**
* Remove an entry from the directory
* @param name The name of the person to be removed
* @return The current number.If not in the directory, null is returned
*/
String removeEntry(String name);
/**
* Method to save the directory
* pre: The directory has been loaded with data
* post: Contents of the directory written back to the file in the form of name-number pairs on
* adjacent lines
* modified is reset to false.
*/
void save();
}
/**
* Program to display and modify a simple phone directory
*
*/
public class PDApplication {
private static PhoneDirectory phoneDirectory;
private static PDUserInterface phoneDirectoryInterface;
public static void main(String[] args) {
// Check to see if there is a command line argument.
if (args.length == 0) {
System.err.println("You must provide the name of the file that contains the phone directory.");
System.exit(1);
}
// Create a phone directory object.
phoneDirectory = new MapBasedPhoneDirectory();
// Load the phone directory from the file.
phoneDirectory.loadData(args[0]);
// Create a phone directory user interface.
phoneDirectoryInterface = new PDConsoleUI(); // PDGUI();
phoneDirectoryInterface.processCommands(phoneDirectory);
}
}
/**
* Hash table implementation that uses open addressing where
* each hash table element of type Object references a single <Key,Value> pair.
*
*/
public interface IHashMap {
/**
* Returns the value associated with the specified key. Returns null if the key is not present.
* @param key
* @return
*/
Object get(Object key);
/**
* Returns true if this table contains no key-value mappings.
* @return
*/
boolean isEmpty();
/**
* Associates the specified value with the specified key.
* Returns the previous value associated with the specified key,
* or null if there was no mapping for the key.
* @param key
* @param value
* @return
*/
Object put(Object key, Object value);
/**
* Removes the mapping for this key from this table if it is present.
* Returns the previous value associated with the specified key, or null
* if there was no mapping.
* @param key
* @return
*/
Object remove(Object key);
/**
* Returns the size of the table.
* @return
*/
int size();
}
public class HashTableOpen implements IHashMap {
// inner class.
private static class Entry {
/** The key */
private Object key;
/** The value */
private Object value;
/**
* Creates a new key-value pair.
*
* @param key
* @param value
*/
public Entry(Object key, Object value) {
this.key = key;
this.value = value;
}
public Object getKey() {
return key;
}
public Object getValue() {
return value;
}
public Object setValue(Object value) {
Object oldValue = this.value;
this.value = value;
return oldValue;
}
@Override
public String toString() {
return "<" + getKey() + ", " + getValue() + ">";
}
}
// Data fields
/** The hash table array */
private Entry[] table;
/** The initial capacity */
private static final int START_CAPACITY = 101;
/** The max. load factor */
private double LOAD_THRESHOLD = 0.75;
/** The number of keys in the table excluding the keys that were deleted */
private int numKeys;
/** The number of deleted keys */
private int numDeletes;
/** A special object to indicate that an entry has been deleted. */
private static final Entry DELETED = new Entry("*****", "*****");
// Constructor
public HashTableOpen() {
table = new Entry[START_CAPACITY];
}
/**
* Method get for class HashTableOpen
*
* @param key
* The key being sought
* @return The value associated with this key if found; otherwise null.
*/
@Override
public Object get(Object key) {
// Find the first table element that is empty or the the table element
// that contains the key.
int index = find(key);
// if the search is successful, return the value.
if (table[index] != null) {
return table[index];
} else {
return null; // key not found.
}
}
@Override
public boolean isEmpty() {
return numKeys == 0;
}
/**
* Method put for class HashTableOpen post: This key-value pair is inserted
* in the table and numKeys is incremented. If the key is already in the
* table, its value is changed to the argument value and numKeys is not
* changed. If the LOAD_THRESHOLD is exceeded, the table is expanded.
*
* @param key
* The key of item being inserted
* @param value
* The value for this key
* @return Old value associated with this key if found; otherwise null.
*/
@Override
public Object put(Object key, Object value) {
// Find the first table element that is empty
// or the table that contains the key.
int index = find(key);
// If an empty element was found, insert new entry.
if (table[index] == null) {
table[index] = new Entry(key, value);
numKeys++;
// Check whether rehash is needed
double loadFactor = (double) (numKeys + numDeletes) / table.length;
if (loadFactor > LOAD_THRESHOLD) {
rehash();
}
}
// assert: table element that contains the key was found.
// Replace value for this key.
Object oldVal = table[index].value;
table[index].value = value;
return oldVal;
}
/**
* Expands table size when load factor exceeds LOAD_THRESHOLD post: The size
* of the table is doubled and is an odd integer. Each nondeleted entry from
* the original table is reinserted into the expanded table. The value of
* numKeys is reset to the number of items actually inserted; numDeletes is
* reset to 0.
*/
private void rehash() {
// Save a reference to oldTable.
Entry[] oldTable = table;
// Double capacity of this table.
table = new Entry[1 * oldTable.length + 1];
// Reinsert all items in oldTable into expanded table.
numKeys = 0;
numDeletes = 0;
for (int i = 0; i < oldTable.length; i++) {
if ((oldTable[i] != null) && (oldTable[i] != DELETED)) {
// insert entry in expanded table
put(oldTable[i].key, oldTable[i].value);
numKeys++;
}
}
}
/**
* Remove a table element by setting it to reference object DELETED.
*
* @param key
* The key of item being deleted.
* @return The previous value associated with the specified key, or null if
* there was no mapping for the key.
*/
@Override
public Object remove(Object key) {
// Find the first table element that is empty
// or the table that contains the key.
int index = find(key);
// If an empty element was found return null
if (table[index] == null) {
return null;
} else {
// key was found
table[index] = DELETED;
numDeletes++;
numKeys--;
return table[index].value;
}
}
@Override
public int size() {
return numKeys;
}
/**
* Finds either the target key or the first empty slot in the search chain
* using linear probing. pre: The table is not full
*
* @param key
* The key of the target object
* @return The position of the target or the first empty slot if the target
* is not in the table.
*/
private int find(Object key) {
// Calculate the starting index.
int index = key.hashCode() % table.length;
if (index < 0) {
index += table.length; // Make it positive
}
// increment index until an empty slot is reached or the key is found.
while ((table[index] != null) && (!table[index].key.equals(key))) {
index++;
// Check for wrap around
if (index >= table.length) {
index = 0; // Wrap around
}
}
return index;
}
public static void main(String[] args) {
HashTableOpen hashTable = new HashTableOpen();
hashTable.put("34", "İstanbul");
hashTable.put("44", "Malatya");
hashTable.put("77", "Yalova");
System.out.println("Value for key 44 is: " + hashTable.get("44"));
System.out.println("Key 06 is" + (hashTable.get("06") == null ? " not" : "") + " found in hash table...");
System.out.println("Key 34 is" + (hashTable.get("34") == null ? " not" : "") + " found in hash table...");
for (int i = 0; i < HashTableOpen.START_CAPACITY; i++) {
System.out.println(hashTable.table[i]);
}
}
}
In this blog we implement the index by storing each word and all the line numbers for that word as a single index entry.
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.text.Collator;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Locale;
import java.util.Map.Entry;
import java.util.StringTokenizer;
import java.util.TreeMap;
/**
* Building an Index/Glossary for a book using Map
*
*/
public class IndexGenerator {
// Data fields
/** Gets the collator for the default locale */
private final Collator collator = Collator.getInstance(Locale.getDefault());
/** The search tree used to store the index. */
private TreeMap<String, ArrayList<Integer>> index = new TreeMap<String, ArrayList<Integer>>(
collator);
public void buildIndexAllLines(BufferedReader br) throws IOException {
int lineNum = 0; // Line number
String nextLine; // Each data line
// Keep reading lines until done.
while ((nextLine = br.readLine()) != null) {
lineNum++;
// Create a StringTokenizer for the current data line
// using punctuation and white space as delimiters.
StringTokenizer tokens = new StringTokenizer(nextLine,
" ,.:-!?/%()\"“”");
// insert each token in the index.
while (tokens.hasMoreTokens()) {
String word = tokens.nextToken().toLowerCase();
ArrayList<Integer> lines = (ArrayList<Integer>) index.get(word);
// Get the list
if (lines == null) {
lines = new ArrayList<Integer>();
}
if (!lines.contains(lineNum)) {
lines.add(new Integer(lineNum));
}
index.put(word, lines); // Store new list.
}
}
}
public static void main(String[] args) throws IOException {
IndexGenerator app = new IndexGenerator();
BufferedReader br = new BufferedReader(new FileReader(args[0]));
app.buildIndexAllLines(br);
showIndex(app);
}
private static void showIndex(IndexGenerator app) {
Iterator<Entry<String, ArrayList<Integer>>> indexIter = app.index
.entrySet().iterator();
while (indexIter.hasNext()) {
Entry<String, ArrayList<Integer>> entry = indexIter.next();
StringBuffer buff = new StringBuffer(entry.getKey());
Iterator<Integer> valueIter = entry.getValue().iterator();
while (valueIter.hasNext()) {
Integer integer = (Integer) valueIter.next();
buff.append(", ").append(integer);
}
System.out.println(buff.toString());
}
}
}
The sample output is what follows:
bahçesinde, 13
bahçesindeki, 15
bakımından, 21
balyan’a, 5
barındığı, 13
barındırmak, 25
başkalarının, 5
batı, 7, 15, 21
bazılarıdır, 5
belirlenen, 17
benzer, 21
benzerlikler, 7
beylerbeyi, 1, 3, 5, 11, 15, 17, 19, 25, 29
biçimde, 27
biçiminde, 11
bir, 1, 3, 7, 9, 15, 17, 19, 23, 25, 29
biri, 1, 19, 25
import java.io.PrintStream;
import java.io.Serializable;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
/**
* Class to represent and build a Huffman tree.
*
*/
@SuppressWarnings("serial")
public class HuffmanTree implements Serializable {
// Nested classes
/** A datum in the Huffman tree */
public static class HuffData implements Serializable {
// Data fields
/** The weight or probability assigned to this HuffData */
private double weight;
/** The alphabet symbol if this is a leaf */
private Character symbol;
public HuffData(double weight, Character symbol) {
this.weight = weight;
this.symbol = symbol;
}
public Character getSymbol() {
return symbol;
}
}
// Data fields
/** A reference to the completed Huffman tree */
private BinaryTree<HuffData> huffTree;
/**
* A Comparator for Huffman trees; nested class
*/
private static class CompareHuffmanTrees implements
Comparator<BinaryTree<HuffData>> {
/**
* Compare two objects.
*
* @param
*/
@Override
public int compare(BinaryTree<HuffData> treeLeft,
BinaryTree<HuffData> treeRight) {
double wLeft = treeLeft.getData().weight;
double wRight = treeRight.getData().weight;
return Double.compare(wLeft, wRight);
}
}
/**
* Builds the Huffman tree using the given alphabet and weights. post:
* huffTree contains a reference to the Huffman tree.
*
* @param symbols
* An array of HuffData objects
*/
public void buildTree(HuffData[] symbols) {
Queue<BinaryTree<HuffData>> theQueue = new PriorityQueue<BinaryTree<HuffData>>(
symbols.length, new CompareHuffmanTrees());
// Load the queue with the leaves.
// The loop loads the priority queue with trees consisting of just leaf
// nodes.
// Each leaf node contains a HuffData object with the weight and
// alphabet symbol.
for (HuffData nextSymbol : symbols) {
BinaryTree<HuffData> binaryTree = new BinaryTree<HuffData>(nextSymbol, null, null);
theQueue.offer(binaryTree);
}
// Build the tree from the bottom up. The first step is to remove the
// first two tree references from the priority
// queue and combine them to form a new tree. We insert the new tree
// back into the priority queue.
// Again we remove the first two references and combine them.
// We repeat the process until there is one tree in the queue, and
// that will be the Huffman tree.
while (theQueue.size() > 1) { // While the priority queue has more
// than one item
BinaryTree<HuffData> left = theQueue.poll();
BinaryTree<HuffData> right = theQueue.poll();
double wl = left.getData().weight;
double wr = right.getData().weight;
HuffData sum = new HuffData(wl + wr, null);
BinaryTree<HuffData> newTree = new BinaryTree<HuffData>(sum, left, right);
theQueue.offer(newTree);
}
// The queue should now contain only one item.
huffTree = theQueue.poll();
}
public static void main(String[] args) {
HuffData[] symbols = { new HuffData(22, 'c'), new HuffData(13, 'b'),
new HuffData(32, 'd'), new HuffData(64, 'a'),
new HuffData(103, 'e'), };
HuffmanTree huffmanTree = new HuffmanTree();
huffmanTree.buildTree(symbols);
huffmanTree.printCode(System.out);
System.out.println("\n'1110' decoded to: " + huffmanTree.decode("1110"));
}
/**
* Outputs the resulting code.
* To display the code for each alphabet symbol, we perform a preorder traversal of the finl tree.
* When we traverse the left subtree we append a 0 to the code, and when we traverse the right
* subtree, we append a 1 to the code.
*
* @param out
* A PrintStream to write the output to.
* @param code
* The code up to this node.
* @param tree
* The current node in the tree
*/
private void printCode(PrintStream out, String code, BinaryTree<HuffData> tree) {
HuffData theData = tree.getData();
if (theData.symbol != null) {
if (theData.symbol.equals(' ')) {
out.println("space: " + code);
} else {
out.println(theData.symbol + ": " + code);
}
} else {
printCode(out, code + "0", tree.getLeftSubTree());
printCode(out, code + "1", tree.getRigthSubTree());
}
}
/**
* Outputs the resulting code.
*
* @param out
* A PrintStream to write the output to
*/
public void printCode(PrintStream out) {
printCode(out, "", huffTree);
}
/**
* Method to decode a message that is input as a string of digit characters '0' and '1'
* @param codedMessage
* @return The decoded message as a String.
*/
public String decode(String codedMessage) {
StringBuffer result = new StringBuffer();
BinaryTree<HuffData> currentTree = huffTree;
for (int i = 0; i < codedMessage.length(); i++) {
if (codedMessage.charAt(i) == '1') {
currentTree = currentTree.getRigthSubTree();
} else {
currentTree = currentTree.getLeftSubTree();
}
if (currentTree.isLeaf()) {
HuffData theData = currentTree.getData();
result.append(theData.symbol);
currentTree = huffTree;
}
}
return result.toString();
}
}
The out is
e: 0
a: 10
d: 110
b: 1110
c: 1111
'1110' decoded to: b
/**
* interface that defines a priority queue. A priority queue is similar to a queue, except that
* items are removed in priority order, where the smallest value is considered the highest priority.
* The PriorityQueue interface is effectively the same as the Queue interface. The differences
* are in the specification for the peek and remove methods. These are defined to return
* the smallest item in the queue rather than the oldest item in the queue.
*
* The smallest item is always removed first from a priority queue(the smallest item has the highest priority)
* just as it is for a heap.
*
* Note that classes that implement the PriorityQueue interface are free to require that the objects
* that are inserted implement Comparable by documenting that an exception will be thrown if they don't.
*
*/
public interface PriorityQueue {
/**
* insert an item into the queue based on its priority.
* post: The item is inserted into the priority queue.
* @param item The item to be inserted.
*/
void insert(Object item);
/**
* Peek at the smallest item in the queue.
* post: The priority queue remains unchanged.
* @return The item with the smallest priority value.
* @throws EmptyQueueException if the queue is empty.
*/
Object peek();
/**
* Remove the smallest item in the queue.
* post: The item is no longer in the queue.
* @return The item with the smallest priority value.
* @throws EmptyQueueException if the queue is empty.
*/
Object remove();
/**
* Return the size of the queue.
* @return The number of items in the queue.
*/
int getSize();
/**
* Determine whether the queue is empty.
* @return true if the queue is empty.
*/
boolean isEmpty();
}
import java.util.ArrayList;
/**
* The HeapPriorityQueue implements PriorityQueue interface by building a heap
* in an ArrayList. The heap is structured so that the 'smallest' item is at the
* top.
*
*/
public class HeapPriorityQueue implements PriorityQueue {
// Data fields
/** The ArrayList to hold the data */
private ArrayList<Object> theData = new ArrayList<Object>();
// Methods
/**
* Compare two items using their natural ordering. pre: Both left and right
* implement Comparable.
*
* @param left
* One item
* @param right
* The other item
* @return Negative integer if left less than right, 0 if left equals right,
* positive integer if left > right
* @throws ClassCastException
* if items are not Comparable.
*/
@SuppressWarnings({ "unchecked" })
protected int compare(Object left, Object right) {
Comparable<Object> comparable = (Comparable<Object>) left;
return comparable.compareTo(right);
}
protected void swap(int parent, int child) {
Object temp = theData.get(parent);
theData.set(parent, theData.get(child));
theData.set(child, temp);
}
/**
* Insert an item into the priority queue. pre: The item to be inserted
* implements Comparable and the ArrayList theData is in heap order. post:
* The item is in the priority queue and theData is in heap order.
*/
@Override
public void insert(Object item) {
// Add the item to the heap.
theData.add(item);
// Child is newly inserted item.
int child = theData.size() - 1;
int parent = (child - 1) / 2; // Find child's parent.
// Reheap
while (parent >= 0
&& compare(theData.get(parent), theData.get(child)) > 0) {
swap(parent, child);
child = parent;
parent = (child - 1) / 2;
}
}
/**
* Peeks at the smallest item in the queue.
*/
@Override
public Object peek() {
if (isEmpty()) {
throw new EmptyQueueException();
} else {
return theData.get(0);
}
}
/**
* Remove an item from the priority queue. pre: The ArrayList theData is in
* heap order post: The ArrayList theData is in heap order
*
* @return The item with the smallest priority value.
* @throws EmptyQueueException
* if the queue is empty.
*/
@Override
public Object remove() {
if (isEmpty()) {
throw new EmptyQueueException();
}
// Save the top of the heap.
Object result = theData.get(0);
// If only one item then remove it.
if (theData.size() == 1) {
theData.remove(0);
return result;
}
// Remove the last item from the ArrayList and place it into the first
// position.
theData.set(0, theData.remove(theData.size() - 1));
// The parent starts at the top.
int parent = 0;
while (true) {
int leftChild = 2 * parent + 1;
if (leftChild >= theData.size()) {
// The item has moved down the tree so that it has no children.
break;
}
int rightChild = leftChild + 1; // 2 * p + 2
int minChild = leftChild; // Assume left child is smaller.
// See whether right child is smaller
if (rightChild < theData.size()
&& compare(theData.get(leftChild), theData.get(rightChild)) > 0) {
minChild = rightChild;
}
// assert: minChild is the index of the smaller child.
// Move smaller child up heap if necessary.
if (compare(theData.get(parent), theData.get(minChild)) > 0) {
swap(parent, minChild);
parent = minChild;
} else { // Heap property is restored.
break;
}
}
return result;
}
@Override
public int getSize() {
return theData.size();
}
@Override
public boolean isEmpty() {
return theData.size() == 0;
}
public static void main(String[] args) {
HeapPriorityQueue app = new HeapPriorityQueue();
app.theData.add(6);
app.theData.add(18);
app.theData.add(29);
app.theData.add(20);
app.theData.add(28);
app.theData.add(39);
app.theData.add(66);
app.theData.add(37);
app.theData.add(26);
app.theData.add(76);
app.theData.add(32);
app.theData.add(74);
app.theData.add(89);
showHeap(app);
app.insert(8);
showHeap(app);
app.remove();
showHeap(app);
}
private static void showHeap(HeapPriorityQueue app) {
for (int i = 0; i < app.theData.size(); i++) {
System.out.print(app.theData.get(i) + " ");
}
System.out.println();
}
}
import java.util.ArrayList;
/**
* Class for Heap which is a complete binary tree.
*
*/
public class Heap {
// Data field.
private ArrayList<Integer> heap;
public Heap() {
heap = new ArrayList<Integer>();
init();
}
/**
* insert the new value into the lower right position. Then move the
* inserted value up the heap, by comparing to the values stored in its
* ancestor nodes. The parent is in position (c-1) / 2. Note that for a node
* at position p, the left child is at 2p+1, and the right child is at
* position 2p+2.
*
* @param elem
*/
public void insert(Integer elem) {
heap.add(elem);
int child = heap.size() - 1;
int parent = (child - 1) / 2;
while (parent >= 0 && heap.get(parent) > heap.get(child)) {
int parentElem = heap.get(parent);
heap.set(parent, heap.get(child));
heap.set(child, parentElem);
child = parent;
parent = (child - 1) / 2;
}
}
/**
* In removing elements from a heap, we must always remove and save the
* element at top of the heap, which is the smallest element.
*/
public void remove() {
int lastItemInHeap = heap.get(heap.size() - 1);
heap.set(0, lastItemInHeap);
heap.remove(heap.size() - 1);
int parent = 0;
while (true) {
int leftChild = 2 * parent + 1;
int rightChild = leftChild + 1; // 2 * p + 2
int minChild = leftChild;
if (leftChild >= heap.size()) {
// The item has moved down the tree so that it has no children.
break;
}
// Assume the smallest child is leftChild.
if (rightChild < heap.size()
&& heap.get(rightChild) < heap.get(leftChild)) {
minChild = rightChild;
}
if (heap.get(parent) > heap.get(minChild)) {
// Swap
int temp = heap.get(parent);
heap.set(parent, heap.get(minChild));
heap.set(minChild, temp);
parent = minChild;
} else {
// It's smaller than both its children.
break;
}
}
}
public static void main(String[] args) {
Heap app = new Heap();
app.showHeap();
app.insert(8);
app.showHeap();
app.remove();
app.showHeap();
}
private void showHeap() {
for (Integer integer : heap) {
System.out.print(integer + " ");
}
System.out.println();
}
// Construct the array list.
private void init() {
heap.add(6);
heap.add(18);
heap.add(29);
heap.add(20);
heap.add(28);
heap.add(39);
heap.add(66);
heap.add(37);
heap.add(26);
heap.add(76);
heap.add(32);
heap.add(74);
heap.add(89);
}
}
The output is:
6 18 29 20 28 39 66 37 26 76 32 74 89
6 18 8 20 28 39 29 37 26 76 32 74 89 66
8 18 29 20 28 39 66 37 26 76 32 74 89
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.text.Collator;
import java.text.DecimalFormat;
import java.util.Iterator;
import java.util.Locale;
import java.util.StringTokenizer;
import java.util.TreeSet;
/**
* Class to build an index/glossary.
*/
public class IndexGenerator {
// Data fields
/** Gets the collator for the default locale */
private final Collator collator = Collator.getInstance(Locale.getDefault());
/** The search tree used to store the index. */
private TreeSet<String> index = new TreeSet%lt;String>(collator);
/** String for formatting numbers as 4 digits with leading zeros. */
private static final String LEADING_ZEROS = "0000";
// Methods
/**
* Reads each word from the file referenced by Buffered Reader and stores it
* in the tree index. post:Lowercase form of each word with line number
* stored in the index.
*
* @param br
* A reference to the data file.
* @throws IOException
*/
public void buildIndex(BufferedReader br) throws IOException {
DecimalFormat threeDigits = new DecimalFormat(LEADING_ZEROS);
int lineNum = 0;
String nextLine;
// Keep reading lines until done.
while ((nextLine = br.readLine()) != null) {
lineNum++;
StringTokenizer tokens = new StringTokenizer(nextLine,
" ,.:-!?/%()\"“”");
while (tokens.hasMoreTokens()) {
String nextToken = tokens.nextToken().toLowerCase();
index.add(nextToken + ", " + threeDigits.format(lineNum));
}
}
}
/**
* Performs an inorder traversal of tree index, one word per line
*/
public void showIndex() {
Iterator<String> indexIter = index.iterator();
// Use iterator indexIter to access and display tree data
String prevToken = "";
while (indexIter.hasNext()) {
StringBuffer sb = new StringBuffer();
String currToken = indexIter.next();
String[] parts = currToken.split(", ");
if (!parts[0].equals(prevToken)) {
System.out.println();
for (int i = 0; i < parts.length; i++) {
sb.append(parts[i]).append(", ");
}
prevToken = parts[0];
} else {
for (int i = 1; i < parts.length; i++) {
sb.append(parts[i]).append(", ");
}
}
System.out.print(sb.toString());
}
}
public static void main(String[] args) throws IOException {
IndexGenerator app = new IndexGenerator();
BufferedReader br = new BufferedReader(new FileReader(args[0]));
app.buildIndex(br);
app.showIndex();
}
}
Glossary generated for a book titled Beylerbeyi Palace:
barındırmak, 0025,
başkalarının, 0005,
batı, 0007, 0015, 0021,
bazılarıdır, 0005,
belirlenen, 0017,
benzer, 0021,
benzerlikler, 0007,
beylerbeyi, 0001, 0003, 0005, 0011, 0015, 0017, 0019, 0025, 0029,
biçimde, 0027,
biçiminde, 0011,
bir, 0001, 0003, 0007, 0009, 0015, 0017, 0019, 0023, 0025, 0029,
biri, 0001, 0019, 0025,
birini, 0011,
import javax.swing.JOptionPane;
/**
* Class that solves Towers of Hanoi problem.
*/
public class TowersOfHanoi {
public static String showMoves(int n, char startPeg, char destPeg,
char tempPeg) {
if (n == 1) {
return "Move disk 1 from peg " + startPeg + " to peg " + destPeg
+ "\n";
} else {
return showMoves(n - 1, startPeg, tempPeg, destPeg) + "Move disk "
+ n + " from peg " + startPeg + " to peg " + destPeg + "\n"
+ showMoves(n - 1, tempPeg, destPeg, startPeg);
}
}
public static void main(String[] args) {
String nDisks = JOptionPane.showInputDialog("Enter number of disks");
String startPeg = JOptionPane
.showInputDialog("Enter start peg (L, M, R)");
String destPeg = JOptionPane
.showInputDialog("Enter destination peg (L, M, R), but not "
+ startPeg);
String tempPeg = JOptionPane
.showInputDialog("Enter temporary peg (L, M, R), but not "
+ startPeg + " or " + destPeg);
String moves = showMoves(Integer.parseInt(nDisks), startPeg
.toUpperCase().charAt(0), destPeg.toUpperCase().charAt(0),
tempPeg.toUpperCase().charAt(0));
JOptionPane.showMessageDialog(null, moves);
}
}
public static int binarySearch(Object[] items, Comparable<Object> target,
int first, int last) {
if (first > last) {
return -1;
} else {
int middle = (first + last) / 2;
int compResult = target.compareTo(items[middle]);
if (compResult == 0) {
return middle; // Base case for successful search
} else if (compResult < 0) {
return binarySearch(items, target, first, middle - 1);
} else { // > 0
return binarySearch(items, target, middle + 1, last);
}
}
}
import java.util.EmptyStackException;
import java.util.Stack;
import java.util.StringTokenizer;
import javax.swing.JOptionPane;
/** Translates an infix expression to a postfix expression. */
public class InfixToPostfix {
// Nested class to report a syntax error.
@SuppressWarnings("serial")
public static class SyntaxErrorException extends Exception {
public SyntaxErrorException(String message) {
super(message);
}
}
// Constant
/** A list of operators */
private static final String OPERATORS = "+-*/()";
// The precedence of the operators, matches order in OPERATORS.
private static final int[] PRECEDENCE = { 1, 1, 2, 2, -1, -1 };
// Data fields
/** Stack of operators */
private Stack<Character> operatorStack;
/** The postfix string being formed */
private StringBuffer postfix;
// Methods
/**
* Extracts and processes each token in infix and returns the equivalent
* postfix.
*
* @param infix
* The infix expression.
* @return The equivalent postfix.
* @throws SyntaxErrorException
*/
public String convert(String infix) throws SyntaxErrorException {
postfix = new StringBuffer();
operatorStack = new Stack<Character>();
// Process each token.
StringTokenizer infixTokens = new StringTokenizer(infix);
try {
while (infixTokens.hasMoreTokens()) {
String nextToken = infixTokens.nextToken();
char ch = nextToken.charAt(0);
// Is it an operand?
if (Character.isJavaIdentifierStart(ch)
|| Character.isDigit(ch)) {
postfix.append(ch);
postfix.append(' ');
} else if (isOperator(ch)) {
processOperator(ch);
} else {
throw new SyntaxErrorException(
"Unexpected char encountered: " + ch);
}
}
// Pop any remaining operators and append them to the postfix.
while (!operatorStack.empty()) {
char ch = operatorStack.pop();
// Any '(' on the stack is not matched.
if (ch == '(') {
throw new SyntaxErrorException("Unmatched opening parentheses");
}
postfix.append(ch);
postfix.append(' ');
}
// assert: Stack is empty, return result.
return postfix.toString();
} catch (EmptyStackException e) {
// Pop was attempted on an empty stack.
throw new SyntaxErrorException("Syntax error: The stack is empty");
}
}
public static void main(String[] args) {
InfixToPostfix app = new InfixToPostfix();
String infix = JOptionPane.showInputDialog("Enter an infix expression");
try {
PostfixEvaluator postfixApp = new PostfixEvaluator();
String postfixForm = app.convert(infix);
JOptionPane.showMessageDialog(null, "Infix expression " + infix
+ "\nconverts to " + postfixForm);
JOptionPane.showMessageDialog(null, "The postfix value is = "
+ postfixApp.eval(postfixForm));
} catch (Exception e) {
JOptionPane.showMessageDialog(null, e.getMessage());
}
System.exit(0);
}
/**
* Processes operator op by updating operatorStack
*
* @param op
* The operator
* @throws EmptyStackException
*/
private void processOperator(char op) {
if (operatorStack.empty() || op == '(') {
operatorStack.push(op);
} else {
// Peek the operator stack and let topOp be top operator.
char topOp = operatorStack.peek();
if (precedence(op) > precedence(topOp)) {
operatorStack.push(op);
} else {
// Pop all stacked operators with equal or higher precedence
// than op.
while (!operatorStack.empty()
&& precedence(op) <= precedence(topOp)) {
operatorStack.pop();
if (topOp == '(') {
// Matching '(' popped - exit loop
break;
}
postfix.append(topOp);
postfix.append(' ');
if (!operatorStack.empty()) {
// Reset topOp.
topOp = operatorStack.peek();
}
}
// assert: Operator stack is empty or current operator
// precedence > top of stack operator precedence.
// The closing parenthesis is considered processed when an opening parentheses is popped from the stack
if (op != ')') {
operatorStack.push(op);
}
}
}
}
/**
*
* @param ch
* @return The precedence of operator op.
*/
private int precedence(char op) {
return PRECEDENCE[OPERATORS.indexOf(op)];
}
/**
*
* @param ch
* @return true if ch is an operator
*/
private boolean isOperator(char ch) {
return OPERATORS.indexOf(ch) != -1;
}
}
import java.util.EmptyStackException;
import java.util.Stack;
import java.util.StringTokenizer;
public class PostfixEvaluator {
// Nested class to report a syntax error.
@SuppressWarnings("serial")
public static class SyntaxErrorException extends Exception {
public SyntaxErrorException(String message) {
super(message);
}
}
// Constant
/** A list of operators */
private static final String OPERATORS = "+-*/";
// Data fields
/** The operand stack */
Stack<Integer> operandStack;
// Methods
/**
* Evaluates a postfix expression.
*
* @param expression
* The expression to be evaluated.
* @return The value of the expression.
* @throws SyntaxErrorException
* if a syntax error is detected.
*/
public int eval(String expression) throws SyntaxErrorException {
// Create an empty stack.
operandStack = new Stack<Integer>();
// Process each token.
StringTokenizer tokens = new StringTokenizer(expression);
try {
while (tokens.hasMoreElements()) {
String nextToken = tokens.nextToken();
char ch = nextToken.charAt(0);
// Does it start with a digit?
if (Character.isDigit(ch)) {
// Get the integer value
int value = Integer.parseInt(nextToken);
// Push the value onto the operand stack.
operandStack.push(value);
} else if (isOperator(ch)) { // Is it an operator?
// Evaluate the operator
int result = evalOperator(ch);
// Push the result onto the operand stack.
operandStack.push(result);
} else { // Invlid character
throw new SyntaxErrorException(
"Invalid character encountered");
}
}
// No more tokens left, pop result from the operand stack.
int answer = operandStack.pop().intValue();
// Operand stack should be empty.
if (operandStack.empty()) {
return answer;
} else {
// Indicate syntax error.
throw new SyntaxErrorException(
"Syntax error: Stack should be empty");
}
} catch (EmptyStackException e) {
// Pop was attempted on an empty stack.
throw new SyntaxErrorException("Syntax error: The stack is empty");
}
}
/**
* Evaluates the current operation This method pops the two operands off the
* operand stack and applies the operator.
*
* @param op
* A character representing the operator.
* @return The result of applying the operator.
* @throws EmptyStackException
* if pop is attempted on an empty stack.
*/
private int evalOperator(char op) {
int rhs = operandStack.pop().intValue();
int lhs = operandStack.pop().intValue();
int result = 0;
// Evaluate the operator
switch (op) {
case '+':
result = lhs + rhs;
break;
case '-':
result = lhs - rhs;
break;
case '*':
result = lhs * rhs;
break;
case '/':
result = lhs / rhs;
break;
}
return result;
}
private boolean isOperator(char ch) {
return OPERATORS.indexOf(ch) != -1;
}
public static void main(String[] args) throws SyntaxErrorException {
if (0 == args.length) {
System.err.println("Please enter the expression to evaluate...");
System.exit(1);
}
String expression = args[0];
PostfixEvaluator app = new PostfixEvaluator();
System.out.println("The value of the expression is: "
+ app.eval(expression));
}
}
In this article, I'd like to provide a solution to the question using Java programming language:
For example if a linked list given to you is
Ahmet -> Ali -> Hasan -> Huseyin -> Ertugrul -> Osman
You are expected to provide the list as:
Ali -> Ahmet -> Huseyin -> Hasan -> Osman -> Ertugrul
/**
* @author NÇ
*/
public class SwapNodes {
public static void main(String[] args) {
Node ahmet = new Node("Ahmet");
Node ali = new Node("Ali");
ahmet.next = ali;
Node hasan = new Node("Hasan");
ali.next = hasan;
Node huseyin = new Node("Hüseyin");
hasan.next = huseyin;
Node ertugrul = new Node("Ertugrul");
huseyin.next = ertugrul;
Node osman = new Node("Osman");
ertugrul.next = osman;
traverse(ahmet);
System.out.println("\nAfter swapping...\n");
Node swapped = swapAdjacentPairs(ahmet);
traverse(swapped);
}
/**
* Traverse the linked list.
*
* @param head
* The linked list's head node.
*/
private static void traverse(Node head) {
while (head != null) {
System.out.print(head.data);
if (head.next != null) {
System.out.print(" ==> ");
}
head = head.next; // Advance down the list.
}
System.out.println();
}
private static Node swapAdjacentPairs(Node head) {
if (head == null || head.next == null) {
return head;
}
Node nextNode = head.next;
Node nextPairNode = head.next.next;
head.next.next = head;
head.next = swapAdjacentPairs(nextPairNode);
return nextNode;
}
/**
* A Node is the building block for a single-linked list.
*
*/
private static class Node {
// Data fields
/** The reference to the data */
private Object data;
/** The reference to the next node */
private Node next;
// Constructors
/**
* Creates a new node with a null text field.
*
* @param dataItem
* The data stored.
*/
private Node(Object dataItem) {
data = dataItem;
next = null;
}
/**
* Creates a new node that references another node.
*
* @param dataItem
* The data stored
* @param nodeRef
* The node referenced by new node
*/
private Node(Object dataItem, Node nodeRef) {
data = dataItem;
next = nodeRef;
}
}
}
Note that a Palindrome is a string that reads the same in left-to-right or right-to-left
For example: "step on no pets"
import java.util.Stack;
/**
* Class with methods to check whether a string is a palindrome
*
* @author NÇ
*
*/
public class Palindrome {
/** String to store in stack */
private String str;
/** Stack to hold characters */
private Stack<Character> charStack = new Stack<Character>();
/**
* Store the argument string in a stack of characters.
*
* @param str
* String of characters to store in the stack.
*/
public Palindrome(String str) {
this.str = str;
fillCharStack();
}
/**
* Method to fill a stack of characters from an input string
*/
private void fillCharStack() {
for (int i = 0; i < str.length(); i++) {
char nextChar = str.charAt(i);
charStack.push(nextChar);
}
}
/**
* post: The stack is empty.
*
* @return The string containing the words in the stack
*/
private String reverse() {
StringBuffer result = new StringBuffer();
while (!charStack.empty()) {
result.append(charStack.pop());
}
return result.toString();
}
public boolean isPalindrome() {
return str.equalsIgnoreCase(reverse());
}
public static void main(String[] args) {
String s = args[0];
Palindrome app = new Palindrome(s);
boolean result = app.isPalindrome();
System.out.println("'" + s + "'"
+ (result == true ? " is " : " is not ") + " a palindrome");
}
}