using System;
using System.Diagnostics;
using System.Text;

using i64 = System.Int64;
using u8 = System.Byte;
using u32 = System.UInt32;

using Pgno = System.UInt32;

namespace Community.CsharpSqlite
{
  using sqlite3_int64 = System.Int64;

  public partial class Sqlite3
  {
    /*
    ** 2008 December 3
    **
    ** The author disclaims copyright to this source code.  In place of
    ** a legal notice, here is a blessing:
    **
    **    May you do good and not evil.
    **    May you find forgiveness for yourself and forgive others.
    **    May you share freely, never taking more than you give.
    **
    *************************************************************************
    **
    ** This module implements an object we call a "RowSet".
    **
    ** The RowSet object is a collection of rowids.  Rowids
    ** are inserted into the RowSet in an arbitrary order.  Inserts
    ** can be intermixed with tests to see if a given rowid has been
    ** previously inserted into the RowSet.
    **
    ** After all inserts are finished, it is possible to extract the
    ** elements of the RowSet in sorted order.  Once this extraction
    ** process has started, no new elements may be inserted.
    **
    ** Hence, the primitive operations for a RowSet are:
    **
    **    CREATE
    **    INSERT
    **    TEST
    **    SMALLEST
    **    DESTROY
    **
    ** The CREATE and DESTROY primitives are the constructor and destructor,
    ** obviously.  The INSERT primitive adds a new element to the RowSet.
    ** TEST checks to see if an element is already in the RowSet.  SMALLEST
    ** extracts the least value from the RowSet.
    **
    ** The INSERT primitive might allocate additional memory.  Memory is
    ** allocated in chunks so most INSERTs do no allocation.  There is an
    ** upper bound on the size of allocated memory.  No memory is freed
    ** until DESTROY.
    **
    ** The TEST primitive includes a "batch" number.  The TEST primitive
    ** will only see elements that were inserted before the last change
    ** in the batch number.  In other words, if an INSERT occurs between
    ** two TESTs where the TESTs have the same batch nubmer, then the
    ** value added by the INSERT will not be visible to the second TEST.
    ** The initial batch number is zero, so if the very first TEST contains
    ** a non-zero batch number, it will see all prior INSERTs.
    **
    ** No INSERTs may occurs after a SMALLEST.  An assertion will fail if
    ** that is attempted.
    **
    ** The cost of an INSERT is roughly constant.  (Sometime new memory
    ** has to be allocated on an INSERT.)  The cost of a TEST with a new
    ** batch number is O(NlogN) where N is the number of elements in the RowSet.
    ** The cost of a TEST using the same batch number is O(logN).  The cost
    ** of the first SMALLEST is O(NlogN).  Second and subsequent SMALLEST
    ** primitives are constant time.  The cost of DESTROY is O(N).
    **
    ** There is an added cost of O(N) when switching between TEST and
    ** SMALLEST primitives.
    *************************************************************************
    **  Included in SQLite3 port to C#-SQLite;  2008 Noah B Hart
    **  C#-SQLite is an independent reimplementation of the SQLite software library
    **
    **  SQLITE_SOURCE_ID: 2010-08-23 18:52:01 42537b60566f288167f1b5864a5435986838e3a3
    **
    *************************************************************************
    */
    //#include "sqliteInt.h"

    /*
    ** Target size for allocation chunks.
    */
    //#define ROWSET_ALLOCATION_SIZE 1024
    const int ROWSET_ALLOCATION_SIZE = 1024;
    /*
    ** The number of rowset entries per allocation chunk.
    */
    //#define ROWSET_ENTRY_PER_CHUNK  \
    //                     ((ROWSET_ALLOCATION_SIZE-8)/sizeof(struct RowSetEntry))
    const int ROWSET_ENTRY_PER_CHUNK = 63;

    /*
    ** Each entry in a RowSet is an instance of the following object.
    */
    public class RowSetEntry
    {
      public i64 v;                /* ROWID value for this entry */
      public RowSetEntry pRight;   /* Right subtree (larger entries) or list */
      public RowSetEntry pLeft;    /* Left subtree (smaller entries) */
    };

