<commit_before>/*
 * Copyright 2012 Google Inc. All Rights Reserved.
 *
 * 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.
 */

/** Plan indicating that there are no matching records. **/
var NOT_FOUND = {
  cost: 0,
  execute: function() {},
  toString: function() { return "no-match(cost=0)"; }
};

/** Plan indicating that an index has no plan for executing a query. **/
var NO_PLAN = {
  cost: Number.MAX_VALUE,
  execute: function() {},
  toString: function() { return "no-plan"; }
};


function dump(o) {
   if ( Array.isArray(o) ) return '[' + o.map(dump).join(',') + ']';
   return o ? o.toString() : '<undefined>';
}


/*
 * Index Interface:
 *   put(state, value) -> new state
 *   remove(state, value) -> new state
 *   plan(state, sink, options) -> {cost: int, toString: fn, execute: fn}
 *   size(state) -> int
 */

var ValueIndex = {
  put: function(s, newValue) { return newValue; },
  remove: function() {},
  plan: (function() {
    var plan = {
      cost: 1,
      execute: function(s, sink) {
        sink.put(s);
      },
      toString: function() { return 'unique'; }
    };

    return function() { return plan; };
  })(),
  select: function(value, sink, options) {
    if ( options ) {
      if ( options.query && ! options.query.f(value) ) return;
      if ( 'skip' in options && options.skip-- > 0 ) return;
      if ( 'limit' in options && options.limit-- < 1 ) return;
    }
    sink.put(value);
  },
  selectReverse: function(value, sink) { sink.put(value); },
  size:   function(obj) { return 1; },
  toString: function() { return 'value'; }
};

var KEY   = 0;
var VALUE = 1;
var SIZE  = 2;
var LEVEL = 3;
var LEFT  = 4;
var RIGHT = 5;

// TODO: investigate how well V8 optimizes static classes

// [0 key, 1 value, 2 size, 3 left, 4 right]
// [0 key, 1 value, 2 size, 3 level, 4 left, 5 right]

