/*******************************************************************************
+
+  LEDA 3.5
+
+  _sortseq.h
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/

#ifndef _LEDA_SORTSEQ_H
#define _LEDA_SORTSEQ_H

#if !defined(LEDA_ROOT_INCL_ID)
#define LEDA_ROOT_INCL_ID 350009
#include <LEDA/REDEFINE_NAMES.h>
#endif

#include <LEDA/sortseq.h>


//------------------------------------------------------------------------------
//
// Sorted sequences with implementation parameter:
//
//   _sortseq<K,I,seq_impl> 
//
//------------------------------------------------------------------------------

/*{\Manpage {_sortseq} {K,I,impl} {Sorted Sequences with Implementation Parameter} }*/

/*{\Mdefinition
An instance of type |\Mname| is a sorted sequence implemented by data type
$impl$. $impl$ must be one of the sorted sequence implementations listed in
section \ref{Implementations Dictionaries} or a user defined data structure
fulfilling the specification given in section \ref{User Implementations
Sorted Sequences}. Note that the key type $K$ must be linearly ordered.
}*/

/*{\Mtext
{\bf Example}\\
Using a sorted sequence implemented by skiplists to list all elements in a 
sequence of strings lying lexicographically between two given search strings.
\begingroup
\ttbig
{\obeyspaces\gdef {\ }}
\ttverbatim

#include <LEDA/_sortseq.h>
#include <LEDA/impl/skiplist.h>

main()
{ 
 _sortseq<string,int,skiplist> S;
 string s1,s2;

 while ( cin >> s1 &&  s1 != "stop" )  S.insert(s1,0);

 while ( cin >> s1 >> s2 )
 { seq_item start = S.locate(s1);
   seq_item stop  = S.locate(s2);
   for (seq_item it = start; it != stop; it = S.succ(it))
      cout << S.key(it) << endl; 
  }

}
\endgroup

}*/



template <class K, class I, class impl> 

#if defined(__NO_TEMPLATE_ARG_BASE__)
class _sortseq : public sortseq<K,I>  { impl* dummy; };
#else

class _sortseq : private virtual impl, public sortseq<K,I>
{

int  key_type_id() const { return LEDA_TYPE_ID(K); }

int  cmp(GenPtr x, GenPtr y) const { return LEDA_COMPARE(K,x,y); }
void clear_key(GenPtr& x)    const { LEDA_CLEAR(K,x); }
void clear_inf(GenPtr& x)    const { LEDA_CLEAR(I,x); }
void copy_key(GenPtr& x)     const { LEDA_COPY(K,x); }
void copy_inf(GenPtr& x)     const { LEDA_COPY(I,x); }
void print_key(GenPtr x)     const { LEDA_PRINT(K,x,cout); }
void print_inf(GenPtr x)     const { LEDA_PRINT(I,x,cout); }

public:

K key(seq_item it) const 
{ return LEDA_CONST_ACCESS(K,impl::key(impl::item(it))); }

I inf(seq_item it) const 
{ return LEDA_CONST_ACCESS(I,impl::inf(impl::item(it))); }

I& operator[](seq_item it)
{ return LEDA_ACCESS(I,impl::inf(impl::item(it))); }

seq_item lookup(const K& y) const 
{ return (seq_item)impl::lookup(leda_cast(y)); }

seq_item locate(const K& y) const 
{ return (seq_item)impl::locate(leda_cast(y)); }

seq_item locate_succ(const K& y) const 
{ return (seq_item)impl::locate_succ(leda_cast(y)); }

seq_item locate_pred(const K& y) const 
{ return (seq_item)impl::locate_pred(leda_cast(y)); }

seq_item min() const { return (seq_item)impl::min(); }
seq_item max() const { return (seq_item)impl::max(); }

seq_item succ(seq_item x) const { return (seq_item)impl::succ(impl::item(x)); }
seq_item succ(const K& y) const { return locate_succ(y); }

seq_item pred(seq_item x) const { return (seq_item)impl::pred(impl::item(x)); }
seq_item pred(const K& y) const { return locate_pred(y); }

seq_item insert(const K& y, const I& x)
{ return (seq_item)impl::insert(leda_cast(y),leda_cast(x));}

seq_item insert_at(seq_item it, const K& y, const I& x)
{ return (seq_item)impl::insert_at_item(impl::item(it),leda_cast(y),leda_cast(x));}

void reverse_items(seq_item it1, seq_item it2) 
{ impl::reverse_items(impl::item(it1),impl::item(it2)); }

void flip_items(seq_item it1, seq_item it2) { reverse_items(it1,it2); }

void del(const K& y) { impl::del(leda_cast(y)); }

void del_item(seq_item it) { impl::del_item(impl::item(it)); }

void change_inf(seq_item it, const I& i) 
{ impl::change_inf(impl::item(it),leda_cast(i));}

int  size()  const { return impl::size(); }
bool empty() const { return (size()==0) ? true : false; }
void clear() { impl::clear(); }

void split(seq_item it,sortseq<K,I>& S1,sortseq<K,I>& S2)
{ impl::split_at_item(impl::item(it),*(impl*)&S1,*(impl*)&S2); }

sortseq<K,I>& conc(sortseq<K,I>& S)
{ impl::conc(*(impl*)&S); return *this; }

 _sortseq() {}
 _sortseq(const _sortseq<K,I,impl>& S) : impl(S) {}
 _sortseq<K,I,impl>& operator=(const _sortseq<K,I,impl>& S)
 { impl::operator=(S); return *this; }
~_sortseq() { impl::clear(); }

};

#endif


#if LEDA_ROOT_INCL_ID == 350009
#undef LEDA_ROOT_INCL_ID
#include <LEDA/UNDEFINE_NAMES.h>
#endif
#endif
