Treeview에서 가장 작은 변경 사항을 결정하십시오.

Question

사용자가 이동하고, 하위 트리를 삭제하고, 노드를 만들고, 노드를 작성할 수있는 트리 뷰가 있습니다.

모든 작업을 한 번에 지속하고 싶지 않지만 사용자가 "내 변경 적용"이라고 말할 수 있습니다. 따라서 새 트리를 오래된 트리와 비교해야하며 가장 중요한 것은 새 트리를 작성하기위한 가장 작은 작업 집합을 결정하는 것입니다. 이 문제에 대한 접근 방법은 무엇입니까?

ASP.NET/C#을 사용하고 있지만이 기술에 대한 의문은별로 없습니다.

는 svick 말한다처럼 당신이

Answer 1

두 가지 방법으로 문제를 해결할 수 있습니다. 모든 사용자의 편집 작업을 캐시 한 다음 일괄 업데이트로 적용 할 수 있습니다. 이것은 목표의 "즉시"부분을 다룹니다.

사용자 작업을 동일한 결과를 생성하는 최적의 동작 집합 ("최적"의 정의에 따라)으로 대체하려는 경우 일반적으로이를 해결하는 것이 매우 어렵습니다. 내가 알고있는 가장 잘 알려진 알고리즘은 "나무 사이의 거리를 편집하는 것"이라고 불리는 것을 기반으로하며 technical report by Zhang and Shasha에 설명되어 있습니다. 이것은 매우 조밀 한 독서임을 경고하십시오. 하나의 XML 문서를 다른 것으로 변경하기위한 최적의 편집 스크립트를 찾기위한 훨씬 더 읽기 쉬운 문서 here이 있습니다. XML을 나무로 변환하고 작업하기 때문에 코어 알고리즘이 문제에 직접 적용될 수 있습니다. 심지어 의사 코드도 함께 제공됩니다.

Answer 2

, 최고의 옵션은 모든 변경 사항을 기록하고 사용자가 "적용"버튼을 클릭 할 때 적용하는 것입니다 감사합니다.

개선 할 수있는 유일한 점은 사용자가 변경을하면이 새로운 변경으로 인해 무효화 된 변경 사항이 있는지 기록에서 확인할 수 있다는 것입니다. 이 경우 하나 이상의 항목을 삭제할 수 있습니다. 내가 생각할 수 예는 두 번째로 노드를 이동

이

• 첫 악장
• 최근에 생성 된 노드를 삭제하고 그 반대의 경우도 마찬가지을 부정한다. 이 경우 새 레코드 항목도 제거해야합니다.
• 노드를 삭제하고 다른 노드 (또는 동일한 크기의 서브 트리)를 작성하기

이 기록 항목의 최소량과 최적 용액 있지만 아마도 목적을 제공하지 않는 이동에 의해 대체 될 수있다 변경 사항 적용 속도를 높이는 것입니다. 단순화 될 수있는 다른 종류의 조작 순서를 감지 할 수는 있지만 그럴 가치가 없을 것입니다. 이러한 복잡한 조작 순서를 감지하는 것은 유익하기에 너무 비싸다.

Answer 3

글쎄, 나는 작업을 통합하는 것이 가장 좋은 옵션이라고 생각하며, 제 경우에는 비 최적 솔루션이 생성되는 시나리오를 생각할 수 없습니다. 누군가가 실제로 관심이 있다면 여기 내 통합 코드를 공유 :

public class TreeOperationConsolidator : ITreeOperationConsolidator 
{ 
    public IEnumerable<ITreeOperation> ConsolidateOperations(IEnumerable<ITreeOperation> operations) 
    { 
     List<ITreeOperation> result = new List<ITreeOperation>(); 
     foreach (var op in operations) 
     { 
      if (op.Operation == OperationType.Move) 
      { 
       ConsolidateMoveOperation(op, operations, result); 
      } 
      else if (op.Operation == OperationType.Rename) 
      { 
       ConsolidateRenameOperation(op, operations, result); 
      } 
      else if (op.Operation == OperationType.Create) 
      { 
       ConsolidateCreateOperation(op, operations, result); 
      } 
      else if (op.Operation == OperationType.Delete) 
      { 
       ConsolidateDeleteOperation(op, operations, result); 
      } 
     } 
     return result; 
    } 

