OPENDJ-3281 Move SmallSet into its own file

Jean-Noël Rouvignac

07.57.2016 5eb89147746f7bd91f29f3e45d3e85ca04bba9db

OPENDJ-3281 Move SmallSet into its own file

AttributeBuilder.java:
Moved SmallSet out of this class.

AttrHistoricalMultiple.java:
Use SmallSet.

SmallSet.java: ADDED with tests

 opendj-core/src/main/java/com/forgerock/opendj/util/SmallSet.java

New file
@@ -0,0 +1,252 @@
/*
 * The contents of this file are subject to the terms of the Common Development and
 * Distribution License (the License). You may not use this file except in compliance with the
 * License.
 *
 * You can obtain a copy of the License at legal/CDDLv1.0.txt. See the License for the
 * specific language governing permission and limitations under the License.
 *
 * When distributing Covered Software, include this CDDL Header Notice in each file and include
 * the License file at legal/CDDLv1.0.txt. If applicable, add the following below the CDDL
 * Header, with the fields enclosed by brackets [] replaced by your own identifying
 * information: "Portions Copyright [year] [name of copyright owner]".
 *
 * Copyright 2006-2010 Sun Microsystems, Inc.
 * Portions Copyright 2012-2016 ForgeRock AS.
 */
package com.forgerock.opendj.util;

import java.util.AbstractSet;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.NoSuchElementException;

import org.forgerock.util.Reject;

/**
 * A small set of values. This set implementation is optimized to use
 * as little memory as possible in the case where there zero or one elements.
 * <p>
 * In addition, any normalization of elements is delayed until the second
 * element is added (normalization may be triggered by invoking
 * {@link Object#hashCode()} or {@link Object#equals(Object)}.
 *
 * @param <E>
 *          The type of elements to be contained in this small set.
 */
public final class SmallSet<E> extends AbstractSet<E> {
    /**
     * The set of elements if there are more than one.
     * <p>
     * It is implemented using a {@link Map} to be able to retrieve quickly
     * the actual value with {@link Map#get(Object)}.
     * <p>
     * See the {@link #get(Object)} and {@link #addOrReplace(Object)} methods.
     */
    private LinkedHashMap<E, E> elements;
    /** The first element. */
    private E firstElement;

    /** Creates a new small set which is initially empty. */
    public SmallSet() {
        // No implementation required.
    }

    /**
     * Creates a new small set from the provided collection.
     *
     * @param c
     *          the collection whose elements are to be placed into this set
     * @throws java.lang.NullPointerException
     *           if the specified collection is null
     */
    public SmallSet(Collection<? extends E> c) {
        addAll(c);
    }

    /**
     * Creates a new small set with an initial capacity.
     *
     * @param initialCapacity
     *          The capacity of the set
     */
    public SmallSet(int initialCapacity) {
        Reject.ifFalse(initialCapacity >= 0);

        if (initialCapacity > 1) {
            elements = new LinkedHashMap<>(initialCapacity);
        }
    }

    @Override
    public boolean add(E e) {
        // Special handling for the first value which avoids potentially expensive normalization.
        if (firstElement == null && elements == null) {
            firstElement = e;
            return true;
        }

        // Create the value set if necessary.
        if (elements == null) {
            if (firstElement.equals(e)) {
                return false;
            }

            elements = new LinkedHashMap<>(2);
            addForbidsReplace(elements, firstElement);
            firstElement = null;
        }

        return addForbidsReplace(elements, e);
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        if (elements != null) {
            return addAllForbidsReplace(elements, c);
        }

        if (firstElement != null && !c.isEmpty()) {
            elements = new LinkedHashMap<>(1 + c.size());
            addForbidsReplace(elements, firstElement);
            firstElement = null;
            return addAllForbidsReplace(elements, c);
        }

        // Initially empty.
        switch (c.size()) {
        case 0:
            // Do nothing.
            return false;
        case 1:
            firstElement = c.iterator().next();
            return true;
        default:
            elements = new LinkedHashMap<>(c.size());
            addAllForbidsReplace(elements, c);
            return true;
        }
    }

    private boolean addForbidsReplace(LinkedHashMap<E, E> map, E e) {
        if (map.containsKey(e)) {
            return false;
        }
        return map.put(e, e) == null;
    }