    /*
    ** Index entries are allocated in large chunks (instances of the
    ** following structure) to reduce memory allocation overhead.  The
    ** chunks are kept on a linked list so that they can be deallocated
    ** when the RowSet is destroyed.
    */
    public class RowSetChunk
    {
      public RowSetChunk pNextChunk;             /* Next chunk on list of them all */
      public RowSetEntry[] aEntry = new RowSetEntry[ROWSET_ENTRY_PER_CHUNK]; /* Allocated entries */
    };

    /*
    ** A RowSet in an instance of the following structure.
    **
    ** A typedef of this structure if found in sqliteInt.h.
    */
    public class RowSet
    {
      public RowSetChunk pChunk;            /* List of all chunk allocations */
      public sqlite3 db;                    /* The database connection */
      public RowSetEntry pEntry;            /* /* List of entries using pRight */
      public RowSetEntry pLast;             /* Last entry on the pEntry list */
      public RowSetEntry[] pFresh;          /* Source of new entry objects */
      public RowSetEntry pTree;             /* Binary tree of entries */
      public int nFresh;                    /* Number of objects on pFresh */
      public bool isSorted;                 /* True if pEntry is sorted */
      public u8 iBatch;                     /* Current insert batch */

      public RowSet( sqlite3 db, int N )
      {
        this.pChunk = null;
        this.db = db;
        this.pEntry = null;
        this.pLast = null;
        this.pFresh = new RowSetEntry[N];
        this.pTree = null;
        this.nFresh = N;
        this.isSorted = true;
        this.iBatch = 0;
      }
    };

    /*
    ** Turn bulk memory into a RowSet object.  N bytes of memory
    ** are available at pSpace.  The db pointer is used as a memory context
    ** for any subsequent allocations that need to occur.
    ** Return a pointer to the new RowSet object.
    **
    ** It must be the case that N is sufficient to make a Rowset.  If not
    ** an assertion fault occurs.
    **
    ** If N is larger than the minimum, use the surplus as an initial
    ** allocation of entries available to be filled.
    */
    static RowSet sqlite3RowSetInit( sqlite3 db, object pSpace, u32 N )
    {
      RowSet p = new RowSet( db, (int)N );
      //Debug.Assert(N >= ROUND8(sizeof(*p)) );
      //  p = pSpace;
      //  p.pChunk = 0;
      //  p.db = db;
      //  p.pEntry = 0;
      //  p.pLast = 0;
      //  p.pTree = 0;
      //  p.pFresh =(struct RowSetEntry*)(ROUND8(sizeof(*p)) + (char*)p);
      //  p.nFresh = (u16)((N - ROUND8(sizeof(*p)))/sizeof(struct RowSetEntry));
      //  p.isSorted = 1;
      //  p.iBatch = 0;
      return p;
    }

    /*
    ** Deallocate all chunks from a RowSet.  This frees all memory that
    ** the RowSet has allocated over its lifetime.  This routine is
    ** the destructor for the RowSet.
    */
    static void sqlite3RowSetClear( RowSet p )
    {
      RowSetChunk pChunk, pNextChunk;
      for ( pChunk = p.pChunk; pChunk != null; pChunk = pNextChunk )
      {
        pNextChunk = pChunk.pNextChunk;
        sqlite3DbFree( p.db, ref pChunk );
      }
      p.pChunk = null;
      p.nFresh = 0;
      p.pEntry = null;
      p.pLast = null;
      p.pTree = null;
      p.isSorted = true;
    }

    /*
    ** Insert a new value into a RowSet.
    **
    ** The mallocFailed flag of the database connection is set if a
    ** memory allocation fails.
    */
    static void sqlite3RowSetInsert( RowSet p, i64 rowid )
    {
      RowSetEntry pEntry;       /* The new entry */
      RowSetEntry pLast;        /* The last prior entry */
      Debug.Assert( p != null );
      if ( p.nFresh == 0 )
      {
        RowSetChunk pNew;
        pNew = new RowSetChunk();//sqlite3DbMallocRaw(p.db, sizeof(*pNew));
        if ( pNew == null )
        {
          return;
        }
        pNew.pNextChunk = p.pChunk;
        p.pChunk = pNew;
        p.pFresh = pNew.aEntry;
        p.nFresh = ROWSET_ENTRY_PER_CHUNK;
      }
      p.pFresh[p.pFresh.Length - p.nFresh] = new RowSetEntry();
      pEntry = p.pFresh[p.pFresh.Length - p.nFresh];
      p.nFresh--;
      pEntry.v = rowid;
      pEntry.pRight = null;
      pLast = p.pLast;
      if ( pLast != null )
      {
        if ( p.isSorted && rowid <= pLast.v )
        {
          p.isSorted = false;
        }
        pLast.pRight = pEntry;
      }
      else
      {
        Debug.Assert( p.pEntry == null );/* Fires if INSERT after SMALLEST */
        p.pEntry = pEntry;
      }
      p.pLast = pEntry;
    }

