/*******************************************************************************
+
+  LEDA 3.5
+
+  f_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 F_SORTSEQ_H
#define F_SORTSEQ_H 

#include <LEDA/basic.h>
#include <LEDA/impl/f_skiplist.h>

#define IMPL f_skiplist

typedef f_skiplist_item f_seq_item;


/*{\Manpage {f_sortseq} {K,I} {Sorted Sequences} }*/

template<class K, class I>

class f_sortseq : public virtual IMPL {

/*{\Mdefinition
 
An instance |S| of the parameterized data type |f_sortseq| is a sequence of
items (|f_seq_item|). Every item contains a key from a linearly ordered data
type |K|, called the key type of |S|, and an information from a data type |I|,
called the information type  of |S|. The number of items in |S| is called the
size of |S|. A sorted sequence of size zero is called empty. We use
\Litem{ |k|,|i|} to
denote a |f_seq_item| with key |k| and information |i|
(called the information associated with key |k|). 
For each |k| in |K| there is at most one item
\Litem{ |k|,|i|} in |S| and if item \Litem{ |k1|,|i1|}
precedes item \Litem{|k2|,|i2|} in |S| then |k1 < k2|.
 
Sorted sequences are a very powerful data type. They can do everything that
dictionaries and priority queues can do. In addition, they support finger
searches and operations |conc|, |split|, |merge| and |delete_subsequence|.
 
The key type |K| must be linearly ordered. The 
linear order on |K| may change over time subject to the condition 
that the order of the elements that are currently in the
sorted sequence remains stable. More precisely,
whenever an operation (except for |reverse_items|) is applied to a
sorted sequence |S|, the keys of |S| must form an increasing sequence according
to the currently valid linear order on |K|. For operation |reverse_items| this
must hold after the execution of the operation. An application of sorted sequences
where 
the linear order on the keys 
evolves over time is the plane sweep algorithm for line segment
intersection. This algorithm sweeps an arrangement of segments by a
vertical sweep line and keeps the intersected segments in a
sorted sequence sorted
according to the y-coordinates of their intersections with the sweep line. For
intersecting segments this order depends on the position of the sweep line.

Sorted sequences support finger searches. A finger search takes an item |it| 
in a sorted sequence and a key |k| and searches for the 
key starting at the item. The cost of a finger search is proportional to the 
logarithm of the distance of the key from the start of the search. A finger
search does not need to know the sequence containing the item; the search is
performed in the sequence containing the item. The sole role of |S| in a call
|S.finger_search(it,k)| is to provide the type of the sorted sequence; |S| may
or may not be the sequence containing |it|. It must however have the same type
as the sequence containing |it|.

}*/



//int  int_type()              const  {  return LEDA_INT_TYPE(K);  }

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:

f_sortseq(const f_sortseq<K,I>& S1) : IMPL(S1)  { }


/*{\Mcreation S }*/
 
f_sortseq()     { }

/*{\Mcreate
creates an instance |S| of type |\Mname|  and initializes it to the empty
sorted sequence. }*/
 


/*{\Moperations 2.8 4.5 }*/

/*{\Mtext \settowidth{\typewidth}{|f_seq_item|}
          \setlength{\colsep}{1em}
          \addtolength{\typewidth}{\colsep}
          \computewidths}*/


virtual K  key(f_seq_item it) const { return LEDA_ACCESS(K,IMPL::key(it)); }

/*{\Mop        returns the key of item |it|. \\
              \precond |it| is an item in |S|.}*/


virtual I  inf(f_seq_item it) const { return LEDA_ACCESS(I,IMPL::inf(it)); } 
/*{\Mop        returns the information of item |it|. \\
              \precond |it| is an item in |S|.}*/


virtual f_seq_item lookup(K k) const  {  return IMPL::lookup(leda_cast(k));  }

/*{\Mop        returns the item with key |k|
              (|nil| if no such item exists in |S|) }*/


virtual f_seq_item finger_lookup(K k) const   
{   return IMPL::finger_lookup(leda_cast(k));   }

/*{\Mop        equivalent to |S.lookup(k)| }*/



virtual f_seq_item locate(K k) const  {  return IMPL::locate(leda_cast(k));  }

/*{\Mop        returns the item \Litem{|k1|,|i|} in |S| such that
              |k1| is minimal with $|k1| \ge k$ (|nil| if no
              such item exists).}*/


virtual f_seq_item finger_locate(K k) const   
{   return IMPL::finger_locate_succ(leda_cast(k));   }

/*{\Mop        equivalent to |S.locate(k)| }*/



virtual f_seq_item locate_succ(K k) const  
{  return IMPL::locate_succ(leda_cast(k));  }

/*{\Mop        equivalent to |S.locate(k)| }*/


virtual f_seq_item succ(K k) const  {  return locate_succ(k);  }
/*{\Mop        equivalent to |S.locate(k)| }*/


virtual f_seq_item finger_locate_succ(K k) const  
        {   return IMPL::finger_locate_succ(leda_cast(k));   }

/*{\Mop        equivalent to |S.locate(k)| }*/


virtual f_seq_item locate_pred(K k) const  
{  return IMPL::locate_pred(leda_cast(k));  }

/*{\Mop  returns the item \Litem{|k1|,|i|} in |S|  such that
        |k1| is maximal with $|k1| \le k$ ( |nil| if no such item exists). }*/


virtual f_seq_item pred(K k) const  {  return locate_pred(k);  }

/*{\Mop  equivalent to |S.locate_pred(k)| }*/


virtual f_seq_item finger_locate_pred(K k) const 
      {   return IMPL::finger_locate_pred(leda_cast(k));   }

/*{\Mop  equivalent to |S.locate_pred(k)| }*/



virtual f_seq_item finger_lookup(f_seq_item it,K k) const 
    {   return IMPL::finger_lookup(it,leda_cast(k));   }

/*{\Mopl  equivalent to |IT.lookup(k)| where |IT| is the sorted sequence 
         containing |it|. \\
         \precond |S| and |IT| must have the same type }*/


virtual f_seq_item finger_locate(f_seq_item it,K k) const 
      {   return IMPL::finger_locate_succ(it,leda_cast(k));   }

/*{\Mopl  equivalent to |IT.locate(k)| where |IT| is the sorted sequence 
         containing |it|. \\
         \precond |S| and |IT| must have the same type. }*/


virtual f_seq_item finger_locate_succ(f_seq_item it,K k) const 
      {   return IMPL::finger_locate_succ(it,leda_cast(k));   }

/*{\Mopl  equivalent to |IT.locate_succ(k)| where |IT| is the sorted sequence 
         containing |it|. \\
         \precond |S| and |IT| must have the same type }*/


virtual f_seq_item finger_locate_pred(f_seq_item it,K k) const 
      {   return IMPL::finger_locate_pred(it,leda_cast(k));   }

/*{\Mopl  equivalent to |IT.locate_pred(k)| where |IT| is the sorted sequence 
         containing |it|. \\
         \precond |S| and |IT| must have the same type. }*/


virtual f_seq_item min() const       {  return IMPL::min_item();  }

virtual f_seq_item min_item() const  {  return IMPL::min_item();  }

/*{\Mop  returns the item with minimal key (|nil| if  |S|  is empty). }*/


virtual f_seq_item max() const       {  return IMPL::max_item();  }

virtual f_seq_item max_item() const  {  return IMPL::max_item();  }

/*{\Mop  returns the item with maximal key (|nil| if  |S| is empty). }*/


virtual f_seq_item succ(f_seq_item it) const  {  return IMPL::succ(it);  }

/*{\Mop  returns the successor item of |it| in the sequence containing |it| 
        (|nil| if there is no such item). }*/


virtual f_seq_item pred(f_seq_item x) const  {  return IMPL::pred(x);  }

/*{\Mop  returns the predecessor item of |it| in the sequence containing |it| 
        (|nil| if there is no such item). }*/


virtual f_seq_item insert(K k,I i)
                       {  return IMPL::insert(leda_cast(k),leda_cast(i));  } 

/*{\Mop  associates information |i| with key |k|: If
        there is an item  \Litem{|k|,|j|}  in  |S| then |j| is
        replaced by |i|, else a new item \Litem{|k|,|i|} is
        added to  |S|. In both cases the item is returned. }*/


virtual f_seq_item insert_at(f_seq_item it,K k,I i)
 {  return IMPL::insert_at_item(it,leda_cast(k),leda_cast(i));  } 

/*{\Mopl Like |IT.insert(k,i)| where |IT| is the sequence containing item |it|.\\
        \precond |it| is an item in |IT| with either\\
        |key(it)| is maximal with $|key(it)| < k$ or\\
        |key(it)| is minimal with $|key(it)| > k$.
        |S| and |IT| have the same type. }*/


virtual f_seq_item insert_at(f_seq_item it,K k,I i,int dir)
 {  return IMPL::insert_at_item(it,leda_cast(k),leda_cast(i),dir);  }

/*{\Mopl  Like |IT.insert(k,i)| where |IT| is the sequence containing item 
         |it|. \\
         \precond |it| is an item in |IT| with\\
         |key(it)| is maximal with $|key(it)| < k$ if |dir = before| or\\
         |key(it)| is minimal with $|key(it)| > k$ if |dir = after|.\\
         |S| and |IT| have the same type. }*/
 

virtual int      size()    {  return IMPL::size();  }

/*{\Mop  returns the size of  |S|. }*/


virtual bool     empty() const {  return IMPL::empty(); }

/*{\Mop  returns true if  |S| is empty, false otherwise. }*/



virtual void     clear()  {  IMPL::clear();  }

/*{\Mop  makes  |S| the empty sorted sequence. }*/



virtual void reverse_items(f_seq_item a, f_seq_item b)  {  IMPL::reverse_items(a,b);  }

/*{\Mopl  the subsequence of |IT| from |a| to |b| is reversed, where |IT| is 
         the sequence containing |a| and |b|. \\
         \precond |a| appears before 
         |b| in |IT|. }*/



virtual void flip_items(f_seq_item a, f_seq_item b)     {  reverse_items(a,b);  }

/*{\Mopl  equivalent to |S.reverse_items(a,b)|. }*/

virtual void del(K k)          {  IMPL::del(leda_cast(k));  }

/*{\Mop  removes the item with key |k| from |S| 
        (null operation if no such item exists). }*/ 


virtual void del_item(f_seq_item it)   {  IMPL::del_item(it);  }

/*{\Mop  removes the item |it| from the sequence containing |it|. }*/



virtual void change_inf(f_seq_item it, I i)  {  IMPL::change_inf(it,leda_cast(i)); }

/*{\Mopl  makes |i| the information of item |it|. }*/


virtual void split(f_seq_item it,f_sortseq<K,I>& S1,f_sortseq<K,I>& S2,int dir)
                       {  IMPL::split_at_item(it,(IMPL&)S1,(IMPL&)S2,dir);  }

/*{\Mopl  splits |IT| at item |it|, where |IT| is the sequence containing |it|,
         into sequences |S1| and |S2| and makes |IT| empty 
         (if distinct from |S1| and |S2|). More precisely, if
          $\mbox{|IT|} = x_1, \ldots,x_{k-1}, \mbox{|it|},x_{k+1}, \ldots,x_n$ 
         and |dir = after| then $\mbox{|S1|} = x_1, \ldots,x_{k-1},\mbox{|it|}$ 
         and $\mbox{|S2|} = x_{k+1}, \ldots,x_n$. If |dir = before| then |S2| 
         starts with |it| after the split. }*/
       

virtual void delete_subsequence(f_seq_item a,f_seq_item b,f_sortseq<K,I>& S1)
                       {  IMPL::delete_subsequence(a,b,(IMPL&)S1);  }

/*{\Mopl  deletes the subsequence starting at |a| and ending at |b| from the
         sequence |IT| containing both and assigns the subsequence to |S1|.\\
         \precond |a| and |b| belong to the same sequence |IT|, 
         |a| is equal or before |b| and |IT| and |S1| have the same type. }*/

/*{\Mtext \newlength{\oldcallwidth}\setlength{\oldcallwidth}{\callwidth}
          \newlength{\oldtypewidth}\setlength{\oldtypewidth}{\typewidth}
          \settowidth{\typewidth}{|f_sortseq<K,I>&|}
          \addtolength{\typewidth}{\colsep} 
          \addtolength{\callwidth}{+\oldtypewidth}
          \addtolength{\callwidth}{-\typewidth}
          \computewidths}*/

virtual f_sortseq<K,I>& conc(f_sortseq<K,I>& S1,int dir)
      {  IMPL::conc((IMPL&)S1,dir); return *this;  }

/*{\Mopl  appends |S1| at the front (|dir = before|) or rear (|dir = after|)
         end of |S|, makes |S1| empty and returns |S|.\\ 
         \precond $|S.key(S.max_item())| < |S1.key(S1.min_item())|$ if |dir = after|
         and $|S1.key(S1.max_item())| < |S.key(S.min_item()|$ if |dir = before|.}*/

/*{\Mtext \setlength{\typewidth}{\oldtypewidth}
          \setlength{\callwidth}{\oldcallwidth}
          \computewidths}*/

virtual void merge(f_sortseq<K,I>& S1) { IMPL::merge((IMPL&)S1);  }

/*{\Mopl  merges the sequence |S1| into sequence |S| and makes |S1| empty.\\
         \precond all keys are distinct. }*/


virtual void print(ostream& out,string s,char c=' ') const
 {  IMPL::print(out,s,c);  }

/*{\Mopl  prints |s| and all elements of |S| separated by |c| onto stream 
         |out|. }*/

virtual void print(string s,char c=' ') const
 {  IMPL::print(cout,s,c);  }

/*{\Mopl  equivalent to |S.print(cout,s,c)|. }*/




virtual void check_data_structure(string s)
 {  IMPL::check_data_structure(s);  }

f_sortseq<K,I>& operator=(const f_sortseq<K,I>& S1)
{ IMPL::operator=((IMPL &) S1); return *this;  }

/*
assigns a copy of |S1| to |S|.
*/


bool operator==(const f_sortseq<K,I>& S1)
{ f_seq_item sit = min_item();  f_seq_item sit1 = S1.min_item();
  while (sit != nil && sit1 != nil)
   if (compare(key(sit),S1.key(sit)) == 0)
     { sit = succ(sit);  sit1 = S1.succ(sit1);}
   else return false;
  return (sit == nil && sit1 == nil);
}

/*{\Mbinop
returns |true| if |S| agrees with |S1| componentwise and |false| otherwise
}*/

bool operator!=(const f_sortseq<K,I>& S1) 
{  return (!(operator==(S1)));  }
/*
returns |false| if |S| agrees with |S1| componentwise and |true| otherwise
*/

virtual ~f_sortseq()    {  IMPL::clear();  }  
}  ;

