//-< DBSCLS.H >------------------------------------------------------*--------*
// GOODS                     Version 1.0         (c) 1997  GARRET    *     ?  *
// (Generic Object Oriented Database System)                         *   /\|  *
//                                                                   *  /  \  *
//                          Created:     28-Mar-97    K.A. Knizhnik  * / [] \ *
//                          Last update: 17-Apr-97    K.A. Knizhnik  * GARRET *
//-------------------------------------------------------------------*--------*
// Some common database classes
//-------------------------------------------------------------------*--------*

#ifndef __DBSCLS_H__
#define __DBSCLS_H__

#include "goods.h"
#include "goodsdlx.h"
#include "wwwapi.h"

#ifdef USE_STL
using namespace std;
#include <string>

#endif

BEGIN_GOODS_NAMESPACE

//
// Dynamicly reallocatable array template. Array is automatically
// expanded when new element is stored at position beyond array bound. 
// This template can't be used directly because it is impossible 
// to register template classes in database.
// Instead of this concrete instantiations of this template can be used. 
//
template<class T>
class GOODS_DLL_EXPORT array_template : public object { 
  protected: 
    nat4 used;
    T    array[1];

    virtual array_template* clone(size_t new_size) const { 
        return new (cls, new_size) array_template(0, cls, new_size); 
    }

    array_template* set_size(nat4 n) { 
        nat4 allocated = (size - offsetof(array_template, array)) / sizeof(T); 
        if (n > allocated) { 
            array_template* new_arr = clone(n < allocated*2 ? allocated*2 : n);
            memcpy(new_arr->array, array, used*sizeof(T));
            memset(array, 0, used*sizeof(T));
            new_arr->used = n; 
            new_arr->mop = mop;
            become(new_arr); 
            return new_arr; 
        }
        used = n; 
        return this; 
    }
  public:
    virtual ref<array_template<T> > clone() const { 
        array_template* new_arr = new (cls, used) array_template(0, cls, used);
        for (int i = used; --i >= 0;) { 
            new_arr->array[i] = array[i];
        }
        return new_arr;
    }

    static ref<array_template<T> > create(size_t allocated_size,
                                          size_t init_size = 0) 
    { 
        assert(init_size <= allocated_size);
        if (allocated_size == 0) { 
            allocated_size = 1;
        }
        return new (self_class, allocated_size) array_template(self_class,
                                                               allocated_size,
                                                               init_size);
    }

    static ref<array_template<T> > create() { 
        return create(4, 0);
    }

    static ref<array_template<T> > create(ref<array_template<T> > copy) { 
        return copy->clone();
    }

    static ref<array_template<T> > create(T const* buf, size_t size) { 
        return new (self_class, size) array_template(self_class, buf, size);
    }

    size_t length() const { return used; }

    //
    // Array elements accessors
    //
    void putat(nat4 index, T const& elem) { 
        if (index >= used) { 
            set_size(index+1)->array[index] = elem; 
        } else { 
            array[index] = elem; 
        }
    }  
    T getat(nat4 index) const { 
        assert(index < used); 
        return array[index]; 
    }  
    T operator[](nat4 index) const {  
        assert(index < used); 
        return array[index]; 
    }  
    
    //
    // Stack protocol
    //
    void push(T const& elem) { 
        int n = used; 
        set_size(n+1)->array[n] = elem;
    }
    T pop() { 
        assert(used > 0);
        used -= 1;
        return array[used]; 
    }
    T top() const { 
        assert(used > 0);
        return array[used-1];
    }
    
    //
    // Massive operation
    // 
    void insert(nat4 pos, T const& elem) { 
        nat4 n = used;
        assert(pos <= n);
        array_template* arr = set_size(n+1);
        memmove(&arr->array[pos+1], &arr->array[pos], (n - pos)*sizeof(T));
        memset(&arr->array[pos], 0, sizeof(T)); 
        arr->array[pos] = elem; 
    }

