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

Last change on this file since 11730 was 11730, checked in by gkronber, 5 years ago

#2283: several major extensions for grammatical optimization

File size: 5.3 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() {
49      this.symbols = new char[maxIdx + 1];
50    }
51
52    // create a sequence from a character
53    public Sequence(char ch)
54      : this() {
55      this.len = 1;
56      symbols[0] = ch;
57
58      if (ch >= 'A' && ch <= 'Z') idxOfFirstNt = 0;
59      else idxOfFirstNt = -1;
60    }
61
62    // create a sequence from a string
63    public Sequence(string s)
64      : this() {
65      if (string.IsNullOrEmpty(s)) throw new ArgumentException();
66      if (s.Length > (maxIdx + 1)) throw new ArgumentException();
67      this.len = s.Length;
68      this.idxOfFirstNt = -1;
69
70      for (int i = 0; i < len; i++) {
71        symbols[i] = s[i];
72        if (idxOfFirstNt == -1 && symbols[i] >= 'A' && symbols[i] <= 'Z') {
73          idxOfFirstNt = i;
74        }
75      }
76    }
77
78    // cloning ctor
79    public Sequence(Sequence original)
80      : this() {
81      this.len = original.len;
82      Array.Copy(original.symbols, this.symbols, len);
83      this.idxOfFirstNt = original.idxOfFirstNt;
84    }
85
86    public void ReplaceAt(int position, int len, Sequence replacement) {
87      if (replacement == null) throw new ArgumentNullException();
88      if (len <= 0) throw new ArgumentException();
89      if (position + len >= maxIdx) throw new ArgumentException();
90      if (Length - len + replacement.Length > (maxIdx + 1)) throw new ArgumentException();
91      var lenDelta = replacement.Length - len;
92      var remainingPartLen = Length - position - len;
93      var startIdxOfRemainingPart = position + len + lenDelta;
94      Array.Copy(symbols, position + len, symbols, startIdxOfRemainingPart, remainingPartLen);
95      Array.Copy(replacement.symbols, 0, symbols, position, replacement.Length);
96
97      this.len = Length + lenDelta;
98      // when the first part contains an NT then it's not necessary to update the index
99      if (idxOfFirstNt >= 0 && idxOfFirstNt < position) return;
100      // if the replacement contains an NT then we can directly calculate the idx of that NT in the new sequence
101      if (replacement.idxOfFirstNt >= 0) {
102        this.idxOfFirstNt = position + replacement.idxOfFirstNt;
103      } else {
104        // otherwise we must find the first NT in the remaining part
105        idxOfFirstNt = -1;
106        for (int i = startIdxOfRemainingPart; idxOfFirstNt == -1 && i < Length; i++) {
107          if (symbols[i] >= 'A' && symbols[i] <= 'Z') idxOfFirstNt = i;
108        }
109      }
110    }
111
112    public IEnumerator<char> GetEnumerator() {
113      return symbols.AsEnumerable().Take(len).GetEnumerator();
114    }
115
116    public override string ToString() {
117      var sb = new StringBuilder(len);
118      sb.Append(symbols, 0, len);
119      return sb.ToString();
120    }
121
122    IEnumerator IEnumerable.GetEnumerator() {
123      return GetEnumerator();
124    }
125
126    public Sequence Subsequence(int startIdx, int len) {
127      if (startIdx < 0 || len <= 0) throw new ArgumentException();
128      if (startIdx >= this.len) throw new ArgumentException();
129      if (startIdx + len > this.len) throw new ArgumentException();
130      var subsequence = new Sequence {len = len};
131
132      Array.Copy(this.symbols, startIdx, subsequence.symbols, 0, len);
133      if (idxOfFirstNt < 0) {
134        subsequence.idxOfFirstNt = -1;
135      } else if (idxOfFirstNt < startIdx) {
136        // need to find first nt in subsequence
137        subsequence.idxOfFirstNt = -1;
138        for (int i = 0; subsequence.idxOfFirstNt == -1 && i < len; i++) {
139          if (subsequence.symbols[i] >= 'A' && subsequence.symbols[i] <= 'Z') subsequence.idxOfFirstNt = i;
140        }
141      } else if (idxOfFirstNt >= startIdx && idxOfFirstNt < startIdx + len) {
142        subsequence.idxOfFirstNt = idxOfFirstNt;
143      } else {
144        Debug.Assert(idxOfFirstNt >= startIdx + len);
145        subsequence.idxOfFirstNt = -1;
146      }
147      return subsequence;
148    }
149  }
150}
Note: See TracBrowser for help on using the repository browser.