    private boolean addAllForbidsReplace(LinkedHashMap<E, E> map, Collection<? extends E> c) {
        boolean modified = false;
        for (E e : c) {
            modified |= addForbidsReplace(map, e);
        }
        return modified;
    }

    /**
     * Adds an element to this small set or replaces the existing element's value with the provided
     * one.
     * <p>
     * The replacement aspect is useful when the small set uses a "normalized" value to compare
     * elements for equality but stores them as an "actual" value.
     *
     * @param element
     *          the actual element to replace in this small set
     */
    public void addOrReplace(E element) {
        remove(element);
        add(element);
    }

    @Override
    public void clear() {
        firstElement = null;
        elements = null;
    }

    @Override
    public Iterator<E> iterator() {
        if (elements != null) {
            return elements.keySet().iterator();
        } else if (firstElement != null) {
            return new Iterator<E>() {
                private boolean hasNext = true;

                @Override
                public boolean hasNext() {
                    return hasNext;
                }

                @Override
                public E next() {
                    if (!hasNext) {
                        throw new NoSuchElementException();
                    }

                    hasNext = false;
                    return firstElement;
                }

                @Override
                public void remove() {
                    firstElement = null;
                }
            };
        } else {
            return Collections.<E> emptySet().iterator();
        }
    }

    @Override
    public boolean remove(Object o) {
        if (elements != null) {
            // Note: if there is one or zero values left we could stop using the set.
            // However, lets assume that if the set was multi-valued before
            // then it may become multi-valued again.
            return elements.keySet().remove(o);
        }

        if (firstElement != null && firstElement.equals(o)) {
            firstElement = null;
            return true;
        }
        return false;
    }

    @Override
    public boolean contains(Object o) {
        if (elements != null) {
            return elements.containsKey(o);
        }
        return firstElement != null && firstElement.equals(o);
    }

    /**
     * Returns the element in this small set that is equal to the provided element.
     *
     * @param o
     *          the element to look for
     * @return the element in this small set that is equal to the provided element,
     *         or {@code null} if no such element exists
     */
    public E get(Object o) {
        if (elements != null) {
            return elements.get(o);
        }
        return firstElement != null && firstElement.equals(o) ? firstElement : null;
    }

    @Override
    public int size() {
        if (elements != null) {
            return elements.size();
        } else if (firstElement != null) {
            return 1;
        } else {
            return 0;
        }
    }
}

 opendj-core/src/test/java/com/forgerock/opendj/util/SmallSetTest.java

New file
@@ -0,0 +1,264 @@
/*
 * The contents of this file are subject to the terms of the Common Development and
 * Distribution License (the License). You may not use this file except in compliance with the
 * License.
 *
 * You can obtain a copy of the License at legal/CDDLv1.0.txt. See the License for the
 * specific language governing permission and limitations under the License.
 *
 * When distributing Covered Software, include this CDDL Header Notice in each file and include
 * the License file at legal/CDDLv1.0.txt. If applicable, add the following below the CDDL
 * Header, with the fields enclosed by brackets [] replaced by your own identifying
 * information: "Portions Copyright [year] [name of copyright owner]".
 *
 * Copyright 2016 ForgeRock AS.
 */
package com.forgerock.opendj.util;

import static java.util.Locale.*;

import static org.assertj.core.api.Assertions.*;

import java.util.Arrays;
import java.util.LinkedHashSet;

import org.testng.annotations.Test;

/** Tests for the {@link SmallSet} class. */
@SuppressWarnings("javadoc")
public class SmallSetTest extends UtilTestCase {
    // @Checkstyle:off
    private final CaseInsentiveString _a = c("a");
    private final CaseInsentiveString _A = c("A");
    private final CaseInsentiveString _b = c("b");
    private final CaseInsentiveString _c = c("c");
    private final CaseInsentiveString _d = c("d");
    // @Checkstyle:on

    @Test
    public void testFirstElement() throws Exception {
        SmallSet<String> set = new SmallSet<>();
        assertThat(set).hasSize(0)
                       .isEmpty();
        assertThat(set.contains("d")).isFalse();
        assertThat(set.remove("d")).isFalse();
        assertThat(set).hasSize(0)
                       .isEmpty();
        assertThat(set.add("a")).isTrue();
        assertThat(set).hasSize(1)
                       .containsExactly("a");
        assertThat(set.contains("a")).isTrue();
        assertThat(set.contains("d")).isFalse();
        assertThat(set.add("a")).isFalse();
        assertThat(set).hasSize(1)
                       .containsExactly("a");
        assertThat(set.remove("c")).isFalse();
        assertThat(set).hasSize(1)
                       .containsExactly("a");
        assertThat(set.remove("a")).isTrue();
        assertThat(set).hasSize(0)
                       .isEmpty();
    }

