package nxm.sys.lib;

import java.util.Arrays; // Used for Array.sort
import java.util.Collections;
import java.util.Map;    // Used for Map.Entry

import nxm.sys.inc.Indexable;
import nxm.sys.inc.Keyable;

/** A class to handle a Keyed Vector that can be accessed by index or key name. Unlike a table, a
    KeyVector permits duplicate keys. Like most Java collections, the KeyVector is zero based
    (0..N-1), although some classes (like {@link Args}) treat it as if it was one-based with a
    special value stored in the 0th slot. <br>
    <br>
    This class pre-dates most of the Java collections that were added in Java 1.1 and Java 1.2.
    KeyVector is currently implemented using insertion-order arrays of keys and values. This
    provides O(1) access to all items accessed by index, however it results in O(N) performance for
    all items accessed by key. As a result, use of KeyVector should be limited to small collections
    when key-access is to be used.

    @author  Jeff Schoen
 */
public class KeyVector extends Object implements Keyable, Indexable {
  /** The default size of new KeyVectors. */
  private static final int DEFAULT_SIZE = 64; // JC4: I picked 64 because it matches size_expand

  // JC4: the following were deprecated so that we can look into using a more efficient way of implementing findIndex(..)
  /** private since NeXtMidas 3.3.2, was deprecated in 2.6.0: Use {@link #put(int,String,Object)} or {@link #getKey(int)}. */
  private String keys[];

  /** private since NeXtMidas 3.3.2, was deprecated in 2.6.0: Use {@link #put(int,String,Object)} or {@link #get(int)}. */
  private Object values[];

  /** private since NeXtMidas 3.3.2, was deprecated in 2.6.0: Use {@link #size()}. */
  private int size=0;

  private int size_expand=64;

  private int lastGet=0; // since the same get is often performed over and over
  private int lastPut=0; // JC4: 23JUL06 also get-after-put and put-after-put

  /** Creates a new instance with the default initial size. */
  public KeyVector () {
    this(DEFAULT_SIZE);
  }

  /** Creates a new instance with the given initial size.
      @param alloc The initial size to allocate.
   */
  public KeyVector (int alloc) {
    keys   = new String[alloc];
    values = new Object[alloc];
  }

  /** Gets the size of the KeyVector.
      @return number of elements in the KeyVector (0 if empty).
   */
  public int getSize() { return size; }

  /** Gets the size of the KeyVector.
      @return number of elements in the KeyVector (0 if empty).
   */
  public int size() { return size; }

  /** Makes a copy of the KeyVector.
      @return A shallow copy of the KeyVector.
   */
  public synchronized KeyVector copy() {
    KeyVector kv = new KeyVector();
    // JC4: Note that copying an array is typically 5x faster than using clone().
    kv.keys        = new String[keys.length];     System.arraycopy(keys,   0, kv.keys,   0, size);
    kv.values      = new Object[values.length];   System.arraycopy(values, 0, kv.values, 0, size);
    kv.size        = size;
    kv.size_expand = size_expand;
    kv.lastGet     = lastGet;
    kv.lastPut     = lastPut;
    return kv;
  }

  /** Sorts the entries in the key vector by key. In cases where there are duplicate keys, their
      mutual ordering is undefined.
      @param reverse Set this to true to reverse the sort order.
      @since NeXtMidas 2.3.0
   */
  public synchronized void sortByKey (boolean reverse) {
    // JC4: I'd prefer not to allocate all of these extra objects just for a simple sort,
    // but I don't think there is a good alternative when duplicate keys are factored in.
    Map.Entry<String,Object>[] array = copy().getEntries();

    if (reverse) Arrays.sort(array, Collections.reverseOrder());
    else         Arrays.sort(array);

    clear();
    for (int i = 0; i < array.length; i++) {
      add(array[i]);
    }
  }

  /** Creates a KeyVal array for this instance. */
  synchronized Map.Entry<String,Object>[] getEntries () { // package-private to allow for future use in Table.entrySet()
    KeyVal[] array = new KeyVal[size];

    for (int i = 0; i < size; i++) {
      array[i] = new KeyVal(this, i);
    }
    return array;
  }

  /** Add an entry by name. This ALWAYS adds the key and value to the END of the KeyVector even if
      the key matches an existing key (i.e. this may add duplicate entries).
      @param key   The key for the value.
      @param value The value to add.
   */
  public synchronized void add (String key, Object value) {
    if (size >= keys.length) expand(size_expand);
    keys[size] = key;
    values[size] = value;
    size++;
  }

  /** Add an entry by name. This ALWAYS adds the key and value to the END of the KeyVector even if
      the key matches an existing key (i.e. this may add duplicate entries).
      @param e The entry to add (note that the key muse be a String).
   */
  private final void add (Map.Entry<String,Object> e) {
    add(e.getKey(), e.getValue());
  }

