<commit_before>/*

    Copyright <NAME> and <NAME>, 2014

    This file is part of Lasercake.

    Lasercake is free software: you can redistribute it and/or modify
    it under the terms of the GNU Affero General Public License as
    published by the Free Software Foundation, either version 3 of the
    License, or (at your option) any later version.

    Lasercake is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Affero General Public License for more details.

    You should have received a copy of the GNU Affero General Public License
    along with Lasercake.  If not, see <http://www.gnu.org/licenses/>.

*/

#ifndef LASERCAKE_TAIL_DROP_MAP_HPP__
#define LASERCAKE_TAIL_DROP_MAP_HPP__

/*

This is a bizarrely specific data structure that might be useful for the time steward.

It implements only two operations:
void insert (key, value), which inserts an element into the map, and
tail_drop (key), which removes and returns all elements with keys after key, not necessarily in order.

Inserting at the end is O(1) worst case.
Inserting elsewhere is O(1), but incurs a debt of up to O(log n) which will be paid off later by tail_drop.
tail_drop is merely O(number of things returned), plus paying off the debt.

Since the results of tail_drop don't actually need to be sorted,
we delay all or part of the O(log n) cost of sorting for as long as we can,
in the hopes of never having to pay it at all.

There is also discard_head (key), which can be used to save memory by assuring the tail_drop_map that you won't query before key, so it can discard some data that it knows will never be used. However, it does not guarantee that all data before key will be discarded.

*/

template <typename key_type, typename mapped_type>
class tail_drop_map {
private:
  //the "bucket" type is used only for collecting unsorted elements
  //1 at a time, then eventually iterating them and dumping them all out.
  typedef std:: vector bucket;
  typedef std:: pair <key_type, mapped_type> value_type;
  
  struct sorted_element {
    sorted_element (value_type const & value): value (value) {}
    value_type value;
    bucket unsorted_elements_before_or_equal_this;
  };
  std:: vector <sorted_element> sorted_elements;
  bucket unsorted_elements;
  
public:
  void insert (value_type const & value) {
    if (value.first >= sorted_elements.back ().value.first) {<commit_msg>Made some improvements to tail_drop_map<commit_after>/*

    Copyright <NAME> and <NAME>, 2014

    This file is part of Lasercake.

    Lasercake is free software: you can redistribute it and/or modify
    it under the terms of the GNU Affero General Public License as
    published by the Free Software Foundation, either version 3 of the
    License, or (at your option) any later version.

    Lasercake is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Affero General Public License for more details.

    You should have received a copy of the GNU Affero General Public License
    along with Lasercake.  If not, see <http://www.gnu.org/licenses/>.

*/

#ifndef LASERCAKE_TAIL_DROP_MAP_HPP__
#define LASERCAKE_TAIL_DROP_MAP_HPP__

/*

This is a bizarrely specific data structure that might be useful for the time steward.

It implements only two operations:
void insert (key, value), which inserts an element into the map, and
tail_drop (key), which removes and returns all elements with keys after key, not necessarily in order.

Inserting at the end is O(1) amortized.
Inserting elsewhere is O(1), but incurs a debt of O(log n) which will be paid off later by tail_drop.
tail_drop is merely O(number of things returned), plus paying off the debt.

Since the results of tail_drop don't actually need to be sorted,
we delay all or part of the O(log n) cost of sorting for as long as we can,
in the hopes of never having to pay it at all.

There is also discard_head (key), which can be used to save memory 
by assuring the tail_drop_map that you won't query before key, 
so it can discard some data that it knows will never be used. 
However, it does not guarantee that all data before key will be discarded.

*/

template <typename key_type, typename mapped_type>
class tail_drop_map {
private:
  typedef std:: pair <key_type, mapped_type> value_type;
  //the "bucket" type is used only for collecting unsorted elements
  //1 at a time, then eventually iterating them and dumping them all out.
  typedef std:: vector <value_type> bucket;
  
  struct sorted_element {
    sorted_element (value_type const & value): value (value) {}
    value_type value;
    bucket unsorted_elements_before_or_equal_this;
  };
  std:: vector <sorted_element> sorted_elements;
  bucket unsorted_elements;
  
public:
  void insert (value_type const & value) {
    if (value.first >= sorted_elements.back ().value.first) {
{'fraction_non_alphanumeric': 0.05488647581441264, 'fraction_numerical': 0.0031589338598223098, 'mean_word_length': 3.9280155642023344, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 18, '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': '2645226', 'n_tokens_mistral': 1446, 'n_tokens_neox': 1392, 'n_words': 724}