text:
# Composite type that represents a NDIMS-dimensional tree.
#
# Implements everything required for AbstractContainer.
#
# Note: The way the data structures are set up and the way most algorithms
# work, it is *always* assumed that
#   a) we have a balanced tree (= at most one level difference between
#                                 neighboring cells, or 2:1 rule)
#   b) we may not have all children (= some children may not exist)
#   c) the tree is stored depth-first
#
# However, the way the refinement/coarsening algorithms are currently
# implemented, we only have fully refined cells. That is, a cell either has 2^NDIMS children or
# no children at all (= leaf cell). This restriction is also assumed at
# multiple positions in the refinement/coarsening algorithms.
#
# An exception to the 2:1 rule exists for the low-level `refine_unbalanced!`
# function, which is required for implementing level-wise refinement in a sane
# way. Also, depth-first ordering *might* not by guaranteed during
# refinement/coarsening operations.
mutable struct Tree{NDIMS} <: AbstractContainer
  parent_ids::Vector{Int}
  child_ids::Matrix{Int}
  neighbor_ids::Matrix{Int}
  levels::Vector{Int}
  coordinates::Matrix{Float64}
  original_cell_ids::Vector{Int}

  capacity::Int
  length::Int
  dummy::Int

  center_level_0::MVector{NDIMS, Float64}
  length_level_0::Float64
  periodicity::NTuple{NDIMS, Bool}

  function Tree{NDIMS}(capacity::Integer) where NDIMS
    # Verify that NDIMS is an integer
    @assert NDIMS isa Integer

    # Create instance
    t = new()

    # Initialize fields with defaults
    # Note: length as capacity + 1 is to use `capacity + 1` as temporary storage for swap operations
    t.parent_ids = fill(typemin(Int), capacity + 1)
    t.child_ids = fill(typemin(Int), 2^NDIMS, capacity + 1)
    t.neighbor_ids = fill(typemin(Int), 2*NDIMS, capacity + 1)
    t.levels = fill(typemin(Int), capacity + 1)
    t.coordinates = fill(NaN, NDIMS, capacity + 1)
    t.original_cell_ids = fill(typemin(Int), capacity + 1)

    t.capacity = capacity
    t.length = 0
    t.dummy = capacity + 1

    t.center_level_0 = @MVector fill(NaN, NDIMS)
    t.length_level_0 = NaN

    return t
  end
end

# Constructor for passing the dimension as an argument
Tree(::Val{NDIMS}, args...) where NDIMS = Tree{NDIMS}(args...)

# Create and initialize tree
function Tree{NDIMS}(capacity::Int, center::AbstractArray{Float64},
                 length::Real, periodicity=true) where NDIMS
  # Create instance
  t = Tree{NDIMS}(capacity)

  # Initialize root cell
  init!(t, center, length, periodicity)

  return t
end

# Constructor accepting a single number as center (as opposed to an array) for 1D
Tree{1}(cap::Int, center::Real, len::Real, periodicity=true) = Tree{1}(cap, [convert(Float64, center)], len, periodicity)

# Clear tree with deleting data structures, store center and length, and create root cell
function init!(t::Tree, center::AbstractArray{Float64}, length::Real, periodicity=true)
  clear!(t)

  # Set domain information
  t.center_level_0 = center
  t.length_level_0 = length

  # Create root cell
  t.length += 1
  t.parent_ids[1] = 0
  t.child_ids[:, 1] .= 0
  t.levels[1] = 0
  t.coordinates[:, 1] .= t.center_level_0
  t.original_cell_ids[1] = 0

  # Set neighbor ids: for each periodic direction, the level-0 cell is its own neighbor
  if all(periodicity)
    # Also catches case where periodicity = true
    t.neighbor_ids[:, 1] .= 1
    t.periodicity = ntuple(x->true, ndims(t))
  elseif !any(periodicity)
    # Also catches case where periodicity = false
    t.neighbor_ids[:, 1] .= 0
    t.periodicity = ntuple(x->false, ndims(t))
  else
    # Default case if periodicity is an iterable
    for dimension in 1:ndims(t)
      if periodicity[dimension]
        t.neighbor_ids[2 * dimension - 1, 1] = 1
        t.neighbor_ids[2 * dimension - 0, 1] = 1
      else
        t.neighbor_ids[2 * dimension - 1, 1] = 0
        t.neighbor_ids[2 * dimension - 0, 1] = 0
      end
    end

    t.periodicity = Tuple(periodicity)
  end
end

# Convenience output for debugging
function Base.show(io::IO, t::Tree{NDIMS}) where NDIMS
  l = t.length
  println(io, '*'^20)
  println(io, "t.parent_ids[1:l] = $(t.parent_ids[1:l])")
  println(io, "transpose(t.child_ids[:, 1:l]) = $(transpose(t.child_ids[:, 1:l]))")
  println(io, "transpose(t.neighbor_ids[:, 1:l]) = $(transpose(t.neighbor_ids[:, 1:l]))")
  println(io, "t.levels[1:l] = $(t.levels[1:l])")
  println(io, "transpose(t.coordinates[:, 1:l]) = $(transpose(t.coordinates[:, 1:l]))")
  println(io, "t.original_cell_ids[1:l] = $(t.original_cell_ids[1:l])")
  println(io, "t.capacity = $(t.capacity)")
  println(io, "t.length = $(t.length)")
  println(io, "t.dummy = $(t.dummy)")
  println(io, "t.center_level_0 = $(t.center_level_0)")
  println(io, "t.length_level_0 = $(t.length_level_0)")
  println(io, '*'^20)
end

# Type traits to obtain dimension
@inline Base.ndims(t::Type{Tree{NDIMS}}) where NDIMS = NDIMS
@inline Base.ndims(t::Tree) = ndims(typeof(t))

# Auxiliary methods to allow semantic queries on the tree
# Check whether cell has parent cell
has_parent(t::Tree, cell_id::Int) = t.parent_ids[cell_id] > 0

# Count number of children for a given cell
n_children(t::Tree, cell_id::Int) = count(x -> (x > 0), @view t.child_ids[:, cell_id])

# Check whether cell has any child cell
has_children(t::Tree, cell_id::Int) = n_children(t, cell_id) > 0

# Check whether cell is leaf cell
is_leaf(t::Tree, cell_id::Int) = !has_children(t, cell_id)

# Check whether cell has specific child cell
has_child(t::Tree, cell_id::Int, child::Int) = t.child_ids[child, cell_id] > 0

# Check if cell has a neighbor at the same refinement level in the given direction
has_neighbor(t::Tree, cell_id::Int, direction::Int) = t.neighbor_ids[direction, cell_id] > 0

# Check if cell has a coarse neighbor, i.e., with one refinement level lower
function has_coarse_neighbor(t::Tree, cell_id::Int, direction::Int)
  return has_parent(t, cell_id) && has_neighbor(t, t.parent_ids[cell_id], direction)
end

# Check if cell has any neighbor (same-level or lower-level)
function has_any_neighbor(t::Tree, cell_id::Int, direction::Int)
  return has_neighbor(t, cell_id, direction) || has_coarse_neighbor(t, cell_id, direction)
end

# Return cell length for a given level
length_at_level(t::Tree, level::Int) = t.length_level_0 / 2^level

# Return cell length for a given cell
length_at_cell(t::Tree, cell_id::Int) = length_at_level(t, t.levels[cell_id])

# Return minimum level of any leaf cell
minimum_level(t::Tree) = minimum(t.levels[leaf_cells(t)])

# Return maximum level of any leaf cell
maximum_level(t::Tree) = maximum(t.levels[leaf_cells(t)])

# Check if tree is periodic
isperiodic(t::Tree) = all(t.periodicity)
isperiodic(t::Tree, dimension) = t.periodicity[dimension]

# Auxiliary methods for often-required calculations
# Number of potential child cells
n_children_per_cell(::Tree{NDIMS}) where NDIMS = 2^NDIMS
n_children_per_cell(dims::Integer) = 2^dims

# Number of directions
#
# Directions are indicated by numbers from 1 to 2*ndims:
# 1 -> -x
# 2 -> +x
# 3 -> -y
# 4 -> +y
# 5 -> -z
# 6 -> +z
n_directions(::Tree{NDIMS}) where NDIMS = 2 * NDIMS

# For a given direction, return its opposite direction
#
# dir -> opp
#  1  ->  2
#  2  ->  1
#  3  ->  4
#  4  ->  3
#  5  ->  6
#  6  ->  5
opposite_direction(direction::Int) = direction + 1 - 2 * ((direction + 1) % 2)

# For a given child position (from 1 to 8) and dimension (from 1 to 3),
# calculate a child cell's position relative to its parent cell.
#
# Essentially calculates the following
#         dim=1 dim=2 dim=3
# child     x     y     z
#   1       -     -     -
#   2       +     -     -
#   3       -     +     -
#   4       +     +     -
#   5       -     -     +
#   6       +     -     +
#   7       -     +     +
#   8       +     +     +
child_sign(child::Int, dim::Int) = 1 - 2 * (div(child + 2^(dim - 1) - 1, 2^(dim-1)) % 2)

