text: // The Layout object is the prototype of Substition objects, and provides utility methods to manipulate
  // common layout tables (GPOS, GSUB, GDEF...)
  
  'use strict';
  
  var check = require('./check');
  
  function searchTag(arr, tag) {
      /* jshint bitwise: false */
      var imin = 0;
      var imax = arr.length - 1;
      while (imin <= imax) {
          var imid = (imin + imax) >>> 1;
          var val = arr[imid].tag;
          if (val === tag) {
              return imid;
          } else if (val < tag) {
              imin = imid + 1;
          } else { imax = imid - 1; }
      }
      // Not found: return -1-insertion point
      return -imin - 1;
  }
  
  function binSearch(arr, value) {
      /* jshint bitwise: false */
      var imin = 0;
      var imax = arr.length - 1;
      while (imin <= imax) {
          var imid = (imin + imax) >>> 1;
          var val = arr[imid];
          if (val === value) {
              return imid;
          } else if (val < value) {
              imin = imid + 1;
          } else { imax = imid - 1; }
      }
      // Not found: return -1-insertion point
      return -imin - 1;
  }
  
  /**
   * @exports opentype.Layout
   * @class
   */
  var Layout = {
  
      /**
       * Binary search an object by "tag" property
       * @instance
       * @function searchTag
       * @memberof opentype.Layout
       * @param  {Array} arr
       * @param  {string} tag
       * @return {number}
       */
      searchTag: searchTag,
      /**
       * Binary search in a list of numbers
       * @instance
       * @function binSearch
       * @memberof opentype.Layout
       * @param  {Array} arr
       * @param  {number} value
       * @return {number}
       */
      binSearch: binSearch,
  
      /**
       * Returns all scripts in the substitution table.
       * @instance
       * @return {Array}
       */
      getScriptNames: function() {
          var gsub = this.getGsubTable();
          if (!gsub) { return []; }
          return gsub.scripts.map(function(script) {
              return script.tag;
          });
      },
  
      /**
       * Returns all LangSysRecords in the given script.
       * @instance
       * @param {string} script - Use 'DFLT' for default script
       * @param {boolean} create - forces the creation of this script table if it doesn't exist.
       * @return {Object} An object with tag and script properties.
       */
      getScriptTable: function(script, create) {
          var gsub = this.getGsubTable(create);
          if (gsub) {
              var scripts = gsub.scripts;
              var pos = searchTag(gsub.scripts, script);
              if (pos >= 0) {
                  return scripts[pos].script;
              } else {
                  var scr = {
                      tag: script,
                      script: {
                          defaultLangSys: { reserved: 0, reqFeatureIndex: 0xffff, featureIndexes: [] },
                          langSysRecords: []
                      }
                  };
                  scripts.splice(-1 - pos, 0, scr.script);
                  return scr;
              }
          }
      },
  
      /**
       * Returns a language system table
       * @instance
       * @param {string} script - Use 'DFLT' for default script
       * @param {string} language - Use 'DFLT' for default language
       * @param {boolean} create - forces the creation of this langSysTable if it doesn't exist.
       * @return {Object}
       */
      getLangSysTable: function(script, language, create) {
          var scriptTable = this.getScriptTable(script, create);
          if (scriptTable) {
              if (language === 'DFLT') {
                  return scriptTable.defaultLangSys;
              }
              var pos = searchTag(scriptTable.langSysRecords, language);
              if (pos >= 0) {
                  return scriptTable.langSysRecords[pos].langSys;
              } else if (create) {
                  var langSysRecord = {
                      tag: language,
                      langSys: { reserved: 0, reqFeatureIndex: 0xffff, featureIndexes: [] }
                  };
                  scriptTable.langSysRecords.splice(-1 - pos, 0, langSysRecord);
                  return langSysRecord.langSys;
              }
          }
      },
  
      /**
       * Get a specific feature table.
       * @instance
       * @param {string} script - Use 'DFLT' for default script
       * @param {string} language - Use 'DFLT' for default language
       * @param {string} feature - One of the codes listed at https://www.microsoft.com/typography/OTSPEC/featurelist.htm
       * @param {boolean} create - forces the creation of the feature table if it doesn't exist.
       * @return {Object}
       */
      getFeatureTable: function(script, language, feature, create) {
          var langSysTable = this.getLangSysTable(script, language, create);
          if (langSysTable) {
              var featureRecord;
              var featIndexes = langSysTable.featureIndexes;
              var allFeatures = this.font.tables.gsub.features;
              // The FeatureIndex array of indices is in arbitrary order,
              // even if allFeatures is sorted alphabetically by feature tag.
              for (var i = 0; i < featIndexes.length; i++) {
                  featureRecord = allFeatures[featIndexes[i]];
                  if (featureRecord.tag === feature) {
                      return featureRecord.feature;
                  }
              }
              if (create) {
                  var index = allFeatures.length;
                  // Automatic ordering of features would require to shift feature indexes in the script list.
                  check.assert(index === 0 || feature >= allFeatures[index - 1].tag, 'Features must be added in alphabetical order.');
                  featureRecord = {
                      tag: feature,
                      feature: { params: 0, lookupListIndexes: [] }
                  };
                  allFeatures.push(featureRecord);
                  featIndexes.push(index);
                  return featureRecord.feature;
              }
          }
      },
  
      /**
       * Get the first lookup table of a given type for a script/language/feature.
       * @instance
       * @param {string} script - Use 'DFLT' for default script
       * @param {string} language - Use 'DFLT' for default language
       * @param {string} feature - 4-letter feature code
       * @param {number} lookupType - 1 to 8
       * @param {boolean} create - forces the creation of the lookup table if it doesn't exist, with no subtables.
       * @return {Object}
       */
      getLookupTable: function(script, language, feature, lookupType, create) {
          var featureTable = this.getFeatureTable(script, language, feature, create);
          if (featureTable) {
              var lookupTable;
              var lookupListIndexes = featureTable.lookupListIndexes;
              var allLookups = this.font.tables.gsub.lookups;
              // lookupListIndexes are in no particular order, so use naïve search.
              for (var i = 0; i < lookupListIndexes.length; i++) {
                  lookupTable = allLookups[lookupListIndexes[i]];
                  if (lookupTable.lookupType === lookupType) {
                      return lookupTable;
                  }
              }
              if (create) {
                  lookupTable = {
                      lookupType: lookupType,
                      lookupFlag: 0,
                      subtables: [],
                      markFilteringSet: undefined
                  };
                  var index = allLookups.length;
                  allLookups.push(lookupTable);
                  lookupListIndexes.push(index);
                  return lookupTable;
              }
          }
      },
  
      /**
       * Returns the list of glyph indexes of a coverage table.
       * Format 1: the list is stored raw
       * Format 2: compact list as range records.
       * @instance
       * @param  {Object} coverageTable
       * @return {Array}
       */
      expandCoverage: function(coverageTable) {
          if (coverageTable.format === 1) {
              return coverageTable.glyphs;
          } else {
              var glyphs = [];
              var ranges = coverageTable.ranges;
              for (var i = 0; i < ranges; i++) {
                  var range = ranges[i];
                  var start = range.start;
                  var end = range.end;
                  for (var j = start; j <= end; j++) {
                      glyphs.push(j);
                  }
              }
              return glyphs;
          }
      }
  
  };
  
  module.exports = Layout;
  