<commit_before>/**
* @license
* Copyright <NAME> 2018 All Rights Reserved.
*
* Use of this source code is governed by an MIT-style license that can be
* found in the LICENSE file at https://github.com/larrydiamond/typescriptcollectionsframework/LICENSE
*/

import {AllFieldCollectable} from "./AllFieldCollectable";
import {ArrayList} from "./ArrayList";
import {BasicIteratorResult} from "./BasicIteratorResult";
import {BasicMapEntry} from "./BasicMapEntry";
import {Collectable} from "./Collectable";
import {Collections} from "./Collections";
import {Comparator} from "./Comparator";
import {Consumer} from "./Consumer";
import {ImmutableCollection} from "./ImmutableCollection";
import {ImmutableMap} from "./ImmutableMap";
import {ImmutableSet} from "./ImmutableSet";
import {JIterator} from "./JIterator";
import {JSet} from "./JSet";
import {LinkedList} from "./LinkedList";
import {List} from "./List";
import {MapEntry} from "./MapEntry";
import {NavigableMap} from "./NavigableMap";
import {NavigableSet} from "./NavigableSet";

export class NavigableHashImpl<K,V> {
  private head:ArrayList<NavigableHashNode<K,V>> = null;
  private height:number = 3;
  private mapComparator:Comparator<K> = null;
  private mapCollectable:Collectable<K> = null;
  private numberElements: number = 0.0;
  private NavigableHashNodeComparator:Comparator<NavigableHashNode<K,V>> = null;
  private NavigableHashNodeCollectable:Collectable<NavigableHashNode<K,V>> = null;

  private hashData:ArrayList<List<NavigableHashNode<K,V>>> = null;

  constructor(iComparator:Comparator<K>, private initialElements:ImmutableMap<K, V> = null, private iInitialCapacity:number=20, private iLoadFactor:number=0.75) {
    this.mapComparator = iComparator;
    this.NavigableHashNodeComparator = new NavigableHashNodeComparator<K,V>(this.mapComparator);
    this.mapCollectable = Collections.collectableFromComparator(iComparator);
    this.NavigableHashNodeCollectable = new NavigableHashNodeCollectable<K,V>(this.mapCollectable);

    this.head = new ArrayList<NavigableHashNode<K,V>>(this.NavigableHashNodeCollectable);
    for (let loop:number = 0; loop < this.height; loop++) {
      this.head.add (null);
    }



  }