# For each child position (1 to 8) and a given direction (from 1 to 6), return
# neighboring child position.
adjacent_child(child::Int, direction::Int) = [2 2 3 3 5 5;
                                              1 1 4 4 6 6;
                                              4 4 1 1 7 7;
                                              3 3 2 2 8 8;
                                              6 6 7 7 1 1;
                                              5 5 8 8 2 2;
                                              8 8 5 5 3 3;
                                              7 7 6 6 4 4][child, direction]

# For each child position (1 to 8) and a given direction (from 1 to 6), return
# if neighbor is a sibling
function has_sibling(child::Int, direction::Int)
  return (child_sign(child, div(direction + 1, 2)) * (-1)^(direction - 1)) > 0
end

# Obtain leaf cells that fulfill a given criterion.
#
# The function `f` is passed the cell id of each leaf cell
# as an argument.
function filter_leaf_cells(f, t::Tree)
  filtered = Vector{Int}(undef, length(t))
  count = 0
  for cell_id in 1:length(t)
    if is_leaf(t, cell_id) && f(cell_id)
      count += 1
      filtered[count] = cell_id
    end
  end

  return filtered[1:count]
end

# Return an array with the ids of all leaf cells
leaf_cells(t::Tree) = filter_leaf_cells((cell_id)->true, t)

# Count the number of leaf cells.
count_leaf_cells(t::Tree) = length(leaf_cells(t))

# Store cell id in each cell to use for post-AMR analysis
function reset_original_cell_ids!(t::Tree)
  t.original_cell_ids[1:length(t)] .= 1:length(t)
end

# Refine entire tree by one level
refine!(t::Tree) = refine!(t, leaf_cells(t))

# Refine given cells and rebalance tree.
#
# Note 1: Rebalancing is iterative, i.e., neighboring cells are refined if
#         otherwise the 2:1 rule would be violated, which can cause more
#         refinements.
# Note 2: Rebalancing currently only considers *Cartesian* neighbors, not diagonal neighbors!
function refine!(t::Tree, cell_ids)
  # Reset original cell ids such that each cell knows its current id
  reset_original_cell_ids!(t)

  # Refine all requested cells
  refined = refine_unbalanced!(t, cell_ids)
  refinement_count = length(refined)

  # Iteratively rebalance the tree until it does not change anymore
  while length(refined) > 0
    refined = rebalance!(t, refined)
    refinement_count += length(refined)
  end

  # Determine list of *original* cell ids that were refined
  # Note: original_cell_ids contains the cell_id *before* refinement. At
  # refinement, the refined cell's original_cell_ids value has its sign flipped
  # to easily find it now.
  @views refined_original_cells = (
      -t.original_cell_ids[1:length(t)][t.original_cell_ids[1:length(t)] .< 0])

  # Check if count of refinement cells matches information in original_cell_ids
  @assert refinement_count == length(refined_original_cells) (
      "Mismatch in number of refined cells")

  return refined_original_cells
end

# Refine all leaf cells with coordinates in a given rectangular box
function refine_box!(t::Tree{NDIMS}, coordinates_min::AbstractArray{Float64},
                     coordinates_max::AbstractArray{Float64}) where NDIMS
  for dim in 1:NDIMS
    @assert coordinates_min[dim] < coordinates_max[dim] "Minimum coordinates are not minimum."
  end

  # Find all leaf cells within box
  cells = filter_leaf_cells(t) do cell_id
    return (all(coordinates_min .< t.coordinates[:, cell_id]) &&
            all(coordinates_max .> t.coordinates[:, cell_id]))
  end

  # Refine cells
  refine!(t, cells)
end

# Convenience method for 1D
function refine_box!(t::Tree{1}, coordinates_min::Real, coordinates_max::Real)
  return refine_box!(t, [convert(Float64, coordinates_min)], [convert(Float64, coordinates_max)])
end

# For the given cell ids, check if neighbors need to be refined to restore a rebalanced tree.
#
# Note 1: Rebalancing currently only considers *Cartesian* neighbors, not diagonal neighbors!
# Note 2: The current algorithm assumes that a previous refinement step has
#         created level differences of at most 2. That is, before the previous
#         refinement step, the tree was balanced.
function rebalance!(t::Tree, refined_cell_ids)
  # Create buffer for newly refined cells
  to_refine = zeros(Int, n_directions(t) * length(refined_cell_ids))
  count = 0

  # Iterate over cell ids that have previously been refined
  for cell_id in refined_cell_ids
    # Go over all potential neighbors of child cell
    for direction in 1:n_directions(t)
      # Continue if refined cell has a neighbor in that direction
      if has_neighbor(t, cell_id, direction)
        continue
      end

      # Continue if refined cell has no coarse neighbor, since that would
      # mean it there is no neighbor in that direction at all (domain
      # boundary)
      if !has_coarse_neighbor(t, cell_id, direction)
        continue
      end

      # Otherwise, the coarse neighbor exists and is not refined, thus it must
      # be marked for refinement
      coarse_neighbor_id = t.neighbor_ids[direction, t.parent_ids[cell_id]]
      count += 1
      to_refine[count] = coarse_neighbor_id
    end
  end

  # Finally, refine all marked cells...
  refined = refine_unbalanced!(t, unique(to_refine[1:count]))

  # ...and return list of refined cells
  return refined
end

# Refine given cells without rebalancing tree.
#
# Note: After a call to this method the tree may be unbalanced!
function refine_unbalanced!(t::Tree, cell_ids)
  # Store actual ids refined cells (shifted due to previous insertions)
  refined = zeros(Int, length(cell_ids))

  # Loop over all cells that are to be refined
  for (count, original_cell_id) in enumerate(sort(unique(cell_ids)))
    # Determine actual cell id, taking into account previously inserted cells
    n_children = n_children_per_cell(t)
    cell_id = original_cell_id + (count - 1) * n_children
    refined[count] = cell_id

    @assert !has_children(t, cell_id) "Non-leaf cell $cell_id cannot be refined"

    # Insert new cells directly behind parent (depth-first)
    insert!(t, cell_id + 1, n_children)

    # Flip sign of refined cell such that we can easily find it later
    t.original_cell_ids[cell_id] = -t.original_cell_ids[cell_id]

    # Initialize child cells
    for child in 1:n_children
      # Set child information based on parent
      child_id = cell_id + child
      t.parent_ids[child_id] = cell_id
      t.child_ids[child, cell_id] = child_id
      t.neighbor_ids[:, child_id] .= 0
      t.child_ids[:, child_id] .= 0
      t.levels[child_id] = t.levels[cell_id] + 1
      t.coordinates[:, child_id] .= child_coordinates(
          t, t.coordinates[:, cell_id], length_at_cell(t, cell_id), child)
      t.original_cell_ids[child_id] = 0

      # For determining neighbors, use neighbor connections of parent cell
      for direction in 1:n_directions(t)
        # If neighbor is a sibling, establish one-sided connectivity
        # Note: two-sided is not necessary, as each sibling will do this
        if has_sibling(child, direction)
          adjacent = adjacent_child(child, direction)
          neighbor_id = cell_id + adjacent

          t.neighbor_ids[direction, child_id] = neighbor_id
          continue
        end

        # Skip if original cell does have no neighbor in direction
        if !has_neighbor(t, cell_id, direction)
          continue
        end

        # Otherwise, check if neighbor has children - if not, skip again
        neighbor_id = t.neighbor_ids[direction, cell_id]
        if !has_children(t, neighbor_id)
          continue
        end

        # Check if neighbor has corresponding child and if yes, establish connectivity
        adjacent = adjacent_child(child, direction)
        if has_child(t, neighbor_id, adjacent)
          neighbor_child_id = t.child_ids[adjacent, neighbor_id]
          opposite = opposite_direction(direction)

          t.neighbor_ids[direction, child_id] = neighbor_child_id
          t.neighbor_ids[opposite, neighbor_child_id] = child_id
        end
      end
    end
  end

  return refined
end

# Wrap single-cell refinements such that `sort(...)` does not complain
refine_unbalanced!(t::Tree, cell_id::Int) = refine_unbalanced!(t, [cell_id])

# Coarsen entire tree by one level
function coarsen!(t::Tree)
  # Special case: if there is only one cell (root), there is nothing to do
  if length(t) == 1
    return Int[]
  end

  # Get list of unique parent ids for all leaf cells
  parent_ids = unique(t.parent_ids[leaf_cells(t)])
  coarsen!(t, parent_ids)
end

