mnj/lua/TableLib.java

   1 /*  $Header: //info.ravenbrook.com/project/jili/version/1.1/code/mnj/lua/TableLib.java#1 $
   2  * Copyright (c) 2006 Nokia Corporation and/or its subsidiary(-ies).
   3  * All rights reserved.
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining
   6  * a copy of this software and associated documentation files (the
   7  * "Software"), to deal in the Software without restriction, including
   8  * without limitation the rights to use, copy, modify, merge, publish,
   9  * distribute, sublicense, and/or sell copies of the Software, and to
  10  * permit persons to whom the Software is furnished to do so, subject
  11  * to the following conditions:
  12  *
  13  * The above copyright notice and this permission notice shall be
  14  * included in all copies or substantial portions of the Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  17  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  18  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  19  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR
  20  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
  21  * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  22  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  23  */
  24
  25 package mnj.lua;
  26
  27 import java.util.Enumeration;
  28
  29 /**
  30  * Contains Lua's table library.
  31  * The library can be opened using the {@link #open} method.
  32  */
  33 public final class TableLib extends LuaJavaCallback
  34 {
  35   // Each function in the table library corresponds to an instance of
  36   // this class which is associated (the 'which' member) with an integer
  37   // which is unique within this class.  They are taken from the following
  38   // set.
  39   private static final int CONCAT = 1;
  40   private static final int INSERT = 2;
  41   private static final int MAXN = 3;
  42   private static final int REMOVE = 4;
  43   private static final int SORT = 5;
  44
  45   /**
  46    * Which library function this object represents.  This value should
  47    * be one of the "enums" defined in the class.
  48    */
  49   private int which;
  50
  51   /** Constructs instance, filling in the 'which' member. */
  52   private TableLib(int which)
  53   {
  54     this.which = which;
  55   }
  56
  57   /**
  58    * Implements all of the functions in the Lua table library.  Do not
  59    * call directly.
  60    * @param L  the Lua state in which to execute.
  61    * @return number of returned parameters, as per convention.
  62    */
  63   public int luaFunction(Lua L)
  64   {
  65     switch (which)
  66     {
  67       case CONCAT:
  68         return concat(L);
  69       case INSERT:
  70         return insert(L);
  71       case MAXN:
  72         return maxn(L);
  73       case REMOVE:
  74         return remove(L);
  75       case SORT:
  76         return sort(L);
  77     }
  78     return 0;
  79   }
  80
  81   /**
  82    * Opens the string library into the given Lua state.  This registers
  83    * the symbols of the string library in a newly created table called
  84    * "string".
  85    * @param L  The Lua state into which to open.
  86    */
  87   public static void open(Lua L)
  88   {
  89     L.register("table");
  90
  91     r(L, "concat", CONCAT);
  92     r(L, "insert", INSERT);
  93     r(L, "maxn", MAXN);
  94     r(L, "remove", REMOVE);
  95     r(L, "sort", SORT);
  96   }
  97
  98   /** Register a function. */
  99   private static void r(Lua L, String name, int which)
 100   {
 101     TableLib f = new TableLib(which);
 102     Object lib = L.getGlobal("table");
 103     L.setField(lib, name, f);
 104   }
 105
 106   /** Implements table.concat. */
 107   private static int concat(Lua L)
 108   {
 109     String sep = L.optString(2, "");
 110     L.checkType(1, Lua.TTABLE);
 111     int i = L.optInt(3, 1);
 112     int last = L.optInt(4, Lua.objLen(L.value(1)));
 113     StringBuffer b = new StringBuffer();
 114     Object t = L.value(1);
 115     for (; i <= last; ++i)
 116     {
 117       Object v = Lua.rawGetI(t, i);
 118       L.argCheck(Lua.isString(v), 1, "table contains non-strings");
 119       b.append(L.toString(v));
 120       if (i != last)
 121         b.append(L.toString(sep));
 122     }
 123     L.pushString(b.toString());
 124     return 1;
 125   }
 126
 127   /** Implements table.insert. */
 128   private static int insert(Lua L)
 129   {
 130     int e = aux_getn(L, 1) + 1; // first empty element
 131     int pos;    // where to insert new element
 132     Object t = L.value(1);
 133     switch (L.getTop())
 134     {
 135       case 2:   // called with only 2 arguments
 136         pos = e;        // insert new element at the end
 137         break;
 138
 139       case 3:
 140         {
 141           int i;
 142           pos = L.checkInt(2);  // 2nd argument is the position
 143           if (pos > e)
 144             e = pos;    // grow array if necessary
 145           for (i = e; i > pos; --i)     // move up elements
 146           {
 147             // t[i] = t[i-1]
 148             L.rawSetI(t, i, Lua.rawGetI(t, i-1));
 149           }
 150         }
 151         break;
 152
 153       default:
 154         return L.error("wrong number of arguments to 'insert'");
 155     }
 156     L.rawSetI(t, pos, L.value(-1));     // t[pos] = v
 157     return 0;
 158   }
 159
 160   /** Implements table.maxn. */
 161   private static int maxn(Lua L)
 162   {
 163     double max = 0;
 164     L.checkType(1, Lua.TTABLE);
 165     LuaTable t = (LuaTable)L.value(1);
 166     Enumeration<Object> e = t.keys();
 167     while (e.hasMoreElements())
 168     {
 169       Object o = e.nextElement();
 170       if (Lua.type(o) == Lua.TNUMBER)
 171       {
 172         double v = L.toNumber(o);
 173         if (v > max)
 174           max = v;
 175       }
 176     }
 177     L.pushNumber(max);
 178     return 1;
 179   }
 180
 181   /** Implements table.remove. */
 182   private static int remove(Lua L)
 183   {
 184     int e = aux_getn(L, 1);
 185     int pos = L.optInt(2, e);
 186     if (e == 0)
 187       return 0;         // table is 'empty'
 188     Object t = L.value(1);
 189     Object o = Lua.rawGetI(t, pos);       // result = t[pos]
 190     for ( ;pos<e; ++pos)
 191     {
 192       L.rawSetI(t, pos, Lua.rawGetI(t, pos+1));   // t[pos] = t[pos+1]
 193     }
 194     L.rawSetI(t, e, Lua.NIL);   // t[e] = nil
 195     L.push(o);
 196     return 1;
 197   }
 198
 199   /** Implements table.sort. */
 200   private static int sort(Lua L)
 201   {
 202     int n = aux_getn(L, 1);
 203     if (!L.isNoneOrNil(2))      // is there a 2nd argument?
 204       L.checkType(2, Lua.TFUNCTION);
 205     L.setTop(2);        // make sure there is two arguments
 206     auxsort(L, 1, n);
 207     return 0;
 208   }
 209
 210   static void auxsort(Lua L, int l, int u)
 211   {
 212     Object t = L.value(1);
 213     while (l < u)       // for tail recursion
 214     {
 215       int i;
 216       int j;
 217       // sort elements a[l], a[l+u/2], and a[u]
 218       Object o1 = Lua.rawGetI(t, l);
 219       Object o2 = Lua.rawGetI(t, u);
 220       if (sort_comp(L, o2, o1)) // a[u] < a[l]?
 221       {
 222         L.rawSetI(t, l, o2);
 223         L.rawSetI(t, u, o1);
 224       }
 225       if (u-l == 1)
 226         break;  // only 2 elements
 227       i = (l+u)/2;
 228       o1 = Lua.rawGetI(t, i);
 229       o2 = Lua.rawGetI(t, l);
 230       if (sort_comp(L, o1, o2)) // a[i]<a[l]?
 231       {
 232         L.rawSetI(t, i, o2);
 233         L.rawSetI(t, l, o1);
 234       }
 235       else
 236       {
 237         o2 = Lua.rawGetI(t, u);
 238         if (sort_comp(L, o2, o1))       // a[u]<a[i]?
 239         {
 240           L.rawSetI(t, i, o2);
 241           L.rawSetI(t, u, o1);
 242         }
 243       }
 244       if (u-l == 2)
 245         break;  // only 3 elements
 246       final Object p = Lua.rawGetI(t, i); // Pivot
 247       o2 = Lua.rawGetI(t, u-1);
 248       L.rawSetI(t, i, o2);
 249       L.rawSetI(t, u-1, p);
 250       // a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2
 251       i = l;
 252       j = u-1;
 253       // NB: Pivot P is in p
 254       while (true)      // invariant: a[l..i] <= P <= a[j..u]
 255       {
 256         // repeat ++i until a[i] >= P
 257         while (true)
 258         {
 259           o1 = Lua.rawGetI(t, ++i);
 260           if (!sort_comp(L, o1, p))
 261             break;
 262           if (i>u)
 263             L.error("invalid order function for sorting");
 264         }
 265         // repreat --j until a[j] <= P
 266         while (true)
 267         {
 268           o2 = Lua.rawGetI(t, --j);
 269           if (!sort_comp(L, p, o2))
 270             break;
 271           if (j<l)
 272             L.error("invalid order function for sorting");
 273         }
 274         if (j < i)
 275           break;
 276         L.rawSetI(t, i, o2);
 277         L.rawSetI(t, j, o1);
 278       }
 279       o1 = Lua.rawGetI(t, u-1);
 280       o2 = Lua.rawGetI(t, i);
 281       L.rawSetI(t, u-1, o2);
 282       L.rawSetI(t, i, o1);      // swap pivot (a[u-1]) with a[i]
 283       // a[l..i-1 <= a[i] == P <= a[i+1..u]
 284       // adjust so that smaller half is in [j..i] and larger one in [l..u]
 285       if (i-l < u-i)
 286       {
 287         j=l;
 288         i=i-1;
 289         l=i+2;
 290       }
 291       else
 292       {
 293         j=i+1;
 294         i=u;
 295         u=j-2;
 296       }
 297       auxsort(L, j, i); // call recursively the smaller one
 298     } // repeat the routine for the larger one
 299   }
 300
 301   private static boolean sort_comp(Lua L, Object a, Object b)
 302   {
 303     if (!Lua.isNil(L.value(2)))   // function?
 304     {
 305       L.pushValue(2);
 306       L.push(a);
 307       L.push(b);
 308       L.call(2, 1);
 309       boolean res = L.toBoolean(L.value(-1));
 310       L.pop(1);
 311       return res;
 312     }
 313     else        // a < b?
 314     {
 315       return L.lessThan(a, b);
 316     }
 317   }
 318
 319   private static int aux_getn(Lua L, int n)
 320   {
 321     L.checkType(n, Lua.TTABLE);
 322     LuaTable t = (LuaTable)L.value(n);
 323     return t.getn();
 324   }
 325 }