    void append(T const* tail, size_t len) { 
        nat4 n = used;
        array_template* arr = set_size(n+len);
        for (size_t i = 0; i < len; i++) { 
            arr->array[i+n] = tail[i];
        }
    }   

    void remove(nat4 pos) {
        assert(pos < used);
        T zero = 0;
        array[pos] = zero;
        memcpy(&array[pos], &array[pos+1], (used - pos - 1)*sizeof(T)); 
        used -= 1;
    }

    int iterate(boolean (*f)(const T &mbr, void const* arg), 
                void const* arg = NULL) const 
    {
        int i = used; 
        while (--i >= 0 && !f(array[i], arg));
        return i;
    }

    int index_of(T const& elem) const {
        for (int i = 0, n = used; i < n; i++) { 
            if (array[i] == elem) { 
                return i;
            }
        }
        return -1;
    }

    int last_index_of(T const& elem) const {
        int i = used; 
        while (--i >= 0 && array[i] != elem);
        return i;
    }

    T*  copy() const { 
        T* arr = NEW T[used];
        int n = used; 
        while (--n >= 0) { 
            arr[n] = array[n]; 
        }
        return arr;
    }

    void copy(T* array, int from, int len) const { 
        assert(unsigned(from + len) <= used && from >= 0 && len >= 0);
        int n = len; 
        while (--n >= 0) { 
            array[n] = this->array[n + from]; 
        }
    }
 
    METACLASS_DECLARATIONS(array_template, object); 

  protected: 
    array_template(class_descriptor& desc, size_t allocated_size, 
                   size_t init_size) 
    : object(desc, allocated_size) 
    {
        used = init_size;
    }

    array_template(class_descriptor& desc, T const* buf, size_t buf_size)  
    : object(desc, buf_size) 
    {
        used = buf_size;
        for (size_t i = 0; i < buf_size; i++) { 
            array[i] = buf[i];
        }
    }
};

template<class T>
inline field_descriptor& array_template<T>::describe_components() { 
    return FIELD(used), VARYING(array); 
}

typedef array_template<char>          ArrayOfByte; 
typedef array_template<int4>          ArrayOfInt; 
typedef array_template<real8>         ArrayOfDouble; 
typedef array_template< ref<object> > ArrayOfObject; 

class GOODS_DLL_EXPORT String : public ArrayOfByte { 
  protected: 
    virtual array_template<char>* clone(size_t new_size) const { 
        return new (cls, new_size) String(0, cls, new_size); 
    }
  public: 

#ifdef USE_LOCALE_SETTINGS
    int  compare(const char* str) const { return strcoll(array, str); }
    int  compareIgnoreCase(const char* str) const { 
        return stricoll(array, str); 
    }
#else
    int  compare(const char* str) const { return strcmp(array, str); }
    int  compareIgnoreCase(const char* str) const {
        return stricmp(array, str); 
    }   
#endif
    int  compare(ref<String> const& str) const { return -str->compare(array); }
    int  compareIgnoreCase(ref<String> const& str) const { 
        return -str->compareIgnoreCase(array); 
    }

    int  index(const char* str) const { 
        char const* p = strstr(array, str); 
        return p ? p - array : -1; 
    }
    
    void append(const char* tail) { 
        nat4 n = used ? used-1 : 0;
        size_t len = strlen(tail) + 1;
        String* s = (String*)set_size(n+len);
        for (size_t i = 0; i < len; i++) { 
            s->array[i+n] = tail[i];
        }
    }   

#ifdef USE_STL
    string getString() const { 
        return string(array);
    }
    static ref<String> create(string const& str) { 
        return create(str.data());
    }
#endif
    char* data() const { 
        char* str = NEW char[used+1];
        strcpy(str, array);
        return str;
    }

    WWWconnection& toPage(WWWconnection& con) const { 
        return con.append(array);
    }

    inline friend WWWconnection& operator << (WWWconnection& con, 
                                              ref<String> str) { 
        return str->toPage(con);
    }

