<commit_before>///////////////////////////////////////////////////////////////////////////////
//                       Copyright (c) 2011 - 2012 by                        //
//                                <NAME>                                //
//                           (All rights reserved)                           //
///////////////////////////////////////////////////////////////////////////////
//                                                                           //
// FILE:    PersistentSkipList.cpp                                           //
//                                                                           //
// MODULE:  Persistent Skip List                                             //
//                                                                           //
// NOTES:   None.                                                            //
//                                                                           //
///////////////////////////////////////////////////////////////////////////////
#ifndef PERSISTENTSKIPLIST_CPP
#define PERSISTENTSKIPLIST_CPP

#include "PersistentSkipList.hpp"

using namespace persistent_skip_list;

///////////////////////////////////////////////////////////////////////////////
// PersistentSkipList Implementation                                         //
///////////////////////////////////////////////////////////////////////////////

template <class T>
PersistentSkipList<T>::PersistentSkipList(int nodeSize)
  : node_size(nodeSize), present(0), head(), tail(), data_set()
{
  SmartPointer<ListNode<T> > negInf(new ListNode<T>(1,false));
  SmartPointer<ListNode<T> > posInf(new ListNode<T>(1,true));
  head.insert( pair<int,SmartPointer<ListNode<T> > >(0,negInf) );
  tail.insert( pair<int,SmartPointer<ListNode<T> > >(0,posInf) );
  // set next on negInf to posInf
  TSA* newNext = new TSA(0,1);
  newNext->setElement(0,posInf);
  negInf->addNext(newNext);
}

template <class T>
PersistentSkipList<T>::~PersistentSkipList() {
}

template <class T>
int PersistentSkipList<T>::getPresent() const {
  assert(this != NULL);
  return present;
}

template <class T>
PersistentSkipList<T>& PersistentSkipList<T>::operator++() {
  incTime();
  return this;
}

template <class T>
void PersistentSkipList<T>::incTime() {
  assert(this != NULL);
  ++present;
}

template <class T>
void PersistentSkipList<T>::drawPresent() {
  assert(this != NULL);
  draw(getPresent());
}

template <class T>
void PersistentSkipList<T>::draw(int t) {
  assert(this != NULL);
  assert(t >= 0);
  cout << "Drawing skip list at time " << t << "..." << endl;
  if(empty(t)) {
    cout << "NULL" << endl;
    return;
  }
  for(int i = 0; i < getHeight(t); ++i) {
    PSLIterator<T> next = begin(t,i);
    
    cout << "Height: " << i+1 << endl;
    
    while(next != end(t)) {
      cout << "Node(data=" << *next
	   << ",height=" << next.getHeight() << ")" << endl;
      ++next;
    }
  }
}

template <class T>
int PersistentSkipList<T>::addHead(SmartPointer<ListNode<T> > new_head) {
  assert(this != NULL);
  assert(new_head != NULL);
  // delete old head if exists
  if(head.count(present) > 0)
    head.erase(present); // shouldn't leak using smart pointer
  // save the new head
  head.insert( pair< int, SmartPointer<ListNode<T> > >(present,new_head) );
  // success
  return 0;
}

template <class T>
SmartPointer<ListNode<T> >& PersistentSkipList<T>::getHead(int t) {
  // reverse linear search from starting time
  while(head.count(t) == 0)
    --t;
  return head[t];
}

template <class T>
int PersistentSkipList<T>::addTail(SmartPointer<ListNode<T> > new_tail) {
  assert(this != NULL);
  assert(new_tail != NULL);
  // delete old head if exists
  if(tail.count(present) > 0)
    tail.erase(present); // shouldn't leak using smart pointer
  // save the new head
  tail.insert( pair< int, SmartPointer<ListNode<T> > >(present,new_tail) );
  // success
  return 0;
}

template <class T>
SmartPointer<ListNode<T> >& PersistentSkipList<T>::getTail(int t) {
  // reverse linear search from starting time
  while(tail.count(t) == 0)
    --t;
  return tail[t];
}

template <class T>
void PersistentSkipList<T>::buildHeadAndTail(int new_height) {
  assert(new_height > getHeight(getPresent()));
  int present = getPresent();
  SmartPointer<ListNode<T> > old_head = getHead(present);
  SmartPointer<ListNode<T> > old_tail = getTail(present);
  int old_height = old_head->getHeight();
  assert(new_height > old_height);
  assert(old_height == old_tail->getHeight());
  SmartPointer<ListNode<T> > new_head(new ListNode<T>(new_height,false));
  SmartPointer<ListNode<T> > new_tail(new ListNode<T>(new_height,true));
  assert(new_head->getHeight() == new_tail->getHeight());
  TSA* new_next = new TSA(present,new_height);
  // make the tail the new next above the old height
  while(--new_height >= old_height) {
    new_next->setElement(new_height,new_tail);
  }
  while(new_height >= 0) {
    SmartPointer<ListNode<T> > next_node =
      old_head->getNext(present)->getElement(new_height);
    if(next_node == old_tail)
      new_next->setElement(new_height,new_tail);
    else
      new_next->setElement(new_height,next_node);
    --new_height;
  }
  new_head->addNext(new_next);
  addHead(new_head);
  // make all the nodes which pointed to the old tail point to the new tail
  --old_height;
  while(old_height >= 0) {
    int end = old_height;
    while(end > 0 &&
	  old_tail->getIncoming(end-1) == old_tail->getIncoming(old_height))
      --end;
    ListNode<T>* toChange = old_tail->getIncoming(old_height);
    if(old_head == toChange) {
      old_height = end-1;
      continue;
    }
    new_next = new TSA(present,
		       toChange->getHeight(),
		       *(toChange->getNext(present)));
    while(old_height >= end) {
      new_next->setElement(old_height,new_tail);
      new_tail->setIncoming(old_height,toChange);
      --old_height;
    }
    toChange->addNext(new_next);
  }
  addTail(new_tail);
}