# Coarsen given *parent* cells (= these cells must have children who are all
# leaf cells) while retaining a balanced tree.
#
# A cell to be coarsened might cause an unbalanced tree if the neighboring cell
# was already refined. Since it is generally not desired that cells are
# coarsened without specifically asking for it, these cells will then *not* be
# coarsened.
function coarsen!(t::Tree, cell_ids::AbstractArray{Int})
  # Return early if array is empty
  if length(cell_ids) == 0
    return Int[]
  end

  # Reset original cell ids such that each cell knows its current id
  reset_original_cell_ids!(t)

  # To maximize the number of cells that may be coarsened, start with the cells at the highest level
  sorted_by_level = sort(cell_ids, by = i -> t.levels[i])

  # Keep track of number of cells that were actually coarsened
  n_coarsened = 0

  # Local function to adjust cell ids after some cells have been removed
  function adjust_cell_ids!(cell_ids, coarsened_cell_id, count)
    for (id, cell_id) in enumerate(cell_ids)
      if cell_id > coarsened_cell_id
        cell_ids[id] = cell_id - count
      end
    end
  end

  # Iterate backwards over cells to coarsen
  while true
    # Retrieve next cell or quit
    if length(sorted_by_level) > 0
      coarse_cell_id = pop!(sorted_by_level)
    else
      break
    end

    # Ensure that cell has children (violation is an error)
    if !has_children(t, coarse_cell_id)
      error("cell is leaf and cannot be coarsened to: $coarse_cell_id")
    end

    # Ensure that all child cells are leaf cells (violation is an error)
    for child in 1:n_children_per_cell(t)
      if has_child(t, coarse_cell_id, child)
        if !is_leaf(t, t.child_ids[child, coarse_cell_id])
          error("cell $coarse_cell_id has child cell at position $child that is not a leaf cell")
        end
      end
    end

    # Check if coarse cell has refined neighbors that would prevent coarsening
    skip = false
    # Iterate over all children (which are to be removed)
    for child in 1:n_children_per_cell(t)
      # Continue if child does not exist
      if !has_child(t, coarse_cell_id, child)
        continue
      end
      child_id = t.child_ids[child, coarse_cell_id]

      # Go over all neighbors of child cell. If it has a neighbor that is *not*
      # a sibling and that is not a leaf cell, we cannot coarsen its parent
      # without creating an unbalanced tree.
      for direction in 1:n_directions(t)
        # Continue if neighbor would be a sibling
        if has_sibling(child, direction)
          continue
        end

        # Continue if child cell has no neighbor in that direction
        if !has_neighbor(t, child_id, direction)
          continue
        end
        neighbor_id = t.neighbor_ids[direction, child_id]

        if !has_children(t, neighbor_id)
          continue
        end

        # If neighbor is not a sibling, is existing, and has children, do not coarsen
        skip = true
        break
      end
    end
    # Skip if a neighboring cell prevents coarsening
    if skip
      continue
    end

    # Flip sign of cell to be coarsened to such that we can easily find it
    t.original_cell_ids[coarse_cell_id] = -t.original_cell_ids[coarse_cell_id]

    # If a coarse cell has children that are all leaf cells, they must follow
    # immediately due to depth-first ordering of the tree
    count = n_children(t, coarse_cell_id)
    @assert count == n_children_per_cell(t) "cell $coarse_cell_id does not have all child cells"
    remove_shift!(t, coarse_cell_id + 1, coarse_cell_id + count)

    # Take into account shifts in tree that alters cell ids
    adjust_cell_ids!(sorted_by_level, coarse_cell_id, count)

    # Keep track of number of coarsened cells
    n_coarsened += 1
  end

  # Determine list of *original* cell ids that were coarsened to
  # Note: original_cell_ids contains the cell_id *before* coarsening. At
  # coarsening, the coarsened parent cell's original_cell_ids value has its sign flipped
  # to easily find it now.
  @views coarsened_original_cells = (
      -t.original_cell_ids[1:length(t)][t.original_cell_ids[1:length(t)] .< 0])

  # Check if count of coarsened cells matches information in original_cell_ids
  @assert n_coarsened == length(coarsened_original_cells) (
      "Mismatch in number of coarsened cells")

  return coarsened_original_cells
end

# Wrap single-cell coarsening such that `sort(...)` does not complain
coarsen!(t::Tree, cell_id::Int) = coarsen!(t::Tree, [cell_id])

# Coarsen all viable parent cells with coordinates in a given rectangular box
function coarsen_box!(t::Tree{NDIMS}, coordinates_min::AbstractArray{Float64},
                     coordinates_max::AbstractArray{Float64}) where NDIMS
  for dim in 1:NDIMS
    @assert coordinates_min[dim] < coordinates_max[dim] "Minimum coordinates are not minimum."
  end

  # Find all leaf cells within box
  leaves = filter_leaf_cells(t) do cell_id
    return (all(coordinates_min .< t.coordinates[:, cell_id]) &&
            all(coordinates_max .> t.coordinates[:, cell_id]))
  end

  # Get list of unique parent ids for all leaf cells
  parent_ids = unique(t.parent_ids[leaves])

  # Filter parent ids to be within box
  parents = filter(parent_ids) do cell_id
    return (all(coordinates_min .< t.coordinates[:, cell_id]) &&
            all(coordinates_max .> t.coordinates[:, cell_id]))
  end

  # Coarsen cells
  coarsen!(t, parents)
end

# Convenience method for 1D
function coarsen_box!(t::Tree{1}, coordinates_min::Real, coordinates_max::Real)
  return coarsen_box!(t, [convert(Float64, coordinates_min)], [convert(Float64, coordinates_max)])
end

# Return coordinates of a child cell based on its relative position to the parent.
function child_coordinates(::Tree{NDIMS}, parent_coordinates, parent_length::Number, child::Int) where NDIMS
  # Calculate length of child cells and set up data structure
  child_length = parent_length / 2
  coordinates = MVector{NDIMS, Float64}(undef)

  # For each dimension, calculate coordinate as parent coordinate + relative position x length/2
  for d in 1:NDIMS
    coordinates[d] = parent_coordinates[d] + child_sign(child, d) * child_length / 2
  end

  return coordinates
end

# Reset range of cells to values that are prone to cause errors as soon as they are used.
#
# Rationale: If an invalid cell is accidentally used, we want to know it as soon as possible.
function invalidate!(t::Tree, first::Int, last::Int)
  @assert first > 0
  @assert last <= t.capacity + 1

  # Integer values are set to smallest negative value, floating point values to NaN
  t.parent_ids[first:last] .= typemin(Int)
  t.child_ids[:, first:last] .= typemin(Int)
  t.neighbor_ids[:, first:last] .= typemin(Int)
  t.levels[first:last] .= typemin(Int)
  t.coordinates[:, first:last] .= NaN
  t.original_cell_ids[first:last] .= typemin(Int)

  return nothing
end
invalidate!(t::Tree, id::Int) = invalidate!(t, id, id)
invalidate!(t::Tree) = invalidate!(t, 1, length(t))

# Delete connectivity with parents/children/neighbors before cells are erased
function delete_connectivity!(t::Tree, first::Int, last::Int)
  @assert first > 0
  @assert first <= last
  @assert last <= t.capacity + 1

  # Iterate over all cells
  for cell_id in first:last
    # Delete connectivity from parent cell
    if has_parent(t, cell_id)
      parent_id = t.parent_ids[cell_id]
      for child in 1:n_children_per_cell(t)
        if t.child_ids[child, parent_id] == cell_id
          t.child_ids[child, parent_id] = 0
          break
        end
      end
    end

    # Delete connectivity from child cells
    for child in 1:n_children_per_cell(t)
      if has_child(t, cell_id, child)
        t.parent_ids[t._child_ids[child, cell_id]] = 0
      end
    end

    # Delete connectivity from neighboring cells
    for direction in 1:n_directions(t)
      if has_neighbor(t, cell_id, direction)
        t.neighbor_ids[opposite_direction(direction), t.neighbor_ids[direction, cell_id]] = 0
      end
    end
  end
end

# Move connectivity with parents/children/neighbors after cells have been moved
function move_connectivity!(t::Tree, first::Int, last::Int, destination::Int)
  @assert first > 0
  @assert first <= last
  @assert last <= t.capacity + 1
  @assert destination > 0
  @assert destination <= t.capacity + 1

  # Strategy
  # 1) Loop over moved cells (at target location)
  # 2) Check if parent/children/neighbors connections are to a cell that was moved
  #    a) if cell was moved: apply offset to current cell
  #    b) if cell was not moved: go to connected cell and update connectivity there

  offset = destination - first
  has_moved(n) = (first <= n <= last)

  for source in first:last
    target = source + offset

    # Update parent
    if has_parent(t, target)
      # Get parent cell
      parent_id = t.parent_ids[target]
      if has_moved(parent_id)
        # If parent itself was moved, just update parent id accordingly
        t.parent_ids[target] += offset
      else
        # If parent was not moved, update its corresponding child id
        for child in 1:n_children_per_cell(t)
          if t.child_ids[child, parent_id] == source
            t.child_ids[child, parent_id] = target
          end
        end
      end
    end

    # Update children
    for child in 1:n_children_per_cell(t)
      if has_child(t, target, child)
        # Get child cell
        child_id = t.child_ids[child, target]
        if has_moved(child_id)
          # If child itself was moved, just update child id accordingly
          t.child_ids[child, target] += offset
        else
          # If child was not moved, update its parent id
          t.parent_ids[child_id] = target
        end
      end
    end

    # Update neighbors
    for direction in 1:n_directions(t)
      if has_neighbor(t, target, direction)
        # Get neighbor cell
        neighbor_id = t.neighbor_ids[direction, target]
        if has_moved(neighbor_id)
          # If neighbor itself was moved, just update neighbor id accordingly
          t.neighbor_ids[direction, target] += offset
        else
          # If neighbor was not moved, update its opposing neighbor id
          t.neighbor_ids[opposite_direction(direction), neighbor_id] = target
        end
      end
    end
  end