    virtual ref<ArrayOfByte> clone() const { 
        return create(array); 
    }

    static ref<String> create(ref<String> copy) { 
        return copy->clone();
    }

    static ref<String> create(size_t init_size = 0) { 
        return new (self_class, init_size) String(self_class, init_size); 
    }

    static ref<String> create(const char* str) { 
        size_t len = strlen(str)+1;
        String* s = new (self_class, len) String(self_class, len); 
        strcpy(s->array, str);
        return s;
    }

    void replace(const char* str) { 
        String* s = (String*)set_size(strlen(str)+1);
        strcpy(s->array, str);
    }

    const char* get_text() const {
        // it is safe to use pointer to buffer of persistent string 
        // only within transaction in which this object was included
        return array;
    }

    void print() const { console::output(array); }

    METACLASS_DECLARATIONS(String, ArrayOfByte); 

  protected: 
    String(class_descriptor& desc, size_t init_size) 
    : ArrayOfByte(desc, init_size, init_size) {}
}; 


//
// Representation of one-to-many relationship: set of objects.
// Set conssist of set owner and a number of set members. 
// Each member contains references to previouse and next member, 
// reference to set owner, reference to associated object 
// and full key of this object. First (last) member has next (prev) field 
// equal to NULL. Member of a set has virtual function to compare
// two members. Also default function for converting complete key 
// to short integer form
//

typedef nat8 skey_t;

class GOODS_DLL_EXPORT set_member : public object {
    friend class set_owner;
  public: 
    ref<set_member> next; 
    ref<set_member> prev; 
    ref<set_owner>  owner; 
    ref<object>     obj;

    char            key[1];

    static ref<set_member> create(ref<object> obj, const char* key) { 
        size_t key_size = strlen(key) + 1;
        return new (self_class, key_size) 
            set_member(self_class, obj, key, key_size);
    }
    static ref<set_member> create(ref<object> obj, const char* key, 
                                  size_t key_size) 
    { 
        return new (self_class, key_size) 
            set_member(self_class, obj, key, key_size);
    }

    ref<set_member> first() const;  
    ref<set_member> last() const;  

    size_t          copyKeyTo(char* buf, size_t bufSize) const;

    inline size_t   getKeyLength() const { 
        return size - offsetof(set_member, key);
    }

    virtual int     compare(ref<set_member> mbr) const;
    virtual int     compare(const char* key, size_t size) const; 
    virtual int     compare(const char* key) const; 
    virtual int     compareIgnoreCase(const char* key) const; 
    virtual skey_t  get_key() const; 
    
    static skey_t   str2key(const char* s, size_t len);

    METACLASS_DECLARATIONS(set_member, object);

  protected: 

    set_member(class_descriptor& aDesc, ref<object> const& obj, 
               const char* key, size_t key_size) 
    : object(aDesc, key_size)
    { 
        next = NULL;
        prev = NULL; 
        owner = NULL; 
        this->obj = obj; 
        memcpy(this->key, key, key_size);
    }
}; 


class GOODS_DLL_EXPORT set_owner : public object { 
  public: 
    ref<set_member> first; 
    ref<set_member> last; 
    ref<object>     obj;
    nat4            n_members;
    
    boolean empty() const { return n_members == 0; }

    virtual ref<set_member> find(const char* key, size_t len) const; 

    ref<set_member> find(const char* key) const { 
        return find(key, strlen(key)+1);
    }

    void put_first(ref<set_member> mbr);
    void put_last(ref<set_member> mbr);
    void put_after(ref<set_member> after, ref<set_member> mbr);
    void put_before(ref<set_member> before, ref<set_member> mbr);

    virtual void insert(char const* key, ref<object> obj) { 
        put_last(set_member::create(obj, key));
    }

    virtual boolean insert_unique(char const* key, ref<object> obj) { 
        if (find(key) == NULL) { 
            insert(key, obj);
            return True;
        }
        return False;
    }