    @Test
    public void testElements() throws Exception {
        SmallSet<String> set = new SmallSet<>();
        assertThat(set).hasSize(0)
                       .isEmpty();
        assertThat(set.add("a")).isTrue();
        assertThat(set).hasSize(1)
                       .containsExactly("a");
        assertThat(set.add("a")).isFalse();
        assertThat(set).hasSize(1)
                       .containsExactly("a");
        assertThat(set.add("b")).isTrue();
        assertThat(set).hasSize(2)
                       .containsExactly("a", "b");
        assertThat(set.add("c")).isTrue();
        assertThat(set).hasSize(3)
                       .containsExactly("a", "b", "c");
        assertThat(set.contains("a")).isTrue();
        assertThat(set.contains("d")).isFalse();

        assertThat(set.remove("d")).isFalse();
        assertThat(set).hasSize(3)
                       .containsExactly("a", "b", "c");
        assertThat(set.remove("b")).isTrue();
        assertThat(set).hasSize(2)
                       .containsExactly("a", "c");
        assertThat(set.remove("a")).isTrue();
        assertThat(set).hasSize(1)
                       .containsExactly("c");
        assertThat(set.remove("c")).isTrue();

        assertThat(set).hasSize(0)
                       .isEmpty();
    }

    @Test
    public void testFirstElementWithNormalizedValues() throws Exception {
        SmallSet<CaseInsentiveString> set = new SmallSet<>();
        assertThat(set).hasSize(0)
                       .isEmpty();
        assertThat(set.get(_d)).isNull();
        assertThat(set.remove(_c)).isFalse();
        assertThat(set).hasSize(0)
                       .isEmpty();
        assertThat(set.add(_a)).isTrue();
        assertThat(set).hasSize(1)
                       .containsExactly(_a);
        assertThat(set.get(_a)).isSameAs(_a);
        assertThat(set.get(_d)).isNull();
        assertThat(set.add(_A)).isFalse();
        assertThat(set.get(_a)).isSameAs(_a);
        assertThat(set).hasSize(1)
                       .containsExactly(_a);
        set.addOrReplace(_A);
        assertThat(set).hasSize(1)
                       .containsExactly(_a);
        set.addOrReplace(_A);
        assertThat(set).hasSize(1)
                       .containsExactly(_A);
        assertThat(set.remove(_c)).isFalse();
        assertThat(set).hasSize(1)
                       .containsExactly(_a);
        assertThat(set.remove(_a)).isTrue();
        assertThat(set).hasSize(0)
                       .isEmpty();
    }

    @Test
    public void testElementsWithNormalizedValues() throws Exception {
        SmallSet<CaseInsentiveString> set = new SmallSet<>();
        assertThat(set).hasSize(0)
                       .isEmpty();
        assertThat(set.add(c("a"))).isTrue();
        assertThat(set).hasSize(1)
                       .containsExactly(c("a"));
        assertThat(set.add(c("a"))).isFalse();
        assertThat(set).hasSize(1)
                       .containsExactly(c("a"));
        assertThat(set.add(c("b"))).isTrue();
        assertThat(set).hasSize(2)
                       .containsExactly(c("a"), c("b"));
        assertThat(set.add(c("c"))).isTrue();
        assertThat(set).hasSize(3)
                       .containsExactly(c("a"), c("b"), c("c"));

        assertThat(set.remove(c("d"))).isFalse();
        assertThat(set).hasSize(3)
                       .containsExactly(c("a"), c("b"), c("c"));
        assertThat(set.remove(c("b"))).isTrue();
        assertThat(set).hasSize(2)
                       .containsExactly(c("a"), c("c"));
        assertThat(set.remove(c("a"))).isTrue();
        assertThat(set).hasSize(1)
                       .containsExactly(c("c"));
        assertThat(set.remove(c("c"))).isTrue();

        assertThat(set).hasSize(0)
                       .isEmpty();
    }