template < class T >
PSLIterator<T> PersistentSkipList<T>::begin(int t, int h) {
  return ++(PSLIterator<T>(getHead(t),t,h));
}

template < class T >
PSLIterator<T> PersistentSkipList<T>::end(int t) {
  return PSLIterator<T>(getTail(t),t);
}

template < class T >
PSLIterator<T> PersistentSkipList<T>::find(const T& toFind, int t) {
  PSLIterator<T> iter = PSLIterator<T>(getHead(t),t,getHeight(t)-1);
  PSLIterator<T> next = iter.getNext();
  const PSLIterator<T> end = this->end(t);
  while( iter.getSearchHeight() > 0 || next != end ) {
    // loop invariant: we have already determined the value of iter
    //                 precedes the data for which we are searching.
    if(next <= toFind && next != end) {
      assert(iter.getSearchHeight() < next.getHeight());
      iter.next();
    } else if(next > toFind && iter.getSearchHeight() > 0) {
      iter.down();
    } else {
      return iter;
    }
    next = iter.getNext();
  }
  return iter;
}

template < class T >
int PersistentSkipList<T>::getHeight(int t) {
  return (getHead(t))->getHeight();
}

template < class T >
bool PersistentSkipList<T>::empty(void) {
  return empty(getPresent());
}