    typedef void (*member_function)(ref<set_member> mbr, void const* arg);
    size_t iterate(member_function, void const* arg = NULL) const;

    ref<set_member> get_first(); 
    ref<set_member> get_last(); 

    virtual void remove(ref<set_member> mbr);

    static ref<set_owner> create(ref<object> obj) { 
        return NEW set_owner(self_class, obj); 
    } 

    METACLASS_DECLARATIONS(set_owner, object);

  protected: 
    set_owner(class_descriptor& desc, ref<object> const& obj, int varying=0) 
    : object(desc, varying)
    { 
        this->obj = obj; 
        n_members = 0;
    }
};  

//
// B tree - multibranch balanced tree, provides fast access for objects 
// in database. B_tree class is derived from set_owner and use set members
// to reference objects. 
//
class GOODS_DLL_EXPORT B_tree : public set_owner {
  public:
    //
    // Default minimal number of used items at not root page 
    //
    enum { dflt_n = (4096-4)/(sizeof(skey_t)+sizeof(dbs_reference_t))/2 }; 
    // enum { dflt_n = 2 };    // only for testing

    ref<set_member> find(skey_t key) const;

    ref<set_member> find(const char* str, size_t len, skey_t key) const;
    ref<set_member> find(const char* str) const;
    
    // Find member with greater or equal key
    ref<set_member> findGE(skey_t key) const;
    ref<set_member> findGE(const char* str, size_t len, skey_t key) const;
    ref<set_member> findGE(const char* str) const;

    void            insert(ref<set_member> mbr);
    void            remove(ref<set_member> mbr);

    void            insert(char const* key, ref<object> obj) { 
        insert(set_member::create(obj, key));
    }

    void            dump() const;
    void            ok() const;

    nat4            get_height() const { return height; }

    static ref<B_tree> create(ref<object> obj, nat4 min_used = dflt_n) {
        return NEW B_tree(self_class, obj, 0, min_used);
    }

    static class_descriptor self_class; 
    friend class_descriptor& classof(B_tree const*); 
    static object* constructor(hnd_t hnd, class_descriptor& desc, 
                               size_t varying_size); 
    B_tree(hnd_t hnd, class_descriptor& desc, size_t varying_size) 
    : set_owner(hnd, desc, varying_size), n(dflt_n) {} 
    virtual field_descriptor& describe_components(); 

  protected:
    friend class B_page;

    ref<B_page> root;   // root page
    nat4        height; // height of tree
    int4        n;      // minimal number of used items at not root page

    B_tree(class_descriptor& desc, ref<object> const& obj=NULL, int varying=0,
        nat4 min_used = dflt_n) 
    : set_owner(desc, obj, varying)
    {
        root = NULL; 
        height = 0;
        n = min_used;
    }
}; 

class GOODS_DLL_EXPORT B_page : public object { 
    friend class B_tree;
  protected: 
    int4 m;            // Index of first used item

    struct item { 
        ref<object> p; // for leaf page - pointer to 'set_member' object
                       // for all other pages - pointer to child page
        skey_t      key; 

        field_descriptor& describe_components() { 
            return FIELD(p), FIELD(key);
        }                               
        inline friend field_descriptor& describe_field(item& s) { 
            return s.describe_components();
        }
    } e[1];
    //
    // Class invariants: 
    //
    //   0 <= m <= 2*n-2, for root page
    //   0 <= m <= n, for other pages
    //
    // For not leaf page:
    // ( for all i : m < i < 2*n : e[i-1].key < e[i].key ) &&
    // ( for all i, j : m <= i < 2*n, e[i].p->m <= j < 2*n-1 :
    //   e[i].key > e[i].p->e[j].key &&
    //   e[i].key == e[i].p->e[2*n-1].key )
    //

    ref<set_member> find(int height, skey_t key, int4 n) const; 
    ref<set_member> findGE(int height, skey_t key, int4 n) const; 