    @Test
    public void testElementsWithNormalizedValuesSpecificMethods() throws Exception {
        final SmallSet<CaseInsentiveString> set = new SmallSet<>();
        assertThat(set).hasSize(0)
                       .isEmpty();
        assertThat(set.addAll(newLinkedHashSet(_a, _b, _c))).isTrue();
        assertThat(set).hasSize(3)
                       .containsExactly(_a, _b, _c);

        assertThat(set.add(_a)).isFalse();
        assertThat(set.get(_a)).isSameAs(_a);

        assertThat(set.add(_A)).isFalse();
        assertThat(set.get(_a)).isSameAs(_a);

        assertThat(set.get(_d)).isNull();

        set.addOrReplace(_a);
        assertThat(set).hasSize(3)
                       .containsExactly(_b, _c, _a);
        assertThat(set.get(_a)).isSameAs(_a);

        set.addOrReplace(_A);
        assertThat(set).hasSize(3)
                       .containsExactly(_b, _c, _A);
        assertThat(set.get(_a)).isSameAs(_A);
    }

    @Test
    public void testAddAllOnInitiallyEmptySet() {
        SmallSet<String> set = new SmallSet<>();
        assertThat(set).hasSize(0)
                       .isEmpty();
        assertThat(set.addAll(SmallSetTest.<String> newLinkedHashSet())).isFalse();
        assertThat(set).hasSize(0)
                       .isEmpty();
        assertThat(set.addAll(newLinkedHashSet("a"))).isTrue();
        assertThat(set).hasSize(1)
                       .containsExactly("a");
        set.clear();
        assertThat(set).hasSize(0)
                       .isEmpty();
        assertThat(set.addAll(newLinkedHashSet("a", "b", "c"))).isTrue();
        assertThat(set).hasSize(3)
                       .containsExactly("a", "b", "c");
    }

    @Test
    public void testAddAllOnFirstElementAndAllElements() {
        SmallSet<String> set = new SmallSet<>();
        assertThat(set).hasSize(0)
                       .isEmpty();
        assertThat(set.add("a")).isTrue();
        assertThat(set).hasSize(1)
                       .containsExactly("a");
        assertThat(set.addAll(newLinkedHashSet("a", "b", "c"))).isTrue();
        assertThat(set).hasSize(3)
                       .containsExactly("a", "b", "c");
        assertThat(set.addAll(newLinkedHashSet("a", "b", "c"))).isFalse();
        assertThat(set).hasSize(3)
                       .containsExactly("a", "b", "c");
    }

    @SuppressWarnings("unchecked")
    private static <E> LinkedHashSet<E> newLinkedHashSet(E... elements) {
        return new LinkedHashSet<>(Arrays.asList(elements));
    }

    private static CaseInsentiveString c(String s) {
        return new CaseInsentiveString(s);
    }

    private static final class CaseInsentiveString {
        private String s;

        public CaseInsentiveString(String s) {
            this.s = s;
        }

        private String lowerCase() {
            return s.toLowerCase(ROOT);
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof CaseInsentiveString) {
                return lowerCase().equals(((CaseInsentiveString) obj).lowerCase());
            }
            return false;
        }

        @Override
        public int hashCode() {
            return lowerCase().hashCode();
        }

        @Override
        public String toString() {
            return s;
        }
    }
}

 opendj-server-legacy/src/main/java/org/opends/server/replication/plugin/AttrHistoricalMultiple.java

@@ -17,8 +17,6 @@
package org.opends.server.replication.plugin;

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

import org.forgerock.opendj.ldap.ByteString;
@@ -30,6 +28,8 @@
import org.opends.server.types.Entry;
import org.opends.server.types.Modification;

import com.forgerock.opendj.util.SmallSet;

/**
 * This class is used to store historical information for multiple valued attributes.
 * One object of this type is created for each attribute that was changed in the entry.
@@ -42,16 +42,8 @@
  private CSN deleteTime;
  /** Last time the attribute was modified. */
  private CSN lastUpdateTime;
  /**
   * Change history for the values of this attribute.
   * <p>
   * We are using a LinkedHashMap here because we want:
   * <ol>
   * <li>Fast access for removing/adding a AttrValueHistorical keyed by the attribute value => Use a Map</li>
   * <li>Ordering changes according to the CSN of each changes => Use a LinkedHashMap</li>
   * </ol>
   */
  private final Map<AttrValueHistorical, AttrValueHistorical> valuesHist = new LinkedHashMap<>();
  /** Change history for the values of this attribute. */
  private final SmallSet<AttrValueHistorical> valuesHist = new SmallSet<>();

   /**
    * Create a new object from the provided information.
@@ -59,15 +51,13 @@
    * @param updateTime the last time this attribute was updated
    * @param valuesHist the new attribute values when updated.
    */
   public AttrHistoricalMultiple(CSN deleteTime,
       CSN updateTime,
       Map<AttrValueHistorical,AttrValueHistorical> valuesHist)
   AttrHistoricalMultiple(CSN deleteTime, CSN updateTime, Set<AttrValueHistorical> valuesHist)
   {
     this.deleteTime = deleteTime;
     this.lastUpdateTime = updateTime;
     if (valuesHist != null)
     {
       this.valuesHist.putAll(valuesHist);
      this.valuesHist.addAll(valuesHist);
     }
   }

