Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.LinkedList;
- import java.util.Queue;
- public class Q3_1_3 {
- public class table<Key extends Comparable<Key>, Value> {
- private class Node {
- private Key key;
- private Value value;
- private Node next;
- public Node(Key key, Value value, Node next) {
- this.key = key;
- this.value = value;
- this.next = next;
- }
- }
- private Node first;
- private int size;
- public int size() {
- return size;
- }
- public boolean isEmpty() {
- return size == 0;
- }
- public void put(Key key, Value value) {
- if (value == null) {
- delete(key);
- return;
- }
- if (isEmpty()) {
- first = new Node(key, value, null);
- size++;
- return;
- }
- //Check first node
- if (first.key.compareTo(key) == 0) {
- first.value = value;
- return;
- } else if (first.key.compareTo(key) > 0) {
- first = new Node(key, value, first);
- size++;
- return;
- }
- //Check all other nodes
- for(Node node = first; node != null; node = node.next) {
- if (node.next != null) {
- if (node.next.key.compareTo(key) == 0) {
- node.next.value = value;
- return;
- } else if (node.next.key.compareTo(key) > 0) {
- Node newNode = new Node(key, value, node.next);
- node.next = newNode;
- size++;
- return;
- }
- } else {
- Node newNode = new Node(key, value, null);
- node.next = newNode;
- size++;
- return;
- }
- }
- }
- public Value get(Key key) {
- for(Node node = first; node != null; node = node.next) {
- if (node.key.compareTo(key) == 0) {
- return node.value;
- }
- }
- return null;
- }
- public void delete(Key key) {
- if (isEmpty()) {
- return;
- }
- //Check first node
- if (first.key.compareTo(key) == 0) {
- first = first.next;
- size--;
- return;
- }
- //Check all other nodes
- for(Node node = first; node != null; node = node.next) {
- if (node.next != null && node.next.key.compareTo(key) == 0) {
- node.next = node.next.next;
- size--;
- return;
- }
- }
- }
- public boolean indexkey(Key key) {
- for(Node node = first; node != null; node = node.next) {
- if (node.key.compareTo(key) == 0) {
- return true;
- }
- }
- return false;
- }
- public boolean indexval(String Value) {
- for(Node node = first; node !=null ; node = node.next) {
- if(node.value.equals(Value)) {
- return true;
- }
- }
- return false;
- }
- public int size(Key low, Key high) {
- int size = 0;
- boolean inTheRange = false;
- for(Node node = first; node != null; node = node.next) {
- if (!inTheRange) {
- if (node.key.compareTo(low) == 0
- || node.key.compareTo(low) > 0) {
- size++;
- inTheRange = true;
- }
- } else {
- if (node.key.compareTo(high) == 0
- || node.key.compareTo(high) < 0) {
- size++;
- } else {
- return size;
- }
- }
- }
- return size;
- }
- public Iterable<Key> keys(Key low, Key high) {
- Queue<Key> keys = new LinkedList<>();
- boolean inTheRange = false;
- for(Node node = first; node != null; node = node.next) {
- if (!inTheRange) {
- if (node.key.compareTo(low) == 0
- || node.key.compareTo(low) > 0) {
- keys.add(node.key);
- inTheRange = true;
- }
- } else {
- if (node.key.compareTo(high) == 0
- || node.key.compareTo(high) < 0) {
- keys.add(node.key);
- } else {
- return keys;
- }
- }
- }
- return keys;
- }
- public Iterable<Key> keys() {
- Queue<Key> keys = new LinkedList<>();
- for(Node node = first; node != null; node = node.next) {
- keys.add(node.key);
- }
- return keys;
- }
- }
- public static void main(String[] args) {
- Q3_1_3 exercise3 = new Q3_1_3();
- table<Integer, String> table = exercise3.new table<>();
- //Test put() and get() and keys()
- //unsorted to show sort
- table.put(5, "Value 4");
- table.put(1, "Value 8");
- table.put(9, "Value 1");
- table.put(2, "Value 12");
- table.put(0, "Value 0");
- table.put(99, "Value 99");
- System.out.println();
- for(Integer key : table.keys()) {
- System.out.println("Key " + key + ": " + table.get(key));
- }
- System.out.println();
- //delete key 2 from the list
- System.out.println("Delete key 2");
- table.delete(2);
- for(Integer key : table.keys()) {
- System.out.println("Key " + key + ": " + table.get(key));
- }
- System.out.println();
- //index a key that does not exist, and a key that does
- System.out.println("index key 98: " + table.indexkey(98));
- System.out.println("index key 99: " + table.indexkey(99) );
- System.out.println();
- //index a value
- System.out.println("Index value 17: "+table.indexval("Value 17"));
- System.out.println("Index value 4: "+ table.indexval("Value 4"));
- System.out.println();
- //check if it is empty
- System.out.println("Is empty: " + table.isEmpty() );
- //check the size of the list
- System.out.println("Size: " + table.size() );
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement