001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.juneau.commons.collections;
018
019import static java.util.Collections.*;
020import static java.util.stream.Collectors.*;
021import static org.apache.juneau.commons.utils.Shorts.*;
022import static org.apache.juneau.commons.utils.Shorts.eq;
023
024import java.util.*;
025
026/**
027 * A bidirectional map with reverse key lookup by value.
028 *
029 * <p>
030 * This implementation provides efficient bidirectional lookups by maintaining two internal maps:
031 * a forward map for key-to-value lookups and a reverse map for value-to-key lookups.
032 *
033 * <h5 class='section'>Features:</h5>
034 * <ul>
035 *    <li>Implements the standard {@link Map} interface for forward key→value lookups
036 *    <li>Provides {@link #getKey(Object)} method for reverse value→key lookups
037 *    <li>Maintains insertion order using {@link LinkedHashMap} internally
038 *    <li>Filters out null keys and values when built via the {@link Builder}
039 *    <li>Supports both mutable and unmodifiable instances via the builder
040 *    <li>Thread-safety: Not thread-safe by default; external synchronization required if accessed by multiple threads
041 * </ul>
042 *
043 * <h5 class='section'>Usage:</h5>
044 * <p class='bjava'>
045 *    <jc>// Create a bidirectional map</jc>
046 *    BidiMap&lt;String,Integer&gt; <jv>map</jv> = BidiMap.<jsm>create</jsm>()
047 *       .add(<js>"one"</js>, 1)
048 *       .add(<js>"two"</js>, 2)
049 *       .add(<js>"three"</js>, 3)
050 *       .build();
051 *
052 *    <jc>// Forward lookup: key → value</jc>
053 *    Integer <jv>value</jv> = <jv>map</jv>.get(<js>"two"</js>);  <jc>// Returns 2</jc>
054 *
055 *    <jc>// Reverse lookup: value → key</jc>
056 *    String <jv>key</jv> = <jv>map</jv>.getKey(2);  <jc>// Returns "two"</jc>
057 * </p>
058 *
059 * <h5 class='section'>Null Handling:</h5>
060 * <p>
061 * The {@link Builder#add(Object, Object)}/{@link Builder#build()} construction path filters out entries with
062 * null keys or values.
063 * {@link #put(Object, Object)} and {@link #putAll(Map)} perform <b>no</b> null filtering after construction —
064 * null keys and values are stored in both the forward and reverse maps unconditionally.
065 *
066 * <h5 class='section'>Unmodifiable Instances:</h5>
067 * <p class='bjava'>
068 *    <jc>// Create an unmodifiable bidirectional map</jc>
069 *    BidiMap&lt;String,Integer&gt; <jv>map</jv> = BidiMap.<jsm>create</jsm>()
070 *       .add(<js>"one"</js>, 1)
071 *       .add(<js>"two"</js>, 2)
072 *       .unmodifiable()
073 *       .build();
074 * </p>
075 *
076 * <h5 class='section'>See Also:</h5>
077 * <ul>
078 *    <li class='link'><a class="doclink" href="../../../../../index.html#juneau-commons">Overview &gt; juneau-commons</a>
079 * </ul>
080 *
081 * @param <K> The key type.
082 * @param <V> The value type.
083 */
084@SuppressWarnings({
085   "java:S3740" // Raw Map/Iterator types used intentionally for bidirectional map operations where erased types are required for structural compatibility
086})
087public class BidiMap<K,V> implements Map<K,V> {
088
089   /**
090    * Builder class for {@link BidiMap}.
091    *
092    * <p>
093    * Provides a fluent API for constructing bidirectional maps.
094    *
095    * <h5 class='section'>Example:</h5>
096    * <p class='bjava'>
097    *    BidiMap&lt;String,Integer&gt; <jv>map</jv> = BidiMap.<jsm>create</jsm>()
098    *       .add(<js>"one"</js>, 1)
099    *       .add(<js>"two"</js>, 2)
100    *       .unmodifiable()
101    *       .build();
102    * </p>
103    *
104    * @param <K> The key type.
105    * @param <V> The value type.
106    */
107   public static class Builder<K,V> {
108      final HashMap<K,V> map = new LinkedHashMap<>();
109      final Set<V> values = new HashSet<>();
110      boolean unmodifiable;
111
112      /**
113       * Adds a key-value pair to this map.
114       *
115       * <p>
116       * Null keys and values are allowed in the builder but will be filtered out
117       * during the {@link #build()} operation.
118       *
119       * @param key The key. Can be <jk>null</jk> (filtered out, along with its value, during {@link #build()}).
120       * @param value The value. Can be <jk>null</jk> (filtered out, along with its key, during {@link #build()}).
121       * @return This object.
122       * @throws IllegalArgumentException if the value already exists mapped to a different key.
123       */
124      public Builder<K,V> add(K key, V value) {
125         if (nn(key) && nn(value)) {
126            var existingValue = map.get(key);
127            if (nn(existingValue) && ! existingValue.equals(value)) {
128               // Key is being overwritten with a different value, remove old value from tracking
129               values.remove(existingValue);
130            }
131            req(! (values.contains(value) && ! value.equals(existingValue)), "Value '%s' is already mapped to a different key in this BidiMap.", value);
132            values.add(value);
133         }
134         map.put(key, value);
135         return this;
136      }
137
138      /**
139       * Builds a new {@link BidiMap} from the entries added to this builder.
140       *
141       * <p>
142       * Null keys and values are automatically filtered out during construction.
143       *
144       * @return A new {@link BidiMap} instance.
145       */
146      public BidiMap<K,V> build() {
147         return new BidiMap<>(this);
148      }
149
150      /**
151       * Makes the resulting map unmodifiable.
152       *
153       * <p>
154       * When set, the built map will be wrapped with {@link Collections#unmodifiableMap(Map)},
155       * preventing any modifications after construction.
156       *
157       * @return This object.
158       */
159      public Builder<K,V> unmodifiable() {
160         unmodifiable = true;
161         return this;
162      }
163   }
164
165   /**
166    * Creates a new builder for this class.
167    *
168    * @param <K> The key type.
169    * @param <V> The value type.
170    * @return A new {@link Builder} instance.
171    */
172   public static <K,V> Builder<K,V> create() {
173      return new Builder<>();
174   }
175
176   private final Map<K,V> forward;
177   private final Map<V,K> reverse;
178
179   /**
180    * Constructor.
181    *
182    * <p>
183    * Constructs a bidirectional map from the provided builder, automatically filtering
184    * out any entries with null keys or values.
185    *
186    * @param builder The builder containing the initial entries. Must not be <jk>null</jk> or a {@link NullPointerException} is thrown.
187    */
188   public BidiMap(Builder<K,V> builder) {
189      var forward2 = builder.map.entrySet().stream().filter(x -> nn(x.getKey()) && nn(x.getValue())).collect(toMap(Map.Entry::getKey, Map.Entry::getValue, (a, b) -> b, LinkedHashMap::new));
190      var reverse2 = builder.map.entrySet().stream().filter(x -> nn(x.getKey()) && nn(x.getValue())).collect(toMap(Map.Entry::getValue, Map.Entry::getKey, (a, b) -> b, LinkedHashMap::new));
191      this.forward = builder.unmodifiable ? unmodifiableMap(forward2) : forward2;
192      this.reverse = builder.unmodifiable ? unmodifiableMap(reverse2) : reverse2;
193   }
194
195   /**
196    * Removes all key-value mappings from this map.
197    *
198    * <p>
199    * Clears both the forward and reverse maps.
200    *
201    * @throws UnsupportedOperationException if the map is unmodifiable.
202    */
203   @Override /* Map */
204   public void clear() {
205      forward.clear();
206      reverse.clear();
207   }
208
209   /**
210    * Returns <jk>true</jk> if this map contains a mapping for the specified key.
211    *
212    * @param key The key to check for. Can be <jk>null</jk>.
213    * @return <jk>true</jk> if this map contains a mapping for the specified key.
214    */
215   @Override /* Map */
216   public boolean containsKey(Object key) {
217      return forward.containsKey(key);
218   }
219
220   /**
221    * Returns <jk>true</jk> if this map maps one or more keys to the specified value.
222    *
223    * <p>
224    * This implementation uses the reverse map for efficient lookup.
225    *
226    * @param value The value to check for. Can be <jk>null</jk>.
227    * @return <jk>true</jk> if this map maps one or more keys to the specified value.
228    */
229   @Override /* Map */
230   public boolean containsValue(Object value) {
231      return reverse.containsKey(value);
232   }
233
234   /**
235    * Returns a {@link Set} view of the mappings contained in this map.
236    *
237    * @return A set view of the mappings contained in this map.
238    */
239   @Override /* Map */
240   public Set<Entry<K,V>> entrySet() {
241      return forward.entrySet();
242   }
243
244   /**
245    * Returns the value to which the specified key is mapped, or <jk>null</jk> if this map contains no mapping for the key.
246    *
247    * @param key The key whose associated value is to be returned. Can be <jk>null</jk>.
248    * @return The value to which the specified key is mapped, or <jk>null</jk> if this map contains no mapping for the key.
249    */
250   @Override /* Map */
251   public V get(Object key) {
252      return forward.get(key);
253   }
254
255   /**
256    * Returns the key that is currently mapped to the specified value.
257    *
258    * <p>
259    * This is the reverse lookup operation that makes this a bidirectional map.
260    *
261    * <h5 class='section'>Example:</h5>
262    * <p class='bjava'>
263    *    BidiMap&lt;String,Integer&gt; <jv>map</jv> = BidiMap.<jsm>create</jsm>().add(<js>"two"</js>, 2).build();
264    *    String <jv>key</jv> = <jv>map</jv>.getKey(2);  <jc>// Returns "two"</jc>
265    * </p>
266    *
267    * @param value The value whose associated key is to be returned. Can be <jk>null</jk>.
268    * @return The key to which the specified value is mapped, or <jk>null</jk> if this map contains no mapping for the value.
269    */
270   public K getKey(V value) {
271      return reverse.get(value);
272   }
273
274   /**
275    * Returns <jk>true</jk> if this map contains no key-value mappings.
276    *
277    * @return <jk>true</jk> if this map contains no key-value mappings.
278    */
279   @Override /* Map */
280   public boolean isEmpty() { return forward.isEmpty(); }
281
282   /**
283    * Returns a {@link Set} view of the keys contained in this map.
284    *
285    * @return A set view of the keys contained in this map.
286    */
287   @Override /* Map */
288   public Set<K> keySet() {
289      return forward.keySet();
290   }
291
292   /**
293    * Associates the specified value with the specified key in this map.
294    *
295    * <p>
296    * This operation updates both the forward map (key→value) and the reverse map (value→key).
297    *
298    * @param key The key with which the specified value is to be associated. Can be <jk>null</jk>.
299    * @param value The value to be associated with the specified key. Can be <jk>null</jk>.
300    * @return The previous value associated with the key, or <jk>null</jk> if there was no mapping for the key.
301    * @throws UnsupportedOperationException if the map is unmodifiable.
302    * @throws IllegalArgumentException if the value already exists mapped to a different key.
303    */
304   @Override /* Map */
305   public V put(K key, V value) {
306      var existingKeyForValue = reverse.get(value);
307      req(! (nn(existingKeyForValue) && ! existingKeyForValue.equals(key)), "Value '%s' is already mapped to key '%s' in this BidiMap.", value, existingKeyForValue);
308      var oldValue = forward.put(key, value);
309      if (nn(oldValue)) {
310         reverse.remove(oldValue);
311      }
312      reverse.put(value, key);
313      return oldValue;
314   }
315
316   /**
317    * Copies all mappings from the specified map to this map.
318    *
319    * <p>
320    * This operation updates both the forward and reverse maps.
321    *
322    * @param m Mappings to be stored in this map. Must not be <jk>null</jk> or a {@link NullPointerException} is thrown.
323    * @throws UnsupportedOperationException if the map is unmodifiable.
324    * @throws IllegalArgumentException if any value in the map already exists mapped to a different key.
325    */
326   @Override /* Map */
327   public void putAll(Map<? extends K,? extends V> m) {
328      // Check for duplicate values before making any changes
329      for (var entry : m.entrySet()) {
330         var key = entry.getKey();
331         var value = entry.getValue();
332         var existingKeyForValue = reverse.get(value);
333         req(! (nn(existingKeyForValue) && ! existingKeyForValue.equals(key)), "Value '%s' is already mapped to key '%s' in this BidiMap.", value, existingKeyForValue);
334      }
335      // All checks passed, now perform the updates
336      for (var entry : m.entrySet()) {
337         put(entry.getKey(), entry.getValue());
338      }
339   }
340
341   /**
342    * Removes the mapping for a key from this map if it is present.
343    *
344    * <p>
345    * This operation removes the entry from both the forward and reverse maps.
346    *
347    * @param key The key whose mapping is to be removed from the map. Can be <jk>null</jk>.
348    * @return The previous value associated with the key, or <jk>null</jk> if there was no mapping for the key.
349    * @throws UnsupportedOperationException if the map is unmodifiable.
350    */
351   @Override /* Map */
352   public V remove(Object key) {
353      var value = forward.remove(key);
354      reverse.remove(value);
355      return value;
356   }
357
358   /**
359    * Returns the number of key-value mappings in this map.
360    *
361    * @return The number of key-value mappings in this map.
362    */
363   @Override /* Map */
364   public int size() {
365      return forward.size();
366   }
367
368   /**
369    * Returns a {@link Collection} view of the values contained in this map.
370    *
371    * @return A collection view of the values contained in this map.
372    */
373   @Override /* Map */
374   public Collection<V> values() {
375      return forward.values();
376   }
377
378   /**
379    * Returns a string representation of this map.
380    *
381    * <p>
382    * The format follows the standard Java map convention: <c>"{key1=value1, key2=value2, ...}"</c>
383    *
384    * @return A string representation of this map.
385    */
386   @Override
387   public String toString() {
388      return forward.toString();
389   }
390
391   /**
392    * Compares the specified object with this map for equality.
393    *
394    * <p>
395    * Returns <jk>true</jk> if the given object is also a map and the two maps represent the same
396    * mappings. More formally, two maps <c>m1</c> and <c>m2</c> represent the same mappings if
397    * <c>m1.entrySet().equals(m2.entrySet())</c>.
398    *
399    * <p>
400    * This implementation compares the entry sets of the two maps.
401    *
402    * @param o Object to be compared for equality with this map.
403    * @return <jk>true</jk> if the specified object is equal to this map.
404    */
405   @Override
406   public boolean equals(Object o) {
407      return (o instanceof Map o2) && eq(this, o2, (x, y) -> x.entrySet().equals(y.entrySet()));
408   }
409
410   /**
411    * Returns the hash code value for this map.
412    *
413    * <p>
414    * The hash code of a map is defined to be the sum of the hash codes of each entry in the map's
415    * <c>entrySet()</c> view. This ensures that <c>m1.equals(m2)</c> implies that
416    * <c>m1.hashCode()==m2.hashCode()</c> for any two maps <c>m1</c> and <c>m2</c>, as required
417    * by the general contract of {@link Object#hashCode()}.
418    *
419    * <p>
420    * This implementation computes the hash code from the entry set.
421    *
422    * @return The hash code value for this map.
423    */
424   @Override
425   public int hashCode() {
426      return entrySet().hashCode();
427   }
428}