redcaribou896 Profile

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class P4Wrapper {

// List
public interface List<E> extends Iterable<E> {

public int size();

public boolean isEmpty();

public boolean isMember(E e);

public void add(E e);

public void add(E e, int index);

public E first();

public E last();

public int firstIndex(E e);

public int lastIndex(E e);

public E get(int index);

public E replace(E e, int index);

public E remove(int index);

public boolean remove(E e);

public int removeAll(E e);

public void clear();

public Object[] toArray();


}

///////////////////// SinglyLinkedList
///////////
public static class SinglyLinkedList<E> implements List<E> {

@SuppressWarnings("hiding")
private class SinglyLinkedListIterator<E> implements Iterator<E>{

private Node<E> nextNode;

@SuppressWarnings("unchecked")
public SinglyLinkedListIterator() {
super();
this.nextNode = (Node<E>) header.getNext();
}

@Override
public boolean hasNext() {
return this.nextNode != null;
}

@Override
public E next() {
if (this.hasNext()) {
E result = this.nextNode.getElement();
this.nextNode = this.nextNode.getNext();
return result;
}
else {
throw new NoSuchElementException();
}
}

}


// node class
private static class Node<E>{
private E element;
private Node<E> next;
public Node(E element, Node<E> next) {
super();
this.element = element;
this.next = next;
}
public Node() {
super();
this.element = null;
this.next = null;

}
public E getElement() {
return element;
}
public void setElement(E element) {
this.element = element;
}
public Node<E> getNext() {
return next;
}
public void setNext(Node<E> next) {
this.next = next;
}

}

// private fields
private Node<E> header;
private int currentSize;



public SinglyLinkedList() {
this.header = new Node<>();
this.currentSize = 0;

}

@Override
public Iterator<E> iterator() {
return new SinglyLinkedListIterator<E>();
}

@Override
public int size() {
return this.currentSize;
}

@Override
public boolean isEmpty() {
return this.size() == 0;
}

@Override
public boolean isMember(E e) {
return this.firstIndex(e) >= 0;
}

@Override
public void add(E e) {

Node<E> temp = this.header;
while (temp.getNext() != null) {
temp = temp.getNext();
}
temp.setNext(new Node<E>(e, null));
this.currentSize++;

// cool
//this.getPosition(this.size() -1).setNext(new Node<E>(e, null));
//this.currentSize++;
}

@Override
public void add(E e, int index) {
if ((index <0) || (index > this.size())){
throw new IndexOutOfBoundsException();
}
if (index == this.size()) {
this.add(e);
}
else {
Node<E> temp = null;
if (index == 0) {
temp = this.header;
}
else {
temp = this.getPosition(index -1);
}
// add new node
Node<E> newNode = new Node<>();
newNode.setElement(e);
newNode.setNext(temp.getNext());
temp.setNext(newNode);
this.currentSize++;
}
}

@Override
public E first() {
if (this.isEmpty()) {
return null;
}
else {
return this.header.getNext().getElement();
}
}

@Override
public E last() {
if (this.isEmpty()) {
return null;
}
else {
Node<E> temp = this.header.getNext();
while (temp.getNext() != null) {
temp = temp.getNext();
}

return temp.getElement();
}
}

@Override
public int firstIndex(E e) {
int currentPosition = 0;
Node<E> temp = this.header.getNext();

while(temp != null) {
if (temp.getElement().equals(e)) {
return currentPosition;
}
else {
temp = temp.getNext();
currentPosition++;
}
}
return -1;

}

@Override
public int lastIndex(E e) {
int i=0;
int lastIndex = -1;
Node<E> temp = this.header.getNext();
while (temp != null) {
if (temp.getElement().equals(e)) {
lastIndex = i;
}
i++;
temp = temp.getNext();
}
return lastIndex;
}

private Node<E> getPosition(int index){
int currentPosition = 0;
Node<E> temp = this.header.getNext();

while (currentPosition != index) {
temp = temp.getNext();
currentPosition++;
}
return temp;
}

@Override
public E get(int index) {
if ((index <0) || (index >= this.currentSize)) {
throw new IndexOutOfBoundsException();
}
return this.getPosition(index).getElement();
}

@Override
public E replace(E e, int index) {
if ((index <0) || (index >= this.currentSize)) {
throw new IndexOutOfBoundsException();
}
Node<E> temp = this.getPosition(index);
E result = temp.getElement();
temp.setElement(e);
return result;
}

@Override
public E remove(int index) {
if ((index < 0) || (index >= this.currentSize)){
throw new IndexOutOfBoundsException();
}
int currentPosition =0;
Node<E> temp = this.header;
while(currentPosition != index) {
temp = temp.getNext();
currentPosition++;
}
Node<E> target = temp.getNext();
E result = target.getElement();
temp.setNext(target.getNext());
target.setElement(null);
target.setNext(null);
this.currentSize--;
return result;

}

@Override
public boolean remove(E e) {
int target = this.firstIndex(e);
if (target < 0) {
return false;
}
else {
this.remove(target);
return true;
}
}

@Override
public int removeAll(E e) {
int count = 0;
while (this.remove(e)) {
count++;
}
return count;
}

@Override
public void clear() {
while(!this.isEmpty()) {
this.remove(0);
}

}

@Override
public Object[] toArray() {
Object[] result = new Object[this.size()];
for (int i=0; i < this.size(); ++i) {
result[i]= this.get(i);
}
return result;
}

}

/////////////// MAP
////
public interface Map<K, V> {

public int size();

public boolean isEmpty();

public V get(K key);

public V put(K key, V value);

public V remove(K key);

public boolean contains(K key);

public List<K> getKeys();

public List<V> getValues();

}

////// Tree Node
public interface TreeNode<E> {

public E getValue();

}

/////////
// Binary Tree Node
public interface BinaryTreeNode<E> extends TreeNode<E> {

public BinaryTreeNode<E> getLeftChild();

public BinaryTreeNode<E> getRightChild();

public BinaryTreeNode<E> getParent();


}

//////
/// BinaryTreeNodeImp

public static class BinaryTreeNodeImp<E> implements BinaryTreeNode<E> {

private E value;

private BinaryTreeNode<E> leftChild;
private BinaryTreeNode<E> rightChild;
private BinaryTreeNode<E> parent;

public BinaryTreeNodeImp(E value, BinaryTreeNode<E> leftChild, BinaryTreeNode<E> rightChild,
BinaryTreeNode<E> parent) {
super();
this.value = value;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.parent = parent;
}

@Override
public E getValue() {
return this.value;
}

@Override
public BinaryTreeNode<E> getLeftChild() {
return this.leftChild;
}

@Override
public BinaryTreeNode<E> getRightChild() {
return this.rightChild;
}

@Override
public BinaryTreeNode<E> getParent() {
return this.parent;
}

public void setValue(E value) {
this.value = value;
}

public void setLeftChild(BinaryTreeNode<E> leftChild) {
this.leftChild = leftChild;
}

public void setRightChild(BinaryTreeNode<E> rightChild) {
this.rightChild = rightChild;
}

public void setParent(BinaryTreeNode<E> parent) {
this.parent = parent;
}

}

////// Key Value Pair
public interface KeyValuePair<K, V> {

public K getKey();
public V getValue();

}

/// Binary Search Tree
public static class BinarySearchTree<K, V> implements Map<K, V> {

// MapEntry class implements KeyValuePair

private static class MapEntry<K,V> implements KeyValuePair<K,V> {
private K key;
private V value;

public MapEntry(K key, V value) {
super();
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
@SuppressWarnings("unused")
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
@SuppressWarnings("unused")
public void setValue(V value) {
this.value = value;
}

}


private int currentSize;
private BinaryTreeNode<MapEntry<K,V>> root;
private Comparator<K> keyComparator;

public BinarySearchTree(Comparator<K> keyComparator) {
this.root = null;
this.currentSize = 0;
this.keyComparator = keyComparator;
}

@Override
public int size() {
return this.currentSize;
}

@Override
public boolean isEmpty() {
return this.size() == 0;
}

@Override
public V get(K key) {
return this.getAux(key, this.root);

}

private V getAux(K key, BinaryTreeNode<MapEntry<K, V>> N) {
if (N == null) {
return null; // not found
}
else {
int comparison = this.keyComparator.compare(key, N.getValue().getKey());
if (comparison == 0) {
return N.getValue().getValue();
}
else if (comparison < 0) {
return this.getAux(key, N.getLeftChild());
}
else {
return this.getAux(key, N.getRightChild());
}
}
}

@Override
public V put(K key, V value) {
if (this.root == null) {
MapEntry<K,V> M = new MapEntry<K,V>(key, value);
this.root = new
BinaryTreeNodeImp<MapEntry<K,V>>(M, null, null, null);
this.currentSize++;
return value;
}
else {
return this.putAux(key, value, (BinaryTreeNodeImp<MapEntry<K, V>>) this.root);
}
}

private V putAux(K key, V value, BinaryTreeNodeImp<MapEntry<K, V>> N) {
int comparison = this.keyComparator.compare(key, N.getValue().getKey());
if (comparison < 0) {
// left
if (N.getLeftChild() == null) {
MapEntry<K,V> M = new MapEntry<K,V>(key, value);
BinaryTreeNodeImp<MapEntry<K,V>> newNode =
new BinaryTreeNodeImp<MapEntry<K,V>>
(M, null, null, N);
N.setLeftChild(newNode);
this.currentSize++;
return value;
}
else {
return this.putAux(key, value,
(BinaryTreeNodeImp<MapEntry<K, V>>) N.getLeftChild());
}
}
else {
// right
if (N.getRightChild() == null) {
MapEntry<K,V> M = new MapEntry<K,V>(key, value);
BinaryTreeNodeImp<MapEntry<K,V>> newNode =
new BinaryTreeNodeImp<MapEntry<K,V>>
(M, null, null, N);
N.setRightChild(newNode);
this.currentSize++;
return value;
}
else {
return this.putAux(key, value,
(BinaryTreeNodeImp<MapEntry<K, V>>) N.getRightChild());
}

}
}

@Override
public V remove(K key) {
if (this.root == null) {
return null;
}
else {
int comparison = this.keyComparator.compare(key, this.root.getValue().getKey());
if (comparison == 0) {
// remove from root
if (this.isLeaf(this.root)) {
V result = this.root.getValue().getValue();
((BinaryTreeNodeImp<MapEntry<K, V>>) this.root).setValue(null);
this.root = null;
this.currentSize--;
return result;

}
else if (this.root.getRightChild() == null) {
V result = this.root.getValue().getValue();
this.root = this.root.getLeftChild();
this.currentSize--;
return result;
}
else {
V result = this.root.getValue().getValue();
BinaryTreeNodeImp<MapEntry<K, V>> S =
this.smallestChild((BinaryTreeNodeImp<MapEntry<K, V>>) this.root.getRightChild());
((BinaryTreeNodeImp<MapEntry<K, V>>) this.root).setValue(S.getValue());;
this.removeAux(S.getValue().getKey(), this.root.getRightChild());
return result;
}
}
else if (comparison < 0) {
// remove from left
return this.removeAux(key, this.root.getLeftChild());
}
else {
//remove right
return this.removeAux(key, this.root.getRightChild());

}
}
}

private boolean isLeaf(BinaryTreeNode<MapEntry<K, V>> N) {
return N.getLeftChild() == null && N.getRightChild() == null;
}

private V removeAux(K key, BinaryTreeNode<MapEntry<K, V>> N) {
// TODO Auto-generated method stub
return null;
}

private BinaryTreeNodeImp<MapEntry<K, V>> smallestChild(
BinaryTreeNodeImp<MapEntry<K, V>> N) {
BinaryTreeNodeImp<MapEntry<K, V>> temp = N;

while (temp.getLeftChild() != null) {
temp = (BinaryTreeNodeImp<MapEntry<K, V>>) temp.getLeftChild();
}
return temp;

}
@Override
public boolean contains(K key) {
return this.get(key) != null;
}

@Override
public List<K> getKeys() {
List<K> result = new SinglyLinkedList<K>();
this.getKeysAux(this.root, result);
return result;

}

private void getKeysAux(BinaryTreeNode<MapEntry<K, V>> N, List<K> result) {
if (N == null) {
return;
}
else {
this.getKeysAux(N.getLeftChild(), result);
result.add(N.getValue().getKey());
this.getKeysAux(N.getRightChild(), result);
}
}

@Override
public List<V> getValues() {
List<V> result = new SinglyLinkedList<V>();
this.getValuesAux(this.root, result);
return result;

}

private void getValuesAux(BinaryTreeNode<MapEntry<K, V>> N, List<V> result) {
if (N == null) {
return;
}
else {
this.getValuesAux(N.getLeftChild(), result);
result.add(N.getValue().getValue());
this.getValuesAux(N.getRightChild(), result);
}

}

public void print(PrintStream out) {
printAux(this.root, out, 0);

}

public void printAux(BinaryTreeNode<MapEntry<K, V>> N,
PrintStream out, int spaces) {
if (N == null) {
return;
}
else {
printAux(N.getRightChild(), out, spaces + 4);
// print this values
for (int i=0; i< spaces; ++i) {
out.print(" ");
}
out.println(N.getValue().getKey());
printAux(N.getLeftChild(), out, spaces + 4);

}
}

}

////
/// Integer Comparator
public static class IntegerComparator implements Comparator<Integer> {

public IntegerComparator() {

}

@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}

}
/////////////////////////////////////////////////////////////////////////////////////////////
//// FOR STUDENTS
//

/*
* Write a non-member method named findNLargestValues. This method finds N largest values in a
* Java array list of integers, and returns them in a new Java array list. The method receives as parameter
* the array list with the original integer data, and the number N. It returns an array list the N largest
* values, ORDERED from largest to smallest.
* Hint: Use a Binary Search Tree to organize the data.
*/
public static ArrayList<Integer> findNLargestValues(ArrayList<Integer> data, int N){
return null;
}
}

redcaribou896

ANSWERS

Subjects

Weekly leaderboard