end

# Raw copy operation for ranges of cells.
#
# This method is used by the higher-level copy operations for AbstractContainer
function raw_copy!(target::Tree, source::Tree, first::Int, last::Int, destination::Int)
  copy_data!(target.parent_ids, source.parent_ids, first, last, destination)
  copy_data!(target.child_ids, source.child_ids, first, last, destination,
             n_children_per_cell(target))
  copy_data!(target.neighbor_ids, source.neighbor_ids, first, last,
             destination, n_directions(target))
  copy_data!(target.levels, source.levels, first, last, destination)
  copy_data!(target.coordinates, source.coordinates, first, last, destination, ndims(target))
  copy_data!(target.original_cell_ids, source.original_cell_ids, first, last, destination)
end
function raw_copy!(c::AbstractContainer, first::Int, last::Int, destination::Int)
  raw_copy!(c, c, first, last, destination)
end
function raw_copy!(target::AbstractContainer, source::AbstractContainer, from::Int, destination::Int)
  raw_copy!(target, source, from, from, destination)
end
function raw_copy!(c::AbstractContainer, from::Int, destination::Int)
  raw_copy!(c, c, from, from, destination)
end

# Reset data structures by recreating all internal storage containers and invalidating all elements
function reset_data_structures!(t::Tree{NDIMS}) where NDIMS
  t.parent_ids = Vector{Int}(undef, t.capacity + 1)
  t.child_ids = Matrix{Int}(undef, 2^NDIMS, t.capacity + 1)
  t.neighbor_ids = Matrix{Int}(undef, 2*NDIMS, t.capacity + 1)
  t.levels = Vector{Int}(undef, t.capacity + 1)
  t.coordinates = Matrix{Float64}(undef, NDIMS, t.capacity + 1)
  t.original_cell_ids = Vector{Int}(undef, t.capacity + 1)

  invalidate!(t, 1, capacity(t) + 1)
end


text:
export upstrip

"""
# Function call

`upstrip(u, U)`

# Description

Returns the number of any physical quantity `u`. If the optional unit `U` is not
specified the quantity is converted to its coherent (preferred) unit before
determining the number.

# Variables

`u` Variable to be processed

`U` Optional target unit; if not provided, the quantity is converted to its coherent (preferred) unit before
determining the number.

# Examples
```julia
julia> I1 = 1.0mA
julia> upstrip(I1)
0.001
julia> usprint(I1, mA)
1.0
"""
function upstrip(u, U=unit(upreferred(u)))
    q=uconvert(U, u)
    return ustrip(q)
end

ext: jl


text:
using ReservoirComputing

train_data = ones(Int, 2, 10)
res_size = 10
generations = 5
permutations = 2

reca = RECA_TwoDim(train_data, res_size, generations, permutations)

W_out = ESNtrain(reca, 0.001, train_data = ones(Float64, 2, 10))
output = RECATD_predict_discrete(reca, 10, W_out)

@test isequal(size(output), size(ones(Int, 2, 10)))

output = RECATDdirect_predict_discrete(reca, W_out, ones(Int, 2, 10))
@test isequal(size(output), size(ones(Int, 2, 10)))


text:
module Order
using JSON3, HTTP, Dates

export extensions, clientExtensions, takeProfit, stopLoss, trailingStopLoss,
    marketOrder, nonMarketOrder, limitOrder, stopOrder, marketIfTouchedOrder,
    relatedOrder, getOrders, getPendingOrders, getOrder, replaceOrder, cancelOrder,
    orderClientExtensions

"""
clientExtension request structs

# Fields
- 'id::String': id of the extension
- 'tag::String': tag of the extension
- 'comment::String': comment of the extension
"""
struct extensions
    id::String
    tag::String
    comment::String
end

# For JSON parsing
struct clientExtensions
    clientExtensions::extensions
end

# Declaring JSON3 struct types
JSON3.StructType(::Type{clientExtensions}) = JSON3.Struct()
JSON3.StructType(::Type{extensions}) = JSON3.Struct()

# ------------------------------------------------------------------------------------
# /accounts/{accountID}/orders POST Endpoint
# ------------------------------------------------------------------------------------

"""
Take profit order struct

# Fields
- 'price::Real': The price to execute at
- 'timeInForce::String': The type of time in force
- 'gtdTime::String': The gtd
"""
mutable struct takeProfit
    price::Real
    timeInForce::String
    gtdTime::String
    # clientExtensions::extensions -> TODO

    takeProfit() = new()
end

"""
Stop loss order struct

# Fields
- 'price::Real': The price to execute at
- 'distance::Real': The price distance
- 'timeInForce::String': The type of time in force
- 'gtdTime::String': The gtd
"""
mutable struct stopLoss
    price::Real
    distance::Real
    timeInForce::String
    gtdTime::String
    # clientExtensions::extensions -> TODO

    stopLoss() = new()
end

"""
Trailing stop loss order struct

# Fields
- 'distance::Real': The price distance
- 'timeInForce::String': The type of time in force
- 'gtdTime::String': The gtd
"""
mutable struct trailingStopLoss
    distance::Real
    timeInForce::String
    gtdTime::String
    # clientExtensions::extensions -> TODO

    trailingStopLoss() = new()
end

"""
Detailed OrderRequest struct from Oanda

# Fields
- 'clientExtensions::clientExtensions': Client extensions for the order
- 'distance': for orders on fill
- 'gtdTime'
- 'instrument': instrument of the order
- 'positionFill': Type of position fill on the order
- 'price': Price the order is placed at
- 'priceBound'
- 'stopLossOnFill::stopLoss': Stop loss settings for an order
- 'takeProfitOnFill::takeProfit' Take profit settings for an order
- 'timeInForce': Type of time in force
- 'tradeClientExtensions::clientExtensions': Client extensions for the trade
- 'tradeID::String'
- 'trailingStopLossOnFill::trailingStopLoss' Trailing stop loss settings for an order
- 'triggerCondition': Trigger condition of the order
- 'type': Type of order
- 'units': Number of units (negative for a short, positive for a long)
"""
mutable struct orderRequest
    clientExtensions::clientExtensions
    distance # for orders on fill
    gtdTime
    instrument # instrument of the order
    positionFill # Type of position fill on the order
    price # Price the order is placed at
    priceBound
    stopLossOnFill::stopLoss # Stop loss settings for an order
    takeProfitOnFill::takeProfit
    timeInForce # Type of time in force
    tradeClientExtensions::clientExtensions
    tradeID::String
    trailingStopLossOnFill::trailingStopLoss
    triggerCondition # Trigger condition of the order
    type # Type of order
    units # Number of units (negative for a short, positive for a long)

    orderRequest() = new()
end

"For JSON parsing"
struct order2send
    order::orderRequest
end

# Declaring JSON3 struct types

JSON3.StructType(::Type{takeProfit}) = JSON3.Mutable()
JSON3.omitempties(::Type{takeProfit})=(:price,:timeInForce,:gtdTime)

JSON3.StructType(::Type{stopLoss}) = JSON3.Mutable()
JSON3.omitempties(::Type{stopLoss})=(:price,:distance,:timeInForce,:gtdTime)

JSON3.StructType(::Type{trailingStopLoss}) = JSON3.Mutable()
JSON3.omitempties(::Type{trailingStopLoss})=(:price,:timeInForce,:gtdTime)

JSON3.StructType(::Type{orderRequest}) = JSON3.Mutable()
JSON3.omitempties(::Type{orderRequest})=(:price, :units, :distance, :priceBound,:triggerCondition,:gtdTime,
                                         :takeProfitOnFill,:stopLossOnFill,:trailingStopLossOnFill,
                                         :clientExtensions,:tradeID, :tradeClientExtensions)

JSON3.StructType(::Type{order2send}) = JSON3.Struct()

