-
Notifications
You must be signed in to change notification settings - Fork 1
/
ST.java
166 lines (145 loc) · 5.72 KB
/
ST.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.SortedMap;
import java.util.TreeMap;
/**
*
* @author asus
*/
public class ST<Key extends Comparable<Key>, Value> implements Iterable<Key> {
private TreeMap<Key, Value> st;
/**
* Initializes an empty symbol table.
*/
public ST() {
st = new TreeMap<Key, Value>();
}
/**
* Returns the value associated with the given key.
* @param key the key
* @return the value associated with the given key if the key is in the symbol table
* and <tt>null</tt> if the key is not in the symbol table
* @throws NullPointerException if <tt>key</tt> is <tt>null</tt>
*/
public Value get(Key key) {
if (key == null) throw new NullPointerException("called get() with null key");
return st.get(key);
}
/**
* Inserts the key-value pair into the symbol table, overwriting the old value
* with the new value if the key is already in the symbol table.
* If the value is <tt>null</tt>, this effectively deletes the key from the symbol table.
* @param key the key
* @param val the value
* @throws NullPointerException if <tt>key</tt> is <tt>null</tt>
*/
public void put(Key key, Value val) {
if (key == null) throw new NullPointerException("called put() with null key");
if (val == null) st.remove(key);
else st.put(key, val);
}
/**
* Removes the key and associated value from the symbol table
* (if the key is in the symbol table).
* @param key the key
* @throws NullPointerException if <tt>key</tt> is <tt>null</tt>
*/
public void delete(Key key) {
if (key == null) throw new NullPointerException("called delete() with null key");
st.remove(key);
}
/**
* Does this symbol table contain the given key?
* @param key the key
* @return <tt>true</tt> if this symbol table contains <tt>key</tt> and
* <tt>false</tt> otherwise
* @throws NullPointerException if <tt>key</tt> is <tt>null</tt>
*/
public boolean contains(Key key) {
if (key == null) throw new NullPointerException("called contains() with null key");
return st.containsKey(key);
}
/**
* Returns the number of key-value pairs in this symbol table.
* @return the number of key-value pairs in this symbol table
*/
public int size() {
return st.size();
}
/**
* Is this symbol table empty?
* @return <tt>true</tt> if this symbol table is empty and <tt>false</tt> otherwise
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* Returns all keys in the symbol table as an <tt>Iterable</tt>.
* To iterate over all of the keys in the symbol table named <tt>st</tt>,
* use the foreach notation: <tt>for (Key key : st.keys())</tt>.
* @return all keys in the sybol table as an <tt>Iterable</tt>
*/
public Iterable<Key> keys() {
return st.keySet();
}
/**
* Returns all of the keys in the symbol table as an iterator.
* To iterate over all of the keys in a symbol table named <tt>st</tt>, use the
* foreach notation: <tt>for (Key key : st)</tt>.
* @return an iterator to all of the keys in the symbol table
*/
public Iterator<Key> iterator() {
return st.keySet().iterator();
}
/**
* Returns the smallest key in the symbol table.
* @return the smallest key in the symbol table
* @throws NoSuchElementException if the symbol table is empty
*/
public Key min() {
if (isEmpty()) throw new NoSuchElementException("called min() with empty symbol table");
return st.firstKey();
}
/**
* Returns the largest key in the symbol table.
* @return the largest key in the symbol table
* @throws NoSuchElementException if the symbol table is empty
*/
public Key max() {
if (isEmpty()) throw new NoSuchElementException("called max() with empty symbol table");
return st.lastKey();
}
/**
* Returns the smallest key in the symbol table greater than or equal to <tt>key</tt>.
* @return the smallest key in the symbol table greater than or equal to <tt>key</tt>
* @param key the key
* @throws NoSuchElementException if the symbol table is empty
* @throws NullPointerException if <tt>key</tt> is <tt>null</tt>
*/
public Key ceil(Key key) {
if (key == null) throw new NullPointerException("called ceil() with null key");
SortedMap<Key, Value> tail = st.tailMap(key);
if (tail.isEmpty()) throw new NoSuchElementException();
return tail.firstKey();
}
/**
* Returns the largest key in the symbol table less than or equal to <tt>key</tt>.
* @return the largest key in the symbol table less than or equal to <tt>key</tt>
* @param key the key
* @throws NoSuchElementException if the symbol table is empty
* @throws NullPointerException if <tt>key</tt> is <tt>null</tt>
*/
public Key floor(Key key) {
if (key == null) throw new NullPointerException("called floor() with null key");
// headMap does not include key if present (!)
if (st.containsKey(key)) return key;
SortedMap<Key, Value> head = st.headMap(key);
if (head.isEmpty()) throw new NoSuchElementException();
return head.lastKey();
}
}