  /** Add all entries in the given Keyable to the end of this KeyVector. Duplicate entries are
      preserved. This is optimized for merging two KeyVector's together.
      @param keyable The keyable instance.
      @since NeXtMidas 2.7.1
   */
  public synchronized void merge (Keyable keyable) {
    if (keyable instanceof KeyVector) {
      KeyVector kv = (KeyVector)keyable;
      int len = kv.size();
      expand(len);
      System.arraycopy(kv.keys,   0, keys,   size, len); // use fast copy
      System.arraycopy(kv.values, 0, values, size, len); // use fast copy
      size += len;
    }
    else {
      String[] newKeys = keyable.getKeys();
      int len = newKeys.length;
      expand(len);
      System.arraycopy(newKeys, 0, keys, size, len); // can use fast copy for keys
      for (int i = 0; i < len; i++) {
        values[size++] = keyable.getKey(newKeys[i]);
      }
    }
  }

  /** Add/replace an entry by index and name. If there are duplicates of <code>key</code> already
      in the KeyVector, this will replace the value of ONE of them with <code>value</code>, which
      one it chooses to replace is undefined.
      @param key   The key for the value.
      @param value The value to add.
      @return Since 3.3.3: the previous value associated with key, or null if there was no mapping for key. (A null
              return can also indicate that the map previously associated null with key)
   */
  public Object put (String key, Object value) {
    int index = findKey(key);
    Object prevValue = get(index); // since 3.3.3 for Bug 2699
    if (index < 0) {
      add(key,value);
      lastPut = size-1;
    } else {
      set(index,key,value);
      lastPut = index;
    }
    return prevValue; // since 3.3.3 for Bug 2699
  }

  /** Add/replace an entry by index and name. Unlike {@link #set(int,String,Object)} this
      will add any extra spaces if the index is larger than the current size.
      @param index The index to add to (0..N).
      @param key   The key for the value.
      @param value The value to add.
   */
  public void put (int index, String key, Object value) {
    if (index<0) return;
    for (int i=size; i<=index; i++) add("",null);
    set(index,key,value);
  }

  /** Get the key name by index.
      @param index The index into the KeyVector (0..N-1).
      @return The key at the given index.
   */
  public String getKey (int index) {
    return keys[index];
  }

  /** Get the key value by index.
      @param index The index into the KeyVector (0..N-1).
      @return The value at the given index or null if index is out of range
   */
  public Object get (int index) {
    if (index<0||index>=size) return null;
    return values[index];
  }

  /** Get the key value by name. If there are duplicates of <code>key</code> already in the KeyVector,
      this will return the value associated with ONE of them, which one it chooses is undefined.
      @param key   The key to look up.
      @return The associated value or <code>null</code> if not found.
   */
  public Object get (String key) {
    return get(findKey(key));
  }

  /** @since 3.5.2 to implement Indexable interface */
  @Override
  public Object getIndex (int index) {
    return get(index);
  }

  /** @since 3.5.2 to implement Indexable interface */
  @Override
  public void setIndex (int index, Object value) {
    set(index, value);
  }

  /** Replaces the value at the given index with a new value (the key at that index remains
      unaltered). This is a NOOP if the index is invalid.
      @param index The index to change the value of (0..N).
      @param value The replacement value.
   */
  public void set (int index, Object value) {
    if (index<0||index>=size) return;
    values[index] = value;
  }

  /** Add/replace an entry by index and name. Unlike {@link #put(int,String,Object)} this
      will NOT add any extra spaces if the index is larger than the current size. It will
      simply ignore this put if the index is invalid.
      @param index The index to add to (0..N).
      @param key   The key for the value.
      @param value The value to add.
   */
  public void set (int index, String key, Object value) {
    if (index<0||index>=size) return;
    keys[index] = key;
    values[index] = value;
  }

  /** Set the key value by name. Unlike put this will NOT add a new value, it will only
      alter an existing value. In cases where there are duplicates of <code>key</code> in the
      KeyVector, only ONE of them will be updated; which one is chosen is undefined.
      @param key   The key name.
      @param value The new value.
   */
  public void set (String key, Object value) {
    set(findKey(key),key,value);
  }

  /** Remove the key value by index and shifts all subsequent values down by one. If the index is
      invalid this is a NOOP.
      @param index The index to remove (0..N).
   */
  public synchronized void remove (int index) {
    if (index<0||index>=size) return;
    size--;
    for (int i=index; i<size; i++) {
      keys[i] = keys[i+1];
      values[i] = values[i+1];
    }
    keys[size]=null;
    values[size]=null;
  }

  /** Remove the key value by name. In cases where there are duplicates of <code>key</code> in the
      KeyVector, only ONE of them will be removed; which one is chosen is undefined.
      @param key   The key name.
   */
  public synchronized void remove (String key) {
    remove(findKey(key));
  }

