3.fc

{- 
  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.
  Flag and the value may be of different lengths.
  When there are overlapping flags, only the first one
  from the overlap needs to be replaced (for example, if the flag is 101,
  value is 111, and string is 10101, then the result would be 11101, but if
  the string is 1010101, then the result would be 1110111).
  Every cell in the input linked list, except for the last one
  (the one that is the deepest in the tree), is guaranteed to be full
  (guaranteed to contain 1023 bits).
  The requirements on the output cell are more loose - only the concatenation of bits
  from the linked list needs to match that of the expected answer, but the structure
  itself may be different (for example, for the purposes of comparing the answer,
  a cell with bit 1 and a ref containing bits 10 is the same as a cell containing
  bit 11 and a ref with bit 0 - they both make up a bitstring 110).
  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...

-}
;; ;; target          endWith    startWith         
;; ;; 101110101       1010000101110101000111111
;; ;; 111111111       1010000111111111000111111
;; ;;

() recv_internal() {
}

(int) tlen(tuple t) asm "TLEN";
;; (slice, slice) load_bits(slice s, int len) asm(s len -> 1 0) "LDSLICEX"; ;; causes compile error
slice skip_bits(slice s, int len) asm "SDSKIPFIRST";
(slice, ()) ~skip_bits(slice s, int len) asm "SDSKIPFIRST";
int slice_data_empty?(slice s) asm "SDEMPTY";
;; builder store_int(builder b, int x, int len) asm(x b len) "STIX"; ;; causes compile error
(slice, int) ~load_int(slice s, int len) asm(s len -> 1 0) "LDIX";
(slice, int) ~load_uint(slice s, int len) asm( -> 1 0) "LDUX";
int slice_bits(slice s) asm "SBITS";
int slice_refs(slice s) asm "SREFS";
(int, int) slice_bits_refs(slice s) asm "SBITREFS";
forall X -> (tuple, X) ~tpop (tuple t) asm "TPOP";
int tuple_length (tuple t) asm "TLEN";
forall X -> (tuple) to_tuple (X x) asm "NOP";

int int_size(int n) asm "UBITSIZE";



;; 3rd try - last day
(cell) find_and_replace(int flag, int value, cell linked_list) method_id {
  slice cs = linked_list.begin_parse();
  int cs_size = cs.slice_bits();
  int flag_size = int_size(flag);

  if(cs_size >= flag_size){
    return single_part(flag, value, linked_list);
  } else {
    if(cs.slice_refs() == 0){
      return linked_list;
    } else {
      cell ref = cs.preload_ref();
      slice ref_cs = ref.begin_parse();
      int ref_cs_size = ref_cs.slice_bits();

      if(cs_size + ref_cs_size >= flag_size){
        return double_part(flag, value, linked_list);
      } else {
        return linked_list;
      }
    }
  }
}

(cell) single_part(int flag, int value, cell linked_list) method_id {
  slice cs = linked_list.begin_parse();
  int flag_size = int_size(flag);
  int value_size = int_size(value);
  int check = cs.preload_uint(flag_size);

  int remove = 0;
  int remove_size = 0;
  int replace = 0;
  int replace_size = 0;

  if(check == flag){
    remove_size = flag_size;
    replace_size = value_size;
    remove = cs~load_uint(remove_size);
    replace = value;
  } else {
    remove_size = 1;
    replace_size = 1;
    remove = cs~load_uint(remove_size);
    replace = remove;
  }
  if(cs.slice_bits() > 0){
    cell next_cell = begin_cell().store_slice(cs).end_cell();
    return begin_cell().store_uint(replace, replace_size)
                        .store_ref(find_and_replace(flag, value, next_cell))
                        .end_cell();
  } else {
    if(cs.slice_refs() > 0){
      cell ref = cs~load_ref();
      return begin_cell().store_uint(replace, replace_size)
                          .store_ref(find_and_replace(flag, value, ref))
                          .end_cell();
    } else {
      return begin_cell().store_uint(replace, replace_size).end_cell();
    }
  }
}

