#include <stdio.h>
#include <stdlib.h>

typedef struct elem Node ;

struct elem { int val
            ; Node* next
            ; } ;

int lookup (int) , insert (int) , delete (int)  ;

Node *p ;               // pointer to the list
Node *r ;               // pointer to the current position for insertion
#define LEN 256         // initial lenght of the list

int
main (int argc , char** argv , char** envp)
{
  r = p = malloc (LEN * sizeof (Node)) ;
  p->val = 0 ; p->next = NULL ;

  // some stuff here

  free (p) ;
  return 0 ;
}

int
lookup (int val)
{
  Node* s = p ;

  while (s->val != val && s->next) s = s->next ;

  if (s->val == val) return val ;
  else return 0 ;
} ;

int
insert (int val)
{
  if (r == p + LEN - 1) { printf ("overflow\n") ; return 1 ; } ;

  r->val = val ; r->next = NULL ;
  if (r != p) (r - 1)->next = r ;
  r += 1 ;

  return 0 ;
} ;

int
delete (int val)
{
  Node* s = p ;

  while (s->val != val && s->next) s = s->next ;

  if (s->next && s->val == val)                // start gc
  {
    while (s->next) { s->val = s->next->val ; s += 1 ; } ;
    r = s ;
    return 0 ;
  }
  else if (s->next == NULL && s->val == val)  // just reset pointer to succ elem
  {
    if (s != p) (s - 1)->next = NULL ;
    r = s ;
    return 0 ;
  }

  else return 1;  // not found
} ;

#include <stdio.h>

typedef struct elem Node ; struct elem { int val ; Node* next ; } ;

void prn (Node*), rreverse (Node*), ireverse (Node*), trreverse (Node*, Node*) ;

int
main (int argc, char** argv, char** envp)
{
  Node a, b, c, d ;

  a.val = 10 ; a.next = &b ;
  b.val = 20 ; b.next = &c ;
  c.val = 30 ; c.next = &d ;
  d.val = 40 ; d.next = NULL ;

  // debug printing:
  prn (&a) ; rreverse (&a) ;
  prn (&d) ; ireverse (&d) ;
  prn (&a) ; trreverse (NULL, &a) ;
  prn (&d) ; return 0 ;
}

//           ***   recursive way:

void
rreverse (Node* p)
{
  Node* r = p->next ;  // r - pointer to my current tail
  if (!r) return ;        // if no tail - r points on former last elem.
                          //it will not be changed anymore
  rreverse (r) ;
  p->next->next = p ; // change pointer of my former succ to point on me now
  p->next = NULL ;  // change my new succ to NULL, but NULL will be buble up continiously
  p = r ;       // change pointer to point on former last elem (see line 02)
                // any time it will be different p, but just the same r
                // at last p will be the global pointer
}
// NB: no tail recursion here, so the stack will grow up


//      ***   tail recursive way:

void
trreverse (Node* a, Node* p)
{
  Node* r = p->next ;
  p->next = a ;
  if (r) trreverse (p, r) ;
}
// if your compiler is TOC - you are win


//     ***   iterative way:

void
ireverse (Node* p)
{
  Node* iter ;
  Node* temp = NULL ;       // the first elem will put it in the next pointer
  Node* work = p ;          // for while loop only - pointer to the first elem

  while (work)             //           my pointer here
  {
    iter = work->next ;     // save      where to move on the next step
    work->next = temp ;     // rewrite   my own next-pointer
    temp = work ;           // remember  my adr
    work = iter ;           // for while loop only - pointer to the next elem
  }

  p = temp ;                // change global pointer to former last elem
}


//   ***   for debug output only
void
prn (Node* h)
{
  while (h) { printf ("--> %i\t", h->val) ; h = h->next ; }
  printf ("\n") ;
}

#include <stdio.h>
#include <stdlib.h>

#define SL_SIZE 17

typedef struct elem Node ; struct elem { int val ; Node* next ; } ;
Node* p ; Node* r ;

