// This may look like C code, but it is really -*- C++ -*-
/* 
Copyright (C) 1988 Free Software Foundation
    written by Doug Lea (dl@rocky.oswego.edu)
    based on code by Marc Shapiro (shapiro@sor.inria.fr)

This file is part of the GNU C++ Library.  This library is free
software; you can redistribute it and/or modify it under the terms of
the GNU Library General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your
option) any later version.  This library is distributed in the hope
that it will be useful, but WITHOUT ANY WARRANTY; without even the
implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE.  See the GNU Library General Public License for more details.
You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free Software
Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#ifndef _<T>MPlex_h
#ifdef __GNUG__
#pragma interface
#endif
#define _<T>MPlex_h 1


#include "<T>.Plex.h"


// Number of bits per long, used in MChunk bit map operations

#define _MAP_BITS  32


class <T>MChunk : public <T>IChunk
{
protected:

  unsigned long* map;          // bitmap of slots
  int            unused;       // number of unused internal slots 

  void           mark(int);    // bitmap operations
  void           free(int);
  int            valid(int) const;

public:

                 <T>MChunk(<T>*    d,        // ptr to array of elements
                        int      base_idx, // initial indices
                        int      low_idx,  // & initially clear map
                        int      fence_idx,
                        int      top_idx);

                 ~<T>MChunk();

// virtuals

  int            first_index() const;
  int            last_index() const;
  int            succ(int idx) const;
  int            pred(int idx) const;
  <T>*           first_pointer() const;                 
  <T>*           last_pointer() const;                 
  <T>*           succ(<T>*) const;                 
  <T>*           pred(<T>*) const; 
  int            empty() const;
  int            full() const;
  int            valid_index(int i) const;
  int            valid_pointer(const <T>* p) const;
  <T>*           grow_high ();
  <T>*           grow_low ();  
  void           shrink_high ();
  void           shrink_low ();     
  void           clear(int);
  void           cleardown(int);
  int            OK() const;

// extensions

  int            unused_indices() const;   // how many free slot in low..fence?

  int            unused_index() const;     // return index of free slot

  int            del(int i);         // delete data indexed by i
                                     // return true if was present
  int            undel(int idx);     // un-delete data indexed by i
                                     // return true if already present

  void           reset_low();        // reset low = lowest valid index; 
  void           reset_high();       // same for high

};


class <T>MPlex: public <T>Plex
{
  <T>MChunk*       ch;          // cached chunk
  int              unused;      // # of free slots between low & fence

  void             make_initial_chunks(int up = 1);
  void             cache(int idx) const;
  void             cache(const <T>* p) const;
  int              dopred(int) const;
  int              dosucc(int) const;

  void             set_cache(const <T>MChunk* t) const; // logically, 
                                               // not physically const

public:
                   <T>MPlex();                 // set low = 0;
                                               // fence = 0;
                                               // csize = default

                   <T>MPlex(int ch_size);      // low = 0; 
                                               // fence = 0;
                                               // csize = ch_size

                   <T>MPlex(int lo,            // low = lo; 
                            int ch_size);      // fence=lo
                                               // csize = ch_size

                   <T>MPlex(int lo,            // low = lo
                            int hi,            // fence = hi+1
                            const <T&> initval,// fill with initval,
                            int ch_size = 0);  // csize= ch_size
                                               // or fence-lo if 0

                   <T>MPlex(const <T>MPlex&);

  void             operator= (const <T>MPlex&);

// virtuals 

  <T>&             high_element ();
  <T>&             low_element ();
  const <T>&       high_element () const;
  const <T>&       low_element () const;

  Pix              first() const;
  Pix              last() const ;
  void             prev(Pix& ptr) const;
  void             next(Pix& ptr) const;
  int              owns(Pix p) const;
  <T>&             operator () (Pix p);
  const <T>&       operator () (Pix p) const;

  int              low() const; 
  int              high() const;
  int              valid(int idx) const;
  void             prev(int& idx) const;
  void             next(int& x) const;
  <T>&             operator [] (int index);
  const <T>&       operator [] (int index) const;
    
  int              Pix_to_index(Pix p) const;
  Pix              index_to_Pix(int idx) const;

  int              can_add_high() const;
  int              can_add_low() const;
  int              full() const;

  int              add_high(const <T&> elem);
  int              del_high ();
  int              add_low (const <T&> elem);
  int              del_low ();
  void             clear();

  int              OK () const; 

// extensions

  int              count() const;             // # valid elements
  int              available() const;         // # deleted elements

  int              unused_index()const;       // return index of a deleted elem
  Pix              unused_Pix() const;        // return Pix of a deleted elem

  int              del_index(int idx);        // logically delete at idx;
                                              // return true if was present
  int              del_Pix(Pix p);            // delete at p

  void             undel_index(int idx);      // undelete at idx;
  void             undel_Pix(Pix p);          // undelete at p;

  void             adjust_bounds();           // reset lo, hi to lowest &
                                              // highest valid indices

  int              add(const <T&> elem);      // add anywhere
};


inline <T>MChunk:: ~<T>MChunk()
{
  delete map;
}

inline void <T>MChunk::mark(int idx)
{
  unsigned int i = idx - base;
  map[i / _MAP_BITS] |= 1 << (i & (_MAP_BITS - 1));
}

inline void <T>MChunk::free(int idx)
{
  unsigned int i = idx - base;
  map[i / _MAP_BITS] &= ~(1 << (i & (_MAP_BITS - 1)));
}

inline int <T>MChunk::valid(int idx) const
{
  unsigned int i = idx - base;
  return map[i / _MAP_BITS] & (1 << (i & (_MAP_BITS - 1)));
}

inline  int <T>MChunk:: valid_index(int i) const
{
  return i >= low && i < fence && valid(i);
}

inline  int  <T>MChunk:: valid_pointer(const <T>* p) const
{
  int i = ((int)p - (int)data) / sizeof(<T>);
  return i >= 0 && i < (fence - base) &&
    (map[(unsigned)i / _MAP_BITS] & (1 << (i & (_MAP_BITS - 1))));
}

inline int <T>MChunk::empty() const
{
  return  fence - low - unused == 0;
}

inline int <T>MChunk::full() const
{
  return  unused + (top - fence) + (low - base) == 0;
}

inline int <T>MChunk::succ(int idx) const
{
  int i = (idx < low)? low : idx + 1;
  while (i < fence && !valid(i)) ++i;
  return i;
}

inline int <T>MChunk::pred(int idx) const
{
  int i = (idx > fence)? (fence - 1) : idx - 1;
  while (i >= low && !valid(i)) --i;
  return i;
}

inline int <T>MChunk::unused_indices() const
{
  return unused;
}

inline <T>*   <T>MChunk:: grow_high ()
{
  if (!can_grow_high()) full_error();
  mark(fence);
  return &(data[fence++ - base]);
}

inline <T>*   <T>MChunk:: grow_low ()
{
  if (!can_grow_low()) full_error();
  mark(--low);
  return &(data[low - base]);
}

inline void <T>MChunk::reset_low()
{
  while (low < fence && !valid(low))
  {
    --unused;
    ++low;
  }
}

inline void <T>MChunk::reset_high()
{
  while (fence > low && !valid(fence - 1))
  {
    --unused;
    --fence;
  }
}

inline  int <T>MPlex::full () const
{
  return 0;
}

inline int <T>MPlex::can_add_high() const
{
  return 1;
}

inline int <T>MPlex::can_add_low() const
{
  return 1;
}

inline int <T>MPlex::available() const
{
  return unused;
}

inline int <T>MPlex::count() const
{
  return fnc - lo - unused;
}

inline void <T>MPlex::set_cache(const <T>MChunk* t) const
{
  ((<T>MPlex*)(this))->ch = (<T>MChunk*)t;
}

inline <T>& <T>MPlex:: operator [] (int idx)
{
  if (!ch-><T>MChunk::valid_index(idx)) cache(idx);
  return * (ch->pointer_to(idx));
}

inline const <T>& <T>MPlex:: operator [] (int idx) const
{
  if (!ch-><T>MChunk::valid_index(idx)) cache(idx);
  return * ((const <T>*)(ch->pointer_to(idx)));
}

inline  int <T>MPlex::Pix_to_index(Pix p) const
{
  if (!ch-><T>MChunk::valid_pointer((<T>*)p)) cache((<T>*)p);
  return ch->index_of((<T>*)p);
}

inline int <T>MPlex::high() const
{
  return (((const <T>MChunk*)tl())-><T>MChunk::valid_index(fnc-1)) ? 
    fnc-1 : dopred(fnc-1);
}

inline int <T>MPlex::low() const
{
  return (((const <T>MChunk*)hd)-><T>MChunk::valid_index(lo))? lo : dosucc(lo);
}

inline  <T>& <T>MPlex::low_element ()
{
  return (*this)[low()];
}

inline const <T>& <T>MPlex::low_element () const
{
  return (*this)[low()];
}

inline  <T>& <T>MPlex::high_element ()
{
  return (*this)[high()];
}

inline const <T>& <T>MPlex::high_element () const
{
  return (*this)[high()];
}

inline  Pix <T>MPlex::index_to_Pix(int idx) const
{
  if (!ch-><T>MChunk::valid_index(idx)) cache(idx);
  return Pix(ch->pointer_to(idx));
}

inline void <T>MPlex::next(int& idx) const
{
  idx = (ch-><T>MChunk::valid_index(idx+1))? idx+1 : dosucc(idx);
}

inline void <T>MPlex::prev(int& idx) const
{
  idx = (ch-><T>MChunk::valid_index(idx-1))? idx-1 : dopred(idx);
}

inline Pix <T>MPlex::first() const
{
  return index_to_Pix(low());
}

inline Pix <T>MPlex::last() const
{
  return index_to_Pix(high());
}


inline void <T>MPlex::undel_Pix(Pix p)
{
  undel_index(Pix_to_index(p));
}

inline int <T>MPlex::del_Pix(Pix p)
{
  return del_index(Pix_to_index(p));
}

inline <T>& <T>MPlex:: operator () (Pix p)
{
  return *((<T>*)p);
}

inline const <T>& <T>MPlex:: operator () (Pix p) const
{
  return *((const <T>*)p);
}

#endif