# src/Struct/Item.js

    import { getStructReference } from '../Util/structReferences.js'
    import ID from '../Util/ID/ID.js'
    import { default as RootID, RootFakeUserID } from '../Util/ID/RootID.js'
    import Delete from './Delete.js'
    import { transactionTypeChanged } from '../Transaction.js'
    import GC from './GC.js'

    /**
     * @private
     * Helper utility to split an Item (see {@link Item#_splitAt})
     * - copies all properties from a to b
     * - connects a to b
     * - assigns the correct _id
     * - saves b to os
     */
    export function splitHelper (y, a, b, diff) {
      const aID = a._id
      b._id = new ID(aID.user, aID.clock + diff)
      b._origin = a
      b._left = a
      b._right = a._right
      if (b._right !== null) {
        b._right._left = b
      }
      b._right_origin = a._right_origin
      // do not set a._right_origin, as this will lead to problems when syncing
      a._right = b
      b._parent = a._parent
      b._parentSub = a._parentSub
      b._deleted = a._deleted
      // now search all relevant items to the right and update origin
      // if origin is not it foundOrigins, we don't have to search any longer
      let foundOrigins = new Set()
      foundOrigins.add(a)
      let o = b._right
      while (o !== null && foundOrigins.has(o._origin)) {
        if (o._origin === a) {
          o._origin = b
        }
        foundOrigins.add(o)
        o = o._right
      }
      y.os.put(b)
      if (y._transaction.newTypes.has(a)) {
        y._transaction.newTypes.add(b)
      } else if (y._transaction.deletedStructs.has(a)) {
        y._transaction.deletedStructs.add(b)
      }
    }

    /**
     * Abstract class that represents any content.
     */
    export default class Item {
      constructor () {
        /**
         * The uniqe identifier of this type.
         * @type {ID}
         */
        this._id = null
        /**
         * The item that was originally to the left of this item.
         * @type {Item}
         */
        this._origin = null
        /**
         * The item that is currently to the left of this item.
         * @type {Item}
         */
        this._left = null
        /**
         * The item that is currently to the right of this item.
         * @type {Item}
         */
        this._right = null
        /**
         * The item that was originally to the right of this item.
         * @type {Item}
         */
        this._right_origin = null
        /**
         * The parent type.
         * @type {Y|YType}
         */
        this._parent = null
        /**
         * If the parent refers to this item with some kind of key (e.g. YMap, the
         * key is specified here. The key is then used to refer to the list in which
         * to insert this item. If `parentSub = null` type._start is the list in
         * which to insert to. Otherwise it is `parent._start`.
         * @type {String}
         */
        this._parentSub = null
        /**
         * Whether this item was deleted or not.
         * @type {Boolean}
         */
        this._deleted = false
        /**
         * If this type's effect is reundone this type refers to the type that undid
         * this operation.
         * @type {Item}
         */
        this._redone = null
      }

      /**
       * Creates an Item with the same effect as this Item (without position effect)
       *
       * @private
       */
      _copy () {
        return new this.constructor()
      }

      /**
       * Redoes the effect of this operation.
       *
       * @param {Y} y The Yjs instance.
       *
       * @private
       */
      _redo (y) {
        if (this._redone !== null) {
          return this._redone
        }
        let struct = this._copy()
        let left = this._left
        let right = this
        let parent = this._parent
        // make sure that parent is redone
        if (parent._deleted === true && parent._redone === null) {
          parent._redo(y)
        }
        if (parent._redone !== null) {
          parent = parent._redone
          // find next cloned items
          while (left !== null) {
            if (left._redone !== null && left._redone._parent === parent) {
              left = left._redone
              break
            }
            left = left._left
          }
          while (right !== null) {
            if (right._redone !== null && right._redone._parent === parent) {
              right = right._redone
            }
            right = right._right
          }
        }
        struct._origin = left
        struct._left = left
        struct._right = right
        struct._right_origin = right
        struct._parent = parent
        struct._parentSub = this._parentSub
        struct._integrate(y)
        this._redone = struct
        return struct
      }

      /**
       * Computes the last content address of this Item.
       *
       * @private
       */
      get _lastId () {
        return new ID(this._id.user, this._id.clock + this._length - 1)
      }

      /**
       * Computes the length of this Item.
       *
       * @private
       */
      get _length () {
        return 1
      }

      /**
       * Should return false if this Item is some kind of meta information
       * (e.g. format information).
       *
       * * Whether this Item should be addressable via `yarray.get(i)`
       * * Whether this Item should be counted when computing yarray.length
       *
       * @private
       */
      get _countable () {
        return true
      }

      /**
       * Splits this Item so that another Items can be inserted in-between.
       * This must be overwritten if _length > 1
       * Returns right part after split
       * * diff === 0 => this
       * * diff === length => this._right
       * * otherwise => split _content and return right part of split
       * (see {@link ItemJSON}/{@link ItemString} for implementation)
       *
       * @private
       */
      _splitAt (y, diff) {
        if (diff === 0) {
          return this
        }
        return this._right
      }

      /**
       * Mark this Item as deleted.
       *
       * @param {Y} y The Yjs instance
       * @param {boolean} createDelete Whether to propagate a message that this
       *                               Type was deleted.
       *
       * @private
       */
      _delete (y, createDelete = true) {
        if (!this._deleted) {
          this._deleted = true
          y.ds.mark(this._id, this._length, false)
          let del = new Delete()
          del._targetID = this._id
          del._length = this._length
          if (createDelete) {
            // broadcast and persists Delete
            del._integrate(y, true)
          } else if (y.persistence !== null) {
            // only persist Delete
            y.persistence.saveStruct(y, del)
          }
          transactionTypeChanged(y, this._parent, this._parentSub)
          y._transaction.deletedStructs.add(this)
        }
      }

      _gcChildren (y) {}

      _gc (y) {
        const gc = new GC()
        gc._id = this._id
        gc._length = this._length
        y.os.delete(this._id)
        gc._integrate(y)
      }

      /**
       * This is called right before this Item receives any children.
       * It can be overwritten to apply pending changes before applying remote changes
       *
       * @private
       */
      _beforeChange () {
        // nop
      }

      /**
       * Integrates this Item into the shared structure.
       *
       * This method actually applies the change to the Yjs instance. In case of
       * Item it connects _left and _right to this Item and calls the
       * {@link Item#beforeChange} method.
       *
       * * Integrate the struct so that other types/structs can see it
       * * Add this struct to y.os
       * * Check if this is struct deleted
       *
       * @private
       */
      _integrate (y) {
        y._transaction.newTypes.add(this)
        const parent = this._parent
        const selfID = this._id
        const user = selfID === null ? y.userID : selfID.user
        const userState = y.ss.getState(user)
        if (selfID === null) {
          this._id = y.ss.getNextID(this._length)
        } else if (selfID.user === RootFakeUserID) {
          // nop
        } else if (selfID.clock < userState) {
          // already applied..
          return []
        } else if (selfID.clock === userState) {
          y.ss.setState(selfID.user, userState + this._length)
        } else {
          // missing content from user
          throw new Error('Can not apply yet!')
        }
        if (!parent._deleted && !y._transaction.changedTypes.has(parent) && !y._transaction.newTypes.has(parent)) {
          // this is the first time parent is updated
          // or this types is new
          this._parent._beforeChange()
        }

        /*
        # $this has to find a unique position between origin and the next known character
        # case 1: $origin equals $o.origin: the $creator parameter decides if left or right
        #         let $OL= [o1,o2,o3,o4], whereby $this is to be inserted between o1 and o4
        #         o2,o3 and o4 origin is 1 (the position of o2)
        #         there is the case that $this.creator < o2.creator, but o3.creator < $this.creator
        #         then o2 knows o3. Since on another client $OL could be [o1,o3,o4] the problem is complex
        #         therefore $this would be always to the right of o3
        # case 2: $origin < $o.origin
        #         if current $this insert_position > $o origin: $this ins
        #         else $insert_position will not change
        #         (maybe we encounter case 1 later, then this will be to the right of $o)
        # case 3: $origin > $o.origin
        #         $this insert_position is to the left of $o (forever!)
        */
        // handle conflicts
        let o
        // set o to the first conflicting item
        if (this._left !== null) {
          o = this._left._right
        } else if (this._parentSub !== null) {
          o = this._parent._map.get(this._parentSub) || null
        } else {
          o = this._parent._start
        }
        let conflictingItems = new Set()
        let itemsBeforeOrigin = new Set()
        // Let c in conflictingItems, b in itemsBeforeOrigin
        // ***{origin}bbbb{this}{c,b}{c,b}{o}***
        // Note that conflictingItems is a subset of itemsBeforeOrigin
        while (o !== null && o !== this._right) {
          itemsBeforeOrigin.add(o)
          conflictingItems.add(o)
          if (this._origin === o._origin) {
            // case 1
            if (o._id.user < this._id.user) {
              this._left = o
              conflictingItems.clear()
            }
          } else if (itemsBeforeOrigin.has(o._origin)) {
            // case 2
            if (!conflictingItems.has(o._origin)) {
              this._left = o
              conflictingItems.clear()
            }
          } else {
            break
          }
          // TODO: try to use right_origin instead.
          // Then you could basically omit conflictingItems!
          // Note: you probably can't use right_origin in every case.. only when setting _left
          o = o._right
        }
        // reconnect left/right + update parent map/start if necessary
        const parentSub = this._parentSub
        if (this._left === null) {
          let right
          if (parentSub !== null) {
            const pmap = parent._map
            right = pmap.get(parentSub) || null
            pmap.set(parentSub, this)
          } else {
            right = parent._start
            parent._start = this
          }
          this._right = right
          if (right !== null) {
            right._left = this
          }
        } else {
          const left = this._left
          const right = left._right
          this._right = right
          left._right = this
          if (right !== null) {
            right._left = this
          }
        }
        if (parent._deleted) {
          this._delete(y, false)
        }
        y.os.put(this)
        transactionTypeChanged(y, parent, parentSub)
        if (this._id.user !== RootFakeUserID) {
          if (y.connector !== null && (y.connector._forwardAppliedStructs || this._id.user === y.userID)) {
            y.connector.broadcastStruct(this)
          }
          if (y.persistence !== null) {
            y.persistence.saveStruct(y, this)
          }
        }
      }

      /**
       * Transform the properties of this type to binary and write it to an
       * BinaryEncoder.
       *
       * This is called when this Item is sent to a remote peer.
       *
       * @param {BinaryEncoder} encoder The encoder to write data to.
       *
       * @private
       */
      _toBinary (encoder) {
        encoder.writeUint8(getStructReference(this.constructor))
        let info = 0
        if (this._origin !== null) {
          info += 0b1 // origin is defined
        }
        // TODO: remove
        /* no longer send _left
        if (this._left !== this._origin) {
          info += 0b10 // do not copy origin to left
        }
        */
        if (this._right_origin !== null) {
          info += 0b100
        }
        if (this._parentSub !== null) {
          info += 0b1000
        }
        encoder.writeUint8(info)
        encoder.writeID(this._id)
        if (info & 0b1) {
          encoder.writeID(this._origin._lastId)
        }
        // TODO: remove
        /* see above
        if (info & 0b10) {
          encoder.writeID(this._left._lastId)
        }
        */
        if (info & 0b100) {
          encoder.writeID(this._right_origin._id)
        }
        if ((info & 0b101) === 0) {
          // neither origin nor right is defined
          encoder.writeID(this._parent._id)
        }
        if (info & 0b1000) {
          encoder.writeVarString(JSON.stringify(this._parentSub))
        }
      }

      /**
       * Read the next Item in a Decoder and fill this Item with the read data.
       *
       * This is called when data is received from a remote peer.
       *
       * @param {Y} y The Yjs instance that this Item belongs to.
       * @param {BinaryDecoder} decoder The decoder object to read data from.
       *
       * @private
       */
      _fromBinary (y, decoder) {
        let missing = []
        const info = decoder.readUint8()
        const id = decoder.readID()
        this._id = id
        // read origin
        if (info & 0b1) {
          // origin != null
          const originID = decoder.readID()
          // we have to query for left again because it might have been split/merged..
          const origin = y.os.getItemCleanEnd(originID)
          if (origin === null) {
            missing.push(originID)
          } else {
            this._origin = origin
            this._left = this._origin
          }
        }
        // read right
        if (info & 0b100) {
          // right != null
          const rightID = decoder.readID()
          // we have to query for right again because it might have been split/merged..
          const right = y.os.getItemCleanStart(rightID)
          if (right === null) {
            missing.push(rightID)
          } else {
            this._right = right
            this._right_origin = right
          }
        }
        // read parent
        if ((info & 0b101) === 0) {
          // neither origin nor right is defined
          const parentID = decoder.readID()
          // parent does not change, so we don't have to search for it again
          if (this._parent === null) {
            let parent
            if (parentID.constructor === RootID) {
              parent = y.os.get(parentID)
            } else {
              parent = y.os.getItem(parentID)
            }
            if (parent === null) {
              missing.push(parentID)
            } else {
              this._parent = parent
            }
          }
        } else if (this._parent === null) {
          if (this._origin !== null) {
            if (this._origin.constructor === GC) {
              // if origin is a gc, set parent also gc'd
              this._parent = this._origin
            } else {
              this._parent = this._origin._parent
            }
          } else if (this._right_origin !== null) {
            // if origin is a gc, set parent also gc'd
            if (this._right_origin.constructor === GC) {
              this._parent = this._right_origin
            } else {
              this._parent = this._right_origin._parent
            }
          }
        }
        if (info & 0b1000) {
          // TODO: maybe put this in read parent condition (you can also read parentsub from left/right)
          this._parentSub = JSON.parse(decoder.readVarString())
        }
        if (y.ss.getState(id.user) < id.clock) {
          missing.push(new ID(id.user, id.clock - 1))
        }
        return missing
      }
    }