    /*
    ** Merge two lists of RowSetEntry objects.  Remove duplicates.
    **
    ** The input lists are connected via pRight pointers and are
    ** assumed to each already be in sorted order.
    */
    static RowSetEntry rowSetMerge(
    RowSetEntry pA,    /* First sorted list to be merged */
    RowSetEntry pB     /* Second sorted list to be merged */
    )
    {
      RowSetEntry head = new RowSetEntry();
      RowSetEntry pTail;

      pTail = head;
      while ( pA != null && pB != null )
      {
        Debug.Assert( pA.pRight == null || pA.v <= pA.pRight.v );
        Debug.Assert( pB.pRight == null || pB.v <= pB.pRight.v );
        if ( pA.v < pB.v )
        {
          pTail.pRight = pA;
          pA = pA.pRight;
          pTail = pTail.pRight;
        }
        else if ( pB.v < pA.v )
        {
          pTail.pRight = pB;
          pB = pB.pRight;
          pTail = pTail.pRight;
        }
        else
        {
          pA = pA.pRight;
        }
      }
      if ( pA != null )
      {
        Debug.Assert( pA.pRight == null || pA.v <= pA.pRight.v );
        pTail.pRight = pA;
      }
      else
      {
        Debug.Assert( pB == null || pB.pRight == null || pB.v <= pB.pRight.v );
        pTail.pRight = pB;
      }
      return head.pRight;
    }

    /*
    ** Sort all elements on the pEntry list of the RowSet into ascending order.
    */
    static void rowSetSort( RowSet p )
    {
      u32 i;
      RowSetEntry pEntry;
      RowSetEntry[] aBucket = new RowSetEntry[40];

      Debug.Assert( p.isSorted == false );
      //memset(aBucket, 0, sizeof(aBucket));
      while ( p.pEntry != null )
      {
        pEntry = p.pEntry;
        p.pEntry = pEntry.pRight;
        pEntry.pRight = null;
        for ( i = 0; aBucket[i] != null; i++ )
        {
          pEntry = rowSetMerge( aBucket[i], pEntry );
          aBucket[i] = null;
        }
        aBucket[i] = pEntry;
      }
      pEntry = null;
      for ( i = 0; i < aBucket.Length; i++ )//sizeof(aBucket)/sizeof(aBucket[0])
      {
        pEntry = rowSetMerge( pEntry, aBucket[i] );
      }
      p.pEntry = pEntry;
      p.pLast = null;
      p.isSorted = true;
    }

    /*
    ** The input, pIn, is a binary tree (or subtree) of RowSetEntry objects.
    ** Convert this tree into a linked list connected by the pRight pointers
    ** and return pointers to the first and last elements of the new list.
    */
    static void rowSetTreeToList(
    RowSetEntry pIn,            /* Root of the input tree */
    ref RowSetEntry ppFirst,    /* Write head of the output list here */
    ref RowSetEntry ppLast      /* Write tail of the output list here */
    )
    {
      Debug.Assert( pIn != null );
      if ( pIn.pLeft != null )
      {
        RowSetEntry p = new RowSetEntry();
        rowSetTreeToList( pIn.pLeft, ref ppFirst, ref p );
        p.pRight = pIn;
      }
      else
      {
        ppFirst = pIn;
      }
      if ( pIn.pRight != null )
      {
        rowSetTreeToList( pIn.pRight, ref pIn.pRight, ref ppLast );
      }
      else
      {
        ppLast = pIn;
      }
      Debug.Assert( ( ppLast ).pRight == null );
    }