// AATree -- balanced binary search tree.
var TreeIndex = {
  create: function(prop, tail) {
    tail = tail || ValueIndex;

    return {
      __proto__: this,
      prop: prop,
      tail: tail
    };
  },

  /**
   * Bulk load an unsorted array of objects.
   * Faster than loading individually, and produces a balanced tree.
   **/
  bulkLoad: function(a) {
     // Only safe if children aren't themselves trees
     if ( this.tail === ValueIndex ) {
       a.sort(toCompare(this.prop));
       return this.bulkLoad_(a, 0, a.length-1);
     }

     var s = undefined;
     for ( var i = 0 ; i < a.length ; i++ ) {
       s = this.put(s, a[i]);
     }
     return s;
  },

  bulkLoad_: function(a, start, end) {
    if ( end < start ) return undefined;

    var m    = start + Math.floor((end-start+1) / 2);
    var tree = this.put(undefined, a[m]);

    tree[LEFT] = this.bulkLoad_(a, start, m-1);
    tree[RIGHT] = this.bulkLoad_(a, m+1, end);
    tree[SIZE] += this.size(tree[LEFT]) + this.size(tree[RIGHT]);

    return tree;
  },

  put: function(s, newValue) {
    return this.putKeyValue(s, this.prop.f(newValue), newValue);
  },

  putKeyValue: function(s, key, value) {
    if ( ! s ) {
      return [key, this.tail.put(null, value), 1, 1];
    }

    var r = this.compare(s[KEY], key);

    if ( r === 0 ) {
      // Set the value's property to be the same as the key in the index.
      // This saves memory by sharing objects.
      value[this.prop.name] = s[KEY];

      s[SIZE] -= this.tail.size(s[VALUE]);
      s[VALUE] = this.tail.put(s[VALUE], value);
      s[SIZE] += this.tail.size(s[VALUE]);
    } else {
      var side = r > 0 ? LEFT : RIGHT;

      if ( s[side] ) s[SIZE] -= s[side][SIZE];
      s[side] = this.putKeyValue(s[side], key, value);
      s[SIZE] += s[side][SIZE];
    }

    return this.split(this.skew(s));
  },

//    input: T, a node representing an AA tree that needs to be rebalanced.
//    output: Another node representing the rebalanced AA tree.

  skew: function(s) {
    if ( s && s[LEFT] && s[LEFT][LEVEL] === s[LEVEL] ) {
// console.log('skew');
      // Swap the pointers of horizontal left links.
      var l = s[LEFT];
      s[LEFT] = l[RIGHT];
      l[RIGHT] = s;

      return l;
    }

    return s;
  },

  updateSize: function(s) {
    s[SIZE] = this.size(s[LEFT]) + this.size(s[RIGHT]) + this.tail.size(s[VALUE]);
  },

  //  input: T, a node representing an AA tree that needs to be rebalanced.
  //  output: Another node representing the rebalanced AA tree.
  split: function(s) {
    if ( s && s[RIGHT] && s[RIGHT][RIGHT] && s[LEVEL] === s[RIGHT][RIGHT][LEVEL] ) {
// console.log('split');
      // We have two horizontal right links.  Take the middle node, elevate it, and return it.
      var r = s[RIGHT];
      s[RIGHT] = r[LEFT];
      r[LEFT] = s;
      r[LEVEL]++;
      this.updateSize(s);
      this.updateSize(r);

      return r;
    }

    return s;
  },

  // input: X, the value to delete, and T, the root of the tree from which it should be deleted.
  // output: T, balanced, without the value X.
  delete: function(s, key) {
    if ( ! s ) return s;

    var r = this.compare(s[KEY], key);

    if ( r === 0 ) {
      // If we're a leaf, easy, otherwise reduce to leaf case. 
      if ( ! s[LEFT] && ! s[RIGHT] ) return undefined;

      // TODO: add a unit test to verify that the size
      // adjusting logic is correct here.
      var side = s[LEFT] ? LEFT : RIGHT;
<commit_msg>Added size adjusting code to AATree skew() method.<commit_after>/*
 * Copyright 2012 Google Inc. All Rights Reserved.
 *
 * 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.
 */

/** Plan indicating that there are no matching records. **/
var NOT_FOUND = {
  cost: 0,
  execute: function() {},
  toString: function() { return "no-match(cost=0)"; }
};

/** Plan indicating that an index has no plan for executing a query. **/
var NO_PLAN = {
  cost: Number.MAX_VALUE,
  execute: function() {},
  toString: function() { return "no-plan"; }
};


function dump(o) {
   if ( Array.isArray(o) ) return '[' + o.map(dump).join(',') + ']';
   return o ? o.toString() : '<undefined>';
}


/*
 * Index Interface:
 *   put(state, value) -> new state
 *   remove(state, value) -> new state
 *   plan(state, sink, options) -> {cost: int, toString: fn, execute: fn}
 *   size(state) -> int
 */

var ValueIndex = {
  put: function(s, newValue) { return newValue; },
  remove: function() {},
  plan: (function() {
    var plan = {
      cost: 1,
      execute: function(s, sink) {
        sink.put(s);
      },
      toString: function() { return 'unique'; }
    };

    return function() { return plan; };
  })(),
  select: function(value, sink, options) {
    if ( options ) {
      if ( options.query && ! options.query.f(value) ) return;
      if ( 'skip' in options && options.skip-- > 0 ) return;
      if ( 'limit' in options && options.limit-- < 1 ) return;
    }
    sink.put(value);
  },
  selectReverse: function(value, sink) { sink.put(value); },
  size:   function(obj) { return 1; },
  toString: function() { return 'value'; }
};

var KEY   = 0;
var VALUE = 1;
var SIZE  = 2;
var LEVEL = 3;
var LEFT  = 4;
var RIGHT = 5;

// TODO: investigate how well V8 optimizes static classes

// [0 key, 1 value, 2 size, 3 left, 4 right]
// [0 key, 1 value, 2 size, 3 level, 4 left, 5 right]

// AATree -- balanced binary search tree.
var TreeIndex = {
  create: function(prop, tail) {
    tail = tail || ValueIndex;

    return {
      __proto__: this,
      prop: prop,
      tail: tail
    };
  },

  /**
   * Bulk load an unsorted array of objects.
   * Faster than loading individually, and produces a balanced tree.
   **/
  bulkLoad: function(a) {
     // Only safe if children aren't themselves trees
     if ( this.tail === ValueIndex ) {
       a.sort(toCompare(this.prop));
       return this.bulkLoad_(a, 0, a.length-1);
     }

     var s = undefined;
     for ( var i = 0 ; i < a.length ; i++ ) {
       s = this.put(s, a[i]);
     }
     return s;
  },

  bulkLoad_: function(a, start, end) {
    if ( end < start ) return undefined;

    var m    = start + Math.floor((end-start+1) / 2);
    var tree = this.put(undefined, a[m]);

    tree[LEFT] = this.bulkLoad_(a, start, m-1);
    tree[RIGHT] = this.bulkLoad_(a, m+1, end);
    tree[SIZE] += this.size(tree[LEFT]) + this.size(tree[RIGHT]);

    return tree;
  },

  put: function(s, newValue) {
    return this.putKeyValue(s, this.prop.f(newValue), newValue);
  },

  putKeyValue: function(s, key, value) {
    if ( ! s ) {
      return [key, this.tail.put(null, value), 1, 1];
    }

    var r = this.compare(s[KEY], key);

    if ( r === 0 ) {
      // Set the value's property to be the same as the key in the index.
      // This saves memory by sharing objects.
      value[this.prop.name] = s[KEY];

      s[SIZE] -= this.tail.size(s[VALUE]);
      s[VALUE] = this.tail.put(s[VALUE], value);
      s[SIZE] += this.tail.size(s[VALUE]);
    } else {
      var side = r > 0 ? LEFT : RIGHT;

      if ( s[side] ) s[SIZE] -= s[side][SIZE];
      s[side] = this.putKeyValue(s[side], key, value);
      s[SIZE] += s[side][SIZE];
    }

    return this.split(this.skew(s));
  },

//    input: T, a node representing an AA tree that needs to be rebalanced.
//    output: Another node representing the rebalanced AA tree.

  skew: function(s) {
    if ( s && s[LEFT] && s[LEFT][LEVEL] === s[LEVEL] ) {
      // Swap the pointers of horizontal left links.
      var l = s[LEFT];

      s[LEFT] = l[RIGHT];
      l[RIGHT] = s;

      this.updateSize(s);
      this.updateSize(l);

      return l;
    }

    return s;
  },

  updateSize: function(s) {
    s[SIZE] = this.size(s[LEFT]) + this.size(s[RIGHT]) + this.tail.size(s[VALUE]);
  },

  //  input: T, a node representing an AA tree that needs to be rebalanced.
  //  output: Another node representing the rebalanced AA tree.
  split: function(s) {
    if ( s && s[RIGHT] && s[RIGHT][RIGHT] && s[LEVEL] === s[RIGHT][RIGHT][LEVEL] ) {
// console.log('split');
      // We have two horizontal right links.  Take the middle node, elevate it, and return it.
      var r = s[RIGHT];

      s[RIGHT] = r[LEFT];
      r[LEFT] = s;
      r[LEVEL]++;

      this.updateSize(s);
      this.updateSize(r);

      return r;
    }

    return s;
  },

  // input: X, the value to delete, and T, the root of the tree from which it should be deleted.
  // output: T, balanced, without the value X.
  delete: function(s, key) {
    if ( ! s ) return s;

    var r = this.compare(s[KEY], key);

    if ( r === 0 ) {
      // If we're a leaf, easy, otherwise reduce to leaf case. 
      if ( ! s[LEFT] && ! s[RIGHT] ) return undefined;

      // TODO: add a unit test to verify that the size
      // adjusting logic is correct here.
      var side = s[LEFT] ? LEFT : RIGHT;

{'fraction_non_alphanumeric': 0.1538659572642238, 'fraction_numerical': 0.007551703424010984, 'mean_word_length': 2.5465611685940353, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2153009', 'n_tokens_mistral': 3998, 'n_tokens_neox': 3843, 'n_words': 1266}