(cell) double_part(int flag, int value, cell linked_list) method_id {
  slice cs = linked_list.begin_parse();
  int flag_size = int_size(flag);
  int value_size = int_size(value);
  int part1_size = cs.slice_bits();
  int part2_size = flag_size - part1_size;
  
  cell ref = cs.preload_ref();
  slice ref_cs = ref.begin_parse();
  
  int check1 = cs.preload_uint(part1_size);
  int check2 = ref_cs.preload_uint(part2_size);
  slice both = begin_cell()
              .store_uint(check1, part1_size)
              .store_uint(check2, part2_size)
              .end_cell()
              .begin_parse();
  int check = both.preload_uint(flag_size);

  int remove = 0;
  int remove_size = 0;
  int replace = 0;
  int replace_size = 0;

  if(check == flag){
    int temp_int = ref_cs~load_uint(part2_size);
    if(ref_cs.slice_bits() > 0){
      cell next_cell = begin_cell().store_slice(ref_cs).end_cell();
      return begin_cell().store_uint(value, value_size)
                        .store_ref(find_and_replace(flag, value, next_cell))
                        .end_cell();
    } else {
      if(ref_cs.slice_refs() > 0){
        cell ref_ref = ref_cs~load_ref();
        return begin_cell().store_uint(value, value_size)
                          .store_ref(find_and_replace(flag, value, ref_ref))
                          .end_cell();
      } else {
        return begin_cell().store_uint(value, value_size).end_cell();
      }
    }
  } else {
    int one_bit = cs~load_uint(1);
    if(cs.slice_bits() > 0){
      cell next_cell = begin_cell().store_slice(cs).end_cell();
      return begin_cell().store_uint(one_bit, 1)
                        .store_ref(find_and_replace(flag, value, next_cell))
                        .end_cell();
    } else {
      return begin_cell().store_uint(one_bit, 1)
                        .store_ref(find_and_replace(flag, value, ref))
                        .end_cell();
    }
  }
}

;; (int) int_size(int n) method_id {
;;   int size = 0;
;;   while(n > 0){
;;     size += 1;
;;     n >>= 1;
;;   }
;;   return size;
;; }
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;



;; ;; 2nd try (after clarifications)
;; ;; testable
;; (cell) find_and_replace(int flag, int value, cell linked_list) method_id {
;;   cell next_cell = null();

;;   int remove_int = 0;
;;   int remove_int_size = 0;
;;   int replace_int = 0;
;;   int replace_int_size = 0;

;;   int flag_size = int_bits(flag);
;;   int value_size = int_bits(value);

;;   slice cs = linked_list.begin_parse();
;;   int cs_size = cs.slice_bits();

;;   ;; if(cs_size == 0){ ;; has become empty
;;   ;;   if(cs.slice_refs_empty?()){
;;   ;;     return begin_cell().end_cell();
;;   ;;   } else {
;;   ;;     cell ref = cs~load_ref();
;;   ;;     return find_and_replace(flag, value, ref);
;;   ;;   }
;;   ;; }

;;   if(cs.slice_refs_empty?()){ ;; if doesn't have any refs so this is last chunk

;;     if(cs_size < flag_size){ ;; bits left in the end are less than flag size
;;       return linked_list;
;;     } else { ;; enough bits left to check flag presence
;;       int check_int = int_from_one_slice(cs, flag_size);
;;       if(check_int == flag){ ;; replacement should happen
;;         remove_int_size = flag_size;
;;         replace_int_size = value_size;
;;         remove_int = cs~load_uint(remove_int_size);
;;         replace_int = value;
;;       } else { ;; we remove 1 bit from beginning and move forward
;;         remove_int_size = 1;
;;         replace_int_size = 1;
;;         remove_int = cs~load_uint(remove_int_size);
;;         replace_int = remove_int;
;;       }
;;       if(cs.slice_bits() > 0){
;;         cell next_cell = begin_cell().store_slice(cs).end_cell();
;;         return begin_cell()
;;                 .store_uint(replace_int, replace_int_size)
;;                 .store_ref(find_and_replace(flag, value, next_cell))
;;                 .end_cell();
;;       } else {
;;         return begin_cell()
;;                 .store_uint(replace_int, replace_int_size)
;;                 .end_cell();
;;       }
;;     }

;;   } else { ;; if linked_list has a ref and is not last chunk
;;     cell ref = cs~load_ref(); ;; maybe will need to be changed to preload instead of load
;;     slice ref_cs = ref.begin_parse();
;;     int ref_cs_size = ref_cs.slice_bits();

;;     if(flag_size > (cs_size + ref_cs_size)){ ;; total bits left are less than flag size
;;       return linked_list; ;; this only happens in last 2 chunks
;;     } elseif(flag_size > cs_size){ ;; 2 haves should be checked, end of linked_list and beginning of ref
      
;;       int check_int = int_from_two_slices(cs, cs_size, ref_cs, flag_size - cs_size);
;;       if(check_int == flag){ ;; replacement should happen
;;         int temp_int = ref_cs~load_uint(flag_size - cs_size);
;;         if(ref_cs.slice_bits() > 0){
;;           cell next_cell = begin_cell().store_slice(ref_cs).end_cell();
;;           return begin_cell()
;;                  .store_uint(value, value_size)
;;                  .store_ref(find_and_replace(flag, value, next_cell))
;;                  .end_cell();
;;         } else {
;;           return begin_cell()
;;                  .store_uint(value, value_size)
;;                  .end_cell();
;;         }
;;       } else { ;; we remove 1 bit from beginning and move forward
;;         int one_bit = cs~load_uint(1);
;;         if(cs.slice_bits() > 0){
;;           next_cell = begin_cell().store_slice(cs).store_ref(ref).end_cell();
;;         } else {
;;           next_cell = ref;
;;         }
;;         return begin_cell()
;;                 .store_uint(one_bit, 1)
;;                 .store_ref(find_and_replace(flag, value, next_cell))
;;                 .end_cell();
;;       }

;;     } else { ;; checking only linked list is enough becuse flag_size doesn't reach end of it
;;       int check_int = int_from_one_slice(cs, flag_size);
;;       if(check_int == flag){ ;; replacement should happen
;;         remove_int_size = flag_size;
;;         replace_int_size = value_size;
;;         remove_int = cs~load_uint(remove_int_size);
;;         replace_int = value;
;;       } else { ;; we remove 1 bit from beginning and move forward
;;         remove_int_size = 1;
;;         replace_int_size = 1;
;;         remove_int = cs~load_uint(remove_int_size);
;;         replace_int = remove_int;
;;       }
;;       if(cs.slice_bits() > 0){
;;         next_cell = begin_cell().store_slice(cs).store_ref(ref).end_cell();
;;       } else {
;;         next_cell = ref;
;;       }
;;       return begin_cell()
;;               .store_uint(replace_int, replace_int_size)
;;               .store_ref(find_and_replace(flag, value, next_cell))
;;               .end_cell();
;;     }
;;   }

;;   return begin_cell().end_cell(); ;; just to silence the compiler
;; }