    /*
    ** Convert a sorted list of elements (connected by pRight) into a binary
    ** tree with depth of iDepth.  A depth of 1 means the tree contains a single
    ** node taken from the head of *ppList.  A depth of 2 means a tree with
    ** three nodes.  And so forth.
    **
    ** Use as many entries from the input list as required and update the
    ** *ppList to point to the unused elements of the list.  If the input
    ** list contains too few elements, then construct an incomplete tree
    ** and leave *ppList set to NULL.
    **
    ** Return a pointer to the root of the constructed binary tree.
    */
    static RowSetEntry rowSetNDeepTree(
    ref RowSetEntry ppList,
    int iDepth
    )
    {
      RowSetEntry p;         /* Root of the new tree */
      RowSetEntry pLeft;     /* Left subtree */
      if ( ppList == null )
      {
        return null;
      }
      if ( iDepth == 1 )
      {
        p = ppList;
        ppList = p.pRight;
        p.pLeft = p.pRight = null;
        return p;
      }
      pLeft = rowSetNDeepTree( ref ppList, iDepth - 1 );
      p = ppList;
      if ( p == null )
      {
        return pLeft;
      }
      p.pLeft = pLeft;
      ppList = p.pRight;
      p.pRight = rowSetNDeepTree( ref ppList, iDepth - 1 );
      return p;
    }

    /*
    ** Convert a sorted list of elements into a binary tree. Make the tree
    ** as deep as it needs to be in order to contain the entire list.
    */
    static RowSetEntry rowSetListToTree( RowSetEntry pList )
    {
      int iDepth;          /* Depth of the tree so far */
      RowSetEntry p;       /* Current tree root */
      RowSetEntry pLeft;   /* Left subtree */

      Debug.Assert( pList != null );
      p = pList;
      pList = p.pRight;
      p.pLeft = p.pRight = null;
      for ( iDepth = 1; pList != null; iDepth++ )
      {
        pLeft = p;
        p = pList;
        pList = p.pRight;
        p.pLeft = pLeft;
        p.pRight = rowSetNDeepTree( ref pList, iDepth );
      }
      return p;
    }

    /*
    ** Convert the list in p.pEntry into a sorted list if it is not
    ** sorted already.  If there is a binary tree on p.pTree, then
    ** convert it into a list too and merge it into the p.pEntry list.
    */
    static void rowSetToList( RowSet p )
    {
      if ( !p.isSorted )
      {
        rowSetSort( p );
      }
      if ( p.pTree != null )
      {
        RowSetEntry pHead = new RowSetEntry();
        RowSetEntry pTail = new RowSetEntry();
        rowSetTreeToList( p.pTree, ref pHead, ref pTail );
        p.pTree = null;
        p.pEntry = rowSetMerge( p.pEntry, pHead );
      }
    }

    /*
    ** Extract the smallest element from the RowSet.
    ** Write the element into *pRowid.  Return 1 on success.  Return
    ** 0 if the RowSet is already empty.
    **
    ** After this routine has been called, the sqlite3RowSetInsert()
    ** routine may not be called again.
    */
    static int sqlite3RowSetNext( RowSet p, ref i64 pRowid )
    {
      rowSetToList( p );
      if ( p.pEntry != null )
      {
        pRowid = p.pEntry.v;
        p.pEntry = p.pEntry.pRight;
        if ( p.pEntry == null )
        {
          sqlite3RowSetClear( p );
        }
        return 1;
      }
      else
      {
        return 0;
      }
    }

    /*
    ** Check to see if element iRowid was inserted into the the rowset as
    ** part of any insert batch prior to iBatch.  Return 1 or 0.
    */
    static int sqlite3RowSetTest( RowSet pRowSet, u8 iBatch, sqlite3_int64 iRowid )
    {
      RowSetEntry p;
      if ( iBatch != pRowSet.iBatch )
      {
        if ( pRowSet.pEntry != null )
        {
          rowSetToList( pRowSet );
          pRowSet.pTree = rowSetListToTree( pRowSet.pEntry );
          pRowSet.pEntry = null;
          pRowSet.pLast = null;
        }
        pRowSet.iBatch = iBatch;
      }
      p = pRowSet.pTree;
      while ( p != null )
      {
        if ( p.v < iRowid )
        {
          p = p.pRight;
        }
        else if ( p.v > iRowid )
        {
          p = p.pLeft;
        }
        else
        {
          return 1;
        }
      }
      return 0;
    }

  }
}