001/*
002 * CDDL HEADER START
003 *
004 * The contents of this file are subject to the terms of the
005 * Common Development and Distribution License, Version 1.0 only
006 * (the "License").  You may not use this file except in compliance
007 * with the License.
008 *
009 * You can obtain a copy of the license at legal-notices/CDDLv1_0.txt
010 * or http://forgerock.org/license/CDDLv1.0.html.
011 * See the License for the specific language governing permissions
012 * and limitations under the License.
013 *
014 * When distributing Covered Code, include this CDDL HEADER in each
015 * file and include the License file at legal-notices/CDDLv1_0.txt.
016 * If applicable, add the following below this CDDL HEADER, with the
017 * fields enclosed by brackets "[]" replaced with your own identifying
018 * information:
019 *      Portions Copyright [yyyy] [name of copyright owner]
020 *
021 * CDDL HEADER END
022 *
023 *      Copyright 2014-2015 ForgeRock AS
024 */
025package org.opends.server.types;
026
027import java.util.*;
028
029/**
030 * A small map of values. This map implementation is optimized to use as little
031 * memory as possible in the case where there zero or one elements. In addition,
032 * any normalization of entries is delayed until the second entry is added
033 * (normalization may be triggered by invoking {@link Object#hashCode()} or
034 * {@link Object#equals(Object)}.
035 * <p>
036 * Null keys are not supported by this map.
037 *
038 * @param <K>
039 *          the type of keys maintained by this map
040 * @param <V>
041 *          the type of mapped values
042 */
043public class SmallMap<K, V> extends AbstractMap<K, V>
044{
045
046  /** The map of entries if there are more than one. */
047  private LinkedHashMap<K, V> entries;
048
049  /** The first key of the Map. */
050  private K firstKey;
051  /** The first value of the Map. */
052  private V firstValue;
053
054
055  /** Creates a new small map which is initially empty. */
056  public SmallMap()
057  {
058    // No implementation required.
059  }
060
061  private void rejectIfNull(Object key)
062  {
063    if (key == null)
064    {
065      throw new NullPointerException("null keys are not allowed");
066    }
067  }
068
069  /** {@inheritDoc} */
070  @Override
071  public V get(Object key)
072  {
073    rejectIfNull(key);
074    if (entries != null)
075    { // >= 2 entries case
076      return entries.get(key);
077    }
078    // 0 and 1 case
079    if (firstKey != null && firstKey.equals(key))
080    {
081      return firstValue;
082    }
083    return null;
084  }
085
086  /** {@inheritDoc} */
087  @Override
088  public V put(K key, V value)
089  {
090    rejectIfNull(key);
091    if (entries != null)
092    { // >= 2 entries case
093      return entries.put(key, value);
094    }
095    if (firstKey == null)
096    { // 0 entries case
097      firstKey = key;
098      firstValue = value;
099      return null;
100    }
101    // 1 entry case
102    if (firstKey.equals(key))
103    { // replace value
104      V oldValue = firstValue;
105      firstValue = value;
106      return oldValue;
107    }
108    // overflow to the underlying map
109    entries = new LinkedHashMap<>(2);
110    entries.put(firstKey, firstValue);
111    firstKey = null;
112    firstValue = null;
113    return entries.put(key, value);
114  }
115
116  /** {@inheritDoc} */
117  @Override
118  public void putAll(Map<? extends K, ? extends V> m)
119  {
120    for (Entry<? extends K, ? extends V> entry : m.entrySet())
121    {
122      put(entry.getKey(), entry.getValue());
123    }
124  }
125
126  /** {@inheritDoc} */
127  @Override
128  public V remove(Object key)
129  {
130    if (entries != null)
131    {
132      // Note: if there is one or zero values left we could stop using the map.
133      // However, lets assume that if the map was multi-valued before
134      // then it may become multi-valued again.
135      return entries.remove(key);
136    }
137
138    if (firstKey != null && firstKey.equals(key))
139    {
140      V oldV = firstValue;
141      firstKey = null;
142      firstValue = null;
143      return oldV;
144    }
145    return null;
146  }
147
148  /** {@inheritDoc} */
149  @Override
150  public boolean containsKey(Object key)
151  {
152    rejectIfNull(key);
153    if (entries != null)
154    {
155      return entries.containsKey(key);
156    }
157    return firstKey != null && firstKey.equals(key);
158  }
159
160  /** {@inheritDoc} */
161  @Override
162  public boolean containsValue(Object value)
163  {
164    if (entries != null)
165    {
166      return entries.containsValue(value);
167    }
168    if (firstKey == null)
169    {
170      return false;
171    }
172    if (firstValue == null)
173    {
174      return value == null;
175    }
176    return firstValue.equals(value);
177  }
178
179  /** {@inheritDoc} */
180  @Override
181  public void clear()
182  {
183    firstKey = null;
184    firstValue = null;
185    entries = null;
186  }
187
188  /** {@inheritDoc} */
189  @Override
190  public int size()
191  {
192    if (entries != null)
193    {
194      return entries.size();
195    }
196    return firstKey != null ? 1 : 0;
197  }
198
199  /** {@inheritDoc} */
200  @Override
201  public Set<Entry<K, V>> entrySet()
202  {
203    if (entries != null)
204    {
205      return entries.entrySet();
206    }
207    if (firstKey == null)
208    {
209      return Collections.emptySet();
210    }
211
212    return new AbstractSet<Entry<K, V>>()
213    {
214
215      @Override
216      public Iterator<Entry<K, V>> iterator()
217      {
218        return new Iterator<Entry<K, V>>()
219        {
220
221          private boolean isFirst = true;
222
223          @Override
224          public boolean hasNext()
225          {
226            return isFirst;
227          }
228
229          @Override
230          public Entry<K, V> next()
231          {
232            if (!isFirst)
233            {
234              throw new NoSuchElementException();
235            }
236            isFirst = false;
237            return new SimpleEntry<>(firstKey, firstValue);
238          }
239
240          @Override
241          public void remove()
242          {
243            firstKey = null;
244            firstValue = null;
245          }
246        };
247      }
248
249      @Override
250      public int size()
251      {
252        return 1;
253      }
254    };
255  }
256
257}