Open wincelee opened 1 year ago
I think it's probably worth registering a TypeAdapter
if you want to be able to serialize and deserialize a PriorityQueue
in a particular way.
Interestingly Gson even has a unit test for PriorityQueue
:
https://github.com/google/gson/blob/43396e45fd1f03e408e0e83b168a72a0f3e0b84e/gson/src/test/java/com/google/gson/functional/CollectionTest.java#L138-L148
However, this test seems to be flawed because the values in the input JSON data are already sorted. If you provide instead "[22, 10, 20]"
the test fails because the PriorityQueue
seems to store them in a different order internally then.
To provide a bit more context on the current Gson behavior: Gson does not have a dedicated adapter for PriorityQueue
at the moment. Therefore it uses the general Collection
adapter to read and write PriorityQueue
instances. The problem is that the iteration order of PriorityQueue
is unspecified, as mentioned by its documentation:
The Iterator provided in method
iterator()
and the Spliterator provided in methodspliterator()
are not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider usingArrays.sort(pq.toArray())
.
This is also not a problem specific to Gson, see this Stack Overflow question about PriorityQueue
iteration order.
So as Éamonn mentioned above, you will have to write a custom TypeAdapter
or maybe even a TypeAdapterFactory
, for example:
class PriorityQueueAdapterFactory implements TypeAdapterFactory {
public static final PriorityQueueAdapterFactory INSTANCE = new PriorityQueueAdapterFactory();
private PriorityQueueAdapterFactory() { }
@Override
public <T> TypeAdapter<T> create(Gson gson, TypeToken<T> typeToken) {
Class<?> rawType = typeToken.getRawType();
// Only handle PriorityQueue, let other factories handle all other types
if (rawType != PriorityQueue.class) {
return null;
}
Type type = typeToken.getType();
Type elementType;
// If raw type without type argument choose Object as element type (and let Gson
// get actual runtime type)
if (type instanceof Class<?>) {
elementType = Object.class;
} else {
ParameterizedType parameterizedType = (ParameterizedType) type;
// Get the element type argument, for example `String` for `PriorityQueue<String>`
elementType = parameterizedType.getActualTypeArguments()[0];
}
@SuppressWarnings("unchecked")
final TypeAdapter<Object> elementAdapter = (TypeAdapter<Object>) gson.getAdapter(TypeToken.get(elementType));
@SuppressWarnings("unchecked")
TypeAdapter<T> r = (TypeAdapter<T>) new TypeAdapter<PriorityQueue<Object>>() {
@Override
public void write(JsonWriter out, PriorityQueue<Object> value) throws IOException {
if (value == null) {
out.nullValue();
return;
}
// Custom Comparator is unsupported because it would otherwise have to be serialized as well
if (value.comparator() != null) {
throw new IllegalArgumentException("Custom Comparator is not supported");
}
// Must manually sort elements because iteration order is unspecified
Object[] elements = value.toArray();
Arrays.sort(elements);
out.beginArray();
for (Object element : elements) {
elementAdapter.write(out, element);
}
out.endArray();
}
@Override
public PriorityQueue<Object> read(JsonReader in) throws IOException {
if (in.peek() == JsonToken.NULL) {
in.nextNull();
return null;
}
PriorityQueue<Object> queue = new PriorityQueue<>();
in.beginArray();
while (in.hasNext()) {
Object element = elementAdapter.read(in);
queue.add(element);
}
in.endArray();
return queue;
}
};
return r;
}
}
(Have not extensively tested this yet)
And then register it like this:
Gson gson = new GsonBuilder()
.registerTypeAdapterFactory(PriorityQueueAdapterFactory.INSTANCE)
.create();
However, as you might have noticed in the adapter code above this is not so efficient because it has to store all elements in an array and sort them before being able to write them to JSON. With all other solutions, such as calling poll()
, you would modify the provided queue, which is probably undesired.
Also, to keep serialization and deserialization symmetric the solution above rejects queues with custom comparator, because otherwise you would also have to somehow serialize and deserialize the comparator as well.
You could use the adapter factory shown above, or maybe the better solution would be to switch to a regular List
instead of a PriorityQueue
if possible.
@eamonnmcmanus, do you think it is worth considering adding explicit support for PriorityQueue
? Currently I don't think it is, given that this might be a somewhat rare corner case and because as shown above the implementation for it would be limited and inefficient.
I think probably a much simpler TypeAdapter
would be possible, that just delegates to the existing adapters for collections or arrays, via an intermediate sorted array? Not very efficient, but anyway we're not going to have a highly efficient solution.
This might be a candidate for gson/extras
, both as a general example of how to do delegation and as something to point people to when this question arises.
I am not very keen on the idea of adding a PriorityQueue
adapter by default, both because it is perhaps surprisingly inefficient and because I think it's fairly likely that it would change behaviour for at least some existing code.
I think probably a much simpler
TypeAdapter
would be possible, that just delegates to the existing adapters for collections or arrays, via an intermediate sorted array?
For delegation you would normally use TypeAdapterFactory
though because TypeAdapter
has no access to the Gson
instance (or maybe I am misunderstanding you). Otherwise you would have to create a new Gson
instance in the adapter, which then does not have the same configuration, e.g. lenientness setting.
Directly trying to serialize the array probably works but there might be some subtle differences regarding which types are used. If you want to preserve the original element type you would have to create from a parameterized type representing PriorityQueue<X>
a generic array type representing X[]
and pass that to Gson.getAdapter
when fetching the delegate. If you omit the type (or use the runtime type) the behavior of Gson's internal TypeAdapterRuntimeTypeWrapper
might differ.
I might not have thought this through completely, but anyway we would necessarily be talking about a TypeAdapterFactory
, right? So it can apply to any PriorityQueue<Foo>
. And then can't it "just" delegate to get a TypeAdapter
for List<Foo>
and copy the toArray()
into a List<Foo>
?
I see that the MultisetTypeAdapterFactory
example in the documentation for TypeAdapterFactory
doesn't do this, but couldn't it?
we would necessarily be talking about a
TypeAdapterFactory
, right?
Yes I think so; otherwise you cannot really perform delegation to my knowledge (except with JsonSerializer
and JsonDeserializer
).
And then can't it "just" delegate to get a
TypeAdapter
forList<Foo>
and copy thetoArray()
into aList<Foo>
?
That would actually be an option; the delegate adapters don't have to be the same for serialization and deserialization (as long as they behave identically). But then it would have to construct a ParameterizedType
representing List<Foo>
when calling Gson.getAdapter
(can be created with TypeToken.getParameterized
or getArray
for Foo[]
), and not just List.class
. Otherwise there might be subtle differences in TypeAdapterRuntimeTypeWrapper
behavior mentioned above; mainly for something like List<Foo<Bar>>
I think, see TypeAdapterRuntimeTypeWrapper.getRuntimeTypeIfMoreSpecific
.
For deserialization it would have also been possible to delegate to the default Gson adapter for PriorityQueue
, because deserialization seems to work as expected.
But at that point I thought it was easier and more transparent (showing that serialization and deserialization behave identically) to implement this serialization and deserialization logic manually.
I see that the
MultisetTypeAdapterFactory
example in the documentation forTypeAdapterFactory
doesn't do this, but couldn't it?
The factory serializes the set in the format [<count1>, <element1>, <count2>, <element2>, ...]
. So delegation would not really be possible unless you use List<Object>
as type and lose all type information about the elements.
For what it is worth, the MultisetTypeAdapterFactory
in that example is rather limited. It only works for a parameterized Multiset
, so when you serialize you must specify the type (toJson(multiset, type)
); just calling for example gson.toJson(ImmutableMultiset.of("a", "b", "b"))
will not use the factory. But extending it to cover also any Multiset
implementation would probably be out of scope for this example because it would require custom logic for deserializing ImmutableMultiset
.
Gson version 2.9.1
Java / Android version
Java 17 IntelliJ IDEA 2023.1 (Ultimate Edition) Build #IU-231.8109.175, built on March 28, 2023 Runtime version: 17.0.6+10-b829.5 aarch64 VM: OpenJDK 64-Bit Server VM by JetBrains s.r.o. macOS 13.0.1 GC: G1 Young Generation, G1 Old Generation Memory: 4096M Cores: 8
Used tools
Description
When i am printing a PriorityQueue using new Gson().toJson(priorityQueue) i get the order of the integers not in the correct way
Expected behavior
PrintingFromWhileLoop: 1 PrintingFromWhileLoop: 2 PrintingFromWhileLoop: 3 PrintingFromWhileLoop: 4 PrintingFromWhileLoop: 5 PrintingFromWhileLoop: 9
Actual behavior
MyPriorityQueueWithoutPrettyPrint: [1,2,5,4,3,9]
Reproduction steps
Queue mQueue = new PriorityQueue<>();
mQueue.offer(4);
mQueue.offer(2);
mQueue.offer(9);
mQueue.offer(1);
mQueue.offer(3);
mQueue.offer(5);
https://github.com/wincelee/MyLeetCodes/blob/c8c5e569dc8fec99070f68c568cc786833faaa6e/src/main/java/leet_code_quizes/easy/GsonPriorityQueueBug.java