#endif


/*{\Mimplementation
Sorted sequences are implemented by skiplists \cite{Pugh-cookbook,Pugh}. 
Let $n$ denote the current size of the sequence. Operations |insert|, |locate|, |lookup| and |del| 
take time $O(\log n)$, operations |succ|, |pred|, |max|, |min_item|, |key|, |inf|, 
|insert_at| and |del_item| take time $O(1)$. |leda_clear| takes 
time $O(n)$ and |reverse_items| $O(l)$, where $l$ is the length of the 
reversed subsequence. |Finger_lookup(x)| and |finger_locate(x)|  take time 
$O(\log min (d,n-d))$ if |x| is the $d$-th item in |S|. |Finger_lookup(it,x)|
and |finger_locate(it,x)| take time $O(\log min (d,n-d))$ where $d$ is the
number of items between |it| and the item containing |x|. Note that
|min(d,n-d)| is the smaller of the distances from |it| to |x| if
sequences are viewed as circularly closed. |Split|, 
|delete_subsequence| and |conc| take time $O(\log min (n_1,n_2))$ 
where $n_1$ and $n_2$ are the
sizes of the results of |split| and |delete_subsequence| and the
arguments of |conc| respectively. |Merge| takes time 
$O(\log ((n_1 + n_2)/n_1))$ where $n_1$ and $n_2$ are 
the sizes of the two arguments. The
space requirement of sorted sequences is linear in the length of the
sequence (about $40n$ Bytes for a sequence of size $n$ plus the space for the
keys and the informations.).
}*/



/*{\Mexample
We use a sorted sequence to list all elements in a sequence of 
strings lying
lexicographically between two given search strings.

\begin{verbatim}

#include <LEDA/f_sortseq.h>
main()
{ f_sortseq<string,int> S;
  string s1,s2;
  while ( cin >> s1 &&  s1 != "stop" ) S.insert(s1,0);
  while ( cin >> s1 >> s2 )
    { f_seq_item stop = S.locate(s2);
      for (f_seq_item it = S.locate(s1); it != stop; it = S.succ(it))
        cout << S.key(it) << "\n";
    } 
}

\end{verbatim}

\noindent
Further examples can be found in section Sorted Sequences of
\cite{Me-Na:LEDA-book}.

}*/