@@ -82,7 +72,7 @@
    * Returns the last time when the attribute was updated.
    * @return the last time when the attribute was updated
    */
   private CSN getLastUpdateTime()
   CSN getLastUpdateTime()
   {
     return lastUpdateTime;
   }
@@ -94,18 +84,6 @@
   }

   /**
    * Duplicate an object. CSNs are duplicated by references.
    * <p>
    * Method only called in tests
    *
    * @return the duplicated object.
    */
   AttrHistoricalMultiple duplicate()
   {
     return new AttrHistoricalMultiple(this.deleteTime, this.lastUpdateTime, this.valuesHist);
   }

   /**
    * Delete all historical information that is older than the provided CSN for
    * this attribute type.
    * Add the delete attribute state information
@@ -115,8 +93,7 @@
   {
     // iterate through the values in the valuesInfo and suppress all the values
     // that have not been added after the date of this delete.
     Iterator<AttrValueHistorical> it = valuesHist.keySet().iterator();
     while (it.hasNext())
     for (Iterator<AttrValueHistorical> it = valuesHist.iterator(); it.hasNext();)
     {
       AttrValueHistorical info = it.next();
       if (csn.isNewerThanOrEqualTo(info.getValueUpdateTime()) &&
@@ -189,8 +166,9 @@
     * Update the historical information when a value is added.
     *
     * @param addedValue
     *          values that was added
   *          the added value
     * @param attrType
   *          the attribute type of the added value
     * @param csn
     *          time when the value was added
     */
@@ -201,23 +179,17 @@

  private void update(CSN csn, AttrValueHistorical valInfo)
  {
    updateValInfo(valInfo, valInfo);
    valuesHist.addOrReplace(valInfo);
    if (csn.isNewerThan(lastUpdateTime))
    {
      lastUpdateTime = csn;
    }
  }

  private void updateValInfo(AttrValueHistorical oldValInfo, AttrValueHistorical newValInfo)
  {
    valuesHist.remove(oldValInfo);
    valuesHist.put(newValInfo, newValInfo);
  }

  @Override
  public Set<AttrValueHistorical> getValuesHistorical()
  {
    return valuesHist.keySet();
    return valuesHist;
  }

  @Override
@@ -394,7 +366,7 @@
      m.setModificationType(ModificationType.REPLACE);
      AttributeBuilder builder = new AttributeBuilder(modAttr.getAttributeDescription());

      for (Iterator<AttrValueHistorical> it = valuesHist.keySet().iterator(); it.hasNext();)
      for (Iterator<AttrValueHistorical> it = valuesHist.iterator(); it.hasNext();)
      {
        AttrValueHistorical valInfo = it.next();

@@ -440,7 +412,11 @@
        // update historical information
        AttrValueHistorical valInfo = new AttrValueHistorical(val, attrType, null, csn);
        AttrValueHistorical oldValInfo = valuesHist.get(valInfo);
        if (oldValInfo != null)
        if (oldValInfo == null)
        {
          valuesHist.add(valInfo);
        }
        else
        {
          // this value already exist in the historical information
          if (csn.equals(oldValInfo.getValueUpdateTime()))
@@ -452,17 +428,13 @@
          if (csn.isNewerThanOrEqualTo(oldValInfo.getValueDeleteTime()) &&
              csn.isNewerThanOrEqualTo(oldValInfo.getValueUpdateTime()))
          {
            updateValInfo(oldValInfo, valInfo);
            valuesHist.addOrReplace(valInfo);
          }
          else if (oldValInfo.isUpdate())
          {
            deleteIt = false;
          }
        }
        else
        {
          updateValInfo(oldValInfo, valInfo);
        }

        /* if the attribute value is not to be deleted
         * or if attribute value is not present suppress it from the
@@ -536,7 +508,7 @@
         * add it in the historical information
         * let the operation process normally
         */
        valuesHist.put(valInfo, valInfo);
        valuesHist.add(valInfo);
      }
      else
      {
@@ -549,7 +521,7 @@
           */
          if (csn.isNewerThan(oldValInfo.getValueUpdateTime()))
          {
            updateValInfo(oldValInfo, valInfo);
            valuesHist.addOrReplace(valInfo);
          }
          builder.remove(addVal);
        }