  public getNavigableHashNodeComparator() : Comparator<NavigableHashNode<K,V>> { return this.NavigableHashNodeComparator; }
  public getNavigableHashNodeCollectable() : Collectable<NavigableHashNode<K,V>> { return this.NavigableHashNodeCollectable; }

/*

  public validateDisplay () : boolean {
    console.log ("NavigableHashImpl::ValidateDisplay - Size of NavigableHashMap = " + this.numberElements);
    let count : number = 0;
    let tmp : NavigableHashNode<K,V> = this.firstEntry();
    while ((tmp !== null) && (tmp !== undefined)) {
      console.log ("NodeList " + JSON.stringify(tmp.getKey()) + " - " + JSON.stringify(tmp.getValue()));
      tmp = tmp.getNextNodeArray().get (0);
      count++;
    }

    for (let loop:number = 0.0; loop < this.head.size(); loop++) {
      const hn : NavigableHashNode<K,V> = this.head.get(loop);
      if ((hn !== null) && (hn !== undefined)) {
        console.log ("Head" + loop + " " + JSON.stringify(hn.getKey()) + " - " + JSON.stringify(hn.getValue()));
      }
    }

    tmp = this.firstEntry();
    while ((tmp !== null) && (tmp !== undefined)) {
      console.log ("Node " + JSON.stringify(tmp.getKey()) + " - " + JSON.stringify(tmp.getValue()) + " " + tmp.getLastNodeArray().size() + " " + tmp.getNextNodeArray().size());
      for (let loop:number = 0.0; loop < this.head.size(); loop++) {
        const ln : NavigableHashNode<K,V> = tmp.getLastNodeArray().get(loop);
        if ((ln !== null) && (ln !== undefined)) {
          console.log ("Last" + loop + " " + JSON.stringify(ln.getKey()) + " - " + JSON.stringify(ln.getValue()));
        }
      }
      for (let loop:number = 0.0; loop < this.head.size(); loop++) {
        const nn : NavigableHashNode<K,V> = tmp.getNextNodeArray().get(loop);
        if ((nn !== null) && (nn !== undefined)) {
          console.log ("Next" + loop + " " + JSON.stringify(nn.getKey()) + " - " + JSON.stringify(nn.getValue()));
        }
      }
      tmp = tmp.getNextNodeArray().get (0);
    }


    // each of the head elements needs to be at least as big as the prior element or null
    for (let loop:number = 1.0; loop < this.head.size() - 1.0; loop++) {
      const lower : NavigableHashNode<K,V> = this.head.get (Math.round (loop - 1.0));
      const higher : NavigableHashNode<K,V> = this.head.get (loop);
      if ((lower !== null) && (lower !== undefined) && (higher !== null) && (higher !== undefined)) {
        const cmp:number = this.mapComparator.compare(lower.getKey(), higher.getKey());
        if (cmp === 1) {
          console.log ("Head elements out of order");
          return false;
        }
      }
    }
    while ((tmp !== null) && (tmp !== undefined)) {
      const next : NavigableHashNode<K,V> = this.nextHigherNode(tmp);
      if ((next !== null) && (next !== undefined)) {
        if ((tmp.getNextNodeArray() === null) || (tmp.getNextNodeArray() === undefined)) {
          console.log ("next node array null");
          return false;
        }
        if ((tmp.getLastNodeArray() === null) || (tmp.getLastNodeArray() === undefined)) {
          console.log ("last node array null");
          return false;
        }
        console.log (JSON.stringify(next.getKey()) + " - " + JSON.stringify(next.getValue()));
        count++;
        const prev : NavigableHashNode<K,V> = next.getLastNodeArray().get (0);
        if (prev !== null) {
          const cmp:number = this.mapComparator.compare(prev.getKey(), tmp.getKey());
          if (cmp !== 0) {
            console.log ("Last node doesnt match " + next.getKey() + " " + tmp.getKey() + " " + prev.getKey());
            return false;
          }
        }
      }
      tmp = next;
    }
    console.log ("End::Size of NavigableHashMap = " + this.numberElements + " found " + count);
    if (this.numberElements === count) {
      return true;
    } else {
      console.log ("Inconsistent size of display NavigableHashMap = " + this.numberElements + " found " + count);
      return false;
    }
  }

*/

  public validate () : boolean {
    let count : number = 0.0;

    let tmp : NavigableHashNode<K,V> = this.firstEntry();
    if ((tmp !== null) && (tmp !== undefined)) {
      count = 1.0;
    }
    // each of the head elements needs to be at least as big as the prior element or null
    for (let loop:number = 1.0; loop < this.head.size() - 1.0; loop++) {
      const lower : NavigableHashNode<K,V> = this.head.get (Math.round (loop - 1.0));
      const higher : NavigableHashNode<K,V> = this.head.get (loop);
      if ((lower !== null) && (lower !== undefined) && (higher !== null) && (higher !== undefined)) {
        const cmp:number = this.mapComparator.compare(lower.getKey(), higher.getKey());
        if (cmp === 1) {
          console.log ("Head elements out of order");
          return false;
        }
      }
    }

    while ((tmp !== null) && (tmp !== undefined)) {
      const next : NavigableHashNode<K,V> = this.nextHigherNode(tmp);
      if ((next !== null) && (next !== undefined)) {
        if ((tmp.getNextNodeArray() === null) || (tmp.getNextNodeArray() === undefined)) {
          console.log ("next node array null");
          return false;
        }
        if ((tmp.getLastNodeArray() === null) || (tmp.getLastNodeArray() === undefined)) {
          console.log ("last node array null");
          return false;
        }
        const prev : NavigableHashNode<K,V> = next.getLastNodeArray().get (0);
        if (prev !== null) {
          const cmp:number = this.mapComparator.compare(prev.getKey(), tmp.getKey());
          if (cmp !== 0) {
            console.log ("Last node doesnt match " + next.getKey() + " " + tmp.getKey() + " " + prev.getKey());
            return false;
          }
        }
        count = count + 1.0;
      }
      tmp = next;
    }
    if (this.numberElements === count) {
      return true;
    } else {
      console.log ("Inconsistent size of NavigableHashMap = " + this.numberElements + " found " + count);
      return false;
    }
  }

