<commit_before># -*- coding: utf-8 -*-

from collections import deque


class SegmentTree(object):
    def __init__(self, size, elements=None):
        self._rmqs = {}
        self._size = size
        self._leaves = {}

        if not elements:
            self._elements = [None] * size
        else:
            if len(elements) != size:
                print 'Size mismatch'   # Or throw error
                return
            self._elements = elements

        self._build(0, 0, size - 1)

    def __str__(self):
        """Return a string representation of the segment tree."""

        queue = deque()
        items = []

        queue.append((0, 0, self._size - 1))
        while queue:
            range_index, start, end = queue.popleft()
            items.append((start, end, self._rmqs[range_index]))

            if start != end:
                # If not a left node, add the left and right child to the queue.
                # Note that every non-leaf node is complete i.e. it has both the
                # left and the right child.
                mid = (start + end) / 2
                left_range_index = 2 * range_index + 1
                right_range_index = left_range_index + 1
                queue.append((left_range_index, start, mid))
                queue.append((right_range_index, mid + 1, end))

        sg_tree_str = ''
        for s, e, m in items:
            sg_tree_str = \
                '{0}\nstart={1}, end={2}, minimum={3}'.format(sg_tree_str,
                                                            s, e, m)
        return sg_tree_str

    def update(self, index, element):
        """Update an element at the specified index."""

        if index < 0 or index > self._size - 1:
            print 'Invalid index'  # Or throw error
            return

        range_index = self._leaves[index]
        self._elements[index] = element
        self._rmqs[range_index] = element

        while True:
            parent_range_index = self._parent_range_index(range_index)
            if parent_range_index < 0:<commit_msg>added module header and license info<commit_after># -*- coding: utf-8 -*-

"""
    zahlen.ds.tree.segment_tree
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~

    This module implements the Segment Tree data structure.

    :copyright: (c) 2014 by <NAME>.
    :license: MIT, see LICENSE for more details.
"""

from collections import deque


class SegmentTree(object):
    def __init__(self, size, elements=None):
        self._rmqs = {}
        self._size = size
        self._leaves = {}

        if not elements:
            self._elements = [None] * size
        else:
            if len(elements) != size:
                print 'Size mismatch'   # Or throw error
                return
            self._elements = elements

        self._build(0, 0, size - 1)

    def __str__(self):
        """Return a string representation of the segment tree."""

        queue = deque()
        items = []

        queue.append((0, 0, self._size - 1))
        while queue:
            range_index, start, end = queue.popleft()
            items.append((start, end, self._rmqs[range_index]))

            if start != end:
                # If not a left node, add the left and right child to the queue.
                # Note that every non-leaf node is complete i.e. it has both the
                # left and the right child.
                mid = (start + end) / 2
                left_range_index = 2 * range_index + 1
                right_range_index = left_range_index + 1
                queue.append((left_range_index, start, mid))
                queue.append((right_range_index, mid + 1, end))

        sg_tree_str = ''
        for s, e, m in items:
            sg_tree_str = \
                '{0}\nstart={1}, end={2}, minimum={3}'.format(sg_tree_str,
                                                              s, e, m)
        return sg_tree_str

    def update(self, index, element):
        """Update an element at the specified index."""

        if index < 0 or index > self._size - 1:
            print 'Invalid index'  # Or throw error
            return

        range_index = self._leaves[index]
        self._elements[index] = element
        self._rmqs[range_index] = element

        while True:
            parent_range_index = self._parent_range_index(range_index)
            if parent_range_index < 0:
{'fraction_non_alphanumeric': 0.10331428571428572, 'fraction_numerical': 0.0096, 'mean_word_length': 1.6063132817153067, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4297202', 'n_tokens_mistral': 1251, 'n_tokens_neox': 1166, 'n_words': 369}