  /** Clear out the KeyVector. */
  public synchronized void clear () {
    for (int i=0; i<size; i++) {
      keys[i]=null;
      values[i]=null;
    }
    size=0;
  }

  /** Find the key's index. This is identical to <code>findKey(key)</code>.
      @param key The key to find.
      @return The index of the given key or -1 if not found.
   */
  public int find (String key) {
    return findKey(key);
  }

  /** Find the key's index. In cases where there are duplicates of <code>key</code> in the KeyVector,
      the index for ONE of them will be returned; which one is chosen is undefined.
      @param key The key to find.
      @return The index of the given key or -1 if not found.
   */
  public int findKey (String key) {
    int index = -1;
    if (key==null || key.isEmpty() || keys==null || keys.length==0) return index;  // since 3.5.0 (Bug 2792)
    if (lastGet<size && key.equals(keys[lastGet])) { index = lastGet; }
    if (lastPut<size && key.equals(keys[lastPut])) { index = lastPut; }

    for (int i=0; i < size; i++) {
      if (key.equals(keys[i])) {
        lastGet = index = i;
        break;
      }
    }
    return index;
  }

  /** Find the value's index. In cases where there are duplicates of <code>value</code> in the KeyVector,
      the index for ONE of them will be returned; which one is chosen is undefined. Note that this
      checks for the value using an identity (<code>==</code>) check rather than an equality
      (<code>.equals(..)</code>) check.
      @param value The value to find.
      @return The index of the given value or -1 if not found.
   */
  public int findValue (Object value) {
    for (int i=0; i<=size; i++) {
      if (value==values[i]) return i;
    }
    return -1;
  }

  /** Rename a key. In cases where there are duplicates of <code>key</code> in the KeyVector,
      the name for ONE of them will be changed; which one is chosen is undefined. This does
      nothing if <code>key</code> is not found.
      @param key The key to find.
      @param newKey The replacement key.
   */
  public void rename (String key, String newKey) {
    int index = findKey(key);
    if (index >= 0) { keys[index]=newKey; }
  }

  /** package-private since NeXtMidas 3.3.2, was deprecated in 2.6.0: This method should be private. */
  synchronized void expand (int expand) {
    int alloc = keys.length + expand;
    String[] nkeys   = new String[alloc];
    Object[] nvalues = new Object[alloc];
    System.arraycopy(keys,   0, nkeys,   0, size);
    System.arraycopy(values, 0, nvalues, 0, size);
    keys   = nkeys;
    values = nvalues;
  }

  /** Get the keys in the KeyVector.
      @return The keys in a String array<br><br>
      NOTE: As of NeXtMidas 2.7.1, this not include "SIZE" and "GETSIZE"
   */
  public String[] getKeys() {
    int num = 0;
    for (int i = 0; i < size; i++) {
      if (keys[i] != null) num++;
    }
    String[] array = new String[num];

    /* Bug 1734 - 28 Jan 09 - JWB - Removed "SIZE" and "GETSIZE" from list of keys*/

    if (num == size) {
      // No null values, use fast array copy (this is extremely common)
      System.arraycopy(keys, 0, array, 0, size);
    } else {
      // Found some nulls, only include non-null values in the output array
      int j = 0;
      for (int i = 0; i < size; i++) {
        if (keys[i] != null) array[j++] = keys[i];
      }
    }
    return array;
  }

  /** Gets a named key. This is the same as {@link #get(String)} except if the key
      is one of four special values:
      <pre>
        "GETPREV"  - returns NULL (added to match Table functionality)
        "GETKEYS"  - same as {@link #getKeys()}
        "GETLIST"  - same as {@link #getKeyList()}
        "GETSIZE"  - same as {@link #size()}
      </pre>

      This method is intended for Macro users. API users
      should call get(String) or the above methods directly.<br><br>

      @param key  The key identifying the value.
      @return The value associated with the key of <code>null</code> if not found.
   */
  public Object getKey (String key) {
    if (key.equals("SIZE")) {
      Shell.deprecate("KeyVector.getKey('SIZE') is deprecated since NeXtMidas 2.7.1, use getKey('GETSIZE')");
      return size();
    }
    else if (key.equals("GETSIZE")) return size();
    else if (key.equals("GETPREV")) return null;
    else if (key.equals("GETKEYS")) return getKeys();
    else if (key.equals("GETLIST")) return getKeyList();
    else                            return get(key);
  }

  public Object setKey (String key, Object value) {
    put(key,value);
    return value;	// always succeeds
  }

  /** Return menu ready list of keys. This is the same as <code>getKeyList(0,size)</code>.
      @return The comma-separated list of keys.
   */
  public String getKeyList() {
    return getKeyList(0,size);
  }