typedef struct supelem Node1 ; struct supelem { int val ; Node1* next ; Node* down ; } ;
Node1* p1 ; Node1* r1 ;

int minval () ;
int coin (int s) { srandom (s) ; int x = random () ; return 1 & x ; }

int
main (int argc, char** argv, char** envp)
{
  // generating skip-list structure with size (SL_SIZE)
  p = malloc (SL_SIZE * sizeof (Node)) ;                 // for the first-level list
  p->next = p ;                                          // create null-sentinel
  r = p + 1 ;                                            // current pos
  p1 = malloc ((3 * SL_SIZE / 4) * sizeof (Node1)) ;     // for the second-level list
  p1->next = p1 ;                                        // create null-sentinel
  r1 = p1 + 1 ;                                          // current pos

  // some stuff here

  free (p) ; free (p1) ; return 0 ;
}


int
insert1 (Node* x)
{
  if (r1 - p1 > (3 * SL_SIZE / 4)) { return 1; } ;

  Node1 y ; y.val = x->val ; y.down = x ;

  // the first element insertion
  if (r1 == p1) { y.next = r1 ; *r1 = y ; r1 += 1 ; return 0 ; }

  Node1 *s = p1 ;  // for list traversing
  Node1 *t = p1 ;

  // all except the first and the last elements insertion
  while (s != s->next)
  {
    if (s->next->val > x->val)
    {
      y.next = s->next ;
      s->next = r1 ;
      *r1 = y ; r1 += 1 ; return 0 ;
    }
    t = s ;       // save as previos element pointer
    s = s->next ; // move to the next element
  };

  // the last element insertion
  if   (s->val < x->val) { s->next = r1 ; y.next  = r1 ; }
  else { y.next  = s ; t->next = r1 ; }

  *r1 = y ; r1 += 1 ; return 0 ;
}


int
delete (int x)
{
  if (x < minval ()) return 1 ;

  // at first in low-level list:
  Node *s = p ;  // for list traversing
  Node *t = p ;  //

  while (s != s->next)
  {
    if (s->val == x) { t->next = s->next ; return 0 ; }
    t = s; s = s->next ; // save previos pointer and increment
  }
  if (s->val == x) { t->next = t->next ; }

  // now in high-level list:
  Node1 *s1 = p1 ;  // for list traversing
  Node1 *t1 = p1 ;

  while (s1 != s1->next)
  {
    if (s1->val == x) { t1->next = s1->next ; return 0 ; }
    t1 = s1 ; s1 = s1->next ; // save previos pointer and increment
  }
  if (s1->val == x) { t1->next = t1->next ; return 0 ; }

  return 1 ;
}


int
lookup (int x)
{
  if (r == p + 1) return 0 ;
  if (x < minval ()) return 0 ;

  Node1* s1 = p1 ;
  Node1* t1 = p1 ;
  while (s1->next->val < x && s1->next != s1) s1 = s1->next ;
  if (s1->val == x) return 1 ;
  Node* s = s1->down ;
  while (s->next != s)
  {
    if (s->val == x) return 1 ;
    s = s->next ;
  } ;

  return 0 ;
}


int minval () { return p->next->val ; }


int
maxval ()
{
  if (r == p + 1) return r->val ;
  Node1* s1 = p1 ;
  while (s1->next != s1) s1 = s1->next ;
  Node* s = s1->down;
  while (s->next != s) s = s->next ;

  return s->val ;
}


int
insert (int x)
{
  if (r - p > SL_SIZE) return 1 ;

  Node y ; y.val = x ;

  // the first element insertion
  if (r == p)
  {
    if (!x) return 1 ;
    else
    {
      y.next = r ; *r = y ;
      if (coin (x)) insert1 (r) ;
      r += 1 ; return 0 ;
    }
  }

  // the next element insertion
  Node *s = p ;  // for list traversing
  Node *t = p ;

  // all except the first and the last elements insertion
  while (s != s->next)
  {
    if (s->next->val > x)
    {
      if (s->val != x)
      {
        y.next = s->next ; s->next = r ; *r = y ;
        if (coin (x)) insert1 (r) ;
        r += 1 ;  return 0 ;
      }
      else return 1 ;
    };
    t = s ;       // save as previos element pointer
    s = s->next ; // move to the next element
  };

  // the last element insertion
  if (s->val  < x) { s->next = r ; y.next  = r ; }
  else if (s->val == x) return 1 ;
  else { y.next  = s ; t->next = r ; }

  *r = y ; r += 1 ; return 0 ;
}

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define LEN 128