    enum operation_effect { 
        done, 
        overflow,
        underflow, 
        propagation
    };  

    operation_effect insert(int r, item& ins, int4 n);
    operation_effect remove(int r, item& rem, int4 n);
    operation_effect handle_underflow(int r, skey_t key, item& rem, int4 n);

    operation_effect find_insert_position(int level, 
                                          ref<B_tree> const& tree, 
                                          item& ins, int4 n) const;
    operation_effect find_remove_position(int level, item& rem, int4 n) const;

    void dump(int level, int height, int4 n) const;
    void ok(skey_t min_key_val, skey_t max_key_val,
            int level, int height, int4 n) const;

    B_page(size_t varying_length) : object(self_class, varying_length) {}

    // create new B tree root
    B_page(ref<B_page> const& root, item& ins, int4 n); 

  public: 
    METACLASS_DECLARATIONS(B_page, object);

  protected:
    static ref<B_page> create(int4 n) { 
        size_t len = n*2;
        B_page* p = new (self_class, len) B_page(len);
        return p;
    }

    static ref<B_page> create(ref<B_page> const& root, item& ins,
                              int4 n) { 
        size_t len = n*2;
        B_page* p = new (self_class, len) B_page(root, ins, n); 
        return p;
    }
}; 

//
// Simple hash table.
//
class GOODS_DLL_EXPORT hash_item : public object { 
  public: 
    ref<hash_item> next;
    ref<object>    obj;
    char           name[1];

    //
    // Call function for object. Apply method returns value
    // returned by function. Iteration through all hash table 
    // elements will finished if True value is return by apply method.
    //
    typedef boolean (*item_function)(const char* name, ref<object> obj);
    boolean apply(item_function f) const { return f(name, obj); }

    hash_item(ref<object> obj, ref<hash_item> next, 
              const char* name, size_t name_len) 
    : object(self_class, name_len)
    {
        this->obj = obj;
        this->next = next;
        strcpy(this->name, name);
    }
#ifdef USE_LOCALE_SETTINGS
     int compare(const char* name) const { return strcoll(name, this->name); }
#else
     int compare(const char* name) const { return strcmp(name, this->name); }
#endif
    static ref<hash_item> create(ref<object> obj, ref<hash_item> chain,
                                 const char* name)
    {
        size_t name_len = strlen(name)+1;
        return new (self_class,name_len) hash_item(obj, chain, name, name_len);
    }
    METACLASS_DECLARATIONS(hash_item, object);
};

class GOODS_DLL_EXPORT hash_table : public object { 
  public: 
    //
    // Add to hash table association of object with specified name.
    //
    void        put(const char* name, ref<object> obj);
    //
    // Search for object with specified name in hash table.
    // If object is not found NULL is returned.
    //
    ref<object> get(const char* name) const;
    //
    // Remove object with specified name from hash table.
    // If there are several objects with the same name the one last inserted
    // is removed. If such name was not found 'False' is returned.
    //
    boolean     del(const char* name);
    //
    // Remove concrete object with specified name from hash table.
    // If such name was not found or it is associated with different object
    // 'False' is returned. If there are several objects with the same name, 
    // all of them are compared with specified object.
    //    
    boolean     del(const char* name, ref<object> obj);

    //
    // Apply function to objects placed in hash table.
    // Function will be applied in some unspecified order
    // to all elements in hash table or until True will be returned by 
    // the function. In the last case reference to this object is returned.
    // Otherwise (if function returns False for all elements in hash table)
    // NULL is returned.
    //
    ref<object> apply(hash_item::item_function) const;

    void reset() { 
        n_elems = 0;
        memset(table, 0, size*sizeof(ref<object>)); 
    }

    size_t get_numer_of_elements() const { return n_elems; }

    static ref<hash_table> create(size_t size) {
        return new (self_class, size) hash_table(size);
    }
    METACLASS_DECLARATIONS(hash_table, object);

  protected: 
    nat4        size;
    nat4        n_elems;
    ref<object> table[1];
    