@@ -560,7 +532,7 @@
           */
          if (csn.isNewerThanOrEqualTo(oldValInfo.getValueDeleteTime()))
          {
            updateValInfo(oldValInfo, valInfo);
            valuesHist.addOrReplace(valInfo);
          }
          else
          {
@@ -642,7 +614,7 @@
      }
      sb.append("lastUpdateTime=").append(lastUpdateTime);
    }
    sb.append(", valuesHist=").append(valuesHist.keySet());
    sb.append(", valuesHist=").append(valuesHist);
    sb.append(")");
    return sb.toString();
  }

 opendj-server-legacy/src/main/java/org/opends/server/types/AttributeBuilder.java

@@ -16,13 +16,9 @@
 */
package org.opends.server.types;

import java.util.AbstractSet;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;

import org.forgerock.i18n.slf4j.LocalizedLogger;
@@ -38,6 +34,8 @@
import org.opends.server.types.Attribute.RemoveOnceSwitchingAttributes;
import org.opends.server.util.CollectionUtils;

import com.forgerock.opendj.util.SmallSet;

/**
 * This class provides an interface for creating new non-virtual
 * {@link Attribute}s, or "real" attributes.
@@ -96,7 +94,6 @@
@RemoveOnceSwitchingAttributes
public final class AttributeBuilder implements Iterable<ByteString>
{

  private static final LocalizedLogger logger = LocalizedLogger.getLoggerForThisClass();

  /** A real attribute */
@@ -154,9 +151,8 @@
        catch (Exception e)
        {
          logger.traceException(e);
          // We couldn't normalize one of the attribute values. If we
          // can't find a definite match, then we should return
          // "undefined".
          // We could not normalize one of the attribute values.
          // If we cannot find a definite match, then we should return "undefined".
          result = ConditionResult.UNDEFINED;
        }
      }
@@ -233,8 +229,8 @@
        catch (Exception e)
        {
          logger.traceException(e);
          // We couldn't normalize one of the attribute values. If we
          // can't find a definite match, then we should return "undefined".
          // We could not normalize one of the attribute values.
          // If we cannot find a definite match, then we should return "undefined".
          result = ConditionResult.UNDEFINED;
        }
      }
@@ -289,8 +285,8 @@
        {
          logger.traceException(e);

          // We couldn't normalize one of the attribute values. If we
          // can't find a definite match, then we should return "undefined".
          // We could not normalize one of the attribute values.
          // If we cannot find a definite match, then we should return "undefined".
          result = ConditionResult.UNDEFINED;
        }
      }
@@ -335,8 +331,8 @@
        {
          logger.traceException(e);

          // The value couldn't be normalized. If we can't find a
          // definite match, then we should return "undefined".
          // The value could not be normalized.
          // If we cannot find a definite match, then we should return "undefined".
          result = ConditionResult.UNDEFINED;
        }
      }
