package net.sf.saxon.om;

import java.io.Serializable;

import java.util.concurrent.ConcurrentHashMap;

import java.util.concurrent.atomic.AtomicInteger;

import java.util.concurrent.locks.ReentrantLock;

import net.sf.saxon.om.NamespaceConstant;

/**
 * A name pool.
 * If it's known that two qualified names belong to the same pool then:
 *   a) their prefix, localName, namespace, and expandedName are cached values;
 *   b) they are equal if their references are the same.
 *   c) expanded names (local name and namespace) are equal 
 *      if their expanded name references are the same;
 */
@SuppressWarnings("serial")
public class NameCache implements Serializable
{
  /**
   * A name pool key.
   */
  public final static class Key implements Serializable
  {
    /**
     * A key prefix.
     */
    public String prefix;
    
    /**
     * A key local name.
     */
    public String localName;
    
    /**
     * A key namespace.
     */
    public String namespace;

    /**
     * Gets a hash code.
     */
    @Override
    public final int hashCode()
    {
      return localName.hashCode() ^
        Integer.rotateLeft(namespace.hashCode(), 13) ^
        Integer.rotateLeft(prefix.hashCode(), 26);
    }
    
    /**
     * Tests whether this instance is equal to other.
     */
    @Override
    public final boolean equals(Object other)
    {
      Key that = (Key)other;
      
      return this.localName.equals(that.localName) &&
        this.namespace.equals(that.namespace) &&
        this.prefix.equals(that.prefix);
    }
  }

  /**
   * Creates a {@link NameCache} instance.
   */
  public NameCache()
  {
    this.next = null;
    
    getQualifiedName("", "");
    getQualifiedName("xml", NamespaceConstant.XML);
    getQualifiedName("xmlns", NamespaceConstant.XMLNS);
    getQualifiedName("xs", NamespaceConstant.SCHEMA);
    getQualifiedName("xsi", NamespaceConstant.SCHEMA_INSTANCE);
  }

  /**
   * Creates a {@link NameCache} instance.
   * @param next a next name cache.
   */
  public NameCache(NameCache next)
  {
    this.next = next;
    this.namesCount.set(next.namesCount.intValue());
  }

  /**
   * Gets a next name cache.
   * @return a next name cache.
   */
  public final NameCache getNext()
  {
    return next;
  }

  /**
   * Gets a cached name.
   * @param name a name to get cached name for.
   * @return a cached name.
   */
  public final String getName(String name)
  {
    NameCache next = this.next;
    
    while(next != null)
    {
      String result = next.names.get(name);
      
      if (result != null)
      {
        return result;
      }
      
      next = next.next;
    }
    
    return put(names, name, name);
  }
  
  /**
   * Gets a cached value.
   * @param value a value to get cached value for.
   * @param length a limit length for a value to cache.
   * @return a cached value.
   */
  public final String getValue(String value, int length)
  {
    if ((value == null) || (value.length() > length))
    {
      return value;
    }
    
    NameCache next = this.next;
    
    while(next != null)
    {
      String result = next.values.get(value);
      
      if (result != null)
      {
        return result;
      }
      
      next = next.next;
    }
    
    return put(values, value, value);
  }
  
  /**
   * Gets a cached namespace.
   * @param namespace a namespace to get cached namespace for.
   * @return a cached namespace.
   */
  public final String getNamespace(String namespace)
  {
    NameCache next = this.next;
    
    while(next != null)
    {
      String result = next.namespaces.get(namespace);
      
      if (result != null)
      {
        return result;
      }
      
      next = next.next;
    }

    return put(namespaces, namespace, namespace);
  }
  
  /**
   * Suggests a prefix for a namespace.
   * @param namespace a namespace to suggest prefix for.
   * @return a prefix suggestion, if available.
   */
  public final String suggestPrefix(String namespace)
  {
    NameCache next = this.next;
    
    while(next != null)
    {
      String result = next.namespacePrefixes.get(namespace);
      
      if (result != null)
      {
        return result;
      }
      
      next = next.next;
    }

    return namespacePrefixes.get(namespace);
  }
  