  /**
  * Removes the mapping for this key from this Map if present.
  * @param {K} key key for which mapping should be removed
  * @return {V} the previous value associated with key, or null if there was no mapping for key. (A null return can also indicate that the map previously associated null with key.)
  */
  public remove (key:K) : V {
    const tmp : NavigableHashNode<K,V> = this.getEntry (key);
    if ((tmp === null) || (tmp === undefined)) {
      return null;
    }
    this.removeElement (tmp);
    return tmp.getValue();
  }

  /**
  * Removes this node from the Map
  * @param {MapEntry<K,V>} node node to remove
  */
  public removeElement (node:NavigableHashNode<K,V>) : void {
    const size : number = node.getNextNodeArray().size();
    const lna:ArrayList<NavigableHashNode<K,V>> = node.getLastNodeArray();
    const nna:ArrayList<NavigableHashNode<K,V>> = node.getNextNodeArray();
    for (let loop:number = 0; loop < size; loop++) {
      const ln:NavigableHashNode<K,V> = lna.get (loop);
      const nn:NavigableHashNode<K,V> = nna.get (loop);
<commit_msg>document out validation method<commit_after>/**
* @license
* Copyright <NAME> 2018 All Rights Reserved.
*
* Use of this source code is governed by an MIT-style license that can be
* found in the LICENSE file at https://github.com/larrydiamond/typescriptcollectionsframework/LICENSE
*/

import {AllFieldCollectable} from "./AllFieldCollectable";
import {ArrayList} from "./ArrayList";
import {BasicIteratorResult} from "./BasicIteratorResult";
import {BasicMapEntry} from "./BasicMapEntry";
import {Collectable} from "./Collectable";
import {Collections} from "./Collections";
import {Comparator} from "./Comparator";
import {Consumer} from "./Consumer";
import {ImmutableCollection} from "./ImmutableCollection";
import {ImmutableMap} from "./ImmutableMap";
import {ImmutableSet} from "./ImmutableSet";
import {JIterator} from "./JIterator";
import {JSet} from "./JSet";
import {LinkedList} from "./LinkedList";
import {List} from "./List";
import {MapEntry} from "./MapEntry";
import {NavigableMap} from "./NavigableMap";
import {NavigableSet} from "./NavigableSet";

export class NavigableHashImpl<K,V> {
  private head:ArrayList<NavigableHashNode<K,V>> = null;
  private height:number = 3;
  private mapComparator:Comparator<K> = null;
  private mapCollectable:Collectable<K> = null;
  private numberElements: number = 0.0;
  private NavigableHashNodeComparator:Comparator<NavigableHashNode<K,V>> = null;
  private NavigableHashNodeCollectable:Collectable<NavigableHashNode<K,V>> = null;

  private hashData:ArrayList<List<NavigableHashNode<K,V>>> = null;

  constructor(iComparator:Comparator<K>, private initialElements:ImmutableMap<K, V> = null, private iInitialCapacity:number=20, private iLoadFactor:number=0.75) {
    this.mapComparator = iComparator;
    this.NavigableHashNodeComparator = new NavigableHashNodeComparator<K,V>(this.mapComparator);
    this.mapCollectable = Collections.collectableFromComparator(iComparator);
    this.NavigableHashNodeCollectable = new NavigableHashNodeCollectable<K,V>(this.mapCollectable);

    this.head = new ArrayList<NavigableHashNode<K,V>>(this.NavigableHashNodeCollectable);
    for (let loop:number = 0; loop < this.height; loop++) {
      this.head.add (null);
    }



  }

  public getNavigableHashNodeComparator() : Comparator<NavigableHashNode<K,V>> { return this.NavigableHashNodeComparator; }
  public getNavigableHashNodeCollectable() : Collectable<NavigableHashNode<K,V>> { return this.NavigableHashNodeCollectable; }

/*

  public validateDisplay () : boolean {
    console.log ("NavigableHashImpl::ValidateDisplay - Size of NavigableHashMap = " + this.numberElements);
    let count : number = 0;
    let tmp : NavigableHashNode<K,V> = this.firstEntry();
    while ((tmp !== null) && (tmp !== undefined)) {
      console.log ("NodeList " + JSON.stringify(tmp.getKey()) + " - " + JSON.stringify(tmp.getValue()));
      tmp = tmp.getNextNodeArray().get (0);
      count++;
    }

    for (let loop:number = 0.0; loop < this.head.size(); loop++) {
      const hn : NavigableHashNode<K,V> = this.head.get(loop);
      if ((hn !== null) && (hn !== undefined)) {
        console.log ("Head" + loop + " " + JSON.stringify(hn.getKey()) + " - " + JSON.stringify(hn.getValue()));
      }
    }

    tmp = this.firstEntry();
    while ((tmp !== null) && (tmp !== undefined)) {
      console.log ("Node " + JSON.stringify(tmp.getKey()) + " - " + JSON.stringify(tmp.getValue()) + " " + tmp.getLastNodeArray().size() + " " + tmp.getNextNodeArray().size());
      for (let loop:number = 0.0; loop < this.head.size(); loop++) {
        const ln : NavigableHashNode<K,V> = tmp.getLastNodeArray().get(loop);
        if ((ln !== null) && (ln !== undefined)) {
          console.log ("Last" + loop + " " + JSON.stringify(ln.getKey()) + " - " + JSON.stringify(ln.getValue()));
        }
      }
      for (let loop:number = 0.0; loop < this.head.size(); loop++) {
        const nn : NavigableHashNode<K,V> = tmp.getNextNodeArray().get(loop);
        if ((nn !== null) && (nn !== undefined)) {
          console.log ("Next" + loop + " " + JSON.stringify(nn.getKey()) + " - " + JSON.stringify(nn.getValue()));
        }
      }
      tmp = tmp.getNextNodeArray().get (0);
    }


    // each of the head elements needs to be at least as big as the prior element or null
    for (let loop:number = 1.0; loop < this.head.size() - 1.0; loop++) {
      const lower : NavigableHashNode<K,V> = this.head.get (Math.round (loop - 1.0));
      const higher : NavigableHashNode<K,V> = this.head.get (loop);
      if ((lower !== null) && (lower !== undefined) && (higher !== null) && (higher !== undefined)) {
        const cmp:number = this.mapComparator.compare(lower.getKey(), higher.getKey());
        if (cmp === 1) {
          console.log ("Head elements out of order");
          return false;
        }
      }
    }
    while ((tmp !== null) && (tmp !== undefined)) {
      const next : NavigableHashNode<K,V> = this.nextHigherNode(tmp);
      if ((next !== null) && (next !== undefined)) {
        if ((tmp.getNextNodeArray() === null) || (tmp.getNextNodeArray() === undefined)) {
          console.log ("next node array null");
          return false;
        }
        if ((tmp.getLastNodeArray() === null) || (tmp.getLastNodeArray() === undefined)) {
          console.log ("last node array null");
          return false;
        }
        console.log (JSON.stringify(next.getKey()) + " - " + JSON.stringify(next.getValue()));
        count++;
        const prev : NavigableHashNode<K,V> = next.getLastNodeArray().get (0);
        if (prev !== null) {
          const cmp:number = this.mapComparator.compare(prev.getKey(), tmp.getKey());
          if (cmp !== 0) {
            console.log ("Last node doesnt match " + next.getKey() + " " + tmp.getKey() + " " + prev.getKey());
            return false;
          }
        }
      }
      tmp = next;
    }
    console.log ("End::Size of NavigableHashMap = " + this.numberElements + " found " + count);
    if (this.numberElements === count) {
      return true;
    } else {
      console.log ("Inconsistent size of display NavigableHashMap = " + this.numberElements + " found " + count);
      return false;
    }
  }

*/

/*
  public validate () : boolean {
    let count : number = 0.0;

    let tmp : NavigableHashNode<K,V> = this.firstEntry();
    if ((tmp !== null) && (tmp !== undefined)) {
      count = 1.0;
    }
    // each of the head elements needs to be at least as big as the prior element or null
    for (let loop:number = 1.0; loop < this.head.size() - 1.0; loop++) {
      const lower : NavigableHashNode<K,V> = this.head.get (Math.round (loop - 1.0));
      const higher : NavigableHashNode<K,V> = this.head.get (loop);
      if ((lower !== null) && (lower !== undefined) && (higher !== null) && (higher !== undefined)) {
        const cmp:number = this.mapComparator.compare(lower.getKey(), higher.getKey());
        if (cmp === 1) {
          console.log ("Head elements out of order");
          return false;
        }
      }
    }

    while ((tmp !== null) && (tmp !== undefined)) {
      const next : NavigableHashNode<K,V> = this.nextHigherNode(tmp);
      if ((next !== null) && (next !== undefined)) {
        if ((tmp.getNextNodeArray() === null) || (tmp.getNextNodeArray() === undefined)) {
          console.log ("next node array null");
          return false;
        }
        if ((tmp.getLastNodeArray() === null) || (tmp.getLastNodeArray() === undefined)) {
          console.log ("last node array null");
          return false;
        }
        const prev : NavigableHashNode<K,V> = next.getLastNodeArray().get (0);
        if (prev !== null) {
          const cmp:number = this.mapComparator.compare(prev.getKey(), tmp.getKey());
          if (cmp !== 0) {
            console.log ("Last node doesnt match " + next.getKey() + " " + tmp.getKey() + " " + prev.getKey());
            return false;
          }
        }
        count = count + 1.0;
      }
      tmp = next;
    }
    if (this.numberElements === count) {
      return true;
    } else {
      console.log ("Inconsistent size of NavigableHashMap = " + this.numberElements + " found " + count);
      return false;
    }
  }
*/

  /**
  * Removes the mapping for this key from this Map if present.
  * @param {K} key key for which mapping should be removed
  * @return {V} the previous value associated with key, or null if there was no mapping for key. (A null return can also indicate that the map previously associated null with key.)
  */
  public remove (key:K) : V {
    const tmp : NavigableHashNode<K,V> = this.getEntry (key);
    if ((tmp === null) || (tmp === undefined)) {
      return null;
    }
    this.removeElement (tmp);
    return tmp.getValue();
  }

  /**
  * Removes this node from the Map
  * @param {MapEntry<K,V>} node node to remove
  */
  public removeElement (node:NavigableHashNode<K,V>) : void {
    const size : number = node.getNextNodeArray().size();
    const lna:ArrayList<NavigableHashNode<K,V>> = node.getLastNodeArray();
    const nna:ArrayList<NavigableHashNode<K,V>> = node.getNextNodeArray();
    for (let loop:number = 0; loop < size; loop++) {
      const ln:NavigableHashNode<K,V> = lna.get (loop);
      const nn:NavigableHashNode<K,V> = nna.get (loop);

{'fraction_non_alphanumeric': 0.16, 'fraction_numerical': 0.005060565275908479, 'mean_word_length': 3.0576671035386633, 'pattern_counts': {'":': 0, '<': 107, '<?xml version=': 0, '>': 93, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, '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': '3473451', 'n_tokens_mistral': 5732, 'n_tokens_neox': 5700, 'n_words': 1425}