@@ -344,8 +340,6 @@
      return result;
    }



    @Override
    public final int size()
    {
@@ -375,239 +369,6 @@
  }

  /**
   * A small set of values. This set implementation is optimized to
   * use as little memory as possible in the case where there zero or
   * one elements. In addition, any normalization of elements is
   * delayed until the second element is added (normalization may be
   * triggered by invoking {@link Object#hashCode()} or
   * {@link Object#equals(Object)}.
   *
   * @param <T>
   *          The type of elements to be contained in this small set.
   */
  private static final class SmallSet<T> extends AbstractSet<T>
  {

    /** The set of elements if there are more than one. */
    private LinkedHashSet<T> elements;

    /** The first element. */
    private T firstElement;

    /**
     * Creates a new small set which is initially empty.
     */
    public SmallSet()
    {
      // No implementation required.
    }

    /**
     * Creates a new small set with an initial capacity.
     *
     * @param initialCapacity
     *          The capacity of the set
     */
    public SmallSet(int initialCapacity)
    {
      Reject.ifFalse(initialCapacity >= 0);

      if (initialCapacity > 1)
      {
        elements = new LinkedHashSet<>(initialCapacity);
      }
    }

    @Override
    public boolean add(T e)
    {
      // Special handling for the first value. This avoids potentially
      // expensive normalization.
      if (firstElement == null && elements == null)
      {
        firstElement = e;
        return true;
      }

      // Create the value set if necessary.
      if (elements == null)
      {
        if (firstElement.equals(e))
        {
          return false;
        }

        elements = new LinkedHashSet<>(2);

        // Move the first value into the set.
        elements.add(firstElement);
        firstElement = null;
      }

      return elements.add(e);
    }

    @Override
    public boolean addAll(Collection<? extends T> c)
    {
      if (elements != null)
      {
        return elements.addAll(c);
      }

      if (firstElement != null)
      {
        elements = new LinkedHashSet<>(1 + c.size());
        elements.add(firstElement);
        firstElement = null;
        return elements.addAll(c);
      }

      // Initially empty.
      switch (c.size())
      {
      case 0:
        // Do nothing.
        return false;
      case 1:
        firstElement = c.iterator().next();
        return true;
      default:
        elements = new LinkedHashSet<>(c);
        return true;
      }
    }

    @Override
    public void clear()
    {
      firstElement = null;
      elements = null;
    }

    @Override
    public Iterator<T> iterator()
    {
      if (elements != null)
      {
        return elements.iterator();
      }
      else if (firstElement != null)
      {
        return new Iterator<T>()
        {
          private boolean hasNext = true;

          @Override
          public boolean hasNext()
          {
            return hasNext;
          }

          @Override
          public T next()
          {
            if (!hasNext)
            {
              throw new NoSuchElementException();
            }

            hasNext = false;
            return firstElement;
          }

          @Override
          public void remove()
          {
            throw new UnsupportedOperationException();
          }

        };
      }
      else
      {
        return Collections.<T> emptySet().iterator();
      }
    }

    @Override
    public boolean remove(Object o)
    {
      if (elements != null)
      {
        // Note: if there is one or zero values left we could stop
        // using the set. However, lets assume that if the set
        // was multi-valued before then it may become multi-valued
        // again.
        return elements.remove(o);
      }

      if (firstElement != null && firstElement.equals(o))
      {
        firstElement = null;
        return true;
      }

      return false;
    }

    @Override
    public boolean contains(Object o)
    {
      if (elements != null)
      {
        return elements.contains(o);
      }

      return firstElement != null && firstElement.equals(o);
    }

    /**
     * Sets the initial capacity of this small set. If this small set
     * already contains elements or if its capacity has already been
     * defined then an {@link IllegalStateException} is thrown.
     *
     * @param initialCapacity
     *          The initial capacity of this small set.
     * @throws IllegalStateException
     *           If this small set already contains elements or if its
     *           capacity has already been defined.
     */
    public void setInitialCapacity(int initialCapacity)
        throws IllegalStateException
    {
      Reject.ifFalse(initialCapacity >= 0);

      if (elements != null)
      {
        throw new IllegalStateException();
      }

      if (initialCapacity > 1)
      {
        elements = new LinkedHashSet<>(initialCapacity);
      }
    }

    @Override
    public int size()
    {
      if (elements != null)
      {
        return elements.size();
      }
      else if (firstElement != null)
      {
        return 1;
      }
      else
      {
        return 0;
      }
    }
  }

  /**
   * An attribute value which is lazily normalized.
   * <p>
   * Stores the value in user-provided form and a reference to the associated
@@ -755,7 +516,7 @@
  /** The attribute description for this attribute. */
  private AttributeDescription attributeDescription;
  /** The set of attribute values, which are lazily normalized. */
  private Set<AttributeValue> values = new SmallSet<>();
  private SmallSet<AttributeValue> values = new SmallSet<>();

  /**
   * Creates a new attribute builder with an undefined attribute type
@@ -880,8 +641,7 @@
      // AttributeValue is already present, but the user-provided value may be different
      // There is no direct way to check this, so remove and add to ensure
      // the last user-provided value is recorded
      values.remove(value);
      values.add(value);
      values.addOrReplace(value);
    }
    return isNewValue;
  }