;; ;; ;; first try (before clarifications)
;; ;; ;; testable
;; ;; (cell) find_and_replace(int flag, int value, cell linked_list) method_id {
;; ;;   tuple tp = linked_list_to_tuple(linked_list);
;; ;;   (tuple sizes, tuple cum_sizes) = get_sizes_and_cum_sizes_tuples(tp);
;; ;;   int total_size = cum_sizes.at(tp.tuple_length() - 1);
;; ;;   int flag_size = int_bits(flag);

;; ;;   int i = 0;
;; ;;   while(i <= (total_size - flag_size)){
;; ;;     slice empty_slice = "";
;; ;;     ;; get slice at index i
;; ;;     (tuple temp_tp, slice check) = get_or_set_slice_in_tuple(i, 0, empty_slice, tp, sizes, cum_sizes);
;; ;;     int int_from_check = check~load_uint(flag_size);
;; ;;     if(flag == int_from_check){
;; ;;       slice value_to_slice = int_to_slice(value, flag_size);
;; ;;       ;; set value as a replacement for flag
;; ;;       (tp, slice temp_slice) = get_or_set_slice_in_tuple(i, -1, value_to_slice, tp, sizes, cum_sizes);
;; ;;       i += flag_size;
;; ;;     } else {
;; ;;       i += 1;
;; ;;     }
;; ;;   }

;; ;;   cell output_linked_list = tuple_to_linked_list(tp);
;; ;;   return output_linked_list;
;; ;; }

;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; new helper functions:

;; ;; parameters should be checked before passing
;; (int) int_from_one_slice(slice cs, int int_size) method_id {
;;   int output = cs~load_uint(int_size); ;; maybe could be changed to preload later to reduce gas
;;   return output;
;; }

;; (int) int_from_two_slices(slice cs1, int int_size_1, slice cs2, int int_size_2) method_id {
;;   int out1 = cs1~load_uint(int_size_1);
;;   int out2 = cs2~load_uint(int_size_2);

;;   ;; test
;;   out1 <<= int_size_2;
;;   int out = out1 + out2;
;;   return (out);
;;   ;; test

;;   cell combination_cell = begin_cell()
;;                           .store_uint(out1, int_size_1)
;;                           .store_uint(out2, int_size_2)
;;                           .end_cell();
;;   slice combination_cs = combination_cell.begin_parse();
;;   int combination_out_int = combination_cs~load_uint(int_size_1 + int_size_2);
;;   return combination_out_int;
;; }