# market order -----------------------------------------------------------------------
"""
    marketOrder(config, instrument, units;[TIF, positionFill, priceBound, TP ,SL ,tSL, clientExt ,tradeExt])

Places a market order

Returns a dictionary

#Arguments
- 'config::config': a valid struct with user configuration data
- 'instrument::String': a valid instrument (e.g. "EUR_USD")
- 'units::String': units to buy (positive value) or sell (negative value)

# Keyword Arguments
- 'TIF::String' : timeinForce value ("GTC","GTD","GFD","FOK","IOC")
- 'positionFill::String' : how positions are modified when the order is filled ("OPEN_ONLY", "REDUCE_FIRST", "REDUCE_ONLY","DEFAULT"). Defaults to "DEFAULT"
- 'priceBound::String': worst price for filling
- 'TP', 'SL', 'tSL' : a NamedTuple with order-on-fill details. Valid values are 'price::Real', 'distance::Real', 'timeInForce::String' and 'gtdTime::String'
- 'clientExt'(not implemented)
- 'tradeExt' (not implemented)

#Examples

   marketOrder(userData,"EUR_JPY",100)
   marketOrder(userData,"EUR_CHF",100,SL=(distance=0.1,),TP=(price=1.12,),tSL=(distance=0.3,)) #Do not forget the comma for single value NamedTuple
"""
function marketOrder(config, instrument::String, units::Real;
                     TIF::String = "FOK", positionFill::String = "DEFAULT", priceBound::Union{Nothing,String}=nothing,
                     TP::NamedTuple=NamedTuple(),SL::NamedTuple=NamedTuple(),tSL::NamedTuple=NamedTuple(),
                     clientExt::NamedTuple=NamedTuple(),tradeExt::NamedTuple=NamedTuple())

    o = orderRequest()

    o.type = "MARKET"
    o.instrument = instrument
    o.units = units
    o.timeInForce = TIF
    o.positionFill = positionFill
    o.priceBound = priceBound

    if !isempty(TP)
        TPdetails = takeProfit()
        haskey(TP, :price) && (TPdetails.price = TP.price)
        haskey(TP, :timeInForce) && (TPdetails.timeInForce = TP.timeInForce)
        haskey(TP, :gtdTime) && (TPdetails.price = Dates.format(TP.gtdTime,"yyyy-mm-ddTHH:MM:SS.sss000000Z"))

        o.takeProfitOnFill = TPdetails
    end

    if !isempty(SL)
        SLdetails = stopLoss()
        haskey(SL, :price) && (SLdetails.price = SL.price)
        haskey(SL, :distance) && (SLdetails.distance = SL.distance)
        haskey(SL, :timeInForce) && (SLdetails.timeInForce = SL.timeInForce)
        haskey(SL, :gtdTime) && (SLdetails.price = Dates.format(SL.gtdTime,"yyyy-mm-ddTHH:MM:SS.sss000000Z"))

        o.stopLossOnFill = SLdetails
    end

    if !isempty(tSL)
        tSLdetails = trailingStopLoss()
        haskey(tSL, :distance) && (tSLdetails.distance = tSL.distance)
        haskey(tSL, :timeInForce) && (tSLdetails.timeInForce = tSL.timeInForce)
        haskey(tSL, :gtdTime) && (tSLdetails.price = Dates.format(tSL.gtdTime,"yyyy-mm-ddTHH:MM:SS.sss000000Z"))

        o.trailingStopLossOnFill = tSLdetails
    end

    # TODO: Client Extensions

    data = order2send(o)

    r = HTTP.post(string("https://",config.hostname,"/v3/accounts/",config.account,"/orders",),
        ["Authorization" => string("Bearer ", config.token), "Content-Type" => "application/json", ],
        JSON3.write(data),)

    return JSON3.read(r.body,Dict{String,Any})
end

# Other type of orders -----------------------------------------------------------------------
"""
 nonMarketOrder(config::config, type::String, instrument, units, price;[TIF, gtdTime, positionFill, trigge, priceBound, TP ,SL ,tSL, clientExt ,tradeExt])

 generic order function for limit, stop and marketIfTouchedOrders

# Arguments
- 'config::config': A valid config object
- 'type::String': The type of order
- 'instrument::String': The instrument to act on
- 'units::Real': The number of units to purchase
- 'price::Real': The price to order at

# Keyword Arguments
- 'TIF::String': timeinForce value ("GTC","GTD","GFD","FOK","IOC")
- 'gtdTime::Union{Nothing,String}': The gtd
- 'positionFill::String': how positions are modified when the order is filled ("OPEN_ONLY", "REDUCE_FIRST", "REDUCE_ONLY","DEFAULT"). Defaults to "DEFAULT"
- 'trigger::String': Trigger type
- 'priceBound::Union{Nothing,String}': worst price for filling
- 'TP', 'SL', 'tSL': a NamedTuple with order-on-fill details. Valid values are 'price::Real', 'distance::Real', 'timeInForce::String' and 'gtdTime::String'
- 'clientExt'(not implemented)
- 'tradeExt' (not implemented)
"""

function nonMarketOrder(config, type::String, instrument::String, units::Real, price::Real;
    TIF::String = "GTC", gtdTime::Union{Nothing,String}=nothing, positionFill::String = "DEFAULT", trigger::String="DEFAULT",priceBound::Union{Nothing,String}=nothing,
    TP::NamedTuple=NamedTuple(),SL::NamedTuple=NamedTuple(),tSL::NamedTuple=NamedTuple(),
    clientExt::NamedTuple=NamedTuple(),tradeExt::NamedTuple=NamedTuple())

    o = orderRequest()

    o.type = type
    o.instrument = instrument
    o.units = units
    o.price = price
    o.timeInForce = TIF
    o.priceBound = priceBound
    !isnothing(gtdTime) && (o.gtdTime = Dates.format(gtdTime,"yyyy-mm-ddTHH:MM:SS.sss000000Z"))
    o.positionFill = positionFill
    o.triggerCondition = trigger

    if !isempty(TP)
        TPdetails = takeProfit()
        haskey(TP, :price) && (TPdetails.price = TP.price)
        haskey(TP, :timeInForce) && (TPdetails.timeInForce = TP.timeInForce)
        haskey(TP, :gtdTime) && (TPdetails.price = Dates.format(TP.gtdTime,"yyyy-mm-ddTHH:MM:SS.sss000000Z"))

        o.takeProfitOnFill = TPdetails
    end

    if !isempty(SL)
        SLdetails = stopLoss()
        haskey(SL, :price) && (SLdetails.price = SL.price)
        haskey(SL, :distance) && (SLdetails.distance = SL.distance)
        haskey(SL, :timeInForce) && (SLdetails.timeInForce = SL.timeInForce)
        haskey(SL, :gtdTime) && (SLdetails.price = Dates.format(SL.gtdTime,"yyyy-mm-ddTHH:MM:SS.sss000000Z"))

        o.stopLossOnFill = SLdetails
    end

    if !isempty(tSL)
        tSLdetails = trailingStopLoss()
        haskey(tSL, :distance) && (tSLdetails.distance = tSL.distance)
        haskey(tSL, :timeInForce) && (tSLdetails.timeInForce = tSL.timeInForce)
        haskey(tSL, :gtdTime) && (tSLdetails.price = Dates.format(tSL.gtdTime,"yyyy-mm-ddTHH:MM:SS.sss000000Z"))

        o.trailingStopLossOnFill = tSLdetails
    end

    # TODO: Client Extensions

    data = order2send(o)

    r = HTTP.post(string("https://",config.hostname,"/v3/accounts/",config.account,"/orders",),
    ["Authorization" => string("Bearer ", config.token), "Content-Type" => "application/json", ],
    JSON3.write(data),)

    return JSON3.read(r.body,Dict{String,Any})
end

# limit order -----------------------------------------------------------------------
"""

    limitOrder(config, instrument, units, price;[TIF, positionFill, priceBound, TP ,SL ,tSL, clientExt ,tradeExt])

Places a limit Order

#Arguments
- 'config::config': a valid struct with user configuration data
- 'instrument::String': a valid instrument (e.g. "EUR_USD")
- 'units::String': units to buy (positive value) or sell (negative value)
- 'price::Real'

# Keyword Arguments
- 'TIF::String' : timeinForce value ("GTC","GTD","GFD","FOK","IOC")
- 'positionFill::String' : how positions are modified when the order is filled ("OPEN_ONLY", "REDUCE_FIRST", "REDUCE_ONLY","DEFAULT"). Defaults to "DEFAULT"
- 'priceBound::String': worst price for filling
- 'TP', 'SL', 'tSL' : a NamedTuple with order-on-fill details. Valid values are 'price::Real', 'distance::Real', 'timeInForce::String' and 'gtdTime::String'
- 'clientExt'(not implemented)
- 'tradeExt' (not implemented)

#Examples

   limitOrder(userData,"EUR_USD",100, 1.10)
   limitOrder(userData,"EUR_JPY",100,117,SL=(distance=1,),TP=(price=12,),tSL=(distance=3,)) #Do not forget the comma for single value NamedTuple
"""
limitOrder(config, instrument::String, units::Real, price::Real;
                    TIF::String = "GTC", gtdTime::Union{Nothing,String}=nothing, positionFill::String = "DEFAULT", trigger::String="DEFAULT",
                    TP::NamedTuple=NamedTuple(),SL::NamedTuple=NamedTuple(),tSL::NamedTuple=NamedTuple(),
                    clientExt::NamedTuple=NamedTuple(),tradeExt::NamedTuple=NamedTuple()) =
        nonMarketOrder(config, "LIMIT", instrument, units, price;
                   TIF=TIF, gtdTime=gtdTime, positionFill=positionFill, trigger=trigger,
                   TP=TP, SL=SL ,tSL=tSL, clientExt=clientExt, tradeExt=tradeExt)

 # stop order -----------------------------------------------------------------------