int isEmpty (void) ;
int push    (int) ;
int pull    (void) ;

int* p ;    // stack pointer
int* r ;    // current position

int
main (int argc , char** argv , char** envp)
{
  p = r = malloc (LEN  * sizeof (int)) ;

  // assert (isEmpty ()) ;
  assert (push (100)) ; assert (isEmpty()) ; assert (push (200)) ;
  int x = pull () ; assert (200 == x) ; assert (isEmpty ()) ;
  x = pull () ; assert (100 == x) ;
  // assert (pull ()) ;

  free (p) ;
  return 0 ;
}

int
isEmpty (void)
{
  if (p == r) return 0 ; else return 1 ;
} ;

int
push (int x)
{
  if (r == p + LEN - 1) { puts ("overflow\t") ; }
  else { r = r + 1 ; *r = x ; } ;
  return r - p ;
} ;

int
pull ()
{
  int x ;
  if (r == p) { puts ("empty\t") ; return r - p ; }
  else { x = *r ; r = r - 1 ; return x ; }
} ;

module type Stack =
sig
  type t
  type a

  val empty : a
  val isEmpty : a -> bool
  val push : t * a -> a
  val pull : a -> t
end

module C : Stack =
struct
  type t = int
  type a = Nil | Cons of t * a

  let empty = Nil
  let isEmpty xs = match xs with | Nil -> true | _ -> false
  let push (x , s) = Cons (x , s)
  let pull s = match s with Nil -> 0 | Cons (x , s) -> x
end

#include <stdio.h>
#include <stdlib.h>

#define KEY_NUM 16                             // size
#define ALL_BUSY ((1 << KEY_NUM) - 1)          // for flags

typedef struct vals Vals;
struct vals { int key; int val; };

int  ukeys[KEY_NUM];       // keyspace
Vals tvals[KEY_NUM];       // table with key-value objects
unsigned int flags = 0;    // busy|free keystatus

Vals lookup (int) ;
int  insert (int) , delete (int) ;


int
main (int argc, char** argv, char** envp)
{
  // initialize keyspace with sequence from 0 to KEY_NUM - 1:
  int i = 0 ; while (i < KEY_NUM) { ukeys[i] = i ; i++ ; }

  return 0 ;
}


Vals
lookup (int key)
{
  if (key < 0 || key > KEY_NUM - 1)
    { printf ("nonexist elem: key=%i\n", key) ;
      exit (1) ;
    } ;
  return tvals[key] ;
}


int
insert (int val)
{
  if (flags == ALL_BUSY) { printf ("overflow. val=%i\n", val) ; return 1 ; } ;

  // find the first free key in keyspace:
  int i, k ;
  for ( i = 0, k = flags; i < 8; i++, k >>= 1 )
      { if (k & 1) continue ; else break ; } ;

  // store value in the table:
  tvals[ukeys[i]].key = i; tvals[ukeys[i]].val = val;

  // re-arrange flags
  flags |= (1 << i) ;   // to indicate that this key is in use now
  if (flags == ALL_BUSY) printf ("table is full now.\n") ;

  return 0 ;
}


int
delete (int key)
{
  if (key < 0 || key > KEY_NUM - 1)
    { printf ("nonexist key=%i\n", key) ; return 1;  } ;

  int k = (1 << key) ;     // is the key in use?
  if (k & flags) { tvals[key].val = 0 ; } else { return 1 ; } ;

  // re-arrange flags
  flags = ~k & flags ;        // to indicate that this key is free now

  return 0 ;
}

// keys : natural nums, vals : natural nums > 0

#include <stdio.h>
#include <stdlib.h>

