/*******************************************************************************
+
+  LEDA 3.5
+
+  dph_array.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_DPHARRAY_H
#define LEDA_DPHARRAY_H

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


//------------------------------------------------------------------------------
// dph_array  
//------------------------------------------------------------------------------ 
#include <LEDA/basic.h> 
#include <LEDA/impl/slist.h> 
#include <LEDA/impl/dp_hash.h> 


template<class itype, class etype>

class dph_array : public dp_hash {

void clear_key(GenPtr& x)   const { LEDA_CLEAR(itype,x); }
void clear_inf(GenPtr& x)   const { LEDA_CLEAR(etype,x); }
void copy_key(GenPtr& x)    const { LEDA_COPY(itype,x);  }
void copy_inf(GenPtr& x)    const { LEDA_COPY(etype,x);  }


etype edef;

SLIST def_list;
slist_item iterator;

public:

etype& operator[](const itype& y) 
{ stp i=lookup(leda_cast(y));
  if (i==nil) 
  { GenPtr p = leda_cast(edef);
    i=insert(leda_cast(y),p);
    def_list.append(leda_cast(y));  
   }
  return LEDA_ACCESS(etype,inf(i)); 
}

const etype& operator[](const itype& y) const
{ stp it = lookup(leda_cast(y));
  if (it) return LEDA_ACCESS(etype,inf(it));
  else return edef;
 }

bool defined(const itype& y) const { return (lookup(leda_cast(y)) != nil); }

slist_item first_item() const { return def_list.first(); }

void loop_to_succ(GenPtr& x) const 
{ x = def_list.succ(slist_item(x)); }

GenPtr forall_defined_test(GenPtr it, itype& x) const
{ if (it) x = LEDA_ACCESS(itype,def_list[slist_item(it)]);
  return it;
}



 dph_array() { }
 dph_array(int n,itype* I,etype* E): dp_hash(n,(GenPtr*)I,(GenPtr*)E) { }
 dph_array(etype i) { edef=i; }

 dph_array(const dph_array<itype,etype>& A): dp_hash((dp_hash&)A) { edef = A.edef; }

virtual ~dph_array() { def_list.clear(); }
};



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

#endif
