// -*- c++ -*-

/*
 * Jakelib2 - General purpose C++ library
 * Copyright (C) 2001 Florian Wolff  (florian@donuz.de)
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * $Id: AbstractMap.h,v 1.4 2003/02/18 17:01:19 alfa Exp $
 */

#ifndef INCLUDE_JAKELIB2_UTIL_ABSTRACTMAP_H
# define INCLUDE_JAKELIB2_UTIL_ABSTRACTMAP_H

#include "Map.h"
#include "AbstractSet.h"
#include "Iterator.h"

namespace jakelib {
  
  namespace lang {
    class Object;
    class Class;
  }

  namespace util {
    class Map;
    class HashMap;
    class Iterator;
 
    /**
     * An abstract implementation of Map to make it easier to create your own
     * implementations. In order to create an unmodifiable Map, subclass
     * AbstractMap and implement the <code>entrySet</code> (usually via an
     * AbstractSet).  To make it modifiable, also implement <code>put</code>,
     * and have <code>entrySet().iterator()</code> support <code>remove</code>.
     * <p>
     *
     * It is recommended that classes which extend this support at least the
     * no-argument constructor, and a constructor which accepts another Map.
     * Further methods in this class may be overridden if you have a more
     * efficient implementation.
     *
     * @author Original author unknown
     * @author Bryce McKinlay
     * @author Eric Blake <ebb9@email.byu.edu>
     * @author Alex Fabijanic (fabijanica@nucorsteel.com)(jakelib2 port)
     * @date January 15, 2003
     * @see Map
     * @see Collection
     * @see HashMap
     * @see LinkedHashMap
     * @see TreeMap
     * @see WeakHashMap
     * @see IdentityHashMap
     * @since 1.2
     * @status updated to 1.4
     */

    class AbstractMap : public jakelib::lang::Object, virtual public jakelib::util::Map 
    {
      friend class BasicAbstractSet;

      /** An "enum" of iterator types. */
      // Package visible for use by subclasses.
      public: static const jint KEYS, VALUES, ENTRIES;

      /**
       * The cache for {@link #keySet()}.
       */
      // Package visible for use by subclasses.
     protected: Set* keys;

      /**
       * The cache for {@link #values()}.
       */
      // Package visible for use by subclasses.
      Collection* values;

      /**
       * The main constructor.
       */
    protected: AbstractMap();

      /**
       * Remove all entries from this Map (optional operation). This default
       * implementation calls entrySet().clear(). NOTE: If the entry set does
       * not permit clearing, then this will fail, too. Subclasses often
       * override this for efficiency.  Your implementation of entrySet() should
       * not call <code>AbstractMap.clear</code> unless you want an infinite loop.
       *
       * @throws UnsupportedOperationException if <code>entrySet().clear()</code>
       *         does not support clearing.
       * @see Set#clear()
       */
    public: virtual void clear();

      /**
       * Create a shallow copy of this Map, no keys or values are copied. The
       * default implementation simply calls <code>super.clone()</code>.
       *
       * @return the shallow clone
       * @throws CloneNotSupportedException if a subclass is not Cloneable
       * @see Cloneable
       * @see Object#clone()
       */
    protected: virtual jakelib::lang::Object* clone(); //throws CloneNotSupportedException

      /**
       * Returns true if this contains a mapping for the given key. This
       * implementation does a linear search, O(n), over the
       * <code>entrySet()</code>, returning <code>true</code> if a match
       * is found, <code>false</code> if the iteration ends. Many subclasses
       * can implement this more efficiently.
       *
       * @param key the key to search for
       * @return true if the map contains the key
       * @throws NullPointerException if key is <code>null</code> but the map
       *         does not permit null keys
       * @see #containsValue(Object)
       */
    public: virtual jboolean containsKey(jakelib::lang::Object* key);

      /**
       * Returns true if this contains at least one mapping with the given value.
       * This implementation does a linear search, O(n), over the
       * <code>entrySet()</code>, returning <code>true</code> if a match
       * is found, <code>false</code> if the iteration ends. A match is
       * defined as <code>(value == null ? v == null : value.equals(v))</code>
       * Subclasses are unlikely to implement this more efficiently.
       *
       * @param value the value to search for
       * @return true if the map contains the value
       * @see #containsKey(Object)
       */
    public: virtual jboolean containsValue(jakelib::lang::Object* value);

      /**
       * Returns a set view of the mappings in this Map.  Each element in the
       * set must be an implementation of Map.Entry.  The set is backed by
       * the map, so that changes in one show up in the other.  Modifications
       * made while an iterator is in progress cause undefined behavior.  If
       * the set supports removal, these methods must be valid:
       * <code>Iterator.remove</code>, <code>Set.remove</code>,
       * <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code>.
       * Element addition is not supported via this set.
       *
       * @return the entry set
       * @see Map.Entry
       */
    public: virtual jakelib::util::Set* entrySet() = 0;