  /** Return menu ready list of keys.
      @param i1 The start index (inclusive).
      @param i2 The end index (exclusive).
      @return The comma-separated list of keys.
   */
  public String getKeyList (int i1, int i2) {
    String list="";
    for (int i=i1; i<i2; i++) {
      if (list.length()>0) list += ",";
      if (keys[i]!=null) list += keys[i];
    }
    return list;
  }

  /** Dump the contents of Vector to {@link System#out}. This is only used for debugging purposes. */
  public void dump() {
    for (int i=0; i<size; i++) {
      System.out.println("Index="+i+" Key="+keys[i]+" Value="+values[i]);
    }
  }

  public String toString() {
    StringBuffer sb = new StringBuffer(1024);
    // Since 3.5.3 Bug 2876 pass in modified default Table flags (escape sequences disabled), rather than boolean
    int flagsPlusDisableEscape = Table.getDefaultFlagsInt() | Table.DISABLE_ESCAPE_SEQUENCES;
    Table.toStringBuffer(this,sb,flagsPlusDisableEscape);
    return sb.toString();
  }

  /** Converts the KeyVector representation of a given string parameter
      @param str string to be converted to KeyVector
      @return KeyVector representation of original string
   */
  public static KeyVector fromString (String str) {
    Table t = new Table(Table.KV);
    t.fromBytes(str.getBytes());
    return (KeyVector)t.getCore();
  }

  /** Creates an iterator that iterates over the elements in this table.
      @return The iterator used for iterating over the keys and values in this KeyVector.
   */
  public Iterator iterator() {
    return new Iterator(this);
  }

  /** An iterator used by the {@link Table} class. */
  public class Iterator {
    /** KeyVector to be iterated*/
    public KeyVector kv;
    /** keys of KeyVector */
    public String[] keys;
    /** values of KeyVector */
    public Object[] values;
    /** current offset */
    public int offset;
    /** number of KeyVector entries */
    public int size;
    /** current key */
    public String key;
    /** current value */
    public Object value;

    /** Iterator Constructor
        @param kv KeyVector to be iterated
     */
    public Iterator (KeyVector kv) {
      this.kv = kv;
      size   = kv.size();
      keys   = new String[size];
      values = new Object[size];
      offset = 0;
      System.arraycopy(kv.keys,   0, keys,   0, size);
      System.arraycopy(kv.values, 0, values, 0, size);
    }
    /** Determines whether or not there are more key-value pairs left
        @return Whether there are remaining key-value pairs
     */
    public boolean hasNext() {
      return offset<size;
    }
    /** Determines whether or not there are more key-value pairs left,
        and if there are, the next iteration gets called.
        @return Whether there are remaining key-value pairs
     */
    public boolean getNext() {
      if (offset>=size) return false;
      next();
      return true;
    }
    /** Runs the next iteration of key-value pairs
        @return key being iterated
     */
    public Object next() {
      key = keys[offset];
      value = values[offset];
      offset++;
      return key;
    }
    /** Removes the current key-value pair */
    public void remove() {
      kv.remove(key);
    }
  }

  /** Used when sorting, this should ALWAYS be private, however we may consider making it
      available from a public method via the Map.Entry interface.
   */
  private static class KeyVal implements Comparable<Object>, Map.Entry<String,Object> {
    final KeyVector kv;
    final int       index;

    KeyVal (KeyVector kv, int index) { // package-private internal use only
      this.kv    = kv;
      this.index = index;
    }

    public String getKey ()   { return kv.getKey(index); }
    public Object getValue () { return kv.get(index);    }
    public String toString () { return ""+getKey()+"="+getValue(); }

    public Object setValue (Object v) {
      Object old = getValue();
      kv.set(index, v);
      return old;
    }

    public int compareTo (Object obj) { // implements Comparable, sorts on key
      KeyVal other = (KeyVal)obj;

      Object k1 = this.getKey();
      Object k2 = other.getKey();

      if (k1 == null) return (k2 == null)? 0 : -1;
      if (k2 == null) return 1;

      String s1 = k1.toString();
      String s2 = k2.toString();

      return s1.compareTo(s2);
    }

    public boolean equals (Object obj) { // implementation copied from docs for Map.Entry
      if (!(obj instanceof Map.Entry)) return false;

      KeyVal    e1 = this;
      Map.Entry<?,?> e2 = (Map.Entry<?,?>)obj;

      return (e1.getKey()==null ?
              e2.getKey()==null : e1.getKey().equals(e2.getKey()))  &&
             (e1.getValue()==null ?
              e2.getValue()==null : e1.getValue().equals(e2.getValue()));
    }

    public int hashCode () { // implementation copied from docs for Map.Entry
      KeyVal e = this;
      return (e.getKey()==null   ? 0 : e.getKey().hashCode()) ^
             (e.getValue()==null ? 0 : e.getValue().hashCode());
    }
  }
}