;; (int) int_bits(int n) method_id {
;;   int count = 0;
;;   while (n > 0) {
;;       count += 1;
;;       n >>= 1; ;; Shift the number right by 1
;;   }
;;   return count;
;; }


;; (cell) one_chunk_single_run(int flag, int value, cell linked_list) method_id {
;;   int remove_int = 0;
;;   int remove_int_size = 0;
;;   int replace_int = 0;
;;   int replace_int_size = 0;

;;   int flag_size = int_bits(flag);
;;   int value_size = int_bits(value);

;;   slice cs = linked_list.begin_parse();
;;   int cs_size = cs.slice_bits();

;;   if(cs_size < flag_size){
;;     return linked_list;
;;   } else {
;;     int check_int = int_from_one_slice(cs, flag_size);
;;     if(check_int == flag){ ;; replacement should happen
;;       remove_int_size = flag_size;
;;       replace_int_size = value_size;
;;       remove_int = cs~load_uint(remove_int_size);
;;       replace_int = value;
;;     } else { ;; we remove 1 bit from beginning and move forward
;;       remove_int_size = 1;
;;       replace_int_size = 1;
;;       remove_int = cs~load_uint(remove_int_size);
;;       replace_int = remove_int;
;;     }
;;     cell next_cell = begin_cell().store_slice(cs).end_cell();
;;     return begin_cell()
;;             .store_uint(replace_int, replace_int_size)
;;             .store_ref(find_and_replace(flag, value, next_cell))
;;             .end_cell();
;;   }
;; }
;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; helper functions:

;; ;; (slice) int_to_slice(int n, int n_size) method_id {
;; ;;   slice output = begin_cell()
;; ;;                   .store_uint(n, n_size)
;; ;;                   .end_cell()
;; ;;                   .begin_parse();
;; ;;   return output;
;; ;; }

;; ;; ;; first: sizes, second: cum_sizes
;; ;; (tuple, tuple) get_sizes_and_cum_sizes_tuples(tuple tp) method_id {
;; ;;   tuple sizes = empty_tuple();
;; ;;   tuple cum_sizes = empty_tuple();
;; ;;   int i = 0;
;; ;;   while(i < tp.tuple_length()){
;; ;;     sizes~tpush(tp.at(i).slice_bits());
;; ;;     if(i == 0){
;; ;;       cum_sizes~tpush(sizes.at(0));
;; ;;     } else {
;; ;;       cum_sizes~tpush(cum_sizes.at(i - 1) + sizes.at(i));
;; ;;     }
;; ;;   }
;; ;;   return (sizes, cum_sizes);
;; ;; }

;; ;; ;; job = -1 for set and 0 for get, leave value = 0 when doesn't exist
;; ;; (slice, int) get_or_set_bit_in_slice(int i, int job, int int_value, slice cs) method_id {
;; ;;   builder output_builder = begin_cell();
;; ;;   int output_int = 0;
  
;; ;;   int j = 0; 
;; ;;   int cs_size = cs.slice_bits();
;; ;;   while(j < cs_size){
;; ;;     int read_int = cs~load_uint(1);
;; ;;     if(j == i){
;; ;;       if(job == -1){
;; ;;         output_int = int_value;
;; ;;       } else {
;; ;;         output_int = read_int;
;; ;;       }
;; ;;       output_builder = output_builder.store_uint(output_int, 1);
;; ;;     }
;; ;;     output_builder = output_builder.store_uint(read_int, 1);
;; ;;   }

;; ;;   slice output_slice = output_builder.end_cell().begin_parse();
;; ;;   return (output_slice, output_int);
;; ;; }