"""
    stopOrder(config, instrument, units, price;[TIF, positionFill, priceBound, TP ,SL ,tSL, clientExt ,tradeExt])

Places a stop Order

#Arguments
- 'config::config': a valid struct with user configuration data
- 'instrument::String': a valid instrument (e.g. "EUR_USD")
- 'units::String': units to buy (positive value) or sell (negative value)
- 'price::Real'

# Keyword Arguments
- 'TIF::String' : timeinForce value ("GTC","GTD","GFD","FOK","IOC")
- 'positionFill::String' : how positions are modified when the order is filled ("OPEN_ONLY", "REDUCE_FIRST", "REDUCE_ONLY","DEFAULT"). Defaults to "DEFAULT"
- 'priceBound::String': worst price for filling
- 'TP', 'SL', 'tSL' : a NamedTuple with order-on-fill details. Valid values are 'price::Real', 'distance::Real', 'timeInForce::String' and 'gtdTime::String'
- 'clientExt'(not implemented)
- 'tradeExt' (not implemented)

#Examples

  stopOrder(userData,"EUR_USD",100, 1.10)
  stopOrder(userData,"EUR_JPY",100,117,SL=(distance=1,),TP=(price=12,),tSL=(distance=3,)) #Do not forget the comma for single value NamedTuple
"""
stopOrder(config, instrument::String, units::Real, price::Real;
                   TIF::String = "GTC", gtdTime::Union{Nothing,String}=nothing, positionFill::String = "DEFAULT", trigger::String="DEFAULT", priceBound::Union{Nothing,String}=nothing,
                   TP::NamedTuple=NamedTuple(),SL::NamedTuple=NamedTuple(),tSL::NamedTuple=NamedTuple(),
                   clientExt::NamedTuple=NamedTuple(),tradeExt::NamedTuple=NamedTuple()) =
       nonMarketOrder(config, "STOP", instrument, units, price;
                  TIF=TIF, gtdTime=gtdTime, positionFill=positionFill, trigger=trigger, priceBound = priceBound,
                  TP=TP, SL=SL ,tSL=tSL, clientExt=clientExt, tradeExt=tradeExt)

# market if touched order -----------------------------------------------------------------------
"""
marketIfTouchedOrder(config, instrument, units, price;[TIF, positionFill, priceBound, TP ,SL ,tSL, clientExt ,tradeExt])

Places a market-if-touched Order

#Arguments
- 'config::config': a valid struct with user configuration data
- 'instrument::String': a valid instrument (e.g. "EUR_USD")
- 'units::String': units to buy (positive value) or sell (negative value)
- 'price::Real'

# Keyword Arguments
- 'TIF::String' : timeinForce value ("GTC","GTD","GFD","FOK","IOC")
- 'positionFill::String' : how positions are modified when the order is filled ("OPEN_ONLY", "REDUCE_FIRST", "REDUCE_ONLY","DEFAULT"). Defaults to "DEFAULT"
- 'priceBound::String': worst price for filling
- 'TP', 'SL', 'tSL' : a NamedTuple with order-on-fill details. Valid values are 'price::Real', 'distance::Real', 'timeInForce::String' and 'gtdTime::String'
- 'clientExt'(not implemented)
- 'tradeExt' (not implemented)

#Examples

  marketifTouchedOrder(userData,"EUR_uSD",100, 1.10)
  marketifTouchedOrder(userData,"EUR_JPY",100,117,SL=(distance=1,),TP=(price=12,),tSL=(distance=3,)) #Do not forget the comma for single value NamedTuple
"""
marketIfTouchedOrder(config, instrument::String, units::Real, price::Real;
                   TIF::String = "GTC", gtdTime::Union{Nothing,String}=nothing, positionFill::String = "DEFAULT", trigger::String="DEFAULT", priceBound::Union{Nothing,String}=nothing,
                   TP::NamedTuple=NamedTuple(),SL::NamedTuple=NamedTuple(),tSL::NamedTuple=NamedTuple(),
                   clientExt::NamedTuple=NamedTuple(),tradeExt::NamedTuple=NamedTuple()) =
       nonMarketOrder(config, "MARKET_IF_TOUCHED", instrument, units, price;
                  TIF=TIF, gtdTime=gtdTime, positionFill=positionFill, trigger=trigger, priceBound = priceBound,
                  TP=TP, SL=SL ,tSL=tSL, clientExt=clientExt, tradeExt=tradeExt)

 # related Orders (Stop loss, take profit, trailing stop loss) -----------------------------------------------------------------------

 """
     relatedOrder(config, tradeID, type, detail)

 Places a stop loss, take profit or trailing stop loss to an open trade (not order)

#Arguments
- 'config::config': a valid struct with user configuration data
- 'tradeID::Union{Int,String}': a valid open trade ID (e.g. "123")
- 'type::String' : type of the order "STOP_LOSS", "TAKE_PROFIT" or "TRAILING_STOP_LOSS"
- 'details::NamedTuple': a NamedTuple with order-on-fill details. Valid values are 'price::Real', 'distance::Real', 'timeInForce::String' and 'gtdTime::String'

 #Examples

    relatedOrder(config, "156", "STOP_LOSS", details=(distance=0.1,)) #Do not forget the comma for single value NamedTuple
 """
function relatedOrder(config, tradeID::Union{Int,String}, type::String, details::NamedTuple=NamedTuple() )

    o = orderRequest()

    o.type = type
    o.tradeID = string(tradeID)
    o.timeInForce = "GTC"

    haskey(details, :price) && (o.price = details.price)
    haskey(details, :distance) && (o.distance = details.distance)
    haskey(details, :timeInForce) && (o.timeInForce = details.timeInForce)
    haskey(details, :gtdTime) && (o.price = Dates.format(details.gtdTime,"yyyy-mm-ddTHH:MM:SS.sss000000Z"))

    data = order2send(o)

    r = HTTP.post(string("https://",config.hostname,"/v3/accounts/",config.account,"/orders",),
        ["Authorization" => string("Bearer ", config.token), "Content-Type" => "application/json", ],
        JSON3.write(data),)

    return JSON3.read(r.body,Dict{String,Any})
end

# ------------------------------------------------------------------------------------
# /accounts/{accountID}/orders GET Endpoint
# ------------------------------------------------------------------------------------

mutable struct orders
    orders::Array{Dict{String,Any},1}
    lastTransactionID::String

    orders() = new()
end

# Declaring JSON3 struct types
JSON3.StructType(::Type{orders}) = JSON3.Mutable()

"Recursive coersion of order Dictionaries to proper Julia types"
function coerceOrderDict(oDict::Dict{String,Any}) #Also used in getOrder endpoints

    valueFields = ["price","priceBound", "distance","trailingStopValue","initialMaketPrice"]

    timeFields = ["createTime","gtdTime","filledTime","cancelledTime"]

    RFC = Dates.DateFormat("yyyy-mm-ddTHH:MM:SS.sssssssssZ")

    for (key, value) in oDict
        if eltype(value) == Pair{String,Any}
            oDict[key] = coerceOrderDict(oDict[key]) #Recursion for Dictionaries inside a transaction field
        elseif eltype(value) == Any #'asks' & 'bids' in 'fullPrice' have an array of liquidity, prices
            oDict[key] = collect(coerceOrderDict.(oDict[key]))
        elseif key in valueFields
            oDict[key] = parse(Float32, value)
        elseif key == "units" && value != "ALL"
            oDict[key] = parse(Float32, value)
        elseif key in timeFields
            oDict[key] = DateTime(first(value, 23), RFC)
        end
    end

    return oDict
end

"""
getOrders(config, count::Int=50; kwargs...)
getOrders(config, IDlist::Vector; kwargs...)

#Arguments
- 'config::config': a valid struct with user configuration data
- 'count::Int': number of orders to return
- 'IDlist::Vector{String}' : a vector of valid order IDs

#Keyword Arguments
- 'state::String: a string with values "PENDING", "FILLED", "TRIGGERED", "CANCELLED" or "ALL". Defaults to "PENDING"
- 'instrument::String'
- 'beforeID::String': last ID to retrieve

#Examples
    getOrders(userData,5)
    getOrders(userData,25, state="FILLED", instrument="EUR_USD")
    getOrders(userData,["123","234","345"])
"""
function getOrders(config, count::Int=50; kwargs...)

    r = HTTP.get(string("https://",config.hostname,"/v3/accounts/",config.account,"/orders",),
                        ["Authorization" => string("Bearer ", config.token)];
                        query = push!(Dict(),"count"=>count, kwargs...,),)

    temp = JSON3.read(r.body, orders)

    for dict in temp.orders
        dict = coerceOrderDict(dict)
    end

    return temp.orders
