////////////////////////////////////////////////////////////////////////////////
   // MillScript: an Open Spice interpreter and batch website creation tool
   // Copyright (C) 2001-2004 Open World Ltd
   //
   // This file is part of MillScript.
   //
   // MillScript is free software; you can redistribute it and/or modify it under
   // the terms of the GNU General Public License as published by the Free
   // Software Foundation; either version 2 of the License, or (at your option)
  // any later version.
  //
  // MillScript 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 General Public License for
  // more details.
  //
  // You should have received a copy of the GNU General Public License along with
  // MillScript; if not, write to the Free Software Foundation, Inc., 59 Temple
  // Place, Suite 330, Boston, MA  02111-1307  USA
  ////////////////////////////////////////////////////////////////////////////////
  package org.millscript.millscript.functions;
  
  import org.millscript.commons.util.EList;
  import org.millscript.commons.util.EMap;
  import org.millscript.commons.util.IList;
  import org.millscript.commons.util.IMap;
  import org.millscript.commons.util.IMapDefault;
  import org.millscript.commons.util.ListIterator;
  import org.millscript.commons.util.MapIterator;
  import org.millscript.commons.util.defaults.ConstantMapDefault;
  import org.millscript.commons.util.list.ELinkedList;
  import org.millscript.commons.util.map.EBinaryTreeMap;
  import org.millscript.commons.util.map.IEmptyMap;
  import org.millscript.millscript.datatypes.MapAwareTools;
  import org.millscript.millscript.vm.Machine;
  
  /**
   * This class implements the MillScript <code>group</code> function.
   */
  public final class GroupFunction extends Function {
  
      /**
       * Returns an empty map with a chain of empty maps as their default values,
       * up to the required depth. The last map in the chain has a default value
       * of <code>null</code>.
       * <p>
       * For example, if the depth is one, this will return an empty map with a
       * default value of <code>null</code>. If the depth is two, this will
       * return an empty map with a default value of an empty map with a default
       * value of <code>null</code>, etc.
       * </p>
       *
       * @param depth the required depth of map
       * @return  an empty map with a chain of empty maps as their default values
       * of the specified depth
       */
      static IMapDefault makeDefault( final int depth ) {
          IMap< Object, Object > nullMap = new IEmptyMap< Object, Object >();
          for ( int i = 1; i < depth; i++ ) {
              final IMapDefault< Object, Object > mapDefault = new ConstantMapDefault< Object, Object >( nullMap );
              nullMap = new IEmptyMap< Object, Object >();
              nullMap.setDefault( mapDefault );
          }
          return new ConstantMapDefault< Object, Object >( nullMap );
      }
  
      /**
       * Returns the supplied data grouped by the specified field. The supplied
       * data is sorted into a Map, whose keys are all the unique values for the
       * specified field and whose values are the list of data which shares that
       * unique value. This method is used for single level groupings, i.e.
       * grouping by a single field.
       *
       * <p>
       * In MillScript we might refer to this as a map-of-lists.
       * </p>
       *
       * @param   mc      the current machine to perform operations on
       * @param   list    a list of objects, with a map view, to group
       * @param   by      the object/field to group by
       * @return  a map containing the grouped data, where the keys are the
       *          unique values for the specified field and the values a list
       */
      @SuppressWarnings( "unchecked" )
      static EMap group( final Machine mc, final IList list, final Object by ) {
          // This map will hold the grouped data and is the map we will return
          EMap result = new EBinaryTreeMap();
          // We must iterate over all the items in the list of objects
          ListIterator< ? > it = list.iterator( true );
          while ( it.hasNext() ) {
              // Get the next object, we will refer to it as a record
              final Object record = it.nextValue();
              // Get the value associated with the specified field for this
              // record. We will refer to this as the key, as it's a key in the
              // resulting map
              final Object key = MapAwareTools.get( record, by );
              // Check if the key exists in the grouped results
              EList sublist = (EList)result.get( key );
              if ( sublist == null ) {
                 // The key doesn't exist, so we must create it
                 sublist = new ELinkedList();
                 result.insert( key, sublist );
             }
             // Add the record to the end of the specified key
             sublist.addLast( record );
         }
         // Return the grouped data
         return result;
     }
 
     /**
      * Returns the supplied data grouped by the specified fields. This is used
      * where the group will have two or more levels. The list of objects that
      * are to be grouped do not need to be maps, but they must have a map view.
      *
      * @param   mc      the current machine to perform operations on
      * @param   list    a list of objects, with a map view, to group
      * @param   fields  a list of fields to group the list by
      * @param   idx     the index number of the field to group by, which is also
      *                  effectively the current level in the group
      * @param   limit   the number of levels this deep group will have
      * @return  a map containing the grouped data
      */
     @SuppressWarnings( "unchecked" )
     static IMap deepGroup( final Machine mc, final IList list, final IList fields, int idx, final int limit ) {
         // Group the specified list of objects by the field for the current
         // level of the grouping. e.g. on the first call to deepGroup, idx would
         // be zero and we would group the specified list of objects by the first
         // field in the list.
         // NOTE - This is a good indication of the usefullness of maps with
         //        default values, as it allows us to skip checks to see if each
         //        level of a group exists when writing MillScript code.
         EMap map = group( mc, list, fields.get( idx ) );
         // Now we need to iterate through the all the values in this map and
         // group the sublist of data recursively
         MapIterator entries = map.iterator( true );
         // Increment the current field counter, i.e. we are now one level
         // further into the deep grouping
         idx += 1;
         // Have we reached the required depth?
         if ( idx < limit ) {
             // Set the default value for the map at the current level to be a
             // special NullMapWithDefault, with the required depth.
             map.setDefault( GroupFunction.makeDefault( limit - idx ) );
             // Loop over all the keys in the map at this level of the group
             while ( entries.hasNext() ) {
                 // Perform the next level of the deep group on the current
                 // sublist of data
                 map.insert(
                     entries.nextKey(),
                     deepGroup( mc, (IList) entries.currentValue(), fields, idx, limit )
                 );
             }
         }
         return map;
     }
 
     /**
      * @see org.millscript.millscript.functions.Function#apply(org.millscript.millscript.vm.Machine, int)
      */
     @Override
     public void apply( final Machine mc, final int nargs ) {
         if ( nargs <= 0 ) {
             checkNargsGT( mc, 1, nargs );
         } else if ( nargs == 2 ) {
             Object by = mc.popObject();
             IList list = mc.popIList();
             mc.pushObject( group( mc, list, by ) );
         } else if ( nargs >= 3 ) {
             // This list will hold the fields to group by
             EList< Object > fields = new ELinkedList< Object >();
             // Pop each field name off the stack and add it to the front of the
             // list. (arguments to a function are pushed onto the stack, hence
             // you pop them off in reverse order)
             for ( int i = 1; i < nargs; i++ ) {
                 fields.addFirst( mc.popObject() );
             }
             // Pop the ungrouped list of maps off the stack
             IList list = mc.popIList();
             // Push the grouped data onto the stack, i.e. from the script point
             // of  view, return the grouped data
             mc.pushObject( deepGroup( mc, list, fields, 1, nargs ) );
         }
         /* otherwise nargs == 1 and we simply fall thru */
     }
 
 }