#define PRIME 11
#define MAX 5

typedef struct elem Elem;

struct elem
        { int    key ;
          int    val ;
          Elem*  next ;
          Elem*  prev ;
        } ;
Elem* table[PRIME] ;           // table with lists of key-value objects
Elem *r, *p ;                  // current position , init position

int lookup (int) , insert (int, int) , delete (int) , hash_func (int) ;

int
main (int argc, char** argv, char** envp)
{
  // initialization
  r = p = malloc (MAX * sizeof (Elem)) ;
  int i ; for (i = 0 ; i < PRIME ; i++) table[i] = NULL ;

  // some stuff here

  // finalization
  free (p) ; return 0 ;
}


int
lookup (int key)
{
  int h = hash_func (key) ; Elem* s = table[h] ;

  while (s)
  {
    if (s->key == key) return s->val ;
    s = s->next ;
  } ;

  return 0 ;
}


int
insert (int key, int val)
{
  if (r - p > MAX - 1) { printf ("overflow\n") ; return -1 ; } ;

  int h = hash_func (key) ; Elem* s = table[h] ;
  Elem x ; x.key = key ; x.val = val ;

  if (!s)
  {
    x.prev = r ; x.next = NULL ;
    *r = x ;
    table[h] = r ;
  }
  else
  {
    while (s->val < val && s->next) s = s->next ;
    if (s->next)
    {
      x.prev = s->prev ; x.next = s ;
      *r = x ;
      s->prev->next = r ; s->prev = r ;
    }
    else
    {
      x.prev = s ; x.next = NULL ;
      *r = x ;
      s->next = r ;
    } ;
  } ;
  r += 1 ;

  return h ;
}


int
delete (int key)
{
  int h = hash_func (key) ; Elem* s = table[h] ;

  while (s)
  {
    if (s->key == key)
    {
      if (s->prev) s->prev->next = s->next ;
      else table[h] = s->next ;
      s->val = 0 ;
      return 0 ;
    } ;
    s = s->next ;
  } ;

  return 1 ;
}


int
hash_func (int key)
{ return key % PRIME; }


// naive garbage collector
void
gc (void)
{
  Elem* g = p ;

  while (g < r)
  {
    if (!g->val)
    {
      while (!r->val) { r -= 1; } ;
      r->prev->next = g ;
      *g = *r ;
      r->val = 0 ;
    } ;
    g += 1 ;
  } ;
}

// universal hash  for m * 2 elements
// p    : prime number
// keys : natural nums [0, p - 1]
//
// hash function in the form: (((a * key + b) mod p) mod m)
// restrictions : 0 < a < p - 1;     0 < b < p - 1;   m < p;     key < p

#include <stdio.h>
#include <stdlib.h>

#define MSIZE 31   // size of the main key table m < p
#define PRIME 283  // primary number p > m

typedef struct elem Elem;

struct elem
        { int    a ;
          int    b ;
          int    tv[4] ;
        } ;

Elem table[MSIZE] ;

int coin (void) , hash_func (int, int, int, int) ;
int lookup (int) , insert (int), delete (int) ;


int
main (int argc, char** argv, char** envp)
{
  // initialization. size of all secondary tables is 4
  int i = 0 ;

  while (i < MSIZE)
    { Elem x = { x.a = 0, x.b = 0 } ; table[i] = x ; i++ ; } ;

  srandom ((long int) &table) ;  // seed the gen for 'coin flip' proc

  // some stuff here

  return 0 ;
}


int
hash_func (int a, int b, int m, int key)
{ return (a * key + b) % PRIME % m; }


int
insert (int key)
{
  int h1, h2, h0 = hash_func (1, 0, MSIZE, key) ;
  Elem* s = &table[h0] ;

  h1 = hash_func (s->a, s->b, 4, key) ;

  if ( ! s->tv[h1] ) s->tv[h1] = key ;                 // ok
  else
  {                                                    // key collision
    lb1:  s->a = coin () ;                             // change coef "a" randomly
          s->b = coin () ;                             // change coef "b" randomly
          h1 = hash_func (s->a , s->b , 4 , key) ;
          h2 = hash_func (s->a , s->b , 4 , *s->tv) ;
          if (h2 == h1) goto lb1 ;                     // yes-yes, I know...
    s->tv[h2] = *s->tv ;
    s->tv[h1] = key ;
  } ;

  return 0 ;
}