      /**
       * Compares the specified object with this map for equality. Returns
       * <code>true</code> if the other object is a Map with the same mappings,
       * that is,<br>
       * <code>o instanceof Map && entrySet().equals(((Map) o).entrySet();</code>
       *
       * @param o the object to be compared
       * @return true if the object equals this map
       * @see Set#equals(Object)
       */
    public: virtual jboolean equals(jakelib::lang::Object* o);

      /**
       * Returns the value mapped by the given key. Returns <code>null</code> if
       * there is no mapping.  However, in Maps that accept null values, you
       * must rely on <code>containsKey</code> to determine if a mapping exists.
       * This iteration takes linear time, searching entrySet().iterator() of
       * the key.  Many implementations override this method.
       *
       * @param key the key to look up
       * @return the value associated with the key, or null if key not in map
       * @throws NullPointerException if this map does not accept null keys
       * @see #containsKey(Object)
       */
    public: virtual jakelib::lang::Object* get(jakelib::lang::Object* key);

      /**
       * Returns the hash code for this map. As defined in Map, this is the sum
       * of all hashcodes for each Map.Entry object in entrySet, or basically
       * entrySet().hashCode().
       *
       * @return the hash code
       * @see Map.Entry#hashCode()
       * @see Set#hashCode()
       */
    public: virtual jint hashCode();

      /**
       * Returns true if the map contains no mappings. This is implemented by
       * <code>size() == 0</code>.
       *
       * @return true if the map is empty
       * @see #size()
       */
    public: virtual jboolean isEmpty();

      /**
       * Returns a set view of this map's keys. The set is backed by the map,
       * so changes in one show up in the other. Modifications while an iteration
       * is in progress produce undefined behavior. The set supports removal
       * if entrySet() does, but does not support element addition.
       * <p>
       *
       * This implementation creates an AbstractSet, where the iterator wraps
       * the entrySet iterator, size defers to the Map's size, and contains
       * defers to the Map's containsKey. The set is created on first use, and
       * returned on subsequent uses, although since no synchronization occurs,
       * there is a slight possibility of creating two sets.
       *
       * @return a Set view of the keys
       * @see Set#iterator()
       * @see #size()
       * @see #containsKey(Object)
       * @see #values()
       */
    public: virtual jakelib::util::Set* keySet();

      /**
       * Associates the given key to the given value (optional operation). If the
       * map already contains the key, its value is replaced. This implementation
       * simply throws an UnsupportedOperationException. Be aware that in a map
       * that permits <code>null</code> values, a null return does not always
       * imply that the mapping was created.
       *
       * @param key the key to map
       * @param value the value to be mapped
       * @return the previous value of the key, or null if there was no mapping
       * @throws UnsupportedOperationException if the operation is not supported
       * @throws ClassCastException if the key or value is of the wrong type
       * @throws IllegalArgumentException if something about this key or value
       *         prevents it from existing in this map
       * @throws NullPointerException if the map forbids null keys or values
       * @see #containsKey(Object)
       */
    public: virtual jakelib::lang::Object* put(jakelib::lang::Object* key, jakelib::lang::Object* value);

      /**
       * Copies all entries of the given map to this one (optional operation). If
       * the map already contains a key, its value is replaced. This implementation
       * simply iterates over the map's entrySet(), calling <code>put</code>,
       * so it is not supported if puts are not.
       *
       * @param m the mapping to load into this map
       * @throws UnsupportedOperationException if the operation is not supported
       * @throws ClassCastException if a key or value is of the wrong type
       * @throws IllegalArgumentException if something about a key or value
       *         prevents it from existing in this map
       * @throws NullPointerException if the map forbids null keys or values, or
       *         if <code>m</code> is null.
       * @see #put(Object, Object)
       */
    public: virtual void putAll(jakelib::util::Map* m);

      /**
       * Removes the mapping for this key if present (optional operation). This
       * implementation iterates over the entrySet searching for a matching
       * key, at which point it calls the iterator's <code>remove</code> method.
       * It returns the result of <code>getValue()</code> on the entry, if found,
       * or null if no entry is found. Note that maps which permit null values
       * may also return null if the key was removed.  If the entrySet does not
       * support removal, this will also fail. This is O(n), so many
       * implementations override it for efficiency.
       *
       * @param key the key to remove
       * @return the value the key mapped to, or null if not present
       * @throws UnsupportedOperationException if deletion is unsupported
       * @see Iterator#remove()
       */
    public: virtual jakelib::lang::Object* remove(jakelib::lang::Object* key);

      /**
       * Returns the number of key-value mappings in the map. If there are more
       * than Integer.MAX_VALUE mappings, return Integer.MAX_VALUE. This is
       * implemented as <code>entrySet().size()</code>.
       *
       * @return the number of mappings
       * @see Set#size()
       */
    public: jint size();