    hash_table(size_t size, class_descriptor& desc = self_class) 
    : object(desc, size) 
    { 
        this->size = size;
        n_elems = 0;
    }
};

//
// Hash tree is combination of hash table and B-tree. Calculated 
// values of hash function are placed at B*-tree pages.
//
class GOODS_DLL_EXPORT H_page : public object { // page of hash tree
  public:
    enum { size_log=7 };
    ref<object> p[1 << size_log];

    ref<object> apply(hash_item::item_function f, int height) const;
    void reset(int height);
    H_page() : object(self_class) {}

    METACLASS_DECLARATIONS(H_page, object);
};

class GOODS_DLL_EXPORT H_tree : public object { 
  public: 
    //
    // Add to hash table association of object with specified name.
    //
    void        put(const char* name, ref<object> obj);
    //
    // Search for object with specified name in hash table.
    // If object is not found NULL is returned.
    //
    ref<object> get(const char* name) const;
    //
    // Remove object with specified name from hash table.
    // If there are several objects with the same name the one last inserted
    // is removed. If such name was not found 'False' is returned.
    //
    boolean     del(const char* name);
    //
    // Remove concrete object with specified name from hash table.
    // If such name was not found or it is associated with different object
    // 'False' is returned. If there are several objects with the same name, 
    // all of them are compared with specified object.
    //    
    boolean     del(const char* name, ref<object> obj);

    //
    // Apply function to objects placed in hash table.
    // Function will be applied in some unspecified order
    // to all elements in hash table or until True will be returned by 
    // the function. In the last case reference to this object is returned.
    // Otherwise (if function returns False for all elements in hash table)
    // NULL is returned.
    //
    ref<object> apply(hash_item::item_function f) const { 
        if (!root.is_nil()) {
            return root->apply(f, height);
        }
        return NULL;
    }
    //
    // Clear hash table
    //
    void reset() { 
        if (!root.is_nil()) { 
            modify(root)->reset(height);
        }
        n_elems = 0;
    }
    size_t get_numer_of_elements() const { return n_elems; }

    METACLASS_DECLARATIONS(H_tree, object);
    H_tree(size_t hash_size, class_descriptor& desc = self_class);

  protected: 
    nat4        size;
    nat4        height;
    nat4        n_elems;
    ref<H_page> root;
};

//
// Binary large object class. This class can be used as base for
// creating multimedia or text objects with large size and sequential 
// access. This class provide functionality for incremental object
// loading by parallel task. 
//

class GOODS_DLL_EXPORT Blob : public object { 
  protected: 
    ref<Blob> next;
    ref<Blob> last;
    nat1      data[1];
    
    static void task_proc load_next_blob_part(void* arg);

  public: 
    //
    // This method is called by 'play' method for each part of blob
    // object within conext of current task. If this method returns False 
    // preloading process is terminated. 
    //
    virtual boolean handle() const;
    //
    // Default implementation of this method just extracts all parts of 
    // blob from database and calls handle method for each part.
    //
    virtual void play() const;

    //
    // Append new blob object at the end of blob objects chain.
    //
    void append(ref<Blob> bp) { 
        modify(last)->next = bp; 
        last = bp;
    }

    //
    // Size of BLOB segment
    //
    size_t get_size() const { 
        return  size - offsetof(Blob, data);
    }   

    //
    // How much segments of BLOB object can be read ahead before processing.
    // Default value is 1.
    //
    static int readahead;

    METACLASS_DECLARATIONS(Blob, object);

    Blob(size_t part_size, class_descriptor& desc = self_class) 
    : object(desc, part_size) 
    { 
        next = NULL;
        last = this;
    }

    Blob(void* buf, size_t buf_size, class_descriptor& desc = self_class) 
    : object(desc, buf_size) 
    { 
        next = NULL;
        last = this;
        memcpy(data, buf, buf_size);
    }
};

END_GOODS_NAMESPACE

#endif