int
lookup (int key)
{
  int h0 = hash_func (1, 0, MSIZE, key) ;
  Elem s = table[h0] ;
  int h1 = hash_func (s.a, s.b, 4, key) ;

  return s.tv[h1] ;
}


int
delete (int key)
{
  int h0 = hash_func (1, 0, MSIZE, key) ;
  Elem *s = &table[h0] ;
  int h1 = hash_func (s->a, s->b, 4, key) ;
  s->tv[h1] = 0 ;

  return 0 ;
}


int
coin ()
{
  int y = random () ;
  srandom (y) ;
  return y % PRIME ;
}

#include <stdlib.h>
#include <stdio.h>
#define INIT 15   // max heap size

int p[INIT];
int k;

void
max_health (int i)
{
  int cl = (i << 1) | 1;   // left child
  int cr = (i << 1) + 2;   // right child

  if      (p[cl] > p[cr] && p[i] < p[cl]) { p[i] ^= p[cl] ^= p[i] ^= p[cl]; }
  else if (p[cl] < p[cr] && p[i] < p[cr]) { p[i] ^= p[cr] ^= p[i] ^= p[cr]; };

  if (i <= k/2 - 2) { max_health (cl); max_health (cr); };
}

int
insert (int x)
{
  if (k == INIT) return 0;
  p[k] = x;
  max_health (0);
  k += 1;
  return k;
}

int
extract ()
{
  int m = *p;
  *p = 0;
  max_health (0);
  k -= 1;
  return m;
}

int count (void) { return k; }

int
main (int argc, char** argv, char** envp)
{
  int i = 0; while (i < INIT) { p[i] = 0; i++; };
  k = 0;

  return 0;
}

module type Heap =
  sig
    type e
    type h

    val empty     : h
    val isEmpty   : h -> bool
    val insert    : e  *  h -> h
    val merge     : h  *  h -> h
    val findMin   : h -> e          (* бросает исключение Empty_heap при пустой куче *)
    val deleteMin : h -> h          (* бросает исключение Empty_heap при пустой куче *)
  end

type 'a heap = E | T of int  *  'a  *  'a heap  *  'a heap

module IntLeftHeap : Heap =
  struct

    exception Empty_heap ;;

    type e    = int
    type h    = int heap
    let empty = E


    let rank xs = match xs with | E -> 0 | T (r , _ , _ , _) -> r


    let makeT (x, a, b) =
      if (rank a) >= (rank b)
      then T (rank b + 1, x, a, b)
      else T (rank a + 1, x, b, a)


    let rec merge (xs , ys) = match (xs , ys) with
      | (E , h) | (h , E) -> h
      | ((T(_ , x , a1 , b1) as h1) , (T(_ , y , a2 , b2) as h2)) ->
          if x <= y
          then makeT (x , a1 , merge (b1 , h2))
          else makeT (y , a2 , merge (h1 , b2))


    let isEmpty xs = match xs with | E -> true | _ -> false

    let insert (x , xs) = merge (T(1, x , E, E) , xs)


    let deleteMin xs = match xs with
      | E -> raise Empty_heap
      | (T(_ , x , a , b)) -> merge (a , b)


    let findMin xs = match xs with
      | E -> raise Empty_heap
      | (T(_ , x , a , b)) -> x

  end

  ; зададим трёхмерный разреженный массив 3x3x3

  set ^a(0,0,0) = 1,
      ^a(2,2,0) = 1,
      ^a(2,0,1) = 1,
      ^a(0,2,1) = 1,
      ^a(2,2,2) = 1,
      ^a(2,1,2) = 1

  merge column = ^a(2,2)
  write column

  ; вывод:

  column(0)=1
  column(2)=1