task3

{- 
  TASK 3 - Find and replace binary substring
  Binary string is represented as a cell linked list: string splitted to chunks,
  first chunk stored to the root cell, next one to the cell in ref and so on;
  each cell can have only one ref. 
  Write the method that find and replaces one flags in the binary string
  with another value. Flags and values can be can be of any length, but
  strictly up to 128 bits. The method must replace every flag it finds.
  Flag and the value to be replaced is guaranteed to be greater than 0.
  Lets give a simple example. We have the target flag 101110101 and the value
  to be written 111111111 as inputs, and a linked list of cells, in which the bit
  value of the first cell ends with ...10100001011, and in the ref we have cell that
  starts with 10101000111111...
  The output should be a linked list where the first
  cell ends with ...10100001111, and the second cell starts with 11111000111111...

-}
(int) ubitsize (int a) asm "UBITSIZE";
forall T -> int tuple_length(T tup) asm "TLEN"; 
forall X -> (tuple, ()) push_back (tuple tail, X head) asm "CONS";
forall X -> (tuple, (X)) pop_back (tuple t) asm "UNCONS";
forall X -> (tuple, (X)) tpop_back (tuple t, int k) asm "INDEXVAR";


;; forall X -> (tuple, (X)) un_pair (tuple t) asm "UNPAIR";

forall X -> (tuple, X) ~tpop (tuple t) asm "TPOP";
forall X -> int cast_to_int (X x) asm "NOP";
forall X -> int is_null (X x) asm "ISNULL";
forall X -> int is_int (X x) asm "<{ TRY:<{ 0 PUSHINT ADD DROP -1 PUSHINT }>CATCH<{ 2DROP 0 PUSHINT }> }>CONT 1 1 CALLXARGS";

(int) are_tuples_equal? (tuple t1, tuple t2) {
  int equal? = -1; ;; initial value to true
    
  if (t1.tuple_length() != t2.tuple_length()) {
    ;; if tuples are differ in length they cannot be equal
    return 0;
  }

  int i = t1.tuple_length();
    
  while (i > 0 & equal?) {
    var v1 = t1~tpop();
    var v2 = t2~tpop();
        
    if (is_int(v1) & is_int(v2)) {
      if (cast_to_int(v1) != cast_to_int(v2)) {
        equal? = 0;
      }
    }
        else {
      equal? = 0;
    }

    i -= 1;
  }

  return equal?;
}

() recv_internal() {
}

tuple get_binary_list(cell c) {
  tuple list = null();
  list~push_back(c);
  tuple res = empty_tuple();
    
  while (~ list.is_null()) {
    cell current_cell = list~pop_back();
    slice current_slice = current_cell.begin_parse();

    do {
      res~tpush(current_slice~load_uint(1));
    } until (current_slice.slice_data_empty?())

    repeat (current_slice.slice_refs()) {
      list~push_back(current_slice~load_ref());
    }
  }

  return res;
}

(tuple) reverse_tuple (tuple t1) {
  tuple t2 = empty_tuple();
  repeat (t1.tuple_length()) {
    var value = t1~tpop();
    t2~tpush(value);
  }
  return t2;
}

global tuple stack; 

(cell) store_data(cell c, tuple flag_t, int value_l, int value) {
  slice ds = c.begin_parse();
  builder base = begin_cell();

  while (~ ds.slice_data_empty?()){
    int data = ds~load_uint(1);

    stack~tpush(data);
    if (stack.tuple_length() == flag_t.tuple_length()) {

      int is_e = are_tuples_equal?(stack, flag_t);
      if (is_e) {
        stack = empty_tuple();
        base~store_uint(value, value_l); 
      } else {
        int v = stack~tpop_back(0);
        base~store_uint(v, 1); 
      }
    }
    
  }

  if (~ ds.slice_refs_empty?()) {
    return base.store_ref(store_data(ds~load_ref(), flag_t, value_l, value)).end_cell();
  }

  if (stack.tuple_length() > 0) {
    builder bb = begin_cell();
    repeat (stack.tuple_length()) {
      int v = stack~tpop_back(0);
      bb~store_uint(v, 1); 
    }

    return base.store_ref(bb.end_cell()).end_cell();
  }
  return base.end_cell();
}

;; testable
(cell) find_and_replace(int flag, int value, cell linked_list) method_id {
  int flag_len = ubitsize(flag); 
  int value_len = ubitsize(value); 
  tuple flag_t = get_binary_list(begin_cell().store_uint(flag, flag_len).end_cell());

  stack = empty_tuple();
  cell result = store_data(linked_list, flag_t, value_len, value);
  return result;
}