    001package org.cpsolver.ifs.util;
    002
    003import java.io.Serializable;
    004import java.util.ArrayList;
    005import java.util.Collection;
    006import java.util.List;
    007
    008/**
    009 * A representation of a boolean query. Besides of AND, OR, and NOT, the query
    010 * may also contain terms (such as major:M1) that are evaluated by the {@link TermMatcher}.
    011 *
    012 * @author  Tomáš Müller
    013 * @version IFS 1.3 (Iterative Forward Search)<br>
    014 *          Copyright (C) 2024 Tomáš Müller<br>
    015 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    016 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    017 * <br>
    018 *          This library is free software; you can redistribute it and/or modify
    019 *          it under the terms of the GNU Lesser General Public License as
    020 *          published by the Free Software Foundation; either version 3 of the
    021 *          License, or (at your option) any later version. <br>
    022 * <br>
    023 *          This library is distributed in the hope that it will be useful, but
    024 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    025 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    026 *          Lesser General Public License for more details. <br>
    027 * <br>
    028 *          You should have received a copy of the GNU Lesser General Public
    029 *          License along with this library; if not see
    030 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    031 */
    032public class Query implements Serializable {
    033    private static final long serialVersionUID = 1L;
    034
    035    private Term iQuery = null;
    036
    037    public Query(String query) {
    038            iQuery = parse(query == null ? "" : query.trim());
    039    }
    040
    041    public Query(Term query) {
    042            iQuery = query;
    043    }
    044
    045    public Term getQuery() { return iQuery; }
    046
    047    /**
    048     * Evaluate if the query using the provided term matcher.
    049     */
    050    public boolean match(TermMatcher m) {
    051            return iQuery.match(m);
    052    }
    053
    054    /**
    055     * Evaluate if the query using the provided term matcher.
    056     */
    057
    058    public boolean match(AmbigousTermMatcher m) {
    059            Boolean ret = iQuery.match(m);
    060            if (ret == null) return true;
    061            return ret;
    062    }
    063
    064    @Override
    065    public String toString() {
    066            return iQuery.toString();
    067    }
    068
    069    public String toString(QueryFormatter f) {
    070            return iQuery.toString(f);
    071    }
    072
    073    public boolean hasAttribute(String... attr) {
    074            for (String a: attr)
    075                    if (iQuery.hasAttribute(a)) return true;
    076            return false;
    077    }
    078
    079    public boolean hasAttribute(Collection<String> attr) {
    080            for (String a: attr)
    081                    if (iQuery.hasAttribute(a)) return true;
    082            return false;
    083    }
    084
    085    private static List<String> split(String query, String... splits) {
    086            List<String> ret = new ArrayList<String>();
    087            int bracket = 0;
    088            boolean quot = false;
    089            int last = 0;
    090            boolean white = false;
    091            loop: for (int i = 0; i < query.length(); i++) {
    092                    if (query.charAt(i) == '"') {
    093                            quot = !quot;
    094                            white = !quot;
    095                            continue;
    096                    }
    097                    if (!quot && query.charAt(i) == '(') { bracket ++; white = false; continue; }
    098                    if (!quot && query.charAt(i) == ')') { bracket --; white = true; continue; }
    099                    if (quot || bracket > 0 || (!white && query.charAt(i) != ' ')) {
    100                            white = (query.charAt(i) == ' ');
    101                            continue;
    102                    }
    103                    white = (query.charAt(i) == ' ');
    104                    String q = query.substring(i).toLowerCase();
    105                    for (String split: splits) {
    106                            if (split.isEmpty() || q.startsWith(split + " ") || q.startsWith(split + "\"") || q.startsWith(split + "(")) {
    107                                    String x = query.substring(last, i).trim();
    108                                    if (split.isEmpty() && x.endsWith(":")) continue;
    109                                    if (!x.isEmpty()) ret.add(x);
    110                                    last = i + split.length();
    111                                    if (!split.isEmpty())
    112                                            i += split.length() - 1;
    113                                    continue loop;
    114                            }
    115                    }
    116            }
    117            String x = query.substring(last).trim();
    118            if (!x.isEmpty()) ret.add(x);
    119            return ret;
    120    }
    121
    122    private static Term parse(String query) {
    123            List<String> splits;
    124            splits = split(query, "and", "&&", "&");
    125            if (splits.size() > 1) {
    126                    CompositeTerm t = new AndTerm();
    127                    for (String q: splits)
    128                            t.add(parse(q));
    129                    return t;
    130            }
    131            splits = split(query, "or", "||", "|");
    132            if (splits.size() > 1) {
    133                    CompositeTerm t = new OrTerm();
    134                    for (String q: splits)
    135                            t.add(parse(q));
    136                    return t;
    137            }
    138            splits = split(query, "");
    139            if (splits.size() > 1) {
    140                    CompositeTerm and = new AndTerm();
    141                    boolean not = false;
    142                    splits: for (String q: splits) {
    143                            if (q.equalsIgnoreCase("not") || q.equals("!")) { not = true; continue; }
    144                            if (q.startsWith("!(")) {
    145                                    q = q.substring(1); not = true;
    146                            } else if (q.toLowerCase().startsWith("not(")) {
    147                                    q = q.substring(3); not = true;
    148                            }
    149                            if (not) {
    150                                    and.add(new NotTerm(parse(q)));
    151                                    not = false;
    152                            } else {
    153                                    Term t = parse(q);
    154                                    if (t instanceof AtomTerm) {
    155                                            AtomTerm a = (AtomTerm)t;
    156                                            for (Term x: and.terms()) {
    157                                                    if (x instanceof AtomTerm && ((AtomTerm)x).sameAttribute(a)) {
    158                                                            and.remove(x);
    159                                                            OrTerm or = new OrTerm();
    160                                                            or.add(x); or.add(a);
    161                                                            and.add(or);
    162                                                            continue splits;
    163                                                    } else if (x instanceof OrTerm && ((OrTerm)x).terms().get(0) instanceof AtomTerm && ((AtomTerm)((OrTerm)x).terms().get(0)).sameAttribute(a)) {
    164                                                            ((OrTerm)x).terms().add(a);
    165                                                            continue splits;
    166                                                    }
    167                                            }
    168                                    }
    169                                    and.add(t);
    170                            }
    171                    }
    172                    return and;
    173            }
    174            if (query.startsWith("(") && query.endsWith(")")) return parse(query.substring(1, query.length() - 1).trim());
    175            if (query.startsWith("\"") && query.endsWith("\"") && query.length() >= 2) return new AtomTerm(null, query.substring(1, query.length() - 1).trim());
    176            int idx = query.indexOf(':');
    177            if (idx >= 0) {
    178                    return new AtomTerm(query.substring(0, idx).trim().toLowerCase(), query.substring(idx + 1).trim());
    179            } else {
    180                    return new AtomTerm(null, query);
    181            }
    182    }
    183
    184    /**
    185     * Representation of a term in the query, that is attribute:value. Or a sub-query.
    186     */
    187    public static interface Term extends Serializable {
    188        /**
    189         * Does the term matches the provided object
    190         */
    191        public boolean match(TermMatcher m);
    192        /**
    193         * Print the term/sub-query
    194         */
    195        public String toString(QueryFormatter f);
    196        /**
    197         * Check if this term (or its sub-terms) contain a given attribute
    198         */
    199        public boolean hasAttribute(String attribute);
    200        /**
    201         * Does the term matches the provided object, returning null if does not apply (e.g., the object does not have the provided attribute)
    202         */
    203        public Boolean match(AmbigousTermMatcher m);
    204    }
    205
    206    /**
    207     * Composition of one or more terms in a query (e.g., A and B and C)
    208     */
    209    public static abstract class CompositeTerm implements Term {
    210        private static final long serialVersionUID = 1L;
    211        private List<Term> iTerms = new ArrayList<Term>();
    212
    213        public CompositeTerm() {}
    214
    215        public CompositeTerm(Term... terms) {
    216            for (Term t: terms) add(t);
    217        }
    218
    219        public CompositeTerm(Collection<Term> terms) {
    220            for (Term t: terms) add(t);
    221        }
    222
    223        /**
    224         * Add a term
    225         */
    226        public void add(Term t) { iTerms.add(t); }
    227
    228        /**
    229         * Remove a term
    230         */
    231        public void remove(Term t) { iTerms.remove(t); }
    232
    233        /** List terms */
    234        protected List<Term> terms() { return iTerms; }
    235
    236        /** Operation over the terms, such as AND or OR */
    237        public abstract String getOp();
    238
    239        @Override
    240        public boolean hasAttribute(String attribute) {
    241            for (Term t: terms())
    242                if (t.hasAttribute(attribute)) return true;
    243            return false;
    244        }
    245
    246        @Override
    247        public String toString() {
    248            String ret = "";
    249            for (Term t: terms()) {
    250                if (!ret.isEmpty()) ret += " " + getOp() + " ";
    251                ret += t;
    252            }
    253            return (terms().size() > 1 ? "(" + ret + ")" : ret);
    254        }
    255
    256        @Override
    257        public String toString(QueryFormatter f) {
    258            String ret = "";
    259            for (Term t: terms()) {
    260                if (!ret.isEmpty()) ret += " " + getOp() + " ";
    261                ret += t.toString(f);
    262            }
    263            return (terms().size() > 1 ? "(" + ret + ")" : ret);
    264        }
    265    }
    266
    267    /**
    268     * Representation of an OR between two or more terms.
    269     */
    270    public static class OrTerm extends CompositeTerm {
    271        private static final long serialVersionUID = 1L;
    272        public OrTerm() { super(); }
    273        public OrTerm(Term... terms) { super(terms); }
    274        public OrTerm(Collection<Term> terms) { super(terms); }
    275
    276        @Override
    277        public String getOp() { return "OR"; }
    278
    279        /** A term matches, when at least one sub-term matches */
    280        @Override
    281        public boolean match(TermMatcher m) {
    282            if (terms().isEmpty()) return true;
    283            for (Term t: terms())
    284                if (t.match(m)) return true;
    285            return false;
    286        }
    287
    288        @Override
    289        public Boolean match(AmbigousTermMatcher m) {
    290            if (terms().isEmpty()) return true;
    291            for (Term t: terms()) {
    292                Boolean r = t.match(m);
    293                if (r == null) return null;
    294                if (r) return true;
    295            }
    296            return false;
    297        }
    298    }
    299
    300    /**
    301     * Representation of an AND between two or more terms.
    302     */
    303    public static class AndTerm extends CompositeTerm {
    304        private static final long serialVersionUID = 1L;
    305        public AndTerm() { super(); }
    306        public AndTerm(Term... terms) { super(terms); }
    307        public AndTerm(Collection<Term> terms) { super(terms); }
    308
    309        @Override
    310        public String getOp() { return "AND"; }
    311
    312        /** A term matches, when all sub-term match */
    313        @Override
    314        public boolean match(TermMatcher m) {
    315            for (Term t: terms())
    316                if (!t.match(m)) return false;
    317            return true;
    318        }
    319
    320        @Override
    321        public Boolean match(AmbigousTermMatcher m) {
    322            for (Term t: terms()) {
    323                Boolean r = t.match(m);
    324                if (r == null) return null;
    325                if (!r) return false;
    326            }
    327            return true;
    328        }
    329    }
    330
    331    /**
    332     * Representation of a NOT term
    333     */
    334    public static class NotTerm implements Term {
    335        private static final long serialVersionUID = 1L;
    336        private Term iTerm;
    337
    338        public NotTerm(Term t) {
    339                iTerm = t;
    340        }
    341
    342        /** A term matches, when sub-term does not match */
    343        @Override
    344        public boolean match(TermMatcher m) {
    345            return !iTerm.match(m);
    346        }
    347
    348        @Override
    349        public boolean hasAttribute(String attribute) {
    350            return iTerm.hasAttribute(attribute);
    351        }
    352
    353        @Override
    354        public Boolean match(AmbigousTermMatcher m) {
    355            Boolean r = iTerm.match(m);
    356            if (r == null) return r;
    357            return !r;
    358        }
    359
    360        @Override
    361        public String toString() { return "NOT " + iTerm.toString(); }
    362
    363        @Override
    364        public String toString(QueryFormatter f) { return "NOT " + iTerm.toString(f); }
    365    }
    366
    367    /**
    368     * Representation of one attribute:value term
    369     */
    370    public static class AtomTerm implements Term {
    371        private static final long serialVersionUID = 1L;
    372        private String iAttr, iBody;
    373
    374        public AtomTerm(String attr, String body) {
    375            if (body.startsWith("\"") && body.endsWith("\"") && body.length()>1)
    376                body = body.substring(1, body.length() - 1);
    377            iAttr = attr; iBody = body;
    378        }
    379
    380        /** A term matches, when {@link TermMatcher#match(String, String)} matches */
    381        @Override
    382        public boolean match(TermMatcher m) {
    383            return m.match(iAttr, iBody);
    384        }
    385
    386        @Override
    387        public boolean hasAttribute(String attribute) {
    388            return attribute != null && attribute.equals(iAttr);
    389        }
    390
    391        public boolean sameAttribute(AtomTerm t) {
    392            return t != null && hasAttribute(t.iAttr);
    393        }
    394
    395        @Override
    396        public String toString() { return (iAttr == null ? "" : iAttr + ":") + (iBody.indexOf(' ') >= 0 ? "\"" + iBody + "\"" : iBody); }
    397
    398        @Override
    399        public String toString(QueryFormatter f) { return f.format(iAttr, iBody); }
    400
    401        @Override
    402        public Boolean match(AmbigousTermMatcher m) {
    403            return m.match(iAttr, iBody);
    404        }
    405    }
    406
    407    /**
    408     * Term matcher interface. Check representing an object to be matched with the query.
    409     *
    410     */
    411    public static interface TermMatcher {
    412        /**
    413         * Does the object has the given attribute matching the given term? For example, for a student, major:M1
    414         * would match a student that has major M1 (attribute is major, term is M1).
    415         */
    416        public boolean match(String attr, String term);
    417    }
    418
    419    /**
    420     * Ambigous term matcher. Returning yes, no, or does not apply (null).
    421     */
    422    public static interface AmbigousTermMatcher {
    423        /**
    424         * Does the object has the given attribute matching the given term?
    425         * Returns null if does not apply.
    426         **/
    427        public Boolean match(String attr, String term);
    428    }
    429
    430    /**
    431     * Query formatter class
    432     */
    433    public static interface QueryFormatter {
    434            String format(String attr, String term);
    435    }
    436
    437    public static void main(String[] args) {
    438            System.out.println(parse("(dept:1124 or dept:1125) and area:bio"));
    439            System.out.println(parse("a \"b c\" or ddd f \"x:x\" x: s !(band or org) (a)or(b)"));
    440            System.out.println(parse("! f (a)or(b) d !d not x s"));
    441            System.out.println(parse(""));
    442            System.out.println(split("(a \"b c\")  ddd f", ""));
    443            System.out.println(split("a \"b c\" OR not ddd f", "or"));
    444            System.out.println(split("a or((\"b c\" or dddor) f) q", "or"));
    445            System.out.println(parse("false"));
    446    }
    447
    448
    449}