source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Sequence.cs @ 11742

Last change on this file since 11742 was 11742, checked in by gkronber, 6 years ago

#2283 refactoring

File size: 5.6 KB
Line 
1using System;
2using System.Collections;
3using System.Collections.Generic;
4using System.Diagnostics;
5using System.Linq;
6using System.Text;
7using System.Threading.Tasks;
8
9namespace HeuristicLab.Problems.GrammaticalOptimization {
10  // represents a sequence of symbols (non-terminal and terminal symbols)
11  // a sequence consisting only of terminal symbols can be a sentence of a language
12  // the class supports in-place manipulation of the sequence symbols (replace NT with another sequence)
13  // sequences provide efficient support left-canonical derivation by storing the index of the first non-terminal symbol
14  // maximal length of sequences is limited to 1000 symbols
15
16  // for symbols the same assumptions for the implementation of grammars apply
17  // - non-terminal symbols must be characters in the range [A..Z]
18  // - terminal symbols can be almost all other characters
19  public class Sequence : IEnumerable<char> {
20    private const int maxIdx = 200;
21
22    private int len;
23    private int idxOfFirstNt;
24    private readonly char[] symbols;
25
26    public char this[int idx] {
27      get { return symbols[idx]; }
28      set { throw new NotSupportedException(); }
29    }
30
31    public int Length {
32      get { return len; }
33      private set { len = value; }
34    }
35
36    public bool IsTerminal {
37      get { return idxOfFirstNt == -1; }
38    }
39
40    public int FirstNonTerminalIndex {
41      get { return idxOfFirstNt; }
42    }
43
44    public char FirstNonTerminal {
45      get { return symbols[idxOfFirstNt]; }
46    }
47
48    private Sequence(int maxLength) {
49      this.symbols = new char[maxLength];
50    }
51
52    // create a sequence from a character
53    public Sequence(char ch)
54      : this(ch, maxIdx + 1) {
55    }
56
57    protected Sequence(char ch, int maxLength)
58      : this(maxLength) {
59      this.len = 1;
60      symbols[0] = ch;
61
62      if (ch >= 'A' && ch <= 'Z') idxOfFirstNt = 0;
63      else idxOfFirstNt = -1;
64    }
65
66    // create a sequence from a string
67    public Sequence(string s) : this(s, maxIdx + 1) { }
68    protected Sequence(string s, int maxLength)
69      : this(maxLength) {
70      if (string.IsNullOrEmpty(s)) throw new ArgumentException();
71      if (s.Length > (maxIdx + 1)) throw new ArgumentException();
72      this.len = s.Length;
73      this.idxOfFirstNt = -1;
74
75      for (int i = 0; i < len; i++) {
76        symbols[i] = s[i];
77        if (idxOfFirstNt == -1 && symbols[i] >= 'A' && symbols[i] <= 'Z') {
78          idxOfFirstNt = i;
79        }
80      }
81    }
82
83    // cloning ctor
84    public Sequence(Sequence original) : this(original, maxIdx + 1) { }
85    protected Sequence(Sequence original, int maxLength)
86      : this(maxLength) {
87      this.len = original.len;
88      Array.Copy(original.symbols, this.symbols, len);
89      this.idxOfFirstNt = original.idxOfFirstNt;
90    }
91
92    public virtual void ReplaceAt(int position, int len, Sequence replacement) {
93      if (replacement == null) throw new ArgumentNullException();
94      if (len <= 0) throw new ArgumentException();
95      if (position + len >= maxIdx) throw new ArgumentException();
96      if (Length - len + replacement.Length > (maxIdx + 1)) throw new ArgumentException();
97      var lenDelta = replacement.Length - len;
98      var remainingPartLen = Length - position - len;
99      var startIdxOfRemainingPart = position + len + lenDelta;
100      Array.Copy(symbols, position + len, symbols, startIdxOfRemainingPart, remainingPartLen);
101      Array.Copy(replacement.symbols, 0, symbols, position, replacement.Length);
102
103      this.len = Length + lenDelta;
104      // when the first part contains an NT then it's not necessary to update the index
105      if (idxOfFirstNt >= 0 && idxOfFirstNt < position) return;
106      // if the replacement contains an NT then we can directly calculate the idx of that NT in the new sequence
107      if (replacement.idxOfFirstNt >= 0) {
108        this.idxOfFirstNt = position + replacement.idxOfFirstNt;
109      } else {
110        // otherwise we must find the first NT in the remaining part
111        idxOfFirstNt = -1;
112        for (int i = startIdxOfRemainingPart; idxOfFirstNt == -1 && i < Length; i++) {
113          if (symbols[i] >= 'A' && symbols[i] <= 'Z') idxOfFirstNt = i;
114        }
115      }
116    }
117
118    public IEnumerator<char> GetEnumerator() {
119      return symbols.AsEnumerable().Take(len).GetEnumerator();
120    }
121
122    public override string ToString() {
123      var sb = new StringBuilder(len);
124      sb.Append(symbols, 0, len);
125      return sb.ToString();
126    }
127
128    IEnumerator IEnumerable.GetEnumerator() {
129      return GetEnumerator();
130    }
131
132    public Sequence Subsequence(int startIdx, int len) {
133      if (startIdx < 0 || len < 0) throw new ArgumentException();
134      if (startIdx >= this.len) throw new ArgumentException();
135      if (startIdx + len > this.len) throw new ArgumentException();
136      var subsequence = new Sequence(maxIdx + 1) { len = len };
137
138      Array.Copy(this.symbols, startIdx, subsequence.symbols, 0, len);
139      if (idxOfFirstNt < 0) {
140        subsequence.idxOfFirstNt = -1;
141      } else if (idxOfFirstNt < startIdx) {
142        // need to find first nt in subsequence
143        subsequence.idxOfFirstNt = -1;
144        for (int i = 0; subsequence.idxOfFirstNt == -1 && i < len; i++) {
145          if (subsequence.symbols[i] >= 'A' && subsequence.symbols[i] <= 'Z') subsequence.idxOfFirstNt = i;
146        }
147      } else if (idxOfFirstNt >= startIdx && idxOfFirstNt < startIdx + len) {
148        subsequence.idxOfFirstNt = idxOfFirstNt;
149      } else {
150        Debug.Assert(idxOfFirstNt >= startIdx + len);
151        subsequence.idxOfFirstNt = -1;
152      }
153      return subsequence;
154    }
155  }
156}
Note: See TracBrowser for help on using the repository browser.