1use alloc::vec;
2
3use jvm::{ClassInstanceRef, Jvm, Result};
4use jvm_class_proto::{JavaFieldProto, JavaMethodProto};
5use jvm_types::{ClassAccessFlags, FieldAccessFlags, MethodAccessFlags};
6
7use crate::{RuntimeClassProto, RuntimeContext, classes::java::lang::Object};
8
9use super::TreeMapEntry;
10
11pub struct TreeMap;
13
14impl TreeMap {
15 pub fn as_proto() -> RuntimeClassProto {
16 RuntimeClassProto {
17 name: "java/util/TreeMap",
18 parent_class: Some("java/util/AbstractMap"),
19 interfaces: vec!["java/util/SortedMap", "java/lang/Cloneable", "java/io/Serializable"],
20 methods: vec![
21 JavaMethodProto::new("<init>", "()V", Self::init, MethodAccessFlags::PUBLIC),
22 JavaMethodProto::new("<init>", "(Ljava/util/Comparator;)V", Self::init_comparator, MethodAccessFlags::PUBLIC),
23 JavaMethodProto::new("<init>", "(Ljava/util/Map;)V", Self::init_map, MethodAccessFlags::PUBLIC),
24 JavaMethodProto::new("<init>", "(Ljava/util/SortedMap;)V", Self::init_sorted_map, MethodAccessFlags::PUBLIC),
25 JavaMethodProto::new("size", "()I", Self::size, MethodAccessFlags::PUBLIC),
26 JavaMethodProto::new("containsKey", "(Ljava/lang/Object;)Z", Self::contains_key, MethodAccessFlags::PUBLIC),
27 JavaMethodProto::new("containsValue", "(Ljava/lang/Object;)Z", Self::contains_value, MethodAccessFlags::PUBLIC),
28 JavaMethodProto::new("get", "(Ljava/lang/Object;)Ljava/lang/Object;", Self::get, MethodAccessFlags::PUBLIC),
29 JavaMethodProto::new(
30 "put",
31 "(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;",
32 Self::put,
33 MethodAccessFlags::PUBLIC,
34 ),
35 JavaMethodProto::new("putAll", "(Ljava/util/Map;)V", Self::put_all, MethodAccessFlags::PUBLIC),
36 JavaMethodProto::new(
37 "remove",
38 "(Ljava/lang/Object;)Ljava/lang/Object;",
39 Self::remove,
40 MethodAccessFlags::PUBLIC,
41 ),
42 JavaMethodProto::new("clear", "()V", Self::clear, MethodAccessFlags::PUBLIC),
43 JavaMethodProto::new("comparator", "()Ljava/util/Comparator;", Self::comparator, MethodAccessFlags::PUBLIC),
44 JavaMethodProto::new("firstKey", "()Ljava/lang/Object;", Self::first_key, MethodAccessFlags::PUBLIC),
45 JavaMethodProto::new("lastKey", "()Ljava/lang/Object;", Self::last_key, MethodAccessFlags::PUBLIC),
46 JavaMethodProto::new(
47 "subMap",
48 "(Ljava/lang/Object;Ljava/lang/Object;)Ljava/util/SortedMap;",
49 Self::sub_map,
50 MethodAccessFlags::PUBLIC,
51 ),
52 JavaMethodProto::new(
53 "headMap",
54 "(Ljava/lang/Object;)Ljava/util/SortedMap;",
55 Self::head_map,
56 MethodAccessFlags::PUBLIC,
57 ),
58 JavaMethodProto::new(
59 "tailMap",
60 "(Ljava/lang/Object;)Ljava/util/SortedMap;",
61 Self::tail_map,
62 MethodAccessFlags::PUBLIC,
63 ),
64 JavaMethodProto::new("keySet", "()Ljava/util/Set;", Self::key_set, MethodAccessFlags::PUBLIC),
65 JavaMethodProto::new("values", "()Ljava/util/Collection;", Self::values, MethodAccessFlags::PUBLIC),
66 JavaMethodProto::new("entrySet", "()Ljava/util/Set;", Self::entry_set, MethodAccessFlags::PUBLIC),
67 JavaMethodProto::new("keyIterator", "()Ljava/util/Iterator;", Self::key_iterator, MethodAccessFlags::empty()),
68 JavaMethodProto::new(
69 "valueIterator",
70 "()Ljava/util/Iterator;",
71 Self::value_iterator,
72 MethodAccessFlags::empty(),
73 ),
74 JavaMethodProto::new(
75 "entryIterator",
76 "()Ljava/util/Iterator;",
77 Self::entry_iterator,
78 MethodAccessFlags::empty(),
79 ),
80 ],
81 fields: vec![
82 JavaFieldProto::new(
83 "root",
84 "Ljava/util/TreeMap$Entry;",
85 FieldAccessFlags::PRIVATE | FieldAccessFlags::TRANSIENT,
86 ),
87 JavaFieldProto::new("size", "I", FieldAccessFlags::PRIVATE | FieldAccessFlags::TRANSIENT),
88 JavaFieldProto::new("comparator", "Ljava/util/Comparator;", FieldAccessFlags::PRIVATE),
89 ],
90 access_flags: ClassAccessFlags::PUBLIC,
91 }
92 }
93
94 async fn init(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<()> {
95 let _: () = jvm.invoke_special(&this, "java/util/AbstractMap", "<init>", "()V", ()).await?;
96 Ok(())
97 }
98
99 async fn init_comparator(
100 jvm: &Jvm,
101 _: &mut RuntimeContext,
102 mut this: ClassInstanceRef<Self>,
103 comparator: ClassInstanceRef<Object>,
104 ) -> Result<()> {
105 let _: () = jvm.invoke_special(&this, "java/util/AbstractMap", "<init>", "()V", ()).await?;
106 jvm.put_field(&mut this, "comparator", "Ljava/util/Comparator;", comparator).await
107 }
108
109 async fn init_map(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>, map: ClassInstanceRef<Object>) -> Result<()> {
110 if map.is_null() {
111 return Err(jvm.exception("java/lang/NullPointerException", "map").await);
112 }
113 let _: () = jvm.invoke_special(&this, "java/util/TreeMap", "<init>", "()V", ()).await?;
114 Self::copy_from_map(jvm, this, map).await
115 }
116
117 async fn init_sorted_map(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>, map: ClassInstanceRef<Object>) -> Result<()> {
118 if map.is_null() {
119 return Err(jvm.exception("java/lang/NullPointerException", "map").await);
120 }
121 let comparator: ClassInstanceRef<Object> = jvm
122 .invoke_virtual(&map, &map.class_definition().name(), "comparator", "()Ljava/util/Comparator;", ())
123 .await?;
124 let _: () = jvm
125 .invoke_special(&this, "java/util/TreeMap", "<init>", "(Ljava/util/Comparator;)V", (comparator,))
126 .await?;
127 Self::copy_from_map(jvm, this, map).await
128 }
129
130 async fn size(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<i32> {
131 jvm.get_field(&this, "size", "I").await
132 }
133
134 async fn contains_key(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>, key: ClassInstanceRef<Object>) -> Result<bool> {
135 Ok(!Self::find_entry(jvm, &this, &key).await?.is_null())
136 }
137
138 async fn contains_value(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>, value: ClassInstanceRef<Object>) -> Result<bool> {
139 let mut entry = Self::first_entry(jvm, &this).await?;
140 while !entry.is_null() {
141 let current: ClassInstanceRef<Object> = jvm.get_field(&entry, "value", "Ljava/lang/Object;").await?;
142 let equal = if value.is_null() {
143 current.is_null()
144 } else {
145 jvm.invoke_virtual(&value, "java/lang/Object", "equals", "(Ljava/lang/Object;)Z", (current,))
146 .await?
147 };
148 if equal {
149 return Ok(true);
150 }
151 entry = Self::successor(jvm, entry).await?;
152 }
153 Ok(false)
154 }
155
156 async fn get(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>, key: ClassInstanceRef<Object>) -> Result<ClassInstanceRef<Object>> {
157 let entry = Self::find_entry(jvm, &this, &key).await?;
158 if entry.is_null() {
159 return Ok(None.into());
160 }
161 jvm.get_field(&entry, "value", "Ljava/lang/Object;").await
162 }
163
164 async fn put(
165 jvm: &Jvm,
166 _: &mut RuntimeContext,
167 mut this: ClassInstanceRef<Self>,
168 key: ClassInstanceRef<Object>,
169 value: ClassInstanceRef<Object>,
170 ) -> Result<ClassInstanceRef<Object>> {
171 let root: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&this, "root", "Ljava/util/TreeMap$Entry;").await?;
172 if root.is_null() {
173 let _ = Self::compare(jvm, &this, &key, &key).await?;
174 let entry: ClassInstanceRef<TreeMapEntry> = jvm
175 .new_class(
176 "java/util/TreeMap$Entry",
177 "(Ljava/lang/Object;Ljava/lang/Object;Ljava/util/TreeMap$Entry;)V",
178 (key, value, ClassInstanceRef::<TreeMapEntry>::from(None)),
179 )
180 .await?
181 .into();
182 jvm.put_field(&mut this, "root", "Ljava/util/TreeMap$Entry;", entry).await?;
183 jvm.put_field(&mut this, "size", "I", 1).await?;
184 return Ok(None.into());
185 }
186
187 let mut parent = root;
188 let comparison;
189 loop {
190 let stored_key: ClassInstanceRef<Object> = jvm.get_field(&parent, "key", "Ljava/lang/Object;").await?;
191 let current_comparison = Self::compare(jvm, &this, &key, &stored_key).await?;
192 if current_comparison == 0 {
193 let old_value: ClassInstanceRef<Object> = jvm.get_field(&parent, "value", "Ljava/lang/Object;").await?;
194 let mut parent = parent;
195 jvm.put_field(&mut parent, "value", "Ljava/lang/Object;", value).await?;
196 return Ok(old_value);
197 }
198 let child: ClassInstanceRef<TreeMapEntry> = if current_comparison < 0 {
199 jvm.get_field(&parent, "left", "Ljava/util/TreeMap$Entry;").await?
200 } else {
201 jvm.get_field(&parent, "right", "Ljava/util/TreeMap$Entry;").await?
202 };
203 if child.is_null() {
204 comparison = current_comparison;
205 break;
206 }
207 parent = child;
208 }
209
210 let mut entry: ClassInstanceRef<TreeMapEntry> = jvm
211 .new_class(
212 "java/util/TreeMap$Entry",
213 "(Ljava/lang/Object;Ljava/lang/Object;Ljava/util/TreeMap$Entry;)V",
214 (key, value, parent.clone()),
215 )
216 .await?
217 .into();
218 jvm.put_field(&mut entry, "color", "Z", false).await?;
219 let mut parent = parent;
220 if comparison < 0 {
221 jvm.put_field(&mut parent, "left", "Ljava/util/TreeMap$Entry;", entry.clone()).await?;
222 } else {
223 jvm.put_field(&mut parent, "right", "Ljava/util/TreeMap$Entry;", entry.clone()).await?;
224 }
225 let size: i32 = jvm.get_field(&this, "size", "I").await?;
226 jvm.put_field(&mut this, "size", "I", size + 1).await?;
227 Self::fix_after_insertion(jvm, &mut this, entry).await?;
228 Ok(None.into())
229 }
230
231 async fn put_all(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>, map: ClassInstanceRef<Object>) -> Result<()> {
232 if map.is_null() {
233 return Err(jvm.exception("java/lang/NullPointerException", "map").await);
234 }
235 if this.identity() == map.identity() {
236 return Ok(());
237 }
238 Self::copy_from_map(jvm, this, map).await
239 }
240
241 async fn remove(
242 jvm: &Jvm,
243 _: &mut RuntimeContext,
244 mut this: ClassInstanceRef<Self>,
245 key: ClassInstanceRef<Object>,
246 ) -> Result<ClassInstanceRef<Object>> {
247 let entry = Self::find_entry(jvm, &this, &key).await?;
248 if entry.is_null() {
249 return Ok(None.into());
250 }
251 let old_value: ClassInstanceRef<Object> = jvm.get_field(&entry, "value", "Ljava/lang/Object;").await?;
252 Self::delete_entry(jvm, &mut this, entry).await?;
253 Ok(old_value)
254 }
255
256 async fn clear(jvm: &Jvm, _: &mut RuntimeContext, mut this: ClassInstanceRef<Self>) -> Result<()> {
257 jvm.put_field(
258 &mut this,
259 "root",
260 "Ljava/util/TreeMap$Entry;",
261 ClassInstanceRef::<TreeMapEntry>::from(None),
262 )
263 .await?;
264 jvm.put_field(&mut this, "size", "I", 0).await
265 }
266
267 async fn comparator(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Object>> {
268 jvm.get_field(&this, "comparator", "Ljava/util/Comparator;").await
269 }
270
271 async fn first_key(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Object>> {
272 let entry = Self::first_entry(jvm, &this).await?;
273 if entry.is_null() {
274 return Err(jvm.exception("java/util/NoSuchElementException", "empty TreeMap").await);
275 }
276 jvm.get_field(&entry, "key", "Ljava/lang/Object;").await
277 }
278
279 async fn last_key(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Object>> {
280 let entry = Self::last_entry(jvm, &this).await?;
281 if entry.is_null() {
282 return Err(jvm.exception("java/util/NoSuchElementException", "empty TreeMap").await);
283 }
284 jvm.get_field(&entry, "key", "Ljava/lang/Object;").await
285 }
286
287 async fn sub_map(
288 jvm: &Jvm,
289 _: &mut RuntimeContext,
290 this: ClassInstanceRef<Self>,
291 from_key: ClassInstanceRef<Object>,
292 to_key: ClassInstanceRef<Object>,
293 ) -> Result<ClassInstanceRef<Object>> {
294 if Self::compare(jvm, &this, &from_key, &to_key).await? > 0 {
295 return Err(jvm.exception("java/lang/IllegalArgumentException", "fromKey > toKey").await);
296 }
297 Ok(jvm
298 .new_class(
299 "java/util/TreeMap$SubMap",
300 "(Ljava/util/TreeMap;ZLjava/lang/Object;ZLjava/lang/Object;)V",
301 (this, false, from_key, false, to_key),
302 )
303 .await?
304 .into())
305 }
306
307 async fn head_map(
308 jvm: &Jvm,
309 _: &mut RuntimeContext,
310 this: ClassInstanceRef<Self>,
311 to_key: ClassInstanceRef<Object>,
312 ) -> Result<ClassInstanceRef<Object>> {
313 let _ = Self::compare(jvm, &this, &to_key, &to_key).await?;
314 Ok(jvm
315 .new_class(
316 "java/util/TreeMap$SubMap",
317 "(Ljava/util/TreeMap;ZLjava/lang/Object;ZLjava/lang/Object;)V",
318 (this, true, ClassInstanceRef::<Object>::from(None), false, to_key),
319 )
320 .await?
321 .into())
322 }
323
324 async fn tail_map(
325 jvm: &Jvm,
326 _: &mut RuntimeContext,
327 this: ClassInstanceRef<Self>,
328 from_key: ClassInstanceRef<Object>,
329 ) -> Result<ClassInstanceRef<Object>> {
330 let _ = Self::compare(jvm, &this, &from_key, &from_key).await?;
331 Ok(jvm
332 .new_class(
333 "java/util/TreeMap$SubMap",
334 "(Ljava/util/TreeMap;ZLjava/lang/Object;ZLjava/lang/Object;)V",
335 (this, false, from_key, true, ClassInstanceRef::<Object>::from(None)),
336 )
337 .await?
338 .into())
339 }
340
341 async fn key_set(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Object>> {
342 Ok(jvm
343 .new_class("java/util/TreeMap$KeySet", "(Ljava/util/SortedMap;)V", (this,))
344 .await?
345 .into())
346 }
347
348 async fn values(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Object>> {
349 Ok(jvm
350 .new_class("java/util/TreeMap$Values", "(Ljava/util/SortedMap;)V", (this,))
351 .await?
352 .into())
353 }
354
355 async fn entry_set(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Object>> {
356 Ok(jvm
357 .new_class("java/util/TreeMap$EntrySet", "(Ljava/util/SortedMap;)V", (this,))
358 .await?
359 .into())
360 }
361
362 async fn key_iterator(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Object>> {
363 let first = Self::first_entry(jvm, &this).await?;
364 Ok(jvm
365 .new_class(
366 "java/util/TreeMap$KeyIterator",
367 "(Ljava/util/TreeMap;Ljava/util/TreeMap$Entry;Ljava/lang/Object;Z)V",
368 (this, first, ClassInstanceRef::<Object>::from(None), true),
369 )
370 .await?
371 .into())
372 }
373
374 async fn value_iterator(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Object>> {
375 let first = Self::first_entry(jvm, &this).await?;
376 Ok(jvm
377 .new_class(
378 "java/util/TreeMap$ValueIterator",
379 "(Ljava/util/TreeMap;Ljava/util/TreeMap$Entry;Ljava/lang/Object;Z)V",
380 (this, first, ClassInstanceRef::<Object>::from(None), true),
381 )
382 .await?
383 .into())
384 }
385
386 async fn entry_iterator(jvm: &Jvm, _: &mut RuntimeContext, this: ClassInstanceRef<Self>) -> Result<ClassInstanceRef<Object>> {
387 let first = Self::first_entry(jvm, &this).await?;
388 Ok(jvm
389 .new_class(
390 "java/util/TreeMap$EntryIterator",
391 "(Ljava/util/TreeMap;Ljava/util/TreeMap$Entry;Ljava/lang/Object;Z)V",
392 (this, first, ClassInstanceRef::<Object>::from(None), true),
393 )
394 .await?
395 .into())
396 }
397
398 async fn copy_from_map(jvm: &Jvm, this: ClassInstanceRef<Self>, map: ClassInstanceRef<Object>) -> Result<()> {
399 let entry_set: ClassInstanceRef<Object> = jvm
400 .invoke_virtual(&map, &map.class_definition().name(), "entrySet", "()Ljava/util/Set;", ())
401 .await?;
402 let iterator: ClassInstanceRef<Object> = jvm
403 .invoke_virtual(&entry_set, &entry_set.class_definition().name(), "iterator", "()Ljava/util/Iterator;", ())
404 .await?;
405 while jvm
406 .invoke_virtual::<_, bool>(&iterator, &iterator.class_definition().name(), "hasNext", "()Z", ())
407 .await?
408 {
409 let entry: ClassInstanceRef<Object> = jvm
410 .invoke_virtual(&iterator, &iterator.class_definition().name(), "next", "()Ljava/lang/Object;", ())
411 .await?;
412 let key: ClassInstanceRef<Object> = jvm
413 .invoke_virtual(&entry, &entry.class_definition().name(), "getKey", "()Ljava/lang/Object;", ())
414 .await?;
415 let value: ClassInstanceRef<Object> = jvm
416 .invoke_virtual(&entry, &entry.class_definition().name(), "getValue", "()Ljava/lang/Object;", ())
417 .await?;
418 let _: ClassInstanceRef<Object> = jvm
419 .invoke_virtual(
420 &this,
421 "java/util/TreeMap",
422 "put",
423 "(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;",
424 (key, value),
425 )
426 .await?;
427 }
428 Ok(())
429 }
430
431 pub(super) async fn compare(
432 jvm: &Jvm,
433 this: &ClassInstanceRef<Self>,
434 left: &ClassInstanceRef<Object>,
435 right: &ClassInstanceRef<Object>,
436 ) -> Result<i32> {
437 let comparator: ClassInstanceRef<Object> = jvm.get_field(this, "comparator", "Ljava/util/Comparator;").await?;
438 if !comparator.is_null() {
439 return jvm
440 .invoke_virtual(
441 &comparator,
442 &comparator.class_definition().name(),
443 "compare",
444 "(Ljava/lang/Object;Ljava/lang/Object;)I",
445 (left.clone(), right.clone()),
446 )
447 .await;
448 }
449 if left.is_null() {
450 return Err(jvm.exception("java/lang/NullPointerException", "null key").await);
451 }
452 if !jvm.is_instance(left.as_ref(), "java/lang/Comparable") {
453 return Err(jvm.exception("java/lang/ClassCastException", "key is not Comparable").await);
454 }
455 jvm.invoke_virtual(
456 left,
457 &left.class_definition().name(),
458 "compareTo",
459 "(Ljava/lang/Object;)I",
460 (right.clone(),),
461 )
462 .await
463 }
464
465 pub(super) async fn find_entry(
466 jvm: &Jvm,
467 this: &ClassInstanceRef<Self>,
468 key: &ClassInstanceRef<Object>,
469 ) -> Result<ClassInstanceRef<TreeMapEntry>> {
470 let comparator: ClassInstanceRef<Object> = jvm.get_field(this, "comparator", "Ljava/util/Comparator;").await?;
471 if comparator.is_null() {
472 if key.is_null() {
473 return Err(jvm.exception("java/lang/NullPointerException", "null key").await);
474 }
475 if !jvm.is_instance(key.as_ref(), "java/lang/Comparable") {
476 return Err(jvm.exception("java/lang/ClassCastException", "key is not Comparable").await);
477 }
478 }
479
480 let mut entry: ClassInstanceRef<TreeMapEntry> = jvm.get_field(this, "root", "Ljava/util/TreeMap$Entry;").await?;
481 while !entry.is_null() {
482 let stored_key: ClassInstanceRef<Object> = jvm.get_field(&entry, "key", "Ljava/lang/Object;").await?;
483 let comparison: i32 = if comparator.is_null() {
484 jvm.invoke_virtual(key, &key.class_definition().name(), "compareTo", "(Ljava/lang/Object;)I", (stored_key,))
485 .await?
486 } else {
487 jvm.invoke_virtual(
488 &comparator,
489 &comparator.class_definition().name(),
490 "compare",
491 "(Ljava/lang/Object;Ljava/lang/Object;)I",
492 (key.clone(), stored_key),
493 )
494 .await?
495 };
496 if comparison == 0 {
497 return Ok(entry);
498 }
499 entry = if comparison < 0 {
500 jvm.get_field(&entry, "left", "Ljava/util/TreeMap$Entry;").await?
501 } else {
502 jvm.get_field(&entry, "right", "Ljava/util/TreeMap$Entry;").await?
503 };
504 }
505 Ok(None.into())
506 }
507
508 pub(super) async fn first_entry(jvm: &Jvm, this: &ClassInstanceRef<Self>) -> Result<ClassInstanceRef<TreeMapEntry>> {
509 let mut entry: ClassInstanceRef<TreeMapEntry> = jvm.get_field(this, "root", "Ljava/util/TreeMap$Entry;").await?;
510 if entry.is_null() {
511 return Ok(entry);
512 }
513 loop {
514 let left: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&entry, "left", "Ljava/util/TreeMap$Entry;").await?;
515 if left.is_null() {
516 return Ok(entry);
517 }
518 entry = left;
519 }
520 }
521
522 pub(super) async fn last_entry(jvm: &Jvm, this: &ClassInstanceRef<Self>) -> Result<ClassInstanceRef<TreeMapEntry>> {
523 let mut entry: ClassInstanceRef<TreeMapEntry> = jvm.get_field(this, "root", "Ljava/util/TreeMap$Entry;").await?;
524 if entry.is_null() {
525 return Ok(entry);
526 }
527 loop {
528 let right: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&entry, "right", "Ljava/util/TreeMap$Entry;").await?;
529 if right.is_null() {
530 return Ok(entry);
531 }
532 entry = right;
533 }
534 }
535
536 pub(super) async fn ceiling_entry(
537 jvm: &Jvm,
538 this: &ClassInstanceRef<Self>,
539 key: &ClassInstanceRef<Object>,
540 ) -> Result<ClassInstanceRef<TreeMapEntry>> {
541 let mut entry: ClassInstanceRef<TreeMapEntry> = jvm.get_field(this, "root", "Ljava/util/TreeMap$Entry;").await?;
542 let mut candidate: ClassInstanceRef<TreeMapEntry> = None.into();
543 while !entry.is_null() {
544 let stored_key: ClassInstanceRef<Object> = jvm.get_field(&entry, "key", "Ljava/lang/Object;").await?;
545 let comparison = Self::compare(jvm, this, key, &stored_key).await?;
546 if comparison == 0 {
547 return Ok(entry);
548 }
549 if comparison < 0 {
550 candidate = entry.clone();
551 entry = jvm.get_field(&entry, "left", "Ljava/util/TreeMap$Entry;").await?;
552 } else {
553 entry = jvm.get_field(&entry, "right", "Ljava/util/TreeMap$Entry;").await?;
554 }
555 }
556 Ok(candidate)
557 }
558
559 pub(super) async fn lower_entry(
560 jvm: &Jvm,
561 this: &ClassInstanceRef<Self>,
562 key: &ClassInstanceRef<Object>,
563 ) -> Result<ClassInstanceRef<TreeMapEntry>> {
564 let mut entry: ClassInstanceRef<TreeMapEntry> = jvm.get_field(this, "root", "Ljava/util/TreeMap$Entry;").await?;
565 let mut candidate: ClassInstanceRef<TreeMapEntry> = None.into();
566 while !entry.is_null() {
567 let stored_key: ClassInstanceRef<Object> = jvm.get_field(&entry, "key", "Ljava/lang/Object;").await?;
568 if Self::compare(jvm, this, key, &stored_key).await? <= 0 {
569 entry = jvm.get_field(&entry, "left", "Ljava/util/TreeMap$Entry;").await?;
570 } else {
571 candidate = entry.clone();
572 entry = jvm.get_field(&entry, "right", "Ljava/util/TreeMap$Entry;").await?;
573 }
574 }
575 Ok(candidate)
576 }
577
578 pub(super) async fn successor(jvm: &Jvm, entry: ClassInstanceRef<TreeMapEntry>) -> Result<ClassInstanceRef<TreeMapEntry>> {
579 if entry.is_null() {
580 return Ok(None.into());
581 }
582 let right: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&entry, "right", "Ljava/util/TreeMap$Entry;").await?;
583 if !right.is_null() {
584 let mut candidate = right;
585 loop {
586 let left: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&candidate, "left", "Ljava/util/TreeMap$Entry;").await?;
587 if left.is_null() {
588 return Ok(candidate);
589 }
590 candidate = left;
591 }
592 }
593
594 let mut child = entry;
595 let mut parent: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&child, "parent", "Ljava/util/TreeMap$Entry;").await?;
596 while !parent.is_null() {
597 let parent_right: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&parent, "right", "Ljava/util/TreeMap$Entry;").await?;
598 if parent_right.is_null() || child.identity() != parent_right.identity() {
599 break;
600 }
601 child = parent;
602 parent = jvm.get_field(&child, "parent", "Ljava/util/TreeMap$Entry;").await?;
603 }
604 Ok(parent)
605 }
606
607 async fn rotate_left(jvm: &Jvm, this: &mut ClassInstanceRef<Self>, mut pivot: ClassInstanceRef<TreeMapEntry>) -> Result<()> {
608 let mut right: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&pivot, "right", "Ljava/util/TreeMap$Entry;").await?;
609 let right_left: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&right, "left", "Ljava/util/TreeMap$Entry;").await?;
610 jvm.put_field(&mut pivot, "right", "Ljava/util/TreeMap$Entry;", right_left.clone())
611 .await?;
612 if !right_left.is_null() {
613 let mut right_left = right_left;
614 jvm.put_field(&mut right_left, "parent", "Ljava/util/TreeMap$Entry;", pivot.clone())
615 .await?;
616 }
617 let parent: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&pivot, "parent", "Ljava/util/TreeMap$Entry;").await?;
618 jvm.put_field(&mut right, "parent", "Ljava/util/TreeMap$Entry;", parent.clone()).await?;
619 if parent.is_null() {
620 jvm.put_field(this, "root", "Ljava/util/TreeMap$Entry;", right.clone()).await?;
621 } else {
622 let parent_left: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&parent, "left", "Ljava/util/TreeMap$Entry;").await?;
623 let mut parent = parent;
624 if !parent_left.is_null() && parent_left.identity() == pivot.identity() {
625 jvm.put_field(&mut parent, "left", "Ljava/util/TreeMap$Entry;", right.clone()).await?;
626 } else {
627 jvm.put_field(&mut parent, "right", "Ljava/util/TreeMap$Entry;", right.clone()).await?;
628 }
629 }
630 jvm.put_field(&mut right, "left", "Ljava/util/TreeMap$Entry;", pivot.clone()).await?;
631 jvm.put_field(&mut pivot, "parent", "Ljava/util/TreeMap$Entry;", right).await
632 }
633
634 async fn rotate_right(jvm: &Jvm, this: &mut ClassInstanceRef<Self>, mut pivot: ClassInstanceRef<TreeMapEntry>) -> Result<()> {
635 let mut left: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&pivot, "left", "Ljava/util/TreeMap$Entry;").await?;
636 let left_right: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&left, "right", "Ljava/util/TreeMap$Entry;").await?;
637 jvm.put_field(&mut pivot, "left", "Ljava/util/TreeMap$Entry;", left_right.clone()).await?;
638 if !left_right.is_null() {
639 let mut left_right = left_right;
640 jvm.put_field(&mut left_right, "parent", "Ljava/util/TreeMap$Entry;", pivot.clone())
641 .await?;
642 }
643 let parent: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&pivot, "parent", "Ljava/util/TreeMap$Entry;").await?;
644 jvm.put_field(&mut left, "parent", "Ljava/util/TreeMap$Entry;", parent.clone()).await?;
645 if parent.is_null() {
646 jvm.put_field(this, "root", "Ljava/util/TreeMap$Entry;", left.clone()).await?;
647 } else {
648 let parent_right: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&parent, "right", "Ljava/util/TreeMap$Entry;").await?;
649 let mut parent = parent;
650 if !parent_right.is_null() && parent_right.identity() == pivot.identity() {
651 jvm.put_field(&mut parent, "right", "Ljava/util/TreeMap$Entry;", left.clone()).await?;
652 } else {
653 jvm.put_field(&mut parent, "left", "Ljava/util/TreeMap$Entry;", left.clone()).await?;
654 }
655 }
656 jvm.put_field(&mut left, "right", "Ljava/util/TreeMap$Entry;", pivot.clone()).await?;
657 jvm.put_field(&mut pivot, "parent", "Ljava/util/TreeMap$Entry;", left).await
658 }
659
660 async fn fix_after_insertion(jvm: &Jvm, this: &mut ClassInstanceRef<Self>, mut entry: ClassInstanceRef<TreeMapEntry>) -> Result<()> {
661 jvm.put_field(&mut entry, "color", "Z", false).await?;
662 loop {
663 let root: ClassInstanceRef<TreeMapEntry> = jvm.get_field(this, "root", "Ljava/util/TreeMap$Entry;").await?;
664 if entry.identity() == root.identity() {
665 break;
666 }
667 let mut parent: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&entry, "parent", "Ljava/util/TreeMap$Entry;").await?;
668 if parent.is_null() || jvm.get_field::<bool>(&parent, "color", "Z").await? {
669 break;
670 }
671 let mut grand: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&parent, "parent", "Ljava/util/TreeMap$Entry;").await?;
672 let grand_left: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&grand, "left", "Ljava/util/TreeMap$Entry;").await?;
673 if !grand_left.is_null() && grand_left.identity() == parent.identity() {
674 let mut uncle: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&grand, "right", "Ljava/util/TreeMap$Entry;").await?;
675 let uncle_is_red = !uncle.is_null() && !jvm.get_field::<bool>(&uncle, "color", "Z").await?;
676 if uncle_is_red {
677 jvm.put_field(&mut parent, "color", "Z", true).await?;
678 jvm.put_field(&mut uncle, "color", "Z", true).await?;
679 jvm.put_field(&mut grand, "color", "Z", false).await?;
680 entry = grand;
681 continue;
682 }
683 let parent_right: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&parent, "right", "Ljava/util/TreeMap$Entry;").await?;
684 if !parent_right.is_null() && parent_right.identity() == entry.identity() {
685 entry = parent.clone();
686 Self::rotate_left(jvm, this, entry.clone()).await?;
687 parent = jvm.get_field(&entry, "parent", "Ljava/util/TreeMap$Entry;").await?;
688 grand = jvm.get_field(&parent, "parent", "Ljava/util/TreeMap$Entry;").await?;
689 }
690 jvm.put_field(&mut parent, "color", "Z", true).await?;
691 jvm.put_field(&mut grand, "color", "Z", false).await?;
692 Self::rotate_right(jvm, this, grand).await?;
693 } else {
694 let mut uncle: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&grand, "left", "Ljava/util/TreeMap$Entry;").await?;
695 let uncle_is_red = !uncle.is_null() && !jvm.get_field::<bool>(&uncle, "color", "Z").await?;
696 if uncle_is_red {
697 jvm.put_field(&mut parent, "color", "Z", true).await?;
698 jvm.put_field(&mut uncle, "color", "Z", true).await?;
699 jvm.put_field(&mut grand, "color", "Z", false).await?;
700 entry = grand;
701 continue;
702 }
703 let parent_left: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&parent, "left", "Ljava/util/TreeMap$Entry;").await?;
704 if !parent_left.is_null() && parent_left.identity() == entry.identity() {
705 entry = parent.clone();
706 Self::rotate_right(jvm, this, entry.clone()).await?;
707 parent = jvm.get_field(&entry, "parent", "Ljava/util/TreeMap$Entry;").await?;
708 grand = jvm.get_field(&parent, "parent", "Ljava/util/TreeMap$Entry;").await?;
709 }
710 jvm.put_field(&mut parent, "color", "Z", true).await?;
711 jvm.put_field(&mut grand, "color", "Z", false).await?;
712 Self::rotate_left(jvm, this, grand).await?;
713 }
714 }
715 let mut root: ClassInstanceRef<TreeMapEntry> = jvm.get_field(this, "root", "Ljava/util/TreeMap$Entry;").await?;
716 jvm.put_field(&mut root, "color", "Z", true).await?;
717 Ok(())
718 }
719
720 pub(super) async fn delete_entry(jvm: &Jvm, this: &mut ClassInstanceRef<Self>, entry: ClassInstanceRef<TreeMapEntry>) -> Result<()> {
721 let size: i32 = jvm.get_field(this, "size", "I").await?;
722 jvm.put_field(this, "size", "I", size - 1).await?;
723
724 let mut target = entry;
725 let left: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&target, "left", "Ljava/util/TreeMap$Entry;").await?;
726 let right: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&target, "right", "Ljava/util/TreeMap$Entry;").await?;
727 if !left.is_null() && !right.is_null() {
728 let successor = Self::successor(jvm, target.clone()).await?;
729 let key: ClassInstanceRef<Object> = jvm.get_field(&successor, "key", "Ljava/lang/Object;").await?;
730 let value: ClassInstanceRef<Object> = jvm.get_field(&successor, "value", "Ljava/lang/Object;").await?;
731 jvm.put_field(&mut target, "key", "Ljava/lang/Object;", key).await?;
732 jvm.put_field(&mut target, "value", "Ljava/lang/Object;", value).await?;
733 target = successor;
734 }
735
736 let target_left: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&target, "left", "Ljava/util/TreeMap$Entry;").await?;
737 let target_right: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&target, "right", "Ljava/util/TreeMap$Entry;").await?;
738 let mut replacement = if !target_left.is_null() { target_left } else { target_right };
739 if !replacement.is_null() {
740 let parent: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&target, "parent", "Ljava/util/TreeMap$Entry;").await?;
741 jvm.put_field(&mut replacement, "parent", "Ljava/util/TreeMap$Entry;", parent.clone())
742 .await?;
743 if parent.is_null() {
744 jvm.put_field(this, "root", "Ljava/util/TreeMap$Entry;", replacement.clone()).await?;
745 } else {
746 let parent_left: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&parent, "left", "Ljava/util/TreeMap$Entry;").await?;
747 let mut parent = parent;
748 if !parent_left.is_null() && parent_left.identity() == target.identity() {
749 jvm.put_field(&mut parent, "left", "Ljava/util/TreeMap$Entry;", replacement.clone())
750 .await?;
751 } else {
752 jvm.put_field(&mut parent, "right", "Ljava/util/TreeMap$Entry;", replacement.clone())
753 .await?;
754 }
755 }
756 jvm.put_field(
757 &mut target,
758 "left",
759 "Ljava/util/TreeMap$Entry;",
760 ClassInstanceRef::<TreeMapEntry>::from(None),
761 )
762 .await?;
763 jvm.put_field(
764 &mut target,
765 "right",
766 "Ljava/util/TreeMap$Entry;",
767 ClassInstanceRef::<TreeMapEntry>::from(None),
768 )
769 .await?;
770 jvm.put_field(
771 &mut target,
772 "parent",
773 "Ljava/util/TreeMap$Entry;",
774 ClassInstanceRef::<TreeMapEntry>::from(None),
775 )
776 .await?;
777 if jvm.get_field::<bool>(&target, "color", "Z").await? {
778 Self::fix_after_deletion(jvm, this, replacement).await?;
779 }
780 } else {
781 let parent: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&target, "parent", "Ljava/util/TreeMap$Entry;").await?;
782 if parent.is_null() {
783 jvm.put_field(this, "root", "Ljava/util/TreeMap$Entry;", ClassInstanceRef::<TreeMapEntry>::from(None))
784 .await?;
785 } else {
786 if jvm.get_field::<bool>(&target, "color", "Z").await? {
787 Self::fix_after_deletion(jvm, this, target.clone()).await?;
788 }
789 let parent: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&target, "parent", "Ljava/util/TreeMap$Entry;").await?;
790 if !parent.is_null() {
791 let parent_left: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&parent, "left", "Ljava/util/TreeMap$Entry;").await?;
792 let parent_right: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&parent, "right", "Ljava/util/TreeMap$Entry;").await?;
793 let mut parent = parent;
794 if !parent_left.is_null() && parent_left.identity() == target.identity() {
795 jvm.put_field(
796 &mut parent,
797 "left",
798 "Ljava/util/TreeMap$Entry;",
799 ClassInstanceRef::<TreeMapEntry>::from(None),
800 )
801 .await?;
802 } else if !parent_right.is_null() && parent_right.identity() == target.identity() {
803 jvm.put_field(
804 &mut parent,
805 "right",
806 "Ljava/util/TreeMap$Entry;",
807 ClassInstanceRef::<TreeMapEntry>::from(None),
808 )
809 .await?;
810 }
811 jvm.put_field(
812 &mut target,
813 "parent",
814 "Ljava/util/TreeMap$Entry;",
815 ClassInstanceRef::<TreeMapEntry>::from(None),
816 )
817 .await?;
818 }
819 }
820 }
821 Ok(())
822 }
823
824 async fn fix_after_deletion(jvm: &Jvm, this: &mut ClassInstanceRef<Self>, mut entry: ClassInstanceRef<TreeMapEntry>) -> Result<()> {
825 loop {
826 let root: ClassInstanceRef<TreeMapEntry> = jvm.get_field(this, "root", "Ljava/util/TreeMap$Entry;").await?;
827 if entry.identity() == root.identity() || !jvm.get_field::<bool>(&entry, "color", "Z").await? {
828 break;
829 }
830 let parent: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&entry, "parent", "Ljava/util/TreeMap$Entry;").await?;
831 let parent_left: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&parent, "left", "Ljava/util/TreeMap$Entry;").await?;
832 if !parent_left.is_null() && parent_left.identity() == entry.identity() {
833 let mut sibling: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&parent, "right", "Ljava/util/TreeMap$Entry;").await?;
834 if !sibling.is_null() && !jvm.get_field::<bool>(&sibling, "color", "Z").await? {
835 jvm.put_field(&mut sibling, "color", "Z", true).await?;
836 let mut parent = parent.clone();
837 jvm.put_field(&mut parent, "color", "Z", false).await?;
838 Self::rotate_left(jvm, this, parent.clone()).await?;
839 sibling = jvm.get_field(&parent, "right", "Ljava/util/TreeMap$Entry;").await?;
840 }
841 let sibling_left: ClassInstanceRef<TreeMapEntry> = if sibling.is_null() {
842 None.into()
843 } else {
844 jvm.get_field(&sibling, "left", "Ljava/util/TreeMap$Entry;").await?
845 };
846 let sibling_right: ClassInstanceRef<TreeMapEntry> = if sibling.is_null() {
847 None.into()
848 } else {
849 jvm.get_field(&sibling, "right", "Ljava/util/TreeMap$Entry;").await?
850 };
851 let left_black = sibling_left.is_null() || jvm.get_field::<bool>(&sibling_left, "color", "Z").await?;
852 let right_black = sibling_right.is_null() || jvm.get_field::<bool>(&sibling_right, "color", "Z").await?;
853 if left_black && right_black {
854 if !sibling.is_null() {
855 jvm.put_field(&mut sibling, "color", "Z", false).await?;
856 }
857 entry = parent;
858 } else {
859 if right_black {
860 if !sibling_left.is_null() {
861 let mut sibling_left = sibling_left;
862 jvm.put_field(&mut sibling_left, "color", "Z", true).await?;
863 }
864 if !sibling.is_null() {
865 jvm.put_field(&mut sibling, "color", "Z", false).await?;
866 Self::rotate_right(jvm, this, sibling.clone()).await?;
867 }
868 sibling = jvm.get_field(&parent, "right", "Ljava/util/TreeMap$Entry;").await?;
869 }
870 if !sibling.is_null() {
871 let parent_color: bool = jvm.get_field(&parent, "color", "Z").await?;
872 jvm.put_field(&mut sibling, "color", "Z", parent_color).await?;
873 }
874 let mut parent = parent;
875 jvm.put_field(&mut parent, "color", "Z", true).await?;
876 if !sibling.is_null() {
877 let mut sibling_right: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&sibling, "right", "Ljava/util/TreeMap$Entry;").await?;
878 if !sibling_right.is_null() {
879 jvm.put_field(&mut sibling_right, "color", "Z", true).await?;
880 }
881 }
882 Self::rotate_left(jvm, this, parent).await?;
883 entry = jvm.get_field(this, "root", "Ljava/util/TreeMap$Entry;").await?;
884 }
885 } else {
886 let mut sibling: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&parent, "left", "Ljava/util/TreeMap$Entry;").await?;
887 if !sibling.is_null() && !jvm.get_field::<bool>(&sibling, "color", "Z").await? {
888 jvm.put_field(&mut sibling, "color", "Z", true).await?;
889 let mut parent = parent.clone();
890 jvm.put_field(&mut parent, "color", "Z", false).await?;
891 Self::rotate_right(jvm, this, parent.clone()).await?;
892 sibling = jvm.get_field(&parent, "left", "Ljava/util/TreeMap$Entry;").await?;
893 }
894 let sibling_left: ClassInstanceRef<TreeMapEntry> = if sibling.is_null() {
895 None.into()
896 } else {
897 jvm.get_field(&sibling, "left", "Ljava/util/TreeMap$Entry;").await?
898 };
899 let sibling_right: ClassInstanceRef<TreeMapEntry> = if sibling.is_null() {
900 None.into()
901 } else {
902 jvm.get_field(&sibling, "right", "Ljava/util/TreeMap$Entry;").await?
903 };
904 let left_black = sibling_left.is_null() || jvm.get_field::<bool>(&sibling_left, "color", "Z").await?;
905 let right_black = sibling_right.is_null() || jvm.get_field::<bool>(&sibling_right, "color", "Z").await?;
906 if left_black && right_black {
907 if !sibling.is_null() {
908 jvm.put_field(&mut sibling, "color", "Z", false).await?;
909 }
910 entry = parent;
911 } else {
912 if left_black {
913 if !sibling_right.is_null() {
914 let mut sibling_right = sibling_right;
915 jvm.put_field(&mut sibling_right, "color", "Z", true).await?;
916 }
917 if !sibling.is_null() {
918 jvm.put_field(&mut sibling, "color", "Z", false).await?;
919 Self::rotate_left(jvm, this, sibling.clone()).await?;
920 }
921 sibling = jvm.get_field(&parent, "left", "Ljava/util/TreeMap$Entry;").await?;
922 }
923 if !sibling.is_null() {
924 let parent_color: bool = jvm.get_field(&parent, "color", "Z").await?;
925 jvm.put_field(&mut sibling, "color", "Z", parent_color).await?;
926 }
927 let mut parent = parent;
928 jvm.put_field(&mut parent, "color", "Z", true).await?;
929 if !sibling.is_null() {
930 let mut sibling_left: ClassInstanceRef<TreeMapEntry> = jvm.get_field(&sibling, "left", "Ljava/util/TreeMap$Entry;").await?;
931 if !sibling_left.is_null() {
932 jvm.put_field(&mut sibling_left, "color", "Z", true).await?;
933 }
934 }
935 Self::rotate_right(jvm, this, parent).await?;
936 entry = jvm.get_field(this, "root", "Ljava/util/TreeMap$Entry;").await?;
937 }
938 }
939 }
940 if !entry.is_null() {
941 jvm.put_field(&mut entry, "color", "Z", true).await?;
942 }
943 Ok(())
944 }
945}