template < class T >
bool PersistentSkipList<T>::empty(int t) {
  return begin(t) == end(t);<commit_msg>Fixed search error<commit_after>///////////////////////////////////////////////////////////////////////////////
//                       Copyright (c) 2011 - 2012 by                        //
//                                <NAME>                                //
//                           (All rights reserved)                           //
///////////////////////////////////////////////////////////////////////////////
//                                                                           //
// FILE:    PersistentSkipList.cpp                                           //
//                                                                           //
// MODULE:  Persistent Skip List                                             //
//                                                                           //
// NOTES:   None.                                                            //
//                                                                           //
///////////////////////////////////////////////////////////////////////////////
#ifndef PERSISTENTSKIPLIST_CPP
#define PERSISTENTSKIPLIST_CPP

#include "PersistentSkipList.hpp"

using namespace persistent_skip_list;

///////////////////////////////////////////////////////////////////////////////
// PersistentSkipList Implementation                                         //
///////////////////////////////////////////////////////////////////////////////

template <class T>
PersistentSkipList<T>::PersistentSkipList(int nodeSize)
  : node_size(nodeSize), present(0), head(), tail(), data_set()
{
  SmartPointer<ListNode<T> > negInf(new ListNode<T>(1,false));
  SmartPointer<ListNode<T> > posInf(new ListNode<T>(1,true));
  head.insert( pair<int,SmartPointer<ListNode<T> > >(0,negInf) );
  tail.insert( pair<int,SmartPointer<ListNode<T> > >(0,posInf) );
  // set next on negInf to posInf
  TSA* newNext = new TSA(0,1);
  newNext->setElement(0,posInf);
  negInf->addNext(newNext);
}

template <class T>
PersistentSkipList<T>::~PersistentSkipList() {
}

template <class T>
int PersistentSkipList<T>::getPresent() const {
  assert(this != NULL);
  return present;
}

template <class T>
PersistentSkipList<T>& PersistentSkipList<T>::operator++() {
  incTime();
  return this;
}

template <class T>
void PersistentSkipList<T>::incTime() {
  assert(this != NULL);
  ++present;
}

template <class T>
void PersistentSkipList<T>::drawPresent() {
  assert(this != NULL);
  draw(getPresent());
}

template <class T>
void PersistentSkipList<T>::draw(int t) {
  assert(this != NULL);
  assert(t >= 0);
  cout << "Drawing skip list at time " << t << "..." << endl;
  if(empty(t)) {
    cout << "NULL" << endl;
    return;
  }
  for(int i = 0; i < getHeight(t); ++i) {
    PSLIterator<T> next = begin(t,i);
    
    cout << "Height: " << i+1 << endl;
    
    while(next != end(t)) {
      cout << "Node(data=" << *next
	   << ",height=" << next.getHeight() << ")" << endl;
      ++next;
    }
  }
}

template <class T>
int PersistentSkipList<T>::addHead(SmartPointer<ListNode<T> > new_head) {
  assert(this != NULL);
  assert(new_head != NULL);
  // delete old head if exists
  if(head.count(present) > 0)
    head.erase(present); // shouldn't leak using smart pointer
  // save the new head
  head.insert( pair< int, SmartPointer<ListNode<T> > >(present,new_head) );
  // success
  return 0;
}

template <class T>
SmartPointer<ListNode<T> >& PersistentSkipList<T>::getHead(int t) {
  // reverse linear search from starting time
  while(head.count(t) == 0)
    --t;
  return head[t];
}

template <class T>
int PersistentSkipList<T>::addTail(SmartPointer<ListNode<T> > new_tail) {
  assert(this != NULL);
  assert(new_tail != NULL);
  // delete old head if exists
  if(tail.count(present) > 0)
    tail.erase(present); // shouldn't leak using smart pointer
  // save the new head
  tail.insert( pair< int, SmartPointer<ListNode<T> > >(present,new_tail) );
  // success
  return 0;
}

template <class T>
SmartPointer<ListNode<T> >& PersistentSkipList<T>::getTail(int t) {
  // reverse linear search from starting time
  while(tail.count(t) == 0)
    --t;
  return tail[t];
}

template <class T>
void PersistentSkipList<T>::buildHeadAndTail(int new_height) {
  assert(new_height > getHeight(getPresent()));
  int present = getPresent();
  SmartPointer<ListNode<T> > old_head = getHead(present);
  SmartPointer<ListNode<T> > old_tail = getTail(present);
  int old_height = old_head->getHeight();
  assert(new_height > old_height);
  assert(old_height == old_tail->getHeight());
  SmartPointer<ListNode<T> > new_head(new ListNode<T>(new_height,false));
  SmartPointer<ListNode<T> > new_tail(new ListNode<T>(new_height,true));
  assert(new_head->getHeight() == new_tail->getHeight());
  TSA* new_next = new TSA(present,new_height);
  // make the tail the new next above the old height
  while(--new_height >= old_height) {
    new_next->setElement(new_height,new_tail);
  }
  while(new_height >= 0) {
    SmartPointer<ListNode<T> > next_node =
      old_head->getNext(present)->getElement(new_height);
    if(next_node == old_tail)
      new_next->setElement(new_height,new_tail);
    else
      new_next->setElement(new_height,next_node);
    --new_height;
  }
  new_head->addNext(new_next);
  addHead(new_head);
  // make all the nodes which pointed to the old tail point to the new tail
  --old_height;
  while(old_height >= 0) {
    int end = old_height;
    while(end > 0 &&
	  old_tail->getIncoming(end-1) == old_tail->getIncoming(old_height))
      --end;
    ListNode<T>* toChange = old_tail->getIncoming(old_height);
    if(old_head == toChange) {
      old_height = end-1;
      continue;
    }
    new_next = new TSA(present,
		       toChange->getHeight(),
		       *(toChange->getNext(present)));
    while(old_height >= end) {
      new_next->setElement(old_height,new_tail);
      new_tail->setIncoming(old_height,toChange);
      --old_height;
    }
    toChange->addNext(new_next);
  }
  addTail(new_tail);
}

template < class T >
PSLIterator<T> PersistentSkipList<T>::begin(int t, int h) {
  return ++(PSLIterator<T>(getHead(t),t,h));
}

template < class T >
PSLIterator<T> PersistentSkipList<T>::end(int t) {
  return PSLIterator<T>(getTail(t),t);
}

template < class T >
PSLIterator<T> PersistentSkipList<T>::find(const T& toFind, int t) {
  PSLIterator<T> iter = PSLIterator<T>(getHead(t),t,getHeight(t)-1);
  PSLIterator<T> next = iter.getNext();
  const PSLIterator<T> end = this->end(t);
  while( iter.getSearchHeight() >= 0 || next != end ) {
    // loop invariant: we have already determined the value of iter
    //                 precedes the data for which we are searching.
    if(next <= toFind && next != end) {
      assert(iter.getSearchHeight() < next.getHeight());
      iter.next();
    } else if(next > toFind && iter.getSearchHeight() > 0) {
      iter.down();
    } else {
      return iter;
    }
    next = iter.getNext();
  }
  return iter;
}

template < class T >
int PersistentSkipList<T>::getHeight(int t) {
  return (getHead(t))->getHeight();
}

template < class T >
bool PersistentSkipList<T>::empty(void) {
  return empty(getPresent());
}

template < class T >
bool PersistentSkipList<T>::empty(int t) {
  return begin(t) == end(t);
{'fraction_non_alphanumeric': 0.19350165562913907, 'fraction_numerical': 0.004552980132450331, 'mean_word_length': 2.153578420709158, 'pattern_counts': {'":': 0, '<': 243, '<?xml version=': 0, '>': 247, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 38, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7210735', 'n_tokens_mistral': 4503, 'n_tokens_neox': 4408, 'n_words': 925}