text: var XSD_INTEGER = 'http://www.w3.org/2001/XMLSchema#integer';
  var XSD_STRING = 'http://www.w3.org/2001/XMLSchema#string';
  
  function Generator(options) {
    this._options = options = options || {};
  
    var prefixes = options.prefixes || {};
    this._prefixByIri = {};
    var prefixIris = [];
    for (var prefix in prefixes) {
      var iri = prefixes[prefix];
      if (isString(iri)) {
        this._prefixByIri[iri] = prefix;
        prefixIris.push(iri);
      }
    }
    var iriList = prefixIris.join('|').replace(/[\]\/\(\)\*\+\?\.\\\$]/g, '\\$&');
    this._prefixRegex = new RegExp('^(' + iriList + ')([a-zA-Z][\\-_a-zA-Z0-9]*)$');
    this._usedPrefixes = {};
    this._sparqlStar = options.sparqlStar;
    this._indent =  isString(options.indent)  ? options.indent  : '  ';
    this._newline = isString(options.newline) ? options.newline : '\n';
    this._explicitDatatype = Boolean(options.explicitDatatype);
  }
  
  // Converts the parsed query object into a SPARQL query
  Generator.prototype.toQuery = function (q) {
    var query = '';
  
    if (q.queryType)
      query += q.queryType.toUpperCase() + ' ';
    if (q.reduced)
      query += 'REDUCED ';
    if (q.distinct)
      query += 'DISTINCT ';
  
    if (q.variables){
      query += mapJoin(q.variables, undefined, function (variable) {
        return isTerm(variable) ? this.toEntity(variable) :
               '(' + this.toExpression(variable.expression) + ' AS ' + variableToString(variable.variable) + ')';
      }, this) + ' ';
    }
    else if (q.template)
      query += this.group(q.template, true) + this._newline;
  
    if (q.from)
      query += this.graphs('FROM ', q.from.default) + this.graphs('FROM NAMED ', q.from.named);
    if (q.where)
      query += 'WHERE ' + this.group(q.where, true) + this._newline;
  
    if (q.updates)
      query += mapJoin(q.updates, ';' + this._newline, this.toUpdate, this);
  
    if (q.group)
      query += 'GROUP BY ' + mapJoin(q.group, undefined, function (it) {
        var result = isTerm(it.expression)
          ? this.toEntity(it.expression)
          : '(' + this.toExpression(it.expression) + ')';
        return it.variable ? '(' + result + ' AS ' + variableToString(it.variable) + ')' : result;
      }, this) + this._newline;
    if (q.having)
      query += 'HAVING (' + mapJoin(q.having, undefined, this.toExpression, this) + ')' + this._newline;
    if (q.order)
      query += 'ORDER BY ' + mapJoin(q.order, undefined, function (it) {
        var expr = '(' + this.toExpression(it.expression) + ')';
        return !it.descending ? expr : 'DESC ' + expr;
      }, this) + this._newline;
  
    if (q.offset)
      query += 'OFFSET ' + q.offset + this._newline;
    if (q.limit)
      query += 'LIMIT ' + q.limit + this._newline;
  
    if (q.values)
      query += this.values(q);
  
    // stringify prefixes at the end to mark used ones
    query = this.baseAndPrefixes(q) + query;
    return query.trim();
  };
  
  Generator.prototype.baseAndPrefixes = function (q) {
    var base = q.base ? ('BASE <' + q.base + '>' + this._newline) : '';
    var prefixes = '';
    for (var key in q.prefixes) {
      if (this._options.allPrefixes || this._usedPrefixes[key])
        prefixes += 'PREFIX ' + key + ': <' + q.prefixes[key] + '>' + this._newline;
    }
    return base + prefixes;
  };
  
  // Converts the parsed SPARQL pattern into a SPARQL pattern
  Generator.prototype.toPattern = function (pattern) {
    var type = pattern.type || (pattern instanceof Array) && 'array' ||
               (pattern.subject && pattern.predicate && pattern.object ? 'triple' : '');
    if (!(type in this))
      throw new Error('Unknown entry type: ' + type);
    return this[type](pattern);
  };
  
  Generator.prototype.triple = function (t) {
    return this.toEntity(t.subject) + ' ' + this.toEntity(t.predicate) + ' ' + this.toEntity(t.object) + '.';
  };
  
  Generator.prototype.array = function (items) {
    return mapJoin(items, this._newline, this.toPattern, this);
  };
  
  Generator.prototype.bgp = function (bgp) {
    return this.encodeTriples(bgp.triples);
  };
  
  Generator.prototype.encodeTriples = function (triples) {
    if (!triples.length)
      return '';
  
    var parts = [], subject = undefined, predicate = undefined;
    for (var i = 0; i < triples.length; i++) {
      var triple = triples[i];
      // Triple with different subject
      if (!equalTerms(triple.subject, subject)) {
        // Terminate previous triple
        if (subject)
          parts.push('.' + this._newline);
        subject = triple.subject;
        predicate = triple.predicate;
        parts.push(this.toEntity(subject), ' ', this.toEntity(predicate));
      }
      // Triple with same subject but different predicate
      else if (!equalTerms(triple.predicate, predicate)) {
        predicate = triple.predicate;
        parts.push(';' + this._newline, this._indent, this.toEntity(predicate));
      }
      // Triple with same subject and predicate
      else {
        parts.push(',');
      }
      parts.push(' ', this.toEntity(triple.object));
    }
    parts.push('.');
  
    return parts.join('');
  }
  
  Generator.prototype.graph = function (graph) {
    return 'GRAPH ' + this.toEntity(graph.name) + ' ' + this.group(graph);
  };
  
  Generator.prototype.graphs = function (keyword, graphs) {
    return !graphs || graphs.length === 0 ? '' :
      mapJoin(graphs, '', function (g) { return keyword + this.toEntity(g) + this._newline; }, this)
  }
  
  Generator.prototype.group = function (group, inline) {
    group = inline !== true ? this.array(group.patterns || group.triples)
                            : this.toPattern(group.type !== 'group' ? group : group.patterns);
    return group.indexOf(this._newline) === -1 ? '{ ' + group + ' }' : '{' + this._newline + this.indent(group) + this._newline + '}';
  };
  
  Generator.prototype.query = function (query) {
    return this.toQuery(query);
  };
  
  Generator.prototype.filter = function (filter) {
    return 'FILTER(' + this.toExpression(filter.expression) + ')';
  };
  
  Generator.prototype.bind = function (bind) {
    return 'BIND(' + this.toExpression(bind.expression) + ' AS ' + variableToString(bind.variable) + ')';
  };
  
  Generator.prototype.optional = function (optional) {
    return 'OPTIONAL ' + this.group(optional);
  };
  
  Generator.prototype.union = function (union) {
    return mapJoin(union.patterns, this._newline + 'UNION' + this._newline, function (p) { return this.group(p, true); }, this);
  };
  
  Generator.prototype.minus = function (minus) {
    return 'MINUS ' + this.group(minus);
  };
  
  Generator.prototype.values = function (valuesList) {
    // Gather unique keys
    var keys = Object.keys(valuesList.values.reduce(function (keyHash, values) {
      for (var key in values) keyHash[key] = true;
      return keyHash;
    }, {}));
    // Check whether simple syntax can be used
    var lparen, rparen;
    if (keys.length === 1) {
      lparen = rparen = '';
    } else {
      lparen = '(';
      rparen = ')';
    }
    // Create value rows
    return 'VALUES ' + lparen + keys.join(' ') + rparen + ' {' + this._newline +
      mapJoin(valuesList.values, this._newline, function (values) {
        return '  ' + lparen + mapJoin(keys, undefined, function (key) {
          return values[key] ? this.toEntity(values[key]) : 'UNDEF';
        }, this) + rparen;
      }, this) + this._newline + '}';
  };
  
  Generator.prototype.service = function (service) {
    return 'SERVICE ' + (service.silent ? 'SILENT ' : '') + this.toEntity(service.name) + ' ' +
           this.group(service);
  };
  
  // Converts the parsed expression object into a SPARQL expression
  Generator.prototype.toExpression = function (expr) {
    if (isTerm(expr)) {
      return this.toEntity(expr);
    }
    switch (expr.type.toLowerCase()) {
      case 'aggregate':
        return expr.aggregation.toUpperCase() +
               '(' + (expr.distinct ? 'DISTINCT ' : '') + this.toExpression(expr.expression) +
               (expr.separator ? '; SEPARATOR = ' + '"' + expr.separator.replace(escape, escapeReplacer) + '"' : '') + ')';
      case 'functioncall':
        return this.toEntity(expr.function) + '(' + mapJoin(expr.args, ', ', this.toExpression, this) + ')';
      case 'operation':
        var operator = expr.operator.toUpperCase(), args = expr.args || [];
        switch (expr.operator.toLowerCase()) {
        // Infix operators
        case '<':
        case '>':
        case '>=':
        case '<=':
        case '&&':
        case '||':
        case '=':
        case '!=':
        case '+':
        case '-':
        case '*':
        case '/':
            return (isTerm(args[0]) ? this.toEntity(args[0]) : '(' + this.toExpression(args[0]) + ')') +
                   ' ' + operator + ' ' +
                   (isTerm(args[1]) ? this.toEntity(args[1]) : '(' + this.toExpression(args[1]) + ')');
        // Unary operators
        case '!':
          return '!(' + this.toExpression(args[0]) + ')';
        case 'uminus':
          return '-(' + this.toExpression(args[0]) + ')';
        // IN and NOT IN
        case 'notin':
          operator = 'NOT IN';
        case 'in':
          return this.toExpression(args[0]) + ' ' + operator +
                 '(' + (isString(args[1]) ? args[1] : mapJoin(args[1], ', ', this.toExpression, this)) + ')';
        // EXISTS and NOT EXISTS
        case 'notexists':
          operator = 'NOT EXISTS';
        case 'exists':
          return operator + ' ' + this.group(args[0], true);
        // Other expressions
        default:
          return operator + '(' + mapJoin(args, ', ', this.toExpression, this) + ')';
        }
      default:
        throw new Error('Unknown expression type: ' + expr.type);
    }
  };
  
  // Converts the parsed entity (or property path) into a SPARQL entity
  Generator.prototype.toEntity = function (value) {
    if (isTerm(value)) {
      switch (value.termType) {
      // variable, * selector, or blank node
      case 'Wildcard':
        return '*';
      case 'Variable':
        return variableToString(value);
      case 'BlankNode':
        return '_:' + value.value;
      // literal
      case 'Literal':
        var lexical = value.value || '', language = value.language || '', datatype = value.datatype;
        value = '"' + lexical.replace(escape, escapeReplacer) + '"';
        if (language){
          value += '@' + language;
        } else if (datatype) {
          // Abbreviate literals when possible
          if (!this._explicitDatatype) {
            switch (datatype.value) {
            case XSD_STRING:
              return value;
            case XSD_INTEGER:
              if (/^\d+$/.test(lexical))
                // Add space to avoid confusion with decimals in broken parsers
                return lexical + ' ';
            }
          }
          value += '^^' + this.encodeIRI(datatype.value);
        }
        return value;
      case 'Quad':
        if (!this._sparqlStar)
            throw new Error('SPARQL* support is not enabled');
  
        if (value.graph && value.graph.termType !== "DefaultGraph") {
          return '<< GRAPH ' +
            this.toEntity(value.graph) +
            ' { ' +
            this.toEntity(value.subject) + ' ' +
            this.toEntity(value.predicate) + ' ' +
            this.toEntity(value.object) +
            ' } ' +
            ' >>'
        }
        else {
          return (
            '<< ' +
            this.toEntity(value.subject) + ' ' +
            this.toEntity(value.predicate) + ' ' +
            this.toEntity(value.object) +
            ' >>'
          );
        }
      // IRI
      default:
        return this.encodeIRI(value.value);
      }
    }
    // property path
    else {
      var items = value.items.map(this.toEntity, this), path = value.pathType;
      switch (path) {
      // prefix operator
      case '^':
      case '!':
        return path + items[0];
      // postfix operator
      case '*':
      case '+':
      case '?':
        return '(' + items[0] + path + ')';
      // infix operator
      default:
        return '(' + items.join(path) + ')';
      }
    }
  };
  var escape = /["\\\t\n\r\b\f]/g,
      escapeReplacer = function (c) { return escapeReplacements[c]; },
      escapeReplacements = { '\\': '\\\\', '"': '\\"', '\t': '\\t',
                             '\n': '\\n', '\r': '\\r', '\b': '\\b', '\f': '\\f' };
  
  // Represent the IRI, as a prefixed name when possible
  Generator.prototype.encodeIRI = function (iri) {
    var prefixMatch = this._prefixRegex.exec(iri);
    if (prefixMatch) {
      var prefix = this._prefixByIri[prefixMatch[1]];
      this._usedPrefixes[prefix] = true;
      return prefix + ':' + prefixMatch[2];
    }
    return '<' + iri + '>';
  };
  
  // Converts the parsed update object into a SPARQL update clause
  Generator.prototype.toUpdate = function (update) {
    switch (update.type || update.updateType) {
    case 'load':
      return 'LOAD' + (update.source ? ' ' + this.toEntity(update.source) : '') +
             (update.destination ? ' INTO GRAPH ' + this.toEntity(update.destination) : '');
    case 'insert':
      return 'INSERT DATA '  + this.group(update.insert, true);
    case 'delete':
      return 'DELETE DATA '  + this.group(update.delete, true);
    case 'deletewhere':
      return 'DELETE WHERE ' + this.group(update.delete, true);
    case 'insertdelete':
      return (update.graph ? 'WITH ' + this.toEntity(update.graph) + this._newline : '') +
             (update.delete.length ? 'DELETE ' + this.group(update.delete, true) + this._newline : '') +
             (update.insert.length ? 'INSERT ' + this.group(update.insert, true) + this._newline : '') +
             (update.using ? this.graphs('USING ', update.using.default) : '') +
             (update.using ? this.graphs('USING NAMED ', update.using.named) : '') +
             'WHERE ' + this.group(update.where, true);
    case 'add':
    case 'copy':
    case 'move':
      return update.type.toUpperCase() + (update.source.default ? ' DEFAULT ' : ' ') +
             'TO ' + this.toEntity(update.destination.name);
    case 'create':
    case 'clear':
    case 'drop':
      return update.type.toUpperCase() + (update.silent ? ' SILENT ' : ' ') + (
        update.graph.default ? 'DEFAULT' :
        update.graph.named ? 'NAMED' :
        update.graph.all ? 'ALL' :
        ('GRAPH ' + this.toEntity(update.graph.name))
      );
    default:
      throw new Error('Unknown update query type: ' + update.type);
    }
  };
  
  // Indents each line of the string
  Generator.prototype.indent = function(text) { return text.replace(/^/gm, this._indent); }
  
  function variableToString(variable){
    return '?' + variable.value;
  }
  
  // Checks whether the object is a string
  function isString(object) { return typeof object === 'string'; }
  
  // Checks whether the object is a Term
  function isTerm(object) {
    return typeof object.termType === 'string';
  }
  
  // Checks whether term1 and term2 are equivalent without `.equals()` prototype method
  function equalTerms(term1, term2) {
    if (!term1 || !isTerm(term1)) { return false; }
    if (!term2 || !isTerm(term2)) { return false; }
    if (term1.termType !== term2.termType) { return false; }
    switch (term1.termType) {
      case 'Literal':
        return term1.value === term2.value
            && term1.language === term2.language
            && equalTerms(term1.datatype, term2.datatype);
      case 'Quad':
        return equalTerms(term1.subject, term2.subject)
            && equalTerms(term1.predicate, term2.predicate)
            && equalTerms(term1.object, term2.object)
            && equalTerms(term1.graph, term2.graph);
      default:
        return term1.value === term2.value;
    }
  }
  
  // Maps the array with the given function, and joins the results using the separator
  function mapJoin(array, sep, func, self) {
    return array.map(func, self).join(isString(sep) ? sep : ' ');
  }
  
  /**
   * @param options {
   *   allPrefixes: boolean,
   *   indentation: string,
   *   newline: string
   * }
   */
  module.exports = function SparqlGenerator(options = {}) {
    return {
      stringify: function (query) {
        var currentOptions = Object.create(options);
        currentOptions.prefixes = query.prefixes;
        return new Generator(currentOptions).toQuery(query);
      },
      createGenerator: function() { return new Generator(options); }
    };
  };
  