;; ;; ;; job = -1 for set and 0 for get, leave value = 0 when doesn't exist
;; ;; (tuple, int) get_or_set_bit_in_tuple(int i, int job, int int_value, tuple tp, tuple sizes, tuple cum_sizes) method_id {
;; ;;   tuple output_tp = empty_tuple();
;; ;;   int output_int = 0;

;; ;;   int chunk_i = 0;
;; ;;   while(i > cum_sizes.at(chunk_i)){
;; ;;     output_tp~tpush(tp.at(chunk_i));
;; ;;     chunk_i += 1;
;; ;;   }

;; ;;   int j = sizes.at(chunk_i) - (cum_sizes.at(chunk_i) - i);
;; ;;   slice target_chunk = tp.at(chunk_i);
;; ;;   (target_chunk, output_int) = get_or_set_bit_in_slice(j, job, int_value, target_chunk); ;; job from parameters specifies being a get or set
;; ;;   output_tp~tpush(target_chunk);

;; ;;   chunk_i += 1;
;; ;;   while(chunk_i < tp.tuple_length()){
;; ;;     output_tp~tpush(tp.at(chunk_i));
;; ;;     chunk_i += 1;
;; ;;   }

;; ;;   return (output_tp, output_int);
;; ;; }

;; ;; ;; job = -1 for set and 0 for get, leave value = 0 when doesn't exist
;; ;; (tuple, slice) get_or_set_slice_in_tuple(int i, int job, slice slice_value, tuple tp, tuple sizes, tuple cum_sizes) method_id {
;; ;;   builder output_builder = begin_cell();

;; ;;   int total_size = cum_sizes.at(tp.tuple_length() - 1);
;; ;;   int slice_value_size = slice_value.slice_bits();

;; ;;   int j = 0;
;; ;;   while(j < total_size){
;; ;;     if((j >= i) & (j < i + slice_value_size)){
;; ;;       int k = j - i;
;; ;;       int read_int = 0;
;; ;;       if(job == -1){
;; ;;         (_, read_int) = get_or_set_bit_in_slice(k, 0, 0, slice_value); ;; get bit k from slice_value
;; ;;         (tp, _) = get_or_set_bit_in_tuple(j, -1, read_int, tp, sizes, cum_sizes); ;; set read_int to bit j in tp
;; ;;       } else {
;; ;;         (_, read_int) = get_or_set_bit_in_tuple(j, 0, 0, tp, sizes, cum_sizes); ;; get bit j from tp
;; ;;       }
;; ;;       output_builder.store_uint(read_int, 1);
;; ;;     }
;; ;;     j += 1;
;; ;;   }


;; ;;   cell output_cell = output_builder.end_cell();
;; ;;   return (tp, output_cell.begin_parse());
;; ;;   ;;;;;;;;;;;;;;;; apparently the upper one is correct but lower one causes compile error
;; ;;   ;; slice ouput_slice = output_builder
;; ;;   ;;                     .end_cell()
;; ;;   ;;                     .begin_parse();
;; ;;   ;; return (tp, output_slice); ;; of course, you wrote output_slice and ouput_slice idiot :)))
;; ;; }

;; ;; (tuple) linked_list_to_tuple(cell linked_list) method_id {
;; ;;   tuple tp = empty_tuple();
;; ;;   while(-1){
;; ;;     slice cs = linked_list.begin_parse();
;; ;;     slice cs_only_data = cs.preload_bits(cs.slice_bits());
;; ;;     tp~tpush(cs_only_data);

;; ;;     if(cs.slice_refs_empty?()){
;; ;;       return tp;
;; ;;     } else {
;; ;;       linked_list = cs~load_ref();
;; ;;     }
;; ;;   }
;; ;;   return tp; ;; added to disable compiler error (debug)
;; ;; }

;; ;; (cell) tuple_to_linked_list(tuple tp) method_id {
;; ;;   slice last_cs = tp~tpop();
;; ;;   cell linked_list = begin_cell()
;; ;;                    .store_slice(last_cs)
;; ;;                    .end_cell();
;; ;;   while(tp.tuple_length() > 0){
;; ;;     last_cs = tp~tpop();
;; ;;     linked_list = begin_cell()
;; ;;                   .store_slice(last_cs)
;; ;;                   .store_ref(linked_list)
;; ;;                   .end_cell();
;; ;;   }
;; ;;   return linked_list;
;; ;; }


;; ;; useful links:
;; ;; https://docs.ton.org/develop/func/cookbook#how-to-get-only-data-bits-from-a-slice-without-refs
;; ;; https://docs.ton.org/develop/func/statements#until-loop
;; ;; https://docs.ton.org/develop/func/statements#operators
;; ;; https://docs.ton.org/develop/func/cookbook#how-to-define-your-own-modifying-method
;; ;; https://docs.ton.org/develop/smart-contracts/fees#how-to-calculate-fees
;; ;; https://docs.ton.org/develop/howto/fees-low-level#computation-fees