<commit_before># IntervalTree
An implementation of the augmented interval tree algorithm in Ruby

# See also
* description in Wikipedia http://en.wikipedia.org/wiki/Interval_tree
* an implementation in Python by <NAME> http://forrst.com/posts/Interval_Tree_implementation_in_python-e0K (broken link)

# ChanegLog

### 2015-11-02, contribution by <NAME> ( https://github.com/calonso )
* Improved centering
* Fixed searching: With some use cases with very large trees, the library fails to find intervals.
* Added rubygems structure to be able to be pushed as a gem  

### 2013-04-06, contribution by <NAME> ( https://github.com/ssimeonov )
* **Range factory**: The current design allows for Range-compatible elements to be added except for the case where `Tree#ensure_exclusive_end` constructs a Range in a private method. In keeping with good design practices of containers such as Hash, this pull requests allows for a custom range factory to be provided to `Tree#initialize` while maintaining perfect backward compatibility.
Search in empty trees failing
* Adds a nil guard in `Tree#search` to protect against empty tree searches failing.
* **Cosmetic improvements**: Language & whitespace in specs, Gemfile addition, and .gitignore update

# Install

```bash
$ gem install augmented_interval_tree
```

# Usage
See spec/interval_tree_spec.rb for details.
```ruby
require "interval_tree"

itv = [(0...3), (1...4), (3...5),]
t = IntervalTree::Tree.new(itv)
p t.search(2)     #=> [0...3, 1...4]
p t.search(1...4) #=> [0...3, 1...4, 3...5]
```

# Note
Result intervals are always returned
in the "left-closed and right-open" style that can be expressed
by three-dotted Range object literals (first...last)

Two-dotted full-closed intervals "(first..last)" are also accepted and internally
converted to half-closed intervals.

# Copyright
**Author**: MISHIMA, Hiroyuki ( https://github.com/misshie ),  <NAME> ( https://github.com/ssimeonov ), <NAME> ( https://github.com/calonso ).

**Copyright**: (c) 2011-2015 MISHIMA, Hiroyuki; <NAME>; <NAME>  
<commit_msg>correct typos in README.me<commit_after># IntervalTree
An implementation of the augmented interval tree algorithm in Ruby

# See also
* description in Wikipedia http://en.wikipedia.org/wiki/Interval_tree
* an implementation in Python by <NAME> http://forrst.com/posts/Interval_Tree_implementation_in_python-e0K (broken link)

# ChanegLog

### 2015-11-02, contribution by <NAME> ( https://github.com/calonso )
* Improved centering
* Fixed searching: With some use cases with very large trees, the library fails to find intervals.
* Added rubygems structure to be able to be pushed as a gem  

### 2013-04-06, contribution by <NAME> ( https://github.com/ssimeonov )
* **Range factory**: The current design allows for Range-compatible elements to be added except for the case where `Tree#ensure_exclusive_end` constructs a Range in a private method. In keeping with good design practices of containers such as Hash, this pull requests allows for a custom range factory to be provided to `Tree#initialize` while maintaining perfect backward compatibility.
Search in empty trees failing
* Adds a nil guard in `Tree#search` to protect against empty tree searches failing.
* **Cosmetic improvements**: Language & whitespace in specs, Gemfile addition, and .gitignore update

# Install

```bash
$ gem install augmented_interval_tree
```

# Usage
See spec/interval_tree_spec.rb for details.
```ruby
require "interval_tree"

itv = [(0...3), (1...4), (3...5),]
t = IntervalTree::Tree.new(itv)
p t.search(2)     #=> [0...3, 1...4]
p t.search(1...4) #=> [0...3, 1...4, 3...5]
```

# Note
Result intervals are always returned
in the "left-closed and right-open" style that can be expressed
by three-dotted Range object literals `(first...last)`

Two-dotted full-closed intervals `(first..last)` are also accepted and internally
converted to half-closed intervals.

# Copyright
**Author**: MISHIMA, Hiroyuki ( https://github.com/misshie ),  <NAME> ( https://github.com/ssimeonov ), <NAME> ( https://github.com/calonso ).

**Copyright**: (c) 2011-2015 MISHIMA, Hiroyuki; <NAME>; <NAME>  

{'fraction_non_alphanumeric': 0.12085250666020829, 'fraction_numerical': 0.02131266650520707, 'mean_word_length': 4.470198675496689, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 21, 'https://': 10, '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': '1706682', 'n_tokens_mistral': 1286, 'n_tokens_neox': 1195, 'n_words': 465}