/*****
  IMPLIST is an inherited form of tlistp (available separately)
          which offers a built-in sorting feature, ordered at
          compile-time. It can sort ascending, or add at beginning
          or at the end, based on the flag at instantiation.
       CAVEAT EMPTOR: This is NOT necessarily the most efficient
          implementation of a list, merely a flexible one
---**/
#ifndef  _IMPLIST_H
#define  _IMPLIST_H

#include"tlistp.h"
#include<ctype.h>
using namespace std;
#include<string>

string rucase(string s,int i=0){
  char c[2]="\0";
  if(i==s.length())
    return "";
  if(i<s.length())
    c[0] = toupper(s[i]);
  return string(c) + rucase(s,i+1);
}
string ucase(string unk){
  return rucase(unk);
}
string rlcase(string s,int i=0){
  char c[2]="\0";
  if(i==s.length())
    return "";
  if(i<s.length())
    c[0] = tolower(s[i]);
  return string(c) + rucase(s,i+1);
}
string lcase(string unk){
  return rlcase(unk);
}

template <class T>
class ImpList : public List<T>{
 public:
 private:
  char ordflag;

  bool addbeg(T x){
    NPtr t=new Node;
    if(NULL==t)
      return false;
    t->d=x;
    t->n=start->n;
    start->n=t;
    return true;
  }
  bool addend(T x){
    NPtr t=new Node;
    if(NULL==t)
      return false;
    NPtr cur=start;
    while(NULL!=cur->n)
      cur=cur->n;
    t->d=x;
    cur->n=t;
    return true;
  }
  bool addord(T x){      // requires '<' operator defined for <T>
    NPtr
      c,n,p;

    c=start->n;
    p=NULL;
    n=new Node;

    if(NULL==n)
      return false;
    n->d=x;

    while(NULL!=c && c->d<x){
      p=c;
      c=c->n;
    }

    if(NULL==p){
      p=n;
      return true;
    }
    lastptr=c;
    p->n=n;
    n->n=c;
    return true;
  }

  bool delbeg(T &x){
    NPtr t=start->n;
    if(NULL==t)
      return false;
    x=t->d;
    start->n=t->n;
    delete t;
    return true;
  }
  bool delend(T &x){
    NPtr t=start->n;
    if(NULL==t)
      return false;
    NPtr p=start;
    while(NULL!=t->n){
      p=t;
      t=t->n;
    }
    delete t;
    p->n=NULL;
    return true;
  }
  bool delord(T &x){      // identical to parent's remove() code
    NPtr                  // because our remove() code is different
      pp = start,
      tp = start->n;

    while (NULL!=t && tp->d!=x) {
      pp = tp;
      tp = tp->n;
    }

    if (NULL==tp || tp->d!=x) {
      lastptr = NULL;
      return false;
    }
    pp->n = tp->n;
    delete tp;
    lastptr = pp;
    return true;
  }

 public:
  ImpList(const ImpList<T> & orig){   // copy constructor for List
    empty();                          // recycle any old nodes
    start = duplst(orig.start);
    cursor = NULL;
  }
  ImpList(char how='='){              // defaults to ordered form of list,
    start = new Node;
    cursor = start->n;
    switch (how){
    case '<':
      ordflag=how;
      break;
    case '>':
      ordflag=how;
      break;
    default:
      ordflag='=';
      break;
    }
  }

  bool find(T &x){
    return getitem(x);
  }

  bool add(T x){
    switch(ordflag){
    case '>':
      return addend(x);
      break;
    case '=':
      return addord(x);
      break;
    default:      // obviously, we need to add somewhere
                  // at the beginning is the fastest
      return addbeg(x);
      break;
    }
  }
  bool remove(T &x){
    switch(ordflag){
    case '>':
      return delend(x);
      break;
    case '<':
      return delbeg(x);
      break;
    default:
      return delord(x);
    }
  }

  void print(ostream &out){
     NPtr
       xp = start->n;
     while (NULL!=xp) {
       out << xp->d << " | ";
       xp = xp->n;
       }
     out <<" eol ";
     }
};

template <class T>
ostream &operator<<(ostream &out, ImpList<T> &t){
  t.print(out);
  return(out);
}

#endif