/**
 * Copyright 2009 Google Inc.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *      http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS-IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */


function newSpanList() {
  function encodeInt(num) {
    num = num & 0x1fffffff;
    // neither 16-bit char can be 0x0001 or mistakable for the other
    return String.fromCharCode(((num >> 15) & 0x3fff) | 0x4000) +
      String.fromCharCode((num & 0x7fff) | 0x8000);
  }
  function decodeInt(str) {
    return ((str.charCodeAt(0) & 0x3fff) << 15) | (str.charCodeAt(1) & 0x7fff);
  }
  function indexOfInt(str, n) {
    var result = str.indexOf(encodeInt(n));
    if (result < 0) return result;
    return result/2;
  }
  function intAt(str, i) {
    var idx = i*2;
    return decodeInt(str.substr(idx, 2));
  }
  function numInts(str) { return str.length/2; }
  function subrange(str, start, end) {
    return str.substring(start*2, end*2);
  }
  var nil = "\1\1";
  var repeatNilCache = [''];
  function repeatNil(times) {
    while (times >= repeatNilCache.length) {
      repeatNilCache.push(repeatNilCache[repeatNilCache.length-1] + nil);
    }
    return repeatNilCache[times];
  }
  function indexOfNonnil(str, start) {
    startIndex = (start || 0)*2;
    var nonnilChar = /[^\1]/g;
    nonnilChar.lastIndex = startIndex;
    var result = nonnilChar.exec(str);
    if (! result) {
      return str.length/2;
    }
    return (nonnilChar.lastIndex - 1)/2;
  }
  function intSplice(str, start, delCount, newStr) {
    return str.substring(0, start*2) + newStr + str.substring((start+delCount)*2);
  }

  function entryWidth(entry) {
    if ((typeof entry) == "number") return entry;
    return (entry && entry.width) || 1;
  }

  // "func" is a function over 0..(numItems-1) that is monotonically
  // "increasing" with index (false, then true).  Finds the boundary
  // between false and true, a number between 0 and numItems inclusive.
  function binarySearch(numItems, func) {
    if (numItems < 1) return 0;
    if (func(0)) return 0;
    if (! func(numItems-1)) return numItems;
    var low = 0; // func(low) is always false
    var high = numItems-1; // func(high) is always true
    while ((high - low) > 1) {
      var x = Math.floor((low+high)/2); // x != low, x != high
      if (func(x)) high = x;
      else low = x;
    }
    return high;
  }
  
  var NEXT_ID = 1;
  var entryList = ""; // e.g. 2, 4, 3, 6
  var charList = ""; // e.g. nil, nil, nil, 2, nil, 4, nil, nil, nil, nil, 3, 6
  var keyToId = {};
  var idToKey = {};
  var idToEntry = {};
  var idToNextId = {};
  var idToPrevId = {};
  var length = 0;
  var totalWidth = 0;

  function idAtIndex(i) { return intAt(entryList, i); }
  function indexOfId(id) { return indexOfInt(entryList, id); }
  function offsetOfId(id) {
    if (! id) return totalWidth;
    var entry = idToEntry[id];
    var wid = entryWidth(entry);
    var lastCharLoc = indexOfInt(charList, id);
    return lastCharLoc + 1 - wid;
  }
  function idAtOffset(n) {
    return intAt(charList, indexOfNonnil(charList, n));
  }
  
  var self = {
    length: function() { return length; },
    totalWidth: function() { return totalWidth; },
    next: function (entryOrKey) {
      if ((typeof entryOrKey) == "object") {
	var entry = entryOrKey;
	var id = idToNextId[keyToId[entry.key]];
	if (id) return idToEntry[id];
	return null;
      }
      else {
	var k = entryOrKey;
	var id = idToNextId[keyToId[k]];
	if (id) return idToKey[id];
	return null;
      }
    },
    prev: function (entryOrKey) {
      if ((typeof entryOrKey) == "object") {
	var entry = entryOrKey;
	var id = idToPrevId[keyToId[entry.key]];
	if (id) return idToEntry[id];
	return null;
      }
      else {
	var k = entryOrKey;
	var id = idToPrevId[keyToId[k]];
	if (id) return idToKey[id];
	return null;
      }
    },
    atKey: function (k) { return idToEntry[keyToId[k]]; },
    atIndex: function (i) { return idToEntry[idAtIndex(i)]; },
    keyAtIndex: function(i) { return idToKey[idAtIndex(i)]; },
    keyAtOffset: function(n) { return idToKey[idAtOffset(n)]; },
    containsKey: function (k) { return !! keyToId[k]; },
    indexOfKey: function (k) { return indexOfId(keyToId[k]); },
    indexOfEntry: function (entry) { return self.indexOfKey(entry.key); },
    setKeyWidth: function (k, width) {
      var id = keyToId[k];
      var charStart = offsetOfId(id);
      var oldWidth = entryWidth(idToEntry[id]);
      var toDelete = 0;
      var toInsert = 0;
      if (width < oldWidth) toDelete = oldWidth - width;
      else if (width > oldWidth) toInsert = width - oldWidth;
      charList = intSplice(charList, charStart, toDelete, repeatNil(toInsert));      
      totalWidth += (width - oldWidth);
    },
    setEntryWidth: function (entry, width) {
      return self.setKeyWidth(entry.key, width);
    },
    getEntryWidth: function (entry) {
      return entryWidth(entry);
    },
    getKeyWidth: function (k) {
      return entryWidth(idToEntry[keyToId[k]]);
    },
    offsetOfKey: function(k) { return offsetOfId(keyToId[k]); },
    offsetOfEntry: function(entry) { return self.offsetOfKey(entry.key); },
    offsetOfIndex: function (i) {
      if (i < 0) return 0;
      else if (i >= length) {
	return totalWidth;
      }
      else {
	return offsetOfId(idAtIndex(i));
      }
    },
    atOffset: function (n) {
      return idToEntry[idAtOffset(n)];
    },
    indexOfOffset: function (n) {
      if (n < 0) return 0;
      else if (n >= totalWidth) return length;
      return indexOfId(idAtOffset(n));
    },
    search: function(entryFunc) {
      return binarySearch(length, function (i) {
	return entryFunc(idToEntry[idAtIndex(i)]);
      });
    },
    push: function(entry, optKey) {
      self.splice(length, 0, [entry], (optKey && [optKey]));
    },
    // entries can be objects with a 'key' property, possibly a 'width' property,
    // and any other properties;  OR they can be just a width number, for an
    // ultra-light-weight representation.  In the latter case the key array is
    // used to get the keys.  Some functions become useless with this usage, i.e.
    // the ones that use an entry for identity.
    splice: function (start, deleteCount, newEntryArray, optKeyArray) {
      var charStart = self.offsetOfIndex(start);
      var charsToDelete = 0;
      var idBefore = ((start == 0) ? null : intAt(entryList, start-1));
      // idAfter is mutated into id of node following deleted nodes
      var idAfter = ((start == length) ? null : (idBefore ? idToNextId[idBefore] :
						 intAt(entryList, start)));
      if (deleteCount > 0) {
	var deleteId = idAfter;
	for(var i=0;i<deleteCount;i++) {
	  var nextId = idToNextId[deleteId];
	  var entry = idToEntry[deleteId];
	  var wid = entryWidth(entry);
	  delete keyToId[idToKey[deleteId]];
	  delete idToKey[deleteId];
	  delete idToEntry[deleteId];
	  delete idToNextId[deleteId];
	  delete idToPrevId[deleteId];
	  length--;
	  totalWidth -= wid;
	  charsToDelete += wid;
	  deleteId = nextId;
	}
	idAfter = (deleteId || null);
      }
      var newChars = [];
      var newIds = [];
      var prevId = idBefore;
      if (newEntryArray && newEntryArray.length > 0) {
	for(var i=0,n=newEntryArray.length; i<n; i++) {
	  var entry = newEntryArray[i];
	  var newId = (NEXT_ID++);
	  var encId = encodeInt(newId);
	  newIds.push(encId);
	  var wid = entryWidth(entry);
	  newChars.push(repeatNil(wid-1), encId);
	  var key = (optKeyArray ? optKeyArray[i] : entry.key);
	  keyToId[key] = newId;
	  idToKey[newId] = key;
	  idToEntry[newId] = entry;
	  if (prevId) {
	    idToNextId[prevId] = newId;
	    idToPrevId[newId] = prevId;
	  }
	  prevId = newId;
	  length++;
	  totalWidth += wid;
	}
	if (prevId && idAfter) {
	  idToNextId[prevId] = idAfter;
	  idToPrevId[idAfter] = prevId;
	}
      }
      else {
	if (idBefore && idAfter) {
	  idToNextId[idBefore] = idAfter;
	  idToPrevId[idAfter] = idBefore;
	}
	else if (idBefore) delete idToNextId[idBefore];
	else if (idAfter) delete idToPrevId[idAfter];
      }
      entryList = intSplice(entryList, start, deleteCount, newIds.join(''));
      charList = intSplice(charList, charStart, charsToDelete, newChars.join(''));
      
      if (length > 0) {
	// checkrep
	if (idToPrevId[idAtIndex(0)]) console.error("a");
	if (idToNextId[idAtIndex(length-1)]) console.error("b");
	for(var i=0;i<length-1;i++) {
	  if (idToNextId[idAtIndex(i)] != idAtIndex(i+1)) console.error("c"+i);
	}
	for(var i=1;i<length;i++) {
	  if (idToPrevId[idAtIndex(i)] != idAtIndex(i-1)) console.error("d"+i);
	}
      }
    }
  };

  return self;
}