· 6 years ago · Feb 22, 2020, 05:32 PM
1package symbolTable;
2
3import java.util.Scanner;
4import edu.princeton.cs.algs4.Queue;
5import java.util.NoSuchElementException;
6
7/**
8 * The <code>OrderedSymbolTable </code> represents a key-value pair
9 * that implements the API on p.366 using in the book
10 * " an sroted linked list in Algorithms 4th edition"
11 * by Robert Sedgewick.
12 */
13
14public class OrderedSymbolTable<Key extends Comparable<Key>, Value> {
15
16 private Node first; // first node in the linked list
17
18 private class Node {
19 // Linked list node
20 Key key;
21 Value value;
22 Node next;
23
24 public Node(Key key, Value value) {
25 this.key = key;
26 this.value = value;
27 }
28 }
29
30
31 public void put(Key key, Value value) {
32 if(key == null)
33 throw new IllegalArgumentException("Keey must not be null");
34
35 if(value == null) {
36 delete(key);
37 return;
38 }
39
40 Node newNode = new Node(key, value);
41
42 if(first == null || first.key.compareTo(newNode.key) >= 0) {
43 newNode.next = first;
44 first = newNode;
45 } else {
46 /* Locate the node before point of insertion */
47 Node currentNode = first;
48
49 while((currentNode.next != null) &&
50 (currentNode.key.compareTo(newNode.key) < 0)) {
51 currentNode.next = newNode;
52 }
53
54 newNode.next = currentNode.next;
55 currentNode.next = newNode;
56 }
57
58
59 }
60
61 public Value get(Key key) {
62 if(key == null)
63 throw new IllegalArgumentException("Key must not be null");
64
65 // If list is empty
66 if(isEmpty())
67 return null;
68
69 // Navigate through list, return associated value.
70 for(Node currentNode = first; currentNode != null; currentNode = currentNode.next) {
71 if(key.equals(currentNode.key)) {
72 return currentNode.value; // Search hit
73 }
74 }
75 return null; // Search miss
76 }
77
78 public void delete(Key key) {
79 if(key == null)
80 throw new IllegalArgumentException("Key must not be null");
81
82 if(isEmpty() || !contains(key))
83 return;
84
85 // Remove key-value pair from table
86 Node currentNode = first;
87 while(currentNode.key.compareTo(key) != 0) {
88 currentNode = currentNode.next;
89 }
90
91 // Rely on garbage collector for deallocation
92 currentNode = currentNode.next;
93 }
94
95 /*public int rank(Key key) {
96 if(key == null)
97 throw new IllegalArgumentException("Key must not be null");
98
99 int low = 0;
100 int high = size - 1;
101
102 while(low <= high) {
103 int middle = low + (high - low) / 2;
104
105 int comparison = key.compareTo(keys[middle]);
106 if(comparison < 0) {
107 high = middle - 1;
108 } else if(comparison > 0) {
109 middle = + 1;
110 } else {
111 return middle;
112 }
113 }
114
115 return low;
116 } */
117
118 public boolean contains(Key key) {
119 if(key == null)
120 throw new IllegalArgumentException("Key must not be null");
121 return get(key) != null;
122 }
123
124
125 /*public Iterable<Key> keys() {
126 return keys(min(), max());
127 }*/
128
129 /*public Iterable<Key> keys(Key lo, Key hi) {
130 if (lo == null) throw new IllegalArgumentException("first argument to keys() is null");
131 if (hi == null) throw new IllegalArgumentException("second argument to keys() is null");
132
133 Queue<Key> queue = new Queue<Key>();
134 if (lo.compareTo(hi) > 0) return queue;
135 for (int i = rank(lo); i < rank(hi); i++)
136 queue.enqueue(keys[i]);
137 if (contains(hi)) queue.enqueue(keys[rank(hi)]);
138 return queue;
139 } */
140
141
142 public boolean isEmpty() {
143 return first == null;
144 }
145
146 //public int size() {
147 //return size;
148 //}
149
150 public Key max() {
151 if(isEmpty())
152 throw new NoSuchElementException("Empty symbol table");
153
154 Key max = first.key;
155 // Navigate through list for min value
156 while(first != null) {
157 if(max.compareTo(first.key) < 0) {
158 max = first.key;
159 }
160 }
161 return max;
162 }
163 public Key min() {
164 if(isEmpty())
165 throw new NoSuchElementException("Empty symbol table");
166
167 Key min = first.key;
168 // Navigate through list for min value
169 while(first != null) {
170 if(min.compareTo(first.key) > 0) {
171 min = first.key;
172 }
173 }
174 return min;
175 }
176
177 public static void main(String[] args) {
178 Scanner scnr = new Scanner(System.in);
179
180 }
181}