    private void ConsolidateDeleteOperation(ITreeOperation op, IEnumerable<ITreeOperation> operations, List<ITreeOperation> result) 
    { 
     bool newlyCreated = result.Any(o => o.SourceId == op.SourceId && o.Operation == OperationType.Create); 

     result.RemoveAll(o => o.SourceId == op.SourceId); 

     var children = (from o in result 
         where 
          (o.Operation == OperationType.Move && o.DestId == op.SourceId) 
          || (o.Operation == OperationType.Create && o.DestId == op.SourceId) 
         select o).ToList(); 

     foreach (var child in children) 
     { 
      result.Remove(child); 
      ConsolidateDeleteOperation(new TreeOperation { Operation = OperationType.Temp, SourceId = child.SourceId }, operations, result); 
     } 

     if (newlyCreated == false && op.Operation != OperationType.Temp) 
      result.Add(op); 
    } 

    private void ConsolidateCreateOperation(ITreeOperation op, IEnumerable<ITreeOperation> operations, List<ITreeOperation> result) 
    { 
     result.Add(op); 
    } 

    private void ConsolidateRenameOperation(ITreeOperation op, IEnumerable<ITreeOperation> operations, List<ITreeOperation> result) 
    { 
     var createOperation = result.FirstOrDefault(o => o.SourceId == op.SourceId && o.Operation == OperationType.Create); 
     if (createOperation == null) 
     { 
      var renameOp = result.FirstOrDefault(o => o.SourceId == op.SourceId && o.Operation == op.Operation); 
      if (renameOp != null) 
      { 
       result.Remove(renameOp); 
      } 
      result.Add(op); 
     } 
     else 
     { 
      createOperation.Argument = op.Argument; 
     } 
    } 

    protected void ConsolidateMoveOperation(ITreeOperation op, IEnumerable<ITreeOperation> operations, List<ITreeOperation> result) 
    { 
     var createOperation = result.FirstOrDefault(o => o.SourceId == op.SourceId && o.Operation == OperationType.Create); 
     if (createOperation == null) 
     { 
      var moveOp = result.FirstOrDefault(o => o.SourceId == op.SourceId && o.Operation == op.Operation); 
      if (moveOp != null) 
      { 
       result.Remove(moveOp); 
      } 
      result.Add(op); 
     } 
     else 
     { 
      createOperation.DestId = op.DestId; 
     } 
    } 
} 

public class TreeOperation : ITreeOperation 
{ 
    public string Argument { get; set; } 

    public OperationType Operation { get; set; } 

    public string SourceId { get; set; } 

    public string DestId { get; set; } 
} 

public enum OperationType 
{ 
    Move, 
    Rename, 
    Create, 
    Delete, 
    Temp 
} 

public interface ITreeOperationConsolidator 
{ 
    IEnumerable<ITreeOperation> ConsolidateOperations(IEnumerable<ITreeOperation> operations); 
} 

public interface ITreeOperation 
{ 
    string Argument { get; set; } 

    OperationType Operation { get; set; } 

    string SourceId { get; set; } 

    string DestId { get; set; } 
} 

그래서 당신이해야 할 일을 트리에있는 모든 사용자의 활동을 추적하는 것입니다 (즉, 다른 곳 세션에서 ITreeOperation의 인스턴스를 저장 (또는). 모든 변경 사항을 적용하기 전에 IEnumerable<ITreeOperation> ConsolidateOperations(IEnumerable<ITreeOperation> operations)으로 전화하십시오.