/*!
@file self_organizing_search.h
@since 2004/1/6
@note


*/



#ifndef __S34_SELF_ORGANIZING_SEARCH_H_
#define __S34_SELF_ORGANIZING_SEARCH_H_


namespace stx{

/*
 * 自己組織化検索 self-organizing-search
 * その1 : ひとつ手前の要素と交換
 */
template<typename ForwardIterator, typename T>
ForwardIterator 
find_and_swap_previous(ForwardIterator first, ForwardIterator last, const T& value) {
  ForwardIterator found = std::find(first, last, value);
  if ( found != last && found != first ) {
    ForwardIterator swap = found; --swap;
    std::iter_swap(found,swap);
    return swap;
  }
  return found;
}

template<typename ForwardIterator, typename Predicate>
ForwardIterator 
find_and_swap_previous_if(ForwardIterator first, ForwardIterator last, Predicate pred) {
  ForwardIterator found = std::find_if(first, last, pred);
  if ( found != last && found != first ) {
    ForwardIterator swap = found; --swap;
    std::iter_swap(found,swap);
    return swap;
  }
  return found;
}

/*
 * 自己組織化検索 self-organizing-search
 * その2 : 先頭の要素との間でrotate
 */
template<typename ForwardIterator, typename T>
ForwardIterator 
find_and_rotate(ForwardIterator first, ForwardIterator last, const T& value) {
  ForwardIterator found = std::find(first, last, value);
  if ( found != last && found != first ) {
    ForwardIterator limit = found; ++limit;
    std::rotate(first, found, limit);
    return first;    
  }
  return found;
}

template<typename ForwardIterator, typename Predicate>
ForwardIterator
find_and_rotate_if(ForwardIterator first, ForwardIterator last, Predicate pred) {
  ForwardIterator found = std::find_if(first, last, pred);
  if ( found != last && found != first ) {
    ForwardIterator limit = found; ++limit;
    std::rotate(first, found, limit);
    return first;    
  }
  return found;
}

/*
 * 自己組織化検索 self-organizing-search
 * その2 : 先頭の要素との間でrotate
 */
template<typename Container, typename T>
Container::iterator 
find_and_rotate_container(Container& container, Container::iterator first, Container::iterator last, const T& value) {
  Container::iterator found = std::find(first, last, value);
  if ( found != last && found != first ) {
    Container::value_type value = *found;
    container.erase(found);
    container.insert(container.begin(), value);
    return container.begin();
  }
  return found;
}

template<typename Container, typename Predicate>
Container::iterator 
find_and_rotate_container_if(Container& container, Container::iterator first, Container::iterator last, Predicate pred) {
  Container::iterator found = std::find_if(first, last, pred);
  if ( found != last && found != first ) {
    Container::value_type value = *found;
    container.erase(found);
    container.insert(container.begin(), value);
    return container.begin();
  }
  return found;
}


}//end of namespace


#endif //end of include once