end

function getOrders(config, IDlist::Vector; kwargs...)

    r = HTTP.get(string("https://",config.hostname,"/v3/accounts/",config.account,"/orders",),
                        ["Authorization" => string("Bearer ", config.token)];
                        query = push!(Dict(),"ids" => join(IDlist,","), kwargs...,),)

    temp = JSON3.read(r.body, orders)

    for dict in temp.orders
        dict = coerceOrderDict(dict)
    end

    return temp.orders
end

# ------------------------------------------------------------------------------------
# /accounts/{accountID}/pendingOrders GET Endpoint
# ------------------------------------------------------------------------------------
"""
getPendingOrders(config)

#Examples
    getPendingOrders(userData)
"""
function getPendingOrders(config)

    r = HTTP.get(string("https://",config.hostname,"/v3/accounts/",config.account,"/pendingOrders",),
                        ["Authorization" => string("Bearer ", config.token)],)

    temp = JSON3.read(r.body, orders)

    for dict in temp.orders
        dict = coerceOrderDict(dict)
    end

    return temp.orders
end

# ------------------------------------------------------------------------------------
# /accounts/{accountID}/orders/{orderSpecifier} GET Endpoint
# ------------------------------------------------------------------------------------

mutable struct singleOrder
    order::Dict{String,Any}
    lastTransactionID::String

    singleOrder() = new()
end

JSON3.StructType(::Type{singleOrder}) = JSON3.Mutable()

"""
getOrder(config, orderID)

#Arguments
- 'config::config': a valid struct with user configuration data
- 'orderID::Union{String,Int}' : avalid order IDs

#Examples
    getOrder(userdata,"100")
"""
function getOrder(config, orderID::Union{String,Int})

    r = HTTP.get(string("https://",config.hostname,"/v3/accounts/",config.account,"/orders/",orderID),
                        ["Authorization" => string("Bearer ", config.token)],)

    temp = JSON3.read(r.body, singleOrder)
    temp.order = coerceOrderDict(temp.order)

    return temp.order
end

# ------------------------------------------------------------------------------------
# /accounts/{accountID}/orders/{orderSpecifier} PUT Endpoint
# ------------------------------------------------------------------------------------

"""
 replaceOrder(config, ID, instrument, units;[TIF, positionFill, priceBound, TP ,SL ,tSL, clientExt ,tradeExt])

#Examples

   replaceOrder(userData,165,"LIMIT","EUR_JPY",100)
   replaceOrder(userData,170,"EUR_CHF",100,SL=(distance=0.1,),TP=(price=1.12,),tSL=(distance=0.3,))
"""
function replaceOrder(config, orderID::Union{Int,String},type::String, instrument::String, units::Real, price::Real;
    TIF::String = "GTC", gtdTime::Union{Nothing,String}=nothing, positionFill::String = "DEFAULT", trigger::String="DEFAULT",priceBound::Union{Nothing,String}=nothing,
    TP::NamedTuple=NamedTuple(),SL::NamedTuple=NamedTuple(),tSL::NamedTuple=NamedTuple(),
    clientExt::NamedTuple=NamedTuple(),tradeExt::NamedTuple=NamedTuple())

    o = orderRequest()

    o.type = type
    o.instrument = instrument
    o.units = units
    o.price = price
    o.timeInForce = TIF
    o.priceBound = priceBound
    !isnothing(gtdTime) && (o.gtdTime = Dates.format(gtdTime,"yyyy-mm-ddTHH:MM:SS.sss000000Z"))
    o.positionFill = positionFill
    o.triggerCondition = trigger

    if !isempty(TP)
        TPdetails = takeProfit()
        haskey(TP, :price) && (TPdetails.price = TP.price)
        haskey(TP, :timeInForce) && (TPdetails.timeInForce = TP.timeInForce)
        haskey(TP, :gtdTime) && (TPdetails.price = Dates.format(TP.gtdTime,"yyyy-mm-ddTHH:MM:SS.sss000000Z"))

        o.takeProfitOnFill = TPdetails
    end

    if !isempty(SL)
        SLdetails = stopLoss()
        haskey(SL, :price) && (SLdetails.price = SL.price)
        haskey(SL, :distance) && (SLdetails.distance = SL.distance)
        haskey(SL, :timeInForce) && (SLdetails.timeInForce = SL.timeInForce)
        haskey(SL, :gtdTime) && (SLdetails.price = Dates.format(SL.gtdTime,"yyyy-mm-ddTHH:MM:SS.sss000000Z"))

        o.stopLossOnFill = SLdetails
    end

    if !isempty(tSL)
        tSLdetails = trailingStopLoss()
        haskey(tSL, :distance) && (tSLdetails.distance = tSL.distance)
        haskey(tSL, :timeInForce) && (tSLdetails.timeInForce = tSL.timeInForce)
        haskey(tSL, :gtdTime) && (tSLdetails.price = Dates.format(tSL.gtdTime,"yyyy-mm-ddTHH:MM:SS.sss000000Z"))

        o.trailingStopLossOnFill = tSLdetails
    end

    # TODO: Client Extensions

    data = order2send(o)

    r = HTTP.put(string("https://",config.hostname,"/v3/accounts/",config.account,"/orders/",orderID),
    ["Authorization" => string("Bearer ", config.token), "Content-Type" => "application/json", ],
    JSON3.write(data),)

    return JSON3.read(r.body,Dict{String,Any})
end

# ------------------------------------------------------------------------------------
# /accounts/{accountID}/orders/{orderSpecifier}/cancel PUT Endpoint
# ------------------------------------------------------------------------------------

"""
cancelOrder(config, ID::Union{String,Int})

#Arguments
- 'config::config': a valid struct with user configuration data
- 'orderID::Union{String,Int}' : avalid order IDs

#Examples
    cancelOrder(userdata,"100")
"""
function cancelOrder(config, ID::Union{String,Int})

    r = HTTP.put(string("https://",config.hostname,"/v3/accounts/",config.account,"/orders/",ID,"/cancel"),
                        ["Authorization" => string("Bearer ", config.token)],)

    temp = JSON3.read(r.body,Dict{String,Any})

    temp["orderCancelTransaction"]["time"] = DateTime(first(temp["orderCancelTransaction"]["time"], 23),Dates.DateFormat("yyyy-mm-ddTHH:MM:SS.sssssssssZ"))

    temp
end

# ------------------------------------------------------------------------------------
# /accounts/{accountID}/orders/{orderSpecifier}/clientExtension PUT Endpoint
# ------------------------------------------------------------------------------------

"""
    orderClientExtensions(config::config, tradeID::String; clientID::String="", tag::String="", comment::String="")

Lets add user information to a specific Trade

# Arguments
- 'config::config': a valid struct with user configuracion data
- 'tradeID::string': a valid trade ID
- clientID, tag and comment: strings with the user information

# Example

    orderClientExtensions(userconfig,"66", clientID="007",tag="foo")
"""
function orderClientExtensions(config, orderID::Union{Int,String}; clientID::String="", tag::String="", comment::String="")

    data = clientExtensions(extensions(clientID, tag, comment))

    r = HTTP.put(string("https://", config.hostname, "/v3/accounts/", config.account,"/orders/",orderID,"/clientExtensions"),
        ["Authorization" => string("Bearer ", config.token),"Content-Type" => "application/json"], JSON3.write(data))

    return JSON3.read(r.body, Dict{String,Any})

end

end #module

max_stars_repo_name: CalebDepatie/Julianda

max_forks_repo_name: CalebDepatie/Julianda


text:
run(`make MUMPS`)
include("deps.jl")

Pkg.build("MUMPS")

max_forks_repo_name: ohinder/Everest


text:
export Formula

Term(str::AbstractString) = begin
    function get_term(str)
        function_match = match(r"(\w*)\((.*)\)$", str)
        if function_match == nothing
            Variable(strip(str))
        else
            name = strip(function_match.captures[1])
            arguments = get_term.(argumentsplit(strip(function_match.captures[2])))
            Function(FunctionSymbol(name), arguments)
        end
    end
    get_term(str)
end

AtomicFormula(str::AbstractString) = begin
    formula = strip_and_remove_surrounding_brackets(str)
    atomic_formula_match = match(r"(\w*)\((.*)\)$", formula)
    name = strip(atomic_formula_match.captures[1])
    arguments = Term.(argumentsplit(strip(atomic_formula_match.captures[2])))
    AtomicFormula(PredicateSymbol(name), arguments)
