Changeset 2018


Ignore:
Timestamp:
Jul 12, 2006, 9:57:12 PM (14 years ago)
Author:
orlov
Message:
  • Code has been refactored as was suggested by Romanenko in letter to

refal-devel@… 11 Jul 2006.

  • Assertions in all unsafe methods have been added.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • to-imperative/trunk/java/org/refal/plus/Expr.java

    r1978 r2018  
    77/*
    88 * TODO:
    9  *   - Insert assertions in all unsafe methods.
    10  *   - Add holes around exprs.
    119 *   - Add clone() implementation.
    1210 *   - Implement Serializable.
     
    1614    implements Comparable, Cloneable
    1715{
     16    public static final Expr empty = new Expr(0);
     17
     18    private static final Object border = new Object ();
     19
     20    private final Object[] terms;
     21
     22    private final int start;
     23
     24    private final int length;
     25
     26    /*
     27     * Several variables for gathering some statistics about expression
     28     * concatenations.
     29     * Do not affect Expr operation.
     30     */
    1831    public static int no_copy = 0;
    1932    public static int left_copy = 0;
     
    2134    public static int both_copy = 0;
    2235
    23     public static final Expr empty = new Expr(0);
    24 
    25     private static final Object border = new Object ();
    26 
    27     private final Object[] expr;
    28 
    29     private final int index;
    30 
    31     private final int length;
    32 
    33     /**
    34      * Creates empty expression
    35      * 
    36      */
    37     public Expr() {
    38         index = 0;
     36    /**
     37     * Creates empty expression.
     38     */
     39    public Expr () {
     40        start = 0;
    3941        length = 0;
    40         expr = empty.expr;
    41     }
    42 
    43     /**
    44      * Creates the expression of the `size` length
    45      *
    46      * @param size --
    47      *            the size of the expression
    48      */
    49     private Expr(int size) {
    50         length = size;
    51         expr = new Object[size*2];
    52         index = size/2;
    53         if (index > 0)
    54             expr[index - 1] = border;
    55         if (index + length < expr.length)
    56             expr[index + length] = border;
    57     }
    58 
    59     /**
    60      * Creates subexpression
     42        terms = empty.terms;
     43    }
     44
     45    /**
     46     * Creates an expression with given length.
     47     */
     48    protected Expr (int len) {
     49        assert len >= 0;
     50        length = len;
     51        terms = new Object[len*2];
     52        start = len/2;
     53        if (start > 0)
     54            terms[start - 1] = border;
     55        if (start + length < terms.length)
     56            terms[start + length] = border;
     57    }
     58
     59    /**
     60     * Creates subexpression.
    6161     *
    6262     * @param e --
    63      *            the expression
     63     *            source expression
    6464     * @param i --
    65      *            the beginning of the expression
     65     *            index where subexpression starts
    6666     * @param len --
    67      *            the length of the expression
    68      */
    69     public Expr(Expr e, int i, int len) {
    70         expr = e.expr;
    71         index = e.index + i;
     67     *            subexpression length
     68     */
     69    public Expr (Expr e, int i, int len) {
     70        assert i >= 0;
     71        assert len >= 0;
     72        assert e.length - len >= i;
     73        terms = e.terms;
     74        start = e.start + i;
    7275        length = len;
    7376    }
    7477
    7578    /**
    76      * Element at position `i`
     79     * Element at position `i`.
    7780     *
    7881     * @param i --
    7982     *            position of the term
    80      * @return Object
    81      */
    82     public Object at(int i) {
    83         return expr[index + i];
    84     }
    85 
    86     /**
    87      * The length of expression
    88      *
    89      * @return
    90      */
    91     public int getLen() {
     83     */
     84    public Object at (int i) {
     85        assert 0 <= i && i < length;
     86        return terms[start + i];
     87    }
     88
     89    /**
     90     * The length of expression.
     91     */
     92    public int getLen () {
    9293        return length;
    9394    }
    9495
    95     public boolean equals(Object o) {
     96    public boolean equals (Object o) {
    9697        return (o instanceof Expr) && equals((Expr) o);
    9798    }
    9899
    99100    /**
    100      * Checks whether two expressions are equal
    101      *
    102      * @param e --
    103      *            the expression
    104      * @return boolean
    105      */
    106     public boolean equals(Expr e) {
     101     * Checks whether two expressions are equal.
     102     */
     103    public boolean equals (Expr e) {
    107104        if (length != e.length)
    108105            return false;
    109         if (expr == e.expr && index == e.index)
     106        if (terms == e.terms && start == e.start)
    110107            return true;
    111         for (int i = index, j = e.index; i < length + index; i++, j++) {
    112             if (expr[i] instanceof Comparable) {
    113                 if (!expr[i].equals(e.expr[j]))
    114                     return false;
    115             } else {
    116                 if (expr[i] != e.expr[j])
    117                     return false;
     108        for (int i = start, j = e.start; i < start + length; i++, j++) {
     109            if (terms[i] == e.terms[j])
     110                continue;
     111            if (terms[i] instanceof Comparable) {
     112                if (terms[i].equals(e.terms[j]))
     113                    continue;
    118114            }
     115            return false;
    119116        }
    120117
     
    122119         * Check how this affects efficiency!
    123120         */
    124 //        expr = e.expr;
     121//        terms = e.terms;
    125122//        index = e.index;
    126123        /*
     
    131128
    132129    /**
    133      * Checks whether this expr equals to the subexpr of another expression e
    134      * starting at index i
     130     * Checks whether this expr equals to the subexpr of another expression `e`
     131     * starting at index `i`
    135132     *
    136133     * @param e --
     
    138135     * @param i --
    139136     *            the position
    140      * @return boolean
    141      */
    142     public boolean eq(Expr e, int i) {
    143         if (expr == e.expr && index == e.index + i)
     137     */
     138    public boolean eq (Expr e, int i) {
     139        assert i >= 0;
     140        assert e.length - i >= length;
     141        if (terms == e.terms && start == e.start + i)
    144142            return true;
    145         for (int k = index, j = e.index + i; k < length + index; k++, j++) {
    146             if (expr[k] instanceof Comparable) {
    147                 if (!expr[k].equals(e.expr[j]))
    148                     return false;
    149             } else {
    150                 if (expr[k] != e.expr[j])
    151                     return false;
     143        for (int k = start, j = e.start + i; k < start + length; k++, j++) {
     144            if (terms[k] == e.terms[j])
     145                continue;
     146            if (terms[k] instanceof Comparable) {
     147                if (terms[k].equals(e.terms[j]))
     148                    continue;
    152149            }
     150            return false;
    153151        }
    154152
     
    156154         * Check how this affects efficiency!
    157155         */
    158 //        expr = e.expr;
     156//        terms = e.terms;
    159157//        index = e.index + i;
    160158        /*
     
    164162    }
    165163
    166     public int compareTo(Object o) {
    167         if (!(o instanceof Expr))
    168             throw new ClassCastException();
     164    public int compareTo (Object o) {
    169165        Expr e = (Expr) o;
    170166//        if (equals(e))        // Check how this affects efficiency!
    171167//            return 0;
    172         int compare_len = -1;                                                                       
     168        int compare_len = -1;
    173169        int min_len = length;
    174         if (length > e.length)
    175         {
     170        if (length > e.length) {
    176171            compare_len = 1;
    177172            min_len = e.length;
    178173        }
    179         else if (length == e.length)
    180         {
     174        else if (length == e.length) {
    181175            compare_len = 0;
    182176        }
    183         for (int i = index, j = e.index; min_len > 0; min_len--, i++, j++)
    184         {
     177        for (int i = start, j = e.start; min_len > 0; min_len--, i++, j++) {
    185178            int res;
    186             Class c1 = expr[i].getClass();
    187             Class c2 = e.expr[j].getClass();
    188             if (c1 == c2)
    189             {
    190                 try
    191                 {
    192                     res = ((Comparable) expr[i]).compareTo(e.expr[j]);
     179            Class c1 = terms[i].getClass();
     180            Class c2 = e.terms[j].getClass();
     181            if (c1 != c2) {
     182                if (RefalRuntime.getPriority(c1) < RefalRuntime.getPriority(c2))
     183                    res = -1;
     184                else
     185                    res = 1;
     186            }
     187            else {
     188                try {
     189                    res = ((Comparable) terms[i]).compareTo(e.terms[j]);
    193190                }
    194                 catch (ClassCastException _)
    195                 {
    196                     int h1 = expr[i].hashCode();
    197                     int h2 = e.expr[j].hashCode();
     191                catch (ClassCastException _) {
     192                    int h1 = terms[i].hashCode();
     193                    int h2 = e.terms[j].hashCode();
    198194                    if      (h1 > h2) res = 1;
    199195                    else if (h1 < h2) res = -1;
     
    205201                }
    206202            }
    207             else
    208             {
    209                 if (RefalRuntime.getPriority(c1) < RefalRuntime.getPriority(c2))
    210                     res = -1;
    211                 else
    212                     res = 1;
    213             }
    214203            if (res != 0) return res;
    215204        }
     
    218207
    219208    /**
    220      * Concatenate two expressions
    221      *
    222      * @param e1,e2 --
    223      *            the expressions
    224      * @return Expr
    225      */
    226     public Expr(Expr e1, Expr e2) {
     209     * Concatenates two expressions.
     210     */
     211    public Expr (Expr e1, Expr e2) {
    227212        length = e1.length + e2.length;
    228         if (length != 0)
     213        if (length == 0) {
     214            start = 0;
     215            terms = empty.terms;
     216            return;
     217        }
     218        if (e1.length == 0) {
     219            terms = e2.terms;
     220            start = e2.start;
     221            no_copy++;
     222            return;
     223        }
     224        if (e2.length == 0) {
     225            terms = e1.terms;
     226            start = e1.start;
     227            no_copy++;
     228            return;
     229        }
     230        if (e1.terms == e2.terms && e1.start + e1.length == e2.start) {
     231            terms = e1.terms;
     232            start = e1.start;
     233            no_copy++;
     234            return;
     235        }
     236        int e1_end = e1.start + e1.length;
     237        if (e1.terms.length - e1_end >= e2.length &&
     238            e1.terms[e1_end] == border)
    229239        {
    230             if (e1.length == 0)
    231             {
    232                 expr = e2.expr;
    233                 index = e2.index;
    234                 no_copy++;
    235             }
    236             else if (e2.length == 0)
    237             {
    238                 expr = e1.expr;
    239                 index = e1.index;
    240                 no_copy++;
    241             }
    242             else if (e1.expr == e2.expr && e1.index + e1.length == e2.index)
    243             {
    244                 expr = e1.expr;
    245                 index = e1.index;
    246                 no_copy++;
    247             }
    248             else if (e1.expr.length - e1.index - e1.length >= e2.length &&
    249                      e1.expr[e1.index + e1.length] == border)
    250             {
    251                 expr = e1.expr;
    252                 index = e1.index;
    253                 if (index + length < expr.length)
    254                     expr[index + length] = border;
    255                 System.arraycopy(e2.expr, e2.index, expr, index + e1.length, e2.length);
    256                 right_copy++;
    257             }
    258             else if (e1.length <= e2.index &&
    259                      e2.expr[e2.index - 1] == border)
    260             {
    261                 expr = e2.expr;
    262                 index = e2.index - e1.length;
    263                 if (index > 0)
    264                     expr[index - 1] = border;
    265                 System.arraycopy(e1.expr, e1.index, expr, index, e1.length);
    266                 left_copy++;
    267             }
    268             else
    269             {
    270                 expr = new Object[length*2];
    271                 index = length/2;
    272                 expr[index - 1] = border;
    273                 expr[index + length] = border;
    274                 System.arraycopy(e1.expr, e1.index, expr, index, e1.length);
    275                 System.arraycopy(e2.expr, e2.index, expr, index + e1.length, e2.length);
    276                 both_copy++;
    277             }
    278         }
    279         else
    280         {
    281             index = 0;
    282             expr = empty.expr;
    283         }
    284     }
    285 
    286     public Expr(Expr e1, Object t2) {
     240            terms = e1.terms;
     241            start = e1.start;
     242            if (start + length < terms.length)
     243                terms[start + length] = border;
     244            System.arraycopy(e2.terms, e2.start, terms, e1_end, e2.length);
     245            right_copy++;
     246            return;
     247        }
     248        if (e1.length <= e2.start && e2.terms[e2.start - 1] == border) {
     249            terms = e2.terms;
     250            start = e2.start - e1.length;
     251            if (start > 0)
     252                terms[start - 1] = border;
     253            System.arraycopy(e1.terms, e1.start, terms, start, e1.length);
     254            left_copy++;
     255            return;
     256        }
     257        terms = new Object[length*2];
     258        start = length/2;
     259        terms[start - 1] = border;
     260        terms[start + length] = border;
     261        System.arraycopy(e1.terms, e1.start, terms, start, e1.length);
     262        System.arraycopy(e2.terms, e2.start, terms, start + e1.length, e2.length);
     263        both_copy++;
     264    }
     265
     266    /**
     267     * Adds one term to the right of the expression.
     268     */
     269    public Expr (Expr e1, Object t2) {
    287270        length = e1.length + 1;
    288         if (e1.expr.length - e1.index - e1.length > 0 &&
    289             e1.expr[e1.index + e1.length] == border)
    290         {
    291             index = e1.index;
    292             expr = e1.expr;
    293             expr[index + e1.length] = t2;
    294             if (index + length < expr.length)
    295                 expr[index + length] = border;
     271        int e1_end = e1.start + e1.length;
     272        if (e1.terms.length - e1_end > 0 && e1.terms[e1_end] == border) {
     273            start = e1.start;
     274            terms = e1.terms;
     275            terms[e1_end] = t2;
     276            if (start + length < terms.length)
     277                terms[start + length] = border;
    296278            right_copy++;
    297         }
    298         else
    299         {
    300             expr = new Object[length*2];
    301             index = 0;
    302             expr[index + length] = border;
    303             System.arraycopy(e1.expr, e1.index, expr, index, e1.length);
    304             expr[index + e1.length] = t2;
    305             both_copy++;
    306         }
    307     }
    308 
     279            return;
     280        }
     281        terms = new Object[length*2];
     282        start = 0;
     283        terms[start + length] = border;
     284        System.arraycopy(e1.terms, e1.start, terms, start, e1.length);
     285        terms[start + e1.length] = t2;
     286        both_copy++;
     287    }
     288
     289    /**
     290     * Concatenates parts of two given expressions.
     291     */
    309292    public Expr(Expr e1, int i1, int len1, Expr e2, int i2, int len2) {
    310         length = len1 + len2;
    311         index = 0;
    312         expr = new Object[length];
    313         System.arraycopy(e1.expr, e1.index + i1, expr, index, len1);
    314         System.arraycopy(e2.expr, e2.index + i2, expr, index + len1, len2);
    315     }
    316 
    317     public static Expr concat(Expr[] arr) {
     293        this(len1 + len2);
     294        assert i1 >= 0;
     295        assert len1 >= 0;
     296        assert e1.length - len1 >= i1;
     297        assert i2 >= 0;
     298        assert len2 >= 0;
     299        assert e2.length - len2 >= i2;
     300        System.arraycopy(e1.terms, e1.start + i1, terms, start, len1);
     301        System.arraycopy(e2.terms, e2.start + i2, terms, start + len1, len2);
     302    }
     303
     304    /**
     305     * Concatenates all expressions from the given array.
     306     */
     307    public static Expr concat (Expr[] arr) {
    318308        int length = 0;
    319309        for (int i = 0; i < arr.length; i++)
     
    322312            return empty;
    323313        Expr e = new Expr(length);
    324         for (int i = 0, index = e.index; i < arr.length; index += arr[i].length, i++)
    325             System.arraycopy(arr[i].expr, arr[i].index, e.expr, index, arr[i].length);
     314        for (int i = 0, index = e.start; i < arr.length; index += arr[i].length, i++)
     315            System.arraycopy(arr[i].terms, arr[i].start,
     316                             e.terms, index, arr[i].length);
    326317        return e;
    327318    }
    328319
    329320    /**
    330      * Creates expression from the Object
    331      *
    332      * @param obj --
    333      *            Object
    334      */
    335     public Expr(Object obj) {
     321     * Creates expression from the Object.
     322     */
     323    public Expr (Object obj) {
    336324        length = 1;
    337         expr = new Object[length*2];
    338         expr[0] = obj;
    339         index = 0;
    340         expr[1] = border;
    341     }
    342 
    343     /**
    344      * Creates expression from the array of Objects
    345      *
    346      * @param arr --
    347      *            Object[]
    348      */
    349     public Expr(Object[] arr) {
     325        terms = new Object[2];
     326        terms[0] = obj;
     327        terms[1] = border;
     328        start = 0;
     329    }
     330
     331    /**
     332     * Creates expression from the array of Objects.
     333     * The returned expression is backed by the array, so the array shouldn't
     334     * be changed after invocation of this method.
     335     */
     336    public Expr (Object[] arr) {
    350337        length = arr.length;
    351         expr = arr;
    352         index = 0;
    353     }
    354 
    355     /**
    356      * Creates expression from a subarray of an array of Objects
    357      *
    358      * @param arr --
    359      *            Object[]
    360      */
    361     public Expr(Object[] arr, int i, int len) {
     338        terms = arr;
     339        start = 0;
     340    }
     341
     342    /**
     343     * Creates expression from a subarray of an array of Objects.
     344     * The returned expression is backed by the array, so the array shouldn't
     345     * be changed after invocation of this method (at least its part from `i`
     346     * to `i + len` shouldn't be changed).
     347     */
     348    public Expr (Object[] arr, int i, int len) {
     349        assert i >= 0;
     350        assert len >= 0;
     351        assert arr.length - len >= i;
    362352        length = len;
    363         expr = arr;
    364         index = i;
    365         if (index > 0)
    366             expr[index - 1] = border;
    367         if (index + length < expr.length)
    368             expr[index + length] = border;
    369     }
    370 
    371     /**
    372      * Returns the contents of the expr.
     353        terms = arr;
     354        start = i;
     355    }
     356
     357    /**
     358     * Returns the contents of this expr.
    373359     */
    374360    public Object[] toArray() {
    375361        Object[] arr = new Object[length];
    376         System.arraycopy(expr, index, arr, 0, length);
     362        System.arraycopy(terms, start, arr, 0, length);
    377363        return arr;
    378364    }
    379365
    380     public void copyToArray(Object[] arr, int where, int what, int len) {
    381         // FIXME: insert here assertion length - len >= what
    382         System.arraycopy(expr, index + what, arr, where, len);
     366    /**
     367     * Writes the contents of this expr to the given array.
     368     */
     369    public void toArray (Object[] arr, int where, int what, int len) {
     370        assert length - len >= what;
     371        System.arraycopy(terms, start + what, arr, where, len);
    383372    }
    384373
     
    386375     * Creates expression from a sequence of chars.
    387376     */
    388     public static Expr fromSequence(CharSequence seq) {
     377    public static Expr fromSequence (CharSequence seq) {
    389378        Expr e = new Expr(seq.length());
    390         for (int i = 0, j = e.index; i < e.length; i++, j++)
    391             e.expr[j] = new Character(seq.charAt(i));
     379        for (int i = 0, j = e.start; i < e.length; i++, j++)
     380            e.terms[j] = new Character(seq.charAt(i));
    392381        return e;
    393382    }
    394383
    395384    /**
    396      * Checks whether term is a symbol
     385     * Checks whether term is a symbol.
    397386     *
    398387     * @param i --
    399388     *            the position
    400      * @return boolean
    401      */
    402     public boolean symbolAt(int i) {
    403         return !(expr[index + i] instanceof Expr);
    404     }
    405 
    406     public boolean isEmpty() {
     389     */
     390    public boolean symbolAt (int i) {
     391        assert 0 <= i && i < length;
     392        return !(terms[start + i] instanceof Expr);
     393    }
     394
     395    public boolean isEmpty () {
    407396        return length == 0;
    408397    }
    409398
    410     public String toString() {
     399    public String toString () {
    411400        return new String(toStringBuffer());
    412401    }
     
    414403    public StringBuffer toStringBuffer () {
    415404        StringBuffer str = new StringBuffer(length);
    416         for (int i = index, last = index + length; i < last; i++) {
    417             if (expr[i] instanceof Expr)
     405        for (int i = start, end = start + length; i < end; i++) {
     406            if (terms[i] instanceof Expr)
    418407                str.append('(')
    419                    .append(((Expr)expr[i]).toStringBuffer())
     408                   .append(((Expr)terms[i]).toStringBuffer())
    420409                   .append(')');
    421410            else
    422                 str.append(expr[i].toString());
     411                str.append(terms[i].toString());
    423412        }
    424413        return str;
     
    429418        StringBuffer str = new StringBuffer(2*length);
    430419        boolean chars = false;
    431         for (int i = index, last = index + length; i < last; i++) {
    432             Object o = expr[i];
     420        for (int i = start, end = start + length; i < end; i++) {
     421            Object o = terms[i];
    433422            if (o instanceof Character) {
    434423                if (!chars) {
     
    470459
    471460    public SplitIterator leftSplit (int l) {
    472         // FIXME: insert here assertion length >= l
    473461        return new SplitIterator(this, l);
    474462    }
    475463
    476464    public SplitIterator rightSplit (int r) {
    477         // FIXME: insert here assertion length >= r
    478465        return new SplitIterator(this, length - r);
    479466    }
     
    490477
    491478        public SplitIterator next () {
    492             left = new Expr(left, 0, left.length + 1);
    493             right = new Expr(right, 1, right.length - 1);
     479            left = new Expr(left.terms, left.start, left.length + 1);
     480            right =
     481                right.length > 0 ? new Expr(right, 1, right.length - 1) : null;
    494482            return this;
    495483        }
    496484
    497485        public SplitIterator prev () {
    498             left = new Expr(left, 0, left.length - 1);
    499             right = new Expr(right, -1, right.length + 1);
     486            left = left.length > 0 ? new Expr(left, 0, left.length - 1) : null;
     487            right = new Expr(right.terms, right.start - 1, right.length + 1);
    500488            return this;
    501489        }
    502490
    503491        public boolean isValid () {
    504             return right.length >= 0 && left.length >= 0;
     492            return right != null && left != null;
    505493        }
    506494
Note: See TracChangeset for help on using the changeset viewer.