      /**
       * Returns a String representation of this map. This is a listing of the
       * map entries (which are specified in Map.Entry as being
       * <code>getKey() + "=" + getValue()</code>), separated by a comma and
       * space (", "), and surrounded by braces ('{' and '}'). This implementation
       * uses a StringBuffer and iterates over the entrySet to build the String.
       * Note that this can fail with an exception if underlying keys or
       * values complete abruptly in toString().
       *
       * @return a String representation
       * @see Map.Entry#toString()
       */
    public: virtual jakelib::lang::String* toString();

      /**
       * Returns a collection or bag view of this map's values. The collection
       * is backed by the map, so changes in one show up in the other.
       * Modifications while an iteration is in progress produce undefined
       * behavior. The collection supports removal if entrySet() does, but
       * does not support element addition.
       * <p>
       *
       * This implementation creates an AbstractCollection, where the iterator
       * wraps the entrySet iterator, size defers to the Map's size, and contains
       * defers to the Map's containsValue. The collection is created on first
       * use, and returned on subsequent uses, although since no synchronization
       * occurs, there is a slight possibility of creating two collections.
       *
       * @return a Collection view of the values
       * @see Collection#iterator()
       * @see #size()
       * @see #containsValue(Object)
       * @see #keySet()
       */
      //AlFa: changed values()=>getValues() (can't have same member function and variable name in C++)
      //public: jakelib::util::Collection* values(); 
    public: virtual jakelib::util::Collection* getValues();

      /**
       * Compare two objects according to Collection semantics.
       *
       * @param o1 the first object
       * @param o2 the second object
       * @return o1 == null ? o2 == null : o1.equals(o2)
       */
      // Package visible for use throughout java.util.
      // It may be inlined since it is final.
      static jboolean equals(jakelib::lang::Object* o1, jakelib::lang::Object* o2);

      /**
       * Hash an object according to Collection semantics.
       *
       * @param o the object to hash
       * @return o1 == null ? 0 : o1.hashCode()
       */
      // Package visible for use throughout java.util.
      // It may be inlined since it is final.
      static jint hashCode(jakelib::lang::Object* o);

      /**
       * A class which implements Map.Entry. It is shared by HashMap, TreeMap,
       * Hashtable, and Collections. It is not specified by the JDK, but makes
       * life much easier.
       *
       * @author Jon Zeppieri
       * @author Eric Blake <ebb9@email.byu.edu>
       */
      class BasicMapEntry : public jakelib::util::Map::Entry
      {	// XXX - FIXME Use fully qualified implements as gcj 3.1 workaround.

        friend class jakelib::util::HashMap;
        /**
         * The key. Package visible for direct manipulation.
         */
        public: jakelib::lang::Object* key;

        /**
         * The value. Package visible for direct manipulation.
         */
        public: jakelib::lang::Object* value;

        /**
         * Basic constructor initializes the fields.
         * @param newKey the key
         * @param newValue the value
         */
        protected: BasicMapEntry(jakelib::lang::Object* newKey, jakelib::lang::Object* newValue);

        /**
         * Compares the specified object with this entry. Returns true only if
         * the object is a mapping of identical key and value. In other words,
         * this must be:
         * 
         <pre>(o instanceof Map.Entry) &&
         (getKey() == null ? ((HashMap) o).getKey() == null
         : getKey().equals(((HashMap) o).getKey())) &&
         (getValue() == null ? ((HashMap) o).getValue() == null
         : getValue().equals(((HashMap) o).getValue()))</pre>
         *
         * @param o the object to compare
         *
         * @return <code>true</code> if it is equal
         */
      public: jboolean equals(jakelib::lang::Object* o);

        /**
         * Get the key corresponding to this entry.
         *
         * @return the key
         */
      public: jakelib::lang::Object* getKey();

        /**
         * Get the value corresponding to this entry. If you already called
         * Iterator.remove(), the behavior undefined, but in this case it works.
         *
         * @return the value
         */
      public: jakelib::lang::Object* getValue();

        /**
         * Returns the hash code of the entry.  This is defined as the exclusive-or
         * of the hashcodes of the key and value (using 0 for null). In other
         * words, this must be:
         * 
         <pre>(getKey() == null ? 0 : getKey().hashCode())
         ^ (getValue() == null ? 0 : getValue().hashCode())</pre>
         *
         * @return the hash code
         */
      public: jint hashCode();

        /**
         * Replaces the value with the specified object. This writes through
         * to the map, unless you have already called Iterator.remove(). It
         * may be overridden to restrict a null value.
         *
         * @param newVal the new value to store
         * @return the old value
         * @throws NullPointerException if the map forbids null values
         */
      public: jakelib::lang::Object* setValue(jakelib::lang::Object* newVal);

        /**
         * This provides a string representation of the entry. It is of the form
         * "key=value", where string concatenation is used on key and value.
         *
         * @return the string representation
         */
      public: jakelib::lang::String* toString();

        JAKELIB_DECLARE_CLASS(BasicMapEntry);
      }; // class BasicMapEntry

      JAKELIB_DECLARE_CLASS(AbstractMap);
    };//class AbstractMap

  }
}
#endif