end

Negation(str::AbstractString) = begin
    secondchar = nextind(str, 1)
    Negation(Formula(str[secondchar:end]))
end

EFormula(str::AbstractString) = begin
    regex = @match first(str) begin
    '?' => r"\?\{(\w+)\}(.*)"
    '∃' => r"∃(\w+)(.*)"
    end
    e_formula_match = match(regex, str)
    name = strip(e_formula_match.captures[1])
    formula = strip(e_formula_match.captures[2])
    EFormula(Variable(name), Formula(formula))
end

AFormula(str::AbstractString) = begin
    regex = @match first(str) begin
    '*' => r"\*\{(\w+)\}(.*)"
    '∀' => r"∀(\w+)(.*)"
    end
    a_formula_match = match(regex, str)
    name = strip(a_formula_match.captures[1])
    formula = strip(a_formula_match.captures[2])
    AFormula(Variable(name), Formula(formula))
end

"""
    Formula(str::AbstractString)

Parse `str` to a Formula object and return that object.
"""
Formula(str::AbstractString) = begin
    formula = strip_and_remove_surrounding_brackets(str)
    parts = strip.(bracketsplit(formula))
    current_junction = findfirst(part->ismatch(r"^(&|[|]|>|∧|∨|→)$", part), parts)
    if current_junction == 0
        @match formula[1] begin
        '?' || '∃' => return EFormula(formula)
        '*' || '∀' => return AFormula(formula)
        '~' || '¬' => return Negation(formula)
        _ => return AtomicFormula(formula)
        end
    else
        formula1 = strip(join(parts[1:current_junction-1]))
        operator = strip(join(parts[current_junction]))
        formula2 = strip(join(parts[current_junction+1:end]))
        @match operator begin
        "&" || "∧" => return Conjunction(Formula(join(formula1)), Formula(formula2))
        "|" || "∨" => return Disjunction(Formula(formula1), Formula(formula2))
        ">" || "→" => return Disjunction(Negation(Formula(formula1)), Formula(formula2))
        end
    end
end


text:
@inline _element_span(indhi, indlo) = indhi - indlo + 1

"""
    findrepeated(iter, min_seq_length::Integer)

Return an `Array` containing the indices of each maximal sequence of repeated elements in `iter` of length
not less than `min_seq_length`. The range of indices of each sequence is given by a `UnitRange`.
By construction, the output array of `UnitRanges` is sorted.

## Example
```julia
julia> a = [fill(1,3); fill("cat", 4); fill(0, 2);  5 ; fill(1,10)];

julia> findrepeated(a, 1)
5-element Array{Any,1}:
 1:3
 4:7
 8:9
 10:10
 11:20

julia> findrepeated(a, 2)
4-element Array{Any,1}:
 1:3
 4:7
 8:9
 11:20
```
"""
function findrepeated(iter, min_seq_length::Integer)
    inds = Vector{Any}()
    isempty(iter) && return inds
    newind = 1
    newx = first(iter)
    j = 0
    for (i, x) in enumerate(iter)
        j = i
        if x != newx
            last_seq_ind = i - 1
            if _element_span(last_seq_ind, newind) >= min_seq_length
                push!(inds, newind:last_seq_ind)
            end
            newind = i
            newx = x
        end
    end
    last_seq_ind = j
    if _element_span(last_seq_ind, newind) >= min_seq_length
        push!(inds, newind:last_seq_ind)
    end
    return inds
end

function compressinds!(inds)
    isempty(inds) && return inds
    inds[1] = inds[1] .- (inds[1].start - 1)
    for i in 2:length(inds)
        gap = inds[i].start - inds[i-1].stop - 1
        if gap > 0
            inds[i] = inds[i] .- gap
        end
    end
    return inds
end
compressinds(inds) = compressinds!(copy(inds))


text:
using Test
import Vol
import LinearAlgebra, DelimitedFiles

return_series = 0.01 * collect(1:50)
lambda = 0.94

@test isapprox(Vol.ewma(return_series, lambda), sqrt(Vol.ewma_canonical(return_series.^2, lambda)))
@test isapprox(Vol.ewma(0.01 * ones(100), lambda), 0.01)

r = [ 1. 2. 3.;
      3. 4. 5.;
      5. 6. 7.;
      10. 20. 30.]

@test LinearAlgebra.issymmetric(Vol.ewma(r, lambda))
@test LinearAlgebra.issymmetric(Vol.ewma_cov(r, lambda))

# the diagonal of the correlation matrix should be ones.
@test isapprox(LinearAlgebra.diag(Vol.ewma(r, lambda)), ones(3))

single_serie = [1.0, 3.0, 10.0]
single_discrete_returns = zeros(2)
single_discrete_returns[1] = (3.0-1.0)/1.0
single_discrete_returns[2] = (10.0-3.0)/3.0
@test isapprox(Vol.discrete_returns(single_serie), single_discrete_returns)

single_log_returns = zeros(2)
single_log_returns[1] = log(3.0) - log(1.0)
single_log_returns[2] = log(10.0) - log(3.0)
@test isapprox(Vol.log_returns(single_serie), single_log_returns)

two_series = [ 1.0 10.0;
               3.0 5.0;
               2.0 15.0]

two_discrete_returns=zeros(2,2)
two_discrete_returns[1,1] = (3.0-1.0)/1.0
two_discrete_returns[2,1] = (2.0-3.0)/3.0
two_discrete_returns[1,2] = (5.0-10.0)/10.0
two_discrete_returns[2,2] = (15.0-5.0)/5.0
@test isapprox(Vol.discrete_returns(two_series), two_discrete_returns)

two_log_returns=zeros(2,2)
two_log_returns[1,1] = log(3.0) - log(1.0)
two_log_returns[2,1] = log(2.0) - log(3.0)
two_log_returns[1,2] = log(5.0) - log(10.0)
two_log_returns[2,2] = log(15.0) - log(5.0)
@test isapprox(Vol.log_returns(two_series), two_log_returns)

@test isapprox(Vol.discrete_returns(r)[1:end, 1], Vol.discrete_returns(r[1:end, 1]))
@test isapprox(Vol.log_returns(r)[1:end, 1], Vol.log_returns(r[1:end, 1]))

single_return = [0.05, 0.01, 0.10, -0.02, -0.10, 0.0]
lambda = 0.94
ewma_canonical_single_return = (0.0 * 1 + (-0.10)*lambda + (-0.02)*(lambda^2) + 0.10*(lambda^3) + 0.01*(lambda^4) + 0.05*(lambda^5)) / (1 + lambda + lambda^2 + lambda^3 + lambda^4 + lambda^5)
@test isapprox(Vol.ewma_canonical(single_return, lambda), ewma_canonical_single_return)

ewma_single_return = sqrt( ((0.0^2) * 1 + ((-0.10)^2)*lambda + ((-0.02)^2)*(lambda^2) + (0.10^2)*(lambda^3) + (0.01^2)*(lambda^4) + (0.05^2)*(lambda^5)) / (1 + lambda + lambda^2 + lambda^3 + lambda^4 + lambda^5))
@test isapprox(Vol.ewma(single_return, lambda), ewma_single_return)

# tests cov -> correl
three_returns = [ 0.1 0.3 0.2 ;
                  0.02 0.03 0.0;
                  0.3  0.3  0.3;
                  0.2  0.0  0.1]

lambda = 0.94

covmatrix = Vol.ewma_cov(three_returns, lambda)
vol_array = Vector{Float64}()
for i in 1:3
    push!(vol_array, Vol.ewma(three_returns[:, i], lambda))
end

corrmatrix = Vol.ewma(three_returns, lambda)
for i in 1:3
    for j in 1:3
        @test isapprox(corrmatrix[i,j], covmatrix[i,j]/(vol_array[i]*vol_array[j]))
    end
end

# Diagonal of the covmatrix should be squared volatilities
@test isapprox(sqrt.(LinearAlgebra.diag(covmatrix)), [Vol.ewma(three_returns[:,i], lambda) for i in 1:3 ])

# market prices
lambda = 0.94
(raw_data, table_header) = DelimitedFiles.readdlm("prices.csv", ',', header=true)
prices = raw_data[:, 4:end]
(rows, cols) = size(prices)
returns = Vol.log_returns(prices)
covmatrix = Vol.ewma_cov(returns, lambda)
corrmatrix = Vol.ewma(returns, lambda)

@test LinearAlgebra.issymmetric(covmatrix)
@test LinearAlgebra.issymmetric(corrmatrix)
@test isapprox(sqrt.(LinearAlgebra.diag(covmatrix)), [Vol.ewma(returns[:,i], lambda) for i in 1:cols ])
@test isapprox(LinearAlgebra.diag(corrmatrix), ones(cols))


text:
"""
"""
function tuplify end

tuplify(x::Any)::Tuple = (x,)

tuplify(x::Tuple)::Tuple = x