  /**
   * Gets a {@link QualifiedName} by a key.
   * Note that key is owned by a caller, and is not cached in the name pool.
   * It can be used for next lookups.
   * @param key a name pool key.
   * @return a qualified name.
   */
  public final QualifiedName getQualifiedName(Key key)
  {
    QualifiedName name;
    NameCache next = this;
    
    while(next != null)
    {
      name = next.qualifiedNames.get(key);
      
      if (name != null)
      {
        return name;
      }
      
      next = next.next;
    }

    String prefix = key.prefix;
    String localName = key.localName;
    String namespace = key.namespace;
    
    // NOTE: it might be better to delegate name pooling to a caller.
    prefix = put(names, prefix, prefix);
    localName = put(names, localName, localName);
    namespace = put(namespaces, namespace, namespace);

    Key newKey = new Key();

    newKey.prefix = "";
    newKey.localName = localName;
    newKey.namespace = namespace;
    
    int id = namesCount.incrementAndGet(); 
    
    if (prefix.length() == 0)
    {
      name = new QualifiedName(localName, namespace, id - 1);
    }
    else
    {
      put(namespacePrefixes, namespace, prefix);
      name = getQualifiedName(newKey);
      newKey.prefix = prefix;
      name =  new QualifiedName(prefix, name, id - 1);
    }
    
    sync.lock();
    
    try
    {
      QualifiedName[] list = namesList;
      
      if (id > list.length)
      {
        QualifiedName[] newList = new QualifiedName[list.length * 3 / 2];
        
        System.arraycopy(list, 0, newList, 0, list.length);
        list = newList;
        namesList = list;
      }

      list[id - 1] = name;
    }
    finally
    {
      sync.unlock();
    }
    
    QualifiedName newName = put(qualifiedNames, newKey, name);
    
    if (newName != name)
    {
      // Try to revert id reservation.
      // It's not a problem when compareAndSet() does not succeed. 
      //
      // Note: we don't need to lock here as:
      //   a) we just want to release the reference;
      //   b) no one with such id can access the list, as it's never returned.
      namesList[id - 1] = null;
      namesCount.compareAndSet(id, id - 1);
      name = newName;
    }
    
    return name;
  }

  /**
   * Gets {@link QualifiedName} instance for a local name and namespace.
   * @param localName a local name.
   * @param namespace a namespace.
   * @return an {@link QualifiedName} instance.
   */
  public final QualifiedName getQualifiedName(
    String localName, 
    String namespace)
  {
    Key key = new Key();
    
    key.prefix = "";
    key.localName = localName;
    key.namespace = namespace;
    
    return getQualifiedName(key);
  }

  /**
   * Gets {@link QualifiedName} instance for a local name and namespace.
   * @param prefix a prefix.
   * @param localName a local name.
   * @param namespace a namespace.
   * @return an {@link QualifiedName} instance.
   */
  public final QualifiedName getQualifiedName(
    String prefix,
    String localName, 
    String namespace)
  {
    Key key = new Key();
    
    key.prefix = prefix;
    key.localName = localName;
    key.namespace = namespace;
    
    return getQualifiedName(key);
  }
  
  /**
   * Gets a qualified name by id.
   * @param id a qualified name id.
   * @return {@link QualifiedName} for the id or null for invalid id.
   * @throws Exception may throw some exception in case of invalid id.
   */
  public final QualifiedName getQualifiedName(int id)
  {
    // This may return null, throw an exception, or even return some phantom 
    // QualifiedName instance in case of invalid id. 
    return namesList[id];
  }
  
  /**
   * Adds a key, value pair in the map if a key is absent in the map.
   * @param <K> a key type.
   * @param <V> a value type.
   * @param map a {@link ConcurrentHashMap} instance.
   * @param key a key instance.
   * @param value a value instance.
   * @return an inserted or existing value.
   */
  private static <K, V> V put(ConcurrentHashMap<K, V> map, K key, V value)
  {
    V existing = map.putIfAbsent(key, value);
    
    return existing == null ? value : existing;
  }

  /**
   * A map of cached names. 
   */
  private final ConcurrentHashMap<String, String> names = 
    new ConcurrentHashMap<String, String>();
  
  /**
   * A map of cached values.
   */
  private final ConcurrentHashMap<String, String> values = 
    new ConcurrentHashMap<String, String>(); 
  
  /**
   * A map of cached namespaces.
   */
  private final ConcurrentHashMap<String, String> namespaces = 
    new ConcurrentHashMap<String, String>();
  
  /**
   * A suggestion of prefixes for namespaces.
   */
  private final ConcurrentHashMap<String, String> namespacePrefixes = 
    new ConcurrentHashMap<String, String>();

  /**
   * A map of cached {@link QualifiedName} instances by name pool key. 
   */
  private final ConcurrentHashMap<Key, QualifiedName> qualifiedNames =
    new ConcurrentHashMap<Key, QualifiedName>();
  
  /**
   * Number of elements used in {@link #namesList}.
   */
  private final AtomicInteger namesCount = new AtomicInteger();
  
  /**
   * Name list array.
   */
  private volatile QualifiedName[] namesList = new QualifiedName[256];
  
  /**
   * Name list write lock.
   */
  private final ReentrantLock sync = new ReentrantLock();
  
  /**
   * A next name cache.